[sp] Dynamic Memory Allocation : Advanced (1)

1. Explicit free list : 포인터를 사용하여 free 블럭만 순회할 수 있음

 

(1) free block의 리스트를 유지, (모든 블럭 아님)

- NEXT free block은 어디에나 있을 수 있음

 -> 따라서 free 블럭의 사이즈, 앞/뒤의 free 포인터 필요

- coalescing을 위한 boundary tag 필요

- free한 블럭만 추적할 수 있으므로, payload 영역 사용 가능

 

(2)

 

- 블럭은 임의의 순서로 있을 수 있음

 

(3) Allocating from explicit free lists

 

 

(4) Freeing with explicit free lists

- Insertion policy : 

   1. LIFO (last-in-first-out) policy : free list의 시작 부분에 free된 블럭을 삽입

                                            : 장점: 간단하고 일정한 시간

                                            : 단점: fragmentation은 address ordered보다 나쁠 수 있음

 

 

ex) case 1 : 앞 뒤 모두 allocated

리스트의 root에 free된 블럭을 삽입

 

 

case 2 : 앞이 allocated

후속 블록을 분리하고 두 메모리 블록을 합친 다음 목록의 루트에 새 블록을 삽입

 

 

case 3 : 뒤가 allocated

선행 블록을 분리하고 두 메모리 블럭을 합친 다음, 리스트의 루트에 새 블럭 삽입

 

 

Case 4 : 앞뒤 free

 

앞 뒤 블럭을 분리하고 3개의 메모리 블럭을 모두 합친 후, 리스트의 루트에 새 블럭 삽입

 

  2. Address-orderd policy : free list block들은 address order대로 있도록 freed 한 블럭을 삽입

   ->  address : prev < curr < next

    : 장점 : fragmentation이 LIFO 보다 느림

 

 

 

(5) Summary

- comparison to implicit list

 : 할당은 모든 블럭 대신 free 블럭의 수 만큼의 선형 시간 -> 메모리가 가득 찼을 때 훨씬 빠름

 : 목록 안팎으로 블럭을 분리해야 하기 때문에 할당가 해제가 좀더 복잡함

 : 연결에 대한 추가적인 영역 필요 ( 각 블럭 마다 추가적인 2 word 공간 필요_

 

- 연결 리스트의 가장 흔한 사용은 segregated free list와 함께 쓰임

 -> 크기가 다른 사이즈의 클래스의 또는 object의 다른 type에 대한 여러 연결 리스트를 유지