[WEEK07] 묵시적 가용 리스트

Implicit List

• 우리가 size와 allocation 상태를 알아야 하는 각각의 block에 대해서 2워드 안에 이 정보들을 저장할 수는 있지만 wasteful하다.

[출처] CMA system programming chap.19

• block들이 정렬되어 있으면, 어떤 low-order address bits는 항상 0이다.
• 항상 0인 비트를 저장하는 대신에 allocated/free flag로서 사용한다.
• size word를 읽을 때 이 비트를 mask out해야 한다.

자세한 Implicit Free List 예시

---

Free Block을 찾기

• First-fit
  • list의 처음부터 탐색을 시작해서, fit한 최초의 free block을 선택한다.
  • allocate & free된 총 block 개수만큼의 선형적인 시간이 걸린다.
  • 실제로는 리스트의 시작 부분에 splinter를 발생시킬 수 있다.

p = start; 
while ((p < end) &&     // not passed end
       ((*p & 1) ||     // already allocated
       (*p  <= len)))   // too small 
  p = p + (*p & -2);    // goto next block (word addressed)

• Next-fit
  • 이전의 탐색이 종료된 부분부터 리스트를 탐색하기 시작한다.
  • 관련없는 block들을 다시 스캐닝하는 것을 방지해서 first-fit보다 종종 빠르다.
  • 단편화가 더 심하다는 연구 결과도 있다.
• Best-fit
  • 리스트를 탐색해서, fit하면서 제일 적은 bytes가 남는 최적의 free block을 선택한다.
  • 단편화를 줄여서 메모리 utilization을 개선한다.
  • 일반적으로 first fit보다 느리다.

---

Free Block을 할당하기

• Splitting: allocated된 공간이 free 공간보다 작을 수 있기 때문에 우리는 아마 block을 분할하고 싶을 것이다.

void addblock(ptr p, int len) {
  int newsize = ((len + 1) >> 1) << 1;  // round up to even
  int oldsize = *p & -2;                // mask out low bit
  *p = newsize | 1;                     // set new length
  if (newsize < oldsize)
    *(p+newsize) = oldsize - newsize;   // set length in remaining
}                                       //   part of block

• splitting 정책
  • 언제 free blocks로 가서 분할하는가?
  • 얼마만큼의 내부 단편화를 허용할 것인가?

---

Block Free하기

• 가장 단순한 구현은 allocated flag를 clear하는 것 뿐이다.

void free_block(ptr p) { *p = *p & -2 } // XXXXXXXX & 11111110 = XXXXXXX0

• 하지만 이는 false fragmentation(오류 단편화)로 이어질 수 있다.
  • 충분한 free 공간이 있음에도 할당기가 그것을 찾지 못하는 상황을 말한다.

---

Coalescing

• 이전/다음 block이 free하다면 coalesce(연결)한다.
• next block과 연결하는 예시:

void free_block(ptr p) {
    *p = *p & -2;          // clear allocated flag
    next = p + *p;         // find next block
    if ((*next & 1) == 0)
    *p = *p + *next;     // add to this block if
}                          //    not allocated

• 그런데 previous block과는 어떻게 연결하지?

양방향 Coalescing

• Boundary tag (경계 태그)
  • size/allocated word를 free blocks의 bottom(end)에 복사한다.
  • 이것은 우리가 리스트를 역방향으로 순회하는 것을 가능하게 하지만, 추가적인 공간을 필요로 한다.
  • 중요하고 일반적인 기술! 🤓

Format of allocated / free blocks

상수 시간 Coalescing

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

연결 불가능 : 현재 블록 Allocated → Free

---

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

현재 블록이 다음 블록과 통합됨 : 현재 블록과 다음 블록의 footer는 현재 블록과 다음 블록의 크기의 합으로 갱신됨

---

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

현재 블록이 이전 블록과 통합됨 : 이전 블록의 header와 현재 블록의 footer는 두 블록의 크기의 합으로 갱신됨

---

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

세 블록 모두 하나의 Free 블록으로 통합됨 : 이전 블록의 header와 다음 블록의 footer는 세 블록의 크기의 합으로 갱신됨

---

경계 태그의 단점

• Internal fragmentation
• Optimized 될 수 있나?
  • 어떤 블록이 footer tag를 필요로 하는가?
  • 그것이 무엇을 의미하는가?

---

Coalescing 정책

• Immediate coalescing (즉시 연결) : free가 호출될 때마다 연결
• Deferred coalescing (지연 연결) : 필요할 때까지 coalescing을 미뤄서 free의 성능을 개선하려고 함
  • 예를 들어, malloc을 위해 free list를 스캔할 때 연결하거나
  • 외부 단편화의 양이 어떤 기준(threshold)을 넘었을 때 연결하거나

---

묵시적 리스트 요약

• 구현은 단순함
• Allocate 비용 : 최악의 경우 선형적인 시간
• Free 비용 : 최악의 경우 상수 시간 (+ coalesing)
• Memory 사용량 : 배치 정책에 따라 다름
• 실제로는 malloc / free에서 사용되지 않음 : 선형적인 시간 때문에...
• 그러나, splitting과 boundary tag coalescing의 개념은 모든 할당기에서 보편적으로 사용됨!