[운영체제] 17. Free Space Management 빈 공간 관리

앞장에서 세그멘테이션에서 발생할 수 있는 문제를 제기하며 끝났다. 첫 번째 문제는 외부 단편화(external fragmentation)였다. 아무리 세그멘테이션으로 물리 메모리를 관리하더라도 빈 공간이 단편화되어 사실 상 사용하기 어렵게 된다는 문제가 발생한다. 두 번째 문제는 세그멘테이션이 아직 유연하지 못해서 sparse한 구조에서 비효율적이라는 것이다. 이번 장에서는 외부 단편화를 해결하기 위한 방법으로 free list에 대해 알아볼 것이다.

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

17.1 가정

17.2 저수준 기법들

1. 분할(splitting)과 병합(coalescing)

빈 공간 리스트는 힙에 있는 빈 공간들의 집합이다. 30바이트의 힙이 있다고 가정하자.

위와 같은 힙의 빈 공간 리스트에는 2개의 원소가 있다. 하나는 0부터 9바이트와 20부터 29바이트에 해당하는 빈 세그멘트 2개이다. 이때 메모리 요청이 들어왔다.

1-1. 10바이트에 대한 요청은 둘 중 하나의 덩어리를 사용하면 된다.

1-2. 그렇다면 10바이트보다 적은 요청에 대해서는 어떻게 할까?
메모리를 1바이트만 요청했다고 해보자. 이 경우 할당기는 분할(splitting)로 알려진 작업을 수행한다. 요청을 만족시킬 수 있는 빈 청크를 찾아 이를 둘로 분할한다. 첫 번째 청크는 호출자에게 반환되고, 두 번째 청크는 리스트에 남는다. 따라서 빈 리스트는 아래와 같이 바뀐다.

기본적인 리스트의 모습은 바뀌지 않았지만, 두 번째 청크는 21부터 시작하고 길이가 9로 줄었다.

분할이라는 기법이 있다면 당연히 병합(coalescing)도 있을 것이다. 응용 프로그램이 free(10)을 호출하여 힙의 중간에 존재하는 공간을 반환한다면 빈 공간이 리스트에 추가되어 아래의 그림처럼 바뀔 것이다.

1-3. 10바이트를 초과하는 모든 요청은 실패할 것이다. 총 20바이트가 비어있지만 빈 공간이 파편화되어 있기 때문에 10바이트를 초과하는 메모리를 할당할 수가 없다. 이를 해결하려면 메모리 청크가 반환될 때 빈 공간들을 병합하면 된다. 메모리 청크를 반환할 때 해제되는 청크의 주소와 바로 인접한 빈 청크의 주소를 살펴본 후, 이 둘이 바로 인접해있다면 그것들을 하나의 더 큰 빈 청크로 병합한다. 그러면 아래와 같은 모양이 될 것이다.

2. 할당된 공간의 크기 파악

free(void *ptr) 인터페이스는 크기를 매개변수로 받지 않는다. 어떻게 해제되는 메모리 영역의 크기를 파악할까? 
대부분의 할당기는 추가 정보를 헤더(header) 블럭에 저장한다. 헤더 블럭은 메모리에 유지되며 보통 해제된 청크 바로 직전에 위치한다. 

위의 예에서는 ptr이 가리키는 크기 20바이트의 할당된 블럭을 검토하고 있다. 사용자는 malloc()을 호출하고 그 결과를 ptr에 저장하였다. 이때 헤더는 할당된 공간의 크기, 무결성 검사를 위한 매직 넘버 등을 저장한다.

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

 헤더가 가리키는 포인터를 얻어내면, 매직넘버를 이용해 안전성 검사도 실시한다. 그리고 해제된 영역의 크기를 알아낸다. 빈 영역의 크기는 ( 헤더 크기 + 사용자에게 할당된 영역 ) 의 크기가 된다.

 

3. 빈 공간 리스트 내장

지금까지 살펴본 빈 공간 리스트를 어떻게 구현할 수 있을까? 빈 공간 내에 리스트를 구축해야 한다.  

4KB의 메모리 청크가 있다고 해보자. 우리는 4096의 공간을 할당받았지만 헤더의 크기(8KB로 가정)를 제외한 공간을 사용할 수 있으므로 4096 - 8 = 4088 이 남게 된다. 헤더의 size 에는 4088이 담긴다.

근데 malloc(100)으로 메모리 요청했다. 4088 - (100+8) = 3980. 남은 메모리는 3980이다. 

이렇게 메모리를 할당하는 과정이 3번 일어난 후 프로그램이 free()를 통해 일부 메모리를 반환하면 어떻게 될까? 이 예제에서 응용프로그램은 free

빈 공간 리스트와 힙을 초기화하고

 

17.3

 

작성중입니다 ... ㅎㅎ ㅜㅜㅜ