CSAPP 9.9, 9.11

CSAPP

9.8.8 가용블록의 분할

• 할당기가 크기가 맞는 가용 블록을 찾은 후에 가용 블록의 어느정도를 할당할지에 대해 정책적 결정을 내려야 한다. 한 가지 옵션은 이 가용 블록 전체를 사용하는 것이다. 비록 간단하고 빠르지만, 큰 단점은 내부 단편화가 생긴다는 것이다. 만일 배치 정책으로 인해 크기가 잘 맞는다면, 일부 추가적인 내부 단편화는 수용할 수도 있다.
• 그렇지만 크기가 잘 안맞는다면, 할당기는 대개 가용 블록을 두 부분으로 나누게 된다. 첫 번째 부분은 할당한 블록이 되고, 새로운 가용 블록이 된다.

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

• 할당기가 요청한 블록을 찾을 수 없다면, 메모리에서 물리적으로 인접한 가용 블록들을 합쳐서(연결해서) 더 큰 가용 블록을 만들어 본다. 이렇게 해도 충분히 큰 블록이 만들어지지 않거나 가용 블록이 이미 최대로 연결 되었다면, 할당기는 커널에게 sork함수를 호출해서 추가적인 힙 메모리를 요청한다. 할당기는 추가 메모리를 한 개의 더 큰 가용 블록으로 변환하고, 이 블록을 가용 리스트에 삽입한 후에 요청한 블록을 이 새로운 가용 블록에 배치한다.

9.9.10 가용 블록 연결하기

• 할당기가 할당한 블록을 반환할 때, 새롭게 반환하는 블록에 인접한 다른 가용 블록이 있을 수 있다. 이러한 인접 가용 블록들은 오류 단편화(false fragmentation)라는 현상을 유발할 수 있으며, 이때는 작고 사용할 수 없는 가용 블록으로 쪼개진 많은 가용 메모리들이 존재한다.
• 오류 단편화를 극복하기 위해 실용적인 할당기라면 연결(coalescing)이라는 과정으로 인접 가용 블록들을 통합해야 한다. 이 과정에서는 언제 연결을 수행할지에 관한 중요한 정책 결정을 해야 한다. 할당기는 블록이 반환될 때마다 인접 블록을 통합해서 즉시 연결을 선택할 수 있다. 또는 일정시간 후 가용 블록들을 연결하기 위해 기다리는 지연 연결을 선택할 수도 있다.
• 즉시 연결은 간단하며 상수시간 내에 수행할 수 있지만, 일부 요청 패턴에 대해서는 블록이 연속적으로 연결되고 잠시 후에 분할되는 쓰래싱의 형태를 유발할 수 있다. 할당기에 대한 논의에서 즉시 연결을 가정하겠지만, 빠른 할당기들은 종종 지연 연결의 형태를 선택한다는 것을 알아야한다.

9.9.11 경계태그로 연결하기

• 현재 블록의 헤더는 다음 블록의 헤더를 가리키고 있으며, 이것은 다음 블록이 가용한지 결정하기 위해 체크 될 수 있다. 그렇다면, 그 크기는 단순히 현재 헤더의 크기에 더해지고, 블록은 상수 시간 내에 연결할 수 있다.
• 이전 블록 연결의 경우 헤더를 상용하는 묵시적 가용리스트가 주어진다면, 유일한 옵션은 현재 블록에 도달할 때 까지 전체 리스트를 검색해서 이전 블록의 위치를 기억하는 것이다. 묵시적 가용 리스트를 사용하면, 이것은 각각의 free 호출이 힙의 크기에 비례하는 시간을 소모할 것이라는 것을 의미한다. 보다 복잡한 가용 리스트의 구조를 사용하더라도 이 검색 시간은 상수가 될 수 없다.
• kunth의 경계 태그 : 상수 시간 이전 블록을 열결하게 해준다. 각 블록의 끝 부분에 풋터(footer 경계태그)를 추가하는 것으로, 풋터는 헤더를 복사한 것이다. 만일 각 블록이 이와 같은 풋터를 포함하게 되면, 할당기는 시작위치와 이전 블록의 상태를 자신의 풋터를 조사해서 결정할 수 있게 되며, 이것은 항상 현재 블록의 시작 부분에서 한 워드 떨어진 곳에 위치한다.
• 경계 태그 아이디어는 여러가지 유형의 할당기와 가용 리스트 구성에도 일반화 될 수 있는 간단하고 우아한 개념이다. 그렇지만 여기에도 잠재적인 단점이 존재한다. 각 블록이 헤더와 풋터를 유지해야 하므로 만일 응용이 많은 작은 크기의 블록을 다룬다면 상당한 양의 메모리 오버헤드가 발생할 수 있다.
• 현재 블록의 추가적인 하위 비트들 중의 하나에 이전 블록의 할당/가용 비트를 저장하려고 한다면, 할당된 블록들은 풋터가 필요 없어지고, 이 추가적인 공간을 데이터를 위해 사용할 수 있었을 것이다. 그렇지만 가용 블록은 여전히 풋터를 필요로 한다는 점에 유의해야 한다.

9.9.13 명시적 가용리스트

• 블록 할당 시간이 전체 힙 블록 수에 비례하기 때문에 묵시적 가용리스트는 범용 할당기에는 적합하지 않다.(비록 힙 블록의 수가 사전에 알려져 있고, 작고 특수한 경우에는 좋을 수도 있지만) 더 좋은 방법은 가용 블록들을 일종의 명시적 자료구조로 구성하는 것이다. 정의에 의해 가용 블록의 본체는 프로그램에서 필요하지 않기 때문에 이 자료구조를 구현하는 포인터들은 가용 블록의 본체 내에 저장 될 수 있다. 힙은 각 가용 블록내에 pred(predecessor)와 succ(successor) 포인터를 포함하는 이중 연결 가용리스트로 구성될 수 있다.
• 묵시적 가용리스트 대신에 이중 연결리스트를 사용하면 first fit 할당 시간을 전체 블록 수에 비례하는 것에서 가용 블록의 수에 비례하는 것으로 줄일 수 있다. 그렇지만 블록을 반환하는 시간은 가용 리스트 내에서 블록을 정렬하는 정책을 어떤 것을 선택하는 가에 따라 비례하거나 상수시간을 가질 수 있다.
• 한 가지 접근법은 리스트를 새롭게 반환한 블록들을 리스트의 시작 부분에 삽입해서 후입선출(LIFO)순으로 유지하는 것이다. LIFO순서와 first fit 배치 정책을 사용하면, 할당기는 대부분의 최초에 사용된 블록들을 먼저 조사한다. 이 경우 블록의 반환은 상수 시간에 수행된다. 만일 경계 태그를 사용하면 연결도 상수 시간에 수행할 수 있다.
• 또 다른 접근법은 리스트를 주소 순으로 관리하는 것으로, 리스트 내 각 블록의 주소가 다음 블록의 주소 보다 작다. 이 경우 블록의 반환은 적당한 선행블록을 찾는데 선형 검색시간을 필요로 한다.
• 명시적 리스트의 단점은 일반적으로 가용 블록들이 충분히 커서 모든 필요한 포인터 뿐만 아니라 헤더, 추가적으로 풋터까지 포함해야 한다는 점이다. 그 결과 최소 블록 크기가 커지고 잠재적인 내부 단편화 가능성까지 증가한다.

9.9.14 분리 가용 리스트

• 할당 시간을 줄이는 대표적인 방법으로 가용 블록의 수에 비례하는 시간이 필요하다. 할당 시간을 줄이는 대표적인 방법으로 알려진 분리 저장장치(segregated storage)는 다수의 가용 리스트를 유지하며, 각 리스트는 거의 동일한 크기의 블록들을 저장한다. 기본적인 아이디어는 모든 가능한 블록 크기를 크기 클래스 라고 하는 동일 클래스의 집합들로 분리하는 것이다.
• 할당기는 가용 리스트의 배열을 관리하고, 크기 클래스마다 크기가 증가하는 순서로 한 개의 가용 리스트를 가진다. 할당기가 크기 n의 블록이 필요하면 적당한 가용 리스트를 검색한다. 만일 크기가 맞는 블록을 찾을 수 없다면, 다음 리스트를 검색하는 식으로 진행된다.

9.11 C프로그램에서의 공통된 메모리 관련버그

9.11.1 잘못된 포인터의 역참조

• 한 프로세스의 가상 주소공간 내에 어떤 의미 있는 데이터로도 매핑되지 않은 큰 구멍들이 존재한다. 만일 포인터를 이 구멍들 중의 하나로 역참조 하려하면, 운영체제는 프로그램을 segmentation 예외로 종료한다. 또한, 일부 가상메모리는 읽기-가능만 허용되어 있다. 이 영역에 쓰려고 하면 보호 예외로 프로그램을 종료시킨다.

9.11.2 초기화되지 않은 메모리를 읽는 경우

• bss 메모리 위치들(초기화되지 않은 전역 C 변수들 같은)은 항상 로더에 의해 0으로 초기화 되며, 이것은 힙 메모리의 경우에는 그렇지 않다. 보편적인 에러는 힙 메모리가 0으로 초기화 한다고 가정하는 것이다.

9.11.3 스택 버퍼 오버플로우 허용하기

• 입력 스트링의 길이를 조사하지 않고 스택 상의 타깃 버퍼에 쓰려고 한다면 이 프로그램은 버퍼 오버플로우 버그를 갖게 된다.

9.11.4 포인터와 이들이 가리키는 객체들이 같은 크기라고 가정하기

• 한 가지 큰 실수는 객체를 가리키는 포인트들이 이들이 가리키는 객체들과 같은 크기라고 가정하는 것이다.

9.11.5 Off-by-One 에러 만들기

• 덮어쓰기 버그의 한 종류이다.

9.11.6 포인터가 가리키는 객체 대신에 포인터 참조하기

• C 연산자의 결합성과 우선순위에 대해 부주의하면, 포인터가 가리키는 객체 대신에 포인터를 잘못 조작하게 된다.
• 우선순위와 결합성에 대해 의심스럽다면 괄호를 사용해야 한다는 것이다.

9.11.7 포인터 연산에 대한 오해

• 또 다른 공통적인 실수는 포인터에 대한 산술연산이 반드시 이들이 가리키는 객체의 크기 단위로 수행되어야 하는 것이지 바이트 단위로 이루어지는 것이 아니라는 것이다.

9.11.8 존재하지 않는 변수 참조하기

• 더 이상 유효하지 않은 지역변수를 참조하게 되는 경우

9.11.9 가용 힙 블록 내 데이터 참조하기

• 이미 반환한 힙 블록 내 데이터를 참조한는 것이다.

9.11.10 메모리 누수 leak 유발

• 메모리 누수는 프로그래머가 할당된 블록들을 반환하는 것을 잊어서 힙에 가비지를 부주의하게 만들 때 일어나는 조용한 살인자다.
• 만일 leak이 자주 호출되면, 힙은 점차적으로 가비지로 가득 차게 되고, 최악의 경우 전체 가상 주소공간을 소모하게 된다. 메모리 누수는 특히 데몬, 서버와 같이 종료 되지 않는 프로그램들의 경우에 심각하다.