이제 가용 리스트를 어떤 식으로 넣어줄지에 대한 Find_fit함수를 구현하려고 한다. 그러면 각각의 fit들이 어떤 것이 있는지 장점은 어떤 것이 있는지 알아보자.
First Fit
말 그대로 제일 처음 발견한 가용 메모리에 넣어버리는 것이다.
이런식으로 항상 heap_listp 부터 훑어서, 사이즈에 맞는 가용 메모리를 발견하면 바로 할당한다 !
일단 이론은 쉬우니까 구현부터 들어봤다. 그냥 처음부터 항상 선형 탐색을 하면 되것거니 감이 왔다.
static void *find_fit(size_t asize){
// *first_fit
void *bp;
for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){
return bp;
}
}
return NULL;
}그래서 선형 탐색으로 first_fit을 구현했다. 여태까지 알고리즘만 계속 풀다보니까 선형탐색은 어떻게 해야할지 바로 감이 왔다. 하하하 !
그럼 이제 카네기 멜론 교수님의 채점 시간이다..
그럼 점수를 보면 !
음... 59점...초등학교 때 사회 점수 59점을 맞아서 엄마한테 혼났던 기억이 팍 스쳤다..
항상 하란대로 하는거는 점수가 좋지 못한거 같다...
그래서 카네기 멜론 교수님이 좋다고 얘기하신 best_fit으로도 구현해 보려고한다.
Best Fit
// * best_fit
void *bp;
void *best_bp = NULL;
size_t best_size = (size_t)(-1); // unsignded int 특성상 음수 값이 해당 자료형의 최댓값
size_t size;
for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0 ; bp = NEXT_BLKP(bp)){
size = GET_SIZE(HDRP(bp));
if (!GET_ALLOC(HDRP(bp)) && (asize <= size)){
if(size < best_size){
best_size = size;
best_bp = bp;
}
}
}
return best_bp;best_fit 또한 구현을 완료했다... first_fit과 구조가 비슷하지만, 계속해서 맞는 사이즈를 탐색하도록 했다. 한번 좋은 거 찾아놓고 계속해서 늘려가는 것이다. 약간 그리디 알고리즘과 비슷했다.
구현 보다 점수가 궁금해서 점수를 봤다. 한 20점 ? 점도 오르지 않을까 생각했다
그만 알아보자...
Next Fit
카네기 멜론 교수님이 별로 좋은 방법이 아니라고, 뭐라고 했던 방법이다...
일단 구현은 다 해보면서, 공부하는게 목표라서 구현을 해봤다.
// * next_fit
void *bp = last_bp;
// last_bp부터 힙 끝까지 탐색
for(bp = NEXT_BLKP(bp); GET_SIZE(HDRP(bp)) != 0; bp = NEXT_BLKP(bp)){
if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){
last_bp = bp; // 찾았으면 last_bp 업데이트
return bp;
}
}
bp = heap_listp;
// 못 찾으면 heap_listp부터 last_bp까지 다시 탐색
while (bp < last_bp) {
bp = NEXT_BLKP(bp);
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
last_bp = bp;
return bp;
}
}
return NULL;
해당 방식으로 정리를 하고 구현을 하였다. 계속해서 가용된 block을 할당해줘서 오류가 있었는데, coalesce함수에서 합쳐지는 걸 생각하지 못했다. 합쳐진 후에 last_bp를 이동시켜도 next_fit이라는 구현 조건에 맞다고 생각하여, 이걸 기반으로 구현하였다.
구현은 어찌저찌 했는데, 결과는..?
아니 카네기 멜론 대학 교수님,,,?
뭔가... 제일 최악이라 거들떠도 보지 않았던게 최고의 퍼포먼스를 내었다...
브루트 포스 알고리즘을 보는 듯한 느낌이였다...
그런데 외부 단편화가 심해져서 그런지, 점수가 좋앗지만, util 점수가 많이 떨어져있었다. 점수가 높다고 다 좋은 코드는 아니니까. 다른 방법을 모색해 볼 예정이다...
하여튼 끝
