Computer Science
운영체제의 메모리 관리 2 - Dynamic Partitioning
3/19/2025
앞서 언급된 고정 파티셔닝의 단점을 극복하기 위해, 동적 파티셔닝이 고안되었습니다.
핵심 개념
고정 파티셔닝에서는 메모리를 사전에 정의된 동일하거나, 동일하지 않은 크기의 영역들로 구분했습니다. 동적 파티셔닝은 메모리 파티션을 사전에 정의하지 않고, 프로세스의 필요에 따라 동적으로 할당시키는 방법입니다.
동적 파티셔닝에서 각각의 파티션은 '파티션 번호'와 '영역의 크기'로 표현됩니다. 프로세스가 메인메모리에 할당될 때, 정확히 그 프로세스가 필요한 만큼의 크기만을 할당합니다.
External Fragmentation
위 예제에서는 동적 파티셔닝 구조에서 프로세스들이 순차적으로 메모리를 할당받는 모습을 보여줍니다. (b), (c), (d)에서 각 프로세스들은 공간을 순차적으로 부여받습니다. 허나 프로세스 4가 들어가기에는, (d)에는 남은 공간이 너무 작습니다. 프로세스 4의 실행을 위해 메모리에 유휴 공간을 만들어야 합니다. 이 때 프로세스 2가 I/O 등의 이유로 CPU를 점유할 수 있는 상황이 되지 않는다면, 운영체제는 프로세스를 디스크로 잠시 옮겨두고, 그 자리에 프로세스 4를 할당합니다. 이후 프로세스 2가 다시 수행될 수 있는 상태가 된다면, 동일한 과정을 거쳐 프로세스 1을 디스크로 옮기고 그 자리를 프로세스 2에 할당합니다.
이 과정에서 볼 수 있는 것은 각각의 프로세스들이 차지한 공간 사이사이에 작은 유휴 공간이 생겼다는 것입니다. (h)의 상황에서 유휴 공간을 모두 합치면 16M 이지만, 이들이 모두 분리되어 있으므로 6M보다 큰 프로세스가 들어가기 위해서는 다른 프로세스를 쫓아내야합니다. 이렇게 유휴 메모리 공간이 점점 파편화되고 효율성이 떨어지는 현상을 외부 파편화external fragmentation이라고 합니다.
외부 파편화를 해결하기 위한 방법으로는 압축compaction이 있습니다. 압축이란 운영체제가 일정한 주기로 프로세스들을 연속적인 위치로 옮겨서, 유휴 공간이 하나의 거대한 블록으로 유지되게 만드는 방법입니다. (h)에서 압축을 수행하면 하단에 16MB의 거대한 블록이 확보되므로 6M 이상의 프로세스도 스와핑 없이 할당될 수 있습니다.
Placement Algorithm
하지만 압축은 상당한 시간이 걸리는 작업입니다. 따라서 운영체제는 메모리의 유휴 공간 중 어디에 프로세스를 할당해야할지를 더 신경써야합니다. Placement Algorithm은 프로세스가 들어갈 수 있는 여러 메모리 공간이 있을 때, 어떤 공간에 할당할지를 결정하는 알고리즘입니다. 대표적인 Placement Algorithm은 다음과 같습니다.
1. Best-fit : 프로세스의 크기와 가장 비슷한 크기의 영역을 선택
2. First-fit : 메모리를 가장 위에서 탐색하기 시작하여 이용가능한 첫번째 영역을 선택
3. Next-fit : 최근에 할당되었던 주소부터 탐색하기 시작하여 이용가능한 첫번째 영역을 선택
위 그림은 왼쪽의 상황에서 서로 다른 알고리즘에 의해 할당된 새로운 프로세스의 위치를 보여줍니다. First-fit은 6MB의 파편을, Best-fit은 2MB의 파편을, Next-fit은 20MB의 파편을 만들었습니다.
사실 위 수치는 기존에 프로세스가 어디에 할당되었냐에 의존합니다. Next-fit의 위치는 상황에 따라 변경될 수 있기 때문입니다. 수치만 보고 판단하기는 어려울지도 모릅니다.
이에 대한 일반적인 연구 결과로는, First-fit이 구현이 쉬울 뿐만 아니라 가장 최적이라는 것입니다. Next-fit은 First-fit보다 살짝 떨어지는 결과를 낳는다고 합니다. Best-fit은 이름과 맞지 않게, 가장 안좋은 성능을 보입니다. Best-fit은 항상 메모리의 가장 작은 파편을 만드는 것을 보장하기에, 다른 방식보다 더 잦은 압축이 필요합니다.
다음 글에서는 Relocation에 대해 알아보겠습니다.