가용 리스트: 묵시적/명시적/분리 Implicit/Explicit/Segregated
본 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있다면 언제든지 피드백을 주시면 감사하겠습니다. 참고로만 활용해주시길 바랍니다.
가용 리스트 Free List
가용 리스트는 동적 메모리 할당에서 사용되는 데이터 구조로, 현재 사용 가능한 메모리 블록(free block: 가용 블록)들을 관리하는 데 사용된다. 메모리 할당 및 해제 작업을 효율적으로 수행하기 위해 사용된다.
블록 Block
블록의 두 가지 예시: 좌) 묵시적 가용 리스트, 우) 명시적 가용 리스트
메모리를 관리하고자 구조화 한 것이 블록이다. 가용 리스트 구현 방식에 따라 블록의 형태는 달라진다.
각 메모리 블록 내에 할당 여부 정보를 저장하여 가용 블록을 관리한다.
- 헤더
- 보통 1워드로 잡는다.
- 블록의 크기(헤더와 추가적인 패딩 포함)를 저장한다.
- 블록이 할당 상태인지 가용 상태인지 인코딩한다.
- 만약 더블 워드 정렬 제한 조건을 선택한다면 블록 크기는 항상 8의 배수이고, 블록 크기의 하위 3비트는 항상 0이다. 그래서 블록 크기의 상위 29비트만 저장할 필요가 있으며, 나머지 3비트는 다른 정보를 인코드하기 위해 남겨둔다.
- 이 경우는 $001$이면 할당 상태이고, $000$이면 가용 상태이다. (Least Significant Bit, LSB 사용)
- 데이터
malloc()을 통해 할당한 데이터
- 패딩 (Optional)
- 가변적인 패딩
- 외부 단편화를 극복하기 위한 할당기 전략의 일부분이거나 정렬 제한 조건을 만족하기 위한 패딩일 수 도 있다.
- 풋터
- 헤더를 복사 한 것
- 이전 블록과
통합하기 위해 사용
- 블록 포인터
명시적 가용 리스트에서 이중 연결 가용 리스트로 사용Predecessor 포인터와Successor 포인터로 이루어짐.
묵시적 가용 리스트 Implicit Free List
묵시적 가용 리스트의 힙 블록 구성
묵시적 가용 리스트는 할당된 블록과 가용 블록을 헤더(Header)와 풋터(Footer)가 포함된 워드에 저장함으로써 간단히 구분하는 방식이다.
힙 내의 블록들이 헤더/풋터 내 필드에 의해 묵시적으로 연결된다. 할당기는 간접적으로 가용 블록 전체 집합을 힙 내의 전체 블록을 다니면서 방문할 수 있다.
- 가령, 현재 블록의 크기가 16바이트라면, 현재 블록에서 16바이트만큼 앞으로 이동하면 다음 블록을 선택할 수 있다.
가용 블록들을 통합하는 $연결_{coalescing}$이라는 과정에서 다음/이전 블록과 헤더와 풋터를 통해 연결할 수 있다.
그리고 힙의 끝을 나타내는 헤더인 $에필로그\;헤더_{Epilogue Header}$가 필요하다는 점에 유의해야 한다.
장점
- 단순하다.
단점
- 할당/재할당 등 가용 리스트를 탐색해야 하는 연산들의 비용이 전체 할당된 블록과 가용 블록의 수에 비례한다.
메모리 블록 구조
- Header
- Payload
- Padding
- Footer
묵시적 가용 리스트의 시간 복잡도 (n = 전체 블록 수)
| First Fit | Best Fit | Next Fit | |
|---|---|---|---|
| 할당 | $O(n)$ | $O(n)$ | $O(n)$ |
| 통합 | $O(1)$ | $O(1)$ | $O(1)$ |
| 해제 | $O(1)$ | $O(1)$ | $O(1)$ |
| 재할당 | $O(n)$ | $O(n)$ | $O(n)$ |
명시적 가용 리스트 Explicit Free List
묵시적 가용 리스트는 구현이 간단하지만 블록 할당 시간이 전체 힙 블록의 수에 비례한다는 단점이 있다.
이중 연결 가용 리스트를 사용하는 힙 블록의 구성
명시적 가용 리스트 Explicit Free List는 가용 블록들을 일종의 명시적 자료구조로 구성하는 방법이다.
가용 블록의 Payload는 필요하지 않기에 이 자료구조를 구현하는 포인터들은 가용 블록의 Payload에 저장될 수 있다.
명시적 가용 리스트에서 힙은 각 가용 블록 내에 $Predecessor$ 포인터와 $Successor$ 포인터를 포함하는 이중 연결 가용 리스트로 구성될 수 있다.
기존 묵시적 가용 리스트에서 전체 블록 수에 비례하는 시간이었던 First Fit 할당 시간을 가용 블록의 수에 비례하는 것으로 줄일 수 있다.
- 또한 Best Fit 할당 시간을 가용 블록의 수에 비례하는 것으로 줄여 효율이 좋아진다.
하지만 블록을 반환하는 시간은 가용 리스트 내에서 블록을 정렬하는 정책에 따라 비례하거나 상수 시간을 가질 수 있다.
후입선출(LIFO) 정책을 사용하여 반환한 블록들을 가용 리스트의 맨 앞에 넣어준다면, 상수 시간에 수행될 수 있다.Address-Ordered 정책을 사용하여 반환한 블록들을 가용 리스트에 주소 순으로 넣어주는 방법도 있다.
분리 가용 리스트 Segregated Free List
위에서 살펴본 명시적 가용 리스트처럼 단일 연결 가용 블록 리스트를 사용하는 할당기는 한 개의 블록을 할당하는 데 가용 블록의 수에 비례하는 시간이 필요하다.
다수의 가용 리스트
할당 시간을 줄이는데 대표적인 방법으로 알려진 분리 가용 리스트는 다수의 가용 리스트를 사용하여 각 리스트는 거의 동일한 크기의 블록들을 저장한다.
기본적인 아이디어는 모든 가능한 블록 크기를 $크기\;클래스_{Size\;Class}$라고 하는 동일 클래스의 집합들로 분리하는 것이다.
크기 클래스를 정의하는 많은 방법들이 존재하고, 대표적으로 블록 크기를 $2^k$로 분리할 수 있다.
- $e.g.$ {1}, {2}, {3, 4}, {5-8}, … , {1,025-2,048}, {2,049-4,096}, {4,097-$\infty$}
할당기는 가용 리스트의 배열을 관리하고, 크기 클래스마다 크기가 증가하는 순서로 한 개의 가용 리스트를 가진다. 할당기가 크기 $n$의 블록이 필요하면 적당한 가용 리스트를 검색한다. 만일 크기가 맞는 블록을 찾을 수 없다면, 다음 리스트를 검색하는 식으로 진행된다.
분리 맞춤 Segregated Fits
분리 맞춤 방식은 할당기는 가용 리스트의 배열을 관리한다. 각 가용 리스트는 크기 클래스에 연관되며, 일종의 명시적 또는 묵시적 리스트로 관리된다.
각 리스트는 잠재적으로 서로 다른 크기의 블록을 포함하고 있으며, 이들의 크기는 해당 크기 클래스에 포함된다.
블록을 할당하기 위해서 요청된 크기 클래스를 결정하고, 크기가 맞는 블록을 위해 해당 가용 리스트를 First Fit 또는 Best Fit으로 검색한다. 만일 블록을 찾으면 (선택적으로) 블록을 분할하고, 나머지를 적당한 가용 리스트에 삽입한다. (각 클래스는 $2^k$ 이상 $2^{k+1}$ 미만의 크기를 가진 블록을 저장한다.)
만일 맞는 블록을 찾지 못하면, 다음 크기 클래스를 위한 가용 리스트를 검색한다. 블록을 찾을 때까지 이 과정을 반복한다.
만일 가용 리스트 어느 곳에서도 맞는 블록을 찾지 못한다면, 추가적인 힙 메모리를 요청하고, 새 힙 메모리에서 이 블록을 할당하며, 나머지를 적절한 크기의 클래스에 배치한다. 블록을 반환하기 위해서 그 결과를 적절한 가용 리스트에 배치하고 연결한다.
버디 시스템 Buddy System
버디 시스템은 각 크기 클래스가 2의 제곱인 특수한 경우의 분리 맞춤 방식이다.
기본 아이디어는 $2^m$개의 워드를 갖는 힙이 주어지면 각 블록의 크기가 $2^k$인$(0\le k \le m)$, 분리 가용 리스트를 사용하는 것이다.
- 가령, 16개의 워드를 갖는 힙이 주어지면, 각 블록의 크기가 1, 2, 4, 8, 16인 분리 가용 리스트를 사용한다.
요청된 블록의 크기들은 인접한 2의 제곱으로 올림한다.
크기 $2^k$의 블록을 할당하려면, $k \le j \le m$인 크기 $2^j$인 첫 번째 가용 블록을 찾는다.
만약 $j=k$라면 끝난 것이고, 아니라면 재귀적으로 $j=k$일 때까지 블록을 절반으로 분할한다.
이와 같은 분할을 수행할 때 생기는 두 개의 블록은 서로가 서로의 버디 Buddy 가 되고, 해당 가용 리스트에 배치된다.
크기 $2^k$의 블록을 반환하려면, 반환하려는 블록의 가용 버디들을 계속해서 연결한다. 할당된 버디를 만나면 연결을 중단한다.
버디 시스템의 핵심은 블록의 주소와 크기가 주어지면 이 블록의 버디 주소를 계산하기 쉽다는 것이다.
가령, 크기가 32바이트인 블록의 주소가 다음과 같다면,
$xxx…x00000$
버디의 주소는 다음과 같다.
$xxx…x10000$
즉, 블록과 이 블록의 버디 주소는 정확히 한 비트 위치만 다르다.
그리고 버디 시스템에서는 블록을 반으로 분할하여 블록들을 나누기 때문에 각 블록의 크기를 풋터에 저장할 필요가 없다.
버디 시스템 할당기의 중요한 장점은 빠른 검색과 연결이다.
주요 단점은 블록 크기가 2의 제곱이라는 사실로, 큰 내부 단편화를 유발할 수 있다.
그래서 버디 시스템 할당기는 범용 부하에 대해서는 부적합하지만, 특정 응용에 국한된 부하에 대해서 블록 크기가 사전에 2의 제곱이라고 알려진 경우, 버디 시스템 할당기는 일정 효과를 거둘 수 있다.
구현
아래 Git 주소는 CMU의 malloc-lab 과제를 구현한 것이고, 나는 묵시적 / 명시적 / 분리 가용 리스트를 구현하였다.
참고