0910_csapp 9장 메모리 동적 할당

week05 malloc lab 구현을 위해 csapp 9장을 정리해보자!

동적 메모리 할당

힙이라는 프로세스의 가상 메모리 영역을 관리한다.

할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다.

할당기는 두 개의 유형이 있으나 둘 다 프로그램이 블록을 명시적으로 할당해야한다. 차이점은 할당된 블록을 free 할 때 무엇이 사용되어야 하는지다.

• 명시적 할당기(Explicit allocatios) : 응용프로그램이 명시적으로 할당된 블록을 해제해야함. 예를들어 c언어의 malloc으로 할당받은 블록을 free로 해제
• 묵시적 할당기(Implicit allocators) : 할당된 프로그램에서 블록이 더이상 사용되지 않을때 할당기가 이를 감지하고 해제해야함. 예를들어 가비지 컬렉터(garbage collectors)

sbrk함수

brk (발음은 브레이크) 는 heap영역이 여기까지임을 나타내주는 포인트이다. sbrk함수는 이 brk 포인트의 위치를 밀거나 당길 수 있게 해주는 함수이다. 만약에 heap 영역 내에 더이상 할당 가능한 빈 공간이 없을때 heap 영역 자체를 늘려서 동적 메모리 할당이 가능하다. 다른 영역을 침범하는것을 예방하기 위해서, maxheap 을 지정하고 사용한다.

시스템콜

응용프로그램은 직접 하드웨어를 건드릴 수 없으며, 반드시 운영체제(커널)을 거쳐서 하드웨어를 조작해야 한다. 메모리를 할당하는 것 역시 하드웨어를 조작하는 일이기때문에 응용프로그램은 시스템 콜을 통해서 제어를 커널 모드로 넘긴 후에 메모리 할당을 할 수 있게 된다.

padding 이 존재하는 이유

cpu cycle 때문이다.

cpu가 64비트라는 뜻은 cpu 에 연결되어있는 데이터통로인 버스(bus)가 64개라는 뜻이다.

최대한 많이 받아서 처리하는것이 좋기 때문에 데이터 전송할때 8바이트로 맞춰서 보내는것.

header와 footer는 1바이트씩 차지해서 총 2바이트를 차지한다.

남는 것은 6바이트인데 만약 4바이트에 데이터가 들어오면? 나머지 2바이트는 패딩으로 처리하는 것이다.

명시적 할당기의 제약조건

1. 할당 및 해제요청에 대한 순서에 어떠한 가정도 할 수 없다.
2. 즉각적인 응답 : 할당요청에 바로 응답해야함
3. 힙만 사용
4. 블록 정렬
5. 할당된 블록 수정 금지

단편화

• 내부단편화(Internal fragmentation) 할당된 블록이 페이로드보다 더 큰 경우에 발생함.
• 외부단편화(External fragmentation) 할당 요청을 충족하기에 충분한 총 빈 메모리가 있지만, 단일 빈 블록이 요청을 처리하기에는 충분하지 않은 경우 발생함.

외부단편화가 훨씬 계산하기가 어렵다. 작은 수의 더 큰 빈 블록을 유지하려는 노력을 통해 외부단편화를 줄인다.

묵시적 가용리스트

모든 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조를 필요로 한다.

하나의 블록은 1워드 크기의 헤더, 데이터, 패딩으로 구성된다.

헤더에는 블록의 크기와 블록의 가용여부가 인코딩된다.

정렬 제한 조건이 더블워드인 경우에는 블록의 크기는 항상 8의 배수 바이트이다. 이때문에 블록 크기를 나타내는 값의 아래 3자리는 항상 0이 되는데 여기에 이 비트의 할당 상태를 표시한다.

장점 = 단순성. 힙 영역내를 순서대로 탐색하여 할당 영역과 가용영역을 탐색할 수 있다.

단점 = 힙이 커질수록 탐색 비용이 함께 비례한다.

할당한 블록을 배치하는 방법

• fist fit 가용리스트를 처음부터 순서대로 탐색하는 방법.
• next fit 가용리스트를 이전 탐색에서 할당한 블록 다음부터 탐색 시도.
• best fit 힙 영역을 전부 탐색하고 할당해야 하는 데이터가 들어갈 수 있는 가용블록 중 가장 작은 것을 찾아 할당하는것.

즉시 연결과 지연 연결

할당기가 할당했던 블록을 반환할때, 블록에 인접한 다른 가용 블록이 있을 수 있다. 이러한 가용 블록들은 정렬과 헤더 때문에 전체적으로 할당하기에 충분한 크기임에도 불구하고 메모리 할당이 불가능한 현상을 발생시키는데 이것이 오류단편화(false fragmentation)이다. 이 현상을 극복하기 위해서 연결이라는 과정으로 인접 가용 블록들을 통합해야 할 필요가 있다.

블록이 반환될때마다 인접 블록을 통합하는 즉시 연결 방식과, 일정 시간 후에 가용 블록을 연결하는 지연 연결 방식이 존재한다.

경계태그

데이터가 할당되었던 블록을 반환할때, 그 블록의 주위에 가용상태인 블록이 있다면 이를 연결해야 한다.

그러나 연결을 할때 가용상태여부를 알려면 각 블록의 헤더를 참조해야 한다.

하지만 헤더를 확인하기 위해 가용 블록의 헤더가 나올때까지 힙영역을 계속 탐색하는것은 데이터 처리 속도에 도움이 되지 않는다(시간복잡도 =O(N))

그래서 각 블록의 끝에 footer 라는 이름으로 헤더의 내용을 복사한 블록을 하나 추가하는 방식을 경계태그라고 부른다. footer는 한 워드만 움직여도 알 수 있게 된다.

명시적 가용 리스트와의 차이점

명시적 가용 리스트는 가용 블록 내부에 이전 가용 블록의 주소와 이후 가용 블록의 주소를 담고 있다는 점이 가장 큰 특징이다. 그래서 힙 내부 영역을 순서대로 탐색하여 가용영역에 메모리를 할당하는 묵시적 가용 리스트와 달리 가용영역만을 탐색하여 더 빠르게 메모리를 할당 할 수 있다.