개발하는데 다 이유가 있겠지

9.9 동적 메모리 할당

동적 메모리 할당기는 힙(Heap)이라고 하는 프로세스의 가상메모리 영역을 관리

• 미초기화된 데이터 영역(bss) 직후에서 시작해서 위쪽으로(높은 주소 방향으로) 커지는 무요구 메모리 영역
• 커널은 힙의 꼭대기를 가르키는 변수 brk를 사용
• 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리(각 블록은 할당 또는 가용한 가상메모리의 연속적인 묶음)

명시적 할당기(malloc, free)

• 응용 프로그램이 명시적으로 할당된 블록을 반환해 줄 것을 요구(free)
• 할당 : malloc / 해제 : free

묵시적 할당기(garbage collector)

• 자동으로 사용하지 않은 할당된 블록을 반환시켜주는 역할을 함

---

9.9.1 malloc과 free 함수

프로그램은 malloc 함수를 호출해서 힙으로부터 블록들을 할당받음

malloc(메모리 할당)

• 주소 단위 : 8의 배수(32비트 기준) / 16의 배수(64비트 기준)
  • 일반적으로 메모리 할당자는 요청한 메모리 크기보다 조금 더 큰 블록을 할당하는 경향이 있음
    (성능 향상 및 메모리 효율적 관리를 위함)
• malloc이 문제를 만나면 Null을 리턴하고 errno를 설정
• malloc은 메모리를 초기화 하지 않음
• calloc은 메모리를 할당하고 할당된 메모리를 0으로 초기화
• realloc은 할당한 블록의 크기를 변경

malloc 함수

sbrk(힙 영역 조절)

커널의 brk포인터를 증감하여 힙을 늘리거나 줄임

성공하면 이전 brk값을 리턴 / 실패하면 -1을 리턴하고 errno를 ENOMEM으로 설정

• incr가 0인 경우 : 현재 brk값을 리턴
• incr가 음수인 경우 : 합법적이긴 하지만, 복잡해짐(잘 사용하지 않음)

sbrk 함수

free(메모리 해제, 반환)

• malloc, calloc, realloc으로 할당한 메모리를 반환함
• 댕글링 포인터 : free로 메모리를 반환 이후에도 해당 포인터를 사용하려고 함

free 함수

---

9.9.2 왜 동적 메모리 할당인가?

실제 실행시키기 전에는 자료 구조의 크기를 알 수 없는 경우가 있기 때문에 동적으로 메모리를 할당해야 함

• n번 입력받는 것을 알기 때문에 필요한 만큼만 메모리를 동적으로 할당할 수 있음
• 그렇지 않고 고정된 배열 크기라면 관리가 어려워짐

---

9.9.3 할당기 요구사항과 목표

명시적 할당기(malloc, free)들은 엄격한 제한사항 내에서 동작해야함

요구사항

1. 임의의 요청 순서 처리하기 : 프로그래머가 필요한 메모리를 원하는 순서로 할당 및 해제를 할 수 있음
2. 요청에 즉시 응답하기 : 성능을 향상시키기 위해 요청을 재정렬하거나 버퍼에 저장하지 않고 즉시 할당 요청에 응답
3. 힙만 사용하기 : 데이터를 물리적으로 떨어트려 서로 영향을 끼치지 않도록 함
   (비확장성 자료 구조 : 멀티 쓰레드 환경에서 동기화없이 여러 스레드가 접근하면 안전하지 않은 자료구조)
4. 블록 정렬하기(정렬 요건) : 크기별, 메모리 주소 순서별, 특정 요구에 따른 정렬을 할 수 있음
5. 할당된 블록을 수정하지 않기 : 블록이 할당되면 이들을 수정하거나 이동하지 않음

목표

1. 처리량 극대화하기
2. 메모리 이용도를 최대화하기

---

9.9.4 단편화

나쁜 힙 이용도의 주요 이유(내부 단편화, 외부 단편화)

내부 단편화

• 할당된 블록이 데이터 자체보다 더 클 때 발생
• 메모리 관리 효율성과 사용률이 떨어짐

외부 단편화

• 할당 요청을 만족시킬 수 있는 메모리 공간을 전체적으로 공간을 모았을 때는 충분한 크기가 있지만, 단일한 가용블록이 없는 경우
• 다음에는 얼마만큼 요구할지 모르기 때문에 측정하기 어렵고 예측이 불가능

---

9.9.5 구현 이슈

가용 블럭 구성 : 어떻게 가용 블록을 지속적으로 추적하는가?

배치 : 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?

분할 : 새롭게 할당된 블록을 가용 블록에 배치한 후 가용 블록의 나머지 부분들로 무엇을 할 것인가?

연결 : 방금 반환된 블록으로 무엇을 할 것인가?

---

9.9.6 묵시적 가용 리스트(implicit free list)

1블럭은 헤더, 데이터, 추가적인 패딩으로 구성됨

헤더에는 블록의 크기와 블록이 할당됐는지 가용한지 인코딩 내용을 담고있음

블록의 구성

특징

1. 블록 크기의 하위 3비트는 항상 0(가용 블록)
2. 최소 블록의 크기는 항상 8의 배수(짝수로 워드로 이루어짐)
3. 외부 단편화를 극복하기 위해 패딩을 사용할 수 있음
4. 특별히 표시한 마지막 블록이 있음(에필로그 헤더)

장점

• 비교적 간단한 자료구조로 구현이 가능하고, 가용한 메모리 공간을 추적하기 위한 별도의 자료구조가 필요없기 때문에 메모리 오버헤드가 적을 수 있음

단점

• 전체 리스트를 탐색해야 하기 때문에 많은 시간이 발생할 수 있음
• 반복된 할당과 해제로 인해 외부 단편화가 발생할 수 있음

---

9.9.7 할당한 블록의 배치

배치 방법에는 first fit, next fit, best fit이 있음

first fit : 가용 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택

• 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있음
• 리스트 앞부분에 작은 가용 블록들을 남겨두는 경향이 있음(큰 블록을 찾는 시간이 오래 걸림)

next fit : 이전 검색이 종료된 지점에서 검색을 시작해서 크기가 맞는 첫 번째 가용 블록을 선택

• first fit에 비해 매우 빠른 속도를 가짐
• first fit보다 최악의 메모리 이용도를 가짐

best fit : 모든 가용 블록을 검색해서 크기가 맞는 가장 작은 블록을 선택

• first fit, next fit보다는 더 좋은 메모리 이용도를 가지지만 힙을 다 검색야하기 때문에 시간이 오래 걸림

---

9.9.8 가용 블록의 분할

크기가 맞는 가용 블록을 찾은 후에 어느 정도를 할당하지를 결정해야 함

1. 요청한 크기만큼 블록을 할당
2. 나머지는 새로운 가용 블럭이 됨

---

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

힙 영역에 마땅한 가용 블록이 없다면 sbrk 함수를 통해서 추가적인 힙 메모리를 요청

할당기는 추가 메모리를 더 큰 가용 블록으로 변환하고, 이 블록을 가용 리스트에 삽입한 후에 요청한 블록을 할당

---

9.9.10 가용 블록 연결하기

free를 통해 할당된 블록을 반환할 때, 반환하는 블록에 인접한 다른 가용 블록들을 연결(coalesing)해야 함

블록이 연속적으로 연결되고, 잠시 후에 분할되는 쓰래싱의 형태를 유발할 수 있음
(쓰래싱 : 페이지 교체에 너무 많은 시간을 쏟는 것)

즉시 연결 : 블록이 반활될 때마다 인접 블록을 통합

지연 연결 : 일정 시간 후에 가용 블록들을 연결

---

9.9.11 경계 태그로 연결하기

힙 블록의 포맷

• 현재 블록의 헤더는 다음 블록의 헤더를 가리키고 있음
  현재 블록의 크기를 더하면 다음 블록의 헤더(다음 블록이 가용한지 확인할 수 있음)
• 이전 블록의 접근하기 위해서 헤더를 복사한 푸터(footer)를 추가함

 

블록 반환할 때의 4가지의 경우