[OS] Memory Management II (Contigous Allocation)

Memory Allocation

 메모리를 할당하는 방법론에는 크게 두 가지가 있다. 하나는 Contigous Allocation(연속할당)이며, 다른 하나는 Non-Contigous Allocation(불연속할당)이다. 먼저 연속할당에는 어떤 방법론들이 있는지 살펴보자. 불연속 할당에 포함되는 Paging과 Segmentation은 다음 포스팅에서 다뤄볼 것이다. 

Fixed Partitioning - 고정분할 방식

 이름만 보면 알 수 있듯이 메모리를 분할하는 방식이다. 초기에는 같은 Size의 Partitioning으로 나뉘었다. 어떻게 보면 가장 간단하게 생각할 수 있는 방식이다. 분할된 메모리의 Size가 모두 같기 때문에 빈 Slot이 있다면 거기에다가 그냥 할당을 해버리면 된다. 이 방법을 균등 고정분할 방식이라고 부른다. 제일 처음 대두된 방법이기에 구현이 매우 쉬우며 Vanila한 방법론이라고 할 수 있다. 그러나 이 방식의 구현은 너무나 많은 Disadvantage를 앉고 있다. 

 균등 고정분할 방식의 가장 큰 문제점은 고정된 Partition의 수이다. 이는 Active한 Process의 수의 제약을 의미한다. 다시 말해서 Process의 Maximum 개수가 Partition의 Maximum 개수로 경정이 되어버린다. 결과적으로 이는 Multiprogramming의 정도의 제약으로 귀결된다. 다음 문제점들은 그림을 보면 알 수 있는데, Partition된 메모리의 크기의 제한으로 인해 분할된 메모리의 크기보다 더 큰 크기의 Program이 올라오려고 하면 이는 올라오지 못한다. 물론 IBM에서는 이를 Overlay하는 방식으로 해결하였지만 중요한 것은 한 번에 이 프로그램을 올리지 못하며, Overlay기법을 사용하지 않는 이상 해당 Program을 Memory에 올리지 못한다는 것이다. 또한 Partition된 부분 안에서의 사용할 수 없는 영역에 대한 문제가 발생한다. Partition으로 인해 Memory에서 10MB를 온전히 사용하지 못하는 것은 명백한 자원에 대한 낭비이다. 이러한 문제점을 Internal Fragment(내부단편화)라고 부른다. 따라서 내부단편화가 발생할 수록 Memory의 Utilization은 감소하게 된다. 이상적으로 모든 Program들이 10MB를 사용하면 좋겠지만 현실적으로 그러한 Case는 잘 발생하지 않는다. 

Fixed Partitioning with Unequal Size Partition

 앞에서는 모든 Partition의 Size가 동일하였기에 Unequal하게 Size를 나눈 비균등 고정분할 방식이 대두되었다. 이렇게 보면 앞선 균등 고정분할 방식에 대한 Solution처럼 보이기는 하지만 여전히 근본적인 문제를 해결하지는 못했다. 이 경우에는 만약 5개의 Process가 모두 10MB를 사용한다고 가정하면 오히려 균등 고정분할 방식이 더 효율적일 수 있다. 모두 10MB일때는 들어갈 수 있는 Slot이 두 곳 밖에 없기 때문에 그 Process들이 끝나야 다른 10MB의 Program에게 TO가 생긴다. 따라서 이는 General한 버전에서의 Trace를 고려하지 못한 방식이라고 할 수 있다. 

 또한 이 방식은 구현 Level에서 고려해야 할 것이 있는데 바로 Process를 배치할 때 어떤 방식으로 넣을 것인가에 대한 고민이 있다. 여기에는 두 가지 방법이 있는데 Multiple Queue를 활용하는 방식과 Single Queue를 이용한 방식이 있다. 먼저 Single Queue는 단순히 Process의 크기와 Memory에 가용한 Partition이 있다면 바로 집어넣는다. 이러한 방식은 Internal Fragmentation가 많이 발생하게 된다. 반면 Multiple Queue는 크기가 비슷한 Process들끼리 묶어서 Partition에 넣는 방식이다. 위 그림에서 예들 들어보자면 3MB 공간에는 3MB이하의 Process, 10MB 공간에는 10MB이하의 Process를 넣는 방식이다. 그렇기 때문에 공간적으로는 Queue를 많이 배치해야하지만 Memory의 Utilization의 측면에서 본다면 납득할만한 방식이다. 그러나 이 방식에는 딜레마가 존재하는데, 예를 들어서 10MB 이하의 Process들만 오게 된다면 12MB공간의 Queue는 빈 상태로 남아있어야 하고, 비슷한 크기의 Process들이 왔을때 다른 크기의 Partition에서 해당 Process를 품을 수 있다면 이때는 어떻게 해야하는가에 대한 고려를 Programmer Level에서 생각해봐야 한다는 것이다. 

Dynamic Partitioning - 동적분할 방식

 Fixed Partitioning의 문제를 해결하기 위해 Run Time에 Dynamic하게 분할할 수 있는 동적분할 방식이 제시되었다. Dynamic한 시점에 Memory의 크기를 결정할 수 있기 때문에 Process가 Require하는 만큼 Memory를 분할하여 Allocate시킬 수 있다. 즉 이는 Internal Fragementation을 없앨 수 있는 하나의 방법이다. 문제는, 내부 단편화는 해결되었지만 반대로 외부 단편화(External Fragementation)이 발생하게 되었다. 

이미지 출처: https://www.geeksforgeeks.org/difference-between-internal-and-external-fragmentation/

 위 그림을 보자. 어떤 Process는 끝나면 해당 메모리 공간을 반환하고 다른 Process가 Memory 공간을 요구한다. 그러나 Swap out된 메모리의 크기가 들어오려는 Process의 크기보다 작을 때 메모리에는 작은 빈 공간이 생긴다. 예를 들어 Memory의 상단부에 10MB짜리 Process가 나가고 8MB의 Process가 들어온다면 2MB의 공간은 2MB 이하의 Process가 들어오지 않는 이상 놀고 있는 공간으로 남는다는 것이다. 이것 역시 Fragment이며 이 Fragment를 External Fragmentation이라고 한다. Programmer들은 항상 최악의 상황을 고려해야기 때문에 이 Fragment는 시간이 지나면 지날수록 많아지게 될 것이다. 따라서 Memory 안에 있는 Process를 옮겨야 하는 상황이 발생할 수 있는데 이를 Memory Compactation이라고 한다. Memory Compactation은 Memory의 Utilization을 높이기 위해 주기적으로 수행되지만 이는 CPU를 사용해서 옮겨야 하는 것이기 때문에 추가적인 Resource의 사용이 수반된다고 볼 수 있다. 

 따라서 애초에 메모리를 배치할 때 잘 배치하자라는 의미에서 Placement(Allocation) Algorithm이 개발되었다. 책에서는 3가지가 있는데 원래는 worst-fit을 포함한 4가지 알고리즘이 있다고 한다. 그러나 강의 및 책에서는 3개만 다루었기 때문에 이 글에서도 3가지만 다룰 것이다.

• First Fit: Memory의 시작점부터 출발해서 Memory를 스캔한다. 스캔할 때 Require하는 Memory의 크기가 들어갈 수 있는 공간이라면 거기에 할당한다.
• Next Fit: 가장 최근에 할당된 곳부터 출발해서 Memory를 스캔한다. 스캔중 가용영역이 있다면 그곳에 배치한다. 
• Best Fit: 요구되는 Memory의 크기와 가장 비슷한 곳에 할당하는 방법이다. 즉 빈 공간 중 요구되는 크기와 빈 공간의 차이가 가장 작은 곳에 할당하는 것이다. 그러나 이 방식은 과연 Best라는 이름이 최선일까라는 것이다. 차이가 가장 작은 곳을 찾으려면 결국 Memory에 대한 선형 탐색이 진행되야 한다. Memory의 크기가 크면 클수록 이 방법은 O(n)의 시간이 매번 수행되야 하는데, CPU의 Cycle이 낮다면 수십초가 걸릴 수 있는 방법이다. 따라서 Best Fit은 이론적인 알고리즘이며 실제로는 First Fit과 Next Fit이 많이 사용된다. 

 정리하자면 동적분할 방식은 내부단편화가 없으며 Memory Utilization을 높일 수 있다는 장점이 있지만, 반대로 외부단편화의 발생 및 외부단편화의 해결을 위한 Compaction의 CPU time의 할애라는 단점을 지니고 있다. 

Buddy Memory Allocation System

 Buddy Allocation은 메모리에 대한 Request가 들어온다면 Kernel이 Free Space를 Split한다. Memory는 2진수를 활용하고 있으며 2의 지수승의 크기를 지니고 있다. 요구된 Size를 체크하는데 Size 역시 2의 지수승이므로, 2^(i-1) < s <= 2^i 사이즈에 맞게 재귀적으로 Split한다. 아래의 그림을 보면 이해가 쉽게 될 것이다. 

출처: https://www.geeksforgeeks.org/buddy-memory-allocation-program-set-1-allocation/

 128 byte라고 했을 때 처음 32B의 request가 온다면 64두개, 32두 개로 나오고 32에 할당할 수 있으므로 할당한다. 다음 7B에서는 32를 16으로 16을 8로 쪼개고, 이제 7B를 할당할 수 있으므로 할당한다. 이러한 방식으로 메모리를 나누면서 할당을 한다. 흡사 Dynamic Partitioning과 유사해 보인다. (fit 하는 과정이) 만약 해당 Allocate된 Process가 끝나게 되면 Memory는 Release되어 Release된 부분과 같은 Size의 부분이 Merge되며 더이상 진행할 수 없을 때 까지 진행된다. Merge Sort의 Merge하는 부분과 유사하다. 같은 부분(Buddy)끼지 Coalesces되기에 이를 Buddy System이라고 하며 이는 병렬 시스템을 사용하는 곳에서 효율이 높다. 그러나 Request 4처럼 Partition된 부분이 가용하지 않다면 Release 될때까지 기다려야 한다는 단점이 존재하기도 한다.