[OS/OSTEP] 17.vm-freespace : 메모리 빈 공간 관리하기 #11

17.vm-freespace

# 시작하며

 앞선 장에서 보았듯 메모리 상에서 빈공간을 관리해야 하는 이유를 알게 됐다. 공간이 고정 크기의 단위로 나누어져 있을 경우에는 관리가 특히 쉽다. 고정 크기 단위의 리스트만 유지하면 된다.

 그러나 공간이 가변크기 일때, 힙에서 malloc()과 free()로 공간을 사용 및 게허가거나, 세그멘테이션 정해진 크기의 물리메모리를 관리하지 않는 경우에는 외부 단편화(external fragment)가 발생한다. 앞에서 설명했지만 다시 설명해보자면, 메모리의 총 빈공간리스트의 크기는 충분하지만, 프로세스가 물리메모리에 부분부분 할당 돼 있기 때문에, 실제로 사용가능한 공간은 크지 않는 경우다. 

 위 그림에서 볼 수 있는 것 처럼 미사용 공간은 20이지만, 11의 공간을 사용하려면 들어갈 곳이 없게 되는 것이다.

 

# 저수준 기법들

## 분할(splitting)

 30바이트의 힙이 아래와 같다. 두개의 미사용공간의 존재하고 가운데 사용중인 공간이 존재한다.

 빈 공간리스트(free list)는 아래와 같이 리스트를 관리하고 있다.

 일단 10바이트의 크기를 힙에 요청했다고 생각해보면, 두 빈공간 리스트 중 아무거나 골라서 사용하게 하면 된다. 그러나 10보다 작은 크기의 공간을 요청하면 어떤 빈공간을 줘야할까? 이 경우에 분할(splitting)기법을 사용하여 빈 공간을 반환해주는데, 즉 자신의 공간을 나누어 주는 것이다. 두번째 리스트가 선택됐고 1을 떼어 준다. 그리고 분할한 리스트을 재조정 해줘야한다. 리스트를 분할할때는 앞에 부분을 주고 뒷부분이 자기 자신이 된다.

1바이트를 할당 해주고 난 후

 

## 병합(coalescing)

 아래의 경우를 다시 생각해보자. 자를 수 있음 당연히 합칠 수 도 있어야한다. free(10)을 호출하여 현재 사용중이던 공간을 반환한다. 즉 미사용 공간으로 바뀌게 된다.

 크게 생각할 필요 없이 가운데 사용중인 공간을 반환해준다. 리스트의 맨앞에 반환시켰다.

 이제 문제가 발생한다. 힙의 총 빈공간은 현재 30이다. 그러나 10, 10, 10 세개로 잘려있기 때문에 10보다 큰 공간을 할당해 줄 수 없는 문제가 발생한다. 리스트들을 합쳐 줘야한다. 메모리를 반환할때 해당 리스트의 양옆을 살펴본다. 그리고 병합이 가능한 연속된 상태라는 것을 알아차리면 병합을 진행한다. 

 

# 추가적인 공간 사용 : 헤더(header)

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

 헤더는 최우선적으로 할당된 메모리의 크기를 알아야한다. 그리고 부가적으로 무결성 검사를 위한 magic넘버나, 추가적인 포인터 등을 가지고 있을 수 있다. 내가 20의 메모리를 할당받았다 하더라도 헤더가 있기때문에 헤더의 크기만큼이 포함된 영역이 배정된다.

 위 그렘에서 현재 ptr의 위치를 즉 자유 공간을 free(ptr)을 이용해 반환하려 한다. 그렇다면 현재 공간의 크기를 알아내야하는데, 헤더에 위치해 있기 때문에 헤더에서 해당 정보를 얻어온다. ptr에서부터 헤더의 접근하는 방법이다.

 그리곤 magic넘버를 확인하여 안정성 검사(sanity check)를 진행한다.

 

# 빈공간 리스트 내장

 현재 초기화 된 4096바이트 크기의 청크가 있다고 가정해보자. 빈 공간 리스트(fress list)는 4096-(헤더크기)의 영역 만큼을 실제 사용할수 있는 크기로 가지고 있으며, header의 size에는 실제 사용할수 있는 빈공간을 알려준다.

 이제 유저는 100바이트의 크기 공간을 요청했다. 그러면 현재 존재하는 한개의 빈 청크를 두개로 분할하여 108바이트( size + header)의 청크와 나머지 공간을 가지고 있는 청크를 생성해낸다. 그리고 할당된 빈공간을 반환시킨다. 아래 그림은 하나의 빈공간만 존재하는 초기의 상태에서 메모리를 100바이트의 메모리를 요청하여 일어난 경우다.  

 비어있던 초기의 4088에서 헤더와 사이즈만큼을 남긴다. 그리고 그 남은 크기에 다시 헤더와 청크로 나눈다. 위 사진처럼 말이다.

 

# 공간 선택하기

 이상적인 공간 할당방식은 속도가 빠르고 단편화를 최소로 해야한다. 그러나 우린 미래를 알 수 없듯이 어떤 공간이 할당되고 삭제 되는지 잘 모른다. 그렇기 때문에 장-단점에 맞는 정책(policy)를 사용해야 한다.

 

# 최적 적합(Best Fit)

 빈 공간 리스트를 순회하면서 요청한 크기와 같거나, 더 큰 빈 메모리 청크를 찾는다. 그리고 그 후보 중 가작 작은 크기, 즉 할당할 공간과 가장 비슷한 공간을 선택한다. 빈 공간 리스트를 한번만 순회하면 정확한 블럭을 찾을 수 있다. 그러나 항상 전체를 검색해야 하기 때문에 성능 저하가 발생한다.

 

# 최악 적합(Worst Fit)

최악 적합의 본질적은 목표는 자유공간(free list)에 작은 크기가 많아지는 것을 막고 커다란 청크를 남긴다는 것이다. 작은 크기가 많아지는것을 줄이면 외부 단편화가 자연히 줄어들 가능성이 높다.  그러나 이역시 공간을 탐색하는데 큰 비용이 수반된다.

 

# 최초 적합(First Fit)

 요청한 공간보다 큰 가장 첫번째 공간을 반환시킨다. 최초 적합은 속도가 빠르다는 장점이 있다. 전체를 탐색할 필요가 없기 때문이다. 그러나 리스트의 시작 부분에 크기가 작은 객체가 많이 생겨날 가능성이 높아진다. 당연한 결과다, 대체로 앞쪽에서 선택이 많이 될거기 때문이다.

# 다음 적합(Next Fit)

  마지막으로 찾았던 원소를 가르키는 추가의 포인터를 유지시키다가, 빈 공간 탐색을 리스트 전체에 균등하게 분산시키는 것이다.  전체를 탐색하지도 않고, 최초 적합과 비슷한 성질을 지니고 있다.

 

# 예제

빈공간 리스트(free list)

크기가 15인 요청이 들어왔을때, 최적 적합(Best fit) 방법은 15보다 큰 것들중에 가장 작은것을 고른다. 이 경우에는 20이 선택 될 것이다.

그리고 15는 공간을 사용하고, 5라는 자유공간이 생긴다. 이 역시 작은 외부 단편화가 많이 일어나게 된다. 

최악의 방법(Worst fit)을 선택했다면, 가운데 30을 선택했을 것이다.  그리고 보다 큰 공간이 넘게 된다. 

 

# 다른접근법 : 개별 리스트(segregated.list)

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

 

# 다른 접근법 : 이진 버디 할당기(binary buddy allocator)

위 그림처럼 최초의 공간이 있다면, 메모리 요청이 발생하면, 요청을 충족시키기에 충분한 공간을 발견할때까지 빈공간을 계속 절반으로 나누어 간다. 아래는 7KB의 상황을 요청할 때이다. 2의 거듭제곱만큼 크기의 블록을 할당할수 있기때문에 내부 단편화 문제가 발생해 빈공간이 생길 수 있다.

 해제될때 좋은 성능을 보인다. 8KB 블럭을 빈 공간 리스트에 반환하면 할당기는 버디의 8KB가 비어있는지 확인하고, 비어 잇다면 두블럭을 병합하여 16KB로 만든다 이러한 행동을 재귀적으로 반복한다.

 

# 마치며

 빈공간 과리는 생각보다 까다로웠다..