서론
하나의 컴퓨터에는 여러가지 프로그램이 있고, 프로그램에는 여러 프로세스가 있으며, 프로세스에는 여러 스레드가 존재합니다. 이때 프로세스는 메모리에 적재(load)가 되어야 수행할 수 있습니다. 메모리는 연속적인 공간이고, 프로세스는 메모리에 어느 위치에 적재가 되어야하는지가 가장 큰 고민거리입니다. 물론 아무곳이나 프로세스를 넣어도 괜찮지만 우리는 메모리를 효율적으로 사용하고 싶습니다. 이것에 대한 고민이 다음과 같은 이론을 탄생시켰습니다.
내부 단편화 vs 외부 단편화
다음과 같은 그림이 있다고 해봅시다. c프로세스는 30MB만큼 있기 때문에 50MB를 가지고 있는 빈 공간에 들어갈 수 있습니다. 이때 c프로세스를 빈공간에 넣으면 20MB만큼의 남는 공간이 생기게 되는데, 이 공간은 다른 프로세스들이 들어가기에 너무 작습니다. 즉 낭비되는 공간입니다. 이러한 경우를 우리는 internal fragmentation 내부 단편화라고 합니다.
다음과 같은 그림이 있다고 해봅시다. 메모리의 남는 공간이 100MB인데, 이 공간은 연속적이지 않습니다. 그렇기 때문에 충분히 c작업이 들어갈 수 있어도 프로세스를 쪼개서 넣을 수 없기 때문에 해당 프로세스는 메모리에 적재할 수 없습니다. 이러한 경우를 external fragmentation 외부 단편화라고 합니다.
First fit vs Best fit vs Worst fit
우리는 이러한 외부 단편화, 내부 단편화를 줄이기 위해서 똑똑하게 프로세스를 적재하고 싶습니다. 그래서 나온 방법이 위에서 언급한 3가지 방법입니다.
First fit
이름 그대로 입니다. 메모리를 맨 위에서부터 쭉 보면서 가장 먼저 빈 공간이 남는 지점에 그냥 넣는 것입니다.
Best fit
메모리를 처음 부터 끝까지 보면서 내부 단편화를 가장 적게 발생시키는 공간을 찾아 그곳에 프로세스를 적재합니다.
Worst fit
메모리를 처음부터 끝까지 보면서 내부 단편화를 가장 크게 발생시키는 공간을 찾아 그곳에 프로세스를 적재합니다.
위의 세가지 방법을 표현한 부분이 이 그림입니다.
마무리
하지만 이 3가지 방법을 써도 결국은 내부 단편화만 해결하지, 외부 단편화는 해결할 수가 없습니다. 결국 새로운 알고리즘이 필요한 것입니다. 그렇기 때문에 외부 단편화를 해결하는 Buddy system과 같은 방법이 여러가지 등장하게 되지만 결국은 paging이라는 새로운 할당 방식을 야기하는 결과를 불러옵니다. paging에 대해서는 다음 글에서 만나요 안녕~