[sp] Dynamic Memory Allocation (3)

1. Implicit List : Bidirectional Coalescing

(1) Boundary tags

- free block의 bottom(end) 부분에 블럭의 사이즈를 입력

- list를 거꾸로 탐색할 수 있음, 추가 공간 필요

블럭의 마지막에 사이즈 적음 -> footer

 

 

(2) Constant Time Coalescing

- Case 1

 

- Case 2

 

- Case 3

 

- Case 4

 

 

2. Allocated block vs free block

(1) 이전 블럭이 allocated라면, 이전 블럭의 boundary tag 필요 없음

(2) 이전 블럭이 free라면, 이전 블럭의 boundary tag가 필요 -> 블럭의 크기를 알 수 있음