Lucid 
할당기의 블록 구조
헤더: 블록 크기와 블록 할당 여부
데이터: 담아야 할 데이터(payload)
여백: 패딩, 외부 단편화 극복하기 위한 전략의 일부분 혹은 정렬 요구사항 만족하기 위함
하나의 블록은 4바이트/8바이트로 구성하는데, word라고 부른다. 1워드는 4바이트, 더블 워드는 8바이트이다.
첫 층은 블록의 헤더로 블록 크기와 가용 여부를 나타낸다. 가용 여부는 뒤 3비트인데, 블록 크기를 16진수 비트로 만드므로 가용 여부 또한 16진수 비트로 구성해야 비트연산을 통해 하나의 16진수로 만들어낼 수 있기 때문이다.
할당된 블록의 경우 특정 자료가 담긴다.
패딩은 블록 크기를 일정하게 정렬하여 규격화하여 효율을 늘리는데 의의가 있다.
예시: 크기가 2byte인 데이터를 넣어야 한다면, 컴퓨터는 16byte블록을 할당할 것. (2byte(데이터) + 4byte(헤더) + 4byte(풋터) = 10 byte) 이지만 2워드로 맞추어 16byte로 만들기 위해 6byte를 패딩으로 넣는 것이다.
풋터는 연속된 블록의 할당 여부를 판단하고 둘을 합칠 것인지에 대한 판단을 빠르게 하도록 도와준다. 단점으로는 블록 개수가 많아지면 메모리 오버헤드가 매우 커진다는 것이다.
Memory Allocator 구현 - 매크로
// 포인터 조작을 위한 매크로들
#define WSIZE 4 // word와 header, footer사이즈(bytes)
#define DSIZE 8 // 더블 워드의 사이즈(bytes)
#define CHUNKSIZE (1<<12) // 힙 확장 크기(bytes)
#define MAX(x, y) ((x) > (y) ? (x) : (y))
/*크기 및 할당 비트를 통합하여 헤더, 풋터에 저장할 값을 반환*/
#define PACK(size, alloc) ((size) | (alloc))
/*포인터 p의 참조인자를 읽기/쓰기*/
#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)))
포인터 조작 매크로
1. 포인터의 형태
- C언어에서는 1바이트 단위의 크기로 메모리 주소를 표현한다.
char: 1바이트
문자 저장에 용이, 어떤 ASCII든 저장 가능. char에 문자만 저장해야 하는 것은 아님, 작은 크기 정숫값 사용에 쓰이기도 한다. 메모리 블록 크기는 바이트 단위로 표기되어 메모리 블록 나타내는 데 적합. 이 매크로에서는 블록 포인터를 char로 사용한다.
가장 작은 데이터 유형이기 때문에 차후 메모리를 할당한 후 이 영역에 모든 데이터를 저장하는 것으로 사용할 수 있게 되는 것이다. 예로, char형 배열을 할당하여 int데이터를 저장하면 4개의 char형 데이터를 저장하여 int형 데이터 1개를 저장할 수 있는 것이다. int: 4바이트
할당 여부를 나타내는데 적합. 이 매크로에서는 블록 헤더를 unsigned int로 사용한다. unsigned: 양수만, 보통 signed이므로 양수와 음수 모두 포함한다.
2. GET_SIZE와 GET_ALLOC 매크로
#define GET_SIZE(p) (GET(p) & ~0x7) & #define GET_ALLOC(p) (GET(p) & 0x1)
&: 비트단위 AND 연산자,~: 비트 단위 NOT연산자.- 블록 사이즈를 바이트 단위로 생각해보면, 사이즈의 최소 단위가 16바이트(헤더: 4byte, 풋터: 4byte, payload: 추가되므로 최소 사이즈는 16byte이다.)임을 알 수 있다. 이를 이진수로 바꿔보면 맨 처음 세자리는 사용하지 않게 되는데, 여기에 할당 여부를 비트 연산으로 추가하여 헤더로 사용하는 것이다.
p가 가리키는 메모리 위치의 값에서 0x7 비트 마스크를 AND 연산하여 블록 크기를 반환. 0x7비트 마스크의 비트 단위 NOT을 반환한다. 0x7(16진법) = 0000 0111(2진법), 블록 크기가 차지하는 메모리 위치의 비트. 결국 ~0x7는: 1111 1000이다. 블록 헤더에서 블록 크기를 반환한다. 블록 크기는 첫 3바이트에 저장됨.(사실 위 숫자는 0을 생략한 것, 실제는 4byte니 32개 숫자가 있어야 한다)