Explicit Allocator - Segregated Free List

https://kimjingyu.tistory.com/entry/Explicit-Allocator-Explicit-Free-List

Explicit Allocator - Explicit Free List

 

Segregated Free List 소개

위 포스팅에서 살펴본 바로 단일 연결 블록 리스트를 사용하는 할당기는 한 개의 블록을 할당하는데 가용 블록의 수에 비례하는 시간이 필요하다. 이때 할당 시간을 줄이는 대표적인 방법으로 알려진 segregated storage는 다수의 가용 리스트를 유지하면서, 각 리스트는 거의 동일한 크기의 블록을 저장하게 한다. 즉, 모든 가능한 블록의 크기를 다음과 같이 size class라고 하는 동일 클래스의 집합들로 분리하는 것이다. 

 

이런 size class를 정의하는 많은 방법들이 존재하는데, 블록 크기를 2의 제곱으로 나눌 수도 있고, 크기가 작은 블록들은 자신의 크기 클래스에 할당하고, 큰 블록들은 2의 제곱으로 분리할 수도 있다.이렇게 할당기는 free list의 배열을 관리하고, size class마다 크기가 증가하는 오름차순 순서로 하는 연결 리스트들을 가진다.

 

 

장점

이렇게 하면 좋은 점이 bitwise 연산을 이용해서 빠르게 요청된 block의 크기에 맞는 free list를 찾을 수 있다는 점이다. 따라서 segregated list를 사용하고, 각 연결리스트마다 오름차순으로 정렬하고, first fit 정책을 사용하면 best fit을 사용한 것처럼 동작한다. 왜냐하면, 오름차순에서 first fit을 수행하면 들어갈 수 있는 가장 적합한 free block에 들어가게 되기 때문이다. 덕분에 전체 힙을 best fit 검색하는 방법을 단순화했다고 볼 수 있다.

 

 

구현