9.9.7~11 할당한 블록의 배치/분할/연결 등

 9.9.7 할당한 블록의 배치

 

어플리케이션이 메모리 할당을 요청할 때, 할당기는 요구되는 메모리 만큼의 가용 블록이 있는지를 검색할 것이다. 이 떄, 할당기가 이 검색을 수행하는 방법은 배치 정책에 의해 결정된다. 이 정책에는 first fit, next fit, best fit 이 세가지가 주로 사용된다.

 

 

 각 정책의 특징은 다음과 같다.

• First Fit

- First fit은 가용 리스트를 처음부터 검색하여 크기가 맞는 첫 번째 가용 블록을 선택한다.

- 장점 : 대체로 리스트의 마지막에 가장 큰 가용 블록들을 남겨둔다.

- 단점 : 대체로 리스트의 앞에 작은 가용 블록들을 남겨두기 때문에 큰 가용 블록을 검색하는 경우, 작은 블록들을 거쳐서 큰 블록으로 가야되기 때문에 시간이 늘어난다. (크든 작든 한 블록을 검사하는 것에 같은 시간이 걸린다는 것을 기억하자.) 

 

• Next Fit

- First Fit에 대안으로 만들어졌으며, 이전 검색에서 가용 블록을 발견했다면, 처음부터 검색하는 것이 아니라 이전 검색에서부터 검색을 시작한다는 것이다. 

- 장점 : 대체로 블록은 앞에서부터 채워나가기때문에 원하는 블록을 빨리 찾을 가능성이 높다.

- 단점 : 대신에 앞에 가용블록이 남아있어도 검색 시도를 하지 않기 때문에 메모리 이용도가 낮아지게 된다.

 

• Best Fit

- 처음부터 전부 검색하여, 크기가 딱 맞는 블록이 어떤것인지 추려내서 할당한다.

- 장점 : 모든 경우의 수에서 가장 최선의 수를 선택하기 때문에 최고의 메모리 이용도를 가진다.

- 단점 : 대신에 최저의 속도를 가지게 된다.

 

 

 9.9.8 가용 블록의 분할

그림 1. 가용 블록 분할의 예

 만약 그림1과 같은 상황에서 8바이트 (2칸) 의 공간 할당을 원한다고 하자.

그럼 맨 앞(왼쪽)에서 검색해서 P2에 도달했을 때, 48바이트 (6칸)의 공간이 있는 것을 알게된다.

 

 

그림 2. 전부 한꺼번에 할당하는 경우 (진한 하늘색은 신경쓰지 말자)

 이 때, 2가지의 경우의 수가 있다. P2에서 P3까지 공간을 전부 할당시키는 것이다. 그렇다면 연산은 단순해서 속도는 빠르겠지만, 16바이트 (4칸) 의 내부단편화가 생기게 된다. 즉, 비효율적이라는 말이다. 

 

하지만, 처음부터 메모리 전체 현황을 잘 파악하여 뒤에 2칸을 발견해서 저기에 놓았다면 (즉, 처음부터 잘 배정했다면) 사이사이 비어있는 공간을 전부 할당해도 내부 단편화 문제는 크지않을 것이다.

 

그림 3. 가용블록을 분할하여 적당한 만큼 할당하는 경우

 두번째 방안으로는 그림 3처럼 필요한 만큼만 할당하는 것이다. 이러면 약간의 연산은 필요하겠지만, 메모리의 활용도는 높아지게 된다.

 

 

 9.9.9 추가적인 힙 메모리 획득하기

만약 할당기가 요청받은 크기의 가용 블록을 찾지 못하면 어떻게 되는가?

 

그림 4. 인접한 가용 블록을 병합한다.

 

첫번째는 그럼 4처럼 인접해있는 가용블록들을 합쳐서 하나의 큰 가용블록으로 만드는 것이다. 

 

하지만, 이렇게 해도 충분한 크기의 가용 블록이 생성되지 않거나 더이상 병합할 수 있는 가용 블록들이 없다면 할당기는 커널에 sork함수를 호출하여 추가적인 힙 메모리를 요청해야한다. 

 

 

9.9.10 가용블록 요청하기

 할당기가 하당한 블록을 반환할 때, 새롭게 반환하는 블록에 인접한 다른 가용 블록들이 있을 수 있다. 이 블록을 병합해주지 않으면, 충분한 메모리가 있음에도 불구하고 할당하지 못하게 된다. 아래 그림을 보자.

 

그림 5. 오류 단편화false fragmentation 의 예

만약 20바이트 (5칸)의 메모리를 할당하고 싶다고 해 보자. 헤더를 제외하고도 24바이트 (6칸)의 공간이 남음에도 불구하고 16/0, 16/0으로 나누어져 있기 때문에 할당하지 못하게 된다.

 

 이는 사용하고 있던 블록이 반환되었을 때, 전후에 가용 블록이 있는지 검색하여 병합해주지 않으면 메모리가 비효율적이 되는 것이다. 이 병합해주는 과정을 연결coalescing이라고 한다.

 

 연결에는 두 가지가 있다. 하나는 블록이 반환되었을 때, 바로 앞뒤를 병합해주는 즉시 연결immediate coalescing과 일정 시간 후에 가용 블록들을 연결하는 지연 연결deferred coalescing이 있다. 지연 연결의 예로는 할당 요청이 실패할 때 모든 가용 블록을 검색하여 병합해주는 방식들이 있다.

 

 즉시 연결이 단순하고 좋게 보이지만, 불필요한 때에도 병합을 해서 무의미한 연산을 할 가능성이 높다. 그렇기에 속도를 추구하는 할당기들은 지연 연결의 형태를 선택하는 경우도 있다.