06_week_C_malloc_2

해당 정리 내용은 CSAPP를 정리하는 부분입니다.

9.9.2 왜 동적메모리를 사용해야하는가

동적메모리를 사용하지 않는 가장 간단한 방법은 최대 배열 크기를 갖는 정적 배열로 정의하는 것
이는 때로는 나쁜 방법이 될 수 있음

만일 프로그램의 사용자가 정해진 배열의 크기보다 더 큰 파일을 읽으려고 한다면, 유일한 대책은 프로그램의 배열을 더 크게 만들고 다시 컴파일 하는 것 뿐

이를 해결하기 위해서 컴파일이 아닌 런타임시에 동적으로 공간을 할당하는 것
메모리를 런타임시에 동적으로 할당하게 된다면 최대 크기는 가용한 가상메모리의 양에 의해서만 제한됨

9.9.3 할당기 요구사항과 목표

explicit allocator는 엄격한 제한사항 내에서 동작

• 임의의 요청 순서 처리하기: application 이전에 allocate request로 부터 얻은 현재 allocated blok과 일치해야한다는 제약에 따라 임의의 allocate 순서를 만들고 해제를 요청할 수 있다. 따라서, alloactor는 할당 순서와 해제 요청에 대하여 어떠한 가정도 할 수 없습니다.
  예를들면, allocator는 모든 allocate 요청이 해제 요청과 동반되거나 allocae와 free 요청이 중첩되었다고 가정할 수 없습니다.
• 요청에 즉시 응답하기: allocator는 allocate 요청에 즉시 응답해야함. 따라서, allocator는 성능을 향상시키기 위해 요청을 다시 정렬하거나 버퍼링할 수 없음
• heap만 사용하기: 확장성을 갖기 위해서 allocator가 사용하는 비확장성 자료 구조들은 heap자체에 저장되어야함
• 블록 정렬하기(alignment requirement): allocator는 data 개체를 보유할 수 있는 방식으로 block을 정렬해야함
• 할당된 블록을 수정하지 않기: allocator는 사용 가능한 block만 조작하거나 변경할 수 있음. 특히, 일단 할당된 block은 수정하거나 이동할 수 없음, 따라서, 할당된 block의 압축 같은 기술은 허용되지 않음

이런 제한사항들을 가지고 개발자는 처리량과 메모리 이용도를 최대화하려는 상충되는 성능 목표를 달성하기 위해 노력함

목표 1: 처리량 극대화하기

allocate request 의 최악의 케이스의 running time 이 free block 의 수에 선형적이고 해제 요청의 실행 시간이 일정한 경우, 합리적으로 우수한 성능을 갖니 allocator를 개발하는 것은 어렵지 않음

목표 2: 메모리 이용도를 최대화하기

가상메모리가 무한자원은 아님
한 시스템에서 모든 프로세스에 의해 할당된 가상메모리의 양은 디스크 내의 스왑 공간의 양에 의해 제한됨
allocator가 heap을 얼마나 효율적으로 사용하는지를 규정하는 많은 방법이 있음
그 중 가장 유용한 단위는 peak utilization 임.

최고 이용도는 $U_k$ 로 나타냄

allocator의 목적은 peak utilization $U_n-1$ 을 전체 배열에 대해서 최대화 하는 것
특히, heap 이용도를 희생해서 처리량을 최대화하는 allocator를 작성하는 것은 쉬움
allocator 설계에서 중요한 점은 이 두 가지 목표 사이에 적절한 균형을 찾는 것

9.9.4 단편화 (fragmentation)

나쁜 heap 이용도의 주요 이유는 fragmentation 이라고 알려진 현상

• 내부 단편화(internal fragmentation) : 할당된 블록이 데이터 자체보다 더 클때 일어남

• 내부 단편화는 payload와 할당된 블록의 크기의 차이들의 합으로 간단화할 수 있음

• 내부 단편화의 양은 al- locator 구현과 이전 requests의 패턴에만 의존함

  ex) 그림 9.34(b)

• 외부 단편화(External fragmentation) : 할당 요천을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는 충분한 크기가 있지만, 요청을 처리할 수 있는 단일한 가용블록은 없는 경우

• 또한, 외부 단편화는 내부단편화보다 더 측정하기 어려움
  --> 이전 요청의 패턴 뿐만 아니라 미래 요청 패턴에도 의존하기 때문

  ex)이전에는 지속적인 4워드 사용으로 문제가 없었지만 앞으로 들어온 워드의 크기를 알 수 없음 (미래 요청 패턴에도 의존함)

  
  ex) 그림 9.34(e)에서 2워드 요청이 아닌 8워드 일 경우 전체로 봤을땐 8워드가 있지만 커널에서 추가적인 가상 메모리를 요청하지 않고는 요청을 만족시킬 수 없음

9.9.5 구현 이슈

가장 간단히 생각할 수 있는 것은
1. 하나의 커다란 바이트의 배열
2. 이 배열의 첫번째 바이트를 가리키는 포인터 p로 구성 가능

위 두 가지만 생각하게 된다면 처리량은 매우 좋지만 메모리 이용도는 아주 안좋을 수 있음

따라서 다음 이슈들을 고려해야함

1. 가용 블록 구성 : 어떻게 가용 블록을 지속적으로 추적하는가?
2. 배치 : 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?
3. 분할 : 새롭게 할당한 블록을 가용 블록에 배치한 후 가용 블록의 나머비 부분들로 무엇을 할 것인가?
4. 연결 : 방금 반환된 블록으로 무엇을 할 것인가?