Free Space Management
새 주소 공간을 만들었더니 듬성 듬성 빈 공간이 생겼어!! Oh my god!! 지져스!
이 빈 공간을 정리를 하고 싶어! 어떻게? 할까..잘하면 돼!!!
모든 메모리 관리 시스템에 대한 근본적인 측면에 대한 논의, 바로 Free space management다!
이 장은 메모리 가상화와는 거리가 조금 멀다.
관리하고 있는 공간이 고정 크기의 단위로 나누어져있다면 관리가 쉽다. 그런 경우 고정 크기 단위의 리스트를 유지하고 클라이언트가 그 중 하나를 요청하면 첫 번째 항목을 반환하면 되기 때문이다.
하지만 그렇게 쉬우면 이 챕터를 하지 않았겠지?
빈 공간 관리가 더 어렵고 흥미로운 경우는 관리하는 공간이 가변-크기 빈공간의 집합으로 구성되어있는 경우다. 영문으로 variable-sized units!
그리고 malloc(), free()에서 처럼 사용자 수준 메모리 할당 라이브러리에서,
Physcial Memory를 Segmentaion으로 관리시 External fragmentation이 발생한다.
단편화 = fragmentation
내부 단편화 Internal fragmentation
일정 크기의 페이지에 프로세스 할당시 프로세스의 크기가 페이지 보다 작을 경우 발생
외부 단편화 External fragmentation
여유 공간이 여러 조작으로 나뉘는 현상
외부, 내부 단편화
Q. 30바이트의 공간을 메모리 공간에 요청해도, Free space 공간의 합이 30이라도 응 요청이 실패된다. 이게 문제라서 이제부터 Free Space를 관리해보자!
Assumptions
malloc(size_t size) and free(void *ptr)
- malloc(size_t size) takes a single parameter, which is time number of bytes requested by the application.
free(void *ptr) takes a pointer and frees the corresponding chunk → the user does not inform the library of its size → the library must be able to figure out how big a chunk of memory.
The space for memory allocation is heap.
The generic data structure used to manage free space in the heap is some kind of free list.
- This structure contains references to all of the free chunks of space in the managed region of memory.
Internal fragmentation
- If allocator hands out chunks of memory bigger than that requested, any unasked-for space in such a chunk is considered internal fragmentation.
We will focus on external fragmentation.
Once the memory is handed out to a client, it cannot be relocated to another location in memory
→ No compaction of free space is possible.
The allocator manages a contiguous region of bytes.
Low-level Mechanisms~!
First, we’ll discuss the basics of splitting and coalescing(병합), common techniques in most any allocator.
Second, we’ll show how one can track the size of allocated regions quickly and with relative ease.
Finally, we’ll discuss how to build a simple list inside the free space to keep track of what is free and what isn’t.
Splitting and Coalescing
A free list contains a set elements that describe the free space still remaining(남아) in the heap.
The free list for this heap would have two elements on it.
One entry describes the first 10byte free segment (bytes 0-9), and one entry describes the other free segment (bytes 20-29)
🏳🌈 10바이트를 초과하는 모든 요청은 실패하여 NULL를 반환할 것이다.
→그럼 10바이트보다 작은 값을 요청하면 어떻게 될까????
이 경우 splitting이 일어난다. 요청을 만족시킬 수 있는 빈 chunk를 찾아 이를 둘로 분할한다.
1바이트 요청이 발생하고 allocator가 리스트의 두번째 원소를 사용하여 요청을 충족시켰다고 가정하자. malloc()은 20을 반환하고 최종 리스트는 위 그림과 같이 된다.
요청이 특정 빈 청크의 크기보다 작은 경우 Splitting기법을 사용한다. Splitting에 동반되는 기법은 빈 공간의 coalescing이다.
응용 프로그램이 free(10)을 요청하여 힙 중간 공간을 반환하면 free space가 list에 추가된다.
하지만 10bite 길이의 chunk 3개로 나누어져 있어서 만약 사용자가 20bite를 요청할 시 단순 list 탐색시 빈 청크를발견하지 못하고 실패한다. 탐색: traversal
! allocator가 이 문제를 방지하기 위하여 할 수 있는 일은 memroy chunk가 반환될 때 free space를 병합하는 것이다. < 엄청 간단하지? 그렇지만 이해는 쉽지 않단다. ㅎㅎ..>:
→ 메모리 청크를 반환할 때 청크의 주와 바로 인접한 빈 청크의 주소를 살펴본다. 새로 해제된 빈 공간이 왼쪽의 빈청크와 바로 인접해있다면 그들을 하나의 더 큰 빈 청크로 병합한다.
이 상태가 할당이 한번도 일어나지 않은 최초의 힙 리스트의 모양이다. coalescing 기법을 사용하여 allocator가 커다란 빈 공간을 응용 프로그램에게 제공할 수 있다는 것을 더 보장할 수 있다.
Tracking The Size of allocated Regions 할당된 공간의 크기 파악
free(void ptr) Interface는 size를 매개변수로 받지 않는다. (포인터를 할당받아서 리턴하는걸요?)
*우리는 포인터가 인자로 전달되면 malloc 라이브러리는 해제되는 메모리 영역의 크기를 신속하게 파악하여 그 공간을 빈 공간 리스트에 추가할 수 있다고 가정한다. 이 작업을 보통 allocator는 추가 정보를 header block에 저장한다. header block은 메모리에 유지되며 보통 해제된 chunk 바로 직전에 위치한다.
Ex) ptr이 가리키는 크기 20bite의 할당된 블록을 검토하고 있다.
사용자는 malloc()을 호출하고 그 결과를 ptr에 저장하였다고 가정하자.
예를 들어 ptr = malloc(20); Header는 적어도 할당된 공간의 크기는 저장해야한다(이 경우 20)
typedef struct __header_t{
int size;
int magic; // 부가적인 무결성 검사를 제공하기 위한 변수
} header_t; 
void free(void *ptr){
header_t *hptr = (void *)ptr - sizeof(header_t);
...↑ 사용자가 free(ptr)을 호출하면 라이브러리는 header의 시작 위를 파악하는 간단한 포인터 연산
헤더를 가리키는 포인터를 얻어내면, 라이브러리는 매직 넘버가 기대하는 값과 일치하는지 비교하여 sanity check를 실시한다. (assert(htpr→magic == 1234567)) 그 다음 새로 헤제된 영역의 크기를 간단한 수학을 토해 계산한다.(즉 헤더의 크기를 영역의 크기에 더함)
<!— 주의할 점이 있다. 빈 영역의 크기는 헤더 크기 더하기 사용자에게 할당된 영역의 크기가 된다.
Embedding A Free List
지금까지 free list의 개념만 다루었지만 이제는 구현을 생각해보자. 보통 새로운 노드를 위한 공간을 할당할 때 malloc()을 호출한다. 하지만 메모리 할당 라이브러리 루틴에서는 불가능하다. 대신 빈 공간 내에 리스트를 구축해야한다.
4096바이트 크기의 메모리 chunck가 있다고 하자. 즉 힙의 크기는 4KB이다. 이를 free list로 관리 하기 위해서는 먼저 list를 초기화해야한다. 처음에 리스트는 (4096-헤더 size)길이의 항목 하나를 가지고 있다.
// 이 list의 노드에 대한 코드
typedef struct __node_t {
int size;
struct __node_t *next;
} node_t;heap을 초기화하고 heap에 free list의 첫 번째 요소를 넣는 코드를 살펴보자. heap은 system call mmap()을 호출하여 얻어진 영역에 구축된다고 가정한다. 이 방법은 유일한 방법은 아니다.
// mmap()이 free list의 chucnk에 대한 포인터를 반환
node_t *head = mmap(NULL, 4096, PROT_READIPROT_WRITE,
MAP_ANONIMAP_PRIVATE, -1, 0);
head->size = 4096-sizeof(node_t);
head->next = NULL;이 코드의 실행 후 리스트는 크기 4088의 항목 하나만을 가지게 된다. 매우 작은 힙이다. head 포인터는 이 영역의 시작 주소를 담고 있다. 영역의 시작 주소를 16KB라고 가정하자.
이때 heap의 모양은 위 그림과 비슷할 것이다.
이제 100bite 메모리 chucnk가 요청되었다고 생각해보자.
이 요청을 처리하기 위해 라이브러리는 먼저 충분한 크기의 chunk를 찾는다. 하나의 빈 청크(4088)만이 존재하기 때문에 이 청크가 선택된다. 요청을 처리하기에 충분히 큰 크기, 앞서 말한 것처럼 빈 영역의 크기 더하기 헤더의 크기를 충족시킬 수 있는 청크와 나머지 빈 청크 두 개로 분할한다.
100바이트에 대한 요청이 오면 라이브러리는 기존 하나의 빈 청크 중 108바이트를 할당하고 할당 영역을 가리키는 ptr를 반환한다. 그리고 free()를 사용할 수 있도록 할당된 공간 직전 8바이트에 헤더 정보를 넣는다. 그런 후 하나 남은 빈 노드를 3980바이트로 축소한다.
이제 100바이트씩 3번 할당한 힙을 보자. 이번에는 free()를 통해 일부 메모리를 반환하면 어떤 일이 벌어질까?
free list는 여전히 head가 가리키는 하나의 노드로 구성되어 있지만 세번의 분할 이후 3764로 축소된 모습이다.
이 예제에서 free(16500)을 호출하여 할당 영역 중 가운테 chunck를 반환한다. 16500은 메모리 영역의 시작 주소 16384, 이전 메모리 청크의 크기 108, 해제되는 청크의 헤더 8바이트를 모두 더해서 나온 값이다. 그림에서는 sptr로 나타난다.
라이브러리는 신속히 빈 공간의 크기를 파악하고, 빈 청크를 free list의 헤드 쪽에 삽입한다고 가정한다면 위그림과 동일하다.
이제 빈 공간 리스트의 첫번째 원소는 작은 빈 청크(100바이트크기이며 list의 헤드가 가리킨다.) 두번째 원소는 큰 빈 청크 3764이다. 드디어 우리 리스트가 하나 이상의 원소를 가진다.
마지막으로 마지막 2개의 사용 중인 청크가 헤제된다고 하자. 병합이 없으면 17.7과 같이 작은 단편으로 이루어진 free list가 될 것이다. 해결책은 리스트를 순회하면서 인접한 청크를 Coalescing 하면 된다.
Growing The Heap
heap space가 부족한 경우 단순히 NULL을 반환하면된다. 어떤 경우에도 유일한 대안이다.
졌잘싸다. ㅋㅋㅋㅋㅋ
대부분의 전통적인 allocator는 적은 크기의 힙으로 시작하며 모두 소진하면 OS로부터 더 많은 메모리를 요청한다. allocator는 heap을 확장하기 위해서 특정 시스템콜(Unix 시스템에서는 sbrk)을 호출한다. sbrk 요청을 수행하기 위해서 OS는 빈 물리 페이지를 찾아 요청 프로세스의 주소 공간을 매핑한 후, 새로운 힙의 마지막 주소를 반환한다. 이로써 큰 힙을 사용할 수 있고 요청은 성공적으로 충족될 수 있다.
Basic Strategies
strategies:전략
일부 기법에 대해 간략히 살펴보았고, 빈 공간 할당을 위한 기본 전략에 대해 살펴보자..
Best Fit
So simple!
- free list를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾는다.
- 후보자 그룹 중에서 가장 작은 크기의 청크를 반환한다. 이를 best-fit chunk라고 부른다.
배경: 사용자가 요청한 크기에 가까운 블럭을 반환함으로써 best fit은 공간의 낭비를 줄이려고 노력한다. 이 행동에 비용도 수반된다. 정교하지 않는 구현은 해당 빈 블럭을 찾기 위해서 항상 전체를 검색해야하기때문에 엄청난 성능 저하를 초래한다.
Worst Fit ↔ Best Fit
가장 큰 빈 청크를 찾아 요청된 크기만큼만 반환하고 남는 부분은 free list에 계속 유지한다. Worst Fit은 Best Fit방식에서 발생할 수 있는 수많은 작은 청크 대신에 커다란 빈 청크를 남기려고 시도한다. 그러나 다시 한번 항상 빈 공간 전체를 탐색해야 하기 때문에 이 방법 역시 높은 비용을 지불해야한다.
First Fit
First Fit는 간단하게 요청보다 큰 첫 번째 블럭을 찾아서 요청만큼 반환한다. 먼저와 같이 남은 빈 공간은 후속 요청을 위해 계속 유지한다. First Fit은 속도가 빠르다는 점이 장점이다. 원하는 블럭을 찾기 위해 항상 free list 전체를 탐색할 필요가 없다. 때때로 list의 시작에 크기가 작은 객체가 많이 생길 수 있다. 따라서 allocator는 free list의 순서를 관리하는 방법이 쟁점이다. 한가지 방법으로 address-based ordering(주소-기반 정렬)을 사용하는 것이다. 리스트를 주소로 정렬하여 coalescing을 쉽게하고, 단편화로 감소시킨다.
Next Fit
항상 리스트의 처음부터 탐색하는 대신 다음 적합 알고리즘은 마지막으로 찾았던 원소를 가리키는 추가의 포인터를 유지한다. 아이디어는 free space 탐색을 list 전체에 더 균등하게 분산시키는 것이다. list의 첫부분에만 단편이 집중적으로 발생하는 것을 방지한다. 이러한 접근 방식은 전체 탐색을 하지 않기때문에 First Fit의 성능과 비슷하다.
'코딩 관련 > OS' 카테고리의 다른 글
| 운영체제 11 - Faster Translations(TLBs) [Memory Virtualization] (0) | 2021.06.12 |
|---|---|
| 운영체제 11 - Paging [Memory Virtualization] (0) | 2021.06.11 |
| 운영체제 9 - Segmentation [Memory Virtualization] (0) | 2021.06.11 |
| 운영체제 8 - Mechanism: Address Translation [Memory Virtualization] (0) | 2021.06.11 |
| 운영체제 7 - Interlude(Memory API) [Memory Virtualization] (0) | 2021.06.11 |
