Operating System: 10. 빈 공간 관리

빈 공간 관리의 문제점

관리하는 공간이 고정 크기의 단위로 나누어져 있는 경우 빈 공간 관리는 쉬울 수 있다(고정 크기의 리스트를 유지하면 된다). 다만, 다음과 같이 메모리 공간이 가변 크기인 경우 경우 외부 단편화가 존재한다.

• 1. malloc()과 free()같은 사용자의 가변적인 크기의 요청이 있는 경우
• 2. 세그먼테이션으로 물리 메모리를 관리하는 경우

  즉, 빈 공간의 전체 크기가 20byte가 10byte, 10byte로 
  나누어져 잇있을 때, 15byte 요청은 실패한다.
  이를 어떻게 해결할 수 있을까?
  

압축

• 단편화해결에 유용하게 사용되는 압축을 사용할 수 있지 않을까?
• 하지만 압축을 위해 할당된 메모리를 다른 위치로 재배치 할 수 없다. C프로그램에서 메모리 청크를 가리키는 포인터를 전달해도 그 영역을 가리키는 포인터를 모두 알아내는 것은 어렵다. 지역 변수, 심지어 실행 중에 레지스터에도 저장되어 있을 수 있기 때문이다.

저수준 기법

1. 분할과 병합

1. 빈 공간의 전체 크기가 20이고, 10, 10으로 나누어져 있을 때 10보다 큰 요청에 대해선 실패한다.
2. 크기 1의 요청이 있는 경우 할당기는 분할(spliting)하여 1을 반환한다. 빈 공간은 19이고, 10, 9로 나누어져 있다.
3. free를 호출하여 공간이 반환된 경우 할당기는 병합(coalescing)한다. 반환되는 메모리 청크의 바로 인접한 빈 청크의 주소를 확인하여 병합하게 된다

할당된 공간 크기 파악

공간을 해제할 때 사용자는 라이브러리에게
크기 정보를 전달하지 않는다.
라이브러리는 포인터만으로 메모리 영역의 크기를
파악하는 데 이를 어떻게 할 수 있을까?

• 대부분의 할당기는 추가 정보를 헤더(header) 블록에 저장한다. 헤더 블럭은 메모리에 유지되며 해제된 청크 바로 직전에 위치한다.

헤더 구성 요소

1. 할당된 공간의 크기
2. 해제 속도를 향상시키기 위한 추가 포인터
3. 무결성 검사를 제공하기 위한 매직넘버

작동 방식

1. 사용자가 free(ptr)을 호출하면 라이브러리는 헤더의 시작 위치를 파악하기 위한 간단한 연산을 한다.


   현재 포인터 - sizeof(header_t)
   

2. 라이브러리는 매직 넘버가 기대한느 값과 일치하는지 비교하여 안정성 검사(sanity check)를 한다.


   assert(nptr->maigc == 1234567)
   

3. 새로 해제된 영역의 크기를 계산한다.(헤더의 크기와 해제된 영역의 크기를 더함) 즉, 사용자가 N 바이트 메모리 청크를 요청하면 라이브러리는 크기 N의 빈 청크를 찾는 것이 아니라 N + 헤더 크기를 만족하는 청크를 찾는다.


기본 전략

이상적인 할당기는 속도가 빠르고 단편화를 최소로 한다.
어느 특정 전략도 잘 맞지 않는 입력을 만나면 
성능이 매우 좋지 않을 수 있다.
최선의 정책이 아닌 기본 전략에 대해 알아보자.

1. 최적 적합(Best Fit)

• 빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾는다. 그 후 후보자 그룹 중에서 가장 작은 크기의 청크를 반환한다. 이를 최적 청크라고 불린다.
• 정교하지 않은 구현은 해당 빈 블럭을 찾기 위해 항상 전체를 검색해야 하기에 성능 저하를 초래한다.

2. 최악 적합(Worst Fit)

• 가장 큰 빈 청크를 찾아 요청된 크기만큼만 반환하고 남는 부분은 빈 공간 리스트에 계속 유지한다.
• 빈 블럭을 찾기 위해 항상 전체를 검색해야 하므로 성능 저하가 있고, 대부분의 연구에서 엄청난 단편화가 발생하여 오버헤드가 크다고 한다.

3. 최소 적합(First Fit)

• 요청보다 큰 첫 번째 블럭을 찾아서 반환한다.
• 원하는 공간을 찾기 위해 항상 전체를 탐색할 필요가 없기에 빠르다.
• 그러나, 리스트의 시작에 크기가 작은 객체가 많이 생길 수 있어 빈 공간 리스트의 순서를 관리하는 것이 중요하다.
  • 주소-기반 정렬(address-based ordering)을 사용하면 리스트를 주소로 정렬하여 변환을 쉽게 하고, 단편화를 감소시킨다.

4. 다음 적합(Next Fit)

• 항상 리스트를 처음부터 검색하는 대신 마지막으로 찾았던 원소를 가리키는포인터를 추가한다.
• 이는 빈 공간 탐색을 리스트 전체에 균등하게 분산시켜 리스트의 첫 부분에만 단편이 집중적으로 발생하는 것을 방지한다.
• 전체 탐색을 하지 않기에 최초 적합과 성능이 비슷하다.

향상된 전략

1. 개별 리스트(segregated list)

• 응용프로그램이 한두 개 자주 요청하는 크기가 있다면, 그 크기의 객체를 관리하기 위한 별도의 리스트를 유지하는 것이다.
• 특정 크기의 메모리 청크를 유지하여 단편화 가능성을 상당히 줄이고, 요청된 크기의 청크만이 존재하기에 복잡한 리스트 검색이 필요하지 않다. 따라서 할당과 해제 요청을 신속하게 처리할 수 있다.
• 하지만, 지정된 크기의 메모리 풀과 일반적인 풀에 얼마만큼의 메모리를 할당해야 하는지에 대한 문제가 있다.

2. 슬랩 할당기(slab allocator)

• 커널이 부팅될 때 여러 객체 캐시(object cache)를 할당한다. 커널 객체란 락, 파일 시스템 아이노드 등 자주 요청되는 자료구조를 말한다. 객체 캐시는 지정된 크기와 객체들로 구성된 빈 공간 리스트이다.
• 기존에 할당된 캐시 공간이 부족하면 상위 메모리 할당기에 추가 슬랩을 요청한다. 요청된 전체 크기는 페이지 크기의 정수배이다. 만약 슬랩 내 객체들에 대한 참조 횟수가 0이 되면 상위 메모리는 이 슬랩을 회수할 수 있다. 더 많은 메로리가 필요할 때 회수하는 식이다.
• 슬랩 할당 방식은 빈 객체들을 사전에 초기화된 상태로 유지한다는 점에서 개별 리스트 방식보다 우수하다. 자료 구조의 초기화와 반납에 많은 시간이 소요되기 때문에 오버헤드를 현저히 감소시킨다.

3. 버디 할당기(biniary buddy allocator)

• 빈 메모리를 개념적으로 크기 2의 거듭제곱인 하나의 큰 공간으로 생각한다. 메모리 요청이 발생하면, 분할하면 공간이 너무 작아져서 요청을 만족할 수 없을 때까지 빈 공간을 2개로 계속 분할한다.
• 아래는 64KB빈 공간에서 7KB블럭을 할당하는 예시이다.

• 내부 단편화가 발생하지만, 버디 할당기의 장점은 블럭이 해제될 때 있다.
  • 1. 8KB블럭이 해제되면 8KB블럭이 비어 있는지 확인한다.
  • 2. 비어 있다면 두 블럭을 병합하여 16KB블럭으로 만든다.
  • 3. 할당기는 다음 16KB의 버디가 비어있는지 확인한다.
  • 4. 비어 있다면 이 블럭을 다시 합병한다.
• 이 재귀 합병 과정은 전체 빈 공간이 복원되거나 버디가 사용중일 때까지 계속 반복된다.