동적 메모리 할당 part 2

part1에서는 묵시적 가용 리스트(implicit list)에 대해 알아보았다. part2는 명시적 가용리스트에 대해 알아 보겠다.

명시적 가용 리스트(explicit list)

• 묵시적 가용리스트는 블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 묵시적 가용리스트는
  범용 할당기에 적합하지 않다.
• 더 좋은 방법은 가용 블록들을 명시적 자료구조로 구성하는 것이다.
  

  

• implicit list 대신 이중 연결 리스트를 사용하면 first fit 할당 시간을 전체 블록 수에 비례하는 것에서 -> 가용 블록의 수에 비례로
  바꿀 수 있다.
• 첫번째 접근법으로는, 새롭게 반환(free)된 블록들을 리스트의 시작 부분에 삽입해서 LIFO순으로 유지하는 것이다.
• 두번째 접근법으로는, 리스트를 주소 순으로 관리하는것으로, 리스트 내 각 블록의 주소가 다음 블록의 주소보다 작다.

단점

- 최소 블록 크기가 거지고 잠재적인 내부 단편화internal fragmentation) 가능성이 증가한다.

 

 

input list

 

input list2

input list3

 

delete 가용 리스트

delete 가용 리스트

delete 가용리스트

첫번째 가용리스트 삭제

place 함수

구현 : https://github.com/grapestore/malloclab