묵시적 가용 리스트(implicit availability list)
실용적인 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록으로 구분하는 데이터 구조를 필요한다. 이 정보를 블록 내에 저장
한 개의 블록은 1워드의 헤더, 데이터, 추가적인 패딩으로 구성된다.
malloc은 payload의 시작을 반환한다.
헤더는 블록 크기(헤더와 추가적인 패딩 포함)와 블록이 할당되었는지 가용 상태인지 인코딩한다.
-> 더블 워드 정렬 제한조건을 부과한다면 블록 크기는 항상 8의 배수, 블록 크기의 하위 3비트는 항상 0이다.
-> 남은 블록 크기의 상위 29비트만 저장할 필요가 있으며 나머지 3비트는 다른 정보를 인코드하기 위해 남겨둔다.
이 경우 블록이 할당되었는지 가용 상태인지를 나타내기 위해 최소 중요 비트(할당된 비트)를 사용하고 있다.
ex) 블록 크기 24바이트(0x18)를 갖는 할당 블록이 있다 헤더는 다음과 같다.
0x00000018 | 0x1 = 0x00000019
ex) 블록 크기 40(0x28)를 갖는 가용 블록은 다음과 같은 헤더
0x00000028 | 0x0 = 0x00000028
헤더 다음에는 응용이 malloc을 불렀을 때 요구한 데이터가 따라온다.
데이터 다음에는 사용하지 않는 패딩이 따라 올 수 있는데 이들의 크기는 가변적이다.
패딩은 외부 단편화를 극복하기 위한 할당기의 전략, 정렬 요구사항을 만족하기 위해 필요하다.
묵시적 리스트
가용 블록이 헤더 내 필드에 의해서 묵시적으로 연결되기 때문이다.
간접적으로 가용 블록 전체 집합을 힙 내의 전체 블록을 다니면서 방문
종료하는 헤더는 할당 비트가 세트되어 있고 크기는 0이다.
장점은 단순성
단점은 할당된 블록을 배치하는 것과 같은 가용 리스트를 탐색해야 하는 연산들의 비용이
힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례
시스템의 정렬 요구조건과 할당기의 블록 포맷 선택이 할당기에 최소 블록 크기를 결정한다는 것을 깨닫는 것이 중요
할당되거나 반환된 블록 모두는 이 최솟값보다 더 작을 수 없다.
-> 더블 워드 정렬 요구조건에서 각 블록의 크기는 2워드(8바이트)의 배수
-> 블록 포맷은 2워드의 최소 블록 크기를 도출할 수 있도록 한다. -> 어플리케이션이 한개의 바이트를 요청할지라도 할당기는 여전히 2워드 블록을 만들 것이다.
할당한 블록의 배치
어플리케이션이 k바이트의 블록을 요청 시 할당기는 요청한 블록을 저장하기에 충분히 큰 가용 블록 리스트에서 검색
검색을 수행하는 방법은 배치 정책에 의해 결정
First fit - 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록 선택
- 장점 - 리스트의 마지막에 가장 큰 가용 블록 남겨두는 경향
- 단점 - 리스트의 앞부분에 작은 가용 블록들을 남겨두는 경향 -> 큰 블록을 찾는 경우 검색 시간 증가
Next fit - 이전 검색이 종료된 지점에서 검색 시작
- 장점 - First fit에 비해 매우 빠른 속도(이전 검색에서 가용 블록 발견 시 나머지 부분에서 원하는 블록 찾은 확률 증가)
- 단점 - First fit 보다 최악의 메모리의 이용도를 갖는 것으로 밝혀짐
Best fit - 모든 가용 블록을 검사, 크기가 맞는 가장 작은 블록 선택
- 장점 - 더 좋은 메모리 이용도
- 단점 - 힙을 완전히 다 검색해야 한다는 점. -> 복잡한 다단 가용 리스트 조직(segregated free list)에서 살펴 본다.
가용 크기 분할
할당기가 크기가 맞는 가용 블록을 찾은 후 가용 블록의 어느 정도를 할당할지에 대해 정책적 결정을 내린다.
한 가지 옵션은 가용 블록 전체를 사용하는것 -> 간단하고 빠르지만, 큰 단점은 내부 단편화가 발생
-> 배치 정책으로 인해 크기가 잘 맞는다면, 일부 가적인 내부 단편화는 수용
크기가 잘 안맞는다면, 대개 가용 블록을 두 부분으로 나눈다. 할당한 블록, 새로운 가용 블록
8워드 가용 블록을 분할해서 응용이 요청한 3워드 힙 메모리 할당을 어떻게 만족 시키는지 보여준다??
추가적인 힙 메모리 획득하기
요청한 블록을 찾을 수 없다면
메모리에서 물리적으로 인접한 가용 블록들을 합쳐서 더 큰 가용 블록을 만들어 보는 것.
이렇게 해도 충분히 큰 블록이 만들어지지 않거나 가용 블록이 이미 최대로 연결디었다면,
커널에게 sbfk 함수를 호출해서 추가적인 힙 메모리를 요청한다.
추가 메모리를 한 개의 더 큰 가용 블록으로 변환하고,
가용 리스트에 삽입한 후에 요청한 블록을 새로운 가용한 블록에 배치
가용 블록 연결하기
할당한 블록을 반환 시 새롭게 반환하는 블록에 인접한 다른 가용 블록이 있을 수 있다.
인접 가용 블록들은 오류 단편화(false fragmentation)라는 현상을 유발할 수 있으며, 작고 사용할 수 없는 가용 블록으로 쪼개진 많은 가용 메모리들이 존재
오류 단편화를 극복하기 위해 실용적인 할당기라면 연결이라는 과정으로 인접 가용 블록들을 통합해야 한다.
언제 연결을 수행해야 할지에 관한 중요한 정책결정을 해야 한다.
블록 반환 시 인접 블록을 통합해서 즉시 연결을 선택할 수 있다.
일정 시간 후에 가용 블록들을 연결하기 위해 기다리는 지연 연결을 선택할 수 있다.
즉시 연결은 간단하며 상수 시간 내에 수행할 수 있지만, 일부 요청 패턴에 대해서는 블록이 연속적으로 연결되고
잠시 후에 분할되는 쓰래싱의 형태를 유발할 수 있다.
경계 태그로 연결하기
반환하려고 하는 블록을 현재 블록이라고 하자, 그러면, 다음 가용 블록을 메모리에서 연결하는 것은 쉽고 효율적
현재 블록의 헤더는 다음 블록의 헤더를 가리키고 있으며, 이것은 다음 블록이 가용한지 결정한지 위해 체크될 수 있다.
그 크기는 단순히 현재 헤더의 크기에 더해지고, 블록은 상수 시간 내에 연결
이전 블록 연결
묵시적 가용 리스트에서 현재 블록에 도달할 때까지 전체 리스트를 검색해서 이전 블록의 위치를 기억
묵시적 가용 리스트를 사용 시 각각의 free호출이 힙의 크기에 비례하는 시간을 소모할 것이라는 것을 의미
경계 태그
상수 시간에 이전 블록을 연결
각 블록의 끝 부분에 푸터(경계 태그)를 추가하는 것으로, 헤더를 복사한 것
할당기는 시ㅏㄱ 위치와 이전 블록의 상태를 자신의 프ㅜ터를 조사해서 결정
이것은 현재 블록의 시작 부분에서 한 워드 떨어진 곳에 위치한다.
할당기가 현재 블록을 반환 시 모든 경우
1. 이전과 다음 블록이 모두 할당
2. 이전 할당, 다음 가용
3. 이전 가용, 다음 할당
4. 이전 다음 블록이 모두 가용
잠재적 단점 - 각 블록이 헤더와 풋터를 유지해야 하므로 만일 응용이 많은 작은 크기의 블록을 다룬다면 상당한 양의ㅡ 메모리 오버헤드가 발생할 수 있다.
EX) 그래프의 모든 메모리에 단 몇 개의 워드만을 필요로 하며, 할당 삭제를 반복 시 헤더와 풋터는 각 할당된 블록의 절반을 차지
다행히 풋터가 할당된 블록에 있을 필요를 없애는 경계 태그를 영리하게 최적화 하는 방법 존재
현재 블록을 메모리에 있는 이전과 다음 블록을 연결 시 만일 이전 블록이 가용한 경우에만 이전 블록의 풋터에 잇는 sizze필드가 필요하다
현재 블록의 추가적인 하위 비트들 중의 하나에 이전 블록의 할당 / 가용 비트를 저장하려고 한다면
할당된 블록들은 풋터가 필요 없어지고 추가적인 공간을 데이터를 위해 사용할 수 있었을 것이다.
가용 블록은 여전히 풋터를 필요로 한다.
종합 설계 - 간단한 할당기 구현
블록 포맷, 가용 리스트 형식, 배치, 분할, 연결 정책 등의 수 많은 옵션들을 가지고 있기 때문에 매우 크다.
최대 블록 크기는 2**23 = 4GB
코드는 32비트(gcc -m32) 또는 64비트(gcc -m64)이며, 프로세스에서 수정 없이 돌 수 있는 것은 64비트이다.
할당기 기본 설계
memlib.c 패키지에서 제공되는 메모리 시스템의 모델을 사용한다.
설계한 할당기가 기존의 시스템 수준의 malloc 패키지와 상관없이 돌 수 있도록 하기 위한것.
mem_init 함수는 힙에 가용한 가상 메모리를 큰 더블 워드로 정렬된 바이트의 배열로 모델한 것.
mem_heap과 mem_brk 사이의 바이트들은 할당된 가상 메모리
mem_brk 다음에 오는 바이트들은 미할당 가상메모리를 나타낸다.
mem_sbrk 함수를 호출해서 추가적인 힙 메모리를 요청, 힙 축소하라는 요청을 거부한느 것만 제외하고는
시스템의 sbrk 함수와 동일한 의미, 동일한 인터페이스
할당기 자체는 사용자가 자신의 응용에서 컴파일하고 링크할 수 있는 소스 파일에 포함
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
/*
* memlib.c - a module that simulates the memory system. Needed because it
* allows us to interleave calls from the student's malloc package
* with the system's malloc package in libc.
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include <errno.h>
#include "memlib.h"
#include "config.h"
/* private variables */
static char *mem_start_brk; /* points to first byte of heap */
static char *mem_brk; /* points to last byte of heap */
static char *mem_max_addr; /* largest legal heap address */
/*
* mem_init - initialize the memory system model
*/
void mem_init(void)
{
/* allocate the storage we will use to model the available VM */
if ((mem_start_brk = (char *)malloc(MAX_HEAP)) == NULL) {
fprintf(stderr, "mem_init_vm: malloc error\n");
exit(1);
}
mem_max_addr = mem_start_brk + MAX_HEAP; /* max legal heap address */
mem_brk = mem_start_brk; /* heap is empty initially */
}
/*
* mem_deinit - free the storage used by the memory system model
*/
void mem_deinit(void)
{
free(mem_start_brk);
}
/*
* mem_reset_brk - reset the simulated brk pointer to make an empty heap
*/
void mem_reset_brk()
{
mem_brk = mem_start_brk;
}
/*
* mem_sbrk - simple model of the sbrk function. Extends the heap
* by incr bytes and returns the start address of the new area. In
* this model, the heap cannot be shrunk.
*/
void *mem_sbrk(int incr)
{
char *old_brk = mem_brk;
if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
errno = ENOMEM;
fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
return (void *)-1;
}
mem_brk += incr;
return (void *)old_brk;
}
/*
* mem_heap_lo - return address of the first heap byte
*/
void *mem_heap_lo()
{
return (void *)mem_start_brk;
}
/*
* mem_heap_hi - return address of last heap byte
*/
void *mem_heap_hi()
{
return (void *)(mem_brk - 1);
}
/*
* mem_heapsize() - returns the heap size in bytes
*/
size_t mem_heapsize()
{
return (size_t)(mem_brk - mem_start_brk);
}
/*
* mem_pagesize() - returns the page size of the system
*/
size_t mem_pagesize()
{
return (size_t)getpagesize();
}
|
mm_init 함수는 할당기를 초기화하고 성공 시 0 아니면 -1 반환
mm_malloc과 mm_free 함수는 이들에 대응되는 시스템 함수들과 동일한 인터페이스와 의미르 ㄹ가진다.
할당기는 블록 포맷을 사용한다.
최소 블록 크기는 16바이트다.
가용 리스트는 묵시적 가용 리스트로 구성되며, 변하지 않는 형태
첫 번재 워드는 더블 워드 경계로 정렬된 미사용 패딩 워드, 패딩 다음에는 특별한 프롤로그 블록이 오며
이것은 헤더와 풋터로만 구성된 8바이트 할당 블록
프롤로그 블록은 초기화 과정에서 생성되며 절대 반환하지 않는다.
프롤로그 블록 다음에는 malloc, free 를 호출해서 생성된 0 또는 1개 이상의 일반 블록들이 온다. 힙은 항상 특별한 에필로그 블록으로 끝나며, 이것은 헤더만으로 구성된 크기가 0으로 할당된 블록이다. 프롤로그와 에필로그 블록들은 연결과정 동안에 가장자리 조건을 없애주기 위한 속임수이다.
할당기는 한 개의 정적 전역변수를 사요하며 이것을 항상 프롤로그 블록을 가리킨다.
- Prologue: 프로그램에서 malloc 함수를 호출할 때, malloc 내부에서 수행되는 초기 설정 및 작업을 나타냅니다. Prologue는 malloc 함수가 할당된 메모리 블록의 메타 정보를 설정하고, 사용 가능한 메모리 블록을 찾아내거나 새로운 메모리 블록을 할당하기 위한 준비 작업을 수행합니다.
- Epilogue: Epilogue는 malloc 함수가 메모리 할당 작업을 완료한 후, 할당된 메모리 블록의 주소를 반환하고 마무리 작업을 수행하는 부분입니다. 주로 malloc 함수가 할당된 메모리 블록을 사용할 수 있게 하고, 메모리 블록의 크기 및 상태 정보를 업데이트합니다.
가용 리스트 조작을 위한 기본 상수와 매크로
기본 상수 정의 - 워드 크기, 더블 워드, 초기 가용 블록과 힙 확장을 위한 기본 크기
|
1
2
3
4
5
6
7
8
|
// 워드, 헤더, 푸터의 사이즈를 4
#define WSIZE 4
// 더블 워드 사이즈를 8
#define DSIZE 8
// 힙을 확장 시 지정 - 4바이트
#define CHUNKSIZE (1<<12)
|
PACK 매크로는 크기와 할당 비트를 통합해서 헤더와 풋터에 저장할 수 있는 값을 리턴한다.
|
1
|
#define PACK(size, alloc) ((size) | (alloc))
|
|
1
2
3
4
5
6
7
|
#define PACK(size, alloc) ((size) | (alloc))
// 사용 예
int block_size = 64; // 메모리 블록의 크기
int is_allocated = 1; // 메모리 블록이 할당되었는지 여부
int packed_value = PACK(block_size, is_allocated);
|
size - 메모리 블록의 크기를 나타낸다. 할당하려는 메모리 블록의 크기
alloc - 메모리 블록이 할당되었는지 여부를 나타낸다. 보통 불리언 값 0또는 1으로 사용된다.
1은 할당된 상태, 0은 미할당 상태
두 값을 비트 OR 연산으로 결합하면 두 값을 하나의 정수로 조합할 수 있다.
GET 매크로는 인자 p가 참조하는 워드를 읽어서 리턴한다.
캐스팅이 중요하다, (void*) 포인터이며, 직접적으로 역참조할 수 없다.
PUT 매크로는 인자 p가 가리키는 워드에 val을 저장한다.
GET_SIZE와 GET_ALLOC 매크로는 각각 주소 p에 있는 헤더 또는 풋터의 size와 할당 비트를 리턴한다.
블록 포인터 bp가 주어지면, HDRP와 FTRP 매크로는 각각 블록의 헤더와 풋터를 가리키는 포인터를 리턴한다.
NEXT_BLKP와 PREV_BLKP 매크로는 다음과 이전 블록의 블록 포인터를 각각 리턴
초기 가용 리스트 만들기
mm_malloc 이나 mm_free를 호출하기 전에 어플리케이션은 mm_init 함수를 호출해서 힙을 초기화해야 한다.
메모리 시스템에서 4워드를 가져와서 빈 가용 리스트를 만들 수 있도록 이들을 초기화한다.
그 후 extend_heap 함수를 호출해서 CHUNKSIZE 바이트로 확장하고 초기 가용 블록을 생성한다.
extend_heap 함수는 두 가지 다른 경우에 호출
1. 힙이 초기화 될대, mm_malloc 이 적당한 맞춤 fit을 찾짖 못했을 때
정렬을 유지하기 위해서 요청한 크기를 인접 2워드의 배수(8바이트)로 반올림하며
그 후에 메모리 시스템으로부터 추갖적인 힙 공간을 요청한다.
힙은 더블 워드 경ㄱ{에서 시작하고, extend_heap으로 가는 모든 호출은 그 크기가 더블 워드의 배수인 블록을 리턴한다.
mem_sbrk로의 모든 호출은 그에필로그 블록의 헤더와 곧 이어서 더블 워드 ㅓㅈㅇ렬된 메모리 블록을 리턴한다.
이 헤더는 새 가용 블록의 헤더가 되고
이 블록의 마지막 워드는 새 에필로그 블록 헤더가 된다. 마지막으로 이전 힙이 가용 블록으로 긑났다면,
두 개의 가용 블록을 통합하기 위해 coalesce 함수를 호출하고 통합된 블록의 블록 포인터를 리턴한다.
블록 반환과 연결
응용은 이전에 할당한 블록을 mm_free 함수를 호출해서 반환하며
이것은 요청한 블록을 반환하고(bp) 인접 가용 블록들은 경계 태그 연결 기술을 사용해서 통합한다.
coalesce 협조 함수는 가용 리스트 포맷으로 인해 -프롤로그와 에필로그 블록을 항상 할당으로 표시한 - 요청한 블록 bp가 힙의 시작부분 또는 끝 부분에 위치하는 숨겨진 문제가 될 수 있는 경ㄱ{ 조건을 무시할 수 있게 된다.
'이들은 특별 블록 없이는 코드는 더 복잡해지며, 에러가 생길 가능성이 높아지고 더 느려지는데,.
매 반환 요처엥 대해 드물게 발생하는 경계 ㅈ호건들을 항상 체크해야 하기 때문이다.
블록 할당
어플리케이션은 mm_malloc 함수를 호출해서 size 바이트의 메모리 블록을 요청
요청한 블록 크기를 조절해서 헤더와 푸터를 위한 공간을 확보하고, 더블워드 요건을 만족시킨다.
12~13줄 - 최소 16바이트 크기의 블록을 수섵ㅇ
8바이트는 젖ㅇ렬 요건을 만족시키기 위해, 추가적인 8바이트는 헤더와 풋터 오버헤드를 위해 8바이트를 넘는 요청에 대해서 15줄 일반적인 규칙은 오버헤드 바이트를 추가하고, 인접 8의 배수로 반올림하는 것.
할당기가 요청한 크기를 조정 후 적절한 가용 블록을 가용 리스트에서 검색한다. 18줄
만일 맞는 블록을 찾으면 할당기는 요청한 블록을 배치하고, 옵션으로 초과부분을 분할하고 19줄
새롭게 할당한 블록을 리턴한다.
할당기가 맞는 블록을 찾지 못하면 힙을 새로운 가용 블록으로 확장하고 요청한 블록은 이 새 가용 블록에 배치하고, 필요한 경우 블록을 분할하며, 이후에 새롭게 할당한 블록의 포인터를 리턴한다.
댓글