빈 공간 관리

메모리 관리 시스템

프로세스 힙의 페이지를 관리하는 malloc 라이브러리일 수 있고 
혹은 프로세스의 주소 공간의 일부분을 관리하는 운영체제 자체일 수 있다.

빈 공간 관리의 경우 고정 크기의 경우 관리가 쉬움 
→ 고정 크기 단위 리스트를 유지하면서 그 중 첫 번째 항목을 반환하면 됨

가변 크기 빈 공간의 경우 관리가 어려움 
→ malloc, free 처럼 사용자 수준 메모리 할당 라이브러리, 
    세그멘테이션으로 물리 메모리를 관리하는 운영체제에서 발생

→ 빈공간을 다양한 크기의 작은 조각으로 분할되어 결국 단편화 발생
→ 요청된 것보다 크더라도 연속된 영역이 존재하지 않으면 요청 실패

가정

- malloc, free에서 제공하는 것과 같은 기본 인터페이스를 가정

- free()는 포인터만으로 해제하고자 하는 메모리 영역의 크기를 파악해야 함 
  → 크기를 알아내는 것은 나중에 논의

- 이 라이브러리가 관리하는 공간은 역사적으로 힙(heap)으로 불리며, 
  힙의 빈 공간을 관리하는데는 일반적인 링크드리스트가 사용된다. // 가용 리스트를 의미

- 이번 장에서는 외부 단편화 방지에 중점을 둔다.

- 클라이언트에게 할당된 메모리는 다른 위치로 재배치될 수 없다고 가정 
→ malloc으로 할당 받은 포인터는 free로 반환할 때까지 
  프로그램이 소유하게 되고 라이브러리에 의해 다른 위치로 옮겨질 수 없다.

- 외부 단편화 해결 방법인 빈 공간 압축도 사용 불가능하다고 가정

저수준 기법들

대부분 할당기에서 사용되는 일반적인 기법에 대해 논의 
1. 분할과 병합 
2. 할당된 영역의 크기를 빠르고 상대적으로 쉽게 파악할 수 있는 방법을 설명 
3. 빈 공간과 사용 중인 공간을 추적하기 위해 빈 공간 내에 간단한 리스트를 구현하는 방법

분할과 병합

요청이 특정 빈 청크의 크기보다 작은 경우 분할한다.
메모리 청크가 반환될 때, 빈 공간들을 병합한다.

분할

빈 공간 리스트는 힙에 있는 빈 공간들의 집합이다.

-> 빈 공간 리스트에는 두 개의 원소가 존재(0 ~ 10, 20 ~ 30)
10 바이트를 초과하는 모든 요청은 실패하여 NULL 반환
10 바이트에 대한 요청은 하나의 빈 청크를 사용하여 쉽게 충족 

 

Ex) 메모리를 1바이트만 요청했다고 가정 
빈 청크를 찾은 후, 이를 둘로 분할한다. 
둘로 나눠진 청크 중 첫 번째 청크는 호출자에게 반환되고,두 번째 청크는 리스트에 남게 됨

-> malloc은 주소 20을 반환하고, 최종 빈 리스트는 위와 같다.

병합

Ex) 주소 10에 대하여 힙의 중간에 존재한느 공간을 반환하는 경우
빈 공간을 다시 리스트에 추가한다.

-> 이 경우 10바이트 청크 3개가 있는 것이므로, 20바이트 요청이 들어오면 할당 실패로 NULL 반환

해제된 빈 공간의 인접한 청크가 있는 경우, 그들을 하나의 더 큰 빈 청크로 병합한다.

할당된 공간의 크기 파악

free() 함수에 포인터만 전달되므로, 해제할 메모리 크기를 포인터만 가지고 알 수 없음
대부분의 할당기는 추가 정보를 헤더 블록에 저장하여 이를 해결 

 

위 예시에서는 ptr이 가리키는 크기 20바이트의 할당된 블럭을 검토하고 있음 
사용자는 malloc()을 호출하고 그 결과를 ptr에 저장 했다고 가정 

- 헤더는 할당된 공간의 크기를 저장해야 함
- 해제 속도 향상을 위해 추가 포인터, 부가적인 무결성 검사를 제공하기 위한 
  매직 넘버 및 기타 정보를 저장해야 함 

// 할당 영역의 크기와 매직 넘버를 저장하는 간단한 헤더 
typedef struct __header_t {
    int size;
    int magic;
} header_t;

 

/*
    20.2 예시에서는 사용자가 free(ptr)을 호출하면 라이브러리는 
    헤더의 시작 위치를 파악하기 위한 간단한 포인터 연산을 수행
*/
void free(void *ptr) {
    header_t *hptr = (void *)ptr - sizeof(header_t);
    ...
}

헤더가 가리키는 포인터를 얻어 내면, 라이브러리는 매직 넘버가 기대하는 값과 일치하는지 비교하여 
안정성 검사를 실시한다.

그리고 새로 해제된 영역의 크기를 간단한 수학을 통해 계산한다.

→ 빈 영역의 크기 = 헤더 크기 + 사용자에게 할당된 영역의 크기 

** N 바이트 청크를 요청하면 N 바이트 + 헤더 크기 청크를 탐색

빈 공간 리스트 내장

보통 새로운 노드를 위한 공간이 필요할 때 malloc()를 호출한다. 
→ 메모리 할당 라이브러리 루틴에서는 이것이 불가능, 빈 공간 내에 리스트를 구축 

4096바이트 크기의 메모리 청크가 있다고 하자. 즉, 힙의 크기는 4KB이다. 
이를 빈 공간 리스트로 관리하기 위해서 먼저 리스트를 초기화 해야 함 

처음에 리스트는 4096 길이의 항목 하나를 가지고 있다.

typedef struct __node_t {
    int size;
    struct __node_t *next;
} node_t;

// mmap()이 빈 공간의 청크에 대한 포인터를 반환 
node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE,
                                        MAP_ANON|MAP_PRIVATE, -1, 0);
head->size = 4096 - sizeof(node_t);
head->next = NULL;

힙은 시스템 콜 mmap()을 호출하여 얻어진 영역에 구축된다고 가정
** 이 코드 실행 후 리스트는 크기 4088의 항목 하나만 가지게 됨
     → 8바이트는 헤더로 사용됨 
Ex) 100 바이트 메모리 청크 요청이 들어온 경우

1. 라이브러리는 리스트에서 100byte + 8 byte 크기를 저장할 수 있는 청크를 찾는다.
2. 빈 청크 중 108byte를 할당하고 할당 영역을 가리키는 포인터(ptr)를 반환한다.
3. 나중에 free에서 사용할 수 있도록 할당된 공간 직언 8바이트에 헤더 정보를 넣는다. 
4. 남은 빈 노드를 3980 바이트로 축소한다.

100바이트씩 할당된 3개의 공간이 존재하는 힙을 살펴본다.

→ 힙 시작 부분 324바이트가 할당된 상태 
3개의 헤더와 호출 프로그램에 의해 사용 중인 3개의 100바이트 영역 존재
빈 공간 리스트는 head가 가리키는 하나의 노드로 구성 (3764 바이트로 축소된 모습)

Ex) free(16500) 호출 - 할당 영역 중 가운데 청크를 반환 

16500은 메모리 영역의 시작 주소(16384), 이전 메모리 청크의 크기(108) 
해제되는 청크의 헤더 8바이트를 더해서 나온 값, 이 값은 sptr이 나타냄

 

** 라이브러리는 신속히 빈 공간 크기를 파악하고, 빈 청크를 빈 공간 리스트에 삽입
   -> 빈 공간 리스트에는 2개의 청크가 존재, 단편화 발생

 

이후 나머지 2개의 사용 중인 청크가 해제 됨 
→ 병합이 없다면 작은 단편으로 이뤄진 빈 공간 리스트가 됨 
** 빈 공간 리스트를 순회하면서 인접한 청크를 병합하면 된다.

힙의 확장

힙 공간이 부족한 경우 어떻게 할 것인가 ??
→ 실패를 반환하면 됨 

대부분의 할당기는 적은 크기의 힙으로 시작하여 모두 소진하면 운영체제로부터 더 많은 메모리 요청
할당기는 힙을 확장하기 위해 특정 시스템 콜을 호출한다.( UNIX - sbrk 호출 )
→ 확장된 영역에서 새로운 청크를 할당 
sbrk 요청을 수행하기 위해 운영체제는 빈 물리 페이지를 찾아 요청 프로세스의 주소 공간에 매핑한 후 
새로운 힙의 마지막 주소를 반환한다. ( 더 큰 힙을 사용 할 수 있음 )

최적 적합(Best fit)

빈 공간 리스트를 검색하여, 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾는다.
그 후, 후보자 그룹 중에서 가장 작은 크기의 청크를 반환 // 최적 청크 반환 

- 공간 낭비를 줄이려고 노력
- 빈 블록 전체를 검색해야 하기 때문에 성능 저하 초래

최악 적합(Worst fit)

가장 큰 빈 청크를 찾아 요청된 크기 만큼만 반환하고, 남은 부분은 빈 공간 리스트에 계속 유지한다.
최악 적합은 최적 적합 방식에서 발생할 수 있는 수 많은 작은 청크 대신, 커다란 빈 청크를 남기려고 시도

- 빈 공간 전체를 탐색해야 하므로 높은 비용을 지불해야 함
- 엄청난 단편화가 발생하여 오버헤드도 큼

최초 적합(First Fit)

간단하게 요청보다 큰 첫 번째 블록을 찾아서 요청만큼 반환한다.
- 탐색 속도가 빠르다는 것이 장점 (전체를 탐색할 필요가 없기 때문)
- 리스트 시작에 크기가 작은 객체가 많이 생길 수 있음

** 할당기가 빈 공간 리스트의 순서를 관리하는 방법이 쟁점
한 가지 방법은 주소-기반 정렬을 사용하는 것 
→ 리스트를 주소로 정렬하면, 병합을 쉽게하고, 단편화를 감소시킴

다음 적합(Next Fit)

마지막으로 찾았던 원소를 가리키는 추가의 포인터를 유지
빈 공간 탐색을 리스트 전체에 더 균등하게 분산시키는 것 

- 리스트 첫 부분에만 단편이 집중적으로 발생하는 것을 방지
- 전체 탐색을 하지 않기 때문에, 최초 적합의 성능과 비슷함

버디 할당

빈 메모리는 처음에 개념적으로 크기 2^N인 하나의 큰 공간으로 생각됨
메모리 요청이 발생하면, 요청을 충족시키기에 충분한 공간이 발견될 때까지 빈 공간을 2개로 계속 분할 

 

→ 7KB를 할당하려면 이에 맞는 8KB를 찾을 때까지 분할 
** 버디 할당은 2의 거듭제곱 크기 만큼의 블럭만 할당할 수 있어 내부 단편화가 발생할 수 있다.
블럭 반환시, 버디가 비어 있는지 확인하고 비어 있다면 이 두 블럭을 다시 병합
→ 다음 블록도 비어 있다면 계속 올라가며 병합 

**
버디 할당이 잘 작동하는 이뉴는 특정 블럭의 버디를 결정하는 것이 쉽다는데 있다. 
→ 각 버디쌍의 주소는 한 비트만 다름 // 어느 위치의 비트가 다른지는 버디트리 수준에 따라 다름