컴퓨터 시스템 - [동적 메모리 할당(808~)]
C언어의 malloc함수의 역할인 동적할당기(dynamic storage allocator), 그 중에서도 명시적 할당기를 직접 구현하며 성능을 높인다.
응용이 명시적으로 할당된 블록을 반환해 줄 것을 요구함.
최대이용도? = 처리량과 이용도사이의 균형
할당된 블록이 payload보다 클 때 일어난다.
할당된 주소는 (64bit 기준) 16의 배수라는 규칙을 지키기 위함이다.
예를 들어 요청된 paylaod는 5 더블 워드라면, 5 * 8로 현재 메모리주소로부터 40바이트 뒤에 다음 payload가 할당되게 된다.
현재 주소는 이미 16의 배수라는 가정 하에, +40 byte 된 다음 주소가 16의 배수가 아니게 되는것이다.
따라서 요청된 payload보다 더 큰 메모리를 할당해 다음 payload가 할당될 주소를 맞춰주는데, 이때 추가할당되는 메모리를 padding이라고 한다.
내부단편화는 외부단편화와 달리 메모리가 얼마나 추가할당되었는지 계산하기 편하다.(정량화 간단)
실제 할당된 메모리 - payload크기 의 합으로 구할 수 있다.
가상메모리에 요청된 크기 이상의 메모리가 남아있지만, split되어있어서 이용하지 못하고 추가적인 free 메모리 블록이 필요한 상황에 일어난다.
외부단편화는 이후에 어떤 할당 요청이 들어오냐에 따라 생길수도 있고 생기지 않을수도 있는 문제이다. 같은 양의 메모리가 요청되어도 작은 양이 여러번 요청되면 생기지 않을 수 있는 문제가 크게 한번에 요청되면 남은 공간이 분할되어있어서 그만한 큰 자리가 남아있지 않을 수도 있기 때문이다. 따라서 계산이 어렵고 예측이 불가능하다.
=> 이 부분에서 first, next, best 전략을 고민해야한다. 남은 메모리공간중 어느 위치에 할당할 것인지 정하는게 최적화를 위해서 중요하다.
어떻게 free상태의 블록의 위치를 찾을까?
implicit free list(묵시적 가용 리스트) / explicit free list(명시적 가용 리스트) / Segregated free list(분리 가용 리스트)
헤더에 주소와 블록의 길이를 표시하고 연산해서 다음 블록의 위치를 찾는다. (실제 포인터를 사용해 다음 블록을 가리키는 것X)
장점: 단순성
단점: free블록에 payload를 할당할 때 힙에 있는 전체 할당된 블록과 free블록의 수(N)만큼 연산해야 함
앞의 free 블록의 포인터가 뒤의 free 블록을 가리킨다. (allocated 블록은 해당X)
모든 가능한 블록 크기를 size class의 집합으로 만든다.
=> Buddy Systems
새롭게 allocated 블록을 배치하기 위한 free 블록을 어떻게 선택하는가?
first fit / next fit / best fit
first fit: 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 free 블록을 택한다. 리스트의 앞에 작은 블록이 남고 뒤에 큰 블록이 남는다.(큰 블록을 찾는 경우에 검색시간이 늘어남)
next fit: first fit과 비슷한데, 이전 검색이 종료된 시점부터 검색을 재시작한다. first fit에 비해 검색 시간이 빠르지만 메모리 이용도가 나쁘다.
best fit: 할당 가능한 모든 free블록 중 크기가 가장 작은 블록을 택한다. 메모리 이용도는 first, next fit에 비해 좋지만, implicit free list를 이용할 경우엔 힙 전체를 검색해야하기 때문에 검색 시간이 늘어난다. segregated free list에서는 힙 전체를 검색하지 않으면서 best fit에 가까운 블록을 찾는 로직을 이용한다.
선택한 free 블록 전체를 사용하면 불필요하게 padding이 생길 우려가 있다.
(best fit이라면 그런 걱정이 없을 수 있음)
블록 할당 후 남은 공간을 free 블록으로 만들어주기 / 안함(best fit)
할당 블록을 free시킬 때, 다른 free된 블록과 언제 합쳐줄까?
적절한 타이밍에 Coalesce 함수를 사용해 free블록을 합친다.
할당기가 현재 블록을 반환할 때, 인접한 블록이 가용상태인지 할당상태인지를 header와 footer태그의 정보를 보고 확인해 인접 블록이 가용상태라면 앞쪽의 헤더와 뒷쪽의 푸터만 남기고 그 가운데를 통합한다.
현재 블록을 기준으로 이전 블록이 free인 경우에만 이전 블록의 footer에 있는 size 필드가 필요하다. 이전 블록이 free가 아닌 경우에는 footer가 필요 없음.(footer가 없다면 allocated인 것!)