버디 시스템 알고리즘: 메모리 동적 할당 (Buddy System)

외부 단편화와 버디 시스템 (external fragmentation)

커널은 연속적인 페이지 프레임 그룹을 할당하는 견고하고 효율적인 정책을 세워야 한다. 이때 메모리 관리와 관련한 유명한 문제인 '버디 시스템 알고리즘 외부 단편화(buddy system external fragmentation)'를 해결해야 한다.

외부 단편화(external fragmentation)는 다른 크기의 연속적인 페이지 그룹을 빈번하게 할당하고 해제하여, 할당한 페이지 프레임 블록 사이에 작은 여유 페이지 프레임 여러 개가 '산재'하는 현상이다.

그 결과 나중에는 큰 크기의 연속된 페이지 프레임 할당을 요청할 때 이를 담을 충분한 여유 페이지가 있어도 메모리를 할당하지 못할 수 있다.

8개의 페이지 프레임이 사용되고 있지 않지만, 연속적인 페이지 프레임 그룹으로 할당할 수 없다.

[Buddy System Algoritm] 외부 단편화 external fragmentation

외부 단편화를 해결하는 방법 = buddy system

1. 페이징 회로를 활용하여 불연속적인 여유 페이지 프레임의 그룹을 연속된 가상 주소 구간에 매핑한다.

2. 남아있는 연속된 여유 페이지 프레임 블록을 관리하는 적절한 기법을 개발하여, 작은 블록을 요청할 때 큰 여유 블록을 쪼개서 할당하는 경우를 가능한 한 줄인다.

커널은 다음 두 가지 이유 때문에 두 번째 접근법을 선호한다

1. 연속된 가상 주소로는 요청을 처리할 수 없고 실제로 연속된 페이지 프레임이 필요한 경우가 종종 있다.

2. 버디 시스템 알고리즘에서 커널 페이지 테이블을 수정하지 않아도 된다.

Buddy System 알고리즘

사용하지 않는 모든 페이지 프레임을 그룹별로 묶어서 블록 리스트 10개에 넣는다.

각 리스트는 연속된 페이지 프레임 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024개로 구성된 그룹을 담는다. 블록의 첫 번째 페이지 프레임의 물리적인 주소는 그룹 크기의 배수다.

16-페이지 프레임의 시작 주소는 16*4K의 배수다(212 = 4096으로 정규 페이지 크기).

Buddy system 알고리즘 예

누군가 연속된 페이지 프레임 256개로 구성된 그룹(즉 1024KB)을 요청했다고 하자. 버디 시스템 알고리즘은 먼저 256-페이지-프레임 리스트에 여유 블록이 있는지 검사한다.

[버디 시스템 알고리즘] Struct ZONE 구조

여유 블록이 없으면 다음으로 큰 블록, 즉 512-페이지 프레임 리스트에서 여유 블록을 찾는다.

여기서 여유 블록을 발견하면 페이지 프레임 512개 중에서 256개를 요청한 쪽으로 할당하고, 나머지 페이지 프레임 256개를 여유 256-페이지 프레임 블록 리스트에 추가한다. 이것이 버디 시스템 알고리즘 특징이다.

여유 512-페이지 블록이 없다면 다음으로 큰 블록, 즉 1024-페이지 프레임에서 블록을 찾는다. 여기서 블록을 찾으면 페이지 프레임 1024개 중 256개를 요청한 쪽으로 할당하고, 나머지 768개 중 처음 512개를 여유 512-페이지-프레임 블록 리스트에, 남은 페이지 프레임 256개를 여유 256-페이지 프레임 블록의 리스트에 넣는다.

1024-페이지 프레임 블록 리스트가 텅 비어 있다면 할당을 포기하고 에러 상황을 알려준다.

반대 작업인 페이지 프레임 블록을 해지하는 데서 알고리즘의 이름이 유래하였다.

커널은 크기가 b인 이웃하는(memory buddy) 여유 블록 쌍을 크기가 2b인 더 큰 블록으로 만들려고 한다. 다음 조건을 만족하면 두 블록은 버디 시스템 알고리즘의 블록이다.

1. 두 블록의 크기가 똑같이 b이다.
2. 두 블록이 연속된 물리적인 주소에 위치한다.
3. 첫 번째 블록의 첫 번째 페이지 프레임의 물리 주소는 2 * b * 2(2의 12승. 이거 수학식)의 배수이다.

정리

기능 추가 및 결과 : 버디 메모리 할당은 최신 운영 체제에 쓰이는 메모리 할당 기술들에 비해 상대적으로 구현하기가 쉬운 편이다.

동적 할당과 같은 다른 간단한 기술들에 견주어 볼 때, 버디 메모리 시스템은 약간의 외부 단편화와 메모리 간결화를 하는 오버헤드를 가지고 있다.

버디 메모리 할당 기술이 작동 방식 때문에 적당한 양의 내부 단편화가 있을 수 있다. 다시 말해, 요청된 메모리가 작은 블록보다 조금 더 크면 메모리가 낭비된다.(66K 메모리를 요청한 프로그램은 128K가 할당되는데, 결과적으로 62K의 메모리가 낭비된다.)

출처 - MDS 교육 자료