11. Free-Space Management¶

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

Managing Heap¶

사용자 수준 메모리 할당 라이브러리에 존재하는 메모리 할당기의 발전 역사에 초점
malloc()과 free()에서 제공하는 것과 같은 기본 인터페이스를 가정

구체적으로 void *malloc (size_t size)는 응용 프로그램이 요청한 바이트 수를 나타내는 변수 size를 받아들인다.

이 함수는 요청된 크기와 같거나 큰 영역을 가리키는, 타입이 없는 또는 C 언어의 용어로 void 포인터를 반환한다.
대응되는 루틴 void free(void *ptr) 는 포인터를 인자로 전달받고 해당 영역을 해제한다.

공간을 해제할 때 사용자는 라이브러리에게 크기 정보를 전달하지 않는다.

라이브러리는 포인터만으로 해제하고자 하는 메모리 영역의 크기를 파악해야 한다.
이 라이브러리가 관리하는 공간은 역사적으로 힙 (heap)으로 불리며,
힙의 빈 공간을 관리하는 데는 일반적으로 링크드리스트가 사용된다. 이 자료 구조는 영역 내의 모든 빈 Chunk에 대한 주소를 갖고 있다.

• 가정

  1. 외부 단편화 방지에 초점

  2. 클라이언트에게 할당된 메모리는 다른 위치로 재배치될 수 없다고 가정

  예를 들어, 프로그램이 malloc()을 호출하여 힙의 일부 영역에 대한 포인터를 받으면, 그 메모리 영역은 대응하는 free()를 통하여 반환될 때까지 프로그램이 소유하게 되고 라이브러리에 의해 다른 위치로 옮겨질 수 없다.
  단편화 해결에 유용하게 사용되는 빈 공간의 압축은 이 경우에는 사용이 불가능하다 ¹ .

할당기에 사용되는 일반적인 기법¶

1. Splitting (분할)¶

• Finding a free chunk of memory that can satisfy the request and splitting it into two.
  • When request for memory allocation is smaller than the size of free chunks.

• Two 10-bytes free segment with 1-byte request
  
  

요청을 만족시킬 수 있는 빈 청크를 찾아 이를 둘로 분할한다.
첫 번째 청크는 호출자에게 반환되고, 두 번째 청크는 리스트에 남게 된다.

따라서 위의 예에서 1바이트 요청이 발생하고 Allocator가 리스트의 두 번째 원소를 사용하여 요청을 충족시키기로 했다고 가정하자.
malloc()은 20(1바이트가 할당된 영역의 주소)을 반환한다.

기본적인 리스트의 모습은 바뀌지 않았다는 것을 알 수 있다.
유일한 변경 사항은 빈 공간이 이제 20이 아니라 21에서 시작한다는 것과 빈 공간의 길이가 이제 9라는 것이다.

2. Coalescing (병합)¶

• 병합 전

  

  병합 후

  

메모리 청크가 반환될 때 빈 공간들을 병합하기
메모리 청크를 반환할 때 해제되는 청크의 주소와 바로 인접한 빈 청크의 주소를 살펴 본 뒤, 새로 해제된 빈 공간이 왼쪽의 빈 청크와 바로 인접해 있다면 그들을 하나의 더 큰 빈 청크로 병합한다.

할당된 영역의 크기 파악: 헤더¶

• 할당된 영역과 헤더

포인터가 인자로 전달되면 malloc 라이브러리는 헤더를 통해 해제되는 메모리 영역의 크기를 신속히 파악하여 그 공간을 빈 공간 리스트에 추가시킬 수 있다.

이 작업을 위해 대부분의 Allocator는 추가 정보를 헤더(header) 블럭에 저장한다. (해제 속도를 향상시키기 위한 추가의 포인터, 부가적인 무결성 검사를 제공하기 위한 매직 넘버 등등)

헤더 블럭은 메모리에 유지되며 보통 해제된 청크 바로 직전에 위치한다.

이 예에서는 ptr이 가리키는 크기 20바이트의 할당된 블럭을 검토하고 있다.
사용자는 malloc()을 호출하고 그 결과를 ptr에 저장하였다고 가정하자. ptr = malloc (20);
헤더는 적어도 할당된 공간의 크기는 저장해야 한다 (이 경우 20).

- The Header of Allocated Memory Chunk¶

`ptr = malloc (20)

다음과 같이 할당 영역의 크기와 매직 넘버를 저장하는 간단한 헤더를 가정하자.

typedef struct __header_t {  
    int size;  
    int magic;  
} header_t;  

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

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

void free(void *ptr) {  
    // 헤더 시작 위치 파악을 위한 간단한 포인터 연산  
    header_t *hptr = (void *)ptr − sizeof(header_t);  
...  
    // 안전성 검사  
    assert(hptr -> magic == 1234567);  

그리고 새로 해제된 영역의 크기를 간단한 수학을 통해 계산한다 (즉, 헤더의 크기를 영역의 크기에 더함).

주의할 점: 빈 영역의 크기는 헤더 크기 더하기 사용자에게 할당된 영역의 크기가 된다.
사용자가 N 바이트의 메모리 청크를 요청하면 라이브러리는 크기 N 의 빈 청크를 찾는 것이 아니라 빈 청크의 크기 N + 헤더의 크기인 청크를 탐색한다.

Embedding A Free List (빈 공간 리스트 구현)¶

빈 공간과 사용 중인 공간을 추적하기 위해 빈 공간 내에 간단한 리스트를 구현하는 방법

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

4096바이트 크기의 메모리 청크(크기가 4 KB인 힙)가 있다고 하자.

이를 빈 공간 리스트로 관리하기 위해서 먼저 리스트를 초기화해야 한다.
처음에 리스트는 헤더 크기를 포함한 4096 길이의 항목 하나를 가지고 있다. 이 리스트 노드의 설명은 다음과 같다.

typedef struct ___node_t {  
    int size;  
    struct _ _node_t *next;  
} node_t;  

1. Heap Initialization¶

• 하나의 빈 청크만을 가진 힙

![[Pasted image 20230305161800.png]]

힙을 초기화하고 힙에 빈 공간 리스트의 첫 번째 원소를 넣는 코드를 살펴보자.
힙은 시스템 콜 mmap()을 호출하여 얻어진 영역에 구축된다고 가정한다.

// mmap() returns a pointer to a chunk of free space  
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;  

이 코드의 실행 후 리스트는 크기 4088의 항목 하나만을 가지게 된다.
head 포인터는 이 영역의 시작 주소를 담고 있다.
영역의 시작 주소를 16 KB라고 가정하자 (아무 가상 주소라도 상관 없다).

2. Allocation¶

![[Pasted image 20230305162006.png]]
![[Pasted image 20230305161955.png]]

• 100바이트 메모리 chunk가 요청
  1. 이 요청을 처리하기 위해 라이브러리는 먼저 충분한 크기의 청크를 찾는다.

하나의 빈 청크 (크기 : 4088) 만이 존재하기 때문에 이 청크가 선택된다.
헤더의 크기를 8바이트라고 가정 (정수형의 크기와 정수형의 매직 넘버) 하면 위 그림과 같이 \(빈\ 영역의\ 크기 + 헤더의\ 크기\) 를 충족시킬 수 있는 청크, 나머지 빈 청크 두 개로 분할된다.

100바이트에 대한 요청이 오면 라이브러리는

1. 기존 하나의 빈 청크 중 108바이트를 할당
2. 할당 영역을 가리키는 포인터 (그림의 ptr)를 반환한다.
3. 그리고 나중에 free() 에서 사용할 수 있도록 할당된 공간 직전 8바이트에 헤더 정보를 넣는다.
4. 그런 후 하나 남은 빈 노드를 3980바이트 (\(4088-108\))로 축소한다.

Free Space with Chunks Allocated¶

![[Pasted image 20230305162028.png]]

이제 100바이트씩 (또는 헤더 포함 108바이트) 할당된 3개의 공간이 존재하는 힙을 살펴보자.
그림에서 볼 수 있듯이 힙의 시작 부분 324바이트가 현재 할당되어 있다. (3개의 헤더와 호출 프로그램에 의해 사용 중인 3개의 100바이트 영역)

빈 공간 리스트는 여전히 head가 가리키는 하나의 노드로 구성되어 있지만 세 번의 분할 이후 3764바이트로 축소된 모습이다. 프로그램이 free()를 통해 일부 메모리를 반환하면 어떤 일이 벌어질까?

Free Space with free()¶

![[Pasted image 20230305162110.png]]

• 20.6 2개의 할당 청크를 가진 빈 공간
  ![[Pasted image 20230305162106.png]]
  이 예제에서 응용 프로그램은 free(16500)을 호출하여 할당 영역 중 가운데 청크를 반환한다.
  16500은 메모리 영역의 시작 주소 16384, 이전 메모리 청크의 크기 108, 해제되는 청크의 헤더 8바이트를 모두 더해서 나온 값이다.

그림에서 이 값은 sptr이 나타낸다. 라이브러리는 신속히 빈 공간의 크기를 파악하고, 빈 청크를 빈 공간 리스트에 삽입한다.

빈 공간 리스트의 헤드 쪽에 삽입한다고 가정하면 공간의 모양은 그림 20.6과 같다.

이제 빈 공간 리스트의 첫 번째 원소는 작은 빈 청크 (100바이트 크기이며 리스트의 헤드가 가리킴)이고 두 번째 원소는 큰 빈 청크 (3764바이트)이다.

드디어 우리 리스트가 하나 이상의 원소를 가진다! 불행하지만 흔히 일어나는 단편화가 발생하였다.

Free Space with Freed Chunks¶

![[Pasted image 20230305162120.png]]

• 병합되지 않은 빈공간 리스트
  ![[Pasted image 20230305162133.png]]

마지막으로 마지막 2개의 사용 중인 청크가 해제된다고 하자. 병합이 없다면, 작은 단편으로 이루어진 빈 공간 리스트가 될 것이다.
모든 메모리가 비어 있긴 하지만, 전부 조각나 있기 때문에 한 청크가 아니라 단편으로 이루어진 메모리처럼 보인다.

병합 실행

• 병합되지 않은 빈 공간 리스트
  ![[Pasted image 20230305162332.png]]

해결책은 간단하다: 리스트를 순회하면서 인접한 청크를 병합하면 된다.
병합이 완료되면 힙은 전체 하나의 큰 청크가 된다.

Double Free¶

Free(str): dangling reference

![[Pasted image 20230305162411.png]]

이미 해제한 메모리를 다시 free() 해제하는 경우가 없도록 주의하자.

힙의 확장¶

![[Pasted image 20230305162442.png]]

일반적으로 allocator는 작은 크기의 힙으로 시작하여 모두 소진하면 운영체제로부터 더 많은 메모리를 요청한다.
힙을 확장하기 위하여 특정 시스템 콜 (예, 대부분의 Unix 시스템에서는 sbrk(), brk())을 호출한다.
그런 후 확장된 영역에서 새로운 청크를 할당한다.

sbrk 요청을 수행하기 위해 운영체제는 빈 물리 페이지를 찾아 요청 프로세스의 주소 공간에 매핑한 후, 새로운 힙의 마지막 주소를 반환한다.

빈 메모리 공간 관리: 기본 전략¶

빈 공간 리스트 관리를 통한 메모리 관리 알고리즘¶

• 빈 공간 리스트를 관리하는 알고리즘의 예시 (고전적인 알고리즘 4가지)
  할당 가능한 메모리 영역을 리스트 형태로 유지.

1. 최초 적합(First Fit)

   리스트 처음부터 탐색, 가장 최초로 발견되는 가능한 빈공간에 할당

2. 다음 적합 (Next fit)

   마지막으로 찾았던 위치의 포인터를 유지한다.

3. 최적 적합(Best Fit)

   빈 공간 중 가장 외부 단편화가 작은 공간에 할당

4. 최악 적합(worst-fit)

   가장 빈 공간이 크게 남는 위치에 할당

5. 개별 리스트 (Segregated List)
   
   한 동안 유행했던 방법은 별도의 개별 리스트(segregated list)를 사용하는 것이다. 기본적인 아이디어는 간단하다. 특정 응용 프로그램이 한두 개 자주 요청하는 크기가 있다면, 그 크기의 개체를 관리하기 위한 별도의 리스트를 유지하는 것이다.

다른 모든 요청은 더 일반적인 메모리 할당기에게 전달된다.

이 방법의 장점은 분명하다. 특정 크기의 요청을 위한 메모리 청크를 유지함으로써 단편화 가능성을 상당히 줄일 수 있다. 요청된 크기의 청크만이 존재하기 때문에 복잡한 리스트 검색이 필요하지 않으므로 할당과 해제 요청을 신속히 처리할 수 있다.

그러나, 지정된 크기의 메모리 풀과 일반적인 풀에 얼마만큼의 메모리를 할당해야 하는지에 대한 문제에 대안이 필요하다.

1. Slap allocator (슬랩 할당기): 개별 리스트의 Advanced 버전
   - Slab: A set of kernel pages
   커널이 부팅될 때 커널 객체를 위한 여러 객체 캐시(object cache)를 할당한다.

커널 객체: 락, 파일 시스템 아이노드 등 자주 요청되는 자료 구조들을 일컫는다.
객체 캐시: 지정된 크기의 객체들로 구성된 빈 공간 리스트이고 메모리 할당 및 해제 요청을 빠르게 서비스 하기 위해 사용된다.

아이노드들로 구성된 객체 캐시가 있고, 락 구조만을 담고 있는 객체 캐시도 있다.
기존에 할당된 캐시 공간이 부족하면 상위 메모리 할당기에게 추가 슬랩을 요청한다.
요청의 전체 크기는 페이지 크기의 정수배이다.

반대로, 슬랩 내 객체들에 대한 참조 횟수가 0이 되면 상위 메모리 할당기는 이 슬랩을 회수할 수 있다.
VM 시스템이 더 많은 메모리를 필요할 때 실제 회수가 일어난다.

슬랩 할당 방식은 빈 객체들을 사전에 초기화된 상태로 유지한다는 점에서 개별 리스트 방식보다 우수하다. (자료 구조의 초기화와 반납에는 많은 시간이 소요된다)

반납된 객체들을 초기화된 상태로 리스트에 유지하여 슬랩 할당기는 객체당 잦은 초기화와 반납의 작업을 피할 수 있어서 오버헤드를 현저히 감소시킨다.

1. 버디 알고리즘 (buddy algorithm = buddy system)
   컴퓨터가 조작하기 빠른 2진수를 기반으로 작동하는 메모리 할당 기법
   빈 공간의 합병은 매우 중요한 기능이기 때문에 설계됨
   
   즉, 1메가바이트 메모리의 경우 21개의 리스트가 필요하다.

1 byte = 2^3 bits
1KB = 2^10 bytes
1MB = 2^20 bytes
1GB = 2^30 bytes

이 체계를 버디 시스템이라고 부르는 이유는 블록이 분할될 때마다 이를 버디라고 부르기 때문이다.

• 스왑

1. 112K 프로세스(프로세스 A)를 메모리로 스왑하는 경우
   리스트는 2의 거듭제곱으로만 유지되므로 2의 거듭제곱인 다음으로 높은 메모리(이 경우 128K)를 할당함.

1M 블록을 512K 블록 2개로 분할한 뒤 512K 블록 중 하나는 256K 블록으로 분할되고 256K 블록 중 하나는 두 개의 128K 블록으로 분할되며, 그 중 하나는 프로세스에 할당된다.

1. 35K가 필요한 프로세스(프로세스 B)가 메모리로 스왑하는 경우
   이 경우 64K 블록이 필요하다.
   64K 목록에 항목이 없으므로 다음 크기 목록(128K)이 고려된다. 여기에는 항목이 있으므로 두 개의 버디가 생성되고 프로세스가 해당 블록 중 하나에 할당된다.

2. 80K가 필요한 프로세스(프로세스 C)가 메모리로 스왑하는 경우
   프로세스는 256K 목록에서 가져온 128K 블록을 차지한다.

• 메모리 해제
  → 병합 시 BitMap을 사용한다.
  1. 프로세스 A가 종료되어 메모리를 해제
  실제로 해당 메모리 블록은 128K 목록에 추가
  이제 다른 프로세스가 60K의 메모리를 요청하면 64K 목록에서 항목을 찾을 수 있으므로 해당 항목을 할당할 수 있다.

2. 이제 프로세스 B가 종료되고 메모리를 해제
   이렇게 하면 해당 블록이 64K 목록에 배치된다.
   프로세스 D가 종료되면 블록 병합을 시작할 수 있다.

3. 마지막으로 C 프로세스가 종료되면 1M 목록의 단일 목록 항목으로 다시 병합할 수 있다.

버디 시스템이 빠른 이유는 2k 바이트의 블록 크기가 반환될 때 병합이 가능한지 확인하기 위해 2k 리스트만 검색하면 되기 때문이다. 인접한 목록만 확인하고 인접한 주소만 확인하면 되므로 빠른 프로세스임.
allocator, paging 시스템에서 메모리를 바꿀 때 쉽게 바꿀 수 있음.

버디 시스템의 문제점

모든 메모리 요청은 2의 거듭제곱으로 반올림해야 하기때문에 메모리 사용량 측면에서 비효율적임.
위에서 80K 프로세스가 128K 메모리 블록에 할당되어야 함.

앞에서 설명한 접근 방식들의 한 가지 문제점은 확장성이다. 빈 공간들의 개수가 늘어남에 따라 리스트 검색이 매우 느려질 수 있다. 좀 더 정교한 Allocator는 복잡한 자료 구조를 사용하여 이 비용을 줄인다 .
→ 균형 이진 트리 (balanced binary tree), 스플레이 트리 (splay tree), 부분 정렬 트리 (partially ordered tree)

• 실제 메모리 할당에 주로 쓰이는 자료 구조 및 알고리즘

추가 참고 자료¶

• Operating Systems: Virtual Memory
• G53OPS : Memory Management
• Chunks - IBM Documentation