[시스템 프로그래밍] 가상메모리[4] - 분리 가용 리스트(Segregated Free List)

 

 

 

 

🧐 분리 가용 리스트(Segregated free list)

이전 글들에서 살펴본 것과 같이 가용 블록 리스트를 단 한개만 사용하는 할당기는 한 개의 블록을 할당하는 데 블록의 수(혹은 가용 블록의 수)에 비례하는 시간이 필요합니다.

 

할당 시간을 줄이는 대표적인 방법으로 알려진 분리 저장장치(Segregated Storage)는 다수의 가용 리스트를 유지하며, 각 리스트는 거의 동일한 크기의 블록들을 저장합니다.

 

기본적인 아이디어는 모든 가능한 블록의 크기를 크기 클래스(size class)라고 하는 동일 클래스의 집합으로 분리하는 것입니다.

 

 

크기 클래스를 정의하는 방법에는 여러 가지가 있습니다.

 

대부분 적은 크기의 블록들은 매 크기마다 클래스를 갖도록 합니다.(2, 3, 4, ...)

크기가 큰 경우에는 2의 제곱마다 클래스를 정의합니다. (1025 ~ 2048, 2049 ~ 4096, ...)

 

 

할당기는 가용 리스트의 배열을 관리하고, 크기 클래스마다 증가하는 순서로 한 개의 가용 리스트를 가집니다.

할당기가 크기 n인 블록이 필요한 경우, 적당한 가용 리스트를 검색합니다.

만일 크기가 맞는 블록을 찾을 수 없다면 다음 리스트를 검색하는 식으로 진행합니다.

 

 

 

 

 

 

 

 

🧐 간단한 분리 가용 리스트 할당기

각 크기 클래스를 위한 가용 리스트는 간단한 분리 저장장치로 동일한 크기의 블록들을 가지며, 각각은 크기 클래스의 가장 큰 원소의 크기를 갖습니다.

 

예를 들어 어떤 크기 클래스가 {17 ~ 32}로 정의되었다면, 이 클래스에 대한 가용 리스트는 전적으로 크기 32의 블록으로 구성됩니다.

 

어떤 주어진 크기의 블록을 할당하기 위해서는 적절한 가용 리스트를 검색해야 합니다.

만일 리스트가 비어 있지 않다면, 첫 번째 블록을 할당합니다.

가용 블록들은 할당 요청을 만족하기 위하여 절대로 분할하지 않습니다.

 

만일 리스트가 비어있다면, 할당기는 운영체제로부터 추가적인 고정 크기의 메모리를 요청하고, 이를 동일한 크기의 블록으로 나눈 뒤 블록들을 함께 연결해서 새로운 가용 리스트를 만듭니다.

 

할당기는 블록을 반환할 때 단순히 이 블록을 해당 가용 리스트의 맨 앞에 삽입합니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 분리 가용 리스트 장점

분리 가용 리스트는 높은 Throughput을 가집니다.

메모리 이용률 또한 우수한데, first fit 방법을 이용하면 best fit과 유사한 메모리 이용률을 얻을 수 있으며, 각 할당 요청 블록에 대해 그 크기를 클래스로 각각 생성한다면 최적할당과 동일해집니다.