[운영체제 만들기] Lazy Buddy Allocator

글의 참고

- http://maraboli.cl/apuntes/guias-free/UNIX.pdf

- 멀티 코어 대용량 메모리 시스템을 위한 역버디 메모리 관리자

- https://homepage.cs.uiowa.edu/~dwjones/opsys/notes/27.shtml

- https://dl.acm.org/doi/abs/10.1145/74851.74867

- unix internals the new frontiers [ 12.7 The SVR4 Lazy Buddy Algorithm ]

---

글의 전제

- 내가 글을 쓰다가 궁금한 점은 파란색 볼드체로 표현했다. 나도 모르기 때문에 나중에 알아봐야 할 내용이라는 뜻이다.

- 밑줄로 작성된 글은 좀 더 긴 설명이 필요해서 친 것이다. 그러므로, 밑 줄 처친 글이 이해가 안간다면 링크를 따라서 관련 내용을 공부하자.

- `글의 참조`에서 빨간색 볼드체로 체크된 링크는 이 글을 작성하면 가장 많이 참조한 링크다.

- `운영체제 만들기` 파트에서 퍼온 모든 참조 글들과 그림은 반드시 `이 글과 그림을 소스 코드로 어떻게 구현을 해야할까` 라는 생각으로 정말 심도있게 잠시 멈춰서 생각해봐야 실력이 발전한다.

---

글의 내용

- Deferred coalescing

: `Deferred coalescing`은 쉽게 설명하면, 필요할 때 까지 병합을 미룬다는 것이다. 버디 할당자 시스템의 성능은 분할과 병합이 다 깍아먹는다. 그래서 이 부분은 미루자는 것이다. 언제까지? 필요할 때 까지. 이걸 버디에 적용할 경우, 언제 병합을 해야 할까? 상황을 가정해보자. 일단 우리는 현재 Lazy buddy를 사용한다고 전제하자. 버디가 생성되고 메모리 할당 요청이 들어오면 초기에는 열심히 분할을 할 것이다. 여기서 하한을 2K로, 상한을 4M로 가정하자. 사용자들의 요청에 열심히 응답하다가 어느 순간 2M의 요청이 들어왔다. 그런데, 열심히 분할만 했지, 병합을 안해서 2M를 할당할 메모리가 없다고 치자. 어떻게 해야 할까? 바로 이 때, 병합을 해야 한다. 즉, De-allocation 시점이 아닌 Allocation 시점에 병합을 진행하게 된다. 

 

: 여기서는 SVR4, 즉, System V Release 4에서 나온 지연 버디 알고리즘에 대해 알아보자. 

 

- SVR4 Lazy buddy

: `SVR4` 알고리즘은 위에서 말했다시피, `병합`을 최대한 미루는 알고리즘이다. 먼저 이 알고리즘에 사용되는 용어들에 대해 알아보자.

N_i " 사이즈가 2^i인 총 블락 개수 

A_i " 사이즈가 2^i인 사용중인 블락의 개수 

Gi " 사이즈가 2^i인 전역 FREE 블락의 개수(globally free). `globally free` 블락은 병합이 조건이 되면 즉각적으로 병합을 하는 블락을 의미한다. 즉, 사이즈가 2^i인 전역 블락이 FREE고 그 친구놈인 전역 버디도 FREE면, 사이즈가 2^i+1 전역 블락으로 병합된다. 전통적인 버디 알고리즘에서 모든 블락들은 전역 블락에 속한다.

Li " 사이즈가 2^i인 지역 FREE 블락의 개수(locally free). `globally free` 블락은 병합 조건이 되어도 병합을 하지 않는 블락을 의미한다. 예를 들어, 사이즈가 2^i인 지역 블락이 FREE고 그 친구놈인 지역 버디도 FREE라도, 병합을 하지 않는다. 지역 블락은 나중에 사용될 것을 예상해서 FREE 상태로 남아있는다.

: 위의 변수들에 관계식은 다음과 같다. 

Ni = Ai + Gi + Li

 

: 위의 식은 간단하다. `전체 블락 개수는 사용중인 블락 개수 + 할당 가능한 로컬 블락 개수 + 할당 가능한 글로벌 블락 개수`를 의미한다. 위의 식에서, 한 가지 중요한 점이 있다. 바로, 사용 중 인 블락이 로컬인지 글로벌인지 알 필요가 없다는 것이다. 왜? SVR4는 `bookkeeping` 정보를 최소화하기 위한 구조로 되어있기 때문이다. 일반적으로, 지연 버디 알고리즘에서는 `Locally Free Blocks` 풀을 유지하다가, `Locally Free Blocks` 개수가 특정 임계값을 넘을 때만, 병합을 한다. 왜 `Locally Free Blocks` 의 개수가 많아질 때, 병합을 할까? `Locally Free Blocks` 개수가 많아졌다는 것은 다음에 새로운 크기의 블락 요청이 들어올 때, 병합이 필요할 가능성이 높아진다. 그래서 병합에 대한 기준을 `Locally Free Blocks` 개수로 두는 것이다. 그럼 임계값은 몇으로 두어야 할까?

 

 

- 지연 버디

: `멀티 코어 대용량 메모리 시스템을 위한 역버디 메모리 관리자` 라는 한국에서 발행된 2012년 논문을 통해 리눅스 2.6 버전에서 사용된 지연 버디 시스템을 알아본다.

 

: 아래의 그림은 `기존 버디 시스템` 이 적용된 구조이다. 지연 계층과 버디 계층이 나눠져 있는데, 지연 계층은 Local, 버디 계층은 Global 이라고 보면 좋을 듯 싶다. 멀티 코어 적용을 위해 각 코어 마다 Lazy buddy가 할당된다.  

 

출처 - https://m.riss.kr/search/detail/DetailView.do?p_mat_type=be54d9b8bc7cdb09&control_no=38e0f0df892d1cb2ffe0bdc3ef48d419&keyword=BUDDY#redirect

 

: `지연 계층`은 `환형 이중 연결 리스트(Circular doublylinkedlist)`를 이용하여 단일 페이지들을 관리한다.

 

: `지연 계층`에서 관리하는 페이지의 개수(count)가 일정 워터마크(low watermark or high watermark)를 넘거나 혹은 비게 된다면 `버디 계층`으로 할당 또는 반납을 요청해야 한다.

 

출처 - https://m.riss.kr/search/detail/DetailView.do?p_mat_type=be54d9b8bc7cdb09&control_no=38e0f0df892d1cb2ffe0bdc3ef48d419&keyword=BUDDY#redirect

 

: 반면 버디 계층의 경우 인접한 페이지들을 병합하여 관리하는 계층으로 총 11개의 리스트를 갖는다. 각각의 리스트는 2^0 ~ 2^10개의 연속된 페이지들을 환형 이중 연결 리스트 형태로 관리한다. 그러므로 버디 계층은 다중 페이지 할당을 처리하거나 지연 계층에서의 요청을 처리 한다.

 

: 지연 계층은 총 3개의 데이터가 들어가 있다.

1" 하이 워터마크
2" 배치 크기
3" 개수

: 각각의 페이지 들은 환형 이중 연결 리스트를 이용하여 관리되며 이 때 관리되는 페이지의 개수는 count 변수를 이용하여 관리한다. -> 

 

: 하이 워터마크의 경우 지연 계층에서 관리하는 페이지 수의 조절을 위해 사용 된다. 즉, 반납 요청 시 지연 계층에 존재하는 단일 페이지의 개수가 하이 워터 마크보다 커진다면 일정 개의 페이지들을 버디 계층으 로 반납한다. -> 이게 궁금한 점은 단일 페이지라는게 단위가 어떻게 되는거지? 4K가 기본 페이지 사이즈라면, 8K는 단일 페이지가 아닌가?

 

: 한편 버디 계층으로 반납 할 페이지의 개수는 배치 크기에 지정되어 있는 숫자를 사용한다.

 

출처 - https://m.riss.kr/search/detail/DetailView.do?p_mat_type=be54d9b8bc7cdb09&control_no=38e0f0df892d1cb2ffe0bdc3ef48d419&keyword=BUDDY#redirect

: 배치 사이즈와 하이 워터마크는 부팅 시점에 메모리의 크기를 고려하여 설정된다. 저자도 언급하고 있는 부분이지만, 각 시스템에 따라 값이 달라질 수 있다. 리눅스 2.6 에서는 위와 같은 식을 사용한다고 한다. 배치 사이즈의 4KB는 페이지 사이즈를 의미하는 

 

 

 

: 할당 요청 시 지연 계층의 페이지 개수가 0 이라면 배치 크기만큼의 페이지 프레임을 버디 계층으로부터 할당 받아서 리스트 자료 구조에 삽입한다. Linux에서는 암묵적으로 지연 계층의 로우 워터마크(low watermark)를 0으로 설정하여 사용하고 있다. 

 

 

: 하지만 단일 페이지의 할당 또는 반납 요청 중 한 가지 요청만 집중적으로 발생 한다면 지연 계층은 부하로 동작한다. 예를 들어 128MB(32,768pages)의 할당 요청이 연속적으로 발생할 경우 지연 계층은 대부분의 요청을 버디 계층으로부터 할당받아 처리해야 한다. 결국 이 경우에는 지연 계층이 단순히 버디 계층으로부터 페이지를 할당받아 전달해 주는 역할을 하게 되므로 지연 계층 관리 부하를 유발할 수 있다. -> 아마 이러한 이유는 요청 사이즈가 굉장히 커서 그런가? 요청 사이즈가 하이 워터마크보다 클 경우, 결국 버디 계층으로 반납을 해야해서 인듯 한데...

 

: 또한 지연 계층과 버디 계층 사이의 할당/반납 요청들이 빈번해지는 경우에는 배치 크기 단위 로 처리되는 특성에 의해 각 요청 간의 편차가 커질 수 있다.

출처 - https://m.riss.kr/search/detail/DetailView.do?p_mat_type=be54d9b8bc7cdb09&control_no=38e0f0df892d1cb2ffe0bdc3ef48d419&keyword=BUDDY#redirect

 

: 위의 의사 코드는 생각보다 너무 단순하다. 자료 구조도 상당히 쉽다. 알고리즘에서 보다시피, 지연 계층은 페이지가 단일 페이지(4KB)인 경우만 처리한다. 중요한 부분은 각 코어의 지연 계층에서 관리하는 페이지의 개수가 하이 워터마크보다 클 경우, 배치 사이즈 만큼의 페이지 개수를 버디 계층으로 반납한다. 처음에 위의 코드를 딱 보고 루프의 조건을 굳이 batch_size로 해야할까 라는 의문이 있었다. 그러나 루프의 조건을 batch_size 만큼이 아닌, count > high_watermark로 할 경우 흔히 임베디드 세계에서 보는 채터링 혹 바운스 현상을 만나게 된다. 즉, 카운트의 값을 하이 워터마크의 기준만큼만 루프를 돌면 그 다음 페이지가 하나만 추가가 되도 다시 버디 계층으로 페이지를 반납해야 한다. 그러므로, 특정 기준을 넘어서면 기준을 넘는 치수보다 더 많이 반납을 해서 다시 돌아오는 주기를 늦추는 것이다. 

 

: 위 논문의 추가 파라미터에는 cold, hot 이라는 내용이 포함되어 있지만, 현재 YohdaOS의 고려 사항이 아니므로 생략한다.

출처 - https://m.riss.kr/search/detail/DetailView.do?p_mat_type=be54d9b8bc7cdb09&control_no=38e0f0df892d1cb2ffe0bdc3ef48d419&keyword=BUDDY#redirect

 

: 할당 또한 단순하다. 페이지가 단일 페이지면 지연 계층, 다중 페이지면 버디 계층으로 가서 할당한다. 여기서 count의 값에 따라서 버디 계층에서 페이지를 가져올 지 지연 계층에서 곧 바로 줄지가 정해진다. 그리고 버디 계층에서 페이지를 가져올 때는 batch_size만큼을 가져와서 버디 계층에 반복해서 접근하는 것을 막는다. 

 

 

- Watermark-based lazy buddy system 구조

- watermark-based lazy buddy system의 핵심 구조는 블락을 2개로 나눈다는 것이다. 하나는 원래 기존의 BUDDY SYSTEM과 동일한 블락이고, 나머지 하나는 CACHE 같은 블락이다. watermark-based lazy buddy system 에서는 이 블락을 `locally-free` 블락이라고 한다. 최초에 할당시에는 `globally-free` 

 

- watermark-based lazy buddy system은 coalescing rule이라는 것이 있다. 이 규칙은 policy parameter에 의해서 결정이 되는데, policy paremeter는 2가지가 있다.

1" the lazy ratio

2" the speedup ratio

: 나중에 블락들이 다 사용되고 반환될 때, 해당 블락을 locally-free block으로 할지, globally-free block으로 할지의 여부는 위의 2개의 변수를 통해서 결정된다.

 

free blocks은 2가지로 나뉜다.

1" globally-free

 - 자기의 옆의 친구인 버디가 USED가 상태이기 때문에, Coalecsing을 하지 못한 블락들이 모여있다.

 - Coalescing은 서로가 버디인 블락 2개가 모두 `globally-free` 상태일 때 진행한다.

 

2" locally-free 

 - `locally-free`라고 표시된 블락은 bit-map에 FREE라고 표시되지 않는다. 이 표시가 되어 있는 블락은 다이렉트로 FREE LIST에 들어가며, 이 블락의 버디의 상태는 무시한다. 즉, locally-free block은 독단적으로 동작하는 블락이라는 것이다.

 

: 이 구조에서 BLOCK이 FREE 된다고 해서, 곧 바로 해당 BLOCK을 `globally`하게 system-wide bit-map 에다가 FREE로 표시하고, buddy와 coalescing을 진행하는 것은 아니다. 대신에 상황에 따라 해당 블락을 `locally`하게만 FREE 시키고, 해당 블락이 속하는 class의 FREE LIST에 집어넣는다. 그리고 해당 블락을 `locally-free`라고 표시한다. 

 

: 여기서 중요한 개념이 나온다. locally-free라고 표시된 블락은 오직 FREE LIST에서만 FREE만 상태인 것이다. 즉, system-wide bit-map에서는 해당 블락이 여전히 USED로 인식한다는게 중요하다. 해당 블락에 접근할 수 있는 방법은 해당 리스트를 통해서만 접근이 가능하다.

 

: FREE BLOCK이 locally-free block이 될지, globally-free block이 될지는 해당 블락의 class의 mode에 따라 결정된다.이 모드는 해당 블락이 얼마나 자주 사용되고 있느냐를 나타낸다.

 

- 위의 `A Lazy Buddy System Bounded by Two Coalescing Delays per Class`의 문서의 내용을 아래와 같이 요약해본다.

 

- watermark-based lazy buddy system에 대해 초반에 설명한다. 이 개념은 lazy buddy system의 구현체 중 하나인 듯 하다. 실제 이 문서의 저자가 어필하는 알고리즘은 `THE DELAY-2 BUDDY SYSTEM`이다.

 

- watermark-based lazy buddy system은 각 블락에 class라는 개념을 도입한다. 이 문서에서는 class와 mode를 동일한 표현으로 쓰는 것으로 언급된다.

1" lazy mode : 해당 모드의 블락은 굉장히 자주 사용되며, FREE OPERATION은 locally하게 진행된다.

2" reclaiming mode - 해당 모드의 블락은 자주 사용되는 편은 아니며, FREE OPERATION은 globally하게 진행된다.

 

- Coalescing Delay란 ? 사용중인 블락들이 반환되어 버디와의 coalescing 작업을 `coalescing delay`라고 부른다.