[malloc] budy메모리 할당

budy system

---

 

📌개념

• 큰 버퍼들을 반복적으로 2등분하여, 작은 버퍼들을 만들며, 가능할때마다 인접한 메모리를 합치는 과정을 반복하는 기법

 

📌버디 메모리 할당 특징

• 2의 멱승 : 메모리의 할당과 회수를 2의 멱승 단위로 수행
• 합병 : 서로 인접한 버디들이 손쉽게 큰 세그먼트로 병합

 

📌버디 시스템 원리

• 메모리를 1/2로 계속 나누어 요청한 메모리보다 큰 메모리를 할당한다.
• 예를들어 31를 요청했다면 256을 3번나누어 32룰 할당
• 31의 메모리를 회수할 경우 인접한 32와 합치고 다시 64kb, 128kb를 합쳐서 원래의 256kb로 만든다.

 

 

📌버디 메모리 할당 예제

 

💡1024k의 메모리에서 요청시 동작하는 과정

1) 프로그램 A가 64K 크기의 메모리를 요청

-> A 할당
2) 프로그램 B가 128K 크기의 메모리를 요청

-> B 할당

3) 프로그램 C가 64K 크기의 메모리를 요청

-> C 할당

4) 프로그램 D가 128K 크기의 메모리를 요청

-> D 할당

5) 프로그램 C가 메모리를 해제

-> C 해제

6) 프로그램 A가 메모리를 해제

-> A 해제 후 64+64 합쳐서 128 만듬

7) 프로그램 B가 메모리를 해제

-> B 해제후 128+128 합쳐서 256 만듬
8) 프로그램 D가 메모리를 해제

-> D 해제 후 모두 합쳐서 1024 만듬

 

📌버디를 찾아주는 과정

• 크기가 128인 heap이 있고, 처음 여기 32 크기의 할당 요청이 들어왔다고 가정해보자
• 가용 블럭이 크기가 128짜리 하나가 있으므로 이 블록을 할당 해줄 것이다.
• 이때, 블록의 크기가 필요한 크기의 두배 이상이므로 반으로 잘라주는 작업을 진행한다.

 

• 반으로 잘라주고 나면 현재 블록의 사이즈는 64이고, bp에 사이즈를 더하면 버디의 bp를 구할 수 있다.
• 현재 크기가 너무 커서 반으로 잘라주는 작업을 진행 중이므로, 버디는 free list에 추가된다.
• 아직 블록의 크기가 필요한 크기의 두 배 이상이므로 한 번 더 잘라주고 난 뒤 할당을 진행하면 결과는 다음과 같다.

• 이제 할당을 몇번 더 진행하고, 반환도 몇번 진행한 경우를 생각 해보자.

 

• 여기서 96번에 있는 블록을 반환한다고 가정하자.

 

• 이때, 현재 bp와 블록의 사이즈를 이진수로 나타내면 다음 그림과 같다, 버디 시스템에서 핵심은 버디의 bp는 현재 블록의 bp와 딱 사이즈에서 1의 값을 갖는 자리만 다르다는 점이다. 따라서 현재 bp의 사이즈 bit는 0 이므로, 버디의 주소는 현재 bp에서 사이즈 자리의 bit만 1로 바꿔주면, 즉 현재 bp에서 size를 더하면 구할 수 있따.
• 버디가 free 블록이고, 버디의 크기가 현재 블록의 크기와 같기 때문에 연결이 가능할 것이다.

 

• 이번에는 사이즈의 자리가 비트 1이기 떄문에, 현재 bp에서 사이즈를 뺴면 버디의 주소가 나올 것이다.
• 마찬가지로 버디의 크기와 현재 블록의 크기가 같고 free 블록이기 떄문에 연결이 가능할 것이다. 이번에는 버디가 나보다 주소값이 작기 때문에, bp가 버디의 bp로 이동한다.

 

• 이번에도 마찬가지로 size 자리의 bit가 1이기 때문에 buddy의 주소는 bp에서 size를 뺀 값이 된다. 하지만 이번에는 buddy의 크기도 다르고, 이미 할당된 block 이므로 더 이상 연결이 불가능하다. 이러한 상황이 발생하면 연결을 종료한다.
• 그림을 보면 알 수 있듯이 buddy system은 현재 block의 왼쪽에 32 크기의 free block이 있음에도 불구하고 연결을 진행하지 않는다. 이는 모든 block들의 크기가 2^n 형태를 유지해야 한다는 점을 충족시키기 위해서이다.
• 당장 위의 그림에서 만약 왼쪽 block과 연결을 진행했다면 그 결과 합쳐진 block의 크기는 더이상 2^n을 유지하지 못할 것임을 알 수 있다. 
• 이렇게 block의 size 값과 주소값을 통해 buddy의 정보를 알 수 있다. 잘 생각을 해보면 위에서 진행했던 방식들과는 달리 buddy system에서는 block의 footer 정보를 사용하지 않는다는 것을 알 수 있다.