Virtual Memory
Dynamic Memory Allocation
| 동적 메모리 할당 | 동적 메모리 할당기는 힙이라고 하는 프로세스의 가상 메모리 영역을 관리한다. 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다. 각 블록은 할당되었거나 가용한 가상 메모리의 연속적인 묶음이다. |
| 할당기 | 명시적인 할당기는 응용 프로그램이 명시적으로 할당된 블록을 반환해 줄것을 요구한다. 예를들어, C 표준 라이브러리는 malloc 패키지라고 하는 명시적 할당기를 제공한다. 반면에 묵시적 할당기들은 언제 할당한 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 단환하는지 할당기가 판단해서 free를 때려버린다. 묵시적 할당기는 가비지 컬렉터라고 알려져 있다. |
malloc and free function
| malloc, calloc, realloc | malloc 함수는 어떤 종류의 데이터 객체에 대해서 적절히 정렬된 최소 size 바이트를 갖는 메모리 블록의 포인터를 리턴한다. 32비트 모드에서는 항상 8의 배수인 블록을 리턴하고 64비트 모드에서는 16의 배수로 반환된다. 만약 malloc이 프로그램이 가용한 가상 메모리보다 더 큰 크기의 메모리 ㅂ블록을 요청하는 경우, NULL을 리턴하고 errno를 설정한다. malloc은 리턴하는 메모리를 초기화 하지 않는다. 초기화를 하려면 calloc을 사용한다. 이전에 할당된 블록의 크기를 변경하려면 realloc 함수를 사용하면 된다. |
| free | free를 선언할때 free의 인자는 malloc, calloc, realloc에서 획득한 할당된 블록의 시작점을 가르키는 포인터여야 한다. 그렇지 않다면 free는 아무런 동작을 하지 않는다. 심지어 free는 아무것도 리턴하지 않기 때문에 프로그램에 뭔가 이상이 있다는 사실을 알릴 수 있는 수단이 없다. |
| 메모리 할당 해제 | 위 그림은 16워드의 매우 작은 힙을 malloc과 free가 어떻게 관리할 수 있는지 보여준다. 1. a 프로그램은 4 워드 블록을 요청한다. malloc은 가용 블록의 앞부분에서 4워드 블록을 잘라내고, 이 블록의 첫 번째 워드를 가르키는 포인터를 리턴한다. 2. b 프로그램은 5 워드 블록을 요청한다. 이 예제에서 malloc은 가용 블록의 앞부분에서 6 워드 블록을 할당한다. 이 예제에서 malloc은 가용블록이 더블 워드 경계에 정렬되도록 하기 위해 블록에 추가적인 워드를 패딩하였다. 3. c 프로그램은 6워드 블록을 요청 4. d 프로그램은 b에서 할당된 6워드를 free 5. e 프로그램은 2 워드 블록을 요청한다. 이 경우에 malloc은 이전 단계에서 반환된 블록의 부분을 할당하고, 이 새로운 블록의 포인터를 리턴한다. |
Fragmentation
| 단편화란 | 가용 메모리가 할당 요청을 만족시킬 수 없을때 일어남. 두 종류가 있는데 내부 단편화와 외부 단편화로 나뉜다. |
| 내부 단편화 | 내부 단편화는 주로 다음과 같은 상황에서 발생한다. 1. 고정 크기 할당 : 고전된 크기의 메모리 블록에 작은 크기의 데이터를 저장할 때, 블록 내부에 사용되지 않는 공간이 발생한다. 2. 정렬과 패딩 : 데이터 구조나 시스템의 요구 사항으로 인해 메모리 블록이 정렬되거나 패딩이 추가될 경우, 추가된 공간이 발생하여 내부 단편화가 발생할 수 있다. 내부 단편화의 해결 방법은 다음과 같다. 1. 변경 가능한 할당 크기 : 메모리 블록의 크기를 변경 가능하게 설계하여, 데이터 크기에 따라 적절한 크기의 블록을 할당할 수 있도록 한다. 2. 메모리 풀 : 고정 크기의 메모리 블록을 미리 할당하여, 필요한 크기의 블록을 풀에서 가져와 사용하는 방식으로 내부 단편화를 최소화 한다. 3. 메모리 할당 전략: 할당 전략을 조절하여 내부 단편화를 최소화할 수 있다. 예를 들어, 최적의 블록 크기나 할당 방식을 선택하여 메모리 사용을 최적화한다. 4. 메모리 할당 알고리즘: 메모리 할당 알고리즘을 사용하여 내부 단편화를 최소화한다. First Fit, Best Fit, Worst Fit 등의 할당 알고리즘을 선택하여 메모리를 효율적으로 관리한다 |
| 외부 단편화 | 외부 단편화(External Fragmentation)는 메모리 할당 및 해제 과정에서 발생하는 물리적 메모리 공간의 조각화를 의미한다. 이는 연속적인 물리적 메모리 공간에 여러 조각이 분산되어 할당할 수 있는 큰 연속적인 공간이 없는 상태를 말함. 외부 단편화의 원인은 다음과 같다 1. 동적 메모리 할당: 메모리를 동적으로 할당하고 해제할 때, 연속적인 메모리 블록들이 분산되어 할당되거나 해제되면 외부 단편화가 발생할 수 있다. 2. 메모리 할당 전략: 특정 할당 전략(예: 최적 적합, 최악 적합)을 사용할 때, 블록들이 불규칙하게 분산되어 외부 단편화가 발생할 수 있다. 외부 단편화의 해결 방법은 다음과 같다. 1. 메모리 병합 (Memory Coalescing): 연속적인 가용 블록들을 병합하여 큰 연속적인 메모리 블록을 생성합니다. 2. 메모리 풀 (Memory Pool): 고정 크기의 메모리 블록을 미리 할당하여, 필요한 크기의 블록을 풀에서 가져와 사용하여 외부 단편화를 최소화한다. 3. 페이지 할당 (Page Allocation): 메모리를 페이지 단위로 할당하여, 외부 단편화를 줄이고 효율적인 메모리 사용을 지원한다. 4. 가상 메모리 관리: 가상 메모리 기법을 사용하여 물리 메모리와 가상 메모리 사이의 연속성을 확보하여 외부 단편화 문제를 완화한다. |
Implicit Free Lists
| 묵시적 가용 리스트 | 모든 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조를 필요로 한다. 대부분의 할당기는 이 정보를 블록 내에 내장한다. 위 경우에 한 블록은 1워드 헤더, 데이터, 추가적인 패딩으로 구성된다. 헤더는 블록크기와 블록이 할당되었는지 가용 상태인지를 인코딩한다. 만약 더블워드 정렬 제한조건을 부과한다면 블록 크기는 항상 8의 배수이고, 블록 크기의 하위 3비트는 항상 0이다. (bin(8) = 1000). 그래서 블록 크기의 상위 29비트만 저장할 필요가 있으며, 나머지 3비트는 다른 정보를 인코드하기 위해 남겨둔다. 그리고 그렇게 제외되는 3개의 비트에는 allocated, free의 상태를 저장하는데 사용된다. |
| 가용 블록 | 예를 들어 블록크기 24바이트를 갖는 할당된 블록이 있다고 치자. 그러면 헤더는 다음과 같이 된다. 0x00000018 | 0x1 = 0x00000019 (3비트가 기본적으로 할당되어 1개의 패딩이 필요함) 이어서 블록크기 40 바이트인 가용 블록은 다음과 같은 헤더를 갖는다. 0x00000028 | 0x0 = 0x00000028 데이터 다음에는 사용하지 않는 패딩이 따라올 수 있는데, 이들의 크기는 가변적이다. 패딩은 외부 단편화를 극복하기 위한 할당 전략의 일부분일 수 있다. 또는 정렬 요구사항을 만족하기 위해 필요할 수 있다. (B트리의 차수를 맞추기 위함) 이러한 구조를 묵시적 리스트라고 부르는데, 그것은 가용 블록이 헤더 내 필드에 의해서 묵시적으로 연결되기 때문이다. |
| 묵시적 가용 리스트의 사용 | 가용 리스트를 사용하려면 어떤 특별히 표시한 마지막 블록이 필요하다. 이 예제에서 종료하는 헤더는 할당 비트가 세트되어 있고 크기는 0을 갖는다. 묵시적 가용 리스트의 장점은 단순성이다. 중요한 단점은 할당된 블록을 배치하는 것과 같은 가용 리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례한다는 것이다. |
Placing Allocated Blocks
| 할당한 블록의 배치 | 이렇게 만들어진 블록을 저장하기 위해 충분히 큰 가용 블록을 리스트에서 검색한다. 할당기가 이 검색을 수행하는 방법은 배치 정책에 의해서 결정된다. 이 정책에는 first fit, next fit, best fit이 주로 사용된다. |
| first fit, next fit, best fit | first fit은 가용 free 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택한다. Next fit은 first fit과 비슷하지만 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작한다. Best fit은 모든 가용 블록을 검사하며 크기가 맞는 가장 작은 블록을 선택한다. |
| First fit | First fit의 장점은 리스트 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있다는 점이다. 단점은 리스트 앞부분에 작은 가용 블록들을 남겨두는 경향이 있어서 큰 블록을 찾는 경우에 검색 시간이 늘어난다는 것이다. |
| Next fit | Next fit은 first fit 에 대한 대안으로 이전 검색에서 가용블록을 발견했다면 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 아이디어에서 착안한 방법이다. Next fit은 first fit에 비해 매우 빠른 속도를 갖는데, 리스트의 앞부분이 많은 작은 크기의 조각들로 구성되면 특히 더 이런 성향을 보인다. 그렇지만, 일부 연구결과에 의하면 next fit이 first fit보다 최악의 메모리 이용도를 갖는 것으로 밝혀졌다. |
| Best fit | Best fit은 들어가야 할 프로세스의 사이즈와 가장 밀접한 블록을 선택하는 방법 결과적으로 이게 제일 좋다고 한다. |
Splitting Free Blocks
| 가용 블록의 분할 | 할당기가 크기가 맞는 가용 블록을 찾은 후에 가용 블록의 어느 정도를 할당할지에 대해 정책적 결정을 내려야 한다. 한 가지 옵션은 이 가용 블록 전체를 사용하는 것이다. 비록 간단하고 빠르지만, 단점은 내부 단편화가 생긴다는 것이다. 만일 배치정책으로 인해 크기가 잘 맞는다면, 일부 추가적인 내부 단편화는 수용할 수도 있다. 그렇지만 크기가 잘 맞지 않는다면, 할당기는 대개 가용 블록을 두 부분으로 나누게 된다. 첫번째 부분은 할당한 블록이 되고, 나머지는 새로운 가용 블록이 된다 |
Getting Additional Heap Memory
| 추가적인 힙 메모리 획득하기 | 만약 할당기가 요청한 블록을 찾을 수 없다면 메모리에서 물리적으로 인접한 가용 블록들을 합쳐서 더 큰 가용 블록을 만들어 보는것이다. 그렇지만 이래도 블록이 부족하다면 커널에게 sork 함수를 호출해서 추가적인 힙 메모리를 요청한다. 할당기는 추가 메모리를 한개의 더 큰 가용 블록으로 변환하고, 이 블록을 가용 리스트에 삽입한 후에 요청한 블록을 이 새로운 가용 블록에 배치한다. |
Coalescing Free Blocks
| 가용 블록 연결하기 | 할당기가 할당한 블록을 반환할 때, 새롭게 반환하는 블록에 인접한 다른 가용 블록들이 있을 수 있다. 이러한 인접 가용 블록들은 오류 단편화 라는 현상을 유발할 수 있으며, 이때는 작고 사용할 수 없는 가용 블록으로 쪼개진 많은 가용 메모리들이 존재한다. |
| 오류 단편화 | 37번 사진에서 메모리를 해제해서 38번 사진과 같은 상태가 되면 4워드를 요청해도 할당에 실패하게 된다. 이런 오류 단편화를 극복하기 위해 연결과정으로 가용 블록들을 통합시킨다 |
