[OStudy] 7주차 - 메모리 가상화(3)

 이전 챕터까지는 메모리의 주소 변환 과정에 대해 배웠고, 가장 원시의, 기초적 바운드 기법에 대해 알아보았습니다. 이번 주차에는 이전에 언급한, 외부 또는 내부 단편화에 대한 해소를 위해, 보다 효율적으로 메모리의 빈 공간을 활용하는 기법들을 알아보겠습니다. 따라서 메모리 관리 시스템의 가장 근본적인 측면에 대해 알아보게 됩니다. 메모리 관리 시스템은, 우리가 익히 아는 Malloc과 같이 힙 페이지 관리 라이브러리부터 프로세스 주소 공간 중 일부를 관리하는 운영체제 그 자체까지 포함됩니다. 

 

가정

 본격적인 메모리 관리 시스템을 공부하기 전에, 몇가지 가정을 전제로 깔고 가겠습니다. 먼저 이번 파트에서는, malloc과 free 에서 제공하는 것과 같은 기본 인터페이스를 가정합니다. C에서의 void *malloc(size_t size) 는 프로그램이 요청한 바이트 수(size)를 받아 요청된 크기와 같거나 큰 영역을 가리키는, void 포인터로(타입이 없는) 반환합니다. free의 경우, 포인터를 인자로 전달받아 해당 영역을 해제합니다. 이때 크기 정보는 넘기지 않습니다. 이 라이브러리가 관리하는 공간을 힙(heap)이라 부릅니다. 이 힙의 빈공간을 관리할 땐 (저희가 지겹도록 했던) 링크드 리스트가 보통 사용됩니다. 이 자료 구조는 영역 내 모든 빈 청크 주소를 유지합니다. 빈 공간끼리 연결하니까요. 

이번 파트에서는 외부 단편화를 중점으로 둡니다. 할당기가 요청한 크기보다 더 큰 메모리 청크가 할당될 때, 요청된 범위 너머 사용되지 않는 공간에 대해서는 할당 범위 내부의 낭비, 즉 내부 단편화로 간주합니다. 아래를 통해 정리하겠습니다.

 

 외부 단편화(External Fragmentation) : 메모리에 할당되지 않은 작은 빈공간이 산재해 있는 현상입니다. 분명 이들의 합은 실제 배정 가능한 크기가 나오더라도, 요청이 들어왔을 때 이를 처리하지 못하게 됩니다.

내부 단편화(Internal Fragmentation) : 할당된 메모리 블록 내부에서 발생하는 낭비를 뜻합니다. 요청보다 큰 할당이 이루어졌을 때 해당 격차 만큼이 내부 단편화에 해당되게 됩니다.  

 

특히, 할당된 메모리의 경우, 타 위치로 재배치 될 수 없다고 가정합니다. malloc()을 통해 포인터를 받았을 때, 이를 free 시키기 전까진 이는 프로그램 소유의 공간으로 할당되며, 타 위치로 옮길 수 없습니다. 이는 저번 주에 진행한, 메모리 압축 기법은 이번 가정으로 인해 사용이 불가합니다.(가능하다면 매력적이겠지만, 머리아파질 것입니다..)

할당기에서 사용되는 일반적인 기법으로, 분할(Splitting)과 병합(Coalescing)이 존재합니다. 이번 챕터에서는 이에 대한 기초와, 위 언급에서 이야기했듯, free 땐 크기 정보를 넘기지 않음에도, 할당된 영역의 크기를 어떻게 쉽고 빠르게 파악할 수 있는지 다뤄보겠습니다. 가장 기초적인 기법으로는 아래의 네 가지, 최적적합, 최악적합, 최초적합, 다음적합이 존재합니다. 하나하나 다뤄보겠습니다.

 

최적적합(Best-Fit)

 최적 적합은, 말 그대로 최적의, 낭비가 적은, 즉 '할당 가능한 공간 중 가장 작은 공간에' 할당하는 기법입니다. 결국 할당 가능한 공간을 모두 알고 있어야 해당 기법의 실현이 가능합니다. 그렇기 때문에, 이 최적 청크를 알기 위하 빈 공간 리스크를 한번 순회해야합니다. 위에서 이야기했든, 가장 최적의 블록이 할당됩니다. 따라서 내부 단편화의 감소 효과가 높습니다. 하지만 전체를 순회해야 한다는 것은 큰 비용이 될 수 있습니다. 이는 이대로, 성증 저하가 야기됩니다.

최악적합(Worst-Fit)

 최악 적합은, 최적 적합과 반대로 낭비가 가장 큰, 남는 공간 중 가장 큰 역역을 할당하는 방식입니다. 가장 큰 청크를 찾아 요청한 크기만큼만 할당하고, 남는 공간을 다시 빈 공간 리스트에 저장하는 방식입니다. 언뜻 보기엔 비효율로 보입니다. 그리고 이는 실제로도 맞습니다. 최악적합은 최적적합의 남은 데이터 블록의 산개 대신, 커달한 청크로 뭉친 상태로 남기고자 합니다. 물론 여전히 전체 탐색에 대한 비용이 존재하고 일반적인 경우 최적적합의 효율이 더 높기 때문에 최악적합의 경우 아직까진 연구, 실험적인 기법이라 여길 수 있겠습니다.

 

최초적합(First-Fit)

  위의 두 기법은, 최적 또는 최악, 결국 어떠한 기준의 최대를 충족하는 조건을 판단하기 위해 리스트 전체를 순회한다는 특징을 보였습니다. 최초적합의 경우 이와는 정반대로, 최초적합은, 요청된 크기를 만족하는 불록을 식별할 시 즉시 순회를 멈추고 해당 영역으로 할당시키는 기법입니다. 이는 생각보다 매력적인 기법입니다. 우선 쉽고 빠릅니다. 찾을때까지만 돌리면 되니까요. 비효율이지 않을까 싶지만, 자주 흝는 앞쪽 영역은 계속 쪼개지고 쪼개져, 할당하기 어려운 크기까지 줄여 효율화를 노릴 수도 있습니다. 하지만 시간이 지나면 지날수록, 앞쪽 영역은 잘게 쪼개져있어 할당가능한 영역이 없어지기 때문에 탐색 시간이 점진적으로 증가합니다. 또한 이는 앞쪽에 단편화가 집중될수도 있음을 의미합니다. 

다음적합(Next-Fit)

 다음적합 기법은, 최초적합 기법에서 한번 더 발전시켜 고안된 기법입니다. 최초적합 기법은 위에서 언급했듯이, 앞 구간이면 앞 구간일수록 더 많이 탐색을 진행했기에 단편화가 더 집중되었다 설명했습니다. 그렇다면 최초적합의 장점은 그대로 가져가되, 이 단편화만 분산시킨다면 어떨까요? 다음적합이 이에 해당합니다. 최초적합처럼 최초로 조건에 부합하는 블록을 식별할 시 이를 채택합니다.하지만 이후 탐색에서 다시 처음부터 순회하는 것이 아닌, 해당 탐색을 중지한 지점부터 재탐색합니다. 이러한 방식으로 사이클을 굴리는 작업입니다. 이는 이전의 단편화 집중을 탐색 시작 지점 변경을 통해 성공적으로 분산시킵니다. 물론 단편화 자체는 없어지진 않습니다. 하지만 균등한 분산과 동시해 최초 적합과 비슷한 선능을 보장받을 수 있습니다.

 

개별 리스트(Segregated List)

  해당 부분부터는 위 기초적인 구상에 이어 보다 아이디어를 발전시킨 알고리즘과 기술들을 소개합니다. 어떤 경우는, 프로그램이 선호하는, 즉 자주 요청하는 크기가 주어져 있을 겁니다. 이전에는 전체 리스트 중, 빈 공간만 추려서 연결 리스트를 형성시켰다면, 개별 리스트는 여기서 한번 더, 크기별로 일종의 숏컷을 개설하는 기법입니다. 해당 기법은 '크기'에 최적화된 메모리 청크를 추가 관리하는 덕분에 단펴화 측면에서 굉장히 강합니다. 다만 크기별로 유지한다는 것은, 그만큼 유지해야 하는 정보가 많고 따라서 공간적 측면에서 일부 오버헤드가 발생합니다. 

 

슬랩 할당기(Slab Allocator)

 위 개별 리스트에서 한번 더 발전시킨 영역의 특수 목적 할당기인, 슬랩 할당기도 존재합니다. 커널 부팅 시, 커널 객체를 위 여러 객체 캐시(Object Cache)가 할당됩니다. 커널 객체는, 락이나 파일시스템 inode 등 자주 요청되는 자료 구조들을 말합니다. 이 객체 캐시는 지정된 크기의 객체들로 구성된 빈 공간 리스트이며, 메모리 할당이나 해제 요청을 빠르게 수행할 수 있게 하기 위해 사용됩니다. 할당된 캐시 공간이 부족하다면, 상위 메모리 할당기에 추가 슬랩(Slab)이 요청됩니다. 이 요청의 전체 크기는 페이지 크기의 N배로 요청되며, 반대로 참조 회수가 0이 될때는 이 슬랩이 회수됩니다. 특히 가상 메모리 시스템에서 더 많은 메모리가 요구될 때 이 회수가 발생합니다. 슬랩 할당기의 가장 큰 메리트는, '초기화된 상태'로 존재함에 있습니다. 기존의 개별리스트 방식은 매 객체에 대한 초기화와 반납의 과정이 존재하지만, 슬랩 할당기는 여기서 발생하는 오버헤드를 회피할 수 있어 해당 측면의 성능이 우수합니다.

 

버디 할당(Buddy Allocation)

 버디, 전우조 할당입니다. 빈 메모리 공간을 처음부터 2^n 로 거듭제곱 단위로 설정합니다. 그리고 요청이 들어왔을 때, 이를 반으로 자를 수 있는지 먼저 고려합니다. 그리고 조건이 충족되지 못할 때까지 이 과정을 반복합니다. 그렇다면 마지막에, 즉 2^n 단위에서 조건을 만족하는 최소한의 크기가 됐을 때 해당 영역으로 할당되고 이 할당 과정에서 자른 n 만큼의 빈 공간 노드들이 구별됩니다. 특히 둘로 나눠가며 찾는 과정이기에 2의 거듭제곱을 감소시키는 방식을 사용할 수 있고, 이는 비트마스크 기법을 활용해 굉장히 빠른 하드웨어 단위 시간으로 처리 가능합니다. 그리고 2 거듭제곱을 사용한다는것은 이 리스트의 인덱스를 관리하는 측면에서도 굉장히 유리하며 본인의 반대편, 즉 전우조, 버디를 즉시 파악할 수 있어 버디의 할당 여부를 빠르게 파악할 수 있습니다. 특히 이 할당 정보를 유지하는 오버헤드 또한 존재해왔는데 버디는 본인의 주소로 반대편을 즉시 연산할 수 있기에(크기만 알고 있다면) 관련 정보 유지의 오버헤드 또한 감소시킬 수 있습니다.