🖥[CSAPP] 9장. 분리 가용리스트 (Segregated Free List)

1. 분리 가용리스트 (Segregated Free List)란?

  -  대부분 2의 제곱수를 기준으로 각각 size class에 대한 Free list들을 구분한다. 

  -  Allocation 시 요청 크기에 맞는 Free list에서 가용 블록을 찾으므로 탐색 시간이 훨씬 줄어듦

  - 간단한 분리 저장장치 Simple Segregated Storage

      👉 Free 블록들의 크기는 size class의 가장 큰 사이즈로 한다.

      👉 각 free 블록들은 할당되어도 절대로 분할되지 않는다.

      👉 블록의 할당과 반환이 상수 시간에 이루어지지만 당연히 내부, 외부 단편화에 취약하다.

  -  각 size class에 대한 free list 안의 free 블록들이 동일한 크기를 갖는다.

 

2. 분리 맞춤 Segregated Fit

👉각 Free list 안의 가용 블록들은 서로 다른 크기를 갖지만, 해당 size class의 크기 범위보다 작거나 크면 안 된다.

 

 

3. 블록 할당 시

 - 요청한 사이즈에 해당되는 size class를 정한다

 - 해당 Free list를 First-fit 방식으로 검색해 적당한 크기의 블록을 찾는다.

 - 블록을 찾으면 블록을 분할하고, 분할한 새 가용 블록을 적당한 Free list에 넣는다.

 -  블록을 찾지 못했다면 다음 size class의 Free list를 검색한다.

 - 각 size class에 대한 free list들 안에 서로 다른 크기의 free 블록들의 배열들을 저장한다.