24.09.06 CSAPP, CS

CSAPP

9.9.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이 자주 호출되면, 힙은 점차적으로 가비지로 가득 차게 되고, 최악의 경우 전체 가상 주소공간을 소모하게 된다. 메모리 누수는 특히 데몬, 서버와 같이 종료 되지 않는 프로그램들의 경우에 심각하다.

CS

스택과 힙

• 스택(stack)과 힙(heap) 저장 공간은 프로그램이 메모리를 관리하는 두 가지 주요 방식이다. 이 두 메모리 영역은 구조와 관리 방식이 다르며, 속도 차이가 있다. 일반적으로 스택이 힙보다 훨씬 빠르다. 그 이유는 두 저장 공간의 구조적 차이와 메모리 할당 방식에서 기인한다.

1. 스택과 힙의 기본 개념

• 스택(Stack)
  • 함수 호출, 지역 변수, 임시 객체 등을 저장하는 메모리 영역이다. LIFO(Last In, First Out) 구조로, 메모리 할당과 해제가 매우 빠르게 이루어진다.
• 힙(Heap)
  • 동적 메모리 할당이 이루어지는 메모리 영역이다. 프로그램 실행 중에 new 또는 malloc 같은 동적 메모리 할당 함수를 통해 메모리를 할당하고, delete 또는 free 함수로 해제한다.

2. 스택의 속도가 빠른 이유

2.1. 메모리 할당과 해제의 간단함

• 스택은 메모리를 선형적으로 사용하며, 현재 스택 포인터(stack pointer)가 가리키는 위치를 기준으로 할당과 해제가 이루어진다. 새로운 변수를 생성하거나 함수 호출이 발생하면 스택 포인터를 위로 이동시켜 공간을 할당하고, 함수가 종료되면 스택 포인터를 아래로 이동시켜 해당 공간을 해제한다.
• 스택에서의 메모리 할당과 해제는 상수 시간 복잡도 O(1)를 가지며, CPU 레지스터를 이용하여 직접적으로 처리되기 때문에 매우 빠르다.

2.2. 캐시 친화적(cache-friendly)

• 스택 메모리는 연속적으로 할당되기 때문에, CPU 캐시 메모리와 잘 맞는다. 이는 캐시 지역성(cache locality)이 높다는 것을 의미한다. 즉, 최근에 사용된 메모리 위치가 가까운 시일 내에 다시 사용될 가능성이 높다.
• 이러한 특성은 캐시 미스(cache miss)를 줄이고, 메모리 접근 속도를 높인다.

2.3. 간단한 데이터 구조

• 스택은 메모리의 시작 지점과 끝 지점을 알기 때문에, 데이터 구조가 단순하고 관리가 용이하다. 따라서 메모리 할당에 대한 추가적인 오버헤드가 거의 없다.

3. 힙의 속도가 느린 이유

3.1. 복잡한 메모리 할당과 해제

• 힙 메모리는 프로그램이 실행되는 동안 필요에 따라 메모리를 동적으로 할당하고 해제하는 방식이다. 힙 메모리는 연속적이지 않고, 비연속적으로 할당되기 때문에 메모리 단편화(fragmentation)가 발생할 수 있다.
• 힙에서 메모리를 할당하려면 메모리 할당기(memory allocator)가 적절한 크기의 블록을 찾아야 하며, 이것은 시간 복잡도가 O(1)이 아닌 O(n)에 가까운 경우가 많다.
• 메모리를 해제할 때도 해당 블록이 다른 블록과 병합되어야 할 수 있으며, 이러한 과정은 추가적인 시간적 오버헤드를 발생시킨다.

3.2. 캐시 친화적이지 않음

• 힙 메모리는 데이터가 메모리 내에서 분산되어 있다. 따라서 연속적으로 접근하는 경우가 드물고, 캐시 미스가 더 자주 발생한다.
• 이는 캐시 효율성을 저하시켜, 메모리 접근 속도를 느리게 한다.

3.3. 메모리 오버헤드와 관리 비용

• 힙 메모리는 포인터, 메모리 할당자의 데이터 구조, 메모리 블록 크기 및 상태 정보를 저장하기 위한 메타데이터가 필요하다. 이러한 메타데이터는 추가적인 메모리 오버헤드를 유발한다.
• 또한, 동적 메모리 할당 시마다 메모리 할당기에서 메모리를 관리하기 위한 로직이 실행되며, 이는 추가적인 CPU 사이클을 소비한다.