개념
- 모든 블록이 아니라, free 블록의 리스트를 관리한다.
- 결합을 위해 boundary tag는 여전히 사용한다.
- 값이 있을 경우 payload를 값을 담을때 사용하고, 아닌 경우 payload를 이전/다음 free block의 포인터를 담기 위해 사용한다.
- malloc으로 분할이 생기면, 포인터 저장 위치가 뒤로 밀릴 수도 있다.
삽입정책
- 새로 free한 블록의 리스트를 저장하는 방법을 정해야 한다. ( 현재 free 블록에 어디를 저장할지?)
- LIFO (Last In First Out)
- 새로 free한 블록을 링크드 리스트 맨 앞에 둔다.
- 장점 : 간단하다. 일정한 시간이 소요된다.
- 단점 : 주소 순서로 관리하는 것보다 파편화가 심해진다.
- Address-ordered
- free블록을 링크드 리스트에서 주소 순으로 배치한다.
- 장점 : 탐색을 해야 한다.
- 단점 : 파편화가 더 LIFO보다 낫다.
LIFO 방식
