08: 05 입실
malloc 암시적 리스트 기반 원리 확실히 이해하고 구현하기
malloc lab
매크로 확실히 이해하기
#define WSIZE 4
워드를 4바이트로 설정한다.
#define DSIZE 8
더블워드를 8바이트로 설정한다.
#define CHUNKSIZE (1 << 12)
청크 사이즈(힙 영역 확장 기본 단위)를 2^12 = 4096으로 설정한다.
메모리 할당 최소 사이즈이며 기본 단위가 된다.
(1 << n)은 2의 n제곱을 구하는 빠른 연산이다.
1 << 12는 비트연산자(왼쪽 시프트)이다.
1은 이진수로 000...001이다. 이 비트를 왼쪽으로 12 옮기는 연산이다.
왼쪽 시프트가 발생할 때마다 원래 값에 2씩 곱해진다.
12번 왼쪽으로 2의 12제곱이 된다.
메모리 블록을 4KB씩 할당하는 게 아님!
메모리 블록을 할당하려면 힙 영역이 확보되어야 하는데,
이때 확보되는 힙 영역의 단위를 4KB씩 한다는 의미
왜 청크 단위로 힙을 확장할까?
메모리 공간을 확장한다는 건 리소스가 투입되는 작업이다.
따라서 일정 크기 단위로 확장을 해서 확장에 따른 리소스 투입을 효율화 하는 것!
#define MAX(x, y) ((x) > (y) ? (x) : (y))
최대값을 찾는 함수 매크로이다.
x와 y 중 큰 값을 반환한다.
매크로 정의할 때는 괄호를 써주는 게 관례
매크로는 치환을 해주는 건데, 치환 시 우선 순위에 따라 예상치 못한 결과 발생할 수도 있음.
그래서 확실하게 괄호를 작성하는 게 안정성을 위해 중요함.
#define PACK(size, alloc) ((size) | (alloc))
size에 할당 여부 비트를 비트 OR연산을 통해 최종적인 헤더 값을 리턴한다.
size와 alloc을 비트 or 연산을 한다.
alloc은 할당 여부를 나타내는 플래그이다. (0 or 1)
블록의 사이즈를 계산할 때 ~0x7 비트 연산을 통해 하위 3비트를 000으로 만들었음.
이때 alloc이 0이면(미할당 상태) 블록 사이즈 비트의 MLB는 0이 되지만,
alloc이 1이면(할당 상태) 블록 사이트 비트의 MLB는 1이 된다.
#define GET(p) (*(unsigned int *)(p))
포인터 p의 참조 주소를 통해 p를 역참조한다.
p는 void 포인터이다.(블록 포인터)
따라서 먼저 p를 양수 타입으로 캐스팅한 후(메모리 주소로 캐스팅),
그 후 해당 주소를 역참조해서 값을 가지고 온다.
이렇게 하면 p 메모리 주소의 값을 가져올 수 있다.
#define PUT(p, val) (*(unsigned int *)(p) = (val))
포인터 p의 참조 주소를 통해 p에 특정 값을 할당한다.
p는 void 포인터이다.(블록 포인터)
따라서 먼저 p를 양수 타입으로 캐스팅한 후(메모리 주소로 캐스팅),
그후 해당 주소를 포인팅하고, 포인팅된 메모리에 val을 할당한다.
#define GET_SIZE(p) (GET(p) & ~0x7)
헤더 값에서 사이즈를 리턴하는 함수.
p는 void 포인터이다.(블록 포인터)
GET(p)는 p를 역참조한다.
이 값은 비트 AND 연산을 통해 하위 3비트를 000으로 바꾼다.
(가장 가까운 8의 배수로 내림)
즉, 기존 헤더에는 사이즈에 할당된 경우 1이 추가되어 있는데,
이 값을 무조건 000으로 바꿔서 할당 여부와 무관한 사이즈를 반환하는 것
#define GET_ALLOC(p) (GET(p) & 0x1)
헤더 값에서 할당 여부를 리턴하는 함수.
p는 void 포인터이다.(블록 포인터)
GET_SIZE(p)가 할당 여부를 제외한 사이즈만 가져왔다면,
이 함수는 반대로 할당 여부만 가지고 온다.
즉, & 0x1를 통해 헤더 비트에서 나머지 모든 비트는 0으로 바꾸고 LSB만 살려서 온다.
#define HDRP(bp) ((char *)(bp)-WSIZE)
HDRP = Header Pointer
해당 블록의 헤더 주소를 반환한다.
-
블록 포인터를 char타입으로 캐스팅한다.
이때 주소값이 손실되는 게 아니라 주소값에 위치한 데이터를 해석하는 방식이 char 타입으로 바뀌는 것이다.
이렇게 캐스팅을 해야 WSIZE를 빼면 산술적으로 8이 빠지는 게 아니라,
char(1바이트) 8인 8바이트가 빠진다.
즉, char로 캐스팅하는 이유는 바이트 단위로 정의된 WSIZE로 포인터 연산을 하기 위해서이다. -
캐스팅 값에서 1워드를 뺀 후 헤더 포인터를 반환한다.
(페이로드 시작점인 블록 포인터에서 헤더 크기인 1워드를 빼면 헤더의 위치가 반환됨.)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
FTRP = Footer Pointer
해당 블록의 푸터 주소를 반환한다.
-
블록 포인터를 char*타입으로 캐스팅한다.
(이유는 HDRP와 같음) -
헤더접근해서 블록의 사이즈를 포인터 연산으로 더한다.
이렇게 하면 원래 가리키고 싶었던 푸터 주소에서 더블워드만큼 앞질러 가게 된다.
(다음 블록의 페이로드를 가리키게 됨.) -
더블워드 사이즈를 뺀다.
이 결과 해당 블록의 푸터를 가리키게 된다.
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))
다음 블록 포인터(페이로드)를 가리킨다.
GET_SIZE(((char *)(bp)-WSIZE)))는 해당 블록의 헤더 포인터를 얻어서 해당 블록 크기 반환- 해당 블록 페이로드 포인터에 블록 크기를 더하면 다음 블록의 페이로드 주소를 가리킨다.
#define PREV_BLKP(bp) ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE)))
이전 블록의 포인터(페이로드)를 가리킨다.
GET_SIZE(((char *)(bp)-DSIZE)))는 이전 블록의 푸터에서 이전 블록 크기를 반환- 해당 블록 페이로드 포인터에 이전 블록 크기를 빼서 이전 블록 페이로드 주소를 가리킨다.
프롤로그와 에필로그 블록이 왜 필요하나?
힙에 데이터 블록 추가 시 앞, 뒤 경계가 없는 것처럼
프롤로그, 에필로그를 각각 더미 블록으로 만들어서 블록 추가 시
앞, 뒤 블록이 경계가 아닌 다른 블록이 있는 것과 같은 효과를 줌.
맨 앞 미사용 블록은 왜 필요하나?
힙 영역의 경계를 나타냄.
mm_inti()
초기 힙 영역을 확보하고, 패딩 블록, 프롤로그 블록, 에필로그 블록을 생성한다.
sbrk를 호출하기 전에 brk를 데이터 세그먼트 끝을 가리키고 있음.
이때, sbkr를 호출해서 brk를 지정해서 힙 영역을 확보하는 것
아래 코드는 다음과 같이 동작한다.
mem_sbrk를 호출해서 데이터 세그먼트 끝에 있던 brk를 4워드 위로 올림.
이렇게 했을 때 brk는 힙의 끝을 포인팅함.
그리고 반환값은 확장된 힙 영역의 시작 주소를 반환함.
(즉, 이전 브레이크 포인터의 위치)
여기서 힙의 마지막이란 마지막 블록의 끝임.
이때 마지막 블록의 끝은 사실상 마지막 블록의 페이로드 지점이지만,
마지막 블록(에필로그)은 헤더만 있기 때문에
페이로드 시작점이 전체적인 힙의 마지막 경계를 포인팅 하는 것.
만약 힙 영역 확보에 실패하면 -1을 반환한다.
힙 영역 확보에 성공했으면 확보된 영역에 초기 블록을 할당한다.
이 부분은 처음 할당한 4워드 다음부터 1워드씩 할당한다.
초기 4워드를 버리는 이유는 정렬을 위해 8의 배수로 정렬하기 위해서이다.
-
1워드째 블록에는 정렬을 위한 패딩을 추가한다.
(혹시 이 이유가 에필로그 블록은 푸터가 없어서 초기 힙 확보 시 정렬이 안 맞으니까
정렬을 맞추기 위한 용도로도 쓰이나?) -
2워드째 블록은 프롤로그 블록의 헤더이다.
기본 블록 사이즈 DSIZE(=헤더+푸터)에 할당 비트 1을 결합해서 헤더 값을 설정한다. -
3워드째 블록은 프롤로그 블록의 푸터이다.
기본 블록 사이즈 DSIZE(=헤더+푸터)에 할당 비트 1을 결합해서 푸터 값을 설정한다. -
4워드째 블록을 에필로그 블록의 헤더이다.(에필로그 블록은 푸터가 없다.)
힙의 끝을 나타내는 특수한 블록으로, 사이즈를 0으로 하고 할당 비트 1을 결합해서 헤더 값을 설정한다.
현재 힙 리스트 포인터는 현재는 힙이 초기화된 끝,
즉 힙의 완전 시작점을 가리키고 있다.
이 힙 포인터를 2워드 앞으로 옮겨서 프롤로그의 푸터, 에필로그의 헤더로 위치시켜
새로운 블록을 삽입할 준비를 한다.
이후 청크사이즈를 워드 단위로 환산해서 brk를 확장한다.
int mm_init(void)
{
/* Create the initial empty heap */
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;
}
heap_list += (2 * WSIZE);부분이 init 함수가 끝나면 스택에서 지워지는데
왜 있지? 라는 생각을 했는데 이건 포인터 전역 변수 였음.
그래서 heap_list는 새로운 블록이 할당될 자리를 가리키는 거였다!
extend_heap()
brk 포인터로 힙 영역을 확장한다. 이때 확장 단위는 청크사이즈이다.
매개변수로 워드가 들어온다.(1워드 = 4바이트, 매크로 상수로 정의된 상태)
워드 단위의 사이즈를 메모리 주소 단위로 환산해야 한다.
만약 사이즈가 홀수이면 words에 1워드를 더해서 WSIZE(비트)를 곱해서 사이즈를 변환하고,
짝수이면 그냥 그대로 words에 WSIZE(비트)를 곱해서 사이즈를 변환한다.
mem_sbrk로 void* 포인터 타입으로 반환받아 힙 확보 여부를 체크한다.
이걸 long타입으로 바꿔서 -1과 비교해서 할당 여부를 체크한다.
코드 통일성을 위해 long타입으로 캐스팅 하지 않고,
-1을(void *)-1로 캐스팅 해서 비교함.
이 과정에서 할당 연산자 우선 순위에 대해서 공부하게 되었음.
힙영역이 확장되면 확장된 부분은 하나의 메모리 블록이 된다.
다음 힙 확장 직전의 블록(원래 에필로그 블록)할당 여부를 할당 가능(0)으로 바꾸고,
데이터 크기도 size만큼 부여한다.
블록 끝에 푸터 자리에 사이트와 할당 여부를 0으로 바꿔서 푸터 필드를 생성한다.
그리고 다음 블록의 헤더 위치(당장은 어떤 블록도 없지만)에
데이터 사이즈0, 할당 불가(1)로 특수하게 세팅해서 에필로그 블록 헤더를 생성한다.
마지막으로 coalesce를 통해 빈 블록을 병합한다.
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((bp = mem_sbrk(size)) == (void *)-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);
}연산자 우선순위로 인해 오류가 발생함!
if (bp = mem_sbrk(size) == (void *)-1)
이 코드에서 mem_sbrk호출 전에 조건식을 먼저 평가하고 그 다음 그 결과를 bp에 할당함..
이때는if ((bp = mem_sbrk(size)) == (void *)-1)이렇게 괄호를 추가해서 호출을 먼저 해야 함.
할당 연산자가 먼저 평가되는데, 이떄 우항에 비교 연산이 있으므로, 또 그게 먼저 평가됨.
그래서 bp에는 두 값이 같은지 다른지를 0, 1로 반환하고 그 값이 bp에 저장되어서 오류가 발생하는 것.
coalesce()
bp를 중심으로 가용 블록을 병합한다.
size는 우선 현재 블록의 사이즈를 할당한다.
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)
{
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);
}
return bp;
}케이스 1. 전 할당 불가 ❌, 후 할당 불가 ❌
별도 병합 없이 그냥 bp를 반환하면 됨
케이스 2. 전 할당 가능 ❌, 후 할당 불가 ✅
1. 현재 블록 사이즈에 다음 블록의 사이즈를 더함.
2. 현재 블록의 헤더를 새로운 사이즈와 할당 가능(0)을 결합해서 값 할당
3. 현재 블록의 푸터를 새로운 사이즈와 할당 가능(0)을 결합해서 값 할당
(bp값은 별도 조정 없이 바로 반환)
케이스 3. 전 할당 불가 ✅, 후 할당 가능 ❌
1. 현재 블록 사이즈에 사이즈를 이전 블록의 사이즈를 더함.
2. 현재 블록 푸터에 새로운 사이즈와 할당 가능(0)을 결합해서 값 할당
3. 이전 블록 bp를 불러와서, 이전 블록의 헤더에 새로운 사이즈와 할당 가능(0)을 결합해서 값 할당
4. bp를 이전 블록 위치로 해서 반환(병합된 블록의 페이로드)
케이스 4. 전 할당 가능 ✅, 후 할당 가능 ✅
1. 현재 블록 사이즈에 이전 블록 사이즈(이전 블록 헤더 접근), 다음 블록 사이즈(다음 블록 푸터 접근)를 더함.
2. 이전 블록 헤더에 새로운 사이즈와 할당 가능(0)을 결합해서 값 할당
3. 다음 블록 푸터에 새로운 사이즈와 할당 가능(0)을 결합해서 값 할당
4. bp를 이전 블록 위치로 해서 반환(병합된 블록의 페이로드)
비트가 1이면 이미 할당되었다는 뜻이다.
헷갈리며 안 됨. 0인 경우, 즉 Falsy일 경우가 할당 가능한 상태다.
place()
블록 포인터 주소를 받아서 asize 사이즈를 블록에 할당하고 할당 비트(1)처리 한다.
(확보된 데이터 블록에 실제로 데이터 사이즈를 반영해서 데이터 블록을 사용 처리하는 함수)
static void place(void *bp, size_t allocated_size)
{
size_t current_size = GET_SIZE(HDRP(bp));
if ((current_size - allocated_size) >= (2 * DSIZE))
{
PUT(HDRP(bp), PACK(allocated_size, 1));
PUT(FTRP(bp), PACK(allocated_size, 1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(current_size - allocated_size, 0));
PUT(FTRP(bp), PACK(current_size - allocated_size, 0));
}
else
{
PUT(HDRP(bp), PACK(current_size, 1));
PUT(FTRP(bp), PACK(current_size, 1));
}
}케이스 1. 현재 블록 사이즈에서 할당할 사이즈를 뺐을 때(즉, 남는 부분)가 더블워드 2배 이상일 때
(남는 블록이 최소 블록 크기와 같거나 클 때, 블록을 분할해야 함.)
현재 코드에서는 최소 크기를 더블워드의 2배로 잡았음.
왜냐면 정렬 기준이 더블 워드기 때문에
그 이하로 쪼개는 건 의미가 없음.
1. 헤더에 할당 사이즈와 할당 비트 1을 결합해서 저장
2. 푸터에 할당 사이즈와 할당 비트 1을 결합해서 저장
케이스 2. 남은 블록을 분할할 필요가 없을 때
해당 블록에 헤더와 푸터에 할당 비트를 1로 바꾸면 됨.
1. 헤더 값을 기존 블록 사이즈에 할당 비트 1을 결합해서 설정
2. 푸터 값을 기존 블록 사이즈에 할당 비트 1을 결합해서 설정
3. 다음 블록이 위치할 수 있는 주소(페이로드)로 bp이동
4. 해당 지점의 헤더에 남은 블록의 크기만큼에 비할당 비트 0을 결합해서 설정
5. 해당 지점의 푸터에 남은 블록의 크기만큼에 비할당 비트 0을 결합해서 설정
find_fit()
메모리 할당 알고리즘에 따라 할당할 블록을 찾는다.
우선은 최초 적합 알고리즘부터 구현
static void *find_fit(size_t allocated_size)
{
void *bp;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
{
if (!GET_ALLOC(HDRP(bp)) && (allocated_size <= GET_SIZE(HDRP(bp))))
{
return bp;
}
}
return NULL;
}-
heap_listp를 데이터 블록을 할당할 수 있는 위치이다.(블록의 페이로드 위치)
반복문은 계속해서 다음 블록의 페이로드를 탐색한다. -
할당 가능한 블록 && 해당 블록의 사이즈가 할당하려는 사이즈 이상이면 해당 bp를 반환
-
for문이 끝났는지 빈 블록이 없으면 NULL을 반환(상위 함수에서 힙 영역을 늘릴 예정)
mm_malloc()
요청된 사이즈만큼의 메모리 블록을 가용블록으로 확보하고 해당 페이로드 주소값을 리턴하는 함수
void *mm_malloc(size_t size)
{
size_t allocated_size;
size_t extendsize;
char *bp;
if (size == 0)
return NULL;
if (size <= DSIZE)
allocated_size = 2 * DSIZE;
else
allocated_size = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
if ((bp = find_fit(allocated_size)) != NULL)
{
place(bp, allocated_size);
return bp;
}
extendsize = MAX(allocated_size, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
return NULL;
place(bp, allocated_size);
return bp;
}- 요청 사이즈가 0이면 NULL을 반환한다.
2-1. 요청 사이즈가 더블 워드보다 적으면 요청 사이즈를 2 더블 워드로 재할당한다.
(경계에 맞춰 최소 블록 크기를 더블 워드로 설정함.)
(이유는 어떤 블록이든 1이상의 크기가 있다면 메타데이터가 최소 더블 워드를 차지함.)
2-2. 요청 사이즈가 더블 워드보다 크면
사이즈에 메타데이터(DSIZE)를 추가, 그리고 8배수 맞추기 위해 (DSIZE-1)을 추가
그 다음 나누기 /DSIZE를 하면 size_t가 int형이기 때문에 몫만 남음.
남은 몫에 DSIZE를 곱하면 반올린된 값이 나옴.
DSIZE-7을 하는 이유는 어차피 사이즈와 DSIZE-1을 더한 값을
DSIZE로 나눴을 때 8을 넘지 않으면 영향을 미치지 않음.
-
find_fit 함수를 통해 해당 사이즈를 할당할 블록을 찾음.
찾은 수 place함수를 통해 해당 위치에 해당 사이즈의 메모리 블록을 할당 가능 상태로 만듦.
해당 블록 포인터 반환. -
만약 할당할 블록을 찾지 못했다면 힙 영역을 확장하고 새로운 메모리 블록을 생성함.
할당해야 할 사이즈와 청크 사이즈 중에 큰 값을 확장 사이즈로 설정
(힙 영역은 청크 사이즈 단위로 확장함)
힙을 확장한 값이 NULL이면(즉, 힙 영역 확장 불가) NULL을 반환
그렇지 않으면 place 함수로 새롭게 생성된 메모리 블록에 해당 사이즈를 할당하고, 빈 공간 적절히 처리
해당 블록 포인터 반환.
mm_free()
메모리 블록의 할당 비트를 할당 가능(0)으로 바꾼다.
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);
}해당 클록의 사이즈를 할당한다.
해당 블록의 헤더의 값을 사이즈와 할당 가능 비트(0)을 연산한 후 설정한다.
해당 블록의 푸터의 값을 사이즈와 할당 가능 비트(0)을 연산한 후 설정한다.
이제 기본적인 코드는 다 이해함!
할당 과정부터 병합, 해제까지 코드와 진행 원리 자체는 이해했다!
(realloc은 우선 기존 코드 활용)
이제 최적화 시작한다!!
결과 보충 설명
Utilization(이용률): 시스템 지원 이용률. 시스템 리소스 사용 효율성 측정.
Throughput(처리량): 시스템이 작업을 얼마나 빠르게 처리하는지 나타냄.
스터디
페이지 교체 알고리즘
https://www.youtube.com/watch?v=nF26uioM6zU
페이지 교체 시 더티 비트를 고려하는데,
더티 비트가 1이면 오염된(?) 페이지 이므로
디스크 쓰기 작업으로 동기화 시키고 교체,
더티 비트가 0이면 디스크와 현재 페이지의 데이터가 동일하기 때문에
별도 디스크 쓰기 작업 없이 페이지 교체
페이지 참조열
CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
페이지 참조열을 통해 페이지 폴트 횟수를 알 수 있다.
(page reference string)
1. FIFO
가장 먼저 올라온 애부터 페이지 아웃
페이지 참조열을 보고 메모리에 올라온 페이지 중에
가장 먼저 적재된 페이지를 페이지 아웃
적재된 시간을 어떻게 알까?
페이지 테이블에 적재된 시간을 기록한다고 함.
2. 2차 기회(second chance)
큐를 사용함. 페이지를 실제로 큐에서 인, 아웃
입장 순으로 오래된 거 페이지 아웃 시키려고 했을 때,
참조 비트가 1인 경우: CPU가 참조된 적이 있는 페이지
-> 참조 비트 0으로 바꾸고 적재 시간을 현재 시간으로 설정(기회 한 번 더 줌)
참조 비트가 0인 경우: CPU가 참조한 적 없음
-> 더티 비트가 1이면 페이지를 디스크에 기록하고 페이지 교체
-> 더티 비트가 0이면 페이지를 디스크에 기록하지 않고 그냥 페이지 교체.
(더티 비트 사용 예시)
클럭 알고리즘은 2차 기회 알고리즘을 변형한 것. 원형 큐를 사용함.
큐를 아웃하는 대신 포인터를 사용함. 즉 페이지 순서가 보장됨.
추가되는 페이지는 원형 큐 최상단에 추가
3. 최적 페이지 교체
가장 먼 미래에 참조될 페이지를 교체
(근데 알 수가 없음, 그래서 다른 알고리즘 선능 평가 척도로서 쓰이는 이론적인 하한선)
4. LRU(Least Recently Used)
과거를 기준 가장 오래 사용되지 않은 페이지 교체
내부 단편화 추가
메모리 블록의 헤더와 푸터로 일종의 내부 단편화로 본다.
그럼 명시적 해제 리스트 방식은 내부 단편화가 더 심한 거라고 볼 수 있음.
RB Tree는 로직 자체 이해가 너무 어려웠는데,
malloc은 오히려 구현 메커니즘 이해는 (RB Tree보다는) 쉬움!
최적화 하는 과정이 막막하긴 하지만..
최대한 인터넷 안 찾아보고 구현해 보는 것 도전!
