[OS] 메모리 가상화(Memory Virtualization): 4. Free-Space Management

 

*이 글은 Operating Systems: Three Easy Pieces(운영체제 아주 쉬운 세 가지 이야기)를 바탕으로 작성되었습니다. 첨부한 모든 그림은 해당 도서에서 가져온 자료입니다. 내용 중 잘못된 부분이 있다면 알려주세요 :)

 

 

지난 글에서 segmentation으로 메모리를 관리하여도 외부 단편화 문제가 있다는 것을 보았다.

메모리의 빈 공간들은 여러 크기로 분할되다가 결국 단편화된다.

 

 

예시로, 위 그림을 보자.

현재 빈 공간의 총 크기는 20byte로, 10bytes 짜리 공간 2개가 나눠져있다.

하지만, 15byte짜리 요청을 실패한다.

 

빈 공간들을 어떻게 관리해야할까?

• 단편화를 최소화 시키기 위해 어떻게 해야할까?
• 가변 사이즈 요청을 어떻게 만족할 수 있을까?
• 여러 가지 방법들의 시간과 공간의 오버헤드는 어떻게 될까?

 

이번 글에서 고민해보자!!

 

---

일단 이번 글에선 malloc()과 free()에서 제공하는 것과 같은 기본 인터페이스를 가정한다.

 

• malloc

void* malloc (size_t size)

 

• free

void free(void *ptr)

 

---

 

🧐 Low-level 기법들

1. 분할과 병합 (Splitting and Coalescing)

 

 

아래 그림에 30byte의 힙이 있다.

 

아래 그림은 힙에 있는 빈 공간들의 리스트이다.

위 힙의 10byte짜리 빈 공간 2개가 원소로 있다.

 

case1) malloc

 

메모리 1byte를 요청했다.

1byte 영역이 분할되어 할당되고, 빈 공간 리스트의 원소가 조정된다.

 

case2) free

 

메모리를 10byte 만큼 반환했다.

기존에 할당되어 있던 주소 10, 길이 10 공간이 빈 공간 리스트에 추가된다.

 

 

위 같은 상태로 두면, 20 byte의 요청을 받으면 실패한다.

이때 공간들을 병합한다.

 

 

2. 할당된 공간의 크기 파악

 

void free(void *ptr)

 

free 인터페이스는 크기를 매개변수로 받지 않는다.

= malloc 시 할당 값에 대한 추가 정보를 저장해야한다.

 

이를 위해 대부분은 할당 시 header 블럭에 정보를 저장한다.

 

예시로 살펴보자.

아래 그림은 ptr이 가리키는 크기 20byte의 할당된 블럭이다.

 

ptr = malloc(20);

 

사용자는 malloc()을 호출하여, 그 결과를 ptr에 저장했다.

header는 할당된 공간의 크기, 해제 속도를 향상시키기 위한 추가 포인터, 무결성 검사를 위한 magic 값 등을 저장한다.

 

free(ptr)

 

사용자가 free(ptr)을 호출한다.

void free(void *ptr){
	header_t *hptr = (void *)ptr - sizeof(header_t);
    ...

 

header의 시작 위치를 찾기 위한 연산을 한다.

header에서 찾은 정보로 free한다.

 

 

3. 빈 공간 리스트 내장

 

위 형태로 빈 공간 리스트를 사용하려면, 당연히 빈 공간 리스트가 필요하다.

하지만 malloc()으로 구현할 수 없다... 그 이전에 빈 공간 리스트가 존재해야한다.

 

그럼 빈 공간 리스트를 먼저 만들자!

 

4096byte 크기의 메모리 청크가 있다고 하자.

힙의 크기는 4KB

힙을 초기화하고 빈 공간 리스트의 첫 번째 원소를 만드는 코드를 살펴보자.

// mmap() returns a pointer to a chunk of free space
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;

 

systemcall mmap()을 호출하여 얻은 공간에 구축한다.

 

위 코드를 실행 후 리스트는 크기 4088의 Free Chunk를 갖는다.

 

이때 100byte를 요청받았다고 하자.

라이브러리는 기존의 빈 청크 중 108byte를 할당하고, ptr을 반환한다.

추후 free() 호출 시 사용하기 위해 header에 넣어둔다.

 

그리고 빈 노드 사이즈를 4088-108로 축소한다.

 

 

이젠 100byte씩 (header 포함 108byte) 3개의 공간을 할당했다고 생각해보자.

아래와 같다.

 

자 그럼 free()를 해보자!

free(sptr) 호출 시 빈 공간의 크기를 파악하고, 빈 청크를 빈 공간 리스트에 삽입한다.

 

 

나머지 두 공간들도 free하자.

 

병합이 없다면 단편화가 발생한다...

전부 조각이 나있는 메모리...

이는 리스트를 돌면서 인접한 청크들을 병합하면 해결된다.

 

4. 힙의 확장

 

힙의 크기가 부족한 경우엔 확장해야 한다.

allocator는 sbrk(), brk() 같은 시스템콜을 호출하여,  확장된 영역에서 새로운 청크를 할당한다.

 

---

🧐 빈 공간 할당의 기본 방식

 

자 지금까지 low level의 기법들을 살펴보았다.

이제 빈 공간 할당!!!!!

 

allocator는 속도가 빠르고, 단편화를 최소화해야한다.

다양한 전략들이 있지만, 각각에 따라 fit한 방법을 찾아야한다.

 

 

최적 적합 (Best Fit)
= 작은 것 찾아서 먼저 쓰자

• 요청한 크기와 같거나 큰 빈 메모리 청크를 찾는다.
• 이 중 가장 작은 크기의 청크를 반환한다.

➡︎ 공간 낭비는 작지만, 이에 따른 비용 수반과 수많은 작은 청크

 

 

최악 적합 (Worst Fit)

= 큰 것 찾아서 쓰고 남기자

• 가장 큰 빈 청크를 찾아 요청 크기 만큼 반환

➡︎ 큰 청크를 찾기 위한 높은 비용, 단편화

 

 

최초 적합 (First Fit)

= 첫 번째 블럭 쓰자

• 요청보다 큰 첫 번째 블럭을 찾아 요청 크기 만큼 반환

➡︎ 빠르다, 때때로 작은 청크들이 많이 생성

 

 

다음 적합 (Next Fit)

= 최초 적합인데, 탐색 중이던 리스트 포인터 유지

• 처음부터 탐색하, 마지막으로 찾았던 원소를 가리키는 추가 포인터 유지

➡︎ 빈 공간 탐색 리스트 전체를 균등하게 이용, 최초 적합 성능과 비슷

 

 

---

🧐 또다른 방식

 

기본 전략 이외에도 다른 방식들이 있다....

(왜이리 ... 많게 느껴지죠...)

 

개별 리스트 (Segregated Lists)

= 자주 요청하는 크기를 관리하는 별도의 리스트 관리

• 특정 응용 프로그램이 자주 요청하는 사이즈가 있다면 별도 리스트로 관리
• 다른 요청은 일반 리스트로 관리

➡︎ 단편화 가능성을 매우 줄임, 리스트 탐색 줌

➡︎ 별도 리스트, 일반 리스트 각각 얼만큼의 메모리 할당해야할까?
    이를 slab allocator로 해결한다.

 

 

이진 버디 할당 (Binary Buddy Allocator)

= 메모리를 2^N인 하나의 큰 공간으로 생각

 

➡︎ 내부 단편화 문제, 특정 블럭의 버디 결정이 쉬움

 

---

 

와 이번 글에서 정말 많은 메모리 allocator를 보았다...

다음 글은 segmentation의 외부 단편화 문제를 해결할 방법을 드디어 소개하려한다!!!

 

↯ 다음글 ↯

https://koakwak.tistory.com/8

[OS] 메모리 가상화(Memory Virtualization): 5. Paging: 개요