크래프톤 정글(C언어 WEEK 5 ~ 8)
묵시적 리스트 구현(Next Fit)[56점]
devkty
2025. 4. 30. 03:33
728x90
묵시적 리스트 (Next Fit)[56점]
기본적으로 전체틀은 바뀌지 않습니다.
First Fit에서 Next Fit으로 바꾸려면, 기존의 코드에서 find_fit 함수만 바꾸면 됩니다. 그러나 저는 얼마 안가 해당 함수만 바꾸면 되는 걸 알게 되었습니다.
합병을 담당하는 coalesce에 맨 밑 리턴 값에 last_bp = bp; 을 추가하여야 합니다. 또한 last_bp 변수를 어떤 함수에서든 쓸수 있게 전역변수로 선언해줘야 합니다.(초깃값 NULL)
전역 변수 추가 및 coalesce 수정
.
.
.
// 다음 블록의 포인터
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
// 이전 블록의 포인터
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
/* 추가할 부분 */ static void *last_bp = NULL; // next fit을 위한 선언
// 상수 시간에 인접 가용 블록 병합하기
static void *coalesce(void *bp) {
.
.
.
else { // Case 3: 이전 블록은 가용(free), 다음 블록은 할당된 경우
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))); // 이전 블록 + 현재 블록 + 다음 블록을 모두 합쳐 크기를 늘림
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록의 헤더를 새 size로 업데이트 (free 상태)
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); // 다음 블록의 푸터를 새 size로 업데이트 (free 상태)
bp = PREV_BLKP(bp); // bp를 병합된 블록(이전 블록) 쪽으로 이동
}
/* 추가할 부분 */ last_bp = bp; // next fit을 위한 bp 포인터 값 반환
return bp; // 병합이 끝난 블록의 포인터를 반환
}find_fit 수정
static void *find_fit(size_t asize)
{
if (last_bp == NULL) // NULL이면
last_bp = mem_heap_lo() + 2 * WSIZE; // 원래대로 힙 시작 주소에서 2워드(8바이트)를 건너뛴 곳(첫 블록)부터 탐색 시작
void *bp = last_bp; // 가장 최근의 값을
void *heap_end = mem_heap_hi(); // memlib에 있는 최근 주소 바이트를 가져옴
// 1단계: last_bp부터 힙 끝까지
while ((char *)bp <= (char *)heap_end) {
// 현재 포인터(bp)가 힙 끝 주소(heap_end)를 넘지 않았는지 확인
if (!GET_ALLOC(HDRP(bp)) && asize <= GET_SIZE(HDRP(bp))) {
// 현재 블록이 가용 상태(free)이며 현재 블록의 크기가 요청 크기(asize) 이상이면
last_bp = bp; // 마지막 탐색 성공 위치를 저장하여 다음 탐색의 시작 지점으로 삼음
return bp; // 조건을 만족하는 블록을 찾았으므로 해당 포인터 반환
}
bp = NEXT_BLKP(bp); // 조건을 만족하지 않으면 다음 블록으로 이동
}
// 2단계: 힙 시작부터 last_bp까지
// 힙의 실제 첫 블록은 padding + prologue(2워드)를 지난 곳이므로 mem_heap_lo() + 8에서 시작
for (bp = mem_heap_lo() + 2 * WSIZE; (char *)bp < (char *)last_bp; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && asize <= GET_SIZE(HDRP(bp))) { // 위와 동일한 조건으로 블록 검사
last_bp = bp; // 다음 탐색을 위한 위치 갱신
return bp; // 조건을 만족하는 블록 반환
}
}
return NULL; // 못 찾았을 경우
}위의 총 3가지 부분을 수정하면 정상적으로 Next Fit을 구현할 수 있습니다.
find_fit 함수는 기존의 First Fit 코드와 다르게, 크게 두가지 케이스로 나눌 수 있습니다.
- 최근 수정된 포인터 last_bp부터 힙 끝까지 확인해서 적절한 블록을 추가하는 케이스
- 힙 시작부터 last_bp까지 확인해서 적절한 블록을 추가하는 케이스
→ 위의 두 사항을 참고하여 수정하면 좋을 것 같습니다. 추가적으로 last_bp가 없다면 기존 코드대로 진행하는 if문도 추가하면 정상적으로 구현 가능합니다.
리눅스 구축환경에 따라 다르겠지만, 저의 시놀로지 도커 Ubuntu 18.04에서는 56점이 나왔습니다. 사양과 버전에 따라 더 높게 나오는 것 같습니다.
Next Fit이 왜 우수한 점수를 보여주는가?
bp = mem_heap_lo() + 2 * WSIZE; // 항상 힙 처음부터 탐색 시작
while (GET_SIZE(HDRP(bp)) > 0) {
if (!GET_ALLOC(HDRP(bp)) && asize <= GET_SIZE(HDRP(bp)))
return bp;
bp = NEXT_BLKP(bp);
}위의 코드는 First Fit의 일부 코드를 가져온 것입니다. 보면 알 수 있듯이 항상 힙 처음부터 탐색을 시작하는 것을 알 수 있습니다. 그러면 두가지 문제가 발생합니다.
- 자주 호출되면 앞부분 블록에 집중적으로 할당됨 → 힙 앞쪽 단편화 심화
- 탐색 시간이 길어질 수 있음
// 탐색은 마지막에 할당된 위치 이후부터 시작
while ((char *)bp <= (char *)heap_end) {
...
}
for (bp = mem_heap_lo() + 2 * WSIZE; (char *)bp < (char *)last_bp; bp = NEXT_BLKP(bp)) {
...
}그러나 Next Fit은 다음과 같은 부분으로 최근 할당된 위치 기준으로 탐색하기 때문에, First Fit 보다 더 나은 성능을 보여줍니다.
Next Fit은 다음과 같은 이점이 있습니다.
- 최근에 할당된 위치 기준으로 가용 블록 분포를 넓게 활용함
- 힙 전체를 균등하게 사용하려는 특성이 있음
- 탐색 시간 단축 가능 → 특히 할당 요청이 빈번할 때 성능이 좋아짐
트러블 슈팅 시 다음 벨로그를 참고했습니다.
참고용 Next Fit 전체 코드
/*
* mm-naive.c - 가장 빠르지만 메모리 효율이 가장 낮은 malloc 패키지입니다.
* 이 단순 접근 방식에서는 brk 포인터를 단순히 증가시켜 블록을 할당합니다.
* 블록은 순수한 페이로드입니다. 헤더나 푸터가 없습니다. 블록은 병합되거나 재사용되지 않습니다.
* realloc은 mm_malloc과 mm_free를 사용하여 직접 구현됩니다.
*
* 참고: 이 헤더 주석을 해결책에 대한 간략한 설명을 제공하는 자체 헤더 주석으로 바꾸세요.
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
/*********************************************************
* NOTE TO STUDENTS: Before you do anything else, please
* provide your team information in the following struct.
********************************************************/
team_t team = {
/* Team name */
"5team",
/* First member's full name */
"Kim Taeyong",
/* First member's email address */
"bovik@cs.cmu.edu",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""
};
// 기본 상수
#define WSIZE 4 // 글자, 헤더, 풋터 크기 4byte
#define DSIZE 8 // 더블(부동소수점) 글자 크기 8byte
#define CHUNKSIZE (1<<12) // 힙 확장을 위한 기본 크기(초기의 빈 블록의 크기)
// 매크로
#define MAX(x, y) ((x) > (y) ? (x) : (y))
// size와 할당 비트를 결합, header와 footer에 저장할 값
#define PACK(size, alloc) ((size) | (alloc))
// p가 참조하는 워드 반환(포인터라서 직접 역참조 불가능 -> 타입 캐스팅)
#define GET(p) (*(unsigned int *)(p))
// p에 val 저장
#define PUT(p, val) (*(unsigned int *)(p) = (val))
// 사이즈 (~0x7: ...11111000, '&' 연산으로 뒤에 세자리 없어짐)
#define GET_SIZE(p) (GET(p) & ~0x7)
// 할당 상태
#define GET_ALLOC(p) (GET(p) & 0x1)
// Header 포인터
#define HDRP(bp) ((char *)(bp) - WSIZE)
// Footer 포인터 (Header의 정보를 참조해서 가져오기 때문에, Header의 정보를 변경했다면 변경된 위치의 Footer가 반환됨에 유의)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
// 다음 블록의 포인터
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
// 이전 블록의 포인터
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
static void *last_bp = NULL; // next fit을 위한 선언
// 상수 시간에 인접 가용 블록 병합하기
static void *coalesce(void *bp) {
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 이전 블록 할당 상태 가져옴(0 = free, 1 = allocated)
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 다음 블록 할당 상태 가져옴(0 = free, 1 = allocated)
size_t size = GET_SIZE(HDRP(bp)); // 현재 블록 사이즈
/// case 1. 이전 블록과 다음 블록 모두 할당된 경우 (병합 불가)
if (prev_alloc && next_alloc) {
return bp;
}
// Case 2: 이전 블록은 할당, 다음 블록은 가용(free)한 경우
else if (prev_alloc && !next_alloc) {
size += GET_SIZE(HDRP(NEXT_BLKP(bp))); // 현재 블록과 다음 블록을 합쳐 크기를 늘림
PUT(HDRP(bp), PACK(size, 0)); // 현재 블록의 헤더를 새 size로 업데이트 (free 상태)
PUT(FTRP(bp), PACK(size, 0)); // 합쳐진 블록의 푸터를 새 size로 업데이트
}
/// case 3: 이전 블록은 가용(free), 다음 블록은 할당된 경우
else if (!prev_alloc && next_alloc) {
size += GET_SIZE(HDRP(PREV_BLKP(bp))); // 이전 블록과 현재 블록을 합쳐 크기를 늘린다
PUT(FTRP(bp), PACK(size, 0)); // 이전 블록의 헤더를 새 size로 업데이트(free)
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 현재 블록의 푸터를 새 size로 업데이트
bp = PREV_BLKP(bp); // bp를 병합된 블록(이전 블록) 쪽으로 이동
}
else { // Case 3: 이전 블록은 가용(free), 다음 블록은 할당된 경우
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))); // 이전 블록 + 현재 블록 + 다음 블록을 모두 합쳐 크기를 늘림
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록의 헤더를 새 size로 업데이트 (free 상태)
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); // 다음 블록의 푸터를 새 size로 업데이트 (free 상태)
bp = PREV_BLKP(bp); // bp를 병합된 블록(이전 블록) 쪽으로 이동
}
last_bp = bp; // next fit을 위한 bp 포인터 값 반환
return bp; // 병합이 끝난 블록의 포인터를 반환
}
// 힙 확장: 새 가용 블록으로 힙을 확장한다.
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
// 더블 워드 정렬 유지
// size: 확장할 크기
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; // 더블워드의 가장 가까운 배수로 반올림(홀수면 1 더해서 곱한다)
if ((long)(bp = mem_sbrk(size)) == -1) // 힙 확장
return NULL;
PUT(HDRP(bp), PACK(size, 0)); // 새 빈 블록 헤더 초기화
PUT(FTRP(bp), PACK(size, 0)); // 새 빈 블록 풋터 초기화
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 에필로그 블록 헤더 초기화
return coalesce(bp); // 병합 후 coalesce 함수에서 리턴된 블록 포인터 반환
}
/////////////////
// 검색 후 가용블록 반환하기 (First fit)
// 가용 리스트를 순차적으로 검색해서, 요청 크기 이상의 가용 블록을 찾아 반환한다
static void *find_fit(size_t asize)
{
if (last_bp == NULL) // NULL이면
last_bp = mem_heap_lo() + 2 * WSIZE; // 원래대로 힙 시작 주소에서 2워드(8바이트)를 건너뛴 곳(첫 블록)부터 탐색 시작
void *bp = last_bp; // 가장 최근의 값을
void *heap_end = mem_heap_hi(); // memlib에 있는 최근 주소 바이트를 가져옴
// 1단계: last_bp부터 힙 끝까지
while ((char *)bp <= (char *)heap_end) { // 현재 포인터(bp)가 힙 끝 주소(heap_end)를 넘지 않았는지 확인
if (!GET_ALLOC(HDRP(bp)) && asize <= GET_SIZE(HDRP(bp))) { // 현재 블록이 가용 상태(free)이며 현재 블록의 크기가 요청 크기(asize) 이상이면
last_bp = bp; // 마지막 탐색 성공 위치를 저장하여 다음 탐색의 시작 지점으로 삼음
return bp; // 조건을 만족하는 블록을 찾았으므로 해당 포인터 반환
}
bp = NEXT_BLKP(bp); // 조건을 만족하지 않으면 다음 블록으로 이동
}
// 2단계: 힙 시작부터 last_bp까지
// 힙의 실제 첫 블록은 padding + prologue(2워드)를 지난 곳이므로 mem_heap_lo() + 8에서 시작
for (bp = mem_heap_lo() + 2 * WSIZE; (char *)bp < (char *)last_bp; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && asize <= GET_SIZE(HDRP(bp))) { // 위와 동일한 조건으로 블록 검사
last_bp = bp; // 다음 탐색을 위한 위치 갱신
return bp; // 조건을 만족하는 블록 반환
}
}
return NULL; // 못 찾았을 경우
}
// 효과적으로 분할하기
// 블록을 할당할 때, 남는 공간이 충분하면 블록을 분할(split) 하고, 그렇지 않으면 그냥 전체 블록을 할당한다
static void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp)); // 현재 블록의 전체 크기 가져오기
if ((csize - asize) >= (2 * DSIZE)) // Case 1: 블록을 분할할 수 있는 경우 (남은 크기가 최소 블록 크기 이상일 때)
{
// 현재 블록에 asize 크기만큼 할당 표시
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
// 남은 부분을 새로운 가용 블록으로 설정
PUT(HDRP(NEXT_BLKP(bp)), PACK((csize - asize), 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK((csize - asize), 0));
}
else // Case 2: 블록을 분할하지 않고 통째로 사용하는 경우
{
// 현재 블록 전체를 할당 표시
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
//////////////
// mm_init - initialize the malloc package.
// 힙 생성하기: 패딩+프롤로그 헤더+프롤로그 풋터+에필로그 풋터를 담기위해 4워드 크기합을 구성함
// 생성 후 CHUNKSIZE만큼 추가 메모리를 요청해 힙의 크기를 확장
int mm_init(void)
{
char *heap_listp; // 초기 힙을 생성한다
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1) // 4워드 크기의 힙 생성, heap_listp에 힙의 시작 주소값 할당
return -1;
PUT(heap_listp, 0); // 정렬 패딩
PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); // 프롤로그 헤더
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); // 프롤로그 풋터
PUT(heap_listp + (3*WSIZE), PACK(0, 1)); // 에필로그 헤더(프로그램이 할당한 마지막 블록의 뒤에 위치하며, 블록이 할당되지 않은 상태를 나타냄)
heap_listp += (2*WSIZE);
if (extend_heap(CHUNKSIZE/WSIZE) == NULL) // free블록으로 빈 힙을 CHUNKSIZE bytes로 확장
return -1;
return 0;
}
// mm_malloc - Allocate a block by incrementing the brk pointer.
// Always allocate a block whose size is a multiple of the alignment.
// 가용 블록 할당하기
// brk 포인터를 증가시켜 블록을 할당합니다. 항상 정렬 크기의 배수인 블록을 할당합니다.
void *mm_malloc(size_t size)
{
size_t asize; // 요청된 크기를 조정한 블록 크기 (payload + overhead 포함)
size_t extendsize; // heap을 확장할 사이즈
char *bp; // 새로 할당할 블록 포인터
// 잘못된 요청 처리: size가 0이면 NULL 반환
if(size == 0)
return NULL;
// 요청 크기 조정 (payload + header/footer 포함, alignment 맞추기)
if (size <= DSIZE) // 8바이트 이하 시
asize = 2*DSIZE; // 최소 블록 크기 16바이트 할당 (헤더 4 + 푸터 4 + 저장공간 8)
else
asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE); // size에 overhead 추가하고, DSIZE 단위로 8의 배수로 올림 (align)
// Step 1: 가용 리스트에서 알맞은 블록 찾기
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize); // 블록을 할당하고
return bp; // 포인터 반환
}
// Step 2: 가용 블록이 없으면 힙을 확장
extendsize = MAX(asize, CHUNKSIZE); // 최소 CHUNKSIZE만큼은 확장
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL; // 확장 실패시 NULL 반환
place(bp, asize); // 새로 확장한 블록에 메모리 배치
return bp; // 새 블록 포인터 반환
}
// mm_free - Freeing a block does nothing.
// 블록 반환하기
void mm_free(void *bp)
{
size_t size = GET_SIZE(HDRP(bp)); // 현재 블록(bp)의 헤더를 읽어서 블록 크기(size)를 가져옴
PUT(HDRP(bp), PACK(size, 0)); // 블록의 헤더(Header) 정보를 업데이트: size 그대로, 할당 비트(allocation bit)는 0 (free 상태)
PUT(FTRP(bp), PACK(size, 0)); // 블록의 푸터(Footer) 정보도 업데이트: size 그대로, 할당 비트는 0 (free 상태)
coalesce(bp); // 인접한 가용 블록들과 병합(Coalesce) 시도
}
// mm_realloc - Implemented simply in terms of mm_malloc and mm_free
// 재할당 블록 재할당하기
// 기존 블록 내용을 새 블록에 복사한 후 기존 블록을 해제, 새 포인터 반환
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr; // 기존 블록 포인터
void *newptr; // 새로 할당받을 블록 포인터
size_t copySize; // 복사할 데이터 크기
// Step 1: 새 크기만큼 메모리를 할당
newptr = mm_malloc(size);
if (newptr == NULL) // 메모리 할당 실패 시 NULL 반환
return NULL;
// Step 2: 기존 블록의 크기 읽기
copySize = GET_SIZE(HDRP(oldptr));
// Step 3: 복사할 크기를 요청 크기로 조정 (원래 블록이 더 크면 size까지만 복사)
if (size < copySize)
copySize = size;
// Step 4: 데이터 복사
memcpy(newptr, oldptr, copySize);
// Step 5: 기존 블록 반환 (free)
mm_free(oldptr);
return newptr; // 새 블록 포인터 반환
}728x90