[Malloc-Lab] My Study - Implicit Free List

First-fit

• heap을 맨 처음부터 뒤지기 시작해서 처음으로 요청받는 메모리보다 size가 더 큰 free block을 할당한다.

• 만약 heap의 앞에 size가 작은 block들만 남아있으면 탐색시간이 길여지므로 throughput가 떨어진다.

• 또한 처음으로 발견하는 block이 요청받은 메모리보다 사이즈가 훨씬 클 경우에도 그냥 할당하기 때문에 단편화가 발생하기 쉽다.

  Internal Fragmentation - 요청하는 메모리보다 큰 size의 block을 할당하기 때문에 메모리 누수가 발생할 수 있다.

  External Fragmentaiton - split을 통해 남은 공간을 다시 free block으로 반환해도, size가 작은 블록이 생기는 것이기 때문에 단편화가 발생할 수 있다.
  

Best-fit

• heap을 맨 처음부터 끝까지 검색하여 요청받는 size와 가장 크기가 비슷한 free block을 할당한다.
• fragmentation을 최소화하나, 매번 힙 전체를 다 검색해야 하기 때문에 throughput이 크게 떨어질 수 있다.

Next-fit

• 가장 마지막으로 할당된 block의 정보를 보관하고 있다가 다음 메모리 할당 요청 시 가장 마지막으로 찾았던 free block의 다음 block 부터 탐색하는 방식이다.

Next-fit vs First-fit

• first-fit은 매 탐색마다 heap을 맨 처음부터 탐색하기 때문에 초반에 크기가 작은 free block들만 많이 있을 경우 비효율적으로 탐색을 하게 됨. → throughput 감소 Next-fit은 가장 마지막으로 할당된 블록이후부터 탐색하기 때문에 앞에 크기가 작은 free block들이 많을 경우에 이들을 탐색하지 않기 때문에 → throughput 향상