개발 공부
[운영체제][OSTEP] 빈 공간 관리
메모리의 빈 공간을 관리하는 방법에 대해 공부해봅니다.
![[운영체제][OSTEP] 빈 공간 관리](https://www.datocms-assets.com/66479/1686988115-ostep.jpg?auto=format&w=860)
🚪 들어가며
빈 공간 관리가 어려운 경우: 관리하는 공간이 가변-크기 빈 공간들의 집합으로 구성된 경우
ex1) 사용자-수준 메모리 할당 라이브러리(malloc(), free())
ex2) 세그멘테이션으로 물리 메모리를 관리하는 운영체제
➡️ 위 예시들과 같은 경우 외부 단편화 존재
(빈 공간들의 전체 크기) > (요청된 크기) 이더라도 하나의 연속된 영역 존재X 일 경우
➡️ 요청 실패
1️⃣ 가정
malloc()과 free()에서 제공하는 것과 같은 기본 인터페이스를 가정
void *malloc(size_t size)
인자: 응용 프로그램의 요청 바이트 수
반환: 요청된 크기와 같거나 큰 영역을 가리키는 void 포인터
void free(void *ptr)
인자: 포인터
반환: 해당 영역을 해제
위의 루틴들을 포함하는 라이브러리가 관리하는 공간: 힙(heap)
힙의 빈 공간 관리: 일반적인 링크드리스트 사용(반드시 리스트일 필요X)
할당된 메모리 > 요청한 메모리
➡️ 할당 청크의 내부에서 낭비가 발생: 내부 단편화
클라이언트에게 할당된 메모리는 다른 위치로 재배치될 수 없다고 가정
➡️ ⚠️ 단편화 해결에 유용하게 사용되는 빈 공간의 압축은 이 경우 사용 불가능
운영체제가 세그멘트를 구현할 때에는 단편화 해결을 위해 압축을 사용할 수 있음
➡️ 세그멘테이션 내용 참고
2️⃣ 저수준 기법들
분할과 병합
빈 공간 리스트: 힙에 있는 빈 공간들의 집합
30바이트의 힙이 있다고 가정하자.
┌──────────┬────────────┬────────────┐
│ free │ used │ free │
└──────────┴────────────┴────────────┘
0 10 20 30이 힙의 빈 공간 리스트는 다음과 같이 나타날 수 있다.
┌─────────┐ ┌──────────┐
│ addr: 0 │ │ addr: 20 │
head → │ │ → │ │ → NULL
│ len: 10 │ │ len: 10 │
└─────────┘ └──────────┘이 예시의 경우 10바이트를 초과하는 모든 요청은 실패하여 NULL을 반환한다.
10바이트에 대한 요청은 둘 중 하나의 빈 청크를 사용하여 쉽게 충족된다.
이때, 10바이트보다 적은 요청에 대해서는 어떤 일이 일어날까?
메모리를 1바이트만 요청했다고 가정 ➡️ 할당기(allocator)는 분할(splitting) 작업을 수행
이는 요청을 만족시킬 수 있는 빈 청크를 찾아 둘로 분할한 후 첫 번째 청크는 호출자에게 반환하고 두 번째 청크는 리스트에 남게하는 작업
위의 예시에서 할당기가 두 번째 원소를 사용하여 요청을 충족시키기로 한 경우 최종적으로 빈 공간 리스트는 다음과 같이 바뀐다.
┌─────────┐ ┌──────────┐
│ addr: 0 │ │ addr: 21 │
head → │ │ → │ │ → NULL
│ len: 10 │ │ len: 9 │
└─────────┘ └──────────┘이와 같이 기본적인 리스트의 모습은 바뀌지 않고 분할이 수행된 원소의 구성 값이 바뀐 것을 알 수 있다.
⭐ 이처럼 요청이 특정 빈 청크의 크기보다 작은 경우 분할 기법을 사용한다.
이러한 분할에 동반되는 기법은 빈 공간의 병합(coalescing)이다.
다시 위의 첫 예시를 가지고 와보자.
┌──────────┬────────────┬────────────┐
│ free │ used │ free │
└──────────┴────────────┴────────────┘
0 10 20 30이 상태에서 응용 프로그램이 free(10)을 호출하여 힙의 중간에 존재하는 공간을 반환하는 경우
┌──────────┐ ┌─────────┐ ┌──────────┐
│ addr: 10 │ │ addr: 0 │ │ addr: 20 │
head → │ │ → │ │ → │ │ → NULL
│ len: 10 │ │ len: 10 │ │ len: 10 │
└──────────┘ └─────────┘ └──────────┘빈 공간 리스트는 위와 같이 나타날 수 있는데, 이때 발생할 수 있는 문제점을 살펴보자.
힙 전체가 비어 있지만, 10바이트 길이의 청크 3개로 나누어져 있다.
➡️ 사용자가 20바이트를 요청하는 경우 실패 반환
⭐ 할당기는 이 문제를 방지하기 위해 메모리 청크가 반환될 때 빈 공간들을 병합
💡 아이디어
메모리 청크 반환 시 해제되는 청크의 주소와 바로 인접한 빈 청크들이 존재하는 경우 하나의 더 큰 빈 청크로 병합한다.
병합 수행 후 최종 리스트는 다음과 같이 바뀐다.
┌─────────┐
│ addr: 0 │
head → │ │ → NULL
│ len: 30 │
└─────────┘이 상태는 할당이 한 번도 일어나지 않은 최초의 힙 리스트와 동일하다.
병합 기법을 통해 할당기가 큰 빈 공간을 응용 프로그램에게 제공할 수 있다는 것을 더욱 보장할 수 있다.
할당된 공간의 크기 파악
free(void *ptr) 인터페이스 ➡️ 크기를 매개변수로 받지 않음.
포인터가 인자로 전달되면 malloc 라이브러리는 해제되는 메모리 영역의 크기를 신속히 파악하여 그 공간을 빈 공간 리스트에 추가시킬 수 있다고 가정
➡️ 이 작업을 위해 대부분의 할당기는 추가 정보를 헤더(header) 블럭에 저장
헤더 블럭은 메모리에 유지되며 보통 해제된 청크 바로 직전에 위치
다음의 예시를 살펴보자.
ptr이 크기 20바이트의 할당된 블럭을 가리키고 있다. ptr = malloc(20);
┌────────────────┐ ┐
│ │ │
│ │ │ The header used by malloc library
│ │ │
ptr → ├────────────────┤ ┤
│ │ │
│ │ │
│ │ │ The 20 bytes returned to caller
│ │ │
│ │ │
└────────────────┘ ┘헤더는 적어도 할당된 공간의 크기는 저장해야하며, 해제 속도를 향상시키기 위한 추가의 포인터, 부가적인 무결성 검사를 제공하기 위한 매직 넘버 및 기타 정보를 저장할 수 있다.
🔖 매직 넘버: 상수로 선언하지 않은 숫자를 의미하며, 코드를 작성한 사람이 아니고서는 그 의미를 파악하기 어렵기 때문에 매직이라는 수식어가 붙게 되었다.
예를 들어, 다음과 같이 헤더를 가정하는 경우
typedef struct __header_t {
int size;
int magic;
} header_t;헤더는 다음과 같이 표현할 수 있다.
hptr → ┌────────────────┐
│ size: 20 │
├────────────────┤
│ magic: 1234567 │
ptr → ├────────────────┤ ┐
│ │ │
│ │ │
│ │ │ The 20 bytes returned to caller
│ │ │
│ │ │
└────────────────┘ ┘사용자가 free(ptr)을 호출하면 라이브러리는 헤더의 시작 위치를 파악하기 위해 간단한 포인터 연산을 한다.
void free(void *ptr) {
header_t *hptr = (void *)ptr − sizeof(header_t);
...헤더를 가리키는 포인터를 얻어 낸 후, 라이브러리는 매직 넘버가 기대하는 값과 일치하는지 비교하여 안전성 검사(sanity check)를 실시한다.(assert(hptr->magic == 1234567))
그 후 새로 해제된 영역의 크기를 계산한다. (헤더의 크기 + 영역의 크기)
➡️ 빈 영역의 크기 = 헤더의 크기 + 사용자에게 할당된 영역의 크기
N 바이트의 메모리 청크 요청 ➡️ 라이브러리는 (빈 청크의 크기 N + 헤더의 크기)인 청크를 탐색
빈 공간 리스트 내장
이러한 빈 공간 리스트를 실제로 어떻게 구현할 수 있을까?
새로운 노드를 위한 공간이 필요할 때 ➡️ malloc() 호출
But, 메모리 할당 라이브러리 루틴에서는 이것이 불가능
4096바이트 크기의 메모리 청크가 있다고 가정하자.(= 4KB 힙)
리스트 노드를 다음과 같이 표현할 수 있을 때, 이 메모리 청크를 빈 공간 리스트로 관리하기 위한 과정을 살펴보자.
typedef struct __node_t {
int size;
struct __node_t *next;
} node_t;🧹 먼저 리스트를 초기화 한다.(초기에 4096 - 헤더 크기 길이의 항목 하나를 가짐.)
힙을 시스템 콜 mmap()을 호출하여 얻어진 영역에 구축된다고 가정할 때, 힙을 초기화하고 힙에 빈 공간 리스트의 첫 번째 원소를 넣는 코드는 다음과 같다.
// mmap()이 빈 공간의 청크에 대한 포인터를 반환
node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE,
MAP_ANON|MAP_PRIVATE, −1, 0);
head−>size = 4096 − sizeof(node_t);
head−>next = NULL;위 코드 실행 후 리스트는 크기 4088(4096-8(node_t))의 항목 하나만을 가지게 된다.
head 포인터가 가리키는 이 영역의 시작 주소를 16KB라고 가정하면 힙의 모양은 다음과 같다.
head → ┌────────────────┐ [virtual address: 16KB]
│ size: 4088 │ header: size field
├────────────────┤
│ next: 0 │ header: next field(NULL is 0)
ptr → ├────────────────┤ ┐
│ │ │
│ │ │
... │ The rest of the 4KB chunk
│ │ │
│ │ │
└────────────────┘ ┘이때, 100바이트 메모리 청크가 요청된다면 라이브러리는 먼저 충분한 크기의 청크를 찾는다.
➡️ 현 시점에서는 하나의 빈 청크(크기: 4088)만 존재하므로 해당 청크가 선택됨.
✂️ 선택된 청크를 (빈 영역의 크기 + 헤더의 크기)를 충족하는 청크와 나머지 빈 청크 두 개로 분할한다.
헤더의 크기를 8바이트라고 가정하면 힙의 공간 모습은 다음과 비슷할 것이다.
┌────────────────┐ [virtual address: 16KB]
│ size: 100 │
├────────────────┤
│ magic: 1234567 │
ptr → ├────────────────┤ ┐
│ │ │
│ │ │
... │ The 100 bytes now allocated
│ │ │
│ │ │
head → ├────────────────┤ ┘
│ size: 3980 │
├────────────────┤
│ next: 0 │
├────────────────┤ ┐
│ │ │
│ │ │
... │ The free 3980 byte chunk
│ │ │
│ │ │
└────────────────┘ ┘즉, 108바이트를 할당하고 할당 영역을 가리키는 포인터(위의 ptr)를 반환한다.
할당된 공간 직전의 8바이트에는 헤더 정보가 담기는데, 이 정보는 free()시 활용된다.
다음으로는 아래와 같이 호출 프로그램에 의해 사용 중인 3개의 100바이트 영역이 존재하는 상황에서 프로그램이 free()를 통해 일부 메모리를 반환하는 경우를 살펴보자.
┌────────────────┐ [virtual address: 16KB]
│ size: 100 │
├────────────────┤
│ magic: 1234567 │
├────────────────┤ ┐
│ │ │
│ │ │
... │ 100 bytes still allocated
│ │ │
│ │ │
├────────────────┤ ┘
│ size: 100 │
├────────────────┤
│ magic: 1234567 │
sptr → ├────────────────┤ ┐
│ │ │
│ │ │
... │ 100 bytes still allocated
│ │ │ (but about to be freed)
│ │ │
├────────────────┤ ┘
│ size: 100 │
├────────────────┤
│ magic: 1234567 │
├────────────────┤ ┐
│ │ │
│ │ │
... │ 100 bytes now allocated
│ │ │
│ │ │
head → ├────────────────┤ ┘
│ size: 3764 │
├────────────────┤
│ next: 0 │
├────────────────┤ ┐
│ │ │
│ │ │
... │ The free 3764 byte chunk
│ │ │
│ │ │
└────────────────┘ ┘응용 프로그램은 이제 free(16500)을 호출하여 할당 영역 중 가운데 청크를 반환한다.
➡️ 16500(sptr) = 16384(시작 주소) + 108(이전 메모리 청크) + 8(해체 청크의 헤더)
라이브러리는 빈 공간의 크기를 파악한 후 빈 청크를 빈 공간 리스트에 삽입한다.
이때, 빈 공간 리스트의 헤드 쪽에 삽입한다고 가정하면 공간의 모양은 다음과 같아진다.
┌────────────────┐ [virtual address: 16KB]
│ size: 100 │
├────────────────┤
│ magic: 1234567 │
├────────────────┤ ┐
│ │ │
│ │ │
... │ The 100 bytes still allocated
│ │ │
│ │ │
head → ├────────────────┤ ┘
│ size: 100 │
├────────────────┤
│ next: 16708 │ ───────────────────────────────┐
sptr → ├────────────────┤ │
│ │ │
│ │ │
... (now a free chunk of memory) │
│ │ │
│ │ │
├────────────────┤ │
│ size: 100 │ │
├────────────────┤ │
│ magic: 1234567 │ │
├────────────────┤ ┐ │
│ │ │ │
│ │ │ │
... │ 100 bytes now allocated │
│ │ │ │
│ │ │ │
├────────────────┤ ┘ │
│ size: 3764 │←───────────────────────────────┘
├────────────────┤
│ next: 0 │
├────────────────┤ ┐
│ │ │
│ │ │
... │ The free 3764 byte chunk
│ │ │
│ │ │
└────────────────┘ ┘이제 빈 공간 리스트는 순서대로 작은 빈 청크(100바이트), 큰 빈 청크(3764바이트)로 구성된다.
➡️ ⚠️ 단편화가 발생한다!
여기서 마지막 2개의 사용 중인 청크가 해제된다고 할 때, 병합이 없다면 작은 단편으로 이루어진 빈 공간 리스트가 될 것이다.
➡️ 따라서 리스트를 순회하며 인접한 청크를 병합하여 이를 해결한다.
힙의 확장
힙 공간이 부족한 경우에는 어떻게 해야 할까?
➡️ 가장 쉬운 방법: 단순히 실패를 반환하는 것(경우에 따라 유일한 대안일 수 있음.)
대부분의 전통적인 할당기 ➡️ 적은 크기의 힙으로 시작하여 모두 소진하면 운영체제로부터 더 많은 메모리를 요청
할당기는 힙을 확장하기 위하여 특정 시스템 콜(예: sbrk) 호출 후 확장된 영역에서 새로운 청크를 할당
sbrk 요청을 수행하기 위해 운영체제는 빈 물리 페이지를 찾아 요청 프로세스의 주소 공간에 매핑한 후, 새로운 힙의 마지막 주소를 반환
3️⃣ 기본 전략
이상적인 할당기 = 빠른 속도 & 단편화 최소
하지만 할당과 해제 요청 스트림은 무작위(프로그래머에 의해 결정)로 이루어지기 때문에 어느 특정 전략도 경우에 따라 성능이 매우 좋지 않을 수 있음.
최적 적합(Best Fit)
최적 적합 전략은 다음과 같다.
[1] 빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾는다.
[2] 후보자 그룹 중 가장 작은 크기의 청크(최적 청크)를 반환한다.
최소 적합이라고도 불리며, 빈 공간 리스트를 한 번만 순회하면 반환할 정확한 블럭을 찾을 수 있다.
공간의 낭비를 줄이고자 고안된 방법이지만, 그에 따른 비용이 수반된다.
➡️ 정교하지 않은 구현은 엄청난 성능 저하를 초래(항상 전체를 검색하는 경우)
최악 적합(Worst Fit)
최적 적합의 반대 방식으로 가장 큰 빈 청크를 찾아 요청된 크기 만큼만 반환하고 남는 부분은 빈 공간 리스트에 계속 유지한다.
최적 적합 방식에서 발생할 수 있는 많은 작은 청크들 대신 커다란 빈 청크를 남기려고 시도하지만, 빈 공간 전체를 탐색해야 하므로 역시 높은 비용이 수반된다.
⚠️ 대부분의 연구에서 엄청난 단편화가 발생하면서 오버헤드도 여전히 크다는 것을 보임.
최초 적합(First Fit)
요청보다 큰 첫 번째 블럭을 찾아서 요청만큼 반환한다.
➡️ ✅ 속도가 빠르다는 것이 장점(항상 리스트 전체를 탐색할 필요X)
그러나 때때로 리스트의 시작에 크기가 작은 객체가 많이 생길 수 있음.
➡️ 할당기가 빈 공간 리스트의 순서를 관리하는 방법이 쟁점
➡️ 이러한 한 가지 방법으로 주소-기반 정렬(address-based ordering)이 있다.
주소-기반 정렬 사용 시 리스트를 주소로 정렬하여 병합을 쉽게 하고, 단편화를 감소시킬 수 있다.
다음 적합(Next Fit)
항상 리스트의 처음부터 탐색하는 대신 마지막으로 찾았던 원소를 가리키는 추가의 포인터를 유지
➡️ 빈 공간 탐색을 리스트 전체에 더 균등하게 분산
다음 적합 알고리즘은 리스트의 첫 부분에만 단편이 집중적으로 발생하는 것을 방지
전체 탐색을 하지 않으므로 최초 적합의 성능과 비슷함.
4️⃣ 다른 접근법
기본적인 접근 방식 외 메모리 할당을 향상시키기 위한 기술과 알고리즘들을 살펴보자.
개별 리스트
특정 응용 프로그램이 한두 개 자주 요청하는 크기가 있다면, 그 크기의 객체를 관리하기 위한 별도의 리스트를 유지한다.
➡️ ✅ 특정 크기의 요청을 위한 메모리 청크를 유지함으로써 단편화 가능성이 상당히 줄어듬.
➡️ ✅ 요청된 크기의 청크만이 존재하므로 할당과 해제 요청을 신속히 처리할 수 있음.
⚠️ 그러나 지정된 크기의 메모리 풀과 일반적인 풀에 얼마만큼의 메모리를 할당해야 할까?
➡️ 특수 목적 할당기인 슬랩 할당기(slab allocator)를 통해 해결
다른 모든 요청은 더 일반적인 메모리 할당기에게 전달된다.
[슬랩 할당기의 동작]
[1] 커널 부팅 시 커널 객체를 위한 여러 객체 캐시(object cache)를 할당
🔖 커널 객체: 파일 시스템 inode 등 자주 요청되는 자료 구조들을 일컬음.
🔖 객체 캐시: 지정된 크기의 객체들로 구성된 빈 공간 리스트로 메모리 할당 및 해제 요청을 빠르게 서비스 하기 위해 사용됨.
[2] 기존에 할당된 캐시 공간이 부족하면 상위 메모리 할당기에게 추가 슬랩을 요청
🛸 요청의 전체 크기는 페이지 크기의 정수배
[3] 반대로 슬랩 내 객체들에 대한 참조 횟수가 0이 되면 상위 메모리는 이 슬랩을 회수할 수 있음.
🛸 VM 시스템이 더 많은 메모리를 필요할 때 실제 회수가 일어남.
빈 객체들을 사전에 초기화된 상태로 유지
➡️ 개별 리스트 방식보다 우수
반납된 객체들을 초기화된 상태로 리스트에 유지
➡️ 객체당 잦은 초기화와 반납의 작업을 피할 수 있으므로 오버헤드를 현저히 감소
버디 할당
빈 공간의 합병은 할당기의 매우 중요한 기능 ➡️ 합병을 간단히 하는 방법들이 설계됨.
이러한 예 중 하나가 이진 버디 할당기(binary buddy allocator)
빈 메모리는 처음에 개념적으로 크기 2^N인 하나의 큰 공간으로 생각됨.
메모리 요청 발생 시, (요청한 공간의 크기 < 찾고자 하는 크기)를 만족하는 동안 빈 공간을 2개로 계속 분할한다.
64KB의 빈 공간에서 7KB의 블럭을 할당하는 예시를 살펴보자.
┌───────────────────────────────────────────────┐
│ 64KB │
└───────────────────────────────────────────────┘
↓ ↓
┌───────────────────────┬───────────────────────┐
│ 32KB │ 32KB │
└───────────────────────┴───────────────────────┘
↓ ↓
┌───────────┬───────────┐
│ 16KB │ 16KB │
└───────────┴───────────┘
↓ ↓
┌─────┬─────┐
│ 8KB │ 8KB │
└─────┴─────┘이와 같이 빈 공간을 2개로 분할한 후 왼쪽의 8KB 블럭이 할당되어 사용자에게 반환된다.
이 방식은 2의 거듭제곱 크기 만큼의 블럭만 할당할 수 있으므로 내부 단편화로 인한 문제가 두드러질 수 있음에 유의해야 한다.
버디 할당의 아름다움은 블럭이 해제될 때 나타난다.
8KB 블럭을 빈 공간 리스트에 반환하는 경우를 살펴보자.
[1] 할당기는 "버디" 8KB가 비어 있는지 확인한다.
[2] 비어 있다면 두 블럭을 병합하여 16KB 블럭으로 만든다.
[3] 할당기는 다음 16KB의 버디가 비어 있는지 확인한다.
[4] 비어 있다면 이 두 블럭을 다시 합병한다.
[5] 위의 과정을 재귀적으로 트리를 따라 전체 빈 공간이 복원되거나 버디가 사용 중이라는 것이 밝혀질 때까지 수행한다.
버디 할당이 잘 작동하는 이유 ➡️ 특정 블럭의 버디를 결정하는 것이 쉬움.
각 버디 쌍의 주소는 오직 한 비트만 다름.
➡️ 어느 위치의 비트가 다른가는 버디 트리의 수준에 따라 달라짐.
기타 아이디어
앞선 접근 방식들의 한 가지 문제점 ➡️ 확장성
빈 공간들의 개수가 늘어남에 따라 리스트 검색이 매우 느려질 수 있음.
좀 더 정교한 할당기는 복잡한 자료 구조를 사용하여 이 비용을 줄임.
➡️ 균형 이진 트리, 스플레이 트리, 부분 정렬 트리 등이 있음.
현대의 시스템은 멀티프로세서 및 멀티쓰레드로 작동됨.
➡️ 멀티프로세서를 위해 할당기를 최적화하는 노력들이 많이 있었음.
📚 참고 문헌
Operating Systems: Three Easy Pieces ― 17: Free-Space Management
![[운영체제][OSTEP] 세그멘테이션](https://www.datocms-assets.com/66479/1686988115-ostep.jpg?ar=1&auto=format&crop=focalpoint&dpr=0.47&fit=crop&fp-x=0.5&fp-y=0.5&w=430)