연속 메모리 할당 (Contiguous Memory Allocation)

연속 메모리 할당 (Contiguous Memory Allocation)

주 메모리는 운영체제뿐만 아니라 여러 사용자 프로세스도 수용해야 한다. 그리고 이 각 영역은 목적에 맞도록 효율적으로 관리되어야 한다.

메모리는 일반적으로 두 개로 나누어지는데, 하나는 메모리에 상주하는 운영체제를 위한 것이다. 그리고 다른 하나는 사용자 프로세스를 위한 것이다. 운영체제는 메모리 어느 쪽 끝에도 위치할 수 있으며, 이 결정에 영향을 미치는 중요한 요인은 인터럽트 벡터이다. 인터럽트 벡터는 흔히 0번지에 위치하기 때문에 운영체제는 하위 메모리에 위치시키는 것이 보통이다. 그러므로 운영체제는 하위 메모리에 위치하는 상황만 논의할 것인데, 다른 상황도 비슷하다.

보통 여러 프로세스가 동시에 메모리에 적재되어 있는 것이 바람직하기 때문에 메모리에 적재되기 위하여 입력 큐에서 대기 중인 프로세스들에게 메모리를 얼마나 어떻게 할당하는 것이 좋은가를 생각할 필요가 있다. 이러한 연속 메모리 할당 시스템에서 프로세스는 연속된 메모리 공간을 차지하게 된다.

1. 메모리 보호 (Memory Protection)

메모리 할당에 대해 더 구체적으로 설명하기 전에 메모리 매핑과 보호에 대해 먼저 알아보자. 메모리 매핑과 보호는 이전에 다룬재배치 레지스터와 상한 레지스터를 사용한다. (링크: <http://neos518.tistory.com/120?category=806096>)

재배치 레지스터는 가장 작은 물리주소의 값을 저장하고, 상한 레지스터는 논리주소의 범위 값을 저장한다. 각각의 논리주소는 상한 레지스터보다 작아야 한다. MMU는 동적으로 논리주소에 재배치 레지스터의 값을 더함으로써 주소를 변환하는 역할을 한다. 이렇게 변환된 주소는 메모리에 보내진다.

CPU 스케줄러가 다음으로 실행할 프로세스를 선택할 때 디스패처는 문맥 교환의 일환으로 재배치 레지스터와 상한 레지스터에 정확한 값을 적재한다. CPU에 의해서 생성되는 모든 주소들은 이 레지스터들의 값을 참조해서 확인 작업을 거치기 때문에 운영체제와 다른 사용자 프로그램을 현재 실행 중인 사용자 프로그램의 접근으로부터 보호할 수 있다.

여기서 재배치 레지스터를 사용하면서, 운영체제의 크기는 실행 중이라도 얼마든지 변경될 수 있음을 알 수 있다. 이러한 기능은 매우 유용하게 쓰일 수 있다. 예를 들어, 운영체제가 지원하던 어떤 주변장치가 향후 더 이상 쓰이지 않는다고 가정하면, 운영체제 중 그 장치와 관련된 코드는 더 이상 메모리에 있을 필요가 없게 된다. 이러한 부분을 일시적 운영체제 코드(transient OS code)라고 부른다. 즉, 필요에 따라 메모리에 올라오기도 하고 지워지기도 하는 부분이다. 이러한 기능을 최대한 활용하면 전체 운영체제의 크기는 매우 작아질 수 있다.

2. 메모리 할당 (Memory Allocation)

가장 간단한 공간 할당 방법은 메모리를 똑같은 고정된 크기로 분할(partition)하는 것이다. 각 분할마다 한 프로세스를 적재할 수 있고, 이때 분할의 개수가 다중 프로그래밍 정도(multiprogramming degree)를 결정한다. 한 분할이 비게 되면 한 프로세스가 입력 큐에서 선택되어 빈 분할에 들어온다. 프로세스가 끝나면 그 분할은 다른 프로세스를 위해 사용될 수 있다. 이러한 기법은 원래 IBM OS/360 운영체제에 사용되었지만 현재에는 사용되지 않는다.

가변 분할 기법에서 운영체제는 메모리의 어떤 부분이 사용되고, 어떤 부분이 사용되지 않는가를 파악할 수 있는 테이블을 유지한다. 초기에 모든 메모리 공간은 한 개의 큰 사용 가능한 블록으로 간주된다. 이 경우, 한 개의 공간(hole)이 있다고 표현한다. 새 프로세스가 생겨나고 메모리가 필요해지면 운영체제는 자유 공간을 찾아 이 프로세스에게 충분한 크기의 공간을 주게 된다.

프로세스가 시스템에 들어오면, 일단 입력 큐에 넣는다. 운영체제는 각 프로세스가 메모리를 얼마나 요구하며, 또 사용 가능한 메모리 공간이 어디에 얼마나 있는지를 고려하여 공간을 할당한다. 프로세스가 공간을 할당받게 되면 이후로는 CPU를 할당받기 위해 경쟁한다. 프로세스가 끝나면 메모리를 반납하고, 운영체제는 입력 큐에 있는 다른 프로세스로 이 공간을 채운다.

운영체제는 항상 가용 공간의 크기들과 입력 큐를 유지해야 한다. 운영체제는 특정 알고리즘을 사용하여 입력 큐의 프로세스들을 일정한 순서로 배치할 수도 있다. 공간을 차례로 할당해 주다가 만일 한 프로세스의 메모리 요구가 만족될 수 없게 되면, 공간이 생길 때까지 기다리던가, 좀 더 적으 ㄴ메모리를 요구하는 다른 프로세스가 있는가를 알아보기 위해 입력 큐로 되돌아갈 수도 있다.

일반적으로, 메모리에는 여러 크기의 자유 공간이 여기저기 존재하게 된다. 프로세스가 공간을 필요로 할 때 운영체제는 이 자유 공간들의 집합에서 적절한 것을 찾아내야 한다. 만약 자유 공간을 찾았는데 그것이 요청한 것보다 약간 크면 두 개로 나누어 한 조각은 프로세스에게 할당하고, 나머지 하나는 자유 공간으로 취급한다. 프로세스가 끝나면, 그 공간을 운영체제로 되돌려 주는데, 만약 이 되돌아온 공간이 다른 자유 공간 블록과 인접해 있다면, 이 두개의 블록을 합쳐서 한 개의 큰 자유 공간 블록으로 만든다. 그리고 나서 이렇게 합친 큰 자유 공간을 기다리고 있는 프로세스가 있는지를 확인해 볼 필요가 있다.

이러한 기법은 동적 메모리 할당 문제(dynamic storage allocation problem)의 특별한 예이다. 이것은 일련의 자유 공간 리스트로부터 크기 n 바이트의 블록에 대한 요청을 어떻게 만족시켜 줄 수 있는지를 결정하는 문제이다. 이러한 문제에 대한 해결책은 여러 가지가 제시되는데, 최초 적합(First-fit), 최적 적합(Best-fit), 최악 적합(Worst-fit)은 가장 일반적인 기법들이다.

- 최초 적합

요청을 만족시키는 충분히 큰 첫 번째 가용 공간을 할당한다. 검색은 집합의 시작에서부터 하거나, 지난 번 검색이 끝났던 곳에서 시작될 수 있다. 충분히 큰 가용 공간을 찾았을 때 검색을 끝낼 수 있다.

- 최적 적합

요청을 만족시키는 충분히 큰 공간들 중에서 가장 작은 것을 택한다. 리스트가 크기 순으로 정렬되어 있지 않다면 리스트 전체를 검색해야 한다. 이 방법은 아주 작은 잔여 공간을 만들어낸다.

- 최악 적합

가장 큰 가용 공간을 택한다. 이 방식에서 할당해 주고 남는 자유 공간은 충분히 커서, 다른 프로세스들을 위하여 유용하게 사용될 수 있다. 이때, 자유 공간들이 크기순으로 정렬되어 있지 않으면 리스트 전체를 검색해야만 한다.

과거에 여러 차례의 모의실험(simulation)을 통한 연구에서 최초 적합과 최적 적합 모두가 시간과 메모리 이용 효율 측면에서 최악 적합보다 좋다는 것이 입증되었다. 최초 적합이나 최적 적합이나 공간 효율성 측면에서는 어느 것이 항상 더 좋다고 말할 수 없지만, 최초 적합이 일반적으로 속도가 더 빠르다.

3. 단편화 (Fragmentation)

앞서 언급한 메모리 적합 알고리즘을 사용하다보면 외부 단편화(external fragmentation: fragment는 공간 중 일부가 사용 못하게 되는 부분을 일컫는다) 문제가 발생하게 된다. 프로세스들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 어떤 자유 공간은 너무 작은 조각이 되어 버린다. 외부 단편화는 이처럼 유휴 공간들을 모두 합치면 충분한 공간이 되지만 그것들이 너무 작은 조각들로 여러 곳에 분산되어 있을 때 발생한다.

이 단편화 문제는 매우 심각해질 수 있다. 최악의 경우에는, 모든 프로세스 사이마다 못 쓰게 된 자유 공간을 가질 수 있다. 이 모든 자유 공간들을 합쳐 하나의 큰 자유 공간을 만들면 여기에 여러 개의 프로세스들을 실행시킬 수 있을 것이다.

최초 적합과 최적 적합 중 어느 것을 사용하느냐가 이 양에 영향을 준다. 자유 공간의 어느 쪽을 할당해 주느냐(잔여 공간이 자유 공간의 위쪽이냐 아래쪽이냐)도 고려해야 할 요소 중 하나이다. 어떤 알고리즘을 사용하더라도 외부 단편화는 문제로 남는다.

메모리의 전체 크기와 프로세스의 평균 크기가 얼마인가에 따라 외부 단편화는 사소한 문제가 되거나 심각한 문제가 된다. 예를 들어 최초 적합의 경우, 통계적인 분석을 해보면 N개의 블록이 할당되었을 때 0.5N개의 블록이 단편화 때문에 손실될 수 있다. 즉, 메모리의 3 분의 1이 쓸 수 없게 될 수 있다는 것이다. 이 특성은 50% 규칙(50-percent rule)으로 알려져 있다.

메모리 공간을 낭비하는 현상인 단편화는 내부적으로도 발생할 수 있다. 18,464B 크기의 자유 공간을 생각해 보자. 어느 한 프로세스가 18,462B를 요구한다고 가정해 보자. 요구된 블록을 정확히 할당하면 2B의 가용 공간이 남는다. 이러한 경우, 2B짜리 가용 공간을 추적하는데 사용되는 오버헤드가 2B의 가용 공간을 활용했을 때 보다 훨씬 클 것이다.

따라서, 일반적으로는 메모리를 먼저 아주 작은 공간들로 분할하고, 프로세스가 요청하면 할당을 항상 이 분할된 크기의 정수 배로만 해주는 것이 보통이다. 이 경우, 할당된 공간은 요구된 공간보다 약간 더 클 수 있다. 읻르 두 크기 사이의 차이가 바로 내부 단편화(internal fragmentation)이고, 이 내부 단편은 분할 내부에 존재하지만 현재 사용되고 있지 않는 메모리를 말한다.

외부 단편화 문제를 해결하는 한 가지 방법은 압축(compaction)이다. 이 방법은 메모리의 모든 내용들을 한 군데로 몰고 모든 자유 공간들을 다른 한 군데로 몰아서 큰 블록을 만드는 것이다. 그러나, 압축이 한상 가능한 것은 아니다. 프로세스들이 새로운 위치로 옮겨져 실행되기 위해서는 프로세스 내 모든 주소들이 동적으로 재배치되어야 한다. 따라서, 압축은 프로세스들의 재배치가 실행 시간에 동적으로 이루어지는 경우에만 가능하다.

또, 압축이 가능하더라도 그 비용을 검토해 보아야 한다. 가장 간단한 압축 알고리즘은 단순히 모든 프로세스를 한쪽 끝으로 이동시켜 모든 가용 공간이 반대 방향으로 모이도록 하는 방법이지만, 비용이 매우 많이 든다. 외부 단편화 문제를 해결할 수 있는 다른 방법은 한 프로세스의 주소 공간을 여러 개의 동떨어진 공간으로 배정하는 것이다. 이 방법을 사용하는 대표적인 시스템으로는 페이징과 세그멘테이션이 있다. 물론, 이 두 가지 기법은 서로 합쳐서 사용할 수도 있다.