[Malloc-Lab] Explicit Free List & Segregated Free List

📍 Explicit Free List

• Organization

  • 할당이 해제되어 있는 블록들은 연결리스트 형태로 관리하는 방식이다.

  • free block내에 pred와 succ포인터를 포함하는 이중연결리스트로 구현할 수 있다. 이러한 구조 때문에 Explicit방식에서는 각 free block의 size 정보뿐만 아니라 이전과 다음 free block에 대한 정보를 명시적으로 가지고 있다.

  • 모든 block을 검색하는 implicit방식을 개선하여, 검색할 때 모든 블록을 검사하지 않고, 할당이 해제된 블록들만 검사하는 방식이다. (실제 성능은 implicit에서 next-fit방식과 유사)

    

  • free block들은 논리적으로 1번 그림과 같이 이중연결 리스트로 관리되지만, 실제로는 free block과 alloc block이 함께 존재하고, free block끼리만 pred와 succ포인터로 연결되어 있는 것이다.

  • 또한 연결리스트의 마지막 블록(prologue block)은 allocated block임.

• Allocating Blocks

  1. 연결리스트를 순회하면서 free block의 size를 확인한다.

  2. block size가 할당 size보다 작다면 해당 블록의 next포인터로 이동하여 다음 블록을 순회한다.

     

  3. block size가 할당하려는 size보다 크거나 같다면 할당한다.

     1. 해당 block을 free list에서 제외한다.

     2. block size가 할당할 수 있는 사이즈 공간보다 크다면, 블록을 분할하여 할당한다. 나머지 블록은 free block으로 변경한 후 연결리스트에 추가한다.

        할당 size가 정렬 기준 사이즈 공간보다 작다면 padding을 통해 해당 block을 정렬기준에 맞춘다.

     3. 메모리를 할당하고 해당 block의 주소를 반환한다.

  4. 할당할 수 있는 공간이 없다면 (연결리스트의 끝에 도달했다면) 힙을 확장한다.

  5. 제거된 block의 prev와 next를 수정하여 free list의 앞 뒤 block을 연결한다.

     

• Free Blocks - Insertion Policy - free한 block을 어디에 둘 것인가에 따라 2가지 정책을 사용한다.

  • LIFO(선입선출)

    • 단순하고 상수시간에 처리됨. (throughout 향상)

    • fragmentation이 address-ordered policy보다 안 좋음.

    • 📍 할당해제 과정

      1. 할당을 해제할 block의 주소를 받는다.

      2. 해제할 block의 앞 뒤의 block을 확인한다.

         1. free block이 없다면 해당 block만 연결리스트의 가장 앞에 추가하고 prev와 next를 설정한다.

      3. 해제할 block의 앞 혹은 뒤에 이미 free block이 있다면 해당 free block을 free list에서 제외한다.

         

      4. 해제할 block과 앞에서 제외한 free block과 합쳐 하나의 free block으로 만들고 연결리스트의 가장 앞에 추가한다.

         

  • Address-ordered

    • free list가 항상 address 순서대로 있도록 free list를 삽입. addr(prev) < addr(curr) < addr(next)
      
    • address 순서대로 배치해야 하기 때문에 검색이 필요함.
    • fragmentation이 LIFO보다 좋음. (memory utilization 향상) - coalesce 확률이 더 높기 때문

📍 Segrgated Free List

• free list 안의 block들을 size 별로(size-class) 구분하는 방식이다.
• 대부분 $2^n$을 기준으로 클래스를 나눈다. (1-2, 3-4, 5-8, 9-16, 17-32 …)

• Allocating Blocks
  • Free list가 주어지면 각 block들은 해당되는 size-class에 배치된다.
  • $2^n$을 class가 구분되어 있으므로 $O(log_n)$의 속도로 block이 어떤 size class에 속하는지 알 수 있다.
  • free block은 가장 처음에 맞는(first-fit) size class별로 구분하여 할당한다.
  • first fit 방식으로 탐색하지만, size class가 $2^n$을 기준으로 구분되어 있으므로 $O(log_n)$의 속도를 갖기 때문에 implict 방식보다 크게 개선된 thorughput을 가진다.
  • 또한 실제로 가장 적절한 size-class별로 구분하여 할당하기 때문에 best-fit 방식과 유사하므로 memory utilization에서 향상된 성능을 기대할 수 있다.

📌  참고 자료

Dynamic Memory Allocation : Basic Concepts 15-213 15-213: Introduction to Computer Systems 19th Lecture, Nov. 3, 2015

Dynamic Memory Allocation : Addvanced Concepts 15-213 15-213: Introduction to Computer Systems 20th Lecture, Nov. 5, 2015

Computer Systems A Programmers Perspective (3rd) - Randal E. Bryant • David R. O’Hallaron