Implicit Free List
header에 있는 block size로 다음 블록의 위치를 '묵시적'으로 가리킴
(가용 블록이 헤더 내 필드 'block size'에 의해 묵시적으로 연결)
- 장점: 구조 간단, 구현 편함
- 단점: 탐색 시 전체 블록 순회
<초기 힙 구성>
<전체 힙 구성>
여러 매크로/함수 함수 중 그림을 통해 이해한 몇 개를 기록하고자 한다.
1. extend_heap()
2. place()
3. coalescing()
Explicit Free List
블록의 payload 내에 predecessor/successor 포인터로 다음 가용 리스트의 위치를 '명시적'으로 가리킴
- 장점: 가용 블록끼리 연결되어 있어 전체 순회X
- 단점: 블록에 포인터/헤더/풋터까지 포함해 블록 크기 증가, 내부 단편화 발생 가능성
명시적 구현 코드를 찾아봤을 때, 초기 힙을 구성하는 방법이 두 가지로 나뉘는 것 같았다.
하나는 프롤로그 블록을 가용 블록과 같은 형태로 만들어 초기화하고 이걸 루트로 삼는 방법이었고,
또 하나는 프롤로그 블록 이후에 새 가용 블록을 만들어 이걸 루트로 삼는 방법이었다.
<프롤로그 블록 내에 pred/succ 포인터 넣어 초기화>
<프롤로그 블록 이후 새 가용 블록 만들어 초기화>
그림으로 보면 위와 같은 형태다. 처음엔 두 번째와 같은 방식으로 구현하려다, 직접 그리면서 이해하다보니 초기 힙 블록 개수의 차이를 보고 첫 번째 방식이 효율적이지 않을까 싶어 수정하였다.
<전체 힙 구성(블록 사이즈는 예시)>
위 사진에서 가용 리스트들을 물리적으로 따로 관리하는 게 아니라 포인터로 연결만 해주는 것.
결국 저 그림을 힙에 대입하면 아래와 같은 그림이 나온다.
저렇게 되면 succ이 뒤에를 가리키는 게 아닌가? 헷갈렸는데 그게 아니라 애초에 앞이 프롤로그고 뒤가 에필로그인 것
묵시적에서 추가된 것들만 기록
1. GET_PRED(), GET_SUCC() 매크로
2. add_free_block()
3. remove_free_block()
처음 명시적 코드를 봤을 때, 프롤로그 블록 앞에 쌓인다는 말이 뭔지 많이 헷갈려서 반나절을 고민했던 것 같다.
난 당연히 가용 블록끼리 연결된다면 프롤로그->에필로그 방향으로 퐁당퐁당 연결되는 걸로 예상했다.
그런데 LIFO 방식으로 구현하기 위해 프롤로그 앞으로 가용 블록들이 연결되면서 루트가 추가된 가용 블록으로 바뀌고,
결국 마지막엔 프롤로그 블록이 오면서 가용 블록 리스트의 끝을 알 수 있도록 하는 구현이었다.
(프롤로그 블록의 헤더를 보면 할당 상태, 즉 가용 블록 리스트 중 할당 상태인 것은 프롤로그 블록 단 하나)하나 생각해봐야 할 점은, 주소 기반 방식으로 구현을 하면 내가 생각했던 방식처럼 퐁당퐁당 연결이 되는지?
그리고 초기 힙을 구성할 때 프롤로그 안에 pred/succ 포인터를 넣는 것이 아닌, 프롤로그 뒤에 새 가용 블록을 만들고 시작한다면 루트도 가용 상태일텐데 그럼 뭘로 끝을 판단하는 지? 결국 어차피 가용 블록 리스트의 끝 블록은 succ가 NULL이지 않나? 그걸로 판단할 수 있지 않나?
또한 realloc 개선 부분을 하지 못 했다. 묵시적을 끝내고 realloc 개선을 우선으로 시도해보라고 정글 과제에도 적혀있었는데, 자세히 보지 않았던 것 같다.
명시적까지 끝냈더니 시간이 없어 못 하고 이미 7주차가 시작됐기 때문에, 다음에 시간 날 때 시도하거나 타 코드를 보고 이해해봐야겠다 일단 건너건너 들은 내용으로는, 본래 과제에서 주어진 realloc은 재활용하지 않고 새로 malloc을 하고, 이전 걸 free하는 식이었다고 한다. 개선된 realloc은 재활용하는 식인 것 같은데,, 제대로 알아본 적은 없어서 모르겠다ㅎ
