컴퓨터 시스템 - [동적 메모리 할당(808~)]
Explicit allocator 구현
C언어의 malloc함수의 역할인 동적할당기(dynamic storage allocator), 그 중에서도 명시적 할당기를 직접 구현하며 성능을 높인다.
Explicit allocator (명시적 할당기) 란?
응용이 명시적으로 할당된 블록을 반환해 줄 것을 요구함.
- 개발자가 직접 free, delete 해줘야함
- C: malloc-free
Implicit allocator (묵시적 할당기)
- 개발자가 free할 필요X
- high level language :Java, C++
요구사항
- 할당된 블록만 Free시킬 수 있다.
- 요청에 즉시 응답하기: 효율성을 위해 먼저 들어온 free/malloc요청을 미루고 다른 명령을 받을 수 없다.
- 힙만 사용하기: Stack 및 다른 타입의 가상메모리에 저장할 수 없다. 프로그램 실행 중에 확장 가능한 것은 heap 뿐이기 때문이다. (Stack은 확장성있지만 미리 크기를 지정해주어야 함)
- 메모리주소는 32bit 모드 기준 8의 배수이고, 64bit 모드 기준 16의 배수이다.
- 할당된 블록을 수정하지 않기. 일단 한 번 할당된 데이터를 메모리관리의 효율성을 위해 자리를 이동시키지 않는다.
=> 왜 이동시키지 않을까?
목표
- 시간효율을 높인다.[처리량 극대화]
(=> 블록 전체를 돌기보다 효율적인 header & footer 사용 고려) - 메모리 이용도를 최대화 => 최대이용도
최대이용도? = 처리량과 이용도사이의 균형
용어 정리
- Payload : 적재물. 저장할 데이터를 가리킴.
- padding
- fragmenation
...
Fragmentation : 단편화
Internal: 내부 단편화
할당된 블록이 payload보다 클 때 일어난다.
할당된 주소는 (64bit 기준) 16의 배수라는 규칙을 지키기 위함이다.
예를 들어 요청된 paylaod는 5 더블 워드라면, 5 * 8로 현재 메모리주소로부터 40바이트 뒤에 다음 payload가 할당되게 된다.
현재 주소는 이미 16의 배수라는 가정 하에, +40 byte 된 다음 주소가 16의 배수가 아니게 되는것이다.
따라서 요청된 payload보다 더 큰 메모리를 할당해 다음 payload가 할당될 주소를 맞춰주는데, 이때 추가할당되는 메모리를 padding이라고 한다.
내부단편화는 외부단편화와 달리 메모리가 얼마나 추가할당되었는지 계산하기 편하다.(정량화 간단)
실제 할당된 메모리 - payload크기 의 합으로 구할 수 있다.
External : 외부 단편화
가상메모리에 요청된 크기 이상의 메모리가 남아있지만, split되어있어서 이용하지 못하고 추가적인 free 메모리 블록이 필요한 상황에 일어난다.
외부단편화는 이후에 어떤 할당 요청이 들어오냐에 따라 생길수도 있고 생기지 않을수도 있는 문제이다. 같은 양의 메모리가 요청되어도 작은 양이 여러번 요청되면 생기지 않을 수 있는 문제가 크게 한번에 요청되면 남은 공간이 분할되어있어서 그만한 큰 자리가 남아있지 않을 수도 있기 때문이다. 따라서 계산이 어렵고 예측이 불가능하다.
=> 이 부분에서 first, next, best 전략을 고민해야한다. 남은 메모리공간중 어느 위치에 할당할 것인지 정하는게 최적화를 위해서 중요하다.
구현 이슈
free 블록 찾기
어떻게 free상태의 블록의 위치를 찾을까?
implicit free list(묵시적 가용 리스트) / explicit free list(명시적 가용 리스트) / Segregated free list(분리 가용 리스트)
implicit free list
헤더에 주소와 블록의 길이를 표시하고 연산해서 다음 블록의 위치를 찾는다. (실제 포인터를 사용해 다음 블록을 가리키는 것X)
장점: 단순성
단점: free블록에 payload를 할당할 때 힙에 있는 전체 할당된 블록과 free블록의 수(N)만큼 연산해야 함
explicit free list
앞의 free 블록의 포인터가 뒤의 free 블록을 가리킨다. (allocated 블록은 해당X)
Segregated free list
모든 가능한 블록 크기를 size class의 집합으로 만든다.
=> Buddy Systems
Placing allocated blocks
새롭게 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 블록 나누기
선택한 free 블록 전체를 사용하면 불필요하게 padding이 생길 우려가 있다.
(best fit이라면 그런 걱정이 없을 수 있음)
블록 할당 후 남은 공간을 free 블록으로 만들어주기 / 안함(best fit)
Coalescing free blocks : false fragmentation <=> thrashing
할당 블록을 free시킬 때, 다른 free된 블록과 언제 합쳐줄까?
- 안합치면 => 쪼개진 공간때문에 할당불가라 false fragmentation
- 바로 합치면 => 만약 일일이 합쳐놓았는데 다시 작은 공간의 요청이 들어와서 도로 나눠야한다면 thrashing
적절한 타이밍에 Coalesce 함수를 사용해 free블록을 합친다.
가용 블록을 경계 태그로 연결하기 : header & footer
할당기가 현재 블록을 반환할 때, 인접한 블록이 가용상태인지 할당상태인지를 header와 footer태그의 정보를 보고 확인해 인접 블록이 가용상태라면 앞쪽의 헤더와 뒷쪽의 푸터만 남기고 그 가운데를 통합한다.
경계 태그의 최적화
현재 블록을 기준으로 이전 블록이 free인 경우에만 이전 블록의 footer에 있는 size 필드가 필요하다. 이전 블록이 free가 아닌 경우에는 footer가 필요 없음.(footer가 없다면 allocated인 것!)
