메모리관리

# 가상메모리

# SMP (Symmetric Multiprocessing)

: 모든 CPU가 메모리와 입출력 버스 등을 공유하는 구조

=> 병목현상 발생

# NUMA (Non-Uniform Memory Access)

: SMP 구조에서 병목현상이 발생하여 CPU들을 몇개의 그룹으로 나누고 각 그룹에게 별도의 지역 메모리를 할당

<-> UMA (Uniform Memory Access)

# Node 

: 리눅스에서 뱅크를 표현하는 구조

- bank : 리눅스에서 접근 속도가 같은 메모리의 집합을 부르는 말

- ~/include/linux/mmzone.h

- UMA구조에서는 뱅크가 한개, NUMA 구조에서는 뱅크가 여러개

- 리눅스의 전역변수인 contig_page_data변수로 뱅크에 접근 가능

- NUMA처럼 뱅크가 복수개인 경우, pgdat_list라는 배열을 통해 뱅크에 접근이 가능

=> 리눅스에서는 하드웨어 시스템에 관계없이 노드라는 일관되 자료구조를 통하여 전체 물리메모리에 접근이 가능

# pg_data_t 자료구조

: UMA구조에서 단일노드를 contig_page_data변수로, NUMA구조에서 복수노드를 pgdat_list 배열로 가리켜도

 두 변수는 pg_data_t 구조체를 통해 표현

------------------------------------------------------------------------------------------------------------------------------------------------------------

typedef struct pglist_data {

struct zone node_zones[MAX_NR_ZONES];        // zone 구조체를 담기위한 배열

struct zonelist node_zonelists[GFP_ZONETYPES];    

int nr_zones;        // zone의 개수를 저장

...

unsigned log node_start_pfn;        // 해당 물리메모리가 메모리 맵의 번지수를 저장하는 변수

unsigned long node_present_pages;    // 해당 노드에 속해있는 물리메모리의 실제 양을 저장하는 변수

unsigned log 

...

} pg_data_t;

------------------------------------------------------------------------------------------------------------------------------------------------------------

* 물리메모리 할당 요청시 태스크가 수행되고있는 CPU와 가까운 노드에서 메모리 할당을 시도

# zone

: 일부 ISA 버스 기반의 디바이스를 지원하기위해, node의 일부분(16MB이하 부분)을 따로 관리할 수 있도록 자료구조를 만듬

(물리메모리 중 반드시 16MB 이하 부분을 할당해 주어야 했음)

- ~/include/linux/mmzone.h

- 동일한 속성을 가짐

- 다른 zone의 메모리와는 별도로 관리되는 메모리 집합

- ZONE_DMA, ZONE_DMA31 : 특별히 관리되는 16MB 이하의 메모리

(16MB 이상의 메모리는 ZONE_NORMAL이라고 함)

- ZONE_HIGHMEN : 1GB이상의 메모리를 필요로하는 경우 바로 커널의 가상주소공간과 1:1로 연결해주는 것은 비효율 적이라고 판단하여 

896MB의 물리메모리만 커널의 가상주소공간과 1:1로 연결하고, 나머지 부분은 필요할 때 동적으로 할당하는데,

이때 896MB 이상의 메모리 영역을 일컫는 용어

- 모든 시스템에서 언제나 DMA. NORMAL, HIGHMEN이라는 세개의 zone이 존재하는 것은 아님

- 각각의 zone은 자신에게 할당된 물리메모리의 관리를 위해 zone 구조체를 사용

해당 zone에 속해있는 물리 메모리의 시작주소, 크기

버디할당자가 사용할 free_area 구조체를 담는 변수 등등

- watermark와 vm_stat를 통해 남아있는 빈 공간이 부족한 경우 적절한 메모리 정책을 결정

- page가 부족하여 메모리 할당 요청에 대하여 실패한 경우 프로세스들을 wait_queue에 넣고 hashing을 수행하여 wait_table변수가 가리키게 함

- cat /proc/zoneinfo 명령어를 통해 확인

# Page Frame

: 물리메모리의 최소 단위

- zone은 자신에게 속한 물리메모리를 관리

- 각각의 페이지 프레임은 page 구조체로 관리 (~/include/linux/mm_types.h)

- 페이지 프레임 당 하나의 page 구조체가 존재. (모든 물리메모리에 접근이 가능해야하므로)

- page frame : 하나의 페이지로 관리

- zone : 복수개의 페이지 프레임으로 구성

- node : 하나 또는 복수개의 node로 구성

- 리눅스의 전체 물리 메모리 : 하나 또는 복수개의 node 

# Buddy와 Slab

- 내부 단편화문제를 해결하기 위해 슬랩할당자 사용

- 메모리관리의 부하와 외부 단편화의 해결을 위해 버디할당자 사용

* 물리메모리는 설정한 페이지프레임의 최소단위로 할당

(기본 4KB, 8KB와 2MB 등으로도 설정이 가능)

# Buddy Allocator

- 페이지프레임이 4KB의 경우 10KB를 할당하려할 때 3개의 페이지프레임으로 할당하지 않고 16KB를 할당        

=> 메모리관리의 부하를 줄이고 외부 단편화를 방지

* 커널 2.6.19버전 이전에서 사용되던 버디 

- zone 구조체에 존재하는 free_area[]배열을 통해 구축

- zone 당 하나의 버디가 존재

- free_area[] 배열의 각 엔트리는 free_area 구조체

- free_area 구조체는 free_list와 map이라는 필드를 가짐

------------------------------------------------------------------------------------------------------------------------------------------------------------  

/* ~/include/linux/mmzone.h  */

#define    MAX_ORDER    10        // 10개의 엔트리를 가짐. 0~9의 각 숫자는 해당 엔트리의 free_area가 관리하는 할당의 크기를 나타냄

// 0인경우 2^0으로 1개의 페이지프레임 할당, 1인경우 2^1이므로 2개의 페이지프레임 할당 

// 4KB, 8KB, 16KB... 4MB(2^10 * 4KB) ---> 이 단위들로 메모리 할당이 가능

struct zone {

...

struct free_area    free_area[MAX_ORDER];    // 

...

};

struct free_area {                

struct list_head    free_list;      // 자신에게 할당된 free 페이지 프레임을 list로 관리

// ex. free_list[1]에 free상태의 연속된 2개의 페이지 프레임들이 free_list로 연결

unsinged long     *map;         // 자신이 관리하는 수준에서 페이지의 상태를 bitmap으로 관리

// ex. 전체 물리메모리를 2개의 페이지 프레임 단위로 봤을 때의 상태를 map이라는 bitmap에 저장

};

------------------------------------------------------------------------------------------------------------------------------------------------------------  

그림 출처. https://lwn.net/Articles/121618/

* order(0) -> free_area[0]

  order(1) -> free_area[1]

  ...

* 버디할당자 동작방식

Linux kernel physical memory allocator (Buddy) - Part 2-1

http://woodz.tistory.com/57

http://woodz.tistory.com/58

http://woodz.tistory.com/59

http://woodz.tistory.com/60

# Lazy Buddy

- 커널 2.6.19부터는 free_area 구조와 버디 할당자의 구현이 조금 바뀐

- 프레임에 할당하거나 해제하는 작업에서 페이지를 쪼개거나 합치는데 이럴 때 비트맵 수정도 필요함

- 반복 과정에서 오버헤드가 발생

- 페이지프레임에 대한 작업을 조금 미루자!

 *변경된 free_area 구조체

------------------------------------------------------------------------------------------------------------------------------------------------------------

/* ~/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;      

unsinged long    nr_free;    // 기존의 비트맵 포인터에서 자신이 관리하는 zone내에서 비사용중인 페이지 프레임의 갯수를 저장하는 변수로 바뀜

};

------------------------------------------------------------------------------------------------------------------------------------------------------------

- zone 마다 유지되고 있는 watermark(high, low, min)값과 현재 사용가능한 페이지 수를 비교

- zone에 가용 메모리가 충분한 경우 해제된 페이지의 병합 작업을 최대한 뒤로 미룸

- 가용 메모리가 부족해지는 경우 병합작업을 수행

* 병합작업

- __free_pages(), 버디에 메모리를 반납하는 함수

- __free_pages()함수는 내부적으로 __free_one_page()라는 함수를 호출

- __free_one_page(), MAX_ORDER만큼 루프를 돌면서 현재 해제하는 페이지가 버디와 합쳐져서 상위 order에서 관리될 수 있는지 확인

- 가능하면 현재 order의 nr_free를 감소시킴

, 상위로 페이지를 이동 후 상위 order의 nr_free를 증가  

=> 해당 작업을 반복하여 전체 order의 버디를 동작

- __alloc_pages() : 버디 할당자로부터 페이지를 할당받는 커널 내부 함수 중 가장 저수준의 함수

- __free_page() : 페이지를 해제하는 함수

- 2의 승수의 크기 단위로 관리하므로 함수 호출시에도 메모리의 크기를 2의 승수로 지정

- 복수개의 zone에 각각의 버디 할당자가 동작할 수 있는 상황에서는 어느 zone에서 메모리를 할당 받았는지 같은 몇몇 속성을 지정해 주어야 함

- 현재 시스템의 버디 할당자 관련 정보 조회 : "$ cat /proc/buddyinfo"

# Slab Allocator

: 일종의 캐시의 집합을 통하여 메모리를 관리하는 정책

- 페이지 프레임의 크기가 요청되는 메모리의 크기와의 차이가 상대적으로 많이 날 수록 내부 단편화로 낭비되는 공간이 증가

- 미리 페이지 프레임을 할당 받은 후 일정한 크기로 분할 해 둔 뒤 사용자가 메모리를 요청하면 버디할당자가 아닌 미리 할당받아 분할한 이 공간(일종의 캐시)에서 공간을 받아옴

- 해제 역시 중간의 이 공간에 이루어짐

- 현재 시스템의 slab 할당자와 관련된 정보조회 : "$ cat /proc/slabinfo"

출처. http://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/9_VirtualMemory.html

- 캐시의 크기?