메모리 관리에 대한 내용 시작!

메모리는 주소를 통해 접근하는 매체이다. 그래서 메모리에는 주소가 매겨진다. 그 주소는 두가지로 나눌 수 있다.

Logical Address vs Physical Address

Logical Address (=virtual address)

프로그램이 실행되면 프로그램 마다 독자적인 주소공간이 생기는데 이런 식으로 프로그램마다 가지고 있는 메모리 공간을 Logical address라한다.
각 프로세스마다 0번지부터 시작된다. CPU가 보는 주소는 논리적 주소이다.

Physical address

메모리에 프로그램이 실제로 올라가는 위치이다.
물리적인 메모리는 하나로, 0번지부터 통으로 관리가 되기 때문에 메모리의 하위주소 부분에는 os 커널이 올라가 있고 상위주소에는 여러 프로그램이 섞여 올라가 있다.

주소 바인딩

주소 바인딩은 symbolic address → logical address → physical address으로 변환하는 과정 중에서 logical address → physical address 로 바뀌는 부분이다.
즉 어떤 프로그램이 물리적인 메모리 어디로 올라갈지 메모리 주소를 정하는 것이다.

symbolic address란? 프로그래밍할 때 "메모리 몇번지에 저장해!" 라는 식으로 하는 것이 아니라 변수의 이름을 주고, 함수 역시 "몇번지로 점프해!" 라 하지 않고 함수 이름으로 호출한다. 즉 프로그래머 입장에서 숫자가 아니라 symbol로 된 주소를 사용한다. 이를 symbolic address라고 표현. 이게 컴파일 되면 0번지부터 시작되는 그 프로그램의 독자적인 Logical address로 바뀌는 것이다.

그럼 주소 바인딩은 언제 일어날까? (다음 내용)

compile time binding

이 방식은 컴파일 시에 주소 변환이 일어나는 방식이다.

논리적 주소가 곧 물리적 주소가 되기 때문에 컴파일러가 absolute code를 생성한다고 한다. 만약 메모리에 올라간 위치를 바꾸고 싶다면 compile을 다시 해야만 한다.

load time binding

이 방식은 실행이 시작될 때 주소 변환이 일어나는 방식이다.

컴파일해서 만들어지는 코드가 재배치 가능 코드(relocatable code)로, 실행 시에 어느 위치든지 올라갈 수 있는 코드를 의미한다.

Run time binding 역시 이에 해당한다.

execution time binding (= run time binding)

수행이 시작된 후에도 프로세스의 메모리 상 위치(물리적 주소)를 옮길 수 있는 방법이다.

프로그램 실행 중에도 주소가 바뀐다. 따라서 CPU가 주소를 참조할 때마다 binding을 점검해야 한다. (address mapping table)

즉 이 내용이 물리적 메모리에 어디 올라가 있는지 그때그때 주소변환 해야 한다. 그러기 위해서는 하드웨어 적인 지원이 필요하다. (ex. base and limit registers, MMU) MMU라는 하드웨어가 이를 담당한다.

그림으로 주소 바인딩 이해하기

=> 위의 세가지 방식은 아래와 같은 그림으로 비교하면 이해하기 쉽다.

소스코드는 symbolic address로 작성되어 있다.

소스코드가 컴파일 되면 symbolic address(A,B,C)가 숫자로 된 logical address로 바뀐다. 이는 프로그램마다 독자적으로 가지는 주소이다. 이 과정이 완료되면 각각의 문장들이 메모리의 0, 10, 20, 30, 40 번지에 들어간다.

실행이 되려면 물리적인 메모리에 올라가야 한다. 이렇게 physical address가 결정되는 것을 주소바인딩이라고 부른다.

compile time binding

compile time binding은 compile 시점에 이미 physical address가 결정되는 것을 말한다.

컴파일 때 logical address를 정하는데 이 경우에는 logical address에 대응되는 physical address에 올린다. 그래서 다른 physical address 비어있어도 항상 0부터 올라간다. 그렇기 때문에 매우 비효율적이다. 예전에 컴퓨터에서 프로그램을 하나만 실행시켰을 때는 이런 방법을 사용하기도 했지만 이제는 사용하지 않는다.

load time binding

load time binding은 프로그램이 시작되어 메모리에 올라갈 때 physical address가 결정되는 것이다.

컴파일 타임에는 논리적인 주소만 정해진 상태에서 실행시켜서 물리적 주소 중에 비어있는 주소부터 메모리를 올린다.

run time binding

run time binding은 load time binding처럼 실행 시 물리적 주소가 결정된다.

그런데 이 물리적 주소가 실행 중에 바뀔 수 있다는 점에서 차이가 있다.
현대 컴퓨터에서 사용하는 방법은 run time binding이다.

CPU 가 바라보는 주소는?
CPU가 바라보는 주소는 logical address이다. 그 이유는 컴파일해서 실행파일에 올라간 instruction code 내용에 있는 address가 logical address이기 때문이다. 그리고 물리적 메모리에 올라갈 때 코드 상의 주소는 Logical address로 남아있기 때문에 (바꾸려면 컴파일을 다시 해야하기 때문에 그대로 남아있다.) CPU 가 바라보는 주소는 logical address일 수 밖에 없다.
CPU가 메모리 몇번지에 있는 내용을 달라고 요청하면 매번 주소변환을 해서 물리적인 메모리 위치를 찾아 그 내용을 읽어 CPU에게 전달한다.

MMU

run time binding은 그때그때 물리적 메모리 어디에 올라가 있는지 주소 변환을 해야 한다.

logical address를 physical address로 매핑하는 것을 지원해주는 하드웨어가 바로 MMU이다.
주소변환을 할 때는 기본적인 MMU에서는 레지스터 두개로 주소변환을 한다.

MMU의 레지스터

relocation register(=base register)

base register는 프로그램의 물리적 주소의 시작위치를 나타낸다.

예를 들어 위의 그림에서 좌측 하단의 그림은 p1에서 실행중인 프로그램을 나타내며 logical memory 0~3000을 가지고 있다. CPU가 346번지를 달라고 했다는 것은 여기서 0번지에서 346만큼 떨어져 있는 곳의 내용을 요청한 상황이다. 그리고 이 프로그램이 physical memory 상에는 14000번지부터 올라가 있다. 따라서 이 내용의 물리적 주소를 구하기 위해선 물리적 주소의 시작 위치 (14000=base register)와 논리적 주소를 더해서 구한다.

limit register

limit register는 이 프로그램의 크기를 담고 있다.

이를 저장해두는 이유는 만약 프로그램이 악의적인 프로그램인 경우 자신의 범위를 넘어서는 메모리에 있는 내용을 요청해서 다른 프로그램이 존재하는 메모리 위치를 요청할 수 있다. 따라서 이를 잘못된 요청임을 알아채고 그 요청을 받아들이지 않기 위해 논리적 주소가 프로그램의 크기보다 크지 않은지 확인해야 한다.

만약 limit register를 벗어나는 요청이면 trap(일종의 software interrupt)을 걸어서 cpu 제어권을 OS로 넘긴다. 그럼 OS는 프로그램을 abort시키는 등 악의적인 프로그램을 처리한다.

올바른 요청이라면, bsae register와 논리적 주소를 더하는 연산을 해서 physical address를 구해 거기에 있는 메모리를 읽어 cpu에게 전달한다.

이것이 register 두개를 이용한 간단한 MMU Scheme이다. 사용자 프로그램은 logical address만을 다룬다. 실제 physical address를 볼 수도 없고 알 필요도 없다. physical address는 요청이 되었을 때 MMU가 그때그때 주소 변환을 해준다.

몇가지 용어

Dynamic Loading

프로그램을 메모리에 동적으로 올리는 것이다.

이는 필요할 때마다, 즉 해당 루틴이 불려질 때마다 그때그때 프로그램을 메모리에 올리는 것이다. 프로그램 전체를 미리 올리는 것이 아니라 해당 루틴이 불려질 때마다 그 부분을 메모리에 올린다.

이를 통해 memory utilization을 향상시킬 수 있다. 왜냐하면 전체 코드 중에서 오류 처리 루틴처럼 가끔씩만 사용되지만 많은 양을 차지하는 코드인 경우 dynamic loading을 통해 전체 코드를 미리 다 올려두지 않아 메모리가 낭비되지 않기 때문이다.

dynamic loading은 운영체제의 특별한 지원없이 프로그래머가 라이브러리 형태로 프로그램 자체에서 구현할 수 있는 기능이다. OS는 라이브러리 형태로 dynamic loading을 지원하고, 프로그래머가 그 라이브러리를 써서 코딩을 한다.

cf) 현재 컴퓨터 시스템도 프로그램을 실행시키면 모두 메모리에 올라가는 것이 아니라 당장 필요한 부분만 메모리에 올라가고 필요 없으면 메모리에서 쫓겨난다. 그런데 이것은 dynamic loading이 아니라 운영체제게 직접 관리하는 paging 시스템에 의해 이루어지는 것이다. (섞어쓰기도 한다.)

Overlays

dynamic loading과 구분하여 살펴볼 필요가 있다.(dynamic loading은 라이브러리 사용)

overlays도 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올려둔다. 이 내용만 봐선 차이가 없다.
그러나 역사적으로 차이가 있다. overlays는 초창기 시스템에서 워낙 메모리의 공간이 작아 전체 프로그램을 메모리에 올려놓을 수 없어 프로그래머가 수작업으로 운영체제의 지원없이 프로그램을 쪼개서 수작업으로 코딩을 한 것이다. 다른 말로 manual overlay라 하며 프로그래밍이 매우 복잡하고 어렵다.

swapping

swapping은 프로세스를 일시적으로 메모리에서 통째로 backing store(=swap area)(하드디스크 등)로 쫓아내는 것이다.

swap area로 쫓겨나는 것을 swap out, 쫓겨났던 게 다시 올라오는 것을 swap in 이라고 한다.

일반적으로 중기 스케줄러에 의해 swap out(원칙적으로 프로그램 전부가 쫓겨나는 것을 의미)시킬 프로세스를 선정된다. 그래서 중기스케줄러를 swapper라고도 부른다. 메모리에 너무 많은 프로그램이 올라와 있으면 시스템이 비효율적이어지므로 중기 스케줄러가 일부 프로그램을 골라 통째로 메모리를 디스크로 쫓아내는 일을 하게 된다. 이것이 swapping의 개념과 연결되어 있다.

swapper는 cpu 우선순위가 낮은 프로그램을 쫓아낸다. swapping 시스템이 지원되기 위해서는 (binding과 연결해서 생각해야 함) run time binding을 사용해야 한다. 왜냐면 다른 방법들의 경우 쫓겨났다가 다시 올라올 때 원래의 physical address를 찾아 올라가야 하기 때문에 swapping의 효과가 떨어진다. 따라서 효율적인 동작을 위해 run time binding을 사용해서 나중에 다시 올라갈 때 다른 비어있는 위치로도 올라갈 수 있도록 해야한다.

swap time은 대부분 transfer time이다. 즉 swap되는 데이터 양에 비례하는 시간이다. 디스크를 접근하는 시간은 seek time(디스크 헤드가 이동하는 시간)이 대부분을 차지한다. 그렇지만 이렇게 용량이 방대한 swapping 시스템에서는 양이 워낙 많기 때문에 transfer time도 상당 부분 차지하고 있다.

Dynamic Linking

Linking을 실행 시간(execution time)까지 미루는 기법이다.

linking은 여러 군데 존재하는 컴파일된 파일들을 묶어서 하나의 실행 파일로 만드는 것이다.

라이브러리가 내 프로그램의 실행 파일 코드에 포함되는 것을 static linking이라 한다. 반면 dynamic linking은 내 실행 파일 안에 라이브러리가 포함하지 않고 라이브러리 위치를 찾을 수 있는 작은 코드인 stub만을 둔다. 그래서 실행되다가 라이브러리 호출하는 곳에 이르면 라이브러리를 찾는다.(별도의 파일 형태로 되어있다.) 필요하면 라이브러리를 메모리에 올리고 이미 메모리에 있는 경우 그 루틴의 주소로 간다.

static linking의 경우 printf 함수의 라이브러리 코드를 사용하게 되면 동일한 라이브러리를 각각의 프로세스가 메모리에 올리기 때문에 메모리를 낭비하게 된다. 반면 dynamic linking의 경우 프로그램이 실행이 될 때 printf 호출 부분에 이르면 printf에 해당하는 라이브러리 파일을 찾아 메모리에 올려 사용한다. 만약 다른 사용자에 의해 이 라이브러리가 이미 메모리에 올라와 있다면 추가로 올릴 필요 없이 같이 공유할 수 있다.

그래서 dynamic linking을 해주는 라이브러리를 shared library라고 부른다. 리눅스와 같은 환경에서는 shared object, 윈도우 같은 환경에서는 dll같은 파일이 해당된다.

물리적 메모리 관리법

물리적인 메모리에는

• 낮은 주소부분에 OS 상주 영역이 올라가고,
• 높은 주소부분에 사용자 프로세스 영역이 올라간다.

사용자 프로세스 영역을 할당하는 방법이 두가지 있다.

Contiguous Allocation

연속 할당 방법으로, 프로그램 하나를 통째로 올리는 방법이다.
각각의 프로세스가 메모리의 연속적인 공간에 적재되도록하는 것이다.

fixed partition allocation과 variable partition allocation으로 세분화된다.

고정 분할 방식 Fixed Partition Allocation

프로그램이 들어갈 사용자 메모리 영역을 미리 파티션으로 나누어 놓는 것이다.

위의 그림에서 프로그램들이 분할된 공간에 들어가고 낭비되는 공간들이 있다. 이런 낭비되는 공간도 External fragmentation(외부조각), Internal Fragmentation(내부조각)으로 나뉜다.

• 외부 조각은 프로그램을 메모리에 올리고 싶은데 올리려는 프로그램보다 메모리 조각이 더 작아 사용하지 못하는 경우를 의미한다(분할이 작아서 생기는 문제).
• 그리고 내부 조각은 분할된 조각이 프로그램보다 더 커서 프로그램이 들어간 후 남는 공간을 의미한다.(분할이 커서 생기는 문제)

굉장히 융통성이 없어 내부조각과 외부조각이 발생한다.

가변 분할 방식

사용자 메모리 영역을 미리 나누어 놓지 않는다. 프로그램이 시작될때마다 차곡차곡 메모리에 순서대로 올리는 방법이다.

위 그림에서 만약 B가 끝나면 그 공간이 빈공간이 된다. 그 다음 D가 수행되면 D의 크기가 크기 때문에 B가 있던 자리에 들어가지 못한다. 따라서 외부조각이 발생한다. (내부조각은 발생하지 않는다)

프로그램의 종료와 실행에 따라 외부조각이 발생한다.

Hole

contiguous allocation을 사용하면 비어있는 메모리 공간이 메모리 여러 곳에 산발적으로 생기게 된다. 프로세스가 도착하면 수용 가능한 hole을 할당해주어야 한다.

이를 위해 운영체제는 할당공간(메모리에서 사용되고 있는 부분)과 가용공간(hole)의 정보를 유지하고 있어야 한다. 프로그램이 종료되면 할당공간을 가용공간으로 편입시키고, 새로운 프로그램이 실행되면 hole에 넣어야 한다.

그럼 hole 중에서 어떤 곳에 집어넣을지 정하는 문제에 대해 알아보자.

Dynamic Storage-Allocation Problem

가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제이다. 이 방법은 크게 세가지 알고리즘이 있다.

• First-fit size가 n 이상인 것 중 최초로 찾아지는 hole에 할당한다.
  
• Best-fit (Hole list가 크기 순으로 정렬되어 있지 않다면)모든 hole 리스트를 탐색하여 size가 n이상인 가장 작은 Hole, 즉 프로그램의 크기와 가장 가까운 hole에 집어넣는다. 많은 수의 아주 작은 hole들이 생성된다.
  
• worst-fit 가장 큰 hole 에 프로그램을 할당한다. 전체 리스트를 모두 탐색해야 하고 상대적으로 아주 큰 Hole들이 생성된다.
  

⇒ first-fit(hole 찾을 때 좋음)이나 best-fit(미래에 좋음)이 worst-fit보다 속도와 공간 이용률 측면에서 효과적이다.

compaction

외부 조각으로 생기는 Hole들을 한군데로 밀어 큰 홀을 만듦으로써 외부조각 문제를 해결하는 방법이다. 매우 비용이 많이 드는 방법이다.

run time binding이 되어야 compaction이 가능하다.

모든 홀을 다 합치는 것보다 최소한의 프로그램만을 이동해서 큰 홀을 만드는 것이 더 효율적이다. 이 역시 고려하기 복잡하다.

Noncontiguous Allocation

프로그램을 구성하는 주소 공간을 쪼개서 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라간다.

Paging, Segmentation, Paged Segmentation(혼합)으로 세분화된다.

현대에서는 이 방법을 사용하며, 그 중에서도 특히 Paging을 사용한다.

Paging

Paging이란 프로그램을 구성하는 주소공간을 같은 크기의 page로 자르는 것이다. 그래서 page 단위로 물리적 메모리에 올리거나 backing store에 내려 놓는다. 물리적 메모리에 사용자 프로그램이 들어가는 공간도 page하나의 크기만큼으로 미리 잘라놓는다. 이를 page frame이라 부른다.

이런 기법을 사용하면 프로그램의 어떤 페이지든지 비어있는 위치로 들어갈 수 있다. 따라서 연속할당에서 일어나는 문제가 없어진다.

단 주소 변환을 페이지 별로 해야하기 때문에 address binding이 복잡해진다.

메모리 공간이 page 크기 배수가 아닐 수 있어 약간의 내부조각이 생길 수는 있다.

Segmentation

프로그램의 주소공간을 의미있는 단위로 자르는 것을 segmentation 기법이라고 부른다.
code, data, stack처럼 자르거나 함수단위로 자르는 등의 방법이 있다. 세그먼트 크기는 균일하지 않기 때문에 dynamic storage-allocation problem이 역시 일어날 수 있다.

이 역시 segmentation 별로 address binding해야 한다.