연속 메모리 할당

외부 단편화 문제

프로세스는 메모리의 연속된 공간에 존재해야한다. 그런데 이런 연속 메모리 할당(Contiguous Memory Allocation)은 외부 단편화(external fragmentation) 문제를 낳는다. 외부 단편화란, 메모리의 빈 공간이 불연속적으로 흩어져있어서 빈 공간을 합한 크기가 하나의 프로세스를 할당하기 충분한 크기임에도 프로세스를 할당하지 못하는 것이다. 그림으로 살펴보면 다음과 같다.

메모리에 프로세스 A, B, C가 올라와있다. 아무것도 할당되지 않은 빈 공간을 hole이라고 한다. B가 모든 작업을 마치고 메모리에서 내려간다. 메모리에는 총 1000의 빈 공간이 있지만 그림처럼 500, 500으로 나뉘어있다. 그래서 새로운 프로세스 D는 600의 공간을 차지함에도 불구하고 공간이 없어서 올라오지 못한다. 이러한 현상을 외부 단편화라고 한다.

연속 메모리 할당 알고리즘에는 세 가지가 있다.

• 최초 적합(First-fit) : 가장 먼저 발견한 빈 공간에 프로세스 할당
• 최적 적합(Best-fit) : 할당 가능한 최소 크기의 빈 공간에 프로세스 할당
• 최악 적합(Worst-fit) : 할당 가능한 최대 크기의 빈 공간에 프로세스 할당

빈 공간이 100, 500, 600, 300, 200KB로 흩어져있는 메모리 공간이 있다. 여기에 크기가 212, 417, 112, 426KB 인 프로세스를 순서대로 메모리에 올려야한다고 생각해보자

최초 적합으로 메모리를 할당한다면, 212KB는 위에서부터 빈 공간을 찾을 때 가장 먼저 들어갈 수 있는 500KB 공간에 할당된다. 다음 417KB 프로세스는 600KB 빈 공간에, 112KB 프로세스는 (500 - 212) KB 빈 공간에 할당된다. 결과적으로 426KB 크기의 프로세스는 외부 단편화로 할당할 수 없게 된다.

최적 적합으로 할당할 경우, 212KB는 할당 가능한 가장 작은 크기인 300KB에, 417KB는 500KB, 112KB는 200KB, 426KB는 600KB에 할당되므로 모든 프로세스를 할당할 수 있다.

최악 적합으로 할당하는 경우 (212KB, 600KB), (412KB, 500KB), (112KB, 600-212KB)에 할당되고 426KB 프로세스는 할당되지 못한다.

할당 방식의 성능을 비교하면 속도는 최초 적합이 가장 빠르고, 메모리 이용률은 최초 적합과 최적 적합이 가장 높다. 그러나 어떤 방식을 사용하든 평균적으로 $\frac{1}{3}$의 메모리 공간이 사용되지 못하고 낭비된다. 위 세 가지 방법 이외에도 compaction이라는 방법이 있다. 메모리에 올라와있는 프로세스들을 한 쪽으로 땡겨서 hole을 한 곳으로 모으는 것인데, 최적의 알고리즘이 없다.

페이징(paging)

다른 좋은 방법이 없을까 고민하던 운영체제 개발자들은 페이징이라는 방법을 고안해냈다. 페이징이란 프로세스를 일정한 크기로 잘라서 메모리에 할당하는 방법이다. 이때 잘린 프로세스 조각 하나를 페이지라고 한다. 모든 프로세스를 같은 크기로 잘라서 할당한다면 프로세스가 종료되어 빈 공간이 생겨도 다른 프로세스가 다시 그 곳을 채울 수 있기 때문에 외부 단편화 문제가 해결된다. 하지만 앞서 말했듯이 프로세스가 실행되기 위해서는 메모리의 연속된 공간에 존재해야한다. 이 문제를 해결하기 위해 MMU가 사용된다.

MMU를 여러 개 사용해서 실제 물리적인 메모리 공간에선 프로세스가 조각 조각으로 나뉘어 흩어진 채로 존재하는데도, CPU는 마치 프로세스가 연속된 메모리 공간에 존재하는 것처럼 동작하도록 CPU를 속일 수 있다.

page vs frame

앞서 프로세스를 고정된 크기로 잘라낸 것이 페이지라고 했다. 이 페이지 하나를 물리적인 메모리에 할당해주어야 하는데, 하나의 페이지를 할당할 수 있는 메모리의 한 조각을 페이지 프레임(page frame), 줄여서 프레임이라고 부른다. 이때, 프로세스는 페이지의 집합, 메모리는 프레임의 집합으로 생각할 수 있다. MMU는 페이지를 프레임에 매핑하는 페이지 테이블로서 동작한다.

주소 변환(Address Translation)

OS는 모든 free frame들을 관리한다. n pages의 프로세스를 메모리에 올리기 위해서 n 개의 free frame을 찾고 그곳에 페이지를 할당한다. 이때 논리 주소를 물리 주소로 변환하기 위해 page table을 관리한다.

페이지가 어떻게 프레임에 매핑되는지 그 과정을 살펴보자.

MMU의 Logical Address 해석

어떤 컴퓨터의 논리적 주소 공간(Logical address space)의 크기가 $2^{m}$bytes이고 페이지의 크기(page size)가 $2^{n}$bytes라면, 주소값 하나는 다음과 같은 의미를 갖는다.

페이지 크기가 4bytes이고 다음과 같이 페이지 테이블과 프레임이 구성되어 있을 때, 논리 주소 13번지는 물리 주소 몇 번지에 저장되는지 살펴보자.

CPU에서 낸 논리 주소는 페이지 크기를 기준으로 나눌 수 있다. 페이지 하나의 크기가 $2^{n}$ bytes이면 주소값의 하위 n 비트가 페이지 변위가 되고 나머지 비트가 페이지 번호가 된다. 이를 통해 실제 논리 주소가 몇 번 페이지의 몇 번째에 있는지 알아낼 수 있다.

출처: Operating System Concepts(10th edition)

CPU가 논리 주소를 내면, MMU는 페이지 테이블에서 해당 주소의 페이지 번호에 매핑되는 프레임 번호를 찾아낸다. 프레임 번호에 변위를 합하여 해당 논리 주소에 매핑되는 물리 주소를 계산한다.

주소 변환 예제

paging 과정을 자세히 살펴보자. 메인 메모리의 크기가 32 bytes이고 논리 주소 공간이 16 bytes, 페이지 크기가 4 bytes인 컴퓨터 시스템이 있다.

출처: Operating System Concepts(10th edition)

페이지의 크기는 프레임의 크기와 같으므로, 32bytes 메모리는 32 bytes / 4 bytes = 8 개의 프레임으로 나뉜다.

페이지의 크기가 $2^{2}$ bytes이고 논리 주소 공간이 $2^{4}$ bytes니까, 전체 논리 주소 공간도 위와 같이 4개의 페이지로 나뉘어진다.

위에서 살펴본 것처럼 논리 주소값의 하위 2비트가 페이지 변위(offset), 나머지가 페이지 번호가 된다. 각 주소에 a ~ p가 저장되어 있다고 가정하자.

각 페이지가 5, 6, 1, 2번 프레임에 저장되었고 이것이 페이지 테이블에 기록되어 있을 때, 논리 주소 6번지를 물리 주소로 변환하는 과정은 다음과 같다.

내부 단편화(internal fragmentation)

위 예제에서 논리 주소 14, 15번지가 아무것도 저장되어있지 않은 빈 공간이라면, 해당 프레임의 절반은 사용되지 못한다. 이를 내부 단편화라고 한다.