WEEK06 - TIL 분리 가용 리스트(segregated free list)

 

9.9.14 분리 가용 리스트(segregated free list)

단일 연결 블록 리스트를 사용하는 할당기는 한 개의 블록을 할당하는 데 가용 블록의 수에 비례하는 시간이 필요

→ 시간을 줄이는 대표적인 방법인 "분리 저장장치(segregated storage)"는 다수의 가용 리스트를 유지하며, 각 리스트는 거의 동일한 크기의 블록들을 저장.

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

 

※크기 클래스 정의하는 방법

1. 블록 크기를 2의 제곱으로 나누기

2. 크기가 작은 블록들은 자신의 크기 클래스에 할당, 큰 블록들은 2의 제곱으로 분리

 

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

- 할당기가 크기 n의 블록이 필요하다? → 적당한 가용 리스트를 검색

- 크기가 맞는 블록을 찾을 수 없다? → 다음 리스트를 검색하는 식으로 진행

 

10여 가지의 변형된 분리 저장장치 중 두 개의 기본 방법 설명

 

☞ 간단한 분리 저장장치(segregated-fit)

각 크기 클래스를 위한 가용 리스트는 간단한 분리 저장장치로 동일한 크기의 블록들을 가지고, 각 크기 클래스의 가장 큰 원소의 크기를 갖음. [ex. 어떤 크기 클래스 {17~32}로 정의, 이 클래스에 대한 가용 리스트는 전적으로 32 블록 크기로 구성

 

어떤 주어진 크기 블록을 할당하기 위해 적절한 가용 리스트를 검색

→ 리스트가 비어있지 않으면 첫번째 블록 전체 할당

→ 리스트가 비어있다면, 할당기는 운영체제로부터 추가적인 고정 크기의 메모리를 요청(대개 여러 개의 페이지 크기)하여 동일한 크기의 블록으로 나누고, 블록들을 함께 연결해, 새로운 가용 리스트를 만듦.

할당기는 블록을 반환할 때, 이 블록을 해당 가용 리스트 맨 앞에 삽입

 

이 방식의 장점,

1. 블록을 할당하고 반환하는 게 모두 빠른 상수시간 연산

2. 각 메모리 블록 내의 동일한 크기, 분할 불가, 연결 불가 등이 연합해서 블록당 오버헤드가 거의 없음

→ 각각의 메모리 블록이 동일한 크기의 블록만을 가져, 할당된 한 개의 블록의 크기는 그 주소로부터 추정 가능

→ 연결 작업이 없기에 할당된 블록들은 헤더에 할당/가용 태그가 필요하지 않음.

→ 할당된 블록들은 헤더가 필요 없고, 연결도 없기 때문에 풋터도 필요하지 않음

할당과 반환 연산이 가용 리스트의 시작 부분에서 삽입, 삭제하기에 리스트는 이중 연결하는 대신에 단일 연결만 해도 가능.

* 지켜야 하는 것은 블록 내 필요한 필드는 각 가용 블록 내의 1워드 SUCC pointer! 그래서 최소 블록 크기는 1워드!

 

단점으론,

단순한 분리 저장장치는 내부와 외부 단편화에 취약하다는 점

- 내부 단편화는 가용 블록들이 분할되지 않기에 발생

- 더 최악은 일부 참조 패턴은 가용 블록들이 절대로 연결되지 않기에 극단적인 외부 단편화를 유발할 수 있음.

 

 

☞ 분리 맞춤

이 방식에서 할당기는 가용 리스트의 배열을 관리

= 각 가용 리스트는 크기 size 클래스에 연관되며, 일종의 명시적 또는 묵시적 리스트로 구성.

각 리스트는 잠재적으로 서로 다른 크기의 블록들을 포함하며 다양한 분리 맞춤 할당기들이 존재.

 

- 블록을 할당하기 위해 요청된 크기 클래스를 결정, 크기가 맞는 블록을 위해 해당 가용 리스트를 first-fit 방식으로 검색

→ 만약 블록을 찾으면(선택적), 블록을 분할하고 나머지를 적당한 가용 리스트에 삽입

→ 찾지 못한다면, 다음 크기의 클래스를 위한 가용 리스트를 검색 [블록을 찾을 때까지 이 과정을 반복]

→ 만약 가용 리스트 어느 곳도 맞는 블록이 없다면? 추가적인 힙 메모리를 운영체제에 요청해 새 힙 메모리에 이 블록을 할당하고, 나머지를 적절한 크기의 클래스에 배치. 블록을 반환하기 위해 그 결과를 적절한 가용 리스트에 배치/연결

 

분리 맞춤 방식은 C 표준 라이브러리에서 제공되는 GNU malloc 패키지 수준의 할당기에서 선택 = 방식이 빠르고 메모리 관리가 효율적이기 때문.

→ 검색 시간은 줄고, 검색이 전체 힙이 아니라 힙의 특정 부분에 제한되기 때문

→ 메모리 이용도는 개선될 수 있는데, 그건 분리 가용 리스트의 단순한 first-fit 검색이 전체 힙을 best-fit 검색하는 것을 단순화한 것이라는 사실

 

 

끗🤗