동적 메모리 할당 분리가용 리스트

Segregated list Allocator(분리가용리스트)

- seg-list는 explicit의 개선 방법입니다. 할당이 해제되 가용 블록들을 크기별로 모아줌으로써 좀 더 빠른 search가 가능합니다.

- explicit 방식과 동일하게 연결리스트를 만들지만 사이즈별로 만들어야 하기 때문에 여러개의 연결리스트가 필요합니다. 여러개의 연결리스트 포인터를 힙에 저장하여 특정한 사이즈의 메모리를 할당하고자 하면 해당 사이즈에 맞는 연결리스트로 이동하여 할당할 블록의 위치를 찾습니다. 할당하는 메모리의 사이즈를 나누는 단위는 정해지지 않았지만 대부분 2^n 단위로 나누게 됩니다.

 

 

// Global var
// seg-list를 table로 만들어줍니다.
void *segregated_free_lists[LISTLIMIT];

// 가용 블럭 insert 과정입니다.

int list = 0;
    
// Select segregated list
// 비트 연산을 통해 2^n으로 새로 가용된 블럭의 크기를 해당 인덱스로 찾아줍니다.
while ((list < LISTLIMIT - 1) && (size > 1)) {
  size >>= 1;
  list++;
}

// Keep size ascending order and search
// 해당 index의 해당하는 root ptr값을 리턴해주고 explicit과 동일한 LIFO방식으로 insert 해줍니다
search_ptr = segregated_free_lists[list];