[OSTEP-17] Free Space Management

개요

• 메모리 관리 시스템의 근본적인 측면을 논의한다
  • 힙의 페이지를 관리하는 malloc
  • 프로세스 주소 공간의 일부분을 관리하는 운영체제 자체
• 관리하는 공간이 가변-크기 빈 공간들의 집합이면 메모리를 관리하는 것이 어려울 수 있음
• malloc() 과 free() 에서처럼 사용자-수준 메모리-할당 라이브러리에서, 세그멘테이션으로 물리 메모리를 관리하는 운영체제에서 발생함
• 어떠한 경우에도 외부 단편화가 존재함

 

 

핵심 질문: 빈 공간을 어떻게 관리하는가

가변 크기의 요구를 충족시켜야 할 때, 빈 공간은 어떻게 관리가 되어야 하는가? 단편화를 최소화하기 위해 어떤 전략을 사용할 수 있는가? 여러 대안들의 시간과 공간의 오버헤드는 어떻게 되는가

가정

• malloc() 과 free() 에서 제공하는 것과 같은 기본 인터페이스를 가정.
  • void *malloc(size_t size) 는 응용 프로그램이 요청한 바이트 수를 나타내는 변수 size를 받아들임
• 크기정보를 전달하지 않고도 공간을 해제할 수 있어야함
• 힙의 빈 공간을 관리하는 데는 일반적인 링크드리스트가 사용됨
  • 이 자료구조는 반드시 리스트일 필요는 없고 빈 공간들을 표현할 수 있는 자료구조면 충분함
• free() 를 통해 메모리가 반환될 때 까지 프로그램이 소유하게 되고 라이브러리에 의해 다른 위치로 옮겨 질 수 없음
  • 압축은 사용 불가

저수준 기법들

분할

 

• 10 바이트를 초과하는 모든 요청은 실패해 NULL 을 반환
• 1 바이트를 요청할 경우 할당기는 분할로 알려진 작업을 수행함

 

• 위에서 free(10) 을 호출할경우 리스트에는 힙 전체가 비어있지만 10바이트 길이의 청크 3개로 나누어짐
  • 이는 빈 청크를 발견하지 못하고 실패를 반환함
    • 해결방법
      • 메모리 청크를 반환할때 해제되는 청크의 주소와 바로 인접한 빈 청크의 주소를 살펴봄
      • 새로 해제된 빈 공간이 왼쪽의 빈 청크와 바로 인접해 있다면 하나의 더 빈 청크로 통합

 

할당된 공간의 크기 파악 (Free)

• free 인터페이스는 크기를 매개변수로 받지 않고, 포인터가 인자로 전달되면 malloc 라이브러리는 해제되는 메모리 영역의 크기를 신속히 파악하여 해당 공간을 빈 공간 리스트에 추가
• 대부분의 할당기는 추가 정보를 header 블럭에 저장
• free 는 헤더를 가리키는 포인터를 얻어내고, 안정성 검사를 실시함

 

 

빈 공간 리스트 내장

• 보통 새로운 노드를 위한 공간이 필요할 때 malloc() 을 호출함
• 4096바이트 크기의 메모리 청크가 있다고 가정, 즉. 힙의 크기는 4KB. 이를 빈 공간 리스트로 관리하기 위해 먼저 리스트를 초기화함
• 리스트는 4096 길이의 항목 하나를 가지고 있음

 

 

힙의 확장

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

기본 전략

• 빈 공간 할당을 위한 기본 전략
• 이상적인 할당기는 속도가 빠르고 단편화를 최소로 해야함
  • 불행하게도 할당과 해제 요청 스트림은 무작위, 결국 프로그래머에 의해 결정되기 때문에, 어느 특정 전략도 잘 맞지 않는 입력을 만나면 성능이 매우 좋지 않을 수 있음

최적 적합 (Best Fit)

• 빈 공간 리스트 탐색 → 최적 사이즈의 메모리 청크를 탐색
  • 정교하지 않은 구현은 해당 빈 블럭을 찾기 위해 항상 전체를 탐색해야함

최악 적합 (Worst Fit)

• 최적 적합의 반대 방식, 가장 큰 빈 청크를 찾아 요청된 크기 만큼만 반환하고 남는 부분은 빈 공간 리스트에 계속 유지

최초 적합 (First Fit)

• 간단하게 요청보다 큰 첫 번째 블럭을 찾아서 요청만큼 반환
• 장점: 리스트 전체를 탐색할 필요가 없음
  • 때때로 리스트의 시작에 크기가 작은 객체가 많이 생길 수 있음
  • 빈 공간 리스트의 순서를 관리하는 방법이 쟁점임
    • 주소-기반 정렬을 사용할 수 있음
    • 리스트를 주소로 정렬하여 병합을 쉽게하고, 단편화를 감소시킴

다음 적합 (Next Fit)

• 마지막으로 찾았던 원소를 가리키는 추가의 포인터를 유지
• 빈 공간 탐색을 리스트 전체에서 균등하게 분산시키는 것
• 리스트의 첫 부분에서만 단편화가 생기는 것을 방지
• 최초 적합의 성능과 비슷함

다른 접근 법

• 단순한 최적 적합 할당에 그치지 않고, 그 이상에 대해서 생각해볼 수 있음

개별 리스트

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