이전 두 게시글을 통해 정적과 동적, 명시적과 묵시적에 대해 자세히 알아보았다.
그럼 이제 malloc을 구현할 차례이다.
나의 블로그는 코드 한줄 한줄 설명하지는 않는다.
그런건 나보다 뛰어나신 분들이 훨씬 잘 정리해두었으니 그 글을 보길 바란다. 물론 나도 github에 주석을 정말 열심히 달아두긴 했다.
그럼 나는 뭘 쓰냐고?
생각의 흐름 (이라고 쓰고 의식의 흐름이라 말한다.)
1. 메모리 할당 요청이 들어오면 가용블록을 찾는다.
(어떻게?)2. 가용블록에 할당을 한다.
(사이즈가 딱 안맞아서 남으면?)3. 해제 요청이 들어온다.
4. 해제 해준다.
(전 후에 가용블록이 있다면?)
어떻게 가용블록을 찾느냐에 따라서 explicit allocator 구현 방식들이 나뉜다.
Implicit free list에서는 payload(우리가 진짜 저장하고 싶은 데이터) 앞 뒤에 header와 footer를 둔다.
header와 footer에는 똑같은 정보가 들어간다.
1. 사이즈, 2. 할당여부
왜 header가 있어야 할까?
그럼 역으로 질문해보자. 없다면 어떻게 될 것인가?
만일 header가 없다면 사이즈가 40byte인 블록이 할당될 때 어떤 과정을 거치는지 생각해보자.
heap을 앞에서부터 1word(32bit 시스템에서는 4byte)마다 계속 문을 두들거야 할것이다. "나 여기에 들어가도 될까?" 할당이 안되어있다면, 그 다음 블록이 할당되어있는지 9번 더 검사를 해야한다. 연속 10번 비어있을 때까지... (아이고 내가 다 힘들다...)
컴퓨터는 우리처럼 멀리서 전반적인 상황을 알고 있지 못한다는 것을 항상 기억하자.
하지만 header가 있다면?
문을 두들겼을 때, 난 사이즈가 32이고 할당되어있어! 그러니 8칸 뒤로가! 라고 할당된 블록이 말해줄 것이고 우린 훨씬 덜 문을 두들기게 되었다.
그럼 footer는?
위에서 말한 4번 과정(해제해 줄 때)을 수행할 때, 우린 중요한 과정을 하나 더 거쳐야 한다.
그것은 바로 앞, 뒤로 가용블록이 있는지 확인을 하고 있다면 합치는 과정.
코드 구현에선 이 과정을 coalesce 함수로 구현한다.
왜 coalesce 과정이 필요할까?
40사이즈(가용), 48사이즈(할당), 60사이즈(할당)
이런 사이즈들의 블록들이 있다고 해보자.
내가 만일 여기서 할당된 48사이즈 블록을 해제해주었다.
그리고 80사이즈 블록을 할당하려고 한다.
만일 coalesce과정이 없어서 가용상태인 40, 48사이즈 블록이 합쳐지지 않았다면
컴퓨터는 음! 40엔 못들어가! 48에도 못들어가! 이렇게 판단을 한다
우리가 봤을 땐 아니!!!! 둘이 합치면 88이잖아!!! 이렇게 답답해해도 안된다... 컴퓨터는 그런 애다...
아무튼 저런 경우를 막기 위해서 지금 블록이 해제 될 경우, 앞 뒤에 가용블록이 있을 때 합쳐주어야 한다.
그럼 본론으로 돌아가서.
왜 footer가 필요할까?
40사이즈(가용), 48사이즈(할당), 60사이즈(가용)
이 예시를 봐보자
내가 만일 48사이즈 블록을 해제해주면 당장 할 일은? 앞 뒤를 돌아다니면서 "똑똑똑!! 당신은 가용블록인가요?!?!?!"를 묻고 다녀야 한다. 60사이즈에게 묻는건 간단하다. header가 있으니. 헤더로 방문하여 음! 이 블록은 할당이 안되었네? 사이즈가 60이야? 그럼 합쳐서 108하면 개꿀이군! 이라고 생각한다.
그럼 앞에 블록을 방문하려면...? 헤더를 찾으려 40칸을 앞으로 가야한다. 컴퓨터는 40칸인줄 모르고 있을테니
"똑똑똑 너 헤더야? 아니네." *39
"아 드디어 헤더다 반가워. 넌 가용상태구나... 우리 합치자..." 이렇게 된다.
만일 footer가 있다면? 한칸만 앞으로 갔을 때 사이즈와 할당여부 음! 얜 가용상태 이고 40사이즈라고? 그럼 앞(prev) 나 뒤(next) 전부합쳐서 우린 148사이즈~ 이렇게 되는거다.
그럼 이제 블럭을 넣으려고 한다. 근데 여기서 의문이 하나 들어야 한다.
32사이즈 요청이 들어왔을 때, 가용상태인 블럭의 사이즈들이 16, 80, 800인 상태라면 어떤 블록을 할당해주는게 맞을까?
이제 여기서 나오는 방법이 first-fit, next-fit, best-fit이다.
이름만 봐도 이해가 되지 않는가? next-fit은 잘 감이 안오긴 한다.
first-fit은 앞에서부터 찾아나갈 때 들어갈수만 있다면 냅다 들어가는 것이다.
best-fit은 끝까지 다 돌아보고 자신이 들어가기 적합한 곳에 들어가는 것이다.
next-fit은 이전에 어디에 들어갔는지를 기억해놓고, 그 다음부터 돌면서 들어갈 수 있는 곳을 찾으면 바로 들어가는 것이다.
best-fit은 속도가 너무 느릴 것이라 판단하여 구현을 딱히하진 않았다. 끝까지 반복문을 돌면서 size차이가 제일 적게 나는 블록으로 업데이트해고 끝까지 다 돌아봤을 때 size가 적게 차이나는, 저장해둔 블록에 들어가면 될 것이다.
이제 Implicit 다 끝났다. 이 내용을 코드에 적기만 하면 완성!
속도가 너무 빨라서 이해가 덜 되었어도 코드로 넘어가자. 주석이 상세하게 달려있다.
정말 감사합니다 ㅠㅜ