[SW 정글 44일차] explicit 구현과 인스트럭션, 분산 파일 시스템

오늘은 어제 공부한 explicit free list를 사용하여 동적할당기를 직접 구현하고 컴퓨터 시스테 6장. 메모리 구조를 읽으면서 앞에서도 계속 봤던 인스트럭션이라는 단어와 분산 파일 시스템에 대해 공부해보았다.

 

 

 

1. 인스트럭션과 분산 파일 시스템

인스트럭션(instruction)은 컴퓨터가 어떠한 것을 어떻게 하는지 알고자 할 때, 이것을 알려주는 것이 인스트럭션이다.

예를 들어, 컴퓨터가 사각형을 그려야한다고 생각해보자.

시작 포인트를 준다.

시작 포인트에서 오른쪽으로 x만큼 간다.

그 지점에서 y만큼 아래로 간다.

그 지점에서 x만큼 왼쪽으로 간다.

그 지점에서 y만큼 위쪽으로 가서 시작 포인트를 만나게 선을 긋는다.

 

위와 같은 일려의 과정을 인스트럭션이라고 할 수 있다.

 

 

 

2. Explicit free list 구현하기

explicit free list에 대한 정리는 어제 했다.

https://straw961030.tistory.com/229

[SW 정글 43일차] #if, #elif, #else와 implicit + next_fit 그리고 explicit

코드를 보면 아래와 같다.

mm_init함수부터 달라져야하는 것을 볼 수 있다.

그 이유는 explicit free list를 구현하기 위해서는 더블링크드리스트가 필요하고 더블링크드리스트의 시작지점이 있어야하므로 prologue header 뒤에 2word를 할당받아 다음 free된 block 주소를 이어줄 수 있도록 해준다.

 

그리고 새롭게 4개의 매크로함수를 정의했다.

#define GET_NEXT_PTR(bp) (*(char **)(bp + WSIZE))

#define GET_PREV_PTR(bp) (*(char **)(bp))

#define SET_NEXT_PTR(bp, qp) (GET_NEXT_PTR(bp) = qp)

#define SET_PREV_PTR(bp, qp) (GET_PREV_PTR(bp) = qp)

위 매크로 함수는 free된 block이 나왔을 때, 링크를 이어주기 위한 함수와 주소를 찾아주기 위해 사용된다.

 

그리고 coalesce()함수에서도 앞, 뒤 free block이 링크된다면, 기존에 존재하던 free block을 링크드리스트에서 삭제해주는 작업이 추가됐다.

 

할당할 block을 찾기 위해 사용된 find_fit은 first-fit을 사용했다.

 

이전까지 동적할당기를 구현한 것은 implicit + next-fit이였는데 오늘 explicit를 구현해보니 점수가 확실히 많이 올랐다.

 

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include "memlib.h"
#include "mm.h"

#define WSIZE 4                     // word size 4로 지정
#define DSIZE (2 * WSIZE)           // double word size 8로 지정
#define CHUNKSIZE (1 << 12)         // heap size를 늘릴 때 사용할 chunksize 지정
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
#define GET_SIZE(p)  (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define HDRP(bp) ((void *)(bp) - WSIZE)
#define FTRP(bp) ((void *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLK(bp) ((void *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLK(bp) ((void *)(bp) - GET_SIZE((void *)(bp)-DSIZE))

#define GET_NEXT_PTR(bp) (*(char **)(bp + WSIZE))
#define GET_PREV_PTR(bp) (*(char **)(bp))
#define SET_NEXT_PTR(bp, qp) (GET_NEXT_PTR(bp) = qp)
#define SET_PREV_PTR(bp, qp) (GET_PREV_PTR(bp) = qp)


static char *heap_listp = 0;
static char *free_list_start = 0;
static void *coalesce(void *bp);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
static void insert_in_free_list(void *bp);
static void remove_from_free_list(void *bp);
static void checkblock(void *bp);
static void checkheap(bool verbose);
static void printblock(void *bp);

int mm_init(void)
{
	if ((heap_listp = mem_sbrk(6 * WSIZE)) == NULL) 
		return -1;

	PUT(heap_listp, 0);							   /* padding */
	PUT(heap_listp + (1 * WSIZE), PACK(2*DSIZE, 1)); /* Prologue header */
	PUT(heap_listp + (2 * WSIZE), 0);
	PUT(heap_listp + (3 * WSIZE), 0);
	PUT(heap_listp + (4 * WSIZE), PACK(2*DSIZE, 1)); /* Prologue footer */
	PUT(heap_listp + (5 * WSIZE), PACK(0, 1));	   /* Epilogue header */
	free_list_start = heap_listp + 2 * WSIZE;
	
	if (extend_heap(4) == NULL)
	{
		return -1;
	}
	return 0;
}

static void *extend_heap(size_t words)
{
	char *bp;
	size_t size;
	size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
	// minimum block을 16사이즈로 정함
	if (size < 16)
	{
		size = 16;
	}
	if ((int)(bp = mem_sbrk(size)) == -1)
	{
		return NULL;
	}

	PUT(HDRP(bp), PACK(size, 0));		 /* free block header */
	PUT(FTRP(bp), PACK(size, 0));		 /* free block footer */
	PUT(HDRP(NEXT_BLK(bp)), PACK(0, 1)); /* new epilogue header */
	return coalesce(bp);
}

static void *coalesce(void *bp) 
{
	size_t NEXT_ALLOC = GET_ALLOC(HDRP(NEXT_BLK(bp)));
	size_t PREV_ALLOC = GET_ALLOC(FTRP(PREV_BLK(bp)));  
	//PREV_BLK(bp) == bp: epilogue block을 만났을 떄. Extend했을 때 epilogue를 만나는 유일한 경우
	size_t size = GET_SIZE(HDRP(bp));

	if (PREV_ALLOC && !NEXT_ALLOC)
	{
		size += GET_SIZE(HDRP(NEXT_BLK(bp)));
		remove_from_free_list(NEXT_BLK(bp));
		PUT(HDRP(bp), PACK(size, 0));
		PUT(FTRP(bp), PACK(size, 0));
	}

	else if (!PREV_ALLOC && NEXT_ALLOC)
	{
		size += GET_SIZE(HDRP(PREV_BLK(bp)));
		bp = PREV_BLK(bp);
		remove_from_free_list(bp);
		PUT(HDRP(bp), PACK(size, 0));
		PUT(FTRP(bp), PACK(size, 0));
	}

	else if (!PREV_ALLOC && !NEXT_ALLOC)
	{
		size += GET_SIZE(HDRP(PREV_BLK(bp))) + GET_SIZE(HDRP(NEXT_BLK(bp)));
		remove_from_free_list(PREV_BLK(bp));
		remove_from_free_list(NEXT_BLK(bp));
		bp = PREV_BLK(bp);
		PUT(HDRP(bp), PACK(size, 0));
		PUT(FTRP(bp), PACK(size, 0));
	}
	insert_in_free_list(bp);
	return bp;
}

void *mm_malloc(size_t size)
{
	size_t asize;	   /* 조정 block size */
	size_t extendsize; /* fit 안 됐으면 늘려야 할 사이즈 */
	void *bp;

	if (size == 0)
		return (NULL);

	/* Adjust block size 하는거 */
	if (size <= DSIZE)
		asize = 2 * DSIZE;
	else
		asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);

	// explicit은 first fit으로
	if ((bp = find_fit(asize)) != NULL)
	{
		place(bp, asize);
		return (bp);
	}

	/* No fit found.  Get more memory and place the block. */
	extendsize = MAX(asize, CHUNKSIZE);
	if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
		return (NULL);
	place(bp, asize);
	return (bp);
}

static void *find_fit(size_t asize)
{
	void *bp;
	static int last_malloced_size = 0;
	static int repeat_counter = 0;
	// 계속 똑같은 사이즈만 요청했을 때 요청 횟수가 60회가 넘어가면 아예 힙사이즈 확늘린다.(성능을 높이기 위한 방법) 
	if (last_malloced_size == (int)asize)
	{
		if (repeat_counter > 60)
		{
			int extendsize = MAX(asize, 4 * WSIZE);
			bp = extend_heap(extendsize / 4);
			return bp;
		}
		else
			repeat_counter++;
	}
	else
		repeat_counter = 0;
	// free block list에서 first fit으로 찾기
	for (bp = free_list_start; GET_ALLOC(HDRP(bp)) == 0; bp = GET_NEXT_PTR(bp))
	{
		if (asize <= (size_t)GET_SIZE(HDRP(bp)))
		{
			last_malloced_size = asize;
			return bp;
		}
	}
	return NULL;
}

static void place(void *bp, size_t asize)
{
	size_t csize = GET_SIZE(HDRP(bp));

	if ((csize - asize) >= 4 * WSIZE)
	{
		PUT(HDRP(bp), PACK(asize, 1));
		PUT(FTRP(bp), PACK(asize, 1));
		remove_from_free_list(bp);
		bp = NEXT_BLK(bp);
		PUT(HDRP(bp), PACK(csize - asize, 0));
		PUT(FTRP(bp), PACK(csize - asize, 0));
		coalesce(bp);
	}
	else
	{
		PUT(HDRP(bp), PACK(csize, 1));
		PUT(FTRP(bp), PACK(csize, 1));
		remove_from_free_list(bp);
	}
}

static void insert_in_free_list(void *bp)
{
	SET_NEXT_PTR(bp, free_list_start);
	SET_PREV_PTR(free_list_start, bp);
	SET_PREV_PTR(bp, NULL);
	free_list_start = bp;
}

static void remove_from_free_list(void *bp)
{
	//내 앞에 누구 있으면
	if (GET_PREV_PTR(bp))
		SET_NEXT_PTR(GET_PREV_PTR(bp), GET_NEXT_PTR(bp)); //내 앞 노드의 주소에다가, 내 뒤 노드의 주소를 넣어준다.
	else												  // 내 앞에 아무도 없으면 == 내가 젤 앞 노드이면
		free_list_start = GET_NEXT_PTR(bp);				  //나를 없애면서, 내 뒷 노드에다가 가장 앞자리의 왕관을 물려주고 간다!
	SET_PREV_PTR(GET_NEXT_PTR(bp), GET_PREV_PTR(bp));
}

void mm_free(void *bp)
{
	size_t size;
	if (bp == NULL)
		return;
	/* Free and coalesce the block. */
	size = GET_SIZE(HDRP(bp));
	PUT(HDRP(bp), PACK(size, 0));
	PUT(FTRP(bp), PACK(size, 0));
	coalesce(bp);
}

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 for header and footer
		/*if newsize가 oldsize보다 작거나 같으면 그냥 그대로 써도 됨. just return bp */
		if (newsize <= oldsize)
		{
			return bp;
		}
		//oldsize 보다 new size가 크면 바꿔야 함.*/
		else
		{
			size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLK(bp)));
			size_t csize;
			/* next block is free and the size of the two blocks is greater than or equal the new size  */
			/* next block이 가용상태이고 old, next block의 사이즈 합이 new size보다 크면 그냥 그거 바로 합쳐서 쓰기  */
			if (!next_alloc && ((csize = oldsize + GET_SIZE(HDRP(NEXT_BLK(bp))))) >= newsize)
			{
				remove_from_free_list(NEXT_BLK(bp));
				PUT(HDRP(bp), PACK(csize, 1));
				PUT(FTRP(bp), PACK(csize, 1));
				return bp;
			}
			// 아니면 새로 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;
}

static void checkblock(void *bp)
{

	if ((uintptr_t)bp % DSIZE)
		printf("Error: %p is not doubleword aligned\n", bp);
	if (GET(HDRP(bp)) != GET(FTRP(bp)))
		printf("Error: header does not match footer\n");
}

void checkheap(bool verbose)
{
	void *bp;

	if (verbose)
		printf("Heap (%p):\n", heap_listp);

	if (GET_SIZE(HDRP(heap_listp)) != DSIZE ||
		!GET_ALLOC(HDRP(heap_listp)))
		printf("Bad prologue header\n");
	checkblock(heap_listp);

	for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = (void *)NEXT_BLK(bp))
	{
		if (verbose)
			printblock(bp);
		checkblock(bp);
	}

	if (verbose)
		printblock(bp);
	if (GET_SIZE(HDRP(bp)) != 0 || !GET_ALLOC(HDRP(bp)))
		printf("Bad epilogue header\n");
}


static void printblock(void *bp)
{
	bool halloc, falloc;
	size_t hsize, fsize;

	checkheap(false);
	hsize = GET_SIZE(HDRP(bp));
	halloc = GET_ALLOC(HDRP(bp));
	fsize = GET_SIZE(FTRP(bp));
	falloc = GET_ALLOC(FTRP(bp));

	if (hsize == 0)
	{
		printf("%p: end of heap\n", bp);
		return;
	}

	printf("%p: header: [%zu:%c] footer: [%zu:%c]\n", bp,
		   hsize, (halloc ? 'a' : 'f'),
		   fsize, (falloc ? 'a' : 'f'));
}

 

---

[오늘의 나는 어땠을까?]

오늘은 지난 주차부터 많이 보지 못했던 컴퓨터 시스템 책을 볼 수 있는 시간을 가졌고 explicit를 구현하면서 코드를 내 것으로 만들려고 노력했다.

 

컴퓨터 시스템을 읽으면서 캐시메모리에 대해서는 간단히 알고있었지만 지역성을 유지하고 효율성을 높이기 위해 case별로 생각해보면서 캐시메모리에 대해 더 자세히 알 수 있었다.

 

SW 정글에서 우리에게 후드집업을 선물로 주셨는데 2XL이지만 사이즈가 생각보다 많이 작은 것같다..

그래도 운영진님들이 우리를 생각해서 제작해주셨고 이러한 후드집업이 나중에는 또 다른 추억의 물품이 될 수 있기에 감사하게 받았다.

지난 번 채널코퍼레이션 설명회 이후 채널코퍼레이션 맨투맨을 주셨는데 회사별 cloth collection도 가능할 것 같다.

 

지금까지 sw 정글 후드집업, 채널코퍼레이션 맨투맨, 프로그래머스 반팔티까지..