[TIL] 크래프톤 정글 5주차 CS:app 9(가상 메모리 & 동적 메모리 할당)

9장 가상 메모리(virtual memory)

- 한 시스템 내 여러 프로세스들이 CPU와 메인 메모리를 공유하게 되면서 여러 어려움을 겪게 된다.

 

메모리를 너무 많이 차지해서 프로세스가 중단되거나 느려질 수 있고, 메모리 손실에도 취약해질 수 있다.

 

- 더 효율적이고 에러를 적게 갖기 위해 현대의 시스템은 가상 메모리(virtual memory) VM 이라고 알려진 메인 메모리의 추상화를 제공한다.

 

- 가상 메모리는 다음과 같은 3개의 중요한 기능을 제공한다.

 

1) 메인 메모리를 디스크에 저장된 주소공간에 대한 캐시로 취급해서 메인 메모리 내 활성화된 영역만 유지하고, 필요에 따라 데이터를 디스크와 메모리 간에 전송하는 방법으로 메인 메모리를 효율적으로 사용한다.

 

2) 각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 단순화한다.

 

3) 각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호한다.

 

9.9 동적 메모리 할당(Dynamic Memory Allocation)

- 가상 메모리의 영역을 저수준의 mmap, munmap 함수를 사용해서 생성하고 삭제할 수 있지만, 추가적인 가상 메모리를 런타임에 얻어야될 때, 동적 메모리 할당기(dynamic memory allocator)를 사용하는 것이 더 편리하고 호환성이 좋다.

 

- 동적 메모리 할당기는 다음 그림의 heap이라고 하는 프로세스의 가상 메모리 영역을 관리한다.

 

- 힙은 초기화된 데이터 영역 직후에 시작해서 높은 주소 방향으로 커지는 무요구(zero-demand) 메모리 영역이다.

 

각각의 프로세스에 대해, 커널은 힙의 꼭대기를 가리키는 변수 brk(break)를 사용한다.

 

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

 

각 블록은 할당되었거나 free된(가용한) 가상메모리의 연속된 묶음이라고 보면 된다.

 

- 할당된 블록은 응용 프로그램에서 사용되기 위해 명시적으로 보존되고, 가용한(free) 블록은 응용 프로그램이 명시적으로 할당할 때까지 그 상태 그대로 남아있다.

 

이때 할당된 블록은 명시적으로 또는 묵시적으로(explicitly, implicitly) 반환될 때까지 할당된 채로 남아있다.

 

- 할당기들은 다음과 같은 2개의 기본 유형이 있다. 두 유형 모두 응용 프로그램이 블록을 명시적으로 할당하도록 요구한다.

 

· 명시적 할당기(explicit allocators)는 응용 프로그램이 명시적으로 할당된 블록을 반환해 줄 것을 요구한다.

ex) C에서 malloc으로 명시적으로 메모리 공간을 할당 받았으면, free를 이용해 명시적으로 반환해야됨(C++에서의 new와 delete가 유사)

 

· 묵시적 할당기(implicit allocators)는 할당된 블록이 언제 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 검출할 수 있을 것을 요구한다.

묵시적 할당기는 GC(garbage collector)라고 알려져있으며, 자동으로 사용하지 않은 할당된 블록을 반환시켜주는 작업을 garbage collection이라고 부른다.

(관련 정리 글 : https://jeokyong-development.tistory.com/24)

9.9.1 malloc과 free 함수

 

- malloc 함수는 블록에 들어갈 수 있는 종류의 데이터 객체에 대해 연속되어 최소 size 바이트를 갖는 메모리 블록의 포인터를 리턴한다.

 

- 실제 구현에서 연속된 것은 코드가 32비트 모드(gcc -m32)와 64비트 모드(default)에서 동작하도록 컴파일되었는지에 따라 다르다.

 

32비트 모드 : 항상 8의 배수인 블록을 리턴한다.(주소값이 항상 8의 배수)

 

64비트 모드 : 항상 16의 배수인 블록을 리턴한다.(주소값이 항상 16의 배수)

 

- 만약 malloc이 문제가 생긴다면(ex : 가용한 가상 메모리보다 더 큰 크기의 메모리 블록을 요구하는 경우), NULL을 리턴하고 errno를 설정한다.

 

- 만약 메모리 공간을 0으로 초기화하고 싶다면 calloc을, 할당된 블록의 크기를 변경하려면 realloc 함수를 사용할 수 있다.

(관련 정리 글 : https://jeokyong-development.tistory.com/23)

 

- malloc과 같은 동적 메모리 할당기는 mmap과 munmap 함수를 이용거나 sbrk 함수를 사용하여 명시적으로 힙 메모리를 할당하거나 반환할 수 있다.

 

- sbrk 함수는 커널의 brk 포인터에 incr 값을 더해 힙을 늘리거나 줄인다.

 

성공하면 이전의 brk 포인터를 반환하고, 실패한다면 -1을 리턴하고 errno를 ENOMEM으로 설정한다.

 

- 이때 incr 값이 0이면 sbrk는 현재의 brk 값을 리턴하고, 음수라면 정상 작동하지만 리턴 값(이전의 brk 값)이 새로운 힙의 탑을 지나서 abs(incr) 바이트 만큼 위를 가리키기 때문에 상황이 복잡해진다.

 

- 프로그램들은 다음과 같은 free함수를 호출해서 할당된 힙 블록을 반환한다.

 

- ptr인자는 malloc, calloc, realloc에서 나온 할당된 블록의 시작 주소를 가리켜야한다. 그렇지 않으면 정상적으로 작동하지 않는다.(반환되는 것이 없어서 잘못된 것을 알 수도 없음)

 

- 위 그림은 C 프로그램에 대해 16워드의 작은 힙을 malloc과 free가 어떻게 관리할 수 있는지를 보여준다.

 

각 박스는 4바이트 워드를 나타내고, 굵은 선의 사각형은 할당된 블록을, 하얀색 사각형은 가용 블록을 나타낸다.

 

(a) 프로그램이 4워드 블록을 요청하고, malloc이 가용 블록의 앞부분에서 4워드 블록을 잘라내고, 해당 블록의 첫 번째 워드를 가리키는 포인터를 리턴한다.

 

(b) 프로그램이 5워드 블록을 요청하고, malloc이 가용 블록의 앞부분에서 6워드 블록을 할당한다.(이 장에서 allocator가 8바이트 더블 워드 경계의 블록을 리턴한다고 가정한다.) 더블 워드를 맞추기 위해 1워드를 추가로 할당하여 패딩했다.

 

(c) 프로그램이 6워드 블록을 요청하고, malloc은 가용 블록에서 6워드 블록을 잘라내 할당한다.

 

(d) 프로그램이 (b)에서 할당된 6워드 블록을 반환해준다. free를 했음에도 포인터 p2는 여전히 malloc에서 반환된 블록을 가리킨다.

p2가 새로운 malloc 콜에 의해 다시 초기화될 때까지 p2를 사용하지 않아야한다.

 

(e) 프로그램이 2워드 블록을 요청하면, malloc이 이전 단계에서 반환된 블록의 부분을 할당하고, 이 새로운 블록의 시작 부분을 가리키는 포인터를 리턴한다.

9.9.2 왜 동적 메모리 할당인가?

- 동적 메모리 할당을 사용하는 가장 중요한 이유는 프로그램을 실행시키기 전에 사용할 자료 구조의 크기를 알 수 없는 경우들이 있기 때문이다.

 

- 위 그림처럼 정해진 크기 MAXN 만큼을 할당하는 것은 MAXN보다 더 큰 파일을 읽으려 한다면 MAXN을 다시 키워서 컴파일하는 방법 밖에 없어 관리하는데 어렵다.

 

- 따라서 위와 같이 n 값을 알 수 있을 때 배열을 런타임에 동적으로 할당하는 것이 더 나은 방법이다.

 

배열의 최대 크기는 가용한 가상메모리의 크기에 의해서만 제한된다.

9.9.3 할당기(Allocators) 요구사항과 목표

- 명시적 할당기들은 다음과 같이 엄격한 제한 사항 내에서 동작해야 한다.

 

· 임의의 요청 순서 처리하기 : 응용 프로그램은 각각의 가용 요청이 이전의 할당 요청에 의해 현재 할당된 블록에 대응되어야 한다는 제한 사항을 만족하면서 임의의 순서로 할당과 반환 요청을 할 수 있다.

 

그래서 할당과 반환 요청의 순서에 대해 아무런 가정을 할 수 없다.

ex) 할당 요청을 받은 뒤 바로 대응되는 반환 요청이 온다는 가정을 할 수 없다.

 

· 요청에 즉시 응답하기 : 할당기는 할당 요청에 즉시 응답할 수 있어야한다. 할당기는 성능 향상을 위해 요청들의 순서를 바꾸거나 미룰 수 없다.

 

· 힙만 사용하기 : 할당기가 확장성을 갖기 위해, 할당기가 사용하는 비확장성 자료 구조들은 힙에 저장되어야 한다.

 

· 블록 정렬하기(정렬 요건) : 할당기는 블록들이 어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬해야한다.

 

· 할당된 블록을 수정하지 않기 : 할당기는 가용 블록을 조작하거나 변경할 수만 있다. 어떤 블록이 할당되면 그 블록을 수정하거나 이동하지 않는다.

따라서 할당된 블록들을 압축하는 것 같은 기법들은 허용되지 않는다.

 

- 위와 같은 제한 사항들을 가지고 작업하기 위해 할당기 개발자는 처리량과 메모리 이용도를 최대화하려는 상충되는 다음과 같은 성능 목표를 달성하려 한다.

 

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

·  할당과 반환 요청들을 만족시키기 위한 평균 시간을 최소화해서 처리량을 최대화한다.

 

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

·  한 시스템에서 모든 프로세스에 의해 할당된 가상메모리의 양은 디스크 내의 스왑 공간에 의해 제한된다.

 

· 가상 메모리는 효율적으로 사용해야 하는 유한한 자원이다. 큰 크기의 메모리 블록을 할당해주고 반환하는 동적 메모리 할당기의 경우 특히 그러하다.

 

· 할당기가 힙을 얼마나 효율적으로 사용하는지를 규정하는 가장 유용한 단위는 최고 이용도(peak utilization)이다.

 

다음과 같은 n개의 할당, 반환 요청의 배열이 주어졌다고 하자.

 

 

만약 어떤 응용 프로그램이 p 바이트 블록을 요청하면, 할당된 블록은 데이터 p 바이트를 갖는다.

 

요청 R_k가 완료된 후에 종합 데이터 P_k는 현재 할당된 블록들의 데이터들의 합이고, H_k는 현재 (단조 증가하는) 힙의 크기를 나타낸다.

 

할당기의 목적은 최고 이용도 U_n-1 을 전체 배열에 대해 최대화하는 것이다.

 

하지만 위의 식에서 알 수 있듯, 처리량과 이용도를 동시에 최대화시키는 것은 불가능하므로 둘 사이의 적절한 가운데 값을 찾는 것이 중요하다.

9.9.4 단편화(Fragmentation)

- 안좋은 힙 사용의 주요 이유는 단편화(fragmentation)라고 알려진 현상인데, 이는 가용 메모리가 할당 요청을 만족시키기에는 가용한 공간이 부족할 때 일어난다.

 

- 단편화는 다음과 같은 두 가지 종류가 존재한다 : 내부 단편화, 외부 단편화

내부 단편화(Internal Fragmentation)

- 내부 단편화는 할당된 블록이 데이터 자체보다 더 클 때 일어난다.

ex) 그림 9.34(b)에서 볼 수 있듯이 요청하는 크기는 5 블록이지만 실제 할당된 블록은 6 블록이다.

 

- 내부 단편화는 할당된 블록의 크기와 저장된 데이터의 차이의 합으로 정량화할 수 있다.

 

따라서 내부 단편화는 이전에 요청한 패턴과 할당기의 구현(그림 9.34의 예처럼 더블 워드 기준으로 할당하는 것과 같은 것들)에 대해서만 의존한다.

외부 단편화(External Fragmentation)

- 외부 단편화는 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때에는 충분한 크기가 존재하지만, 해당 요청을 처리할 연속된 가용 블록은 없는 경우에 발생한다.

ex) 그림 9.34(e)에서 2 워드 요청이 아닌, 8 워드 요청이었다면 힙에 8개의 가용 워드가 남았지만 커널에서 추가적인 가상메모리를 요청하지 않으면 만족시킬 수 없다.

 

- 외부 단편화는 이전 요청의 패턴과 할당기 구현에만 의존하는 것이 아니라 미래의 요청 패턴에도 의존하기 때문에 측정하기가 어렵다.

 

따라서 할당기들은 대부분 많은 수의 더 작은 가용 블록들 보다는 더 적은 수의 큰 가용 블록들을 유지하려는 방법들을 채택하고 있다.

9.9.5 구현 이슈

- 처리량과 이용도 사이에 좋은 균형을 갖는 실용적인 할당기는 다음 이슈들을 고려해야 한다.

 

· 가용 블록 구성(Free block organization) : 어떻게 가용 블록을 지속적으로 추적하는가?

 

· 배치(Placement) : 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?

 

· 분할(Splitting) : 새롭게 할당한 블록을 가용 블록에 배치한 후 가용 블록의 나머지 부분들로 무엇을 할 것인가?

 

· 연결(Coalescing) : 방금 반환된 블록으로 무엇을 할 것인가?

9.9.6 묵시적 가용 리스트(Implicit Free Lists)

- 대부분의 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 정보를 블록 내에 저장한다.

 

- 위 그림은 블록에 데이터를 저장하는 하나의 예시이다.

 

이 경우 한 블록은 1워드 헤더, 데이터, 추가적인 패딩으로 구성된다.

 

· 헤더는 블록 크기(헤더와 추가적인 패딩 포함)와 블록이 할당되었는지 가용 상태인지를 인코딩한다.

ex) 만약 더블 워드 정렬 제한 조건이 있다면 블록 크기는 항상 8의 배수이고, 블록 크기의 하위 3비트는 항상 0이다.

 

이 때, 하위 3비트를 남겨두는 이유는 메모리 블록과 관련된 추가적인 정보를 저장하기 위해 사용하기 위해서이다. 이 정보는 메모리 블록의 상태를 나타내거나 할당된 블록인지 여부, 특정 플래그 등이 될 수 있다. 이렇게 하면 블록 크기의 저장 공간을 최대한 활용하면서 필요한 메타데이터를 함께 저장할 수 있다.

 

위 그림의 경우 가장 최소의 비트만 할당 여부를 나타내기 위해 사용하고 있다.

 

ex) 24바이트(0x18)의 블록 크기를 갖는 할당된 블록이 있을 때 헤더는 다음과 같다.

 

ex) 40바이트(0x28)의 블록 크기를 갖는 가용 블록은 다음과 같은 헤더를 갖는다.

 

- 헤더 다음에는 응용 프로그램이 malloc을 호출했을 때 요구한 데이터가 따라오고, 그 다음에는 사용하지 않는 패딩이 올 수 있다.

 

패딩의 크기는 가변적으로, 패딩을 외부 단편화를 극복하기 위한 수단으로 사용할 수도 있고, 정렬 요구 사항을 만족하기 위해 사용할 수도 있다.

 

 

- 그림 9.35와 같은 블록 포맷이 주어졌을 때, 힙을 연속된 할당, 가용 블록의 배열로 위와 같이 구성할 수 있다.

 

- 위와 같은 구조를 묵시적 리스트라 부르는데, 이는 가용 블록이 헤더 내 필드에 의해 묵시적으로 연결되기 때문이다.(블록 크기를 통해 다음 블록으로 연결될 수 있음)

 

- 묵시적 리스트의 장점으로는 단순성이 있고, 단점으로는 할당된 블록을 배치할 때와 같이 가용 리스트를 탐색해야 할 때, 그 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례한다는 점이 있다.

 

- 시스템의 정렬 요구 조건과 할당기의 블록 포맷 선택이 최소 블록 크기를 결정한다.

9.9.7 할당한 블록의 배치

- 응용 프로그램이 할당기에 블록을 요청할 때, 할당기는 해당 블록을 저장하기에 충분한 크기를 갖고 있는 가용 블록을 찾아야 한다.

 

해당 검색을 수행하는 방법으로 first fit, next fit best fit이 있다.

First fit

- 가용(free) 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택한다.

 

- 장점 : 리스트의 마지막에 가장 큰 가용 블록을 남겨두는 경향이 있다.

  단점 : 리스트의 앞 부분에 작은 가용 블록을 남겨두는 경향이 있어 큰 블록을 찾는 경우에 검색 시간이 늘어난다.

Next fit

- first fit과 비슷하지만 검색을 이전 검색이 종료된 지점부터 시작한다는 것이 다르다.

 

- 장점 : first fit에 비해 매우 빠른 속도를 갖는다.(리스트의 앞 부분이 많은 작은 크기의 조각들로 구성되면 더 빠르다.)

  단점 : first fit보다 메모리 이용도가 안좋다.

Best fit

- 모든 가용 블록을 검사하며 크기가 맞는 가장 작은 블록을 선택한다.

 

- 장점 : 메모리 이용도가 위 2개에 비해 좋다.

  단점 : 힙을 완전히 다 검색해야 하기 때문에 검색 시간이 가장 길다.

 

 

- 힙을 전부 검색하지 않는 best-fit을 단순화 시킨 다단 가용 리스트 조직(segregated free list)라는 것이 존재한다.

9.9.8 가용 블록의 분할

- 할당기는 크기가 맞는 가용 블록을 찾은 후에 어느 정도를 할당할지에 대해 정책적 결정을 내려야 한다.

 

만약 단순히 가용 블록 전체를 사용하게 되면 내부 단편화가 생길 수 있다.

(크기가 잘 맞는다면 어느 정도 수용이 가능하다)

 

- 크기가 맞지 않는다면 할당기는 가용 블록을 두 부분으로 나눠 첫 번째를 할당한 블록으로, 나머지를 새로운 가용 블록으로 만든다.

 

- 위 그림은 그림 9.36의 8워드 가용 블록을 분할하여 응용 프로그램이 요청한 3워드 힙 메모리 할당을 어떻게 만족시키는지 보여준다.

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

- 만약 할당기가 요청한 크기의 블록을 찾지 못하면 다음과 같은 방법이 존재한다.

 

1) 메모리에서 물리적으로 인접한 가용 블록들을 연결하여 더 큰 가용 블록을 만든다.

 

2) 1과 같이 해도 안된다면 커널에게 sork 함수를 호출하여 추가적인 힙 메모리를 요청한다. 그렇게 받은 추가 메모리를 한 개의 큰 가용 블록으로 변환하고 가용 리스트에 삽입한 후에 요청한 블록을 새로운 가용 블록에 배치한다.

9.9.10 가용 블록 연결하기

- 할당기가 할당한 블록을 반환할 때, 해당 블록에 인접한 다른 가용 블록이 있을 수 있다.

 

그러한 인접한 가용 블록들은 오류 단편화(false fragmentation)라는 현상을 유발할 수 있고, 해당 현상이 일어나면 너무 작아 사용할 수 없을 크기의 가용 블록들로 쪼개진 가용 메모리가 존재한다.

 

- 위 그림은 그림 9.37에서 할당한 블록을 반환한 결과를 보여준다.

 

위와 같이 되면 각각 3워드의 데이터를 갖는 두 개의 인접한 블록이 생기게 되어 4워드를 요청하게 되면 4워드 블록을 넣을 만한 공간을 찾지 못해 실패하게 된다.

 

- 오류 단편화를 극복하기 위해 연결(coalescing)이라는 과정으로 인접 가용 블록들을 합병해야 한다.

 

Coalescing을 할 때 2가지 정책을 선택할 수 있다.

 

1) 블록이 반환될 때 마다 인접 블록을 통합하는 즉시 연결

 

2) 일정 시간 후에 가용 블록들을 연결하기 위해 기다리는 지연 연결

ex) 할당기가 일부 할당 요청이 실패할 때까지 연결을 지연할 수 있고, 그 후 전체 힙을 검색해서 모든 가용 블록들을 연결할 수 있다.

 

- 즉시 연결은 간단하고, 상수 시간 내에 수행할 수 있지만, 일부 요청 패턴에 대해서는 블록이 반복해서 연결되고 바로 분할되는 쓰래싱(thrashing) 형태를 유발할 수 있다.

Thrashing(쓰래싱)이란?

페이지 부재율(page fault)이 증가하여 CPU 이용율이 급격하게 떨어지는 현상을 얘기한다.

 

쓰래싱이 발생하는 이유는 프로세스를 처리하는 시간보다 메모리에 적재되지 못한 페이지로 인하여 페이지 교체에 드는 시간이 증가하게 되고 그로 인해 CPU 이용율이 떨어지게 된다.

 

- 그림 9.38에서 3워드 블록을 반복해서 할당하고 반환하는 과정이 불필요한 분할과 연결을 유발하여 CPU 이용율을 급격히 떨어뜨리는 것이다.

9.9.11 경계 태그로 연결하기(Coalescing with Boundary Tags)

- 만약 할당기가 단순히 묵시적 가용 리스트의 헤더 데이터들을 이용하여 반환하려는 블록과 다음 가용 블록을 연결할 때에는 상수 시간이 소요되지만, 이전 블록과 연결하려 한다면 전체 리스트를 검색해야 하므로 어떤 구조를 사용해도 free 호출이 힙의 크기에 비례하는 시간을 소모할 것이다.

 

- 경계 태그(Boundary Tags)라는 기법을 사용하면 상수 시간에 이전 블록과 현재 블록을 연결할 수 있다.

 

위 그림에 나오듯이 각 블록의 끝 부분에 풋터(footer => 경계 태그)를 추가하는 것으로, 풋터는 헤더를 복사한 것과 같다.

 

위와 같이 풋터를 포함하게 되면, 할당기는 시작 위치와 이전 블록의 상태를, 이전 블록의 풋터를 조사함으로써 결정할 수 있게 된다.(풋터는 항상 시작 부분에서 한 워드 떨어진 곳에 위치하게 된다.)

 

- 할당기가 현재 블록을 반환할 때, 다음 네 가지 경우가 가능하다.

 

1. 이전과 다음 블록이 모두 할당되어 있는 경우

2. 이전 블록은 할당 상태, 다음 블록은 가용 상태인 경우

3. 이전 블록은 가용 상태, 다음 블록은 할당 상태인 경우

4. 이전 블록과 다음 블록 모두 가용 상태인 경우

 

위 그림에서 각 경우에 대한 것을 확인할 수 있다.

 

Case 1) 인접 블록이 모두 할당 상태이므로 바로 coalescing(연결)이 가능하다. 따라서 바로 현재 블록이 할당 상태에서 가용 상태가 된다.

 

Case 2) 현재 블록은 다음 블록과 통합된다. 현재 블록의 헤더와 다음 블록의 풋터는 현재와 다음 블록의 크기를 합친 것으로 갱신된다.

 

Case 3) 이전 블록이 현재 블록과 통합된다. 이전 블록의 헤더와 현재 블록의 풋터는 각각의 크기를 합한 값으로 갱신된다.

 

Case 4) 세 블록 모두 하나의 가용 블록으로 통합되고 이전 블록의 헤더와 다음 블록의 풋터는 세 블록의 크기를 합한 것으로 갱신된다.

 

모든 case에서 연결(coalescing)은 상수 시간에 이루어진다.

경계 태그의 단점

- 응용 프로그램이 많은 작은 크기의 블록을 다룬다면 상당한 양의 메모리 오버헤드가 발생할 수 있다.

 

ex) 어떤 그래프 응용 프로그램이 malloc과 free를 반복해서 호출하여 그래프의 노드들을 만들었다가 없애는 것을 한다면, 각 그래프의 노드는 메모리에 단 몇 개의 워드 만을 필요로 하지만, 헤더와 풋터가 할당된 블록의 절반을 차지할 것이다.

 

- 이는 할당된 블록에 이전 블록의 할당 / 가용 비트를 저장하면 할당된 블록들에 풋터는 필요가 없어지게 되므로 경계 태그를 최적화할 수 있다.(가용 블록에는 여전히 풋터가 필요하다.)

9.9.13 명시적 가용 리스트(Explicit Free Lists)

- 묵시적 가용 리스트를 사용하면 블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 범용 할당기에는 적합하지 않다.(특정 상황에는 이게 더 유리할 수 있다.)

 

따라서 가용 블록들을 명시적 자료구조로 구성하면 더 좋은 방법이 될 수 있다.

 

- 가용 블록의 body는 필요하지 않기 때문에 위 그림과 같이 각 가용 블록 안에 전임자 predecessor와 후임자 successor을 가리키는 포인터를 포함하는 이중 연결 가용 리스트로 구성할 수 있다.

 

이 방식을 사용하면 first fit 할당 시간을 전체 블록의 수에 비례하게 하는 것이 아닌, 가용 블록의 수에 비례하는 것으로 줄일 수 있다.

 

하지만 블록을 반환하는 시간은 블록을 정렬하는 정책에 따라 비례하거나 상수 시간을 가질 수 있다.

 

1) 새롭게 반환된 블록들을 리스트의 시작 부분에 삽입해서 후입선출(LIFO) 순으로 유지 하는 방법

 

LIFO와 first fit 배치 정책을 이용하면, 할당기는 최근에 사용된 블록들을 먼저 조사하게 된다. 이 경우 반환은 상수 시간에 수행된다.

 

경계 태그를 사용하게 되면 연결 또한 상수 시간에 수행된다.

 

2) 리스트를 주소 순으로 관리하는 방법(리스트 내 각 블록의 주소가 다음 블록의 주소보다 작게 함)

 

이 경우는 블록을 반환할 때 적당한 선행 블록을 찾는 데 선형 검색 시간(O(n))을 필요로 한다.

 

대신, 주소 순서를 사용하는 first fit이 LIFO 순서를 사용하는 경우보다 best fit에 근접하는 메모리 이용도를 가진다.

 

 

- 명시적 리스트의 단점은 가용 블록들이 충분히 커서 모든 필요한 포인터 뿐만 아니라 헤더, 풋터까지 모두 포함할 수 있어야한다는 점이다.

그 결과, 최소 블록 크기가 커지고 잠재적인 내부 단편화 가능성이 증가한다.

9.9.14 분리 가용 리스트(Segregated Free Lists)

- 분리 저장 장치(segregated storage)는 다수의 비슷한 크기의 가용 리스트를 유지하며 할당 시간을 줄일 수 있다.

 

- 기본적인 아이디어는 모든 가능한 블록 사이즈들을 size class(크기 클래스)라 하는 동일한 클래스의 집합들로 분리하는 것이다.(같은 크기 or 특정 범위의 크기를 갖는 블록들을 하나의 클래스라고 생각하면 됨)

 

크기 클래스를 정의하는 것은 다양한 방법들이 존재한다.

 

ex1) 블록 크기를 2의 제곱들로 정할 수 있다.

이 예시의 경우 3, 4의 블록 크기를 갖는 것들이 같은 클래스, 5~8의 크기를 갖는 것들이 같은 클래스가 된다.

 

 

ex2) 다음과 같이 크기가 작은 블록들은 자신의 크기 클래스에 할당하고, 큰 블록들은 2의 제곱으로 분리할 수 있다.

 

 

- 할당기는 위와 같은 가용 리스트의 배열을 관리하고, 크기 클래스마다 한 개의 ㅋ가용 리스트를 가진다.

 

할당기가 크기 n의 블록이 필요하면 적당한 가용 리스트를 검색하는데, 만약 크기가 맞는 블록이 없으면 다음 리스트를 검색하는 식으로 진행된다.

간단한 분리 저장장치(Simple Segregated Storage)

- 간단히 설명하면 각각의 크기 클래스에 속한 블록들은 해당 크기 클래스의 가장 큰 원소의 크기를 갖게 되는 방식이다.

ex) 어떤 크기 클래스가 {17 ~ 32}로 정의되었다면, 이 클래스에 대한 가용 리스트는 모두 크기 32의 블록으로 구성된다.

 

- 어떤 크기의 블록을 할당하기 위해 적절한 가용 리스트를 찾았을 때, 만약 가용 리스트가 비어있지 않다면(free 블록이 있다면) 첫 번째 블록의 전체를 할당한다.

 

- 가용 블록들은 할당 요청을 만족시키기 위해 분할되지 않는다.

 

- 만약 리스트가 비어있다면(가용 블록이 없다면) 할당기가 운영체제로부터 고정 크기의 메모리를 추가로 요청하고(대부분 여러 종류의 페이지 크기로 요청함), 이 메모리를 동일한 크기의 블록으로 나누고 연결하여 새로운 가용 리스트를 만든다.

 

- 반환할 때에는 해당 가용 리스트의 맨 앞에 삽입한다.

 

- 장점

블록 할당과 반환이 상수 시간 연산이다.

 

메모리 블록의 동일한 크기, 분할 불가, 연결 불가 등의 규칙 덕분에 블록당 오버헤드가 거의 없다.

(블록의 주소로 크기를 추정할 수 있고, 연결 작업이 없어 헤더에 할당 / 가용 태그가 필요없다. 따라서 헤더와 풋터도 필요하지 않다.)

(가용 블록들도 1워드 succ 포인터(다음 블록을 가리키는 포인터)만이 필요하여 최소 블록 크기가 1워드이다.)

 

- 단점

내부, 외부 단편화에 취약하다.

(내부 단편화는 가용 블록들이 분할되지 않기 때문에, 외부 단편화는 가용 블록들이 연결되지 않기 때문에 생긴다.)

분리 맞춤(Segregated Fits)

- 여러 크기의 블록들이 하나의 클래스에 포함될 수 있다.(위의 ex1과 같음)

 

- 어떤 크기의 블록 할당을 요청 받으면, 크기 클래스를 결정하고 해당 클래스에서 first-fit 방식으로 검색한다.

 

만약 블록을 찾으면 해당 블록에 할당한 뒤, 만약 크기가 좀 남는다면 분할하여 분할된 블록을 적절한 클래스에 삽입한다.

 

- 적당한 크기의 블록을 못 찾으면 추가적인 힙 메모리를 운영체제에 요청해 새 힙 메모리에서 이 블록을 할당하고 나머지를 적절한 크기의 클래스에 배치한다.

 

- 블록을 할당하고 분할하여 다른 클래스에 배치하기 때문에 first-fit 방식으로 검색함에도 best-fit과 같은 효과를 낼 수 있다.

버디 시스템(buddy system)

- 버디 시스템은 각 크기 클래스가 2의 제곱인 분리 맞춤의 특수한 경우이다.

 

- 어떤 크기의 블록 할당을 요청 받으면 해당 블록을 담을 수 있는 최소 크기의 블록이 나올 때까지 절반으로 분할한다.

ex) 100의 크기의 블록 할당을 요청 받고, 현재 가용 블록의 크기가 2^10(1024) 라면 128의 가용 블록이 나올 때까지 분할한 뒤 128에 할당

 

- 이 때, 분할되는 가용 블록들끼리 버디 주소를 계산하기 쉽다는 것이 버디 시스템의 핵심 사항이다.

ex) 1024 블록을 절반으로 나누면 해당 블록의 주소는 x0000000000 과 x1000000000로, 특정 비트 하나만 다르게 된다. 이 경우는 512에 해당하는 9번 째 비트만 다르게 됨

 

- 장점

빠른 검색과 연결

 

- 단점

블록 크기가 2의 제곱이기 때문에 내부 단편화를 유발할 수 있다.

 

따라서 범용 부하에 대해서 부적당하지만, 특정 상황에서는 유용하게 사용될 수 있다.