Buddy System
각 크기 클래스가 2의 거듭제곱인 segregated fits의 특별한 경우이다.
기본 아이디어는 2^m 워드 더미가 주어졌을 때 각 블록 크기 2^k에 대해 별도의 자유 목록을 유지한다. (0<=k<=m)
요청된 블록 크기는 2에 가장 가까운 거듭제곱으로 반올림된다.
원래 크기 2^m 워드의 가용 블록이 하나 있다. 크기 2^k의 블록을 할당하려면 k<=j<=m이 되는 2^j 크기의 사용 가능한 첫 번째 블록을 찾는다. 만약 j=k이면 완료된다. 그렇지 않으면 블록을 j=k가 될 때까지 반으로 분할한다. 분할을 수행하면 남은 각 반(buddy)이 적절한 free list에 표시된다. 크기가 2^k인 블록을 free로 만들기 위해 free buddies와 결합을 계속한다. 할당된 버디를 만나면 결합을 중지한다.
buddy system의 중요한 사실은 블록의 주소와 크기가 주어지면, 버디의 주소를 계산하는 것은 쉽다는 것이다. 예를 들어, 32바이트 블록의 주소는 xxx...x00000 이고, buddy address는 xxx...x10000이다.
즉, 블록과 버디의 주소는 정확히 한 비트 위치에서 다르다.
buddy system allocator의 가장 큰 장점은 빠른 검색과 병합이다.
블록 크기에 대한 2의 거듭제곱 요구사항이 상당한 내부 단편화를 일으킬 수 있다는 큰 단점도 있다. 이러한 이유로 버디 시스템 할당기는 범용 워크로드에 적합하지 않다. 그러나, 블록의 크기가 2의 거듭제곱으로 미리 알려진 특정 애플리케이션별 워크로드의 경우 버디 시스템 할당기는 확실한 매력을 가진다.
Buddy System 아이디어
1) 동일한 블록 크기를 갖는 다수의 가용 리스트 활용
- Segregated Fits 방식과 다수의 free_array를 활용한다는 점은 동일하지만, 하나의 free_array에 들어있는 블록의 크기가 모두 동일하다는 차이가 있다.
- 각 블록은 2의 거듭제곱 크기이다.
2) 블록 할당
- 할당하려는 size를 2의 n승이 되도록 올림 처리한 후 크기에 맞는 블록을 탐색한다.
- 할당할 블록을 탐색할 때는 크기에 맞는 가용 리스트에서 탐색을 진행하고, 블록이 존재하지 않는다면 다음 가용 리스트로 이동해서 탐색을 이어나간다. (Segregated Fits와 동일)
- 선택한 블록의 크기가 할당하려는 size와 다르다면 필요한 사이즈의 블록이 될 때까지 반으로 할당하지 않은 부분은 해당 크기에 맞는 적합한 free_array에 추가한다.
3) 블록 반환
- buddy system의 장점인 빠른 검색과 연결을 가능하게 해주는 부분은 블록 반환 시 발생하는 병합에 있다.
void mm_free(void *bp) {
size_t size = GET_SIZE(HDRP(bp));
// header & footer free
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp); // 이 부분!!!!!
}- 블록이 분할되면서 생기는 두개의 블록은 서로가 서로의
buddy가 된다. - 각 블록의 bp를 활용해서 서로의
buddy를 찾을 수 있다. - 반환하는 블록의
buddy가 가용 상태인지 확인해서 가용 상태라면 병합한다. - 인접한 블록이더라도
buddy가 아니라면 병합하지 않는다.
4) 블록 병합
모든 블록의 크기가 2의 거듭제곱 크기라는 것을 이용해서, 현재 반환되는 블록의 buddy를 찾을 수 있다.
buddy의 bp는 현재 bp에서 size만큼 빼거나 더해서 구할 수 있다.- size만큼 빼야 하는지 더해야 하는지 파악하려면 현재
buddy가 왼쪽 버디인지, 오른쪽 버디인지 알아야 한다. - 현재 블록의 주소에서 메모리 블록이 시작하는 주소를 빼고, 그 값이 블록의 사이즈를 비트로 나타낸 것과 비교했을 때 겹치는 비트가 있다면 현재 블록은 오른쪽
buddy에 해당한다.
출처
Randal E. Bryant David R. O’Hallaron - Computer Systems A Programmer’s Perspective-Pearson (2015)
