반응형
6주 차의 과제 malloc-lab 구현을 하기 위해 필요한 개념과 implicit 가용 리스트 구현 코드에 대해서 정리하는 글이다.
모든 글의 자세한 내용은 컴퓨터 시스템 책에 나와있으니 자세한 내용이 궁금하다면 책을 참고하기 바란다.
1. 동적 메모리 할당이 필요한 이유 & 알아야 하는 이유
이번 과제를 간단히 생각해서 동적 메모리 할당기를 만든다고 생각하면 된다.
이걸 만들기 앞서 왜 만들어야하는지 이유를 알아보자
만약 동적 메모리 할당 없이 정적으로만 메모리 할당이 가능하다면 어떤 일이 일어날까??
일단 항상 필요한 메모리를 알아야 할 것이다. 100개의 숫자를 저장하는 배열이 필요하면 100개짜리 배열을 만들면 된다. 이때 100개가 아닌 1000개로 늘어나면 다시 배열을 1000개로 늘려야 할 것이다.
필요한 데이터가 바뀔 때 마다 새롭게 작성해야 하는 불편함이 있다.
만약 우리가 필요한 메모리를 모른다고 생각해보자. 그러면 충분히 넉넉하게 메모리를 할당해야만 정상적으로 프로그램이 동작한다. 하지만 많은 양의 메모리를 할당했는데 생각한 메모리보다 적은 메모리가 필요할 수 있다.
이러한 상황에서는 불필요한 메모리가 낭비된다.
이러한 문제점 때문에 런타임에서 필요할 때 필요한 만큼의 메모리를 할당하는 동적메모리할당이 필요하다.
요약
- 동적 메모리 할당으로 자료구조의 크기를 모르는 상황에서도 필요한 만큼의 메모리할당으로 메모리를 낭비하지 않아도 되고 관리도 쉬워지기 때문이다.
동작원리를 알아야하는 이유
- 할당기를 정확하고 효율적으로 사용하기 위해서 할당기가 어떻게 동작하는지 이해할 필요가 있다.
2. 동적메모리 할당기
동적 메모리 할당기가 무엇인지 알아보자
동적 메모리 할당 기는 heap(힙)이라는 프로세스의 가상 메모리 영역을 관리한다.
동적 메모리 할당기는 힙(heap)이라고 하는 프로세스의 가상 메모리 영역을 관리한다. 자세한 내용은 시스템마다 다르지만, 힙을 미초기화된 데이터 영역 직후에 시작해서 위쪽으로(높은 주소 방향으로) 커지는 무요구 메모리 영역이라고 가정하자. 각각의 프로세스에 대해서, 커널은 힙의 꼭대기를 가리키는 변수 brk(break라고 발음)를 사용한다.
할당기는 힙을 다양한 크기의 ‘블록’들의 집합으로 관리한다. 블록들은 할당되었거나(allocated), 가용한(free) *가상메모리의 연속적인 묶음이다. 가용 블록은 애플리케이션이 명시적으로 할당할 때까지 가용한 상태로 남아있고, 할당된 블록은 애플리케이션에 의해 명시적으로 또는 메모리 할당기 자신에 의해 묵시적으로 반환될 때까지 할당된 채로 남아있다.
2 - 1. 할당기 두 가지 유형(명시적 할당기, 묵시적 할당기)
명시적 할당기
- 응용프로그램이 할당된 블록을 반환해 줄 것을 요구한다.
- C에서는 malloc 이라는 명시적 할당기를 제공한다
우리가 과제에서 구현하게될 할당기이다.
묵시적 할당기
- 할당된 블록이 프로그램에 의해 더 이상 사용되지 않을 때를 할당기가 알 수 있도록 요구한다.
- 가비지 컬렉터로 알려져 있으며 자동으로 사용하지 않는 할당된 블록을 반환시키는 작업을 한다.
3. 할당기 요구사항과 목표
명시적 할당기들은 다소 엄격한 제한사항 내에서 동작해야 한다.
- 임의의 요청 순서 처리
- 응용프로그램은 임의의 순서로 할당과 반환 요청을 할 수 있다.
- 모든 할당 요청이 쌍을 이루는 할당과 반한 요청이 연속된다고 가정할 수 없음
- 요청에 즉시 응답 & 블록 정렬
- 할당기는 블록들이 어떤 종류의 데이터 객체라도 저장할 수 있는 방식으로 정렬해야 한다.
- 힙만 사용하기
- 확장성을 갖기 위해서 할당기가 사용하는 비확장성 자료 구조들은 힙 자체에 저장되어야 한다.
- 할단된 블록 수정하지 않기
- 할당기는 가용 블록만 조작하거나 변경 가능
- 블록이 할당되면 수정하거나 이동할 수 없다.
- 할당된 블록들을 압축하는 것 같은 기법은 허용되지 않는다.
4. 단편화(Fragmentation)
메모리 단편화
- 메모리 공간이 작은 조각으로 나눠져 사용 가능한
메모리가 충분히 존재하지만 할당(사용)이 불가능한 상태
내부 단편화
- 메모리를 할당할 때 프로세스가 보다 더 큰 메모리가 할당되어 사용하는 메모리 공간을 낭비할 때
외부 단편화
- 총 메모리 공간은 충분하지만 요청을 처리할 수 있는 단일한 가용 블록이 없을 때 발생
위 그림에서 파란 부분은 메모리 할당 상태 흰색은 가용 상태 블록을 나타낸다.
만약 위의 상태에서 8블록을 요청하면 가용 블록의 수(흰색)는 8개로 충분하지만
단일 가용 블록은(6개 p2와 p3 사이)는 8개가 되지 않아 외부 단편화가 발생한다.
5. 묵시적 가용 리스트
묵시적 가용 리스트는 아래와 같은 형태이다.
할당(allocated)된 블록은 색칠되어 있고 가용(free) 블록은 흰색이다.
하나의 네모는 1 Word로 책 기준 4byte이다.
이제부터 블록의 기본 포맷과 할당 블록의 배치, 분할, 연결 등을 설명하겠다.
5-1 기본 힙 블록의 포맷
일단 그림부터 보고 하나씩 설명을 하겠다. 그림 2의 블록 그림은 그림 1의 네모 하나(word 단위)가 아니다.
할당된 블록(파란색) 또는 가용 블록(흰색) 묶음을 말한다. 그림 1의 제일 앞 흰색 2칸을 묶어서 위의 그림 2를 나타낸다.
힙 블록은 크게 3가지로 구분되고 각 부분이 담고 있는 정보를 보자
- 1 워드(4byte) 헤더
- Block size (헤더와 패딩 포함)
- Allocated(1) / free(0) 여부
- 데이터(Payload)
- 할당된 블록에 데이터가 저장되는 부분
- 패딩(Optional)
- *정렬 제한 조건을 맞춰주기 위해 추가하는 부분
- 외부 단편화를 막기 위해서도 사용됨
정렬 제한 조건
정렬 제한 조건이란 할당기에 블록을 할당 시 블록들이 가지는 byte의 수가 정렬 조건의 배수가 되게 하는 것이다.
책에서는 더블 워드(8byte) 정렬 조건으로 정렬이 이루어진다.
만약 8byte의 데이터를 확보한다면
헤더(4byte) + 데이터(8byte)가 되어 12byte가 필요한데 더블 워드 정렬 조건으로 byte수가 8의 배수가 되어야 한다.
이때 패딩(4byte) 하나를 추가하여 8의 배수를 맞춰준다.
헤더의 하위 3비트
더블 워드 정렬 제한 조건에 맞다면 블록 크기는 항상 8의 배수이고 하위 3비트는 항상 0이다.
위의 말이 처음에는 이해가 가지 않아서 고생하였다. 왜 하위 3비트는 항상 0인지 설명하겠다.
먼저 우리가 기억하는 건 아래 두 가지
1. 헤더는 1 word로 4byte의 크기 4byte는 32비트
2. 더블 워드 정렬로 블록의 크기는 항상 8의 배수
헤더의 32비트에는 블록의 사이즈가 저장된다.
하위 비트 세 개 1 1 1(2) 은 십진수로 나타내면 최대 7까지 나타낼 수 있다.
그렇기 때문에 8의 배수가 헤더에 저장되면 4번째 비트부터 변화가 생기고 하위 3개 비트는 항상 0이다.
이 하위 세개 중 가장 오른쪽을 Allocated(1) / free(0) 여부 기록용으로 사용된다.
5 - 2 할당한 블록의 배치
위에서 블록의 포맷과 리스트의 모양까지 알아보았다.
이제 블록을 할당하는 배치 정책을 알아보자
- Frist fit
- 가용 free 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택한다.
- 책에서 구현한 방법
- Next fit
- 이전 검색이 종료된 지점에서 검색을 시작한다.
- Best fit
- 모든 가용 블록을 검사하여 크기가 맞는 가장 작은 블록을 선택한다.
5-3 가용 블록의 분할
할당기는 대체로 가용 블록을 두 부분으로 나누게 된다.
첫 번째는 할당한 블록이 되고 나머지는 새로운 블록이 된다.
아래의 예시를 보자
p부터 4크기를 할당하면 6 전체를 할당하지 않고 4만큼 할당하고 2만큼 새로운 가용 블록을 만든다.
5-4 가용 블록의 연결
위 사진 처럼 가용 블록이 16, 16으로 나눠져있다.
가용 메모리가 인접하게 있는 현상을 오류 단편화라고 한다.
이렇게 나눠져있는 상태에서 32를 할당하면 공간이 충분하더라도 할당할 수 없어 블록을 연결해야한다.
- 오류 단편화를 극복하기 위해 연결(coalescing) 과정으로 인접한 가용 블록을 연결한다.
5-5 경계 태그로 연결하기
만약 반환하여 가용상태로 만드는 블록이 '현재블록'이라고 할 때, 다음 가용 블록을 연결하는 것은 간단하다.
현재 블록의 헤더의 주소에서 헤더의 크기를 더해주면 다음 블록의 헤더를 찾을 수 있다.
하지만 이전 블록을 찾기 위해서는 앞에서부터 다시 탐색해야 가능하다.
위 가용 블록하는 과정을 쉽게 하기 위해서 블록에 새로운 요소 푸터가 추가된다.
footer는 헤더를 그대로 복사하여 블록의 끝에 추가한다.
헤더와 같이 4byte를 추가한다.
footer는 이전 블록을 쉽게 찾게 해준다.
다만 작은 크기의 블록을 여러개 할당하면 상당한 양의 메모리 오버헤드가 발생한다.
5-6 연결하는 4가지 경우
- case1: 이전과 다음 블록이 모두 할당되어 있는 상태
- 현재 블록의 상태를 변경하면 된다.
- case:2 이전 블록은 할당 상태, 다음 블록은 가용상태
- 현재블록과 다음 블록이 통합된다.
- case:3 이전 블록은 가용상태, 다음 블록은 할당 상태
- 이전 블록의 헤더와 현재 블록의 풋터는 두 블록의 크기를 합한 것이다.
- 이전 블록과 다음 블록 통합
- case:4 이번 블록과 다음 블록 모두 가용 상태이전 블록의 헤드와 다음 블록의 푸터는 세 블록의 크기를 합한 것으로 갱신된다.
- 세 블록 모두 하나의 가용 블록으로 통합
6. 코드 구현하기
책에 있는 코드 그대로이며 이해되지 않는 부분을 따로 정리한 내용이다.
마지막에 코드 전체를 올려두었다.
구현에 앞서 상수와 메크로를 선언한다
#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))
/* 주소 p의 헤더 또는 푸터의 SIZE와 할당 비트를 리턴한다.*/
#define GET_SIZE(p) (GET(p) & ~0x7) // 뒤에 3비트를 제외하고 읽어옴
#define GET_ALLOC(p) (GET(p) & 0x1) // 할당 가용 확인
/* 각각 블록 헤더와 풋터를 가리키는 포인터를 리턴한다.*/
#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)))
#define PREV_BLKP(bp) (((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE)))라인별 설명
GET(p) (*(unsigned int *)(p))
- 인자 p가 참조하는 워드(워드의 값)를 읽어서 리턴한다.
- p는 (void * )형인데 역참조가 불가능하여 형변환 한다.
PUT(p, val) (*(unsigned int *)(p) = (val))
- 인자 p가 가리키는 워드에 val을 저장한다.
GET_SIZE(p) (GET(p) & ~0X7)
- 주소 p에 있는 헤더 또는 푸터의 size를 리턴한다.
- 7을 비트연산 not으로 반전 시키고 & 연산으로 뒤의 3비트를 제외한 값을 읽어온다.
GET_ALLOC(p) (GET(p) & 0X1)
- 주소 p에 있는 헤더 또는 푸터의 할당 비트를 리턴한다.
HDRP(bp) ((char *)(bp) - WSIZE)
- 블록 헤더를 가리키는 포인터를 리턴한다.
- bp(payload의 시작 주소) 에서 1word 만큼 앞으로 주소 이동 (헤더)
FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp))- DSIZE)
- 블록 Footer를 가리키는 포인터를 리턴한다.
- bp주소 + 블록사이즈 - 더블 워드 사이즈(8)를 연산하면 Footer 블록을 가리키게 된다.
NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
- 다음 블록의 블록 포인터를 리턴한다.
- GET_SIZE 부분은 HDRP랑 같다. bp에 블록 사이즈 만큼 더해서 주소를 옮기면 다음 블록으로 이동한다.
PREV_BLKP(bp) ((char*)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
- 이전 블록의 블록 포인터를 리턴한다.
- GET_SIZE부분을 연산하면 이전 블록의 푸터의 size 값을 가져온다.
- bp에서 이전 푸터의 size 만큼 빼주면 이전 블록의 bp로 이동하게 된다.
mm_init(void) - 빈 가용 리스트를 초기화함
int mm_init(void)
{
// mem_sbrk: 힙 영역을 incr(0이 아닌 양수) bytes 만큼 확장하고, 새로 할당된 힙 영역의 첫번째 byte를 가리키는 제네릭 포인터를 리턴함
/* 비어있는 heap을 만든다.*/
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);
// 두 가지 다른 경우에 호출된다.
// (1) 힙이 초기화 될때 (2) mm_malloc이 적당한 맞춤fit을 찾지 못했을 때
if (extend_heap(CHUNKSIZE/WSIZE) == NULL){
return -1;
}
return 0;
}라인별 설명
if((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
- heap_listp에 4word만큼의 메모리를 확장한다.
- padding, prologue (header, footer), epilogue를 위한 공간을 할당한다.
PUT(heap_listp, 0)
- 제일 처음 padding 영역을 추가한다.
PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1));
- Prologue header를 1워드 할당하고 DSIZE로 값을 넣는다.
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));
- Prologue footer를 1워드할당하고 DSIZE로 값을 넣는다.
PUT(heap_listp + (3*WSIZE), PACK(0, 1));
- Epilogue header를 1워드 할당하고 0 사이즈를 넣는다.
if (extend_heap(CHUNKSIZE/WSIZE) == NULL){
- 힙을 CHUNKSIZE 바이트로 확장하고 초기 가용 블록을 생성함
extend_heap(size_t words) - 2가지 다른 경우에 함수 호출
static void *extend_heap(size_t words)
{
// 요청한 크기를 인접 2워드의 배수(8바이트)로 반올림하여, 그 후에 추가적인 힙 공간 요청
char *bp;
size_t size;
// 요청한 크기를 2워드의 배수로 반올림하고 추가 힙 공간을 요청함
size = (words %2) ? (words+1)*WSIZE : words * WSIZE;
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);
};size = (words %2) ? (words+1)*WSIZE : words * WSIZE
- 정렬을 위해 인접 2워드의 배수(8바이트)로 반올림하며, 추가적인 힙 공간 요청
PUT(HDRP(bp), PACK(size, 0))
- 새로운 블록에 헤더를 만든다.
PUT(FTRP(bp), PACK(size, 0));
- 새로운 블록의 푸터를 만든다.
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
- 새로운 블록 뒤에 붙는 에필로그 헤더를 만든다.
return coalesce(bp);
- 이전 힙이 가용 블록으로 끝났다면 두 개의 가용 블록을 통합하기 위해 coalesce 호출
static void *coalesce(void *bp) - 할당된 블록을 합치는 4가지 경우
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);
//bp = PREV_BLKP(bp); 동일하게 동작함
//PUT(HDRP((bp)), PACK(size, 0));
//PUT(FTRP(bp), PACK(size, 0));
}
return bp;
}static void *find_fit(size_t asize) - 적절한 가용블록을 검색한다.
static void *find_fit(size_t asize){
// 적절한 가용 블록을 검색한다.
//first fit 검색을 수행한다. -> 리스트 처음부터 탐색하여 가용블록 찾기
void *bp;
//헤더의 사이즈가 0보다 크다. -> 에필로그까지 탐색한다.
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;
}
}
return NULL;
}
static void place(void *bp, size_t asize)
매개변수
- void bp*: bp 가용 블록의 주소
- size_t asize: 가용블록에 할당하는 size
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));
}
}void *mm_malloc(size_t size) - size만큼 메모리를 할당함
void *mm_malloc(size_t size)
{
size_t asize;
size_t extendsize;
char *bp;
if (size == 0){
return NULL;
}
// size를 바탕으로 헤더와 푸터의 공간 확보
// 8바이트는 정렬조건을 만족하기 위해
// 추가 8바이트는 헤더와 푸터 오버헤드를 위해서 확보
if (size <= DSIZE){
asize = 2*DSIZE;
}else{
asize = DSIZE*((size+(DSIZE) + (DSIZE-1)) / DSIZE);
}
// 가용 블록을 가용리스트에서 검색하고 할당기는 요청한 블록을 배치한다.
if((bp = find_fit(asize)) !=NULL){
place(bp, asize);
return bp;
}
//맞는 블록을 찾기 못한다면 새로운 가용 블록으로 확장하고 배치한다.
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}void mm_free(void *ptr) - 할당한 블록 반환
void mm_free(void *ptr)
{
size_t size = GET_SIZE(HDRP(ptr));
// 헤더와 푸터를 0으로 할당하고 coalesce를 호출하여 가용 메모리를 이어준다.
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
coalesce(ptr);
}전체 코드
/*
* 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 */
"team 8",
/* First member's full name */
"Heo Wonyoung",
/* First member's email address */
"dnjsdud2257@gmail.com",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""
};
/* 기본 상수 및 macros*/
#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))
/* 주소 p의 헤더 또는 푸터의 SIZE와 할당 비트를 리턴한다.*/
#define GET_SIZE(p) (GET(p) & ~0x7) // 뒤에 3비트를 제외하고 읽어옴
#define GET_ALLOC(p) (GET(p) & 0x1) // 할당 가용 확인
/* 각각 블록 헤더와 풋터를 가리키는 포인터를 리턴한다.*/
#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)))
#define PREV_BLKP(bp) (((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE)))
// 전역 힙 변수 및 함수 선언
static void *heap_listp;
static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
// mem_sbrk: 힙 영역을 incr(0이 아닌 양수) bytes 만큼 확장하고, 새로 할당된 힙 영역의 첫번째 byte를 가리키는 제네릭 포인터를 리턴함
/* 비어있는 heap을 만든다.*/
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);
// 두 가지 다른 경우에 호출된다.
// (1) 힙이 초기화 될때 (2) mm_malloc이 적당한 맞춤fit을 찾지 못했을 때
if (extend_heap(CHUNKSIZE/WSIZE) == NULL){
return -1;
}
return 0;
}
static void *extend_heap(size_t words)
{
// 요청한 크기를 인접 2워드의 배수(8바이트)로 반올림하여, 그 후에 추가적인 힙 공간 요청
char *bp;
size_t size;
// 요청한 크기를 2워드의 배수로 반올림하고 추가 힙 공간을 요청함
size = (words %2) ? (words+1)*WSIZE : words * WSIZE;
if((long)(bp = mem_sbrk(size)) == -1)
return NULL;
PUT(HDRP(bp), PACK(size, 0)); //free 블록의 header
PUT(FTRP(bp), PACK(size, 0)); //free 블록의 footer
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // new epilogue header
return coalesce(bp);
};
// 할당된 블록을 합칠 수 있는 경우 4가지에 따라 메모리 연결
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);
bp = PREV_BLKP(bp);
PUT(HDRP((bp)), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
}
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 asize;
size_t extendsize;
char *bp;
if (size == 0){
return NULL;
}
// size를 바탕으로 헤더와 푸터의 공간 확보
// 8바이트는 정렬조건을 만족하기 위해
// 추가 8바이트는 헤더와 푸터 오버헤드를 위해서 확보
if (size <= DSIZE){
asize = 2*DSIZE;
}else{
asize = DSIZE*((size+(DSIZE) + (DSIZE-1)) / DSIZE);
}
// 가용 블록을 가용리스트에서 검색하고 할당기는 요청한 블록을 배치한다.
if((bp = find_fit(asize)) !=NULL){
place(bp, asize);
return bp;
}
//맞는 블록을 찾기 못한다면 새로운 가용 블록으로 확장하고 배치한다.
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *ptr)
{
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
coalesce(ptr);
}
static void *find_fit(size_t asize){
// 적절한 가용 블록을 검색하고 가용블록의 주소를 반환한다
//first fit 검색을 수행한다. -> 리스트 처음부터 탐색하여 가용블록 찾기
void *bp;
//헤더의 사이즈가 0보다 크다. -> 에필로그까지 탐색한다.
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;
}
}
return NULL;
}
//
static void place(void *bp, size_t asize){
// 맞는 블록을 찾으면 요청한 블록을 배치하고 초과부분을 분할한다.
size_t csize = GET_SIZE(HDRP(bp));
if((csize - asize) >= (2*DSIZE)){
//가용 블록에 사이즈 - 요청한 블록의 사이즈 각 더블워드*2 크거나 같을때
//요청 블록을 넣고 남은 사이즈는 가용 블록으로 분할
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{
//할당하고 남은 블록이 더블워드*2보다 작다며 나누지 않고 할당
// 남은 블록이 더블워드*2보다 작은 경우는 데이터를 담을 수 없음
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
/*
* 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;
}반응형
'지난 글 모음' 카테고리의 다른 글
| [sw 정글] pintos 3주차 - part 2: Anonymous page & Lazy Loading (0) | 2022.06.21 |
|---|---|
| [sw 정글] pintos 3주차 - part 1: Memory Management (0) | 2022.06.21 |
| [week06] sw정글 사관학교 6주차 회고 (2) | 2022.05.09 |
| [sw정글] RB트리 INSERT pseudo-code 정리 - sentinel node (2) | 2022.05.02 |
| [sw 정글] 5/02 TIL c언어 및 Linked-list, 이진검색트리 (1) | 2022.05.02 |