🖥[CSAPP] 9장. Malloc Lab 명시적 가용(Explicit Free List)리스트 구현하기
1. 명시적 가용 리스트란?
- 명시적 가용리스트는 가용 블록을 명시적 자료구조로 구성하는 것이다.
- 가용 블록들끼리 포인터로 연결한다. 다음 가용 블록의 위치를 명시적으로 알 수 있다.
- 하나의 더블 연결 리스트를 만들어 가용 블록들을 연결한다.
- 가용 블록은 헤더와 풋터 말고는 데이터를 필요로 하지 않으므로, 가용 블록 안의 payload 자리에 다음 가용 블록과 이전 가용 블록의 주소를 저장한다. (가용 블록 안에 포인터가 삽입)
- 할당된 블록을 반환하는 정책은 두가지가 있다.
👉 LIFO(후입선출) 방법 이용하기
👉 블록의 주소이용하기
- 이중 연결 가용 리스트를 이용하여 명시적 가용 리스트를 구현할 경우 first fit 탐색 시간을 가용 블록의 수로 줄일 수 있다.
2. Explicit Free List의 할당
- 해당 가용 리스트를 분할한 다음 새 가용 블록을 기존 가용 블록과 링크되었던 이전블록과 링크한다.
3. 새로 반환된 가용 블록을 free list 어디에 링크해야할까?
(1) LIFO(Last In First Out) 방안
- Free list의 처음에 새 반환 블록을 넣는다.
- 간단하고 O(1) 의 시간 복잡도를 갖지만, Adress ordered 방법보다 단편화 발생 확률이 높다.
(2) Adress Ordered 방안
- 이전 블록의 주소 < 현재 블록의 주소 < 다음 블록의 주소
- 단편화 확률은 낮아지지만 탐색 시간이 필요하다. RBTree 같은 탐색시간이 빠른 자료구조를 사용한다고 해도 Segregate방법이나 Best fit 보다는 느리다고 한다.
3. LIFO 방안을 이용한 반환
(1) Case 1 : 반환 블록 양 쪽이 할당 블록
- Free List의 맨 앞을 반환 블록으로 만들어준다.
- Free List의 Root의 Next를 반환 블록과 연결
-기존의 Root와 연결되었던 블록을 반환 블록의 Next와 연결
(2) Case 2 : 반환 전 : 할당블록, 후 : 가용블록
- 직후 블록을 Free List에서 떼어낸 다음, 반환 블록과 연결
-이 새블록을 Free List의 Root와 연결
(3) Case 3 : 반환 전 : 가용블록, 후 : 할당블록
- 직후 블록을 Free List에서 떼어낸 다음, 반환 블록과 연결
-이 새블록을 Free List의 Root와 연결
(4) Case 4 : 반환 블록 양 쪽이 가용 블록
- 직후 블록을 Free List에서 떼어낸 다음, 반환 블록과 연결
-이 새블록을 Free List의 Root와 연결