개념

• 모든 블록은 크기& 할당 상태가 필요하다.

  • 이를 하나의 워드에 저장한다.
  • 블록이 정렬된 상태라면, 주소의 몇몇 낮은자리 비트는 언제나 0이다.
    • 이를 allocated/free flag로 쓴다.
  • 크기가 기록된 워드를 볼 때, 해당 플래그도 같이 본다.

  

  • 헤더 뒤에는 malloc을 불렀을 때 요구한 데이터가 따라온다.
  • 그 뒤에는 패딩이 올 수도 있다.

힙에서 저장된 예시

묵시적 가용 리스트에서 free block 찾기

• First fit

  • 리스트 첫번째부터 시작하여, 사이즈에 맞는 첫번째 free block을 찾는다.
  • 전체 블록의 수 만큼의 시간이 걸릴 수 있다.
  • 리스트 처음에 “파편”을 야기 시킬 수 있다.
    • 앞 부분에 작은 가용 블록들을 남겨두는 경향이 있다.

  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

  • First Fit과 유사하나, 이전에 탐색이 종료된 곳부터 찾는다.
  • First Fit 보다 빠르다.
  • 파편화가 First Fit보다 더 심하다.

• Best Fit

  • 리스트를 탐색하여, 최선의 free block을 찾는다.
    • 필요한 메모리와 사이즈가 가장 유사한 것.
  • 파편화를 가장 적게 한다.
  • 보통 First Fit 보다 느리다.

가용 블록의 분할

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

가용블록 free

• allocated flag를 해제해준다.

void free_block(ptr p) { *p = *p & -2 }

• & -2 하는 이유
• 단 이 경우 false fragmentation이 발생 가능하다.
  • free한 공간이 충분히 있음에도 불구하고 malloc이 불가능함

연결