동적메모리 할당
- 동적 메모리 할당기는 힙이라고 하는 가상 메모리 영역 관리
- 커널은 힙의 꼭대기를 기리키는 변수인 brk를 사용
- 명시적인 할당기는 프로그램이 명시적으로 할당된 블록을 반환해줄 것을 요구
- 묵시적 할당기 -> 가비지 컬렉터: 할당된 블록이 더 이상 프로그램에 의해 사용되지 않는지 할당기가 검출할 수 있을 것을 요구
malloc과 free
malloc은 블록 내에 포함될 수 있는 데이터 객체에 대해서 적절히 정렬된 최소 size 바이트를 가지는 메모리 블록의 포인터를 리턴한다.
프로그램이 malloc이 할당한 메모리보다 더 큰 메모리를 요구하는 경우 NULL을 리턴 -> errno를 설정
- malloc은 리턴하는 메모리를 초기화하지 않음
- calloc은 할당된 메모리를 0으로 초기화하는 래퍼함수이다.
- realloc은 이전에 할당된 메모리의 크기를 변경할려는 경우 사용
malloc은 mmap과 munmap 함수를 사용해서 명시적으로 힙메모리를 할당하거나 반환 / sbrk 함수를 사용
sbrk 함수는 커널의 brk포인터에 incr을 더해서 힙을 늘리거나 줄인다.
- 성공하면 이전의 btr 값을 리턴
- 실패하면 -1을 리턴 -> errno를 ENOMEM으로 설정
- Incr가 0이면 현재의 btr 값을 리턴
- 음수를 incr로 받으면 가능하긴 하지만 리턴 값이 새로운 힙의 탑을 지나서 abs바이트를 가르키기때문에 복잡해짐
free 함수를 사용해 할당된 힙 블록을 반환
동적메모리 할당은 왜 하는가?
종종 프로그램들이 실제 실행시키기 전에 자료구조의 크기를 알 수 없는 경우가 많음
가장 간단한 방법은 배열을 정해진 최대 크기를 가진 정적 배열을 생성하는 것
문제점: 사용자가 임의로 정한 최대크기보다 더 큰 메모리를 사용할려고 하면 error
따라서 자료구조의 크기를 알 수 있을 때 배열을 런타임에 할당하는 것
할당기 요구사항과 목표
- 임이의 요청 순서처리하기: 할당기는 할당과 반환 요청의 순서에 대해서는 아무 가정도 할 수 없다.
- 요청에 즉시 응답하기: 할당기는 블록들을 이들이 어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬해야 한다.
- 힙만 사용하기: 확장성을 갖기 위해 할당기가 사용하는 비확장성 자료 구조들은 힙 자체에 저장해야한다.
- 할당된 블록을 수정하지 않기: 블록은 할당되면 수정하거나 이동하지 않는다. 그래서 압축같은 기법도 적용할 수 없다.
단편화
단편화는 가용메모리가 할당 요청을 만족시키기에 부족할 때 일어난다. 단편화에는 2종류의 단편화가 있다.
1. 내부단편화: 할당된 블록이 데이터 자체보다 클 때 일어난다.
- 내부단편화는 정령화하기가 간단하다. 이것은 단순히 할당된 블록의 크기와 이들의 데이터 사이의 차이의 합이다.
2. 외부단편화: 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 봤을 때는 크키가 충분하지만 이 요청을 처리하기에 블록들이 떨어져있을 때 발생한다.
- 외부단편화는 내부단편화보다 측정하기가 힘들다. 이전 요청의 패턴과 할당기 구현에만 의존하는 게 아니라 미래의 요청이 어떻게 될 지 모르기 때문이다.
- 외부단편화는 측정하기 어렵고 예측하기 어렵기때문에 할당기들은 대게 많은 수의 작은 가용 블록들보다는 더 적은 수의 큰 가용블록들을 유지하는 방법들을 사용한다.
할당기 고려사항
- 가용블록 구성: 어떻게 가용 블록을 지속적으로 추적하는가?
- 배치: 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?
- 분할: 새롭게 할당한 블록을 가용블록에 배치한 후 가용블록의 나머지 부분들로 무엇을 할것인가?
- 연결: 방금 반환된 블록으로 무엇을 할것인가?
묵시적 가용리스트
모든 실용적인 할당기들은 블록 경계를 구분하고 할당된 블록과 가용블록을 구분하는 데이터 구조가 필요하다.
대부분의 할당기들은 이 정보를 블록 내에 저장한다.
단순한 접근법에서 한 블록은 1워드 헤더, 데이터, 패딩(optional)로 구성된다.
헤더는 블록의 크기와 블록이 할당된 상태인지를 인코딩해서 나타낸다.
1. 000은 free
2. 001은 Allocated
- 헤더 다음에는 프로그램이 malloc을 불렀을 때 요구한 데이터가 따라온다.
- 패딩은 없을 수도 있는데 이들의 크기는 가용적이다.
패딩은 외부단편화를 해결하는 전략이 될 수도 있고, 정렬 요구사항을 만족하기 위해 필요할 수도 있다.
패딩은 8의 배수 정해진 바이트의 크기를 맞춰 주기 위해서 사용> 17바이트를 할당해야하면 8의 배수로 맞추는게 할당기가 검색할 때 더 빨라지므로 추가적인 워드를 주더라도 이를 24바이트에 맞춤
묵시적 가용리스트의 장점은 단순성이다.
중요한 단점은 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례한다는 것이다.
할당한 블록의 배치
프로그램이 K바이트의 블록을 요청하면 할당기는 요청한 블록을 저장할 수 있는 큰 가용 블록을 리스트에서 검색한다. 할당기가 이 검색을 수행하는 방법은 배치 정책에 의해서 결정된다.
주로 first fit, next fit, best fit이 사용된다.
- First fit: 가용 리스트에서 처음부터 검색해서 크기가 맞는 첫번째 가용블록을 선택한다. (그리디 전략)
- 장점: 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있다.
- 단점: 리스트의 앞부문에 작은 가용 블록들을 남겨두는 경향이 있어서 큰 블록을 찾는 경우에 검색 시간이 늘어난다. - Next fit: first fit과 비슷하지만 검색을 리스트이 처음에서 시작하는 게 아니라 이전 검색이 종료된 지점에서 검색을 시작한다.
- 장점: first fit보다 매우 빠른 속도를 가진다 (리스트의 앞부분이 작은 크기의 조각들로 구성되어 있으면 더 그런 성향이 있음)
- 단점: first fit보다 최악의 메모리 이용도를 갖는다. - Best fit: 모든 가용 블록을 검사하며 크기가 가장 알맞는 블록을 선택한다.
가용 블록의 분할
할당기가 크기가 맞는 가용 블록을 찾으면 가용블록의 어느 정도를 할당할 지 결정해야한다.
제일 단순한 옵션은 가용 블록의 전체를 사용하는 것이다. 간단하고 빠르긴 하지만 큰 단점은 내부 단편화가 생긴다는 것이다.
가용 블록이 할당할려는 블록보다 큰 경우 필요한 만큼만 분할해서 할당하고 나머지 부분을 free 상태로 둔다.
prologue header/footer: 힙의 시작을 알리는 블록
- prologue header: 메모리 할당구조를 구성하는 블록으로써, 가장 처음 생성되는 블록, 다음과 같은 정보를 담고 있음
- 블록의 크기
- 블록의 사용 여부 (0 or 1)
- prologue footer: prologue header 다음으로 생성되는 블록으로 다음과 같은 정보를 담음
- 블록의 크기
- 블록의 사용 여부 (0 or 1)
epilogue block header: 힙의 끝을 알리는 블록
epilogue block header: heap의 끝을 나타내는 특별한 block header. -> 마지막 block의 header와 footer의 역할을 수행
epilogue block header의 크기는 0이며 이를 통해 heap의 끝을 나타냄.
footer가 필요한 이유는 block header와 연결된 block의 크기 정보를 포함하기 때문 가용블록 연결하기
오류 단편화: 할당된 블록이 반환됐을 때 인접한 곳에 가용블록이 있지만 작은 블록인 상태로 존재하는 것을 말한다. 이를 해결하기 위해 연결하는 과정이 필요하다.
연결을 하는 경우 3가지의 케이스가 있다.
- 앞 뒤 블록이 모두 할당된 상태인 경우- > 자기 자신만 free하고 끝!
- 앞 블록은 할당 상태 / 뒤 블록은 비할당상태 -> 현재 블록과 뒤의 블록을 합친다.
- 앞 뒤 블록 모두 비할당상태 -> 앞 뒤 블록 모두 합친다.
