지난 장에서 Segmentation을 활용한 주소 변환 기법을 공부하며, Segment로 할당 받은 사이 사이에 조그맣게 끼어 있어 연속적으로 다른 segment를 할당해줄 수 없는 External fragmentation 문제가 발생할 수 있음을 발견했다.
Memory Virtualization 챕터를 시작하며 메모리를 연속적으로, 빈틈없이 나누어서 프로세스에 나누어주는 방법에 대해 얘기할 때는 딱히 External fragmentation에 대해 걱정할 필요가 없었다. 어차피 고정된 크기로 물리 메모리를 나누고 있기 때문에, 프로세스에 할당된 메모리 블록과 블록 사이에는 Fragmentation이 아니라 그냥 그대로 프로세스에 할당해줄 수 있는 크기임이 보장되었었거든. (Internal fragmentation 문제가 있기는 했지만.)
운영체제를 만들면서 처음부터 이러한 External fragmentation이 발생하지 않도록 한다는건, 배낭 어떤 물건을 넣어도 항상 빈틈없이 꽉 들어갈 수 있도록 만드는 것과 비슷한 느낌인 것 같다. 불가능하다는거지!
그렇기 때문에 처음부터 이 빈 메모리 공간들을 관리함으로써 이러한 External fragmentation 문제를 최소화해볼 것이다.
17.1. Assumptions
앞에서 공부했듯이, 메모리를 할당받아오는 공간을 Heap이라 부르며, 빈 공간은 기본적으로 Linked List를 사용하여 관리한다고 한다. 이 주제를 처음 접했을 때는 Hash 같은 자료구조를 쓸 것 같았는데, 빈 공간을 관리할 수만 있으면 어떤 자료 구조든 상관 없기는 하단다.
사용자가 이 Heap 영역의 메모리 할당을 요청했기 때문에 이런 문제들이 발생하는 것이었으니까, 사용자와 OS 사이의 접점, 그러니까 System call을 기준으로 빈 공간의 관리 기법에 대해 논의하는 것이 좋을 것 같다.
- void *malloc(size_t size)
프로세스가 요청한 바이트 수를 나타내는 size를 인자로 받아, 요청된 크기와 딱 맞거나 그것보다 좀 더 큰 메모리 공간을 할당해 그 공간을 가리키는 void pointer를 반환해준다.- free (void *ptr)
malloc System call을 통해 할당 받은 메모리의 시작 주소를 인자로 받아서, 물리 메모리 위의 해당 영역에 대한 사용을 해제해 다른 malloc System call에 의해 할당될 수 있도록 해준다.
System call의 요청자는 사용자(가 작성한 프로세스)이고, 응답자는 우리가 공부하고 있는 OS이다.
여기서 사알짝 걸리는 부분이 있는데, malloc을 통해 '얼만큼' 공간을 할당해달라고 요청하는 것은 자연스러운 반면 '이 위치'의 메모리를 해제해달라고 하는건 뭐가 하나 빠진 느낌이 들지 않는가? 아님 말고
바로 '얼만큼' 공간을 해제해달라는 Parameter가 없다는 점인데, 이건 뒤에서 천천히 배울 예정이니 일단은 그냥 그런가보다 하고 넘겨도 된다.
또 위 API가 제공되는 것 말고도 두 가지 가정을 해야 한다.
첫째로 한 번 malloc을 통해 heap 영역의 메모리를 프로세스가 할당 받으면 명시적으로 free 호출이 있기 전까지는 계속해서 프로세스가 해당 메모리 공간을 점유하며, 임의로 다른 무언가가 다른 위치로 물리 메모리 점유 영역을 옮길 수 없다는 것인데, 이것까지 고민하면 문제가 복잡해지기 때문이다. 자신 있으면 해보던가,,?
둘째로 External fragmentation을 해결하기 위해 앞에서 배운 Compact 기법을 사용할 수 없다는 것이다. 애초에 이런 일이 최대한 발생하지 않도록 하기 위한 공간 관리 기법을 고민해보자는 것이기도 하고,,
17.2. Low-Level Mechanisms
위와 같이 10~20KB만 프로세스에 할당되어 있고, 0~10KB, 20~30KB이 빈 공간인 Heap 공간을 상상해보자. 아마 11KB만큼의 주소 공간을 필요로 하는 프로세스가 있다면 External fragmentation이 발생한 상황일 것이다.
그리고 저 두 영역의 빈 공간을 위와 같이 Linked List로 관리하는 상황을 떠올려보자. Linked List의 탐색은 O(N)의 시간 복잡도를 가지니까, 빈 공간이 있는지 확인하다가 빈 공간을 발견해 프로세스에게 할당해주는데 최악의 경우 맨 마지막 노드(addr 20)까지 탐색해야할 것이다.
뭐 10KB만큼 할당해달라고 요청받았다면 그냥 addr 0 노드에 해당하는 영역을 통째로 넘겨주고 해당 노드를 list에서 삭제하면 되겠지만, 이보다 작은 영역인 1KB를 요청한다면 어떻게 처리해 주어야 할까?
Splitting
첫번째 노드는 이전과 같고, 두번째 노드의 addr이 21로, len이 9로 변했다.
말 그대로 두 번째 노드에 해당하는 빈 공간을 21KB를 기준으로 쪼개서(splitting), 앞쪽의 20~21KB 구간을 메모리 할당을 요청한 프로세스에게 떼어준 상황이다.
위에서 10KB를 떼어 달라는 요청이 있으면 그냥 다 주고 노드를 삭제하면 되겠다는 생각을 좀 더 이러한 관점에 맞춰서 생각해보면, 빈 공간의 시작점인 20KB에서 요청받은 10KB만큼 떨어진 30KB을 기준으로 앞뒤로 공간을 쪼갠 다음 프로세스에게 넘겨주고, 이때 len이 0이 되었으므로 해당 노드를 리스트에서 삭제한 상황이라고 상상해도 무리가 없을 것 같다.
이렇게 노드가 삭제되는 상황만 아니라면, 기본적으로 splitting이 발생하기 전후의 Free list의 형태, 그러니까 길이는 변하지 않는다는 점도 눈여겨보자.
Coalescing
위 Free List는 아직 외부로부터 메모리 할당을 요청받지 않은 상태를 보여준다. 외부에 메모리를 떼어준 적이 없으니, 아직 Fragmentation이고 뭐고 발생하지 않은 깨끗한 상태라 할 수 있다.
여기에 어쩌다보니 10~20KB 구간의 10KB를 프로세스에 내주면 위와 같은 Fragmentation이 발생하게 될 것이고,
위에서 가정했듯 프로세스에 제공된 free(10) System call을 통해 프로세스가 10KB 지점의 메모리를 OS에 반납하면 Free list의 head 바로 뒤에 '10KB 지점부터 10KB만큼'의 빈 공간이 생겼음을 갱신할 수 있다.
그런데 메모리를 기껏 반환해줬는데도, 각각의 노드가 모두 10KB만큼의 빈 공간이 있다고 기록하고 있기 때문에 그 이상의 메모리 공간은 프로세스에 할당해줄 수 없는 External fragmentation이 발생하게 된다.
그래서 OS가 이 빈 공간들을 위와 같이 병합(Coalescing)해주면, 인접해있는 빈 공간들끼리 앞에서부터 하나의 노드로 합쳐져 최종적으로는 위와 같이 최초의 Heap 메모리 상태와 같아지게 될 것이다.
...
정리하자면,,
요청된 공간보다 현재 발견한 노드의 빈 공간이 여유 있거나 딱 맞는 경우 경우 해당 노드에서 요청된만큼 메모리를 떼어서 할당(splitting)해주고, 이때 딱 떨어지게 빈 공간을 요청해 len이 0이 된 경우 더이상 빈 공간을 기록하는 것이 아니므로 해당 노드를 list로부터 삭제한다.
만약 요청된 크기와 같거나 그보다 여유 있는 빈 공간 노드가 없다면 당연히 메모리가 부족하므로 프로세스에 추가적인 메모리 할당이 불가능하다고 알려야겠지만, 처음부터 free가 발생했을 때 인접한 두 빈 공간을 합쳐서 더 큰 공간으로 만들어줄 수 있다면(coalescing) 진짜 메모리에 빈 공간이 하나도 없는 경우는 어쩔 수 없어도 External fragmentation으로 인해 메모리를 할당해주지 못하는 문제는 해결할 수 있을 것이다. 와!
Tracking The Size Of Allocated Regions
Free list를 사용해서 빈 공간을 프로세스에 할당해주는 절차와, 프로세스가 메모리를 다시 OS에 반환했을 때 External fragmentation을 없애는 절차를 생각해보았다.
추상화된 수준에서는 알겠는데, 아까 은근슬쩍 넘어간 free(10) 호출에서 어떻게 메모리를 해제할 크기, 그러니까 원래 malloc을 통해 할당 받은 메모리의 끝 경계를 어떻게 알아낼 수 있을지에 대해서는 아직 생각해보지 않았다.
이 free System call을 위한 '정보'가 부족하다는게 요점인데, 이걸 위와 같이 각각의 할당된 메모리의 앞부분(header block)에 기록해주면 된다.
20byte를 시스템에 요청한 상황인데, 요청된 20byte 뿐만 아니라 이 앞부분에 hptr로 시작 주소가 기록된 header가 추가되었다. size야 free에서 얼만큼의 메모리 공간을 해제해야할지 기록해야 하기 때문에 당연히 필요한데, 그 아래 있는 magic number는 Integrity(무결성)을 보장하기 위해 추가적으로 사용되는 값이라고 한다. 해제하기 전에 정말 이 메모리를 해제하려는게 맞는지 두 번 확인하기 위한 수단쯤 된다. (size와 magic number말고도 더 필요하면 더 정의할 수 있나보다.)
위의 Header는 위의 구조체로써 정의할 수 있으므로,
free System call은 대강 위와 같이 hptr, 그러니까 헤더를 가리키는 포인터를 해제하려는 메모리의 시작 포인터로부터 헤더 크기만큼 이전 주소로 계산하여 알아낸다. header 개념이 도입되었다고 해도 malloc을 통해 반환되는 값은 헤더의 시작 주소가 아니라 실제로 사용하려는 메모리의 시작 주소라는게 중요하다!
이렇듯 실제로 사용할 메모리 공간 뿐만 아니라 header를 위한 메모리 공간도 필요하기 때문에, 위의 Free list에서 여유가 있는 빈 공간을 찾을 때 딱 요청된 메모리 크기만큼이 아니라 헤더를 위한 공간까지 포함하여 할당해줄 수 있는 노드를 탐색해야 한다.
Embedding A Free List
Free list의 거시적인 형태(Linked list)와 연산 방법(Splitting, Coalescing), 저장해야 할 정보(addr, len, header_t)까지 고차원적으로 생각해 보았으니, 이제 좀 더 구체적으로 이 Free list를 어떻게 구현해야 할지 고민해보자. 애초에 이 Free list도 어딘가의 메모리를 점유해야 할텐데, 그럼 이 free list는 어떻게 메모리를 받아서 존재할 수 있다는 걸까?
Heap 전체의 크기가 4096Byte, 그러니까 4KB인 빈 공간이 있다고 가정해보자.
Free list의 한 노드를 위와 같이 정의한다면,
System call mmap()을 통해 아래와 같이 Free list의 첫 번째 노드가 될 head node를 할당받을 수 있다. (mmap은 malloc보다 좀 더 HW와 가까운 System call이라고 생각하자.)
mmap에 전달되는 Parameter를 모두 이해할 필요는 없을 것 같고, 이때 node_t의 크기인 node_t가 size의 크기 4byte, 다음 __node_t 포인터를 가리키는 포인터의 크기 4byte까지 총 8byte이므로 head를 리스트에 넣어준 후에는 위와 같이 4088byte 만큼의 빈 공간이 남았음을 head node에 기록했다는 것 정도만 알고 있으면 될 것 같다.
아, 이때 head의 위치를 16KB라고 해두자. 어디여도 상관은 없지만,,
이때 어떤 프로세스가 100B 만큼의 공간을 요청하면, OS는 Free list의 head node부터 탐색해가며 (100+8)B 이상의 빈 공간을 찾을 것이다. 방금 막 Free list를 초기화했기 때문에 4088만큼의 빈 공간을 가지고 있는 노드를 108KB 기준으로 잘라서(splitting) 앞쪽 부분에 header와 실제 사용할 메모리 공간으로 내어주고, malloc에 대한 응답으로 16KB에 header 크기만큼을 더한 위치를 ptr로 반환해준다.
그럼? 빈 공간을 splitting 해서 나누어줘도 아직 빈 공간이 남아 있으므로 여전히 노드의 갯수가 하나인 대신 head의 위치가 16KB + 108B로 밀리고, 남은 공간 역시 108B만큼 줄어든 3980B가 되었음을 확인할 수 있다.
이번엔 화끈하게 메모리 할당을 두 번 더해서, head가 총 108*2 = 216만큼 뒤로 물러나고, size 역시 216만큼 줄어 3764B가 되었다.
이제 할당은 알 것 같으니, sptr이 가리키는 위치, 그러니까 메모리의 시작 위치인 16KB로부터 맨 처음 할당받은 크기인 108B, 거기에 sptr의 header 만큼인 8B를 더한 (16K + 108 + 8)B = 16500B에 대한 메모리 해제를 수행해보자.
짠. 첫번째 세번째 덩어리는 아직 점유중인 메모리이므로 똑같고, 두번째 덩어리가 free(sptr) System call을 통해 OS에 반납되었다.
여기서는 반납된 메모리가 Free list의 head쪽에 삽입되어 head가 16500 지점으로 옮겨졌는데, 100B를 반납했기 때문에 size는 100이고, 아까까지 Free list head였던 노드가 뒤로 하나 물러났기 때문에 next가 해당 노드를 가리키는 16708로 되어 있음을 알 수 있다. (Free list node와 {header+할당받은 메모리}가 비슷하게 생겨서 헷갈릴 수 있는데, 각 구조체의 member를 잘 생각해야 한다.)
이로써 드디어 Free list에 두 개의 node가 발생함으로써 sptr과 세번째 메모리 덩어리 이전 공간에 여백이 생겨 External fragmentation이 발생한 모습을 확인할 수 있다. 아까 세운 가정에서 한 번 시스템으로부터 메모리를 할당받으면, 임의로 그 위치가 변하지 않는다고 했으니 이는 어쩔 수 없는 fragmentation이다.
그럼 남은 첫번째, 세번째 메모리 덩어리도 마저 해제해보자.
아마 세번째 덩어리가 첫번째 덩어리보다 나중에 해제되어서 Free list에 가장 마지막으로 삽입된 것 같다. 메모리를 해제한 것까지는 좋았는데, 이렇게 되면 맨 마지막 노드(size 3764)를 제외하면 100B 이상의 메모리 할당은 받아줄 수가 없게 된다.
그래서 필요한게 아까 배운 Coalescing이다! OS에 반납된 첫번째, 두번째, 세번째 덩어리와 Splitting 당한 원래의 빈 공간 노드가 물리적으로 연속되어 있으므로, 이젠 이 흩어진 fragment들을 합쳐 다시 16KB - 8Byte 만큼의 Free space node로 만들어줄 수 있다.
Growing The Heap
만약 가용한 Free List가 없다면? 그땐 어쩔 수 없다. 요청한 프로세스에게 진짜로 빈털털이라서 내어줄 수 있는 메모리가 없다고 응답하면 된다.
뭐,, OS가 처음부터 Heap으로 쓸 메모리를 다 내어준게 아니라 좀 작은 크기만 Heap으로 쓸 수 있도록 넘겨주었다면, UNIX의 sbrk() System call 같은걸 사용해서 Heap 공간 자체를 추가적으로 더 할당받을 수도 있다고 한다. 정말 꿍쳐놓은 메모리조차 없다? 그럼 어쩔 수 없고.
17.3. Basic Strategies
지금까지는 그냥 앞에서부터 빈 노드를 탐색하다가 가장 먼저 만나는 여유 있는 빈 공간을 Splitting 하여 넘겨주는 식으로 설명했었는데, 이를 포함한 여러 빈 공간 노드 선택 기법들과 속도, fragmentation 최소화 측면에서 각각의 장단점을 살펴볼 것이다. (위의 메모리 상태를 가정하고, 각각의 전략에 따른 메모리 할당 결과를 이미지로 보여줄 것이다!)
1. Best Fit
맨 앞부터 맨 뒤까지 노드를 모두 훑어보고, 요청된 메모리 공간과 가장 크기가 비슷한(딱 맞는) 노드를 찾아 해당 블럭에서 splitting을 통해 메모리를 할당 받는 방법이다.
처음부터 최대한 딱 맞는 메모리 공간을 넘겨줌으로써 낭비되는 공간을 없도록 하겠다는게 주요 목적인데,, 가장 알맞는 노드를 찾으려 하다보니 일단 모든 빈 공간 노드를 조회해봐야 한다는 측면에서 오버헤드가 발생하고, 애초에 앞으로 프로세스가 요청할 크기와 딱 맞는 빈 공간이 계속 있으리라는 보장이 없기 때문에 오히려 미세한 External fragmentation이 더 많이 발생한다.
15KB짜리 메모리 할당 요청에 Best fit 전략을 사용하면, 첫 노드는 10KB밖에 여유가 없으니 메모리를 떼어줄 수 없고, 두번째, 세번째 노드를 비교해봤을 때 30보단 20짜리 여유 공간에 더 꽉 차게 들어가기 때문에 세번째 노드로부터 메모리를 떼어 받게 된다.
2. Worst Fit
Best Fit과 정 반대로, 맨 앞부터 맨 뒤까지 노드를 모두 훑어보고 가장 널널한 노드를 선택해 Splitting하여 메모리를 할당 받는 방법이다.
이름이 Worst여서 Best Fit보다 뭔가 안좋을 것 같은데, 오히려 할당해주고 남은 fragmentation의 크기가 가장 큰 선택지를 고르는 것이기 때문에 파편이 아니라 그 자체로 메모리를 여유있게 넘겨줄 수 있는 노드로써 기능하게 된다는 장점이 있다. 다만 Best Fit과 마찬가지로 모든 노드를 살펴봐야 하기 때문에 성능이 좀 떨어진다는 단점은 그대로 있지만,,
마찬가지로 15KB 메모리 할당에 대해, 10KB짜리 노드는 공간을 내어줄 수 없지만 두번째, 세번째 노드의 경우 여유가 있어 둘을 비교해보았을 때 두번째 노드인 30KB로부터 메모리를 떼어 받을 경우 여유 공간이 더 남아 이번엔 두번째 노드로부터 메모리를 받게 되었다.
3. First Fit
이전까지 사용하던 전략인데, 그냥 head부터 순회하다가 요청된 메모리만큼을 떼어줄 수 있는 노드를 발견하면 그 노드를 선택해 splitting 및 할당을 받는 것이다.
Best/Worst Fit과 달리 굳이 리스트의 끝까지 조회할 필요가 없으므로 일반적으로 더 빠르게 대상 노드를 찾을 수 있지만, 먼저 발견한 노드 뒤쪽에 더 나은 결과를 가져다 줄 노드가 있을 수 있으므로 항상 최선의 선택을 할 보장은 없다는 문제점이 있다.
또한 계속 앞쪽에서 여유있는 노드를 발견할 확률이 아무래도 높으므로 fragment가 리스트의 앞쪽에 계속해서 누적될 가능성도 높을 수밖에 없는데, Address-based ordering, 그러니까 주소를 기준으로 리스트를 계속해서 정렬 상태를 유지시킴으로써 fragmentation이 발생하면 거기에 인접한 다른 노드에 coalescing 시켜주는 방법을 사용하면 최소한 단편화 문제는 해결할 수 있게 된다.
First fit 전략을 사용하면 가장 먼저 만나는 여유 있는 노드가 두번째 노드, 그러니까 30KB짜리 노드였기 때문에 Worst fit 전략과 같은 결과를 낸다.
4. Next Fit
First Fit이 맨 앞부터 여유 있는 노드를 탐색하기 때문에 앞쪽에 fragmentation이 누적되는 것이 문제였다면, Next fit에서는 탐색 위치를 이전의 메모리를 떼어준 위치로 하여 fragmentation을 여기저기 분산시킨다.
Best/Worst Fit과 같이 모든 노드를 조회하는 것이 아니기 때문에 속도 측면에서 First fit과 거의 유사한 반면, First fit과 달리 fragmentation이 연속적으로 누적되어 있을 확률이 상대적으로 적어 여유 있는 노드를 만날때까지 필요한 노드 탐색의 횟수가 적어진다는 장점이 있다.
17.4. Other Approaches
위의 기본적인 접근 방법 외에도 이것저것 어려운 정책들을 적용할 수 있다.
어지간하면 다 살펴보겠는데, 느무 피곤해서 강의 중에는 Buddy System만 살펴보려고 한다. (...)
Buddy Allocation
아까 빈 메모리 노드를 선택할 때 속도와 fragmentation 두 가지 측면에서 효율성을 따져봐야 한다고 했는데, Buddy allocation은 coalescing을 빠르고 쉽게 처리하는데 초점을 두는 기법이다.
이전까지 배운 전략들과는 달리 빈 메모리 공간을 일단 2^N 크기로 잡아 놓고, 요청된 크기와 최대한 맞아 떨어지는 2^K 크기까지 메모리 공간을 반으로 쪼개다가 남는 공간이 최소가 되는 단위를 만나면 그냥 통째로 메모리를 다 넘겨주는 방식이다.
예를 들어 위의 예제의 경우 7KB를 할당하기 위해 64 -> 32 -> 16 -> 8KB까지 메모리를 쪼갠 후 1KB만큼 낭비되는건 무시하고 그냥 8KB를 통째로 넘겨준 상황이다. (4KB에는 7KB가 못들어가니까!)
물론 딱 2^K만큼의 메모리를 요청하지 않는 한 Internal fragmentation이 반드시 발생할 수밖에 없는 구조이지만, 얘기했듯 Buddy allocation은 Coalescing 과정에서 그 진가가 드러난다.
만약 방금 할당한 8KB를 프로세스가 반환하면, 그와 짝지어진 또 다른 8KB 블럭(Buddy)은 방금 반환된 공간과 연속되어 있으므로 그 위치와 사용 여부를 쉽게 알 수 있으므로, 만약 짝꿍인 8KB buddy가 사용중이지 않음을 감지하면 그대로 16KB 블럭으로 병합시켜주면 되기 때문이다. 언제까지? Buddy가 사용중일 때까지!
마무리
Base & Bound, Segmentation에서 살짝 떨어져서, 메모리 그 자체를 어떻게 관리해야 할지 고민해 보았다. 어떤 정책을 사용하든 Fragment가 발생하는건 피할 수 없으니 이를 최소한으로 줄이고, 최대한 빠르게 처리하는데 초점을 둔다는 점을 꼭 기억하자. 어우 피곤해!
