210120 개발일지(44일차) - 컴퓨터 시스템 9.9장 Malloc Lab 프로젝트(3) : implicit + nextfit 방법으로 구현 / explicit + firstfit 방법으로 구현하기

Github 주소 : https://github.com/kjhchs2/malloc-lab

implicit + nextfit 방법으로 구현하기

지난 번 포스팅에 올린 implicit + firstfit방법 말고 nextfit방법을 통해 점수를 많이 올릴 수 있었다.

• implicit list
• next fitnext fit은 저번 탐색 지점을 기억해, 그곳에서 출발해 충분한 블록을 만나면 그 블록을 선택한다. 내가 짠 코드에서는 마지막으로 할당시킨 블럭의 bp가 시작점이다. 끝 지점(epilogue block)까지 원하는 지점을 못만나면 시작 지점(prologue block)부터 bp까지 다시 탐색한다.
  ※ 이 bp를 표시하기 위해 우리는 last_bp라는 전역 변수를 사용한다.

장점 : 사용한 메모리를 위주로 비할당시킬 확률이 높다면 유리할 수 있다.
단점 : 최적의 메모리 사용은 아닐 확률이 있다.

explicit + firstfit 방법으로 구현하기

explicit list로 구현하는 것은 프리된 리스트들만 연결해서, 이 부분들만 탐색해서 들어갈 자리를 찾을 수 있다. 또, 여기서 의미하는 firstfit은 free block들을 연결해준 free list들을 순서대로 찾아가는 방법이다.
세부 구현은 github을 확인해보면 된다.
이 것이 free list 연결의 핵심!
여기서 내가 가장 헤맸던 점은 free block들을 연결해주는 방법(LIFO로 구현), free_listp의 위치를 옮겨주는 것과 이다!

참고 내용들

1. 전체적인 정리(통키의 블로그) : https://velog.io/@chosh/TIL-010-%EB%8F%99%EC%A0%81-%ED%95%A0%EB%8B%B9-%EB%A9%94%EB%AA%A8%EB%A6%AC-malloc-lab
2. 정민이의 카네기멜론대학 강의 핵심요약 :

   1. Knowing How much to free
      a. 기본적인 방식 : 블록의 앞에 블록 사이즈를 저장한다. 이를 header field(or header)라고 부른다. 모든 할당된 블록에 추가적은 워드가 필요하다.
   2. Keeping Track of Free Block
      a. Implicit list : 모든 블록에 길이와 할당 정보를 저장해서 사용한다.
      b. Explicit list : 해제된 블록 사이에 포인터를 사용한다.
      c. Segregated free list : Different free lists for different size classes
   3. Implicit Free Lists
      a. 블록 사이즈, 할당 여부 => 헤더에 저장
      b. 8 바이트 정렬에서 unused word가 필요할 수 있다.
      c. 이 때문에 내부 파편화가 일어날 가능성이 있다.
      d. One Word(0/1)을 리스트의 끝을 표기하기 위해 사용한다.
   4. Finding a Free Block
      a. First fit : 처음부터 리스트를 탐색해서 할당할 수 있는 크기를 가진 첫 번째 블록을 할당한다.
      b. Next fit : 이전에 탐색이 종료된 지점부터 리스트를 탐색하여 할당을 진행함.
      c. Best fit : 리스트 전부를 탐색해서 가장 적은 바이트에 할당할 수 있는 블록에 할당함.
   5. Allocating int Free Block
      • Splitting
      a. splitting : 할당된 공간보다 작아서 공간이 남을 때, 블록을 쪼개기.
      b. ((len+1) >>1) << 1 : 워드가 짝수이기 때문에(4or8) 길이를 짝수로 만듬.
      c. *p & -2 => -2는 이진수로 1111 1111 1111 1111이다. 그렇기 때문에 헤더의 마지막 3비트를(할당 여부) 초기화 시켜 새롭게 사용하게 해준다.
   6. Freeing a Block
      a. 할당 flag를 사용해서 할당을 해제해준다. p = p&-2
      b. flag를 사용하면 손쉽게 할당을 해제해 줄 수 있지만 splitting 하면서 남은 header가 있어 단편화를 만들어 낸다.
      c. coalesce를 진행해서 앞이나 뒤의 블록이 해제된 상태라면 연결시켜서 하나의 해제된 블록으로 만들어준다.
      d. 앞의 블록과 연결하기 위해 블록의 끝에 사이즈와 할당 정보를 복제해서 넣어준다. 그리고 뒤로 순회하면서 연결 시켜준다.(boundary tag)