가변 분할 메모리와 고정 분할 메모리, 단편화

1. 메모리 오버레이(memory overlay)

과거에는 메모리가 정말 작았다. 요즘은 메모리가 차고 넘치지만, 프로그램도 그만큼 무거워지고 용량이 커졌다. 가령 스타2라는 게임을 플레이한다고 하자. 스타2 프로그램이 총 20GB인데, 메모리가 8GB라면 메모리에 어떻게 프로그램을 옮기고 실행할 수 있을까??

해답은 아주 간단한데, 도마보다 고기가 더 크면 고기를 잘라서 도마에 넣으면 된다. 프로그램도 마찬가지이다. 실제 메모리(물리 메모리)보다 프로그램의 크리가 더 클 떄 전체 프로그램을 메모리에 가져오는 대신 적당한 크기로 잘라서 가져오면 된다. 이 기법을 메모리 오버레이(memory overlay)라고 한다. 'overlay'는 프로그램을 겹겹이 쌓아놓고 실행하는 것을 말한다.

메모리 오버레이의 경우 프로그램을 몇 개의 모듈로 나누고 필요할 때마다 모듈을 메모리에 가져와 사용한다. 전체 프로그램을 메모리에 올려놓고 실행하기에는 메모리의 크기가 작기 때문에 실행하는 데 필요한 중요한 모듈만 올려놓고 나머지는 필요할 때마다 메모리에 가져와 사용하는 것이다.

위는 메모리 오버레이 작동 방식을 보여준다. 스타2 프로그램을 작동하는데 스타2 프로그램은 유닛 정보를 알려주는 기능과, 맵 정보를 알려주는 기능이 있다. 이러한 기능은 각각의 모듈 형태로 분리되어 있다가 프로그램이 실행되면 필요한 모듈만 메모리에 올라와 실행된다. 가령 맵 정보가 필요없고 네트워크 정보가 필요하면 메모리에서 맵 정보를 내쫒고 네트워크 정보를 가져오면 된다. 프로그램 전체를 메모리에 올려놓고 실행하는 것보다 속도가 느리지만 메모리가 프로그램보다 작을 때도 실행할 수 있어 유용하다.

메모리 오버레이에서 어떤 모듈을 가져오거나 내보낼지는 CPU 레지스터 중 하나인 프로그램 카운터(PC)가 결정한다. PC는 앞으로 실행할 명령어의 위치를 가리키는 레지스터로 해당 모듈이 메모리에 없으면 메모리 관리자에게 요청하여 메모리로 가져오게 한다.

메모리 오버레이는 다음과 같은 중요한 의미가 있다.

1. 한정된 메모리에서 메모리보다 큰 프로그램의 실행이 가능하다. 이는 뒤에 나올 가상 메모리 시스템의 기본이 되는 개념이다.
2. 프로그램 전체가 아니라 일부만 메모리에 올라와도 실행이 가능하다. 프로그램은 개념적으로 한 덩어리이지만 일부분만 가지고도 실행할 수 있다. 이는 메모리를 여러 조각으로 나누어 여러 프로세스에 할당할 수 있다는 의미다.

2. 스왑

메모리 오버레이를 이용하여 메모리보다 큰 프로그램을 실행할 수 있다는 것을 확인하였다. 그러나 한 가지 문제가 남는데, 메모리에서 실행 중이던 모듈을 내쫒고 다음 모듈을 실행할 때, 내쫒은 모듈을 어디에 두냐는 것이다.

그냥 하드디스크에 넣으면 되지 않는가?? 라고 생각할 수 있다. 정답이다. 그러나 생각해보면 이 모듈은 조만간 또 쓸지도 모른다. 가령 네트워크 정보가 맵 정보를 메모리에서 내쫒고 들어왔지만, 몇 초뒤에 다시 맵 정보가 불릴 수 있는 것이다. 그렇기 때문에 별로의 공간에 모아두는 것이 좋다. 이러한 영역을 스왑 영역(swap)이라고 한다. 아마 우분투를 설치해보았다면 처음에 swap영역을 선택하라고 할 것인데 그 swap이 바로 이 swap이다.

이 swap 영역은 별도의 정치가 따로 있는 것은 아니다. swap 영역은 하드디스크에 있다. 그러나, 재밌게도 하드디스크 같은 저장장치는 저장장치 관리자가 관리하지만, 스왑 영역은 메모리 관리자가 관리한다. 스왑 영역은 메모리에서 쫒겨났다가 다시 돌아가는 데이터가 머무는 곳이기 때문에 저장장치는 장소만 빌려주고 메모리 관리자가 관리하는 것이다.

따라서, 메모리에서 모듈이 스왑 영역으로 가는 것을 스왑아웃(swap out), 반대로 스왑영역에서 메모리로 가는 것을 스왑인(swap in)이라고 한다.

메모리 오버레이에서 메모리보다 큰 프로그램을 실행할 때 프로그램을 메모리보다 작은 크기의 모듈로 나누어서 사용한다고 했다. 여기에 스왑을 이용하면 스왑 영역의 크기가 메모리의 크기로 인식된다. 다시 말해 사용자는 실제 메모리의 크기와 스왑 영역의 크기를 합쳐서 전체 메모리로 인식하고 사용할 수 있다.

가령, 실제 메모리의 크기가 1GB, 스왑의 크기가 3GB라면 사용자가 인식하는 메모리는 4GB이다. 이는 실제 메모리가 4GB인 컴퓨터보다 속도가 느리지만, 스왑을 사용하면 실제 메모리의 모자란 부분을 보충할 수 있다. 사용자 입장에서는 실제 메모리의 크기에 상관없이 큰 프로그램을 실행할 수 있는 것이다.

3. 다중 프로그래밍 환경에서의 메모리 할당

여태까지 한 번에 하나의 프로세스만 실행되는 단순 메모리 구조의 메모리 오버레이와 스왑의 개념을 살펴보았다. 앞으로는 한 번에 여러 프로세스가 실행되는 구조의 메모리 문제를 알아보자, 한 번에 여러 프로세스를 동시에 실행하는 경우 메모리 관리가 더욱 복잡해지는데, 프로세스들의 크기가 달라 메모리를 어떻게 나누어 사용할 것인지가 가장 큰 문제이다.

3.1 메모리 분할 방식

메모리를 어떤 크기로 나눌 것인가는 메모리 배치 정책에 해당된다. 메모리에 여러 개의 프로세스를 배치하는 방법은 크게 가변 분할 방식(variable size partitioning) ,고정 분할 방식(fixed size programming)으로 나뉜다.

• 가변 분할 방식: 프로세스의 크기에 따라 메모리를 나누는 것이다.
• 고정 분할 방식: 프로세스의 크기와 상관없이 메모리를 같은 크기로 나누는 것이다.

가령, 의자를 생각해보자 식당에 들어가면 유아용 의자가 있는 것을 볼 수 있다. 이는 가변 분할 방식이 된다. 반면, 모두 다 같은 의자를 사용하는 것은 고정 분할 방식이 된다.

그럼 당연히 가변 분할 방식이 더 좋아보이지않는가? 그렇지만 의자를 제공하는 관리자 입장에서는 여간 귀찮은 일이 아니다. 관리 측면에서 매우 불편하고, 손님마다 의자를 준비한다는게 금전적으로 서비스적으로 쉬운 일만은 아니다. 반면, 고정 분할 방식은 관리하기가 비교적 수월하다. 같은 크기의 의자이기 때문에 손님이 의자를 더 요구하면 의자를 하나 더 주기만 하면되기 때문이다.

메모리 배치 역시도 마찬가지로 고정 분할 방식이 관리에 더 용이하다. 메모리 분할 방식을 표현하면 다음과 같다.

왼쪽이 가변 분할 방식, 오른쪽이 고정 분할 방식이다. 그림의 정확함(? 필자가 봐도 못 만들었다)보다 의도한 바를 이해해주었으면 한다. 왼쪽은 가변 분할 방식이기 때문에 각각의 프로세스들이 프로그램의 크기에 따라 가지각색의 메모리 크기를 가지고 있다. 오른쪽은 고정 분할 방식이기 때문에 프로세스들이 고정된 크기인 20kb에 맞게 잘라져 보관된다. 왼쪽에서의 프로세스 A가 오른쪽에서는 20kb 두 개로 나뉘어 서로 다른 위치에 배정된 것을 확인했으면 한다. 또한, 프로세스 B 역시도 14kb이지만 20kb 고정 크기 메모리 영역에 배정된다. 빈공간 6kb는 그냥 남겨두고 사용하는 것이다. 정리하자면 다음과 같다.

1. 가변 분할 방식: 프로세스의 크기에 맞게 메모리가 분할되므로 메모리의 영역이 각각 다르다. 한 프로세스가 연속된 공간에 배치되기 때문에 연속 메모리 할당이라고 한다.
2. 고정 분할 방식: 프로세스의 크기에 상관없이 메모리가 같은 크기로 나뉘며, 큰 프로세스가 메모리에 올라오면 여러 조각으로 나뉘어 배치된다. 한 프로세스가 분산되어 배치되기 때문에 비연속 메모리 할당이라고 한다.

장단점을 정리하면 다음과 같다.

1. 가변 분할 방식의 장점: 가변 분할 방식에서는 프로세스를 한 덩어리로 처리하여 하나의 프로세스를 연속된 공간에 배치한다.

2. 가변 분할 방식의 단점: 가변 분할 방식은 메모리 관리가 복잡하다. 위의 예에서 프로세스 B, 프로세스 D가 작업을 마쳤다고 하자, 그러면 메모리가 14kb, 27kb가 남는다. 이 때 27kb가 넘는 프로세스가 메모리에 올라오려고 한다면 어떻게 될까?? 빈 공간이 떨어져 있기 때문에 올라올 수가 없다. 19kb가 넘는 프로세스를 실행하려면 비어 있는 공간을 하나로 합쳐야 하며, 이 과정에서 프로세스 C의 자리도 옮겨야 한다. 이처럼 가변 분할 방식은 메모리 통합 등의 부가적인 작업이 필요하므로 메모리 관리가 복잡하다.

3. 고정 분할 방식의 장점: 고정 분할 방식에서는 메모리를 일정한 크기로 나누어 관리하기 때문에 메모리 관리가 수월하다. 가변 분할 방식의 메모리 통합 같은 부가적인 작업을 할 필요가 없다.

4. 고정 분할 방식의 단점: 고정 분할 방식에서는 쓸모없는 공간으로 인해 메모리 낭비가 발생할 수 있다. 즉 일정하게 나누어진 공간보다 작은 프로세스가 올라올 경우 메모리 낭비가 발생한다. 위에서 언급했던 대로, 프로세스 B의 크기가 14kb인데, 20kb메모리 공간을 할당해주었다. 이 공간은 비어있지만 다른 프로세스를 배치할 수 없으므로 낭비가 된다.

현대 운영체제에서 메모리 관리는 기본적으로 고정 분할 방식을 사용하면서 일부분은 가변 분할 방식을 혼합하고 있다.

4. 가변 분할 방식의 메모리 관리

앞으로 배울 가상 메모리 시스템에서는 가변 분할 방식을 세그먼테이션 기법이라고도 한다. 여기서는 가변 분할 방식에서 프로세스를 배치하는 방법과 이에 따른 문제점을 살펴보자.

4.1 프로세스 배치와 외부 단편화

단편화(fragmentation) 또는 조각화는 메모리에 프로세스를 배치할 수 없는 빈 영역, 즉 조각들을 말한다.

위의 그림은 가변 분할 방식으로 메모리를 할당했을 때의 방식을 보여준다. 여기서 프로세스 K는 메모리에 들어가길 기다리고 있다. 이 때 프로세스 B, 프로세스 D가 작동을 중지하고 메모리에서 쫒겨난다고 하자.

메모리에서는 14+27 = 41kb이라는 추가 공간이 생겼지만 프로세스 K가 33kb의 크기를 가졌음에도 불구하고 할당될 수 없다. 이는 가변 분할 방식은 연속적으로 프로세스를 메모리에 배치해야하기 때문에 프로세스 K를 넣지 못한다. 이러한 작은 빈 공간을 외부 단편화(external fragmentation)이라고 한다. 프로세스 밖에서 조각이 발생하기 때문에 이렇게 불린다.

가변 분할 방식에서는 외부 단편화로 인한 문제를 해결하기 위해 메모리 배치 방식 이나 조각 모음을 사용한다. 메모리 배치 방식은 작은 조각이 발생하지 않도록 프로세스를 배치하는 것이며, 조각 모음은 조각이 발생했을 때 작은 조각들을 모아서 하나의 큰 덩어리로 만드는 작업이다. 메모리 배치 방식은 가변 분할 방식에서 선처리에 해당하고 조각 모음은 후처리에 해당한다.

4.2 메모리 배치 방식

가변 분할 방식의 외부 단편화 문제를 해결하기 위해 대표적인 메모리 배치 방식으로는 최초 배치(first fir), 최적 배치(best fit), 최악 배치(worst fit) 이 외에도 버디 시스템(buddy system)이 있다.

1. 최초 배치: 최초 배치(first fit)은 단편화를 고려하지 않는 것으로, 프로세스를 메모리의 빈 공간에 배치할 때 메모리에서 적재 가능한 공간을 순서대로 찾다가 첫 번째로 발견한 공간에 프로세스를 배치하는 방법이다.

다음과 같은 상황일 때, 프로세스 K는 다음과 같이 배치된다.

가장 먼저 확보된 공간에 넣어준다.

2. 최적 배치: 최적 배치는 메모리의 빈 공간을 모두 확인한 후 적당한 크기 가운데 가장 작은 공간에 프로세스를 배치하는 방법이다.

다음과 같은 상황에서, 빈 공간은 35b, 33kb가 있다. 이 때 최초 배치는 35kb에 할당되지만, 최적 배치는 33kb이 더 작으므로 여기에 배치된다.

다음과 같이 빈 공간 중, 가장 작은 공간으로 들어가 공간을 효율적으로 사용한다.

3. 최악 배치:최적 배치와 정반대로 최악 배치는 빈 공간을 모두 확인한 후 가장 큰 공간에 프로세스를 배치하는 방식이다. 위의 예제에서 35kb에 프로세스 k를 배치하는 것이다.

결과적으로 어떤 배치 방식을 사용해도 단편화 현상은 발생한다.

4.3 조각 모음

원래 가변 분할 방식의 목적은 프로세스를 한 덩어리로 취급하여 메모리 관리의 효율성을 높이는 것인데, 메모리 배치 방식으로는 근본적으로 문제를 해결하지 못한다.

가변 분할 방식에서는 메모리에 올라오는 프로세스가 차례대로 배치되기 때문에 공간 사용에 큰 문제가 없다. 그러나 작은 프로세스가 작업을 마치고 메모리에서 나가면 그 공간이 조각으로 남아 쓸모없어질 가능성이 크다. 이렇게 단편화가 발생하면 이미 배치된 프로세스를 옆으로 옮겨 빈 공간들을 하나의 큰 덩어리로 만들어야 하는데 이것이 바로 조각 모음이다.

즉, 조각 모음은 서로 떨어져 있는 여러 개의 빈 공간을 합치는 작업이다.

위의 사진이 바로 조각 모음이다. 조각 모음은 다음의 과정을 거친다.

1. 조각 모음을 하기 위해 이동할 프로세스의 동작을 멈춘다.
2. 프로세스를 적당한 위치로 이동한다. 프로세스가 원래의 위치에서 이동하기 때문에 프로세스의 상대 주소값을 바꾼다.
3. 이러한 작업을 다 마친 후 프로세스를 다시 시작한다.

조각 모음을 하려면 프로세스를 중지시키고, 이동하고, 주소를 바꾸고, 다시 시작하는 작업을 해야하기 때문에 시간이 많이 걸린다. 이처럼 가변 분할 방식은 외부 단편화로 인해 조각 모음 같은 부가적인 작업이 필요하므로 메모리 관리가 복잡하다.

참고로 외부 단편화는 하드디스크와 같은 저장장치에서도 발생한다. 하드디스크에는 동영상과 같은 큰 파일도 저장되고 문서와 같은 작은 파일도 저장된다. 빈 하드디스크에 데이터를 채주면 데이터가 차곡차곡 쌓이다가 데이터의 삭제와 저장을 반복하면 데이터가 여러 공간에 나뉘어 저장된다. 이러한 현상은 시간이 흐를수록 더욱 심해지고 결국 하드디스크의 입출력 속도를 떨어뜨려 컴퓨터의 성능을 저하시키는 원인이 된다. 따라서 하드디스크와 같은 저장잧치도 성능을 유지하려면 추가적으로 조각 모음을 실행해야한다.

5. 고정 분할 방식의 메모리 관리

가상 메모리 시스템에서는 고장 분할 방식을 페이징이라고 한다. 가변 분할 방식과 달리 고정 분할 방식은 프로세스의 크기에 상관없이 메모리를 같은 크기로 나누기 때문에 관리하기가 편하다. 그러나 프로세스가 메모리의 여러 조각에 나뉘어 저장되는 것이 문제이다.

5.1 프로세스 배치와 내부 단편화

고정 분할 방식은 가변 분할 방식보다 더욱 공간을 효율적으로 사용하는데, 이는 프로세스를 정해진 크기로 잘라내어 불연속적으로 관리할 수 있기 때문이다.

다음의 상황에서 빈공간 20kb가 두 개 남았는데, 만약 가변 분할 방식이였다면 33kb 프로세스 K를 메모리에 배치하지 못했을 것이다. 하지만, 고정 분할 방식은 프로세스를 잘라내어 20kb, 13kb로 나누어 배치할 수 있으므로 프로세스 K를 메모리에 배치할 수 있게된다.

따라서, 고정 분할 방식은 메모리 관리에 있어 더욱 효율적이고, 가변 분할 방식처럼 외부 단편화가 발생하지않아 조각 모음을 할 필요가 없다.

현대의 메모리 관리 시스템은 고정 분할 방식을 기본으로 사용하고 있다.

그러나 고정 분할 방식도 단점이 있다. 일정하게 나뉜 메모리의 크기보다 작은 프로세스가 배치될 경우 낭비되는 공간이 생긴다는 것이다. 위의 예제에서 다음과 같은 상황이다.

고정된 메모리 영역은 20kb이고 프로세스의 크기는 33kb이므로 20 + 13kb로 나누어 배치할 수 밖에 없다. 따라서, 하나는 20kb 중 13kb만 사용하게 되는 것이다. 이 때 7kb는 사용하지 못하게 되는데, 이를 내부 단편화(internal fragmentation)이라고 한다. 즉, 고정 분할 방식에서는 일정한 크기로 나뉜 파티션 안쪽으로 작은 조각이 발생하고, 메모리 조각에 프로세스를 배치하고 공간이 남는 현상을 말한다.

가변 분할 방식의 외부 단편화는 조각 모음으로 조정했으나 고정 분할 방식에서는 내부 단편화를 해결하기 위해 조각 모음을 할 수 없고 남는 공간을 다른 프로세스에 배정할 수도 없다. 대신 동일하게 분할되는 공간의 크기를 조절하여 내부 단편화를 최소화한다.

지금까지 가변 분할 방식과 고정 분할 방식을 정리하면 다음과 같다.

구분	가변 분할 방식	고정 분할 방식
메모리 단위	세그먼테이션	페이징
특징	연속 메모리 할당	비연속 메모리 할당
장점	프로세스를 한 덩어리로 관리 가능	메모리 관리가 편리
단점	빈 공간의 관리가 어렵다	프로세스가 분할되어 처리된다
단편화	외부 단편화	내부 단편화

6. 버디 시스템

가변 분할 방식의 단점인 외부 단편화를 완화하는 방법으로 버디 시스템이 있다. 버디 시스템은 가변 분할 방식이지만 고정 분할 방식과 유사한 점이 있다.

6.1 버디 시스템의 작동 방식

버디 시스템의 특징은 가변 분할 방식과 고정 분할 방식의 중간 구조라는 것이다. 버디 시스템의 작동 방식은 다음과 같다.

1. 프로세스의 크기에 맞게 메모리를 1/2로 자르고 프로세스를 메모리에 배치한다.
2. 나뉜 메모리의 각 구역에는 프로세스가 1개만 들어간다.
3. 프로세스가 종료되면 주변의 빈 조각과 합쳐서 하나의 큰 덩어리를 만든다.

버디 시스템에서 메모리에 프로세스를 배치할 때는 메모리를 프로세스의 크기에 맞게 1/2 크기로 잘라나간다.

다음과 같이 160kb 크기를 가진 메모리가 있다고 하자. 이 때 33kb크기를 가진 프로세스 B를 메모리에 할당한다고 한다면 버디시스템은 다음과 같이 작동한다.

1. 먼저 메모리 160kb의 2로 나눈다. 80, 40 ,20이 되지만 20은 33kb인 프로세스 B보다 작다. 따라서 40kb 공간을 만든다.
2. 40kb의 공간에 33kb 프로세스 B를 할당한다.

이처럼 버디 시스템은 프로세스를 메모리에 배치할 때 공간을 반으로 쪼개가면서 한 덩어리를 배치할 수 있도록 맞춘다. 재밌는 것은 버디 시스템은 식사를 마치면 주변에 남는 의자를 합쳐서 하나의 덩어리를 만든다.

이렇게 가변 분할 시스템처럼 하나의 프로세스를 연속적으로 크기를 잡아놓지만, 그 안에 들어가는 메모리 공간은 고정 크기인 이유는 메모리 관리가 편하고 효율적이기 때문이다. 또한, 프로세스를 분할하지 않아 프로세스 관리에 더욱 수월하다.

다음과 같은 경우를 확인하자. 프로세스 B는 33kb이지만, 40kb 공간에 할당이 되어있다. 나머지 공간은 모두 full로 채워진 상태에서 새로운 프로세스 40kb 프로세스 K가 들어온다고 하자.

프로세스 B를 내쫒고, 프로세스 K를 넣으려한다. 만약 가변 분할 시스템이었다면 프로세스 B가 33kb의 공간에 할당되었음으로 절대 프로세스 K를 넣지 못한다. 그러나, 버디 시스템은 프로세스 B의 메모리 공간이 40kb로 채워졌기 때문에 33kb인 프로세스 B를 내쫒고 40kb 프로세스 K를 할당할 수 있는 것이다. 따라서, 버디 시스템은 가변 분할 시스템보다 효율적이고 메모리 관리에 이점이 있다.

6.2 버디 시스템의 특징

버디 시스템은 가변 분할 방식과 고정 분할 방식의 특징을 모두 가지고 있다. 가변 분할 방식처럼 메모리가 프로세스 크기대로 나위며, 고정 분할 방식처럼 하나의 구역에 다른 프로세스가 들어갈 수 없고, 메모리의 한 구역 내부에 조각이 생겨 내부 단편화가 발생한다.

바디 시스템이 가변 분할 방식보다 효과적으로 공간을 관리할 수 있는 이유는 비슷한 크기의 덩어리가 서로 모여 있어 통합하기가 쉽기 때문이다. 가변 분할 방식에서는 작은 조각이 큰 조각 사이사이에 있어 조각을 모으려면 큰 덩어리를 옮겨야 한다. 그러나 버디 시스템에서는 비슷한 크기의 조각이 서로 모여 있기 때문에 작은 조각을 통합하여 큰 조각을 만들기 쉽다. 위의 프로세스 크기가 40kb인 것들끼리 모여있는 것과 같은 이치이다. 이처럼 버디 시스템에서는 조각 모음을 하지 않아도 간단히 큰 덩어리를 만들 수 있다.

효율적인 공간 관리 측면에서 보면 고정 분할 방식과 버디 시스템은 비슷한 수준이다. 그러나 공간을 1/2로 나누어가며 메모리를 배분하는 버디 시스템보다 모든 공간을 똑같은 크기로 나누는 고정 분할 방식이 메모리 관리 측면에서 단순하기 때문에 버디 시스템보다 고정 분할 방식이 많이 사용되고 있다.