묵시적 가용 리스트
- 모든 실용적인 할당기는 블록 경계를 구분하고, 할당된 블로고가 가용 블록을 구분하는 데이터 구조를 필요로 한다. 대부분의 할당기는 이 정보를 블록 내에 저장한다.
- 한 블럭은 1워드 헤더, 데이터, 추가적인 패딩으로 구성된다. 헤더에는 블록 크기(헤드와 추가적인 패딩 포함)와 블록의 할당 여부를 넣는다.
- 묵시적 가용 리스트는 힙을 연속된 할당 및 가용 블록의 배열로 구성한다.
- 할당기는 가용 블록 전체 집합을 힙 내의 전체 블록을 다니면서 방문할 수 있다.
묵시적 가용 리스트의 장단점
- 장점
- 단점
- 할당된 블록을 배치하는 것과 같은 가용 리스트를 탐색해야하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록 수에 비례한다.
할당한 블록의 배치
- 프로그램이
malloc(k)
를 통해 k
바이트의 블록을 요철할 때 할당기는 요청한 블록을 저장하기에 충분히 큰 가용 블록을 리스트에서 검색한다. 검색을 수행할 때 수행하는 정책에 따라 first fit
, next fit
, best fit
등이 있다.
first fit
- 가용 리스트를 순차적으로 탐색하면서 조건에 만족하는 블록이 있으면 해당 블록을 할당한다.
- 리스트의 마지막에 가장 큰 가용 블록을 남겨두는 경향이 있다
- 리스트의 앞부분에 작은 가용 블록을 남겨두는 경향이 있어서 큰 블록을 찾는 경우에 검색 시간이 늘어나는 것이 단점이다.
next fit
first fit
의 대안으로, 이전 검색에서 발견한 가용 블록을 발견한 위치에서 탐색을 시작하고 조건에 만족하는 블록이 있으면 해당 블록을 할당한다.
next fit
은 first fit
에 비해 매우 빠른 속도를 가지지만, 일부 연구에 의하면 next fit
이 first fit
보다 최악의 메모리 이용도를 갖는 것으로 밝혀졌다.
best fit
- 요청한 블록의 크기에 알맞은 블럭을(요청 크기보다 크면서 가용 블럭들 중에서 가장 작은 블럭) 할당한다.
- 힙을 완전히 다 탐색해야하는 단점이 있다.
가용 블럭의 분할
- 할당기가 크기가 맞는 가용 블럭을 찾은 후에 가용 블록의 어느 정도를 할당할지에 대해 정책적 결정을 내려야한다.
- 가용 블록 전체를 사용할 수 도 있지만 내부 단편화가 생긴다.
- 따라서 가용 블록을 두 부분으로 나누어 요청한 크기의 블록에는 메모리를 할당하고 나머지는 새로운 가용 블록을 만든다.
추가적인 힙 메모리 획득
- 할당기가 가용 리스트를 탐색했지만 요청한 크기의 블럭을 찾을 수 없는 경우
- 할당기는 커널에게
sbrk()
를 호출 (시스템콜) 추가적인 힙 메모리를 할당한다.
- 할당기는 추가 메모리를 한 개의 큰 가용 블록으로 만들고, 이 블록을 가용 리스트에 삽입한 뒤, 요청한 블록을 새로운 가용 블록에 배치한다.
오류 단편화
- 할당기가 할당한 블록을 반환할 때, 해당 블록의 인접 블록이 가용 블럭일 수 도 있다. 이 경우에는 오류 단편화False fragmentation 현상을 유발할 수 있다.
- 아래 그림을 보면 중간에 3워드 블록이 2개가 인접해있다. 이 때 4워드만큼 할당을 요청하면 가용한 메모리의 크기는 충분하지만 가용 블록이 2개로 나뉘어 있어 요청을 만족시키지 못한다.
- 오류 단편화를 극복하기 위해 인접한 가용 블록을 하나로 병합하는 과정이 필요하다
(Coalesce)
.
경계 태그
- 오류 단편화를 해결하기 위해 두 가용 블럭을 병합하는 과정을 한다고 했는데 어떻게 병합할까?
- 현재 블록 다음 블록은 현재 블록의 헤더를 통해 쉽게 크기와 할당 여부를 확인할 수 있다. 이전 블록의 경우에는 어떻게 크기와 할당 여부를 알 수 있을까?
Knuth
가 개발한 경계 태그
를 통해 상수 시간에 이전 블록을 연결할 수 있다.
- 블록의 끝 부분에
footer(경계 태그)
를 추가한다.
footer
는 헤더를 복사한 것이다.
- 각 블록이 풋터를 포함하면 할당기는 시작 위치와 이전 블록의 상태를 자신의 풋터를 조사해서 결정할 수 있고, 풋터는 항상 현재 블록의 시작 부분에서 1 워드 떨어진 곳에 있다.
First fit을 이용한 전체 코드
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
#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)
#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)))
#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
void *heap_listp;
void *heap_start;
static void *coalesce(void *);
static void *extend_heap(size_t);
static void *find_fit(size_t);
static void place(void *, size_t);
int mm_init(void)
{
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *) - 1)
return -1;
PUT(heap_listp, 0);
PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (3*WSIZE), PACK(0, 1));
heap_listp += (2*WSIZE);
if (extend_heap(CHUNKSIZE/WSIZE) == 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;
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);
}
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;
}
}
return NULL;
}
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_t asize;
size_t extendsize;
char *bp;
if (size == 0)
return NULL;
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)
{
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
coalesce(ptr);
}
static void *coalesce(void *ptr)
{
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
size_t size = GET_SIZE(HDRP(ptr));
if (prev_alloc && next_alloc) {
return ptr;
}
else if (prev_alloc && !next_alloc) {
size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size,0));
}
else if (!prev_alloc && next_alloc) {
size += GET_SIZE(HDRP(PREV_BLKP(ptr)));
PUT(FTRP(ptr), PACK(size, 0));
PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
ptr = PREV_BLKP(ptr);
}
else {
size += GET_SIZE(HDRP(PREV_BLKP(ptr))) + GET_SIZE(FTRP(NEXT_BLKP(ptr)));
PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0));
ptr = PREV_BLKP(ptr);
}
return ptr;
}
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;
}
Next fit을 이용한 전체 코드
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#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)
#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 char *heap_listp;
static void *extend_heap(size_t);
static void *coalesce(void *);
static void *next_fit(size_t);
static void place(void *, size_t);
static char* last_bp;
int mm_init(void){
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *) - 1)
return -1;
PUT(heap_listp, 0);
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (3 * WSIZE), PACK(0, 1));
heap_listp += (2 * WSIZE);
if (extend_heap(CHUNKSIZE / WSIZE) == 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;
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);
}
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
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
if ((bp = next_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 *bp){
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
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)
{
last_bp =bp;
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);
}
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((char *)oldptr - WSIZE) - DSIZE;
if (size < copySize) {
copySize = size;
}
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
static void* next_fit(size_t asize)
{
char* bp = last_bp;
while (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 ;
}
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));
}
}