[Malloc] Implicit Free List방식-구현

Malloc - lab

---

📌heap

• 동적 메모리 할당기는 힙이라는 가상 메모리를 관리한다.
• 이러한 힙 영역에는 할당된 블록과 가용블록이 있다.
• 할당기의 종류
  1. 명시적 할당기(explicit allocator) : 메모리 할당과 해제를 직접적으로 관리하고 조작하는 할당기
     • 단점 : 메모리 누수 , 무효 표인터(이전에 참조하던 메모리 위치를 가리키지만 이제는 무효화된 포인터를 나타냄)
  2. 암시적 할당기(implicit allocator) : 프로그래밍 언어 또는 런타임 라이브러리에 내장되어 있어서 개발자가 명시적으로 메모리 할당 및 해제를 관리하지 않아도 되는 메모리 할당 방식
     • 단점 : 런타임 오버헤드 문제, 성능 문제

 

Malloc pacakge

---

📌malloc

void *malloc(size_t size)

• 할당 성공시, 8byte로 정렬된 메모리의 주소를 가르키는 포인터를 반환한다. 실패시 null(0) 반환.

 

📌free

void free(void *p)

• 할당되지 않는 블록을 가리키는 포인터를 반환한다.
• p는 먼저 malloc이나 calloc에 의해 할당 되어야 함.
  
  • calloc : 블록을 0으로 초기화
  • realloc : 이미 할당된 블록 사이즈를 줄이거나 늘림
  • sbrak : 힙 사이즈를 줄이거나 늘림

 

✏️malloc 사용예시

#include <stdio.h>
#include <stdlib.h>

int main() {
    int *arr;
    int n = 5; // 정수 배열의 크기

    // malloc을 사용하여 n개의 int 크기만큼 메모리 할당
    arr = (int *)malloc(n * sizeof(int));

    if (arr == NULL) {
        fprintf(stderr, "메모리 할당 오류\n");
        return 1;
    }

    // 할당된 메모리를 초기화하고 출력
    for (int i = 0; i < n; i++) {
        arr[i] = i * 10;
        printf("arr[%d] = %d\n", i, arr[i]);
    }

    // 메모리를 해제
    free(arr);
    return 0;
}

 

allocator

---

 

📌할당기 구현 제약

• 이미 할당된 블록의 사이즈를 수정할 수 없다.
• malloc 요청에 바로 응답한다. 지연시키거나 재정렬이 불가능
  • -> 요청 자체를 정렬 하거나 순서를 바꾸는 것이 효율적이다. 하지만 malloc 요청이 들어오면 지연이 아니라 곧바로 힙의 메모리를 할당한 후 포인터를 반환할 수 있어야한다.
• free인 블록에만 할당이 가능하다.
• 할당된 블록은 옮길 수 없다.
• 메모리 정렬이 필요하다.
  • -> 32비트라면 4바이트씩, 64비트라면 8바이트씩
• free 블록만 조작하거나 변경할 수 있다.

 

📌할당기 구현 이슈

• 어떻게 가용(free)블록을 지숙적으로 추적할것인가?
• 어느정도의 메모리를 free시켜야할지 , 하나의 포인터로 알 수 있는가?
• 메모리 할당후 나머지 가용 블록들을 어떻게 처리할 것인가?
  • -> 그대로 놔두면 내부 단편화가 일어날것이다. 작은 블록으로 다시 나눠서 free블록으로 쓸 수도 있을것이다.
• 할당된 free 블록들을 어떻게 고를 것인가?
• free된 블록들을 어떻게 할 것인가? 재연결 할것인가?

 

📌header

• header에는 해당 블록의 사이즈
• 할당여부, free여부를 나타내는 데이터가 담겨져있음

 

📌free된 블록들을 추적하는 법

 

💡1. implicit list (묵시적 가용 리스트)

• 모든 블록들의 헤더들을 방문하여, 해당 블록이 사용할 수 있는지를 저장한다.

 

💡2. explicit list(명시적 가용 리스트)

• free된 블록 내에 다음 free 블록을 가리키는 포인터가 있어, 한 free 블록에서 다음 free 블록의 위치를 명시적으로 알 수 있다.

 

💡3. segregated free list(분리 가용 리스트) 

• 할당이 해제되어 있는 블록들을 사이즈 별로 각각의 연결리스트로 만들어 관리한다.

 

💡4. blocks sorted by size(크기별로 정렬된 블록)

• 균형트리를 이용해 가용 리스트들을 크기 순서대로 정렬한다.

 

implicit list (묵시적 가용 리스트)

---

📌implicit list

• 블록이 할당 되어 있으면 a는 1이고, 할당되어 있지 않으면 0이다. 
• a는 항상 0이기 때문에 사이즈가 4바이트면 100, 2바이트면 10, 여기를 allocated/ free flag로 사용

📌Implicit Free List 예시

• 맨 처음은 unused word
  • -> 맨 처음에 헤더가 필요하고, 32bit로 8바이트(word 2개)로 정렬되어 있다는 전제가 있기 때문이다.

 

 

📌할당할 블록 배치 방법

• 간단하게 예를 들어 설명 해보겠습니다.

• 프로세스가 메인 메모리에 적재되기전 "나의 용량은 99M입니다. 제가 들어갈 수 있을만큼의 용량을 저에게 주세요^^;라고 말할 것이다. 그렇다면 프로세스보다 크거나 같은 가용 블록중 하나를 줄것이다. 어떻게, 어떠한 방법으로 해당 메모리를 프로세스에게 할당해 줄것인가? 바로 , first -fit , next-fit , best-fit 방법을 사용해 줄것이다.
• 위의 그림으로 설명하자면 16M의 프로세스가 메인 메모리에 적재되려고한다.
• first-fit(처음부터 끝까지 탐색하여 요청된 크기와 가장 근접한, 가장 가까운 크기의 메모리를 줄것이다)
  • ->메인 메모리 첫 부분을 가리키는 포인터가 있다고 가정하자, 그 포인터를 사용하여 배열을 탐색하듯이 탐색할 것이다. 첫 가용 블록은 8M으로 다음을 탐색하고, 그다음은 12M , 또 다음을 탐색한다. 그런데 22M은 충분히 16M이 들어갈 수 있다. 그래서 22M의 메모리 공간을 할당해줄것이다.
• next - fit(가장 마지막에 들어간 공간으로부터 가장 적합한곳을 줄것이다.)
  • ->스택처럼, 가장 마지막에 들어간 공간을 가리키는 포인터가 있다고 가정하자. 그 영역부터 탐색을 시작하여 공간을 찾는것이다. 포인터를 증가시키면서 결국 찾은 곳은 36M이다.
• best-fit(처음부터 끝까지 탐색하여 요청된 크기와 가장 근접한, 가장 가까운 크기의 메모리를 줄것이다.)
  • -> 왼쪽에서 보면 현재 18M이 가장 16M과 가깝고 근접하다. 그러므로 18M의 메모리 공간을 줄것이다.

💡1. Fist fit

• first fit : 처음부터 탐색하고 크기가 맞는 첫 가용 블록을 선택
• 장점 : 매우 빠른 탐색 속도 , 처음 으로 충분한 크기의 메모리 블록을 찾아 프로세스를 할당하므로 검색 시간이 매우 짧다.
• 단점 : 프로세스가 메모리 공간을 할당받지 못하는 경우가 발생한다는 것
  • 예시)

Input : blockSize[]   = {100, 500, 200, 300, 600};
        processSize[] = {212, 417, 112, 426};
Output:
Process No.    Process Size    Block no.
   1               212            2
   2               417            5
   3               112            2
   4               426        Not Allocated

• 마지막으로 프로세스 4를 할당하려고 하는데, 사용 가능한 블록중에는 300 크기의 블록이 가장 큰것이고, 이는 426의 프로세스를 수용할 수없어 할당되지 않는다.

 

💡구현 단계

1. 메모리 블록 크기와 프로세스 크기를 입력으로 받습니다.
   • 메모리 블록 크기: 사용 가능한 메모리 블록의 크기를 나타냅니다. 이것은 물리적인 메모리의 크기 또는 파티션 크기일 수 있습니다.
   • 프로세스 크기: 할당하려는 프로세스의 크기를 나타냅니다.
2. 모든 메모리 블록을 초기화하여 빈 상태로 표시합니다.
   • 이 단계에서는 사용 가능한 메모리 블록을 초기화하고, 이 블록들은 초기 상태에서는 아무런 프로세스가 할당되지 않은 상태(빈 상태)로 표시됩니다.
3. 각 프로세스를 선택하고 현재 블록에 할당할 수 있는지 확인합니다.
   • 이 단계에서는 프로세스를 하나씩 선택하고, 현재 검사 중인 메모리 블록에 할당할 수 있는지 여부를 확인합니다.
4. 만약 프로세스 크기가 현재 블록 크기보다 작거나 같으면 해당 블록에 할당하고 다음 프로세스를 확인
   • 현재 검사중인 메모리 블록의 크기가 선택한 프로세스의 크기와 같거나 크면, 해당 프로세스를 현재 블록에 할당합니다. 그런다음 다음 다음 프로세스를 선택하여 할당 가능한 블록을 찾아갑니다.
5. 그렇지 않으면 다음 블록을 확인하고, 이 과정을 반복
   • 현재 블록의 크기가 선택한 프로세스의 크기보다 작으면 다음 메모리 블록으로 이동하여 할당 가능한 블록을 찾는다. 이러한 과정을 모든 블록에 대해 반복

💡first-fit

#include<stdio.h>

// First-Fit 알고리즘을 따라 블록에 메모리를 할당하는 함수
void firstFit(int blockSize[], int m, int processSize[], int n)
{
	int i, j;
	// 각 프로세스에 할당된 블록 ID를 저장하는 배열
	int allocation[n];

	// 초기에는 어떤 블록도 어떤 프로세스에 할당되지 않았습니다.
	for(i = 0; i < n; i++)
	{
		allocation[i] = -1;
	}

	// 각 프로세스를 선택하고 적절한 블록을 찾아 할당합니다
	for (i = 0; i < n; i++)	 // 여기서 n은 프로세스의 수입니다
	{
		for (j = 0; j < m; j++)	 // 여기서 m은 블록의 수입니다
		{
			if (blockSize[j] >= processSize[i])
			{
				// 블록 j를 i번째 프로세스에 할당합니다
				allocation[i] = j;

				// 이 블록에서 사용 가능한 메모리를 감소시킵니다.
				blockSize[j] -= processSize[i];

				break; // 다음 프로세스로 이동합니다.
			}
		}
	}

	printf("\n프로세스 번호\t프로세스 크기\t블록 번호\n");
	for (int i = 0; i < n; i++)
	{
		printf(" %i\t\t\t", i+1); // 프로세스 번호를 출력합니다.
		printf("%i\t\t\t\t", processSize[i]); // 프로세스 크기를 출력합니다.
		if (allocation[i] != -1)
			printf("%i", allocation[i] + 1); // 할당된 블록 번호를 출력합니다.
		else
			printf("할당되지 않음"); // 할당되지 않은 경우를 표시합니다.
		printf("\n");
	}
}

// 메인 함수
int main()
{
	int m; // 메모리 블록의 수
	int n; // 입력 큐에 있는 프로세스의 수
	int blockSize[] = {100, 500, 200, 300, 600}; // 각 블록의 크기
	int processSize[] = {212, 417, 112, 426}; // 각 프로세스의 크기
	m = sizeof(blockSize) / sizeof(blockSize[0]); // 블록 수를 계산합니다.
	n = sizeof(processSize) / sizeof(processSize[0]); // 프로세스 수를 계산합니다.

	firstFit(blockSize, m, processSize, n); // First-Fit 알고리즘을 호출합니다.

	return 0;
}

• 결과

---

 

📌free 블록 찾는 방법 ( fisrt fit)

p = start;

while ((p < end) && ((*p & 1) || (*p <= len))) {
    p = p + (*p & -2);
}

• p의 주소 값이, heap의 맨 끝 주소 보다 작을 때만 반복해서 찾는다. 그리고 p가 가리키는 값의 맨 끝의 비트가 1이면 할당되어 있다는 뜻이니 넘어간다. 또한 우리가 할당하려는 사이즈 보다, p가 가르키는 블록의 사이즈가 작으면 할당할 수 없으니 이 또한 넘어간다.

p = p + (*p & -2);

• 2는 11111110이라고 볼 수 있다. 따라서 &라는 비트 연산자를 통해 p의 사이즈만 가져올 수 있다. 맨 마지막은 allocated, free를 나타내는 flag이므로 이와 상관없이 사이즈만 가져올 수 있다.
• next fit : 이전 탐색이 끝난 지점으로부터 free 리스트를 탐색한다.
• best fit : 처음부터 전부 검색하여 크기가 딱 맞는 블록을 추려낸다. first fit보다 느릴 수 있다.

 

📌free 블록에 할당하기

• 우리가 할당하고자 하는 블록의 크기가 free 블록의 크기보다 작을 수 있다. 이럴 때는 내부 단편화가 발생할 수 있으니 남은 블록을 split하는게 효율적이다.

void addblock (ptr p, int len) {
    int newsize = ((len + 1) >> 1) << 1;
    int oldsize = *p & -2;
    *p = newsize | 1;
    if (newsize < oldsize) {
        *(p + newsize) = oldsize - newsize;
    }
}

• 할당되는 크기인 newsize는 짝수가 되게한다. 홀수가 들어오면 +1을 한 후 오른쪽으로 shift하고 다시 왼쪽으로 shift하면 맨 끝이 0이면서 크기는 짝수가 된다. 원래 사이즈를 oldsize로 읽어주고 p가 가르키는 곳에는 newsize를 넣음과 동시에 1을 더하여 allocated임을 표시한다. 이 떄 만약 원래 블록의 크기가 더 컸다면, p에 newsize만큼 더한 곳의 헤더에는 할당하고 남은 블록의 크기를 나타내게 한다. 이때 newsisze와 oldsize 모두 맨 끝비트는 0이므로 둘이 빼주기만 하면 된다.

 

📌할당된 블록 free시키기

void free_block(ptr p) {
	*p = *p & - 2;
}

• free시키는 것은, 단순히 맨 끝 flag 비트를 0으로 바꿔주면 된다. 블록에 할당된 데이터는 지워지는 방식이 아니라 덮어씌워 지게 되는 것이다.

하지만 이렇게만 해주면 다음과 같이 5를 할당할 때 외부 단편화로 인해 할당할 수 없게 된다. 따라서 free끼리 이어져 있다면 연결 시켜줘야 한다.

 

📌연결

void free_block(ptr p) {
    *p = *p & -2;               // 기존 블록을 반환한다. *p = 0000 0101(allocated) -> 0000 0100(free), p = 0000 1000이라고 가정한다면,
    next = p + *p;              // 다음 블록은 기존 블록에 그 크기를 더한 값이 된다. next = 0000 1100
    if ((*next & 1) == 0) {     // 만약 다음 블록이 free 블록이라면, ex. *next = 0000 0010
        *p = *p + *next;        // 블록의 크기를 늘린다. 이 때 *p, 즉 포인터가 가르키는 값은 헤더이다.
    }                           // *p는 0000 0110으로 크기가 4에서 6으로 된다.
}

• 단순히 free만 시키는 코드에서 연결까지 해주는 것
• flag를 0 으로 만들어준 후, next는 현재 가리키는 포인터에 사이즈를 더해주는 것이다. 이 떄 이 next의 flag가 0이라면 free 블록임을 나타내므로 포인터가 가르키는 header에 현재 블록 사이즈와 next 블록의 사이즈를 더해준다. 이 때 둘다 flag는 0이므로 그저 더해주기만 하면된다.
• 위는 다음 블록이 free일 때이다. 하지만 이전 블록이 free라면 어떻게 연결할까?

 

📌경계태그로 연결하기

• 헤더를 복사하여, 블록의 끝에 위치시키도록한다. 이를 footer 혹은 경계 태그라고 칭한다. 이는 free 리스트를 탐색할 때 뒤로 가는 것 뿐만 아니라 앞으로도 갈 수 있게 해주지만, 공간을 추가적으로 요구한다.

• 헤더에서 한 칸만 앞으로 가면 이전 블록이 할당 상태인지, free상태인지 알 수 있다. 따라서 상수시간, constant time으로 연결 처리할 수 있다.  따라서 free 블록을 연결하는 데에 발생 할 수 있는 시간 복잡도는 O(1)이 된다.

 

📌경계태그연결이 4가지인 경우

 

 

📌경계태그단점과 개선 방안

• 단점 : 결국 header와 footer라는 개념을 사용하면 새로운 메모리 공간을 계속 필요로 하는 셈이니 메모리 오버헤드가 발생한다.
  * 오버헤드 : 어떤 처리를 하기 위해 필요한 간접적인 시간 or 메모리로, header와 footer라는 개념을 도입하면서 메모리 공간을 차지하게 되니 전체적으로 필요한 메모리 공간이 더 늘어나게 된다.
• 개선 방안 : 이전 혹은 이후 블록이 할당된다면, 즉 할당된 블록이 되버린다면 footer를 없애고 데이터를 넣을 수 있도록 한다. case들을 살펴보면 할당된 블록들의 footer들은, 연결된 블록의 header와 footer에 아무런 영향을 끼치고 있지 않다. 따라서 할당된 블록에서는 footer가 필요치 않다.
• 그렇다면, 해당 블록은 어떻게 이전의 블록이 할당되었는지 혹은 free인지 알 수 있을까? 해당 블록에서 헤더의 사용하지 않는 비트인 3개의 비트 중 1개에 이전의 블록 할당 상태를 저장하면 된다. 이러면 앞의 블록이 할당되었다고 가정했을 때, 현재 해당 블록의 3개 비트 중 1개의 비트는 이전 블록이 할당되었다고 알려주므로 연결을 시도하지 않을 것이다.

📌first-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 */
    "week5",
    /* First member's full name */
    "janghotoung",
    /* First member's email address */
    "ghdud4653@gmail.com",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

/* 메크로 */
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12)

#define MAX(x, y) ((x) > (y)? (x) : (y))

/* 크기와 할당 비트를 통합해서 헤더와 풋터에 저장할 수 있는 값을 return */
#define PACK(size, alloc) ((size) | (alloc))

/* 인자 p가 참조하는 워드 읽어서 return */
/* 인자 p는 대개 (void*) 포인터. 직접적으로 역참조 불가 */ 
#define GET(p) (*(unsigned int *)(p))
/* 인자 p가 가리키는 워드에 val 저장 */
#define PUT(p, val) (*(unsigned int *)(p) = (val))

/* 각각 주소 p에 있는 헤더, 풋터의 size와 할당 비트를 return */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/* 블록 포인터 bp가 주어지면, 각각 블록 헤더와 풋터를 가리키는 포인터 return */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* 블록 포인터 bp가 주어지면, 각각 다음과 이전 블록의 블록 포인터를 return */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (DSIZE-1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

/* 함수 선언 */
static void *extend_heap(size_t);
static void *coalesce(void *);

/* 전역 변수 */
static char *heap_listp;

/* 
 * mm_init - 할당기 초기화 
 */
int mm_init(void)
{   
    /* 메모리 시스템에서 4워드 가져와 빈 가용 리스트 만들 수 있도록 초기화 */
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
    return -1;
    PUT(heap_listp, 0);                          /* Alignment padding */
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
    PUT(heap_listp + (3*WSIZE), PACK(0, 1));     /* Epilogue header */
    heap_listp += (2*WSIZE);

    /* heap을 CHUNKSIZE 바이트로 확장 후 초기 가용 블록 생성 */
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL) 
        return -1;
    return 0;
}

/*
 * coalesc - 가용 블럭 생성시 통합 
 */
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){        /* Case 1 */
        return bp;
    }

    else if (prev_alloc && !next_alloc){   /* Case 2 */
        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){   /* Case 3 */
        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{                                   /* Case 4 */
        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);
    }
    return bp;
}

/* 
 * expend_heap - malloc package 초기화
 *               1. 힙 초기화시
 *               2. mm_malloc이 적당한 fit을 못찾았을 때, 정렬 유지 위해 호출
 */
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    /* 정렬 유지 위해 짝수 word 할당 */
    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
    return NULL;

    /* 가용 블럭의 헤더, 푸터 와 epilogue 헤더 초기화 */
    PUT(HDRP(bp), PACK(size, 0));         /* Free block 헤더 */
    PUT(FTRP(bp), PACK(size, 0));         /* Free block 푸터 */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue 헤더 */

    /* 이전 블록이 가용됬을 때 통합 */
    return coalesce(bp);
}

/* first-fit 검색 */
static void *find_fit(size_t asize)
{
    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;
        }
    }
    /* No fit */
    return NULL;    
}

/* 
 * place - 맞는 블록 찾으면 할당기는 요청한 블록을 배치, 옵션으로 추가 부분 분할
 */
static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));

    if ((csize - asize) >= (2 * DSIZE))
    {
        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
    {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

/* 
 * mm_malloc - size 바이트의 메모리 블록 요청
 *             brk pointer를 증가시켜 블록 할당        
 */
void *mm_malloc(size_t size)
{
    size_t asize;        /* 조정된 블록 크기 */
    size_t extendsize;   /* 적합하지 않을 경우 힙을 확장할 크기 */
    char *bp;

    /* 거짓 요청시 */
    if (size == 0)
        return NULL;

    /* 헤더와 풋터 위한 공간 확보 및 더블 워드 요건 만족시킴 */
    if (size <= DSIZE)
        asize = 2*DSIZE;
    else /* 8바이트 넘는 요청에 대해 오버헤드 바이트 추가, 인접 8의 배수로 반올림 */
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
    
    /* 적절한 가용 블록을 가용 리스트에서 검색 */
    if ((bp = find_fit(asize)) != NULL){
        /* 맞는 블록 찾으면 할당기는 요청한 블록을 배치, 옵션으로 추가 부분 분할 */
        place(bp, asize);
        /* 새로 할당한 블록의 포인터 return */
        return bp;
    }

    /* 적절한 가용 블록을 가용 리스트에서 찾지 못하면, 힙을 새로운 가용 블록으로 확장 */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    /* 요청한 블록을 새 가용 블록에 배치, 필요시 블록을 분할 */
    place(bp, asize);
    /* 새로 할당한 블록의 포인터 return */
    return bp;
}

/*
 * mm_free - 요청한 블록 반환하고 경계 태그 연결 사용해 상수 시간에 인접 가용 블록들과 통합
 */
void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    /* 인접 가용 블록들 통합 */
    coalesce(bp);
}


/*
 * mm_realloc - 동적 할당된 메모리 내용 유지하며 할당된 메모리 크기 변경
 */
void *mm_realloc(void *bp, size_t size)
{

    if ((int)size == 0)
    {
        // mm_free(bp);
        return NULL;
    }
    else 
    if (size > 0)
    {
        size_t oldsize = GET_SIZE(HDRP(bp));
        size_t newsize = size + (2 * WSIZE); /* 헤더와 푸터 위한 2 words 추가 */ 
        /* newsize가 oldsize보다 작거나 같으면 return bp */
        if (newsize <= oldsize)
        {
            return bp;
        }
        /* oldsize 보다 new size가 크면 바꿈 */
        else
        {
            /* 다음 블록의 할당 여부 비트 */
            size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
            size_t csize;
            /* next block이 가용 상태이고, old와 next block의 사이즈 합이 new size보다 크면 합쳐서 사용  */
            if (!next_alloc && ((csize = oldsize + GET_SIZE(HDRP(NEXT_BLKP(bp))))) >= newsize)
            {
                // remove_from_free_list(NEXT_BLK(bp));
                PUT(HDRP(bp), PACK(csize, 1));
                PUT(FTRP(bp), PACK(csize, 1));
                return bp;
            }
            /* next block이 할당된 상태이거나, old와 next block의 사이즈 합이 new size보다 작을 때 새 block 생성 */
            else
            {
                void *new_ptr = mm_malloc(newsize);
                // place(new_ptr, newsize);
                memcpy(new_ptr, bp, newsize);
                mm_free(bp);
                return new_ptr;
            }
        }
    }
    else
        return NULL;
}

 

 

 

 

 

📌next-fit

#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 */
    "week5",
    /* First member's full name */
    "janghoyoung",
    /* First member's email address */
    "ghdud4653@gmail.com",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

/* 메크로 */
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12)

#define MAX(x, y) ((x) > (y)? (x) : (y))

/* 크기와 할당 비트를 통합해서 헤더와 풋터에 저장할 수 있는 값을 return */
#define PACK(size, alloc) ((size) | (alloc))

/* 인자 p가 참조하는 워드 읽어서 return */
/* 인자 p는 대개 (void*) 포인터. 직접적으로 역참조 불가 */ 
#define GET(p) (*(unsigned int *)(p))
/* 인자 p가 가리키는 워드에 val 저장 */
#define PUT(p, val) (*(unsigned int *)(p) = (val))

/* 각각 주소 p에 있는 헤더, 풋터의 size와 할당 비트를 return */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/* 블록 포인터 bp가 주어지면, 각각 블록 헤더와 풋터를 가리키는 포인터 return */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* 블록 포인터 bp가 주어지면, 각각 다음과 이전 블록의 블록 포인터를 return */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

/* 정렬 유지 위해 가까운 배수로 반올림 */
#define ALIGN(size) (((size) + (DSIZE-1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

/* 함수 선언 */
static void *extend_heap(size_t);
static void *coalesce(void *);
static void *find_fit(size_t);
static void place(void *, size_t);

/* 전역 변수 */
static char *heap_listp;
static char *last_bp ; 

/* 
 * mm_init - 할당기 초기화 
 */
int mm_init(void)
{   
    /* 메모리 시스템에서 4워드 가져와 빈 가용 리스트 만들 수 있도록 초기화 */
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
    return -1;
    PUT(heap_listp, 0);                          /* Alignment padding */
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
    PUT(heap_listp + (3*WSIZE), PACK(0, 1));     /* Epilogue footer */
    heap_listp += (2*WSIZE);

    /* heap을 CHUNKSIZE 바이트로 확장 후 초기 가용 블록 생성 */
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL) 
        return -1;
    last_bp = heap_listp; 
    return 0;
}

/*
 * coalesc - 가용 블럭 생성시 통합 
 */
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){        /* Case 1 */
        last_bp = bp; 
        return bp;
    }

    else if (prev_alloc && !next_alloc){   /* Case 2 */
        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){   /* Case 3 */
        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{                                   /* Case 4 */
        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);
    }
    last_bp = bp; 
    return bp;
}

/* 
 * expend_heap - malloc package 초기화
 *               1. 힙 초기화시
 *               2. mm_malloc이 적당한 fit을 못찾았을 때, 정렬 유지 위해 호출
 */
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    /* 정렬 유지 위해 짝수 word 할당 */
    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
    return NULL;

    /* 가용 블럭의 헤더, 푸터 와 epilogue 헤더 초기화 */
    PUT(HDRP(bp), PACK(size, 0));         /* Free block 헤더 */
    PUT(FTRP(bp), PACK(size, 0));         /* Free block 푸터 */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue 헤더 */

    /* 이전 블록이 가용됬을 때 통합 */
    return coalesce(bp);
}

/* next-fit 검색 */
static void *find_fit(size_t asize)
{
    char *bp = last_bp;

    /* 현재 위치에서 다음 블록의 블록 크기가 0이 아닐 때, 그 다음 블록 검색 */
    for (bp = NEXT_BLKP(bp); GET_SIZE(HDRP(bp))!=0; bp = NEXT_BLKP(bp))
    {
        /* 가용 블록이고, 크기가 사이즈보다 크거나 같을 때 */
        if (GET_ALLOC(HDRP(bp)) == 0 && GET_SIZE(HDRP(bp)) >= asize)
        {
            last_bp = bp;
            return bp;
        }        
    }

    /* 가용 블록 리스트가 나올 때까지 */
    bp = heap_listp;
    while (bp < last_bp)
    {
        bp = NEXT_BLKP(bp);
        if (GET_ALLOC(HDRP(bp)) == 0 && GET_SIZE(HDRP(bp)) >= asize)
        {
            last_bp = bp;
            return bp;
        }
    }
    return NULL ;  
}

/* 
 * place - 맞는 블록 찾으면 할당기는 요청한 블록을 배치, 옵션으로 추가 부분 분할
 */
static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));

    if ((csize - asize) >= (2 * DSIZE))
    {
        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
    {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

/* 
 * mm_malloc - size 바이트의 메모리 블록 요청
 *             brk pointer를 증가시켜 블록 할당        
 */
void *mm_malloc(size_t size)
{
    size_t asize;        /* 조정된 블록 크기 */
    size_t extendsize;   /* 적합하지 않을 경우 힙을 확장할 크기 */
    char *bp;

    /* 거짓 요청시 */
    if (size == 0)
        return NULL;

    /* 헤더와 풋터 위한 공간 확보 및 더블 워드 요건 만족시킴 */
    if (size <= DSIZE)
        asize = 2*DSIZE;
    else /* 8바이트 넘는 요청에 대해 오버헤드 바이트 추가, 인접 8의 배수로 반올림 */
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
    
    /* 적절한 가용 블록을 가용 리스트에서 검색 */
    if ((bp = find_fit(asize)) != NULL){
        /* 맞는 블록 찾으면 할당기는 요청한 블록을 배치, 옵션으로 추가 부분 분할 */
        place(bp, asize);
        last_bp = bp;
        /* 새로 할당한 블록의 포인터 return */
        return bp;
    }

    /* 적절한 가용 블록을 가용 리스트에서 찾지 못하면, 힙을 새로운 가용 블록으로 확장 */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    /* 요청한 블록을 새 가용 블록에 배치, 필요시 블록을 분할 */
    place(bp, asize);
    last_bp = bp;
    /* 새로 할당한 블록의 포인터 return */
    return bp;
}

/*
 * mm_free - 요청한 블록 반환하고 경계 태그 연결 사용해 상수 시간에 인접 가용 블록들과 통합
 */
void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    /* 인접 가용 블록들 통합 */
    coalesce(bp);
}


/*
 * mm_realloc - 동적 할당된 메모리 내용 유지하며 할당된 메모리 크기 변경
 */
void *mm_realloc(void *bp, size_t size)
{
    if ((int)size < 0)
        return NULL;
    else if ((int)size == 0)
    {
        mm_free(bp);
        return NULL;
    }
    else if (size > 0)
    {
        size_t oldsize = GET_SIZE(HDRP(bp));
        size_t newsize = size + (2 * WSIZE); /* 헤더와 푸터 위한 2 words 추가 */ 
        /* newsize가 oldsize보다 작거나 같으면 return bp */
        if (newsize <= oldsize)
        {
            return bp;
        }
        /* oldsize 보다 new size가 크면 바꿈 */
        else
        {
            /* 다음 블록의 할당 여부 비트 */
            size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
            size_t csize;
            /* next block이 가용 상태이고, old와 next block의 사이즈 합이 new size보다 크면 합쳐서 사용  */
            if (!next_alloc && ((csize = oldsize + GET_SIZE(HDRP(NEXT_BLKP(bp))))) >= newsize)
            {
                // remove_from_free_list(NEXT_BLK(bp));
                PUT(HDRP(bp), PACK(csize, 1));
                PUT(FTRP(bp), PACK(csize, 1));
                return bp;
            }
            /* next block이 할당된 상태이거나, old와 next block의 사이즈 합이 new size보다 작을 때 새 block 생성 */
            else
            {
                void *new_ptr = mm_malloc(newsize);
                place(new_ptr, newsize);
                memcpy(new_ptr, bp, newsize);
                mm_free(bp);
                return new_ptr;
            }
        }
    }
    else
        return NULL;
}