00. 할당기 처리량(Throughput)과 메모리 최고 이용도(Peak Memory Utilization)
(1) 할당기 처리량 : 이 할당기가 얼마나 많은 요청을 처리하는가?
할당기 처리량이란 단위 시간 당 완료되는 요청의 수를 의미한다. 1초에 500번의 할당 연산과 500번의 반환 연산을 할 수 있다면 초당 1000연산의 할당기가 된다.
(2) 메모리 최고 이용도 : 힙을 얼마나 효율적으로 사용하고 있는가?
처리량 R0, R1, R2, ....Rn-1의 총 n번의 할당과 반환 요청에 대해
- HK : k + 1번의 요청 이후의 힙 크기. 항상 증가한다고 가정한다.
- PK : k + 1번의 요청에서의 payload의 합. Allocate면 증가, free면 감소
- UK : 첫 번째 K 요청에 대한 메모리 최고 이용도
- maxPi : k보다 낮은 모든 i에 대해 지금까지의 payload 합 중 가장 큰 값. 최대한으로 많이 할당한 데이터 값
메모리 최고 이용도 = (최대한으로 많이 할당한 데이터 크기)/(힙 크기)
만약 해당 할당기의 UK가 1이면, 다른 overhead 없이 순수하게 payload로만 이루어진 힙을 지닌다는 의미이다. 즉 이루어질 수는 없겠지만, 할당기가 가질 수 있는 가장 이상적인 힙 이용도가 된다. 할당기가 메모리 공간을 낭비하면서 빠른 연산을 수행하는 것은 쉽다. 할당기의 처리량은 높아지겠지만 메모리 최고 이용도는 낮아질 것이다. 이는 좋은 할당기라 보기 힘들다. 중요한 것은 할당기의 처리량과 메모리 최고 이용도 사이의 적절한 균형을 찾는일이다.
01. 묵시적 가용 리스트(Implicit list)와 명시적 가용리스트(Explicit list)
가용할 수 있는 블록들을 효율적으로 사용하려면 어떤 방법이 필요할까? 묵시적 가용리스트와 명시적 가용리스트에 대해 알아보자
묵시적 가용리스트는 할당된 블록과 가용한 블록이 모두 연결되어 있다. 명시적 가용리스트는 가용 가능한 블록끼리만 연결되어 있는 것을 확인 할 수 있다. 여기서 참고할 점 시스템의 정렬 요구조건과 할당기의 블록 포멧 선택이 최소 블록 크기를 결정한다. 따라서 최소 블록 크기는 어떤 방법이냐에 따라 가변적이다. 명시적 가용리스트는 가용 가능한 블록끼리만 연결되어 있다.
- 묵시적 가용리시트 : 할당된 블록과 가용한 블록이 모두 연결되어 있다.
- 명시적 가용리스트 : 가용 가능한 블록끼리만 연결되어 있다.
02. 묵시적 가용리스트의 장단점
- 묵시적 가용리스트의 장점은 단순성이다.
- 묵시적 가용리스트의 단점은 탐색에 필요한 연산 비용이 힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례한다.
- 묵시적 가용리스트는 힙 블록의 수가 사전에 알려져 있고, 작고 특수한 경우에는 좋을 수 있다.
- 묵시적 가용리스트의 탐색시간은 전체 힙 블록의 수에 비례하기 때문에 범용 할당기로는 처리속도가 느릴 수 있다.
03. 묵시적 가용리스트의 구성요소 (헤더, 데이터, 패딩)
(1) 헤더
헤더의 역할은 블록이 할당되었는지, 가용가능한 상태인지를 알려주는 역할과 동시에 블록의 사이즈를 반환한다. 헤더의 크기는 1워드(4byte, 32bit)이며, 32비트 중 29비트는 블록의 사이즈를 저장하고 나머지 3비트는 블록이 할당되었는지 나타낸다.
메모리 할당은 더블워드(8byte) 정렬 제한조건을 부과한다면 블록의 크기는 항상 8의 배수이다. 8의 2진수는 1000이므로 32비트 중 하위 3비트는 항상 0일 것이다. 따라서 하위 3비트(000)은 블록이 할당되었는지 사용이 가능한지 판단하는 블록으로 사용한다.
- 헤더의 크기는 1워드(4byte, 32bit)이다.
- 블록이 할당되었는지, 사용할 수 있는 상태인지를 반환하는 역할을 한다.
- 더블 워드(8byte)정렬 제한 조건을 부과한다면 블록의 크기는 항상 8의 배수이다.
- 8의 2진수는 1000이므로 32비트 중 하위 3비트는 항상 0이다.
- 32비트 중 29비트는 블록의 사이즈를 저장하고 나머지 3비트는 블록이 할당되었는지 나타낸다.
- OR 연산으로 계산한다.
(2) 데이터
- 헤더 다음에는 malloc을 불렀을 때 요구한 데이터가 따라온다. 위 그림에서는 Payload 부분이다.
(3) 패딩
0) 패딩을 알기전에 데이터의 정렬에 대해 알아보자
많은 컴퓨터 시스템들은 기본 자료형들에 대해 사용 가능한 주소를 제한하고 있어서 어떤 객체의 주소는 어떤 값 K(일반적으로 2, 4, 8)의 배수가 되도록 요구한다. 이러한 정렬제한은 프로세서와 메모리 시스템 간의 인터페이스를 구성하는 하드웨어의 설계를 단순하게 한다.
x84-64 하드웨어는 데이터의 정렬과 상관없이 정확하게 동작하지만 인텔은 메모리 시스템 성능을 개선하기 위해 데이터가 정렬될 것을 추천한다. 정렬 규칙은 K의 원시 객체들은 K의 원시 객체들은 K의 배수를 주소로 가져야 한다는 원칙에 기초한다.
| K | Types |
| 1 | char |
| 2 | short |
| 4 | int, float |
| 8 | long, double, char * |
1) 패딩이란?
- 정해진것 보다 바이트를 추가하여 CPU 접근을 용이하게 해준다.
- 데이터가 남는 공간에 패딩이 따라올 수 있는데, 패딩의 크기는 가변적이다.
2) 패딩을 왜 해야할까?
- malloc이 항상 더블워드로 정렬하기 위해서 패딩을 한다.
- 더블워드로 정렬한다는 말은 반환하는 메모리의 크기가 더블워드의 배수라는 말이 아닌, 반환하는 메모리 주소가 더블워드의 배수가 되어야 한다는 말이다. 더블워드로 반환하는 이유는 malloc call에서 쉽게 memory alignment에 맞는 메모리 주소를 반환할 수 있기 때문에 이러한 design choice를 한다!
- 외부 단편화를 극복하기 위해
- 정렬 요구사항을 만족하기 위해
03. 할당한 블록의 배치
(1) first fit : 가용 free 리스트를 처음부터 검색해서 크기가 맞는 첫번째 가용 블록을 선택
👉 장점 : 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있음
👉 단점 : 리스트의 앞부분에 작은 가용 블록들을 남겨두는 경향 있어 큰 블록을 찾는 경우 검색 시간이 늘어남
(2) next fit : fist fit과 비슷하지만 검색 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작한다.
👉 first fit보다 매우 빠른 속도를 가지지만 최악의 메모리 이용도를 갖는다.
(3) best fit : 모든 가용 블록을 검사하며 크기가 맞는 가장 작은 블록을 선택한다.
👉 best fit이 일반적으로 first fit이나 next fit보다는 더 좋은 메모리 이용도를 갖는다는 것을 밝혀냈다.
👉 best fit은 힙을 완전히 다 검색해야한다는 단점이 있다.
👉 best fit의 단점을 개선한 것이 복잡한 다단 가용 리스트(segregated free list)이다.
04. 가용블록의 분할
- 할당기가 크기에 맞는 블록을 찾았을 경우 어느 정도를 할당할지에 대해 결정해야한다.
- 가용 블록 전체를 사용하는 정책을 사용하면, 간단하고 빠르지만 큰 단점으로 내부 단편화가 생긴다.
- 위를 막기 위해 할당할 블록을 만들고 나머지 영역은 가용블록으로 만들어주면 된다.
05. 추가적인 힙 메모리 획득하기
- 가용 블록이 이미 최대로 연결되었다면 할당기는 커널에게 sork 함수를 호출해서 추가적인 힙 메모리를 요청한다.
- 할당기는 추가 메모리를 한 개의 더 큰 가용 블록으로 변환하고, 이블록을 가용 리스트에 삽입한 후에 요청한 블록을 배치
06. 가용 블록 연결하기
- 할당기가 할당한 블록을 free할때 새롭게 반환되는 블록에 인접한 다른 블록이 있을 수 있다.
- 추가적으로 할당할 때 인접한 블록을 연결하면 사용할 수 있지만, 현재는 나눠져 사용할 수 없는 상태의 블록이 되고 이것을 오류 단편화(false fragmentation)이라고 한다.
- 오류의 단편화를 극복하기 위해 실용적인 할당기라면 연결(coalescing) 과정으로 인접 가용 블록을 통합해야한다.
👉 연결을 언제 수행할지가 중요함!
- 블록이 반환될 때마다?
- 일정 시간 후에 가용 블록들을 연결하기 위해 기다리는 지연연결?
- 일부 할당 요청이 실패할 때까지 연결을 지연 ?
07. 오류 단편화(false fragmentation)
- 추가적으로 할당할 때 인접한 블록을 연결하면 사용할 수 있지만, 현재는 나눠져 사용할 수 없는 상태의 블록이 되고 이것을 오류 단편화(false fragmentation)이라고 한다.
- 오류의 단편화를 극복하기 위해 실용적인 할당기라면 연결(coalescing) 과정으로 인접 가용 블록을 통합해야한다.
08. 할당기로 어떻게 연결을 구현할까? (경계 태그로 연결하기)
(1) Header만 있을 때
- 헤더는 다음 블록의 헤더를 가리키고 있다.
- 헤더를 구현하며 다음 주소값만 알고 있을 때 탐색은 상수 시간 O(1)이 걸린다
👉 전체 리스트를 검색해서 이전 블록의 위치를 기억해야하기 때문
(2) 경계태그 footer를 추가해보자
- 가용 블록을 효율적으로 찾기 위해 Knuth가 생각해낸 방법
- 경계 태그란 헤더의 정보(블록의 크기, 할당 여부)를 복사해서 블록의 맨 끝에 둔다.
- footer는 4byte 크기이다.
(3) 경계태그의 단점과 개선방안
- 결국 새로운 메모리를 header와 footer에 할당해야하므로, 메모리 오버헤드가 발생한다.
- 메모리 오버헤드 단점을 극복하기 위해 이전 블록이 가용한 경우에만 사용하는 것이 좋다.
오버헤드 : 어떤 처리를 하기 위해 들어가는 간접적인 시간 & 메모리
08. 할당기 구현 _ fist fit
(1) 할당기 기본설계
- mem_heap : 힙의 첫 바이트를 가리키는 변수
- mem_brk : 힙의 마지막 바이트를 가리키는 변수
- mem_heap :힙의 최대 크기(20MB)의 주소를 가리키는 변수
(2) void mem_init(void) : 최대 힙 메모리 공간을 할당받고 초기화 해준다.
(3) void* mem_sbrk(int incr) : incr 크기만큼 힙을 늘려주고, 새 메모리의 시작점을 리턴한다.
//Private global variables
static char * mem_heap; //Points to first byte of heap
static char * mem_brk; //Points to last byte of heap plus 1
static char * mem_max_addr; //Max lega heap addr plus 1
//mem_init : Initialize the memory system model
void mem_init(void)
{
mem_heap = (char *)malloc(MAX_HEAP);
mem_brek = (char *)mem_heap;
mem_max_addr = (char *)(mem_heap + MAX_HEAP);
}
//mem_sbrk : Simple model of the sbrk funtion
// Extends the heap by incr bytes and returns the start address of the new area.
void *mem_sbrk(int incr)
{
char * old_brk = mem_brk;
if((incr < 0 || (mem_brk + incr) > mem_max_addr))
{
errno = ENOMEN;
fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
return (void *)-1;
}
mem_brk += incr;
// 이전 brk를 리턴한다. 새로운 메모리를 처음부터 사용해야 하니까.
return (void *)old_brk;
}
(2) 가용 리스트 조작을 위한 기본 상수 및 매크로 정의
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12)
#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)
//bp(현재 블록의 포인터)로 현재 블록의 header 위치와 footer 위치 반환
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) - GET_SIZE(HDRP(bp)) - DSIZE)
// 다음과 이전 블록의 포인터 반환
#define NEXT_BLKP(bp) (((char *)(bp) + GET_SIZE((char *)(bp) - WSIZE))) // 다음 블록 bp 위치 반환(bp + 현재 블록의 크기)
#define PREV_BLKP(bp) (((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))) // 이전 블록 bp 위치 반환(bp - 이전 블록의 크기)
(3) mm_init()
- 최초의 가용블록(4words)를 가지고 힙을 생성하고 할당기를 초기화 한다.
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
// Create the initial empty heap
// heap_listp가 힙의 최댓값 이상을 요청한다면 fail
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);
// Extend the empty heap with a free block of CHUNKSIZE bytes
if (extend_heap(CHUNKSIZE/WSIZE) == NULL) {
return -1;
}
return 0;
}
(3) extend_heap()
- 워드 단위 메모리를 인자로 받아 힙을 늘려준다.
- mem_sbrk() 함수를 이용해 새로 힙의 크기를 늘린다. 이 때 더블 워드 정렬에 맞게 할당 받는다.
- 새 가용 블록의 헤더와 풋터를 정해주고 epilogue block을 새로 정해준다.
- 이전 블록의 가용여부를 조사해 연결한다
/*
extend_heap 사용 경우
1) 힙이 초기화될 때
2) mm_malloc이 적당한 fit을 찾지 못했을 때
*/
static void *extend_heap(size_t words) {
char *bp;
size_t size;
// Allocate an even number of words to maintain alignment
size = (words % 2) ? (words+1) * WSIZE : words * WSIZE; // words가 홀수면 +1을 해서 공간 할당
if ((long)(bp = mem_sbrk(size)) == -1) {
return NULL;
}
// initialize free block header/footer and the epilogue header
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
/*
extend_heap 블록 너머에 오지 않도록 배치한 블록 다음 공간을 블록이라 가정하고 epilogue header 배치
(실제로는 존재하지 않는 블록)
*/
// coalesce if the previous block was free
return coalesce(bp);
}
(3) coalesce
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));
// case1: 앞, 뒤 블록 모두 할당되어 있을 때
if (prev_alloc && next_alloc) {
return bp;
}
// case2: 앞 블록 할당, 뒷 블록 가용
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));
}
// case3: 앞 블록 가용, 뒷 블록 할당
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);
}
// case4: 앞, 뒤 블록 모두 가용
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);
}
return bp;
}
(4) mm_malloc
/*
* mm_malloc - Allocate a block by incrementing the brk pointer.
* Always allocate a block whose size is a multiple of the alignment.
*/
void *mm_malloc(size_t size) {
size_t a_size; // adjusted block szie
size_t extend_size; // Amount to extend heap if no fit
char *bp;
// Ignore spurious requests
if (size == 0) {
return NULL;
}
// Adjust block size to include overhead and alignment reqs
if (size <= DSIZE) { // 2words 이하의 사이즈는 4워드로 할당 요청 (header 1word, footer 1word)
a_size = 2*DSIZE;
}
else { // 할당 요청의 용량이 2words 초과 시, 충분한 8byte의 배수의 용량 할당
a_size = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
}
// Search the free list for a fit
if ((bp = find_fit(a_size)) != NULL) { // 적당한 크기의 가용 블록 검색
place(bp, a_size); // 초과 부분을 분할하고 새롭게 할당한 블록의 포인터 반환
return bp;
}
// NO fit found. Get more memory and place the block
extend_size = MAX(a_size, CHUNKSIZE);
if ((bp = extend_heap(extend_size/WSIZE)) == NULL) { // 칸의 개수
return NULL;
}
place(bp, a_size);
return bp;
}
(5) find_fit()
static void *find_fit(size_t a_size) {
void *bp;
for (bp = (char *)heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && (a_size <= GET_SIZE(HDRP(bp)))) {
return bp;
}
}
return NULL; // NO fit
}
(6) place
static void place(void *bp, size_t a_size) {
size_t c_size = GET_SIZE(HDRP(bp));
if ((c_size - a_size) >= (2 * (DSIZE))) {
// 요청 용량 만큼 블록 배치
PUT(HDRP(bp), PACK(a_size, 1));
PUT(FTRP(bp), PACK(a_size, 1));
bp = NEXT_BLKP(bp);
// 남은 블록에 header, footer 배치
PUT(HDRP(bp), PACK(c_size - a_size, 0));
PUT(FTRP(bp), PACK(c_size - a_size, 0));
}
else { // csize와 aszie 차이가 네 칸(16byte)보다 작다면 해당 블록 통째로 사용
PUT(HDRP(bp), PACK(c_size, 1));
PUT(FTRP(bp), PACK(c_size, 1));
}
}
(7) mm_free
/*
* mm_free - Freeing a block does nothing.
*/
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);
}
(8) mm_realloc
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *bp, size_t size)
{
void *old_bp = bp;
void *new_bp;
size_t copySize;
new_bp = mm_malloc(size);
if (new_bp == NULL)
return NULL;
copySize = GET_SIZE(HDRP(old_bp));
if (size < copySize)
copySize = size;
memcpy(new_bp, old_bp, copySize); // 메모리의 특정한 부분으로부터 얼마까지의 부분을 다른 메모리 영역으로 복사해주는 함수(old_bp로부터 copySize만큼의 문자를 new_bp로 복사해라)
mm_free(old_bp);
return new_bp;
}09. 전체코드
/*
* 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 */
"week06",
/* First member's full name */
"YunaNoh",
/* First member's email address */
"vipwhy12@naver.com",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""
};
// Basic constants and macors
#define WSIZE 4 // Word and header/footer size(bytes)
#define DSIZE 8 // Double word size (btyes)
#define CHUNKSIZE (1 << 12) // Extend heap by this amount (bytes) : 초기 가용 블록과 힙 확장을 위한 기본 크기
#define MAX(x, y) ((x) > (y) ? (x) : (y)) // x > y가 참이면 x, 거짓이면 y
// PACK매크로 : 크기와 할당 비트를 통합해서 header와 footer에 저장할 수 있는 값 리턴
#define PACK(size, alloc) ((size) | (alloc))
// Read and wirte a word at address
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
// Read the size and allocated field from address p
#define GET_SIZE(p) (GET(p) & ~0x7) // header or footer의 사이즈 반환(8의 배수)
#define GET_ALLOC(p) (GET(p) & 0x1) // 현재 블록 가용 여부 판단(0이면 alloc, 1이면 free)
// bp(현재 블록의 포인터)로 현재 블록의 header 위치와 footer 위치 반환
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
// 다음과 이전 블록의 포인터 반환
#define NEXT_BLKP(bp) (((char *)(bp) + GET_SIZE((char *)(bp) - WSIZE))) // 다음 블록 bp 위치 반환(bp + 현재 블록의 크기)
#define PREV_BLKP(bp) (((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))) // 이전 블록 bp 위치 반환(bp - 이전 블록의 크기)
// Declaration
static void *heap_listp;
static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t a_size);
static void place(void *bp, size_t a_size);
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
// Create the initial empty heap
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1) { // heap_listp가 힙의 최댓값 이상을 요청한다면 fail
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);
// Extend the empty heap with a free block of CHUNKSIZE bytes
if (extend_heap(CHUNKSIZE/WSIZE) == NULL) {
return -1;
}
return 0;
}
/*
extend_heap 사용 경우
1) 힙이 초기화될 때
2) mm_malloc이 적당한 fit을 찾지 못했을 때
*/
static void *extend_heap(size_t words) {
char *bp;
size_t size;
// Allocate an even number of words to maintain alignment
size = (words % 2) ? (words+1) * WSIZE : words * WSIZE; // words가 홀수면 +1을 해서 공간 할당
if ((long)(bp = mem_sbrk(size)) == -1) {
return NULL;
}
// initialize free block header/footer and the epilogue header
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
/*
extend_heap 블록 너머에 오지 않도록 배치한 블록 다음 공간을 블록이라 가정하고 epilogue header 배치
(실제로는 존재하지 않는 블록)
*/
// coalesce if the previous block was free
return 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));
// case1: 앞, 뒤 블록 모두 할당되어 있을 때
if (prev_alloc && next_alloc) {
return bp;
}
// case2: 앞 블록 할당, 뒷 블록 가용
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));
}
// case3: 앞 블록 가용, 뒷 블록 할당
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);
}
// case4: 앞, 뒤 블록 모두 가용
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);
}
return bp;
}
/*
* mm_malloc - Allocate a block by incrementing the brk pointer.
* Always allocate a block whose size is a multiple of the alignment.
*/
void *mm_malloc(size_t size) {
size_t a_size; // adjusted block szie
size_t extend_size; // Amount to extend heap if no fit
char *bp;
// Ignore spurious requests
if (size == 0) {
return NULL;
}
// Adjust block size to include overhead and alignment reqs
if (size <= DSIZE) { // 2words 이하의 사이즈는 4워드로 할당 요청 (header 1word, footer 1word)
a_size = 2*DSIZE;
}
else { // 할당 요청의 용량이 2words 초과 시, 충분한 8byte의 배수의 용량 할당
a_size = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
}
// Search the free list for a fit
if ((bp = find_fit(a_size)) != NULL) { // 적당한 크기의 가용 블록 검색
place(bp, a_size); // 초과 부분을 분할하고 새롭게 할당한 블록의 포인터 반환
return bp;
}
// NO fit found. Get more memory and place the block
extend_size = MAX(a_size, CHUNKSIZE);
if ((bp = extend_heap(extend_size/WSIZE)) == NULL) { // 칸의 개수
return NULL;
}
place(bp, a_size);
return bp;
}
static void *find_fit(size_t a_size) {
void *bp;
for (bp = (char *)heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && (a_size <= GET_SIZE(HDRP(bp)))) {
return bp;
}
}
return NULL; // NO fit
}
static void place(void *bp, size_t a_size) {
size_t c_size = GET_SIZE(HDRP(bp));
if ((c_size - a_size) >= (2 * (DSIZE))) {
// 요청 용량 만큼 블록 배치
PUT(HDRP(bp), PACK(a_size, 1));
PUT(FTRP(bp), PACK(a_size, 1));
bp = NEXT_BLKP(bp);
// 남은 블록에 header, footer 배치
PUT(HDRP(bp), PACK(c_size - a_size, 0));
PUT(FTRP(bp), PACK(c_size - a_size, 0));
}
else { // csize와 aszie 차이가 네 칸(16byte)보다 작다면 해당 블록 통째로 사용
PUT(HDRP(bp), PACK(c_size, 1));
PUT(FTRP(bp), PACK(c_size, 1));
}
}
/*
* mm_free - Freeing a block does nothing.
*/
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 - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *bp, size_t size)
{
void *old_bp = bp;
void *new_bp;
size_t copySize;
new_bp = mm_malloc(size);
if (new_bp == NULL)
return NULL;
copySize = GET_SIZE(HDRP(old_bp));
if (size < copySize)
copySize = size;
memcpy(new_bp, old_bp, copySize); // 메모리의 특정한 부분으로부터 얼마까지의 부분을 다른 메모리 영역으로 복사해주는 함수(old_bp로부터 copySize만큼의 문자를 new_bp로 복사해라)
mm_free(old_bp);
return new_bp;
}'Computer Systems' 카테고리의 다른 글
| 🖥[CSAPP] 9장. 분리 가용리스트 (Segregated Free List) (1) | 2022.11.02 |
|---|---|
| 🖥[CSAPP] 9장. Malloc Lab 명시적 가용(Explicit Free List)리스트 구현하기 (0) | 2022.11.01 |
| 🖥[CSAPP] 9장. Malloc Lab 동적 메모리 할당 (2) | 2022.10.29 |
| 🖥[CSAPP] 1장. 운영체제는 하드웨어를 관리한다. (0) | 2022.10.29 |
| 🖥[CSAPP] 1장. 캐시가 정말 중요할까? (0) | 2022.10.29 |
댓글