[시스템 프로그래밍] 가상메모리[2] - 묵시적 리스트 (Implicit List)

 

 

 

 

 

이전 글에 이어지는 내용으로, 가용 블록을 관리하는 첫번째 방법인 묵시적 리스트 방식을 살펴보도록 하겠습니다.

 

 

 

 

 

 

 

 

🧐 묵시적 리스트 방식 (Implicit List)

 

 

👉 헤더(Header)

모든 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조를 필요로 합니다.

대부분의 할당기가 해당 정보를 블록 내부에 저장합니다.

 

일반적인 방법으로는 추가적으로 1블록을 사용하여 블록 앞에 블록의 크기를 저장하는 방법이 있습니다.

이때 추가적으로 사용되는 1 워드를 헤더(Header)라고 합니다.

헤더는 블록 크기와 블록이 할당되었는지, 혹은 가용 상태인지를 인코딩합니다.

 

 

만약 더블 워드(8바이트) 정렬 제약조건을 설정한다면, 블록 크기는 항상 8의 배수입니다.

즉 블록 크기의 하위 3비트는 항상 0이 됩니다.

따라서 블록 크기의 상위 29비트만 저장할 필요가 있으며, 나머지 3비트는 다른 정보를 인코딩하기 위해 남겨둡니다.

 

이 경우 블록이 할당되었는지 혹은 가용 상태인지를 나타내기 위해 LSB를 사용합니다.

예를 들어 블록 크기 24바이트(0x18)를 갖는 할당된 블록이 있는 경우, 헤더는 다음과 같이 됩니다.

0x00000018[블록 크기] | 0x1[가용 상태 여부] = 0x00000019

 

블록 크기 40바이트(0x28)를 갖는 가용 블록이 있는 경우, 헤더는 다음과 같이 됩니다.

0x00000028[블록 크기] | 0x0[가용 상태 여부] = 0x00000028

 

 

 

 

헤더 다음에는 애플리케이션이 malloc을 호출하였을 때 요구한 데이터가 존재합니다.

데이터 이후에은 사용되지 않는 패딩이 따라올 수 있는데, 이들의 크기는 가변적입니다.

패딩을 사용하는 이유로는 여러 가지가 있는데, 예를 들어 외부 파편화를 극복하기 위한 할당기의 전략일 수도 있으며, 정렬 요구사항을 만족하기 위해 필요할 수 있습니다.

 

 

 

위에서 살펴본 내용들을 합친 블록의 구조는 다음과 같습니다.

 

위와 같은 블록 형태가 주어졌을 때, 힙을 연속된 할당 및 가용 블록의 배열로 아래 그림과 같이 구성할 수 있습니다.

 

이러한 구조를 묵시적 리스트라고 부르는데, 그것은 가용 블록이 헤더 내 필드에 의해서 묵시적으로 연결되기 때문입니다.

 

특별한 마지막 블록([0/1])이 필요하다는 점에 유의하여야 합니다.

위 그림에서 힙의 마지막 헤더는 할당 비트가 1로 세팅되어 있으며, 그 크기는 0을 갖습니다.

이를 에필로그 헤더(epilogue header)라 부릅니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 할당할 블록 결정하기

애플리케이션이 k 바이트의 블록을 요청할 때, 할당기는 요청한 블록을 저장하기에 충분히 큰 가용 블록을 리스트에서 검색합니다.

이때, 검색을 수행하는 방법은 first fit, next fit, best fit과 같은 배치 정책에 의해 결정됩니다.

 

 

 

 

👉 First fit (최초 할당)

처음부터 검색을 시작하여 맨 처음 크기가 맞는 블록을 선택하는 방법입니다.

모든 블록(할당되었거나, 가용한 블록)의 수에 비례한 시간이 소요됩니다.

리스트의 시작 부분에 작은 파편들이 다수 발생할 수 있습니다.

 

 

First fit은 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있습니다.

단점으로는 리스트에 앞부분에 작은 가용 블록들을 남겨두는 경향이 있다는 것인데, 이로 인해 큰 블록을 찾는 경우에 검색 시간이 늘어날 수 있습니다.

 

 

 

 

👉 Next fit (다음 할당)

first fit과 유사하지만, 이전에 검색이 종료된 위치에서 검색을 시작한다는 점이 다릅니다.

이는 이전 검색에서 가용 블록을 발견했다면 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 아이디어에서 착안한 방법입니다.

first fit에 비하여 매우 빠른 속도를 가지지만, 파편화가 first fit보다 더 심하게 발생됩니다.

 

 

 

 

 

👉 Best fit (최적 할당)

리스트를 검색하여 가장 근접한 크기의 블록을 선택하는 방법입니다.

파편화를 크게 예방할 수 있으나, 전체 리스트를 탐색하므로 first fit보다 훨씬 느리게 동작합니다.

 

 

 

 

 

 

 

 

 

 

 

 

🧐 Free 블록의 분할

할당기가 할당할 가용 블록을 찾은 후, 가용 블록의 어느 정도를 할당할지에 대해 결정하여야 합니다.

 

한 가지 방법은 해당 가용 블록 전체를 사용하는 것입니다.

이는 빠른 속도를 가지지만, 내부 파편화가 발생한다는 단점이 있습니다.

 

다른 방법으로는 가용 블록을 쪼개어, 할당할 블록과 새로운 가용 블록으로 나누는 방법이 있습니다.

 

아래 그림은 그 예시입니다.

Before

After

 

 

 

 

 

 

 

 

 

 

 

 

🧐 가용 블록 통합하기

할당기가 할당한 블록을 반환할 때, 새롭게 반환하는 블록에 인접한 다른 가용 블록들이 있을 수 있습니다.

이러한 인접 가용 블록들은 오류 단편화(false fragmentation)라는 현상을 유발시킬 수 있으며, 이때는 너무 작아 사용할 수 없는 가용 블록으로 쪼개진 많은 가용 메모리들이 존재합니다.

 

 

아래 그림을 통해 예시를 살펴보겠습니다.

 

색이 없는 부분이 free 블록

위 그림은 할당한 블록을 반환한 결과를 보여줍니다.

반환 이후 크기 4워드의 가용 블록과, 2워드의 가용 블록이 각각 존재합니다.

이 둘을 합친다면 5워드 크기의 메모리를 할당받을 수 있지만, 위 상황이라면 요청에 실패합니다.

 

오류 단편화를 극복하기 위한 실용적인 할당기라면 결합(coalescing)이라는 과정을 통해 가용 블록들을 통합해야 합니다.

 

 

이 과정에서 언제 연결을 수행해야 할지에 관한 중요한 정책결정을 해야 합니다.

할당기는 블록이 반환될 때마다 인접 블록을 통합해서 즉시 연결을 선택할 수 있습니다.

또는 일정 시간 후에 가용 블록들을 연결하기 위해 기다리는 지연 연결을 선택할 수도 있습니다.

 

예를 들어 할당기는 일부 할당 요청이 실패할 때까지 연결을 지연할 수 있으며, 그 후에 전체 힙을 검색해서 모든 가용 블록들을 연결합니다.

 

 

즉시 연결은 간단하며 상수 시간 내에 수행될 수 있지만, 일부 요청 패턴에 대해서는 블록이 연속적으로 연결되고 잠시 후에 분할되는 쓰래싱의 형태를 유발할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

🧐 경계 태그

할당기에서 연결을 구현하는 과정을 생각해 보도록 하겠습니다.

 

반환하려는 블록을 현재 블록이라고 하겠습니다.

이 경우 다음 가용 블록을 연결하는 것은 쉽고 또한 효율적입니다.

현재 블록의 헤더는 다음 블록의 헤더를 가리키고 있으며, 이것은 다음 블록이 가용한지 결정하기 위해 체크될 수 있습니다.

그렇다면 그 크기는 현재 블록의 헤더의 크기에 더해지고, 블록은 상수 시간 내에 연결될 수 있습니다.

 

그러나 이전 가용 블록을 연결할 수 있는 방법이 없습니다.

이전 가용 블록을 연결하기 위해 경계 태그(Boundary Tag)를 사용합니다.

이는 각 블록의 끝 부분에 푸터(footer, boundary tag)를 추가하는 것으로, 해당 푸터는 헤더를 복사한 것입니다.

만일 각 블록이 이와 같은 푸터를 포함하게 되면, 할당기는 시작 위치와 이전 블록의 상태를 풋터를 조사해서 결정할 수 있게 되며,

해당 풋터는 항상 현재 블록의 시작 부분의 한 워드 전에 존재합니다.

 

 

다음은 경계 태그를 포함한 블럭의 구조입니다.

 

 

 

 

 

 

 

 

🧐 경계 태그를 사용한 Coalescing

할당기가 현재 블록을 반환할 때 가능한 모든 경우는 다음과 같습니다.

1. 이전과 다음 블록이 모두 할당되어 있다.

다음과 같이 Coalescing이 발생하지 않습니다.

 

 

2. 이전 블록은 할당되어 있지만, 다음 블록은 가용상태이다.

다음과 같이 다음 블록과만 Coalescing이 발생합니다.

 

 

 

 

3. 이전 블록은 가용상태이고, 다음 블록은 할당되어있다.

다음과 같이 이전 블록과만 Coalescing이 발생합니다.

 

 

 

4. 이전 블록과 다음 블록 모두 가용상태이다.

다음과 같이 이전 블록과 다음 블록 모두와 Coalescing이 발생합니다.

 

 

 

 

경계 태그는 간단하고 유용한 개념이지만, 각 블록이 헤더와 푸터를 유지해야 한다는 단점이 존재합니다.

따라서 만일 애플리케이션이 작은 크기의 블록을 많이 다룬다면 상당한 양의 메모리 오버헤드가 발생할 수 있습니다.

 

 

 

이를 조금이나마 최적화 하기 위해, 할당된 블록에서는 풋터를 없애는 방법이 존재합니다.

현재 블록을 이전과 다음 블록과 연결하려고 할 때, 만일 이전 블록이 가용한 경우에만 이전 블록의 풋터에 있는 size 필드가 필요하다는 것을 알 수 있습니다.

현재 블록의 추가적인 하위 비트들 중의 하나에 이전 블록의 할당, 가용 비트를 저장하려고 한다면, 할당된 블록들은 풋터가 필요가 없어지고, 이 추가적인 공간을 데이터를 위해 사용할 수 있을 것입니다.

그러나 가용 블록은 여전히 푸터를 필요로 한다는 것에 유의해야 합니다.

 

 

 

 

 

 

 

🧐 묵시적 가용 리스트의 장단점

묵시적 가용 리스트의 장점은 단순함입니다.

 

단점으로는 가용 리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례한다는 것입니다.

(즉 linear time이 소요됩니다.)

 

메모리 사용량은 할당 정책(first fit, next fit, best fit)에 따라 다릅니다.

 

 

실제 malloc/free 구현 시에는 이용하지 않는데, 이는 위에서 살펴본 할당 시의 선형적인 성능 때문입니다.

그러나 이곳에서 살펴본 블럭의 분할과 경계 태그를 이용하여 가용 블럭을 통합(coalescing)하는 방법은 모든 할당기의 라이브러리에서 사용하는 방법입니다.