WEEK06 - TIL 명시적 가용 리스트(explicit free list)

 

9.9.13 명시적 가용 리스트

블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 '묵시적 가용 리스트'는 범용 할당기에는 적합하지 않다. (비록 힙 블록의 수가 사전에 알려져 있고, 작고 특수한 경우에는 좋을 수도 있으나)

→ 이보다 더 좋은 방법은 가용 블록들을 일종의 명시적 자료구조로 구성하는 것. 가용 블록의 본체는 프로그램에서 필요하지 않기에 이 자료구조를 구현하는 포인터들은 가용 블록의 본체 내에 저장될 수 있음.

ex. 힙은 그림처럼 가용 블록 내에 pred(이전)와 succ(다음) 포인터를 포함하는 이중 연결 가용 리스트로 구성될 수 있음.

 

묵시적 가용 리스트 대신 이중 연결 리스트를 사용하면 first fit 할당 시간을 전체 블록 수에 비례하는 것에서 가용 블록의 수에 비례하는 것으로 줄일 수 있지만, 블록을 반환하는 시간은 가용 리스트 내에서 블록을 정렬하는 정책을 어떤 것을 선택하냐에 비례하거나 상수 시간을 가질 수 있음.

 

- 한 가지 접근법: 리스트를 새롭게 반환하는 블록들을 리스트의 시작 부분에 삽입해 후입선출(LIFO)순으로 유지하는 것. LIFO순과 first fit 배치 정책을 사용하면, 할당기는 최근에 사용한 블록들을 먼저 조사하고 블록의 반환은 상수 시간에 수행됨. → 경계 태그 사용시 연결도 상수 시간에 수행

- 또 다른 접근법: 리스트를 주소 순으로 관리하는 것, 리스트 내 각 블록의 주소가 다음 블록의 주소보다 작은데, 이때 블록의 반환은 적당한 선행블록을 찾는 데 선형 검색 시간을 필요로 함. 절충은 주소 순서를 사용하는 first fit이 LIFO 순서를 사용하는 경우보다 best fit의 이용도에 근접하는 더 좋은 메모리 이용도를 가진다는 것.

 

명시적 리스트의 단점: 일반적으로 가용 블록들이 충분히 커, 모든 필요한 포인터 뿐 아니라 헤더, 추가적으로 풋터까지 포함해야 한다는 것 → 최소 블록 크기가 커지고 잠재적인 내부 단편화 가능성이 증가

 

※ 32bit 운영체제에서 최소 블록 크기는 header(4) + footer(4) + pointer(4) x 2 = 16byte