Buddy Memory Allocator란?

 

Buddy System

why?

- 서로 다른 크기의 연속적인 페이지들을 빈번하게 할당 및 해제하는경우 외부 단편화가 생기는 단점이 있다. 남은 공간으로만 봤을 땐 충분해도 실제 커널이 요청한 사이즈를 처리할 수 있는 연속된 페이지가 없다는 의미이다.

 

버디 시스템은 이러한 외부 단편화를 줄이기 위해 탄생하였다. 이를 통해 연속적인 페이지 단위로 관리가 가능하다. 관리 메커니즘 부터 알아보자.

 

how?

우선 버디 시스템에서는 order 단위로 페이지 할당을 요청한다. 이것은 2^n 단위로만 요청을 할 수 있음을 의미한다. 예를 들어, order 3에 해당하는 페이지를 요청하는 경우 8(2^3 )개의 연속된 페이지들를 요청하는 것이다.

 

struct free_area{
	struct list_head free_list[MIGRATE_TYPES];
    unsignend long nr_free;
}

Allocation

1. A request 32Mb를 하게 되면 해당인덱스를 확인하고 없으면 상위 인덱스를 찾아 가용 블럭을 찾는다 해당케이스는 가용블럭이 1024밖에 없어서 1024는 너무 크기때문에 쪼개고 쪼개서 32Mb 메모리를 할당해준다.

2. B request 64Mb 또한 1024는 너무 크기 때문에 쪼개고 쪼개서 64Mb를 할당해준다.

3. C request는 60Mb에 대한 요청이다 이럴 경우 한단계 위의 크기 (2^n)규칙으로 할당해주기때문에 64Mb가용블럭이없으면 128Mb를 쪼개서 할당해주게 되고 이때 4Mb는 내부 단편화가 발생한다.

 

MIGRATE_TYPES( 이해가 잘 안간다.. 공부가 더 필요해 ..)

-> 우선 요청 할당의 크기를 찾고 -> 어떤메모리 type을 할당해줄건지 접근하는것같다.

 

 MIGRATE_TYPES은 page 타입들을 구분하는 용도로 사용된다. 버디 시스템은 결국 메모리 단편화를 줄이기 위해 나왔으며 단편화를 줄이려면 조각들을 잘 병합시키거나, 잘 쪼개는 등의 기능을 지원해야하며 이렇게 되야 연속적인 페이지들을 관리 할 수 있다.

• MIGRATE_UNMOVABLE
  • 이동과 메모리 반환이 불가능한 타입
  • 커널에서 할당한 페이지, 슬랩, I/O 버퍼, 커널 스택, 페이지 테이블 등에 사용되는 타입

• MIGRATE_MOVABLE
  • 연속된 큰 메모리가 필요한 경우, 현재 사용되는 페이지를 이동시킬 수 있는 타입이다
  • 이동시킴으로 단편화를 막을 수 있다
  • 유저 메모리 할당 시 사용된다

• MIGRATE_RECLAIMABLE
  • 이동은 불가능하지만 메모리 부족시 메모리 회수가 가능한 경우 사용되는 타입
  • 자주 사용은 안됌

• MIGRATE_ISOLATE
  • 커널이 특정 범위의 사용 중인 movable 타입의 페이지들을 다른 곳으로 이동시키기 위해 잠시 요 타입으로 변경하여 관리함.
  • 해당 타입의 페이지들은 버디 시스템이 절대 사용하지 않음

• MIGRATE_HIGHATOMIC

• MIGRATE_CMA

order 1에 해당 타입별로 다시 가용 리스트가 존재 : https://wogh8732.tistory.com/402

 

근데 내 버디 가 누군지 어떻게 아는거지???

할당된애들에 map에 주소 : 사이즈를 저장함

buddy 정보 담은 arr(free_list)

if (i == size)
        {
            cout << "Sorry, failed to allocate memory \n";
        }
         
        // If found
        else
        {
            pair<int, int> temp;
            // 가용 블록리스트에 맨 앞에 블럭 꺼냄
            temp = free_list[i][0];
 
            // Remove first block to split it into halves
            // 분할 할거니까 가용리스트에서 지워주고
            free_list[i].erase(free_list[i].begin());
            // order값 1내림
            i--;
             
            for(; i >= n; i--)
            {
                 
                // Divide block into twwo halves
                // pair type 선언
                pair<int, int> pair1, pair2;
                // pair1(시작주소, 반끝주소)로 생성
                // pair2(반끝주소, 끝주소)로 생성
                pair1 = make_pair(temp.first,
                                  temp.first +
                                  (temp.second -
                                  temp.first) / 2);
                pair2 = make_pair(temp.first +
                                  (temp.second -
                                  temp.first + 1) / 2,
                                  temp.second);
                                   
				// 나눈거 가용 리스트에 넣어줌
                free_list[i].push_back(pair1);
 
                // Push them in free list
                free_list[i].push_back(pair2);
                
                // 두개 다 넣고 하나 다시 꺼냄
                temp = free_list[i][0];
 
                // Remove first free block to
                // further split
                // 새로 할당해준거 가용리스트에서 지움
                free_list[i].erase(free_list[i].begin());
            }
            cout << "Memory from " << temp.first
                 << " to " << temp.second
                 << " allocated" << "\n";
            // 할당해준거 mp[시작주소] = 크기
            mp[temp.first] = temp.second -
                             temp.first + 1;
        }

void deallocate(int id)
{
     
    // If no such starting address available
    if(mp.find(id) == mp.end())
    {
        cout << "Sorry, invalid free request\n";
        return;
    }
     
    // Size of block to be searched
    // mp[address] = size
    int n = ceil(log(mp[id]) / log(2));
     
    int i, buddyNumber, buddyAddress;
 
    // Add the block in free list
    // free 됬으니 우선 다시 가용 리스트에 넣어줌 (시작값, 끝값)
    arr[n].push_back(make_pair(id,
                               id + pow(2, n) - 1));
    cout << "Memory block from " << id
         << " to "<< id + pow(2, n) - 1
         << " freed\n";
 
    // Calculate buddy number
    buddyNumber = id / mp[id];
 
    if (buddyNumber % 2 != 0)
        buddyAddress = id - pow(2, n);
    else
        buddyAddress = id + pow(2, n);
         
    // Search in free list to find it's buddy
    for(i = 0; i < arr[n].size(); i++)
    {
         
        // If buddy found and is also free
        if (arr[n][i].first == buddyAddress)
        {
             
            // Now merge the buddies to make
            // them one large free memory block
            if (buddyNumber % 2 == 0)
            {
                arr[n + 1].push_back(make_pair(id,
                   id + 2 * (pow(2, n) - 1)));
                    
                cout << "Coalescing of blocks starting at "
                     << id << " and " << buddyAddress
                     << " was done" << "\n";
            }
            else
            {
                arr[n + 1].push_back(make_pair(
                    buddyAddress, buddyAddress +
                    2 * (pow(2, n))));
                     
                cout << "Coalescing of blocks starting at "
                     << buddyAddress << " and "
                     << id << " was done" << "\n";
            }
            arr[n].erase(arr[n].begin() + i);
            arr[n].erase(arr[n].begin() +
            arr[n].size() - 1);
            break;
        }
    }
 
    // Remove the key existence from map
    mp.erase(id);
}