어제는 묵시적 가용 리스트에 대해 공부하며 Malloc을 구현해봤습니다
Malloc을 구현하면서 First-Fit에 대해서도 공부를 했는데 다른방법도 있어서 오늘 공부해봤습니다
Next-Fit
Next fit은 메모리 할당 알고리즘 중 하나입니다. 이 알고리즘은 프로세스들을 메모리 내에서 할당할 때 사용됩니다.
Next fit 알고리즘은 프로세스를 순서대로 메모리에 할당하는 방식입니다. 프로세스가 메모리에 할당될 때, 현재 위치부터 순서대로 검사를 시작하여 비어있는 메모리 공간을 찾습니다. 맨 처음 할당할 때는 메모리의 시작 위치부터 검사를 시작하며, 이후에는 이전에 할당된 프로세스의 마지막 위치부터 검사를 시작합니다.
이 알고리즘의 장점은 구현이 간단하고 연속된 메모리 공간을 사용하는 프로세스들에 대해서는 효율적입니다. 또한, 프로세스들이 메모리에 할당되는 순서를 유지하므로, 프로세스들이 실행되는 순서와 메모리에 할당되는 순서가 일치합니다.
하지만 Next fit 알고리즘의 단점은 메모리 공간의 낭비가 발생할 수 있다는 것입니다. 할당된 프로세스가 메모리 공간의 일부만 차지하고 나머지 부분이 비어있는 경우, 그 빈 공간은 다음 프로세스가 할당될 때까지 사용되지 않습니다. 이로 인해 메모리의 활용도가 감소할 수 있습니다
Malloc-Lab
malloc lab은 동적 메모리 할당을 구현하는 과제로, 여러 가지 할당 알고리즘 중에서 first fit과 next fit을 비교하고 구현해야 할 수도 있습니다.
First fit과 Next fit은 모두 동적 메모리 할당에서 사용되는 알고리즘입니다. 두 알고리즘의 주요 차이점은 메모리 공간을 탐색하는 방법입니다.
First fit 알고리즘은 프로세스를 메모리에 할당할 때, 메모리의 시작 지점부터 순서대로 검사하여 첫 번째로 맞는 크기의 빈 공간을 찾습니다. 즉, 가장 처음으로 발견되는 크거나 같은 크기의 빈 공간에 프로세스를 할당합니다.
반면에 Next fit 알고리즘은 프로세스를 메모리에 할당할 때, 이전에 할당된 프로세스의 마지막 위치부터 검사를 시작합니다. 즉, 이전에 할당된 위치에서부터 메모리를 검사하고, 처음으로 맞는 크기의 빈 공간을 찾아 프로세스를 할당합니다. 다음 프로세스의 할당은 이전에 할당된 위치에서부터 다시 검사를 시작합니다.
따라서, First fit은 메모리의 시작 위치에서부터 검사를 시작하는 반면, Next fit은 이전에 할당된 위치에서부터 검사를 시작합니다. 이로 인해 Next fit은 First fit보다 더 효율적으로 메모리 공간을 활용할 수 있습니다. 그러나 Next fit의 경우 메모리의 끝 부분에 빈 공간이 남아있고, 그 공간보다 작은 프로세스를 할당할 때는 메모리의 시작 부분까지 돌아와야 하는 단점이 있습니다.
따라서, First fit은 구현이 간단하고 많은 프로세스들이 작은 빈 공간을 차지할 경우 유리하며, Next fit은 메모리 활용도를 개선하고자 할 때 유용한 알고리즘입니다
/*
* mm-naive.c - The fastest, least memory-efficient malloc package.
*
* In this naive approach, a block is allocated by simply incrementing
* the brk pointer. A block is pure payload. There are no headers or
* footers. Blocks are never coalesced or reused. Realloc is
* implemented directly using mm_malloc and mm_free.
*
* NOTE TO STUDENTS: Replace this header comment with your own header
* comment that gives a high level description of your solution.
*/
#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 */
"ateam",
/* First member's full name */
"Harry Bovik",
/* 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) */
""};
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8 // 할당되는 메모리 블록의 크기를 8의 배수로 정렬하기 위한 상수
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7) // size를 8의 배수로 정렬하는 매크로 함수
#define SIZE_T_SIZE (ALIGN(sizeof(size_t))) // size_t 타입 변수의 크기를 8의 배수로 정렬한 크기입니다
#define WSIZE 4 // 워드와 더블워드의 크기를 각각 4바이트와 8바이트로 정의한 매크로 상수
#define DSIZE 8
#define CHUNKSIZE (1 << 12) // 힙 확장을 위한 기본 크기 (= 초기 빈 블록의 크기)
#define MAX(x, y) ((x) > (y) ? (x) : (y)) //x와 y 중 더 큰 값을 반환하는 매크로 함수
#define PACK(size, alloc) ((size) | (alloc)) // size와 할당 비트를 결합, header와 footer에 저장할 값
#define GET(p) (*(unsigned int *)(p)) // 주소 p에 위치한 값을 읽어옵니다 (포인터라서 직접 역참조 불가능 -> 타입 캐스팅)
#define PUT(p, val) (*(unsigned int *)(p) = (val)) // 주소 p에 값을 저장합니다
#define GET_SIZE(p) (GET(p) & ~0x7) // 주소 p에 위치한 메모리 블록의 크기를 반환 사이즈 (~0x7: ...11111000, '&' 연산으로 뒤에 세자리 없어짐)
#define GET_ALLOC(p) (GET(p) & 0x1) // 주소 p에 위치한 메모리 블록의 할당 여부를 반환
#define HDRP(bp) ((char *)(bp) - WSIZE) // Header 포인터
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // Footer 포인터
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) // 다음 블록의 포인터
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // 이전 블록의 포인터
static char *last_bp;
static char *heap_listp; // 초기 힙 메모리 공간의 포인터를 저장하는 전역 변수
static void *extend_heap(size_t words); // 개수의 워드 크기만큼 힙 메모리 공간을 늘리고, 새로운 블록을 만들어 반환
static void *coalesce(void *bp); // 현재 블록 bp와 인접한 블록이 비어있으면 하나의 큰 블록으로 병합
static void *find_fit(size_t asize); // 요청한 크기 asize에 맞는 비어있는 블록을 찾아 반환
static void place(void *bp, size_t asize); // bp 블록에 asize 크기만큼의 메모리를 할당
int mm_init(void)
{
// 초기화를 위해 4 워드 크기의 힙 공간을 할당합니다.
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *) -1)
return -1;
// 블록을 할당하기 위해 Prologue Header와 Footer를 설정합니다.
PUT(heap_listp, 0);
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
// Epilogue Header를 설정합니다.
PUT(heap_listp + (3 * WSIZE), PACK(0, 1));
// 힙 시작점 주소를 Prologue Header 이후로 변경합니다.
heap_listp += (2 * WSIZE);
// 초기 힙 확장을 시도합니다.
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
last_bp = heap_listp;
return 0;
}
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
// 요청한 워드 수에 기반하여 메모리 크기를 계산합니다.
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
// mem_sbrk 함수를 사용하여 힙 확장을 시도합니다.
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
// 새 블록의 헤더와 푸터를 설정합니다.
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
// Epilogue Header를 설정합니다.
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
// 인접한 블록이 free 블록이면 coalesce 합니다.
return coalesce(bp);
}
void *mm_malloc(size_t size)
{
size_t asize;
size_t extendsize;
char *bp;
// 할당할 크기가 0인 경우 NULL을 반환합니다.
if (size == 0)
return NULL;
// 요청한 크기에 기반하여 할당할 블록의 크기를 계산합니다.
if (size <= DSIZE)
asize = 2 * DSIZE;
else
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
// 할당 가능한 free 블록을 찾습니다.
if ((bp = find_fit(asize)) != NULL) {
// 찾은 블록에 할당을 진행합니다.
place(bp, asize);
return bp;
}
// 할당 가능한 free 블록을 찾지 못한 경우 힙을 확장합니다.
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
// 확장한 힙에 새로운 블록을 할당합니다.
place(bp, asize);
return bp;
}
void mm_free(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
// 블록의 헤더와 푸터에 할당 상태를 변경하여 free로 설정합니다.
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
// 인접한 free 블록이 있는 경우 병합(coalesce)을 수행합니다.
coalesce(bp);
}
static void *coalesce(void *bp)
{
// 이전 블록과 다음 블록의 할당 여부와 크기를 가져옵니다.
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc) {
// 이전 블록과 다음 블록이 모두 할당되어 있으면 병합하지 않고 현재 블록을 반환합니다.
return bp;
}
else if (prev_alloc && !next_alloc) {
// 이전 블록은 할당되어 있고 다음 블록은 할당되어 있지 않으면 다음 블록을 현재 블록에 통합합니다.
// 현재 블록의 크기를 증가시키고, 헤더와 푸터를 업데이트합니다.
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
}
else if (!prev_alloc && next_alloc) {
// 이전 블록은 할당되어 있지 않고 다음 블록은 할당되어 있으면 이전 블록을 현재 블록에 통합합니다.
// 이전 블록의 크기를 증가시키고, 헤더와 푸터를 업데이트합니다.
// 이전 블록의 주소를 현재 블록으로 변경합니다.
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
else {
// 이전 블록과 다음 블록이 모두 할당되어 있지 않으면 이전 블록과 다음 블록을 현재 블록에 통합합니다.
// 이전 블록과 다음 블록의 크기를 추가하여 현재 블록의 크기를 증가시키고, 헤더와 푸터를 업데이트합니다.
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
if ((last_bp > (char *)bp) && (last_bp < NEXT_BLKP(bp)))\
last_bp = bp;
return bp;
}
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
copySize = GET_SIZE(HDRP(oldptr));
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
static void *find_fit(size_t asize)
{
void *bp = last_bp;
for (; GET_SIZE(HDRP(last_bp)) > 0; last_bp = NEXT_BLKP(last_bp)) {
if (!GET_ALLOC(HDRP(last_bp)) && (asize <= GET_SIZE(HDRP(last_bp)))) {
return last_bp;
}
}
for (last_bp = heap_listp; last_bp < bp; last_bp = NEXT_BLKP(last_bp)) {
if (!GET_ALLOC(HDRP(last_bp)) && (asize <= GET_SIZE(HDRP(last_bp)))) {
return last_bp;
}
}
return NULL;
}
static void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp));
if ((csize - asize) >= (2*DSIZE)) {
// 남은 공간이 분할 가능한 최소 블록 크기(DSIZE)보다 크면 블록을 분할합니다.
// 현재 블록을 할당된 상태로 표시하고 크기를 asize로 설정합니다.
// 남은 공간을 가진 새로운 가용 블록을 생성합니다.
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize-asize, 0));
PUT(FTRP(bp), PACK(csize-asize, 0));
}
else {
// 남은 공간이 분할 가능한 최소 블록 크기(DSIZE)보다 작으면 전체 블록을 할당합니다.
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
last_bp = bp;
}Next fit 알고리즘을 공부하면서 어려웠던 점은, 처음에는 프로세스를 할당할 때 이전에 할당된 위치에서부터 검사를 시작한다는 개념이 이해하기 어려웠습니다. 일반적으로 처음부터 시작하는 First fit과는 다른 방식이었기 때문에 혼란스러웠습니다.
또한, Next fit 알고리즘은 메모리의 끝 부분에 빈 공간이 남아있고, 그 공간보다 작은 프로세스를 할당할 때는 메모리의 시작 부분까지 돌아와야 하는 점이 조금 불편하다고 느껴졌습니다. 이전에 할당된 위치에서부터 검사를 시작하다 보니, 작은 공간이 끝에 위치할 경우에는 전체 메모리를 다시 검사해야 했기 때문에 효율성이 떨어질 수 있다는 생각이 들었습니다.
하지만 Next fit 알고리즘의 장점은 메모리 공간의 활용도를 개선할 수 있다는 점이었습니다. 연속된 메모리 공간을 사용하는 프로세스들에 대해서는 First fit보다 효율적으로 할당할 수 있습니다. 이러한 장점을 알게 되면서 Next fit 알고리즘의 가치를 느낄 수 있었습니다.
공부를 하면서 어려움을 겪었지만, 이러한 어려움들은 결국 이해하고 익숙해지면서 극복할 수 있었습니다. 다양한 알고리즘을 공부하면서 개별 알고리즘의 특징과 장단점을 이해하는 것이 중요하다는 것을 느꼈습니다. 이러한 이해를 바탕으로 문제에 적합한 알고리즘을 선택하고 구현할 수 있게 되었습니다
