2022. 9. 19. 01:21ㆍ개발 관련 책 읽기/리눅스 커널 내부구조
각각의 zone은 자신에 속해 있는 물리 메모리들을 관리하는데, 바로 이 물리 메모리의 최소 단위를 페이지 프레임이라 부른다. 각각의 페이지 프레임은 page라는 구조체에 의해 관리된다.
커널은 시스템 내의 모든 물리 메모리에 접근 가능해야 한다. 이를 위해 모든 페이지 프레임 당 하나씩
page 구조체가 존재한다. 시스템이 부팅되는 순간에 물리 메모리의 특정 위치에 로드 된다. 이 위치는 mem_map이라는 전역 배열을 통해 접근 가능하다.
Buddy&Slab
리눅스는 page frame, zone, node라는 구조를 통해 시스템에 존재하는 전체 물리 메모리를 관리할 수 있다. 그럼 리눅스는 자신이 가지고 있는 물리 메모리를 어떻게 할당 또는 해제할까?
리눅스는 물리 메모리의 최소 관리 단위인 page frame 단위로 할당하도록 결정하였다.
결국 4KB가 최소 할당 단위가 된다(8KB, 2MB 등 크기는 설정 가능하다).
그런데 만약 4KB보다 작은 크기를 요청하면 어떻게 될까? 30Byte or 100Byte처럼 작은 크기를 요청할 경우 4KB를 할당해주면 내부 단편화(Internal Fragmentation) 문제가 발생하게 된다.
리눅스는 이를 해결하기 위해 슬랩 할당자(Slab Allocator)를 도입하였다.
만약 10KB를 요청하게 된다면 3개의 page frame을 할당하면 내부 단편화를 최소화할 수 있다.
하지만 리눅스는 16KB를 할당해주는 버디 할당자를 사용하게 된다. 버디 할당자가 메모리 관리의 부하가 적으며 외부 단편화를 줄일 수 있다는 장점을 제공하기 때문이다.
*내부 단편화(internal fragmentation)
분할의 사용하고 남은 일부분을 말한다. 예를 들어 '100'크기를 갖는 분할에 '80'크기를 갖는 프로그램을 배치하였을 경우 '20'의 공간이 내부 단편화 공간이 된다.
*외부 단편화(external fragmentation)
분할의 크기가 프로그램의 크기보다 작아서 사용되지 못한 것을 말한다. 예를 들어 '100' 크기를 갖는 분할이 있을 때 '120' 크기를 갖는 프로그램은 배치되지 못하며 '100'의 공간이 외부 단편화 공간이 된다.
버디 할당자
버디 할당자는 zone 구조체에 존재하는 free_area[]배열을 통해 구축된다. 따라서 버디는 zone당 하나씩 존재하게 된다.
// ~/include/linux/mmzone.h
#define MAX_ORDER 10
struct zone{
....
....
....
struct free_area free_area[MAX_ORDER];
};
struct free_area{
struct list_head free_list;
unsigned long *map;
};위의 소스 코드는 커널 2.6.19버젼 이전에 사용되던 버디이며, 현재는 Lazy 버디라 불리는 새로운 버디가 사용되고 있다. 우선 일반적인 버디에 대해 알아보자.
free_area 배열은 10개의 엔트리를 가진다. 0~9까지 각각의 숫자는 해당 free_area가 관리하는 할당의 크기를 나타낸다. 예를 들어 0인경우 20 즉, 1개의 페이지 프레임이 할당의 단위임을 뜻하고
1인경우 21 2개의 페이지 프레임, 결국 버디는 2의 정수 승 개수의 페이지 프레임들을 할당해주며
리눅스 구현상 최대 할당 크기는 4MB(210 * 4KB)이다.
free_area 구조체는 free_list 변수를 통해 자신에게 할당된 free 페이지 프레임을 list로 관리한다.
또한 자신이 관리하는 수준에서 페이지의 상태를 map변수를 통해 비트맵으로 관리한다.
예를 들어 free_area[1]에는 free상태인 연속된 21(2)개의 페이지 프레임들이 free_list를 통해 연결되어 있고, 또한 전체 물리 메모리를 2개의 페이지 프레임 단위로 봤을 때의 상태를 map이라는 변수의 비트맵에 저장하고 있다.
버디 할당자는 요청된 크기를 만족하는 최소의 order에서 페이지 프레임을 할당해 준다.
만일 그 order에 가용한 페이지 프레임이 존재하지 않으면 상위 order에서 페이지 프레임을 할당받아
두 부분으로 나누어, 한 부분은 할당해주고 나머지 부분은 하위 order에서 가용 페이지 프레임으로 관리한다.이때 나누어진 두 부분을 친구(Buddy)라고 부르며 이 때문에 버디 할당자라고 부른다
Lazy Buddy
커널 버전 2.6.19부터 free_area의 구조와 버디 할당자의 구현이 바뀌어 Lazy 버디가 도입되었다.
그렇다면 기존의 버디에 어떠한 문제가 있었기에 새로운 알고리즘이 나왔을까?
할당/해제 작업을 반복하게되면 할당/해제 작업을 위한 많은 오버헤드가 발생하게 된다. 따라서
할당되었던 페이지 프레임을 애써 합치지 말고, 곧 다시 할당 될 테니 되도록 합치는 작업을 미루면
어떨가 라는 생각으로 Lazy 버디가 나오게 되었다.
비트맵 포인터(*map)가 nr_free라는 변수로 바뀌었다.
nr_free는 자신이 관리하는 zone내에서 비사용중인 페이지 프레임의 개수이다.
// ~/include/linux/mmzone.h
#define MAX_ORDER 11
struct zone{
....
....
....
struct free_area free_area[MAX_ORDER];
};
struct free_area{
struct list_head free_list;
unsigned long nr_free;
};<변경 된 free_area 구조체>
버디는 zone마다 watermark(high,low,min)값과 현재 사용가능한 페이지의 수를 비교한다.
이를 통해 zone에 가용 메모리가 충분한 경우 해제된 페이지의 병합 작업을 최대한 뒤로 미룬다.
만약 가용메모리가 부족해지는 경우에는 버디에 메모리를 반납하는 함수인 __free_pages() 함수는 내부적으로 __free_one_page()라는 함수를 호출하는데 이 함수는 MAX_ORDER만큼 루프를 돌면서
현재 해제하는 페이지가 버디와 합쳐져서 상위 order에서 관리될 수 있는지 확인한다.
가능한 경우 현재 order의 nr_free를 감소시키고,상위로 페이지를 이동 시킨 뒤, 상위 order의 nr_free를 증가시킨다. 이러한 작업을 반복하여 전체 order의 버디를 원할히 동작시켜 주게 된다.
버디 할당자로부터 페이지를 할당받는 커널 내부 함수중 가장 저수준 함수의 이름은 __alloc_pages()
이며 반대로 해제하는 함수의 이름은 __free_pages()이다. 2n 크기 만큼 페이지를 연속적으로 관리하고 있다가 요청이 들어오면 이들을 할당/해제하며 관리하는 것이 버디 할당자이므로 메모리 크기를 2의 승수만큼 지정해 주어야 한다.또한 복수 개의 zone에 각각의 버디 할당자가 동작하고 있을 수 있기 때문에 어느 zone에서 메모리를 할당 받은 것인지와 함께 몇 가지 속성을 지정해 줘야한다.
cat /proc/buddyinfo 를 통해 버디 할당자 관련 정보를 볼수 있다.
슬랩 할당자
버디 할당자를 이용하면 최대한 큰 연속된 공간을 유지하면서 효율적으로 메모리를 관리할 수 있다.
그런데 한 가지 문제가 발생한다. 만약 사용자가 64Byte의 공간을 요청하면 어떻게 해야 할까?
그보다 더 적은 크기의 공간을 요청하면? 같은 의문점이 발생할 수 있다.
메모리 최소 할당 단위인 Page Frame 한 개를 할당 해 줘야 한다. 그러면 page frame크기가 클수록 내부 단편화로 인한 낭비되는 메모리가 역시 많아질 것이다.
위의 문제를 해결하기 위해 free page frame 4KB를 미리 할당 받은 뒤 이 공간을 64Byte로 나누면
64개의 공간이 생길것이다. (64*64 = 4KB) 그런 뒤 process가 64Byte를 요청하면 버디 할당자로부터 할당받아오는 것이 아니라 미리 할당받아 분할하여 관리하고 있던 공간에서 할당해주는 것이다.
추후 process가 해제한다면 역시 버디로 반납하는것이 아니라 미리 할당 받아 관리하던 공간에서 다시 가지고 있으면 된다. 마치 일종의 캐시로 사용하는 것이다. 이러한 cache의 집합을 통해 메모리를 관리하는 정책을 바로 슬랩 할당자라 부른다. proc/slabinfo 를 통해 슬랩 할당자 관련 정보를 볼 수 있다.
그렇다면 어떤 크기의 cache를 가지고 있어야 내부 단편화를 최소 시킬 수 있을까?
자주 할당되고 해제되는 크기의 cache를 가지고 있어야 할것이다.그래서 태스크가 생성되고 제거될 때마다 할당/해제되어야 하는 task_struct를 위한 공간처럼 커널 내부에서 자주 할당/해제되는 자료구조의 크기를 위한 cache를 유지한다. 또한 일반적인 메모리 할당 요청에 대비하기 위해 32Byte에서부터 시작되는 2N승 크기의 cache를 128KB(최근에는 4MB)크기까지 유지한다.
각 cache는 슬랩들로 구성되고 슬랩은 다시 객체(object)들로 구성된다. 예를 들어 64Byte cache라면
64Byte 공간들이 각각 객체에 대응되고 이 객체들이 모여서 슬랩이 되고, 다시 슬랩이 모여 cache가 되는 것이다. 슬랩은 구성하고 있는 객체들의 상태에 따라 Full,Free,Partial로 구분된다.
Free 슬랩은 모든 객체가 사용 가능한 상태이고,Full 슬랩은 모든 객체가 이미 사용 중인 상태이며,
Partial 슬랩은 일부는 사용 일부는 비사용 중인 상태이다. 결국 슬랩 할당자에게 메모리 공간의 할당 요청이 들어온다면 가장 적합한 크기의 캐시를 찾아가서, partial 슬랩으로부터 객체를 할당해준다.
리눅스는 다양한 크기의 캐시를 효율적으로 관리하기 위해 kmem_cache라는 자료구조를 정의해 두었다.이 구조체는 각각의 캐시가 담고있는 객체 크기는 얼마인지 등의 정보를 표현한다.
따라서 새로운 캐시를 생성하기 위해서는 kmem_cache라는 구조체부터 할당받아야 한다.
만약 버디 할당자로부터 할다받으면 4KB(page frame)- sizeof(kmem_cache)만큼의 공간을 낭비하게 될것이다. 그러므로 슬랩 할당자로부터 할당을 받아야 한다. kmem_cache 구조체 크기의 객체를 담고 있는 캐시의 이름이 바로 cache_cache이다. 따라서 cache_cache는 다른 캐시들 보다 먼저 생성되어야 하며, 그런 후에야 이곳에서 kmem_cache를 위한 공간을 할당받아 다양한 캐시를 생성할 수 있게 되는 것이다. 슬랩 할당자로부터 객체를 할당받는 저수준 함수는 kmem_cache_alloc()이먀, 반대로 해제하는 함수는 kmem_cache_free()이다.
특정 크기의 공간을 위한 캐시를 유지하는 것이 슬랩 할당자이므로 이들 함수는 어느 캐시에서 공간을 할당받고,어느 캐시로 공간을 해제시켜야 하는지를 지정해 주어야 한다 더 이상 할당해줄 공간이 없다면 슬랩 할당자는 버디로부터 free page frame을 더 할당받아야 하는데 이때 kmem_cache_grow()같은 함수를 호출하여 슬랩을 확장한다.
또한 슬랩 할당자는 외부 인터페이스 함수로 kmalloc/kfree()를 제공하며, 이 함수를 통해 슬랩 할당자로부터 임의의 크기의 메모리 공간을 할당받을 수 있다. 이러한 용도를 위해 128KB(4MB)크기까지의 캐시를 유지하므로,kmalloc()함수를 이용해 한 번에 할당 받을 수 있는 최대 크기는 128KB 혹은 4MB이며 할당된 공간은 물리적으로 연속이라는 특징을 가진다.
슬랩 할당자의 디테일한 내용은 밑의 블로그에 가면 알수 있다.
http://timewizhan.tistory.com/entry/%EC%8A%AC%EB%9E%A9-%ED%95%A0%EB%8B%B9%EC%9E%90Slab-Allocator
커널은 메모리의 단편화를 조금이나 해결하기 위해 다양한 방법을 사용한다. 그 중에 현재 커널은 버디 시스템과 슬랩 할당자를 사용하는데.. 외부 단편화를 해결하기 위해서는 버디 시스템, 내부 단편화를 해결하..
'개발 관련 책 읽기 > 리눅스 커널 내부구조' 카테고리의 다른 글
| Chapter 5 - 파일 시스템(1) (1) | 2022.09.19 |
|---|---|
| Chapter 4 - 메모리 관리(3) (1) | 2022.09.19 |
| Chapter 4 - 메모리 관리(1) (0) | 2022.09.19 |
| Chapter 3 - 태스크 관리(4) (0) | 2022.09.19 |
| Chapter 3 - 태스크 관리(3) (0) | 2022.09.19 |