운영체제 13. 빈공간 관리

운영체제

13. 빈공간 관리

• 빈공간 관리는 관리하고 있는 공간이 고정 크기의 단위로 나누어져 있는 경우 쉽다. 그런 경우 고정 크기 단위의 리스트를 유지하면 된다. 클라이언트가 그 중 하나를 요청하면 첫 번째 항목을 반환하면 된다.
• 빈공간 관리가 더 어렵고 흥미로운 경우는 관리하는 공간이 가변 크기 빈 공간들의 집합으로 구성되어 있는 경우다. 이 경우 malloc()과 free()에서 처럼 사용자 수준 메모리 할당 라이브러리에서 그리고 세그멘테이션으로 물리 메모리를 관리하는 운영체제에서 발생한다. 어느 경우에도 외부 단편화가 존재한다.

13.1 가정

• malloc()과 free()에서 제공하는 것과 같은 기본 인터페이스를 가정한다.
• 이 라이브러리가 관리하는 공간은 역사적으로 힙으로 불리며, 힙의 빈공간을 관리하는 데는 일반적인 링크드리스트가 사용된다.
• 우리는 또한 클라이언트에게 할당된 메모리는 다른 위치로 재배치 될 수 없다고 가정한다.

13.2 저수준의 기법들

분할과 병합

• 분할(Splitting)
  • 요청이 왔을 때, 요청을 만족 시킬 수 있는 빈 청크를 찾아 이를 둘로 분할한다. 첫 번째 청크는 호출자에게 반환되고, 두 번째 청크는 리스트에 남게된다. 요청이 빈 청크의 크기보다 작은 경우 분할기법이 사용된다.
• 병합(Coalescing)
  • 메모리 청크를 반환할 때 해제되는 청크의 주소와 바로 인접한 빈 청크를 검사한다. 새로 해제된 빈 공간이 기존에 존재하는 빈 청크와 바로 인접해 있다면 그들을 하나의 더 큰 빈공간으로 병합한다.

할당된 공간의 크기 파악

• 대부분의 할당기는 추가 정보를 헤더(header) 블럭에 저장한다. 헤더 블럭은 메모리에 유지되며 보통 해제된 청크 바로 직전에 위치한다.
• 헤더는 할당된 공간의 크기를 저장해야 한다. 또한, 해제 속도를 향상시키기 위한 추가의 포인터, 부가적인 무결성 검사를 제공하기 위한 매직 넘버, 및 기타정보를 저장할 수 있다.
• 사용자가 free(ptr)을 호출하면 라이브러리는 헤더의 시작 위치를 파악하기 위해 간단한 포인터 연산을 한다.
• 헤더를 가리키는 포인터를 얻어내면 라이브러리는 매직 넘버가 기대하는 값과 일치하는지 비교하여 안정성 검사(sanity check)를 실시한다. 그리고 새로 해제된 영역의 크기를 간단한 수학을 통해 계산한다.
• 빈 영역의 크기는 헤더 크기 + 사용자에게 할당된 영역의 크기다.

힙의 확장

• 힙 공간이 부족한 경우 가장 쉬운 방법은 단순히 실패를 반환하는 것이다. 어떤 경우에는 이 방법이 유일한 대안이며, 따라서 NULL을 반환하는 것은 훌륭한 접근법이다.
• 대부분 전통적인 할당기는 적은 크기의 힙으로 시작하여 모두 소진하면 운영체제로 부터 더 많은 메모리를 요청한다. 할당기는 힙을 확장하기 위하여 특정 시스템 콜을 호출한다. 그런 후 확장된 영역에서 새로운 청크를 할당한다. sbrk 요청을 수행하기 위해 운영체제는 빈 물리 페이지를 찾아 요청 프로세스의 주요 공간에 매핑한 후 새로운 힙의 마지막 주소를 반환한다.

13.3 기본전략

최적 적합(Best Fit)

• 빈 공간 리스트를 검색해서 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾는다. 그 후, 후보자 그룹중에서 가장 작은 크기의 청크를 반환한다. 이 청크는 최적 청크라고 불린다. 빈 공간 리스트를 한번만 순회하면 반환할 정확한 블럭을 찾을 수 있다.

최악 적합(Worst Fit)

• 가장 큰 빈 청크를 찾아 요청된 크기만큼만 반환하고 남은 부분은 빈 공간 리스트에 계속 유지한다. 최악 적합의 목적은 최적 적합의 방식에서 발생될 수 있는 작은 청크들을 방지하는 것이다.
• 그러나, 한번 항상 빈 공간 리스트 전체를 탐색해야 하는 오버헤드가 존재한다.

최초 적합(First Fit)

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

다음 적합(Next Fit)

• 항상 리스트의 처음부터 탐색하는 대신 다음 적합 알고리즘은 마지막으로 찾았던 원소를 가리키는 추가의 포인터를 유지한다. 아이디어는 빈 공간 탐색을 리스트 전체에 더 균등하게 분산시키는 것이다. 리스트의 첫 부분에만 단편이 집중적으로 발생하는 것을 방지한다.

13.4 다른 접근법

개별 리스트(Segregate List)

• 특정 응용 프로그램이 한 두개 자주 요청하는 크기가 있다면, 그 크기의 객체를 관리하기 위한 별도의 리스트를 유지하는 것이다. 다른 모든 요청은 더 일반적인 메모리 할당기에 전달된다.
• 이 방법의 장점은 특정 크기의 요청을 위한 메모리 청크를 유지함으로써 단편화 가능성을 상당히 줄일 수 있다. 요청된 크기의 청크만이 존재하기 때문에 복잡한 리스트 검색이 필요하지 않으므로 할당과 해제 요청을 신속히 처리할 수 있다.

특수 목적 할당기 - 슬랩 할당기(Slab Allocator)

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

버디 할당(Buddy Allocator)

• 빈 메모리는 처음에 개념적으로 크기 2^n 인 하나의 큰 공간으로 생각된다. 메모리 요청이 발생하면, 요청을 충족시키기에 충분한 공간이 발견될 때까지 빈 공간을 2개로 계속 분할한다. 이 시점에서 요청된 블럭이 사용자에게 반환된다. 이 방식은 2의 거듭제곱 크기만큼의 블럭만 할당 할 수 있기 때문에 내부단편화로 고생할 수 있다.
• 버디 할당기가 해제될 때, 8KB블럭을 빈 공간 리스트에 반환하면 할당기는 ‘버디’ 8KB가 비어 있는지 확인한다. 비어있다면 두 블럭을 병합하여 16KB로 만든다. 할당기는 다음 16KB의 버디가 비어있는지 확인한다. 비어있다면 이 두 블럭을 다시 합병한다. 이 재귀 합병은 트리를 따라 전체 빈 공간이 복원되거나 버디가 사용 중이라는 것이 밝혀질 때까지 계속 올라간다.

기타 아이디어

• 앞서 설명한 접근 방식들의 한 가지 문제점은 확장성이다. 빈 공간의 개수가 늘어남에 따라 리스트 검색이 매우 느려질 수 있다. 좀 더 정교한 할당기는 복잡한 자료구조를 사용하여 이 비용을 줄인다.