[WEEK07] 명시적 가용 리스트와 분리 가용 리스트

Explicit Free Lists

[출처] CMA system programming chap.19

• 모든 block이 아닌, free block의 리스트만 유지한다.
  • next free block은 어느곳이나 가능하다.
  • 그래서 우리는 size 뿐만 아니라 이전/다음 포인터도 저장해야 한다.
  • 여전히 coalescing에는 boundary tag가 필요하다.
  • 다행히도 우리는 free block만 추적할 것이기 때문에, payload area를 사용할 수 있다.
• 논리적으로는

• 물리적으로는 : block들이 아무 순서로도 가능하다 😵

Explicit Free Lists에서 Allocating하기

Explicit Free Lists로 Freeing하기

• Insertion 정책 : free list의 어디에 새롭게 free된 block을 넣을 것인가?
• LIFO 정책
  • free list의 시작 부분에 freed block을 삽입한다.
  • 장점 : 단순하고 상수 시간 가능
  • 단점 : Address-ordered 정책보다 단편화가 심하다

• Address-ordered 정책
  • free list 내의 block들이 항상 주소 순서대로 있도록 삽입한다 : addr(prev) < addr(cur) < addr(next)
  • 장점 : LIFO보다 단편화가 낮다
  • 단점 : 탐색이 필요하다

LIFO 정책으로 Freeing하기

1️⃣ Case 1 : 이전 블록 Allocated / 다음 블록 Allocated

Free block을 list의 root에 삽입한다.

---

2️⃣ Case 2 : 이전 블록 Allocated / 다음 블록 Free

successor 블록을 나누고 두 메모리 블록들을 연결해서 새로운 블록을 리스트의 루트에 삽입한다.

---

3️⃣ Case 3 : 이전 블록 Free / 다음 블록 Allocated

predecessor 블록을 나누고 두 메모리 블록들을 연결해서 새로운 블록을 리스트의 루트에 삽입한다.

---

4️⃣ Case 4 : 이전 블록 Free / 다음 블록 Free

predecessor와 successor 블록을 나누고 세 메모리 블록들을 연결해서 새로운 블록을 리스트의 루트에 삽입한다.

Explicit Free Lists 요약

• Implicit list와 비교했을 때
  • 모든 블록 대신 free block의 수에 비례해 선형적이다.
  • 거의 모든 메모리가 가득 찼을 때 훨씬 빠르다.
  • 리스트 안밖에서 block을 나눠야 하기 때문에 allocate/free가 약간 더 복잡하다.
  • 각 블록마다 2워드만큼의 추가적인 공간이 연결을 위해 필요하다. (내부 단편화 증가 가능😞)
• 연결 리스트의 가장 흔한 사용은 segregated free list와 함께 사용될 때다.
  • 서로 다른 size class의 다중 연결 리스트를 유지하거나, 아니면 다른 타입의 객체도 가능하다.

---

Segregated Free Lists (Seglist)

Seglist 할당기

• 각각의 블록의 size class는 개별적인 free list를 가진다.

• 종종 각각 작은 size별로 분리된 class를 가진다.
• 큰 size에 대해서는 각각의 2ᵏ size마다 하나의 class를 가진다.
• free lists의 배열에 대해서, 각각은 어떤 size class에 대응된다.
• size n인 block을 allocate하기 위해서
  • size가 m > n인 블록에 대응되는 적절한 free list를 찾는다.
  • 적절한 블록이 발견되면, 블록을 분할해서 적절한 리스트에 fragment(조각)을 배치한다 (optional)
  • 블록이 발견되지 않으면, 다음번째로 큰 class에서 시도한다.
  • 블록이 발견될 때까지 반복한다.
• 블록이 발견되지 않으면
  • (sbrk()를 사용해서) OS로부터 추가적인 heap memory를 요청한다.
  • 이 새로운 메모리로부터 n바이트의 블록을 allocate한다.
  • 가장 큰 size class 안에 single free block으로 나머지를 배치한다.
• 블록을 free하기 위해서, 연결 후 적절한 리스트에 배치한다.
• Seglist 할당기의 장점
  • 더 높은 throughput : 2ᵏ size class에 대응하는 log time
  • 더 나은 memory utilization
    
    • seglist의 first-fit 탐색은 전체 힙에 대한 best-fit 탐색에 근접한다.
    • 심지어는 각 블록마다 size class를 따로 주는 것은 best-fit과 동일하다.

• 특정한 size의 free block들을 연결하는 리스트들의 배열을 사용한다.
• 인덱싱 목적으로 size 클래스를 사용한다. (주로 2ᵏ 크기를 사용함)
• 요청받은 size는 가장 가까운 사용 가능한 size로 반올림된다.
• Simple segregated list
  • free block의 splitting 없음
  • 극심한 외부 단편화 발생
• Segregated fit (분리 맞춤)
  • 적절한 free list에 free block이 없다면 더 큰 블록들을 split한다.
  • free block을 찾기 위해 first-fit 또는 next-fit을 사용한다.
  • 다음 세 가지 타입이 있다:
    1. exact list
    2. strict size classes with rounding
    3. size classes with range lists

Buddy system

• 분리 맞춤의 특별한 케이스다.
  • 제한적인 splitting과 coalescing을 도와준다.
  • free list를 각각의 허용 가능한 size로 나눈다.
  • 단순한 블록 주소 계산을 수행한다.
• free 블록은 그것의 고유한 buddy와만 결합될 수 있다.

3MB가 요청된 경우의 예시

• 종류 : Binary buddy, Fibonacci buddy, weighted buddy, double buddy, …
• Deferred coalescing : 블록들은 free되자마자 결합되지는 않는다. 대신 quick list나 subpool을 사용한다.
• Deferred reuse : 최근에 free된 블록들은 즉시 재사용되지는 않는다.

Seglist 요약

• size에 기반해 다중 free block들을 관리한다.
• 충분히 큰 블록을 더 빠르게 찾도록 보장되기 때문에 throughput을 개선할 수 있다.

각 구현 방식들의 Performance 비교