[운영체제] 묵시적 가용 리스트(implicit free list)

유선·2024년 4월 16일

운영체제 정글 5주차

CS

목록 보기

11/25

🔍 묵시적 가용 리스트 방식?

동적 메모리 할당 및 해제를 위한 메모리 관리 방법 중 하나
힙 블록을 배열로 표현한 구조를 묵시적 가용 리스트
"묵시적(Implicit)"이라 표현하는 이유는 메모리 블록이 헤더 내 필드에 의해 암묵적으로 연결되기 때문이다.
헤더 영역에는 블록의 크기와 할당 여부 정보가 있기 때문에 헤더 정보를 바탕으로 다음 메모리 블록의 위치를 파악할 수 있다.

블록이란?

할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조를 필요로 한다.
대부분의 할당기가 해당 정보를 블록 내부에 저장한다.
한 블록은 1 워드 헤더, 데이터, 패딩(optional)으로 구성

워드란?

워드는 컴퓨터가 한 번에 처리할 수 있는 데이터의 비트 수
2-bit 아키텍처에서 1 워드는 32bit(4byte)이고, 64-bit 아키텍처에서 1 워드는 64bit(8byte)이다.

헤더는 블록의 크기(헤더와 패딩을 포함한)와 블록의 할당 여부 정보를 가진다.
만약 더블 워드(8바이트) 정렬 제약조건을 설정한다면, 블록 크기는 항상 8의 배수 이므로, 블록 크기의 하위 3비트는 항상 0이 된다.(1000)
따라서 블록 크기의 상위 29비트만 저장할 필요가 있으며, 나머지 3비트는 다른 정보를 인코딩하기 위해 남겨둔다.
이 경우 블록이 할당되었는지 혹은 가용 상태인지를 나타내기 위해 최소 중요 비트(할당된 비트)를 사용
블록 크기 24바이트(0x18)를 갖는 할당된 블록이 있는 경우의 헤더

0x00000018[블록 크기] | 0x1[가용 상태 여부] = 0x00000019

블록 크기 40바이트(0x28)를 갖는 가용 블록이 있는 경우의 헤더

0x00000028[블록 크기] | 0x0[가용 상태 여부] = 0x00000028

💡Payload

malloc**이 리턴**하는 것은 payload 영역의 시작점이다.

💡 Padding

패딩은 외부 단편화를 극복하기 위한 할당기 전략의 일부분으로서 들어갈 수 있고,또는 정렬 요구사항을 만족하기 위해 들어갈 수도 있다.
이들의 크기는 가변적이다.

👍 위 내용을 합친 블록 구조 (묵시적 가용 블럭의 구조)

위와 같은 블록 형태가 주어졌을 때, 힙을 연속된 할당 및 가용 블록의 배열로 아래 그림과 같이 구성할 수 있다.

이러한 구조를 묵시적 리스트라고 부른다.
- 묵시적 가용 리스트의 마지막에는 할당기가 리스트의 끝 지점에 도달했다는 것을 알려주기 위한 epilogue 블록이 있다.
- 할당 비트(allocated bit)가 셋팅되어 있어 항상 할당된 상태로 표시되어 있고, 사이즈는 0 바이트

할당한 블록 배치

애플리케이션이 k 바이트의 블록을 요청할 때, 할당기는 요청한 블록을 저장하기에 충분히 큰 가용 블록을 리스트에서 검색한다.
검색을 수행하는 방법은 배치 정책에 의해 결정된다
- first fit, next fit, best fit이 주로 사용된다.

✔️ First fit (최초 할당)

가용 리스트를 처음부터 검색을 시작해서 크기가 맞는 첫 번째 가용 블록을 선택하는 방법이다.
장점: 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있다.
단점: 리스트에 앞부분에 작은 가용 블록들을 남겨두는 경향이 있다는 것인데, 이로 인해 큰 블록을 찾는 경우에 검색 시간이 늘어날 수 있다.

✔️ Next fit (다음 할당)

First fit과 유사하지만, 이전에 검색이 종료된 위치에서 검색을 시작한다는 점이 다르다.
장점: First fit에 비하여 매우 빠른 속도를 가진다.
단점: first fit보다 최악의 메모리 이용도를 갖는다.

✔️ Best fit (최적 할당)

모든 가용 리스트를 검사하여 크기가 맞는 가장 작은 블록을 선택하는 방법이다.
장점: Best fit이 First fit과 Next fit에 비하여 더 좋은 메모리 이용도를 가진다.
단점: 모든 리스트(힙)를 다 검색해야 해서 First fit보다 훨씬 느리게 동작하고 비용이 많이 들 수 있다.

가용(Free) 블록의 분할

블록의 분할은 메모리 할당 요청이 가용 블록보다 작은 경우 해당 블록을 분할하여 사용 가능한 작은 블록을 생성하는 과정을 말한다.
- 메모리 단편화를 줄이고 작은 크기의 할당 요청에 대해 효율적으로 대응할 수 있다.
할당기가 할당할 가용 블록을 찾은 후, 가용 블록의 어느 정도를 할당할지에 대해 결정하여야 한다.
한 가지 옵션은 해당 가용 블록 전체를 사용하는 것이다.
- 빠른 속도를 가지지만, 내부 파편화가 발생한다는 단점이 있다.
다른 방법으로는 가용 블록을 쪼개어, 할당할 블록과 새로운 가용 블록으로 나누는 방법이 있다.

대부분의 경우 가용한 블록 전체를 사용하기 보다 일부분만 할당하여 사용한다.

가용(Free) 블록의 연결

할당기가 할당한 블록을 반환할 때, 새롭게 반환하는 블록에 인접한 다른 가용 블록들이 있을 수 있다.
이러한 인접 가용 블록들은 오류 단편화(false fragmentation)라는 현상을 유발시킬 수 있으며, 이때는 너무 작아 사용할 수 없는 가용 블록으로 쪼개진 많은 가용 메모리들이 존재한다.

위 그림은 할당한 블록을 반환한 결과이다.
반환 이후 크기 4워드의 가용 블록과, 2워드의 가용 블록이 각각 존재한다.
이 둘을 합친다면 5워드 크기의 메모리를 할당받을 수 있지만, 위 상황이라면 요청에 실패한다.

[##Image|kage@PL0vZ/btsGCztkRlQ/SwVVcUnk9pL19iuNgaJ5P1/img.png|CDM|1.3|{"originWidth":623,"originHeight":145,"style":"alignCenter","filename":"Untitled(9).png"}##]

오류 단편화를 극복하기 위해 연결(coalescing)이라는 과정을 통해 가용 블록들을 통합해야 한다.
이 과정에서 언제 연결을 수행해야 할지에 관한 중요한 정책결정을 해야한다.
할당기는 블록이 반환될 때마다 인접 블록을 통합해서 즉시 연결(immediate coalescing)을 선택할 수 있다.
또는, 일정 시간 후에 가용 블록들을 연결하기 위해 기다리는 지연 연결(deferred coalescing)을 선택할 수도 있다.
예를 들어 할당기는 일부 할당 요청이 실패할 때까지 연결을 지연할 수 있으며, 그 후에 전체 힙을 검색해서 모든 가용 블록들을 연결한다.
즉시 연결은 간단하며 상수 시간 내에 수행될 수 있지만, 일부 요청 패턴에 대해서는 블록이 연속적으로 연결되고 잠시 후에 분할되는 쓰래싱의 형태를 유발할 수 있다.

경계 태그로 연결하기

경계 태그는 메모리 블록의 경계를 식별하기 위해 사용
- 이를 통해 인접한 가용 블록을 식별하고 필요한 경우 연결(coalescing)하여 더 큰 가용 블록을 생성할 수 있다.
- 이는 메모리 단편화를 최소화하고 메모리 할당 및 해제 작업의 성능을 향상할 수 있다.
👩🏻‍💻 가용 블록은 어떻게 연결할 수 있을까?
- 블록의 헤더에 블록의 사이즈 정보가 있기 때문에 그 사이즈만큼 이동해서 다음 블록을 찾고 연결할 수 있을 것이다.
👩🏻‍💻 그러면 이전 블록은 어떻게 연결할 수 있겠는가?
- 헤더를 사용하는 묵시적 가용 리스트가 주어진다면, 유일한 옵션은 현재 블록에 도달할 때까지 전체 리스트를 검색하서 이전 블록의 위치를 기억하는 것이다.
  - 묵시적 가용 리스트를 사용하면, 이것은 각각의 free호출이 힙의 크기에 비례하는 시간을 소모할 것을 의미한다.
  - 검색시간이 상수가 될 수 없다.
  - 시간복잡도가 O(N)이 될 것이다.
👩🏻‍💻 이전 가용 블록을 연결하기 위해 경계 태그(Boundary Tag)를 사용한다.
- 이는 각 블록의 끝 부분에 푸터(footer, boundary tag)를 추가하는 것으로, 해당 푸터는 헤더를 복사한 것입니다.
- 이 기법은 상수 시간에 이전 블록을 연결하게 해준다.
만일 각 블록이 이와 같은 푸터를 포함하게 되면, 할당기는 시작 위치와 이전 블록의 상태를 풋터를 조사해서 결정할 수 있게 되며, 해당 풋터는 항상 현재 블록의 시작 부분에서 한 워드 떨어진 곳에 존재한다.

[##Image|kage@oyeR9/btsGCnsN5NE/Cb7qmnmVIkzqd3QtQO93J0/img.png|CDM|1.3|{"originWidth":1520,"originHeight":826,"style":"alignCenter","width":632,"height":343,"caption":"경계 태그를 이용해  이전 블록의 정보 를 쉽게 알 수 있다.","filename":"image222.png"}##]

위 그림은 경계 태그를 포함한 블럭의 구조

경계 태그를 사용한 연결(Coalescing)

4가지의 연결 방법

1️⃣ 이전과 다음 블록이 모두 할당된 상태

Coalescing이 발생하지 않는다.

2️⃣ 이전 블록은 할당되어 있지만, 다음 블록은 가용상태

다음 블록과만 Coalescing이 발생한다.
사이즈가 n인 블록이 해제되면서 n 블록과 m2 블록이 연결되고, 헤더와 푸터의 사이즈 정보는 n+m2로 변경

3️⃣ 이전 블록은 가용상태이고, 다음 블록은 할당상태

이전 블록과만 Coalescing이 발생한다.

4️⃣ 이전 블록과 다음 블록 모두 가용상태

이전 블록과 다음 블록 모두와 Coalescing이 발생
※ 경계 태그는 간단하고 유용한 개념이지만, 각 블록이 헤더와 푸터를 유지해야 한다는 단점이 존재한다.
- 만일 애플리케이션이 작은 크기의 블록을 많이 다룬다면 상당한 양의 메모리 오버헤드가 발생할 수 있다.
⭐️풋터가 할당된 블록에 있을 필요를 없애는 경계 태그를 영리하게 최적화하는 방법이 존재한다!⭐️
- 현재 블록을 메모리에 있는 이전과 다음 블록과 연결하려고 할 때, 만일 이전 블록이 가용한 경우에만 이전 블록의 풋터에 있는 size 필드가 필요하다는 점을 기억할 수 있다.
현재 블록의 추가적인 하위 비트들 중의 하나에 이전 블록의 할당, 가용 비트를 저장하려고 한다면, 할당된 블록들은 풋터가 필요가 없어지고, 이 추가적인 공간을 데이터를 위해 사용할 수 있을 것입니다.
그러나 가용 블록은 여전히 푸터를 필요로 한다는 것에 유의해야 한다.

묵시적 가용 리스트의 장단점

묵시적 가용 리스트는 구조가 단순하다는 장점이 있지만, 성능과 효율성 측면에서 단점도 존재한다.
묵시적 가용 리스트는 모든 블록을 순차적으로 검색하여 필요한 크기의 빈 공간을 찾는데, 만약 가용한 공간이 리스트의 마지막에 있다면 그 공간을 찾기 위해 전체 리스트를 순회해야 하므로 시간 복잡도가 O(n)이 된다.
대부분의 malloc/free 구현에서는 묵시적 가용 리스트 방식을 직접 사용하지 않는다.
- 이 방식이 메모리 단편화 문제를 해결하기 어렵고, 성능 면에서도 최적화되지 않기 때문이다.
블록의 분할과 경계 태그를 활용하여 가용 블록을 통합하는 방법은 대부분의 메모리 할당 라이브러리에서 사용한다.

유선

Sunny Day!

이전 포스트

[운영체제] 단편화(Fragmentation)

다음 포스트