Chapter 9. Process Address Space

 

As seen in the previous chapter( this is 8)

 

a kernel function gets dyanamic memory in a fairly straightforward manner by invoking one of a variety of functions

 

  • Get_free_pages() or alloc_ages(): To get pages from the zoned page frame allocator(buddy system algorithm 
  • kmem_cache_alloc() or kmalloc(): To use the slab allocator for specialized or general-purpose objects
  • vmalloc() or vmalloc_32(): To get a noncontiguous memory area
  •  

 

이제 위 함수들을 이용해서 request가 정상적으로 처리가 된다면

각각의 함수들은 page descriptor address 또는 linear address를 return 한다.

이러한 반환되는 주소들을 이용해서 allocated dynamic memory area의 beginning을 identifying 할 수 있다.

 

위와 같은 simple approache들은 2개의 reason이 있다.

 

1) 커널은 운영체제에서 우선순위가 가장 높은 구성 요소이다. 커널 함수가 동적 메모리를 요청 하려면 반드시 정당한 이유가 있는 것이고, 이러한 요청을 더는 뒤로 미룰 수없다.

 

2) 커널은 자신을 신뢰한다. 모든 커널 함수는 오류가 없다고 가정하기 때문에 프로그래밍 오류로부터 보호할 필요가 없다.

 

When allocating memory to User Mode rpocesses, the situation in entirely different :

 

1) 프로세스꺼는 최대한 연기된다.

2) 사용자 프로그램은 cannot be trusted 이다. 따라서 kernel은 must be prepared to catch all addressing erros caused 해야 한다.

 

 

이장에서는 커널이 새로운 종류의 자원을 이용하여 프로세스에 동적 메모리를 할당하는 일을 연기할 수 있게 한다.

사용자 모드 프로세스가 동적 메모리를 요청하면 커널은 페이지 프레임을 추가로 할당해 주지 않고, 선형 주소의 새로운 범위를 사용할 수 있는 권할을 주는데, 이 범위는 프로세스 주소 공간의 일부가 된다.

 

이장에서 다루는 내용

 

  • 프로세스가 동적 메모리를 어떻게 바라보는지 관점에 대해서 설명한다.
  • 전체 메무리 구역에서 볼때 프로세스 주소 공간이 어떤 기본 구성 요소로 이루워저 있는지를 본다.
  • 프로세스에 페이지 프레임을 할당하는 일을 미룰 때 페이지 폴트 예외 핸들러의 역할을 살펴 본다.
  • 커널이 모든 프로세스 주소 공간을 만들고 삭제하는 방법을 설명 한다.
  • 주소 공간을 관리하는 API와 System call을 설명 한다.

User Mode의 Process가 동적 메모리를 요청하면 커널은 페이지 프레임을 추가로 할당해주지 않고, Linear address의 new range를 주게 된다. 이 범위는 프로세스 주소 공간의 일부가 된다.

이러한 구간을 가리켜 Memory Region이라고 한다.

 

즉, page frame들을 allocating하는 대신에 일단 range만 잡아주는 꼴이 된다.

 

9.1 The Process's Address Space

 

프로세스 address space는 프로세스가 사용할 수 있는 모든 linear address로 구성 된다.

이 주소공간은 서로 배타적이므로, 프로세스 끼리 절대로 관련성이 없다.

 

커널은 선형 주소 구간을 추가하거나 삭제하여 프로세스의 주소 공간을 동적으로 변경 할 수 있다.

 

커널은 프로세스가 현재 소유하는 메모리 구역을 반드시 파악하고 있어야 한다. 왜나하면 페이지 폴트에 대해서 핸들링을 해줘야 하기 때문이다.

 

Lenth of a memory region : The initial address and the lenth of a memroy region must be multipes of 4,096Byte

 

 

9.2 The Memory Descriptor

 

프로세스 주소 공간과 관련한 모든 정보는 "Memory Descriptor"라는 객체에 들어 있다.

이 Object는 mm_struct type이고, Process Descriptor의 mm filed를 가리킨다.

 

When to Get New Memory Regions

 

  1. 새로운 프로세스 생성

  2. exec 시스템 콜로 다른 프로그램을 load 한다.

  3. mmap() system call을 이용해서 "memory mapping"을 한다.  mmap() : 파일에 대한 메모리 mapping을 만들어 process address space를 enlarging 한다. 잘은 모르겠지만, 뭔가 딴거를 일단 process address space로 맵핑 시켜 버리는것 같다. 그래서 process의 주소를 키우는것 같다.

  4. Process의 User Mode stack 사이즈를 키운다.

  5. IPC를 위해 shared memory region을 생성 한다.

  6. heap 그러닌까, process's dyanamic area를 expand 한다. malloc을 이용해서

 

 

 

Porcess Descriptor로 접근하는 방법은 위 그림과 같다.

즉 task_struct의 mm필드로 가서 그 포인터가 지시하는 mm_struct를 가면

memory descriptor의 정보를 알 수 있다.

 

The Memory Descriptor

 

pgd: 페이지 전역 디렉터리를 가리키는 포인터

 

rss: 프로세스에 할당되어진 페이지 프레임의 수, 이것을 조사해보면 main memory가 얼마나 사용 되고 있는지를 알 수 있다.

 

total_vm: 프로세스 주소 공간의 크기(페이지의 수)

 

mmlist: 메모리 디스크립터 리스트에서 인접하는 항목을 가리키는 포인터

 

start_code / end_code: 실행 코드의 시작 주소와 끝 주소

 

brk: heap의 현재 끝 주소

 

mm_users: 2차 사용 횟수 라고 나와있는데 자세히 설명 하면, LightWeight process가 몇게가 mm_struct를 공유하고 있는지 그 숫자를 의미 하게 된다.

 

mm_count: 1차 사용 횟수

즉 이것의 의미는, 메모리 디스크립터의 1차 사용 횟수로 mm_users에 있는 모든 '사용자를 즉 Light-Weight process의 사용을 mm_count에서는 한 단위로 카운트 한다.

Kernel은 mm_count 필드를 감소킬 때마다 이 값이 0이 되는지 검사하여, 0이되면 더는 사용ㅎ지 않는 것이므로 메모리 디스크립터를 해지 한다.

 

예를 들어 설명,

 

LWP 1

LWP 2

위 2개의 프로세스가 mm_struct를 공유한다.

따라서 mm_users = 2, mm_conunt =1이다.

 

이떄 mm_struct를 kernel thread에게 빌려준다. 그러면 mm_count가 2로 증가한다.

이때 LWP1,2가 모두 종료되어도 mmcount는 1만 감소해서 1이 남기 때문에 mm_struct를 유지하게 된다.

물론 try_to_unuse() 함수를 이용해서 mm_count를 증가시켜도 동일한 결과를 얻는다.

 

 

Memory Regions 

 

리눅스 vm_area_struct 타임의 객체를 이용하여 메모리 구역(memory region)을 구현한다.

 

각각의 memory region descriptor는 linear address 구간을 identifiy할 수 있도록 한다.

이 strcut의 filed로는 다음의 것들이 있다.

vm_start: start adress

vm_end: end address

vm_mm : 해당 구역을 소유하는 메모리 디스크립터를 가리키는 포인터

프로세스의 mm_struct 즉, 프로세스가 가지고 있는 memory descriptor를 포인팅 한다.

 

프로세스들은 결고 서로의 memory region을 overlap하지 않는다.

 

 

 

위 그림에서 볼 수 있듯이, 새로운 선형 주소 범위를 프로세스의 주소 공간에 추가할 때 커널은 기존의 메모리 구역을 확장할 수 있는지 검사한다. (a 경우) 가능하다면 확장을 한다.

 

그렇지 않으면 b의 경우 처럼 새로운 메모리 구역을 생성 한다. (b의 경우)

 

마찬가지로 프로세스의 주소 공간에서 선형 주소 범위를 제거할 때 커널은 이에 영향을 받는 메모리 구역의 크기를 조정한다. (c의 경우)

 

어떤 경우에는 크기를 조정할 때 한 메모리 구역이 작은 구역 두개로 나뉘기도 한다. (d의 경우)

 

 

 

 

 

 

Memory Region Data Structures

 

위 그림은 프로세스의 address space와 memory desscriptor, memory region list 사이의 관계를 보여 준다.

 

커널이 자주 하는 일 중 하나는 특정 선형 주소를 포함하는 메모리 구역을 찾는 것이다. 리스트는 정렬 되어 있으므로 메모리 구역의 끝이 지정한 선형 주소 이후에 있는 구역을 찾는 즉시 검색을 종료 한다.

 

 

이러한 리스트 구조는 일반적인 상황에서는 큰 문제가 없지만,

 

객체지향 데이터베이스, malloc() 사용과 관련된 특수한 디버거처럼 수백 내지 수천 구역을 소유하는 큰 응용 프로그램에서는 메모리 구역 리스트를 관리하는 것은 매우 비효율 적이고, 메모리와 관련한 시스템 콜의 성능은 참을 수 없을 만큼 떨어 진다.

 

그래서 리눅스 2.6은 Red_Black Tree라는 자료구조에 Memory descriptor를 저장 한다.

여기서 Node는 보통 left child와 Right child이라는 두 child를 가진다.

 

Read Black tree는 다음과 같은 네가지 규칙을 준수 한다.

 

1) 모든 노드는 빨강이나 검정 중 하나이다.

2) 트리의 Root는 검정이다.

3) Read node의 child는 black이다.

4) 어떤 Node에서 Leaf에 이르는 모든 길에는 같은 수의 black node가 있어야 한다. The number of black node를 셀 때 NULL pointer도 balck node로 계산 한다.

 

Theses four rules ensure that every red0black tree with n internal nodes has a height of at most

 

 

따라서 트리에서 필요한 Node를 찾는 시간은 트리 크기에 로그를 취한 값에 그대로 비례하기 때문에 매우 효율적이다.

 

 

Memory Descirptor 즉 mm_struct의 필드에는

mmap 필드가 있다. 이는 연결 리스트의 head를 포인팅 하게 된다. 모든 Memory region object는 list에서의 다음 object를 포인팅하기 위한 vm_next 필드를 가지고 있다.

 

mm_struct에는 또한 mm_rb 필드가 있다. 이것은 red_back tree의 root를 가리킨다. 모든 memory region object는 rb_node type의 vm_rb 필드에 node의 color와 함께 parent와 left child, right cild에 대한 pointer를 store한다.

 

일반적으로 특정 주소를 포함하는 구역을 찾을 때는 red-black tree를 사용하고, 전체 구역을 검색할 때 연결 리스트가 유용 하다.

 

 

Memory Region versus pages

 

 

 

Page: a set of linear addresses and the data contained in the set of linear addresses

e.g ) the page 0 : linear address interval ranging between 0 and 4095

 

Memory region: consists of a set of pages having consecutive page numbers(of linear addresses)

 

 

 

Memory Region Handling

 

do_mmap() : allocates(enlarge) a linear address interval, After a successful allocation, the memory region could be merged with other memory regions defined for the process.

 

do_munmap(): Delete a linear address interval from the address space of the current process, the intervall to be deleted does not usually correspond to a memory region

 

find_vma(): 지정한 주소에 가장 가까운 구역 찾기

 

find_vma_interseciton() : 지정한 구간과 겹치는 메모리 구역 찾기

 

get_unmapped_area() : 빈 주소 구간 찾기

 

insert_vm_struct() : 메모리 디스크립터 리스트에 구역 삽입

 

 

Page Falut Exception Handler

 

이것의 원인 2가지이다.

프로그래밍 오류

프로세스 주소 공간에 들어 있지만 아직 할당하지 않은 페이지를 참조해서 발생

 

do_page_fault()

page fault interrupt service routine

compares the linear address that caused the page fault against the memory regions of the current process.

 

 

 

 

Page Fault Exception handler

 

bad_area:

do_page_fault()함수가 실행 된다.

process address space에 들어있지 않으면 발생 한다.

사용자 모드에서 에러가 발생하면 current process에 SIGSEGV signal을 보낸다.

 

 

good_area:

 

do_page _falut()는 address가 프로세스의 주소 공간에 속하면 good_area 라벨에 있는 문장 부터 실행 한다.

쓰기 접근 때문에 예외가 발생하였다면 메모리 구역 쓰기 가능인지 검사한다. 쓰기가 가능하지 않으면 bad_area 코드로 점프하고, 쓰기가 가능하면 지역 변수 write를 1로 설정한다.

 

Demand paging

 

이것은 가능한 마지막 순간까지, 즉 프로세스가 램에 존재하지 않는 페이지 주소로 접근하여 페이지 폴트 예외가 발생하는 순간까지 페이지 프레임 할당을 연기하는 동적 메모리 할당 기법이다.

 

 

Copy on Write

 

페이지 프레임을 복사하는 대신에 부모 프로세스와 자식 프로세스 사이에 페이지 프레임을 공유하는 것이다.

그러나 공유하는 동안은 페이지 프레임의 내용을 바꿀 수 없다.

 

 

Process address Space의 Creating과 Deleting

 

clone() , fork(), vfork()

 

 

 

Managing the Heap

 

memory descirptor의 start_brk와 brk 필드가 각각 힙의 시작과 끝주소를 저장 한다.

 

다음 API는 프로세스가 동적 메모리를 요청하고 해지할 때 사용 한다.

 

malloc(size): 동적 메모리를 size바이트만큼 요청한다. 성공적으로 할당하면 시작 메모리 위치의 선형 주소를 반환 한다.

 

calloc(n, size) ; 크기가 size인 요소 n개로 구성된 배열을 요청 한다.

 

realloc

 

free

 

brk(addr): 직접 힙의 크기를 변경한다. addr 매개 변수는 current->mm->brk의 새로운 값을 지정하며, 결과 값은 메모리 구역의 새로운 끝 주소이다.(프로세스는 요청한 addr 값과 결과 값이 일치하는지 검사해야 한다.)

 

sbrk(incr): brk()와 비슷하지만 매개 변수 incr로 지정한 바이트만큼 힙의 크기를 늘리거나 줄인다는 차이가 있다.

 

 

 

 

 

 

 

'Computer Science > Linux Kernel' 카테고리의 다른 글

2장 메모리 주소 지정  (0) 2012.06.07
8장 메모리 관리  (1) 2012.06.07

 

가장 일반적인 아키텍쳐인 80x86에서의 메모리 주소 체계를 다루도록 한다.

 

□ 메모리 주소

 

80x86에서는 다음과 같은 3가지 주소로 구별 된다.

 

1) 논리 주소 : 인텔의 세그먼트 구조를 체계화 한것이다.

 

2) 선형 주소(Linear address = Virtual address) : unsigned int 주소로 즉 32bit로 4GB, 즉 메모리 셀 4,294,967,296개 까지의 주소를 지정 할 수 있다. 선형 주소(Virtual Address)는 보통 16진수로 표기한다. 0x00000000 ~ 0xFFFFFFFF

 

3) 물리 주소 : 메모리 칩에 들어 있는 메모리 셀을 지정하는 데 사용하는 주소이다.

 

 

 

위 그림이 설명한 3개의 주소가 하드웨어 장치 Sementation unit과 paging unit을 이용해서 최종적으로 Physical address로 변환되는 과정을 그림으로 나타낸 것이다.

 

 

※ Memory arbiter

 

멀티 프로세서나 유니프로세서와 DMA간의 동시 메모리 접근을 맊기위한 중간에 중재를 해주는 장치이다. 이것은 하드웨어적으로 동작하기 때문에 프로그래밍 관점에서는 보이지 않는다. 

 

□ 하드웨어 세그멘테이션 

 

인텔은 286이상부터 Real ModeProtected Mode라는 서로 다른 두 가지의 방법으로 주소 변환을 하기 시작 하였다.

 

보호모드에서 주소 변환이 발생한다.

리얼 모드는 운영체제가 부팅할 수 있도록 하기 위함과 호환성을 위해서 남겨둔 것이다.

 

2.2.1. Segment Selectors and Segmentation Registers

 

논리 주소는 두 부분으로 나뉘어 진다.

 

1) Segment Selector : 16bit

2) offset : 32bit

 

위 그림이 Segment selector를 나타낸다.

 

 

Segmentation Register : 프로세서가 세그먼트 셀렉터를 빨리 읽기위한 목적으로 사용된다. 즉 세그먼트 셀렉터를 담는 목적인 것이다.

 

여기에는 cs, ss, ds, es, fs, gs가 있다.

위 중에서 3개는 특별한 용도가 있다.

 

cs ( code segment register ) : 프로그램 명령어를 담고 있는 세그먼트를 가리킨다. 추가로 CPU의 현재 특권 수준(CPL, Current Privilege Level)을 나타내는 2비트의 필드가 있다.

 

ss (stack segment register) : 현재 프로그램의 스택을 담고 있는 세그먼트를 가리킨다.

 

ds (data segment register) : 정적인 데이터와 전역 데이터를 담고 있는 세그먼트를 가리킨다.

 

 

Ring 0는 가장 높은 특권 수준을 Ring 3은 가장 낮은 수준을 나타낸다.

여기서 리눅스는 0과 3만을 사용하게 된다. 이것들은 각각 커널 모드(Kernel Mode)와 사용자 모드(User Mode)로 불리운다.

 

 

2.2.2 Segment Descriptors 세그먼트 디스크립터

 

세그먼트의 특징을 기술하는 8바이트 크기의 '세그먼트 디스크립터로 각 세그먼트를 표현 한다.

 

세그먼트 디스크립터는

 

Global Descriptor Table = GDT 또는

Local Descriptor Table = LDT에 저장 된다.

 

보통 GDT는 단 하나만 정의한다.

 

2.2.3 Fast Access to Segment Descriptors

 

앞서 논리 주소는 16비트 크기의 Segment Selectors와 32비트 크기의 offset으로 구성된다.

 

근대, 여기서 Segment Register에는 Segment Selector만 저장된다고 언급 하였다.

 

80x86 프로세서는 논리 주소를 선형 주소로 빠르게 변환하기 위하여 아래의 레지스터들을 제공한다.

 

프로그래밍이 가능한 레지스터 6개: cs, ss, ds, es, fs, gs

프로그래밍이 불가능한 레지스터(Nonprogrammable)

 

 

 

 

□ 리눅스에서의 세그멘테이션

 

세그멘테이션과 페이징이라는 개념은 둘 다 프로세스의 물리 주소 공간을 나누기 위한 개념이므로 중복되는 것이 다소 있다.

 

세그멘테이션 : 각 프로세스에 다른 선형 주소 공간을 할당 한다.

페이징 : 똑같은 선형 주소 공간을 다른 물리 주소 공간과 매핑 시킨다.

 

리눅스에서는 다음과 같은 이유로 세그멘테이션을 제한적으로 사용하며, 페이징을 널리 사용 한다.

 

1) 모든 프로세스가 동일한 세그먼트 레지스터 값을 가지면, 즉 모든 프로세스가 동일한 선형 주소 공간을 공유하면 메모리 관리가 더 간단해 진다.

 

2) 리눅스 설계의 목적 중 하나는 대중적인 다른 아키텍처와 호환하게 하는 것인데, RISC 아키텍처에서는 세그멘테이션을 매우 제한적으로 지원 한다.

 

따라서 리눅스 2.6 버전에서는 80x86 아키텍처가 필요로 하는 경우에만 세그멘테이션을 사용 한다.

 

 

 

 

 

'Computer Science > Linux Kernel' 카테고리의 다른 글

9장 프로세스 주소 공간  (0) 2012.06.08
8장 메모리 관리  (1) 2012.06.07

2장에서 다룬 물리적 메모리를 논리적 주소매핑으로 관리하는 방법을 배웠다.

 

이제 램의 남은 부분은 동적 메모리라고 부른다.

 

이 동적 메모리는 프로세스 뿐만 아니라 커널 자신도 필요로 하는 소중한 자원이다.

 

모든 멀티태스킹 운영체제는 동적 메모리 사용을 최적화하고 필요할 때만 할당하고, 최대한 빠르게 처리하려고 한다.

 

[그림 8 -1] 동적 메모리

 

위 그림은 동적 메모리로 사용된 페이지 프레임을 그림으로 보여준다.

 

이 장에서의 핵심은 다음 3가지이다.

커널 자신이 어떻게 동적 메모리를 어떻게 할당하는지 설명

  • 메모리 영역 관리 (연속된 메모리 여역, 불연속적인 메모리 영역)
  • 메모리 지역, 커널 매핑, 버디 시스템, 슬랩 캐시, 메모리 풀

페이지 프레임 관리

 

프로세서가 페이지 프레임의 크기로 4KB와 4MB라는 서로 다른 두 크기를 사용하는 방법을 살펴 보았다.

페이지로 관리하면 장점은

1) 프로세서 차원에서 페이지 펄트를 지원할 수 있다.

2) 4K 4M중 작은 쪽이 디스크와 메모리사이의 데이터 전송에 유리 하다.

 

페이지 디스크립터

 

의미 : 커널이 각 페이지 프레임의 현재 상태를 알아야 하기 때문에 필요하 자료 구조이다.

 

페이지 디스크립터에 있는 필드 중 2개가 중요하다.

1) _count : 해당 페이지의 사용 참조 횟수이다.

2)  flags : 페이지 프레임의 상태를 기술하는 플래그이다. 이것은 최대 32개 까지 포함하는 배열이다.

 

불균등 메모리 접근 (Non-Uniform Memory

 

 

□ 메모리 지역

 

이상적인 컴퓨터 구조에서 페이지 프레임은 어떤 용도로 사용할 수 있는 메모리 저장 단위이다.

하지만 실제로는 그렇지 않다.

 

특히 80x86 아키텍쳐에서는 두가지 하드웨어 제약이 있다.

 

1) ISA 버스용 직접 메모리 접근(DMA, Direct Memory Access) 프로세서는 램의 처음 16MB만 접근 할 수 있다는 강한 제한이 있다.

 

2) 많은 램을 가지는 최근 32비트 컴퓨터에서는 선형 주로 공간이 너무 작아서 CPU가 모든 물리 메모리를 직접 접근할 수 없다.

 

이러한 제한을 해결하기 위해서 리눅스 2.6에서는 모든 메모리 노드의 물리 메모리를 세 가지 Zone으로 나눈다.

 

1) ZONE_DMA : 16MB 아래의 메모리 페이지를 포함한다.

2) ZONE_NORMAL : 16MB 부터 896MB 까지의 메모리 페이지를 포함한다.

3) ZONE_HIGHMEM : 896MB 이상의 메모리 페이지를 포함한다.

 

ZONE_DMAZONE_NORMAL 지역은 커널이 선형 주소 공간의 마지막 1GB로 선형 매핑하여 직접 접근할 수 있는 일반 페이지 프레임을 포함한다.

 

각 메모리 지역은 자신만의 디스크립터들을 가진다.

이러한 디스크립터의 많은 필드들은 페이지 프레임 회수를 위해서 사용되어진다.(자세한것은 17장에서 설명 된다.)

 

□ 예약된 페이지 프레임 풀

 

메모리 할당 요청은 두 가지 방식으로 충족 될 수 있다.

 

1) 여유 메모리가 충분한 경우 즉시 충족

2) 메모리를 해지하고 할당하는 경우

 

하지만 문제는 2번째 경우인데, 커널같은 경우 실행되어질 때 페이지가 할당될 수 없다고해서 메모리를 해지할 때까지 대기타는 그런 작업을 할 수가 없다. 왜냐하면 원자성을 충족 시켜야 하기 때문이다. 기다리거나 하는 그런 굼뜬(?) 작업을 하면 문제가 심각해 진다.

따라서 그냥 에러를 반환해버려서 최대한 빨리 처리해 버린다.

 

따라서 이러한 사태를 원천적으로 맊을 수는 없지만, 그나마 최소화 하기 위해서 커널은 페이지 프레임들의 Pool을 만들어 놓는다. 즉 미리 땡겨서 예약해 놓는다는 말이다.

 

이러한 미리 땡겨(?)쓰는 양은 min_free_kbytes 변수에 저장 된다.

이양은 커널 초기화 과정에서 설정되며, 물리 선형 주소의 마지막인 1G 이후에도 메모리가 얼마만큼 있는지에 따라서 가변적으로 결정된다.

 

 

하지만 초기 min_free_kbytes는 128에서 65,536 범위의 값이어야 하다.

(예약된 메모리의 양은 관리자가 /proc/sys/vm/min_free_kbytes 파일을 수정하거나 sysctl() 시스템 콜을 발생 시킴으로써 바꿀 수 있다.

 

□ The Zoned page Frame Allocator

 

Zoned Page Frame Allocator : 연속적인 페이지 프레임 그룹을 위해 메모리 할당 요청을 처리하는 커널 서브 시스템

 

위 구송요소를 보면 이해가 안된다. 당연하다 다음에 설명할 3가지 요소가 있다는 것만 기억하자.

 

1) 지역 할당자

2) 버디 시스템

3) CPU 별 페이지 프레임

 

□ Kernel Mappings of High-Memory Page Frames

 

결국 PAE(물리 주소 확장은) 프로세서의 핀 수를 36개로 늘려서 64GB까지 가질 수 있게 지원하지만,

상위 메모리를 매핑 할 수 있는 선형 주소 공간은 128MB이다.

1GB - 896MB = (1024 - 896)MB = 128MB

커널은 상위 메모리에 페이지 프레임을 매핑 시키기 위해 세가지 다른 메커니즘을 사용한다.

 

리눅스는 모든 RAM 영역의 접근을 아래의 방법들로 가능하게 한다. 즉 32bit 주소 체계가 표현할 수 있는 4GB 이상의 메모리 영역에 대해서 처리하는 방법을 다룬다는 것이다.

 

1) 무조건 alloc_pages() 또는 alloc_page()를 통해서 4G이상의 상위 메모리 페이지 프레임을 할당 할 수 있다. 단, 선형주소가 없기 때문에 페이지 프레임의 선형 주소를 반환하지는 않는다. 그 대신에 그 페이지 프레임의 페이지 디스크립터의 선형 주소를 반환한다.

이 페이지 디스크립터의 선형주소는 커널 초기화 과정에 이루어 지는 것으로 무조건 선형 주소가 존재하게 된다.

 

2) 커널은 선형 주소를 가지지 않는 상위 메모리 내 페이지 프레임을 접근할 수 없다.

그래서 커널 선형 주소 공간의 남는 부분은 128MB 부분을 상위 메모리 페이지 프레임을 매핑하기 위한 전용으로 사용 한다. 즉 이렇게 128mb로 돌려서 쓰는것이다. 따라서 동시에 동시에 상위 메모리에 접근 하는 것에 대해서 허용하지 않는다.

 

세부적으로 나누면 아래와 같이 3가지 방법이 있다.

하지만 결국 어느것도 동시에 64GB의 최대 램 영역을 동시에 접근할 만큼의 충분한 주소를 제공하지 못한다. 결국은 선형 주소공간의 남은양 128MB를가지고 이 4-64=60GB를 맵핑 하는 것이기 때문이다.

 

1) Permanent Kenrel Mapping : 영구 커널 매핑

2) Temporary Kernel Mapping : 임시 커널 매핑

3) Noncontiguous Memory Allocation : 불연속적인 메모리 할당

 

 

Permanent Kenrel Mapping : 영구 커널 매핑

이것을 사용할 경우 현재 프로세스는 블럭 되어 질 수도 있다. 4G이상의 메모리 영역을 접근 할때 여유 페이지 테이블 엔트리가 없을 때 일어날 수 있다.

따라서 인터럽트 핸들러나, 커널 쪽의 실행에서 이 방법을 쓸 수가 없다. 왜냐하면 블럭되면 안되기 때문이다.

 

Temporary Kernel Mapping : 임시 커널 매핑

이 방법의 장점은 절대로 블럭되어 지지 않는다는 것이다.

단점은 매우 적은 수의 임시 커널 매핑만 동시에 할 수 있다는 점이다.

이때는 반드시 다른 커널 제어 흐름이 이 방식을 사용하지 못하도록 해야 한다. 그래야 블럭이 되지 않기 때문이다.

 

Buddy System Algorithm 버디 시스템 알고리즘

 

External Fragmentation : 다른 크기의 연속적인 페이지 프레임 그룹을 빈번하게 할당하고 해지하여, 할당한 페이지 프레임 블록 사이에 작은 여유 페이지 프레임 여러 개가 '산재'하는 현상이다. 그 결과 나중에는 큰 크기의 연속된 페이지 프레임 할당을 요청할 때 이를 담을 충분한 여유 페이지가 있어도 메모리를 할당하지 못할 수도 있다.

 

리눅스는 이러한 External Fragmentation을 해결하기 위해서

그 유명한 Buddy System을 사용 한다.

Buddy를 사용하는 이유는 다음과 같다.

  • 실제로 연속된 페이지 프레임이 필요한 경우가 종종 있기 때문이다. 전형적으로 DMA의 경우
  • 가급적이면 연속된 페이지 프레임을 사용하자. 이러면 페이지 테이블을 덜 자주 수정하게 된다. 자주 수정하면 메모리 엑세스 타임이 늘어나고 느려지게 된다.

 

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

각 리스트는 연속된 페이지 프레임 1,2,4,8,16,32,64,128,256,512,1024개로 구성된 그룹을 담는다.

 

 

이제 간단한 예를 통해서 버디 시스템이 어떻게 동작하는지를 이해 해보자.

누군가 연속된 페이지 프레임 256개로 구성된 그룹 즉 1MB를 요청 하였다고 하자.

버디 알고리즘은 일단 256-페이지 프레임 리스트에 여유 블록이 있는지 검사한다.

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

페이지 프레임 512개 중에서 256개를 요청한 쪽으로 할당하고, 나머지 페이지 프레임 256개를 여유 256 페이지 프레임 블록 리스트에 추가한다.

 

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

 

여기에서 블록을 찾으면 ㅍ페이지 프레임 1,024개 중 256개를 요청한 쪽으로 할당하고, 나머지 768개 중 마지막 512개를 여유 512-페이지 프레임 블록 리스트에 남은 페이지 프레임 256개를 여유 256-페이지 프레임 블록 리스트에 넣는다. 1,024 페이지 프레임 블록 리스트가 텅 비어 있다면 할당을 포기를 하고 에러 상황을 알려 준다.

 

그리고 버디 알고리즘에서 페이지를 통합하는 방법은 아래의 알고리즘을 따른다.

1) 두 블록의 크기가 같다.

2) 두 블록이 연속된 물리적 주소에 우치한다.

3) 첫 번째 블록의 첫 번째 페이지 프레임의 물리 주소는 2 * b * 2^12의 배수 이다.

정리하면

Allocation = split

Free = merge

 

 

 

 

위에 말로 설명하는 것을 그림으로 변경하면 위와 같다.

 

 

Buddy System : Data Structures

 

커널 2.6에서의 버디 시스템은 각 zone에 따라 다르게 사용된다.

 

각 버디 시스템은 다음과 같은 핵심 자료구조를 사용 한다.

  •  zone_mem_map, spanned_pages(size)fields of zone descriptor, Pointer to first page dscriptor of the zone and zone's size in pages , zone_mem_map points somewhere in the mem_map shich is the aaray to store all the page dscriptors.
  • An array having 11elements (one for each group size) of type free_area(see zone dscriptor in Table 8-4)

 

 

 

The Per-CPU page Frame Cache

 

당연히 커널은 페이지 프레임을 request하고 releases하는 작업을 매우 빈번히 발생 시킬것이다.

이것에 대한 속도를 빠르게 처리하기 위해서 CPU당 페이지 프레임 캐쉬를 둔다.

 

이 Cache는 2가지로 나뉘어 진다.

 

hot cache

CPU 하드웨어 캐시에 포함되어 있을 가능성이 높은 페이지 프레임을 저장하는 Cache

 

커널 모드나 사용자 모드의 프로세스가 페이지 프레임을 할당한 후 바로 쓰기 작업을 한다면 핫 캐시에서 페이지 프레임을 얻는 것이 시스템 능률 면에서 이익이다. 보통 페이지 프레임의 하나의 메모리 셀에 접근하는 것은 다른 페이지 프레임이 사용하는 하드웨어 캐시 라인 하나를 훔치는 것이다. 하지만 하드웨어 캐시에 방금 해지시킨 핫 페이지 프레임의 셀과 매핑되었던 라인이 남아 있다면 훔치지 않아도 된다.

 

cold cache

페이지 프레임이 DMA 작업으로 채워진다면 콜드 캐시에서 페이지 프레임을 얻는 것이 편리하다. 이런 경우 CPU는 개입하지 않고 하드웨어 캐시의 라인도 전혀 수정되지 않는다. 콜드 캐시에서 페이지 프레임을 얻는 것은 나머지 다른 종류의 메모리 할당 요청을 위해 핫 페이지 프레임 하드웨어 캐시에 남아 있도록 한다.

 

 

hot cache:

page frame들을 저장 하고 있다.  이 page frame의 내용은 CPU가 가지는 하드웨어 캐쉬안에 포함되어지는 내용 이다.

좋은 성능 가진다. 커널이나 유저모드 프로세스에서 쓰기작업을 할것이라면 allocation 이후에 page 프레임에 대해서

 

 

cold cache:

이것도 역시 page frame을 저장하는 것인데, 이 페이지프레임의 내용은 디스크에서의 내용이다. 이것은 CPU 캐쉬의 내용이 아니다.

DMA 명령어를 가지고 페이지 프레임을 채울려고 할때 매우 편리하다.

 

 

The Zone Allocator

 

 

Zone Allocator는 커널 페이지 프레임 할당자의 시작 단계이다.

일단 여유 페이지 프레임 수가 많은 메모리 Zone을 찾아야 하는데 이게 참 어렵다.

그 이유는 아래와 같다.

 

  • Protect the pool of reserved page frames: 예약된 페이지 풀을 보호 해야한다. 왜냐하면 커널 같은대서 페이지가 부족하다고 회수알고리즘 가동시키고 이렇게할 블락킹의 여유 시간이 없기 때문에 이런 예약 페이지 풀들은 보호되어져야 한다.
  • Trigger the page frame reclaiming alogrithm when memory is scarce: 메모리가 모자랄때 회수 알고리즘을 발생 시켜야 한다.
  • Preserve the small, precious ZONE_DMA memory zone: 페이지 프레임을 ZONE_DMA에 할당하는것을 원치 않는다. 만약 ZONE_NOMAL과 ZONE_HIGHMEM에 할당 요청을 했다면

 

Memory Area Management

 

버디 시스템 알고리즘은 페이지 프레임을 기본 메모리 영역으로 채택한다.

단점 : 상대적으로 큰 메모리 요청을 다룰 때는 좋지만 몇 십 바이트나 몇 백 바이트 처럼 작은 메모리 영역은 처리하기 어렵다.

 

즉 내부 단편화 문제가 발생되는 것이다.

 

이를 해결하기위해 고전 리눅스에서는 기하학적인 방법을 사용하는데

그것은 2의 거듭제곱으로 미리 페이지를 만들어놓고 그것을 사용하는 것이다. 이럴경우 내부 단편화 비율이 최대 50%를 넘지 않는다고 한다.

 

How to allocate small memory area within a page frame.

Linux 2.0 - providing memory areas whoes sizes are geometrically distributed(power of 2) : at most 50% internal fragmentation

 

Linux 2.2 applied "slab allocator" scheme

 

 

The Slab Allocator

 

이것의 전제

  • 자료의 타입에 따라 메모리 영역의 할당 방법이 다를 수 있다.
  • 커널 함수는 같은 유형의 메모리 여역을 반복해서 요청하는 경햠이 있다. 이때 매우 효율 적이다.
  • 메모리 영역 요청을 크기별로 나우어서 빈도를 측정 할 수 있다. 자주 발생 할것 같은 특정 크기에 대한 요청은 크기가 동일한 특수 목적의 객체 집단을 만들어 가장 효율적으로 처리함과 동시에 내부 단편화 문제도 피할 수 있다. 반면 드물게 나오는 크기는 비록 내부 단편화를 일으킬 수 있지만 기하학적으로 분포된 크기인 일련의 객체에 기반한 할당 정책을 통해 처리할 수 있다.

결국 하는말은

빈번하게 발생되는 영역 즉, Process Descriptor와 open file object 같은것들은 생성과 소멸이 매우 빈번한대 이런거 처리할 때 slab allocator는 빠르게 처리한다.

 

객체를 만들어서 관리하는데, 이때 Slab allocator는 이러한 객체들은 절대로 discard 하지 않기 때문에 reinitialized 하는 overhead를 초래하지 않는다.

classified 한 요청은 결국 frequency를 가진다. 따라서 high grequency는 미리 만들어서 to avoid internal fragmentation하고, rarely used object는 power of 2 size 정책을 이용해서 할당한다.(2.0 방식 이용)

 

 

 

 

Slab Allocator는 Object를 모아서 Cache로 만든다.

이러한 Each cache들은 동일한 Type object의 Store이다.

 

e.g : 파일을 열면 해당 열린 파일 객체(Open Object)를 저장하는 데 필요한 메모리 영역을 filp(File Pointer)라는 슬랩 할당자 캐시에서 가져온다.

 

메인 메모리 공간은 결국 이 슬랩에 의해서 나뉘어 지는 것이다.

각각의 슬랩은 결국 하나 또는 그이상의 연속적인 페이지 프레임들로 구성된다. 그리고 이 프레임들은 alocated거나 free object들 이다.

 

커널은 주기적으로 캐쉬를 스캔한다. 그리고 해지된 페이지 프래미은 empty slab들과 일치한다.

kmem_freepage()를 딱 실행하면 모든 사용된 연속적인 페이지 프레임들이 리턴된다 슬랩에 의해서 그리고 이건 버디 시스템으로 간다.

 

 

Slab descriptor 저장할 수 있는 장소는 두가지이다.

Internal slab descriptor : storead inside the slab, at the beginning of the first page frame of the slab 슬랩 내부에 슬랩에 할당한 첫 번째 페이지 프레임의 시작 부분에 저장 한다.

슬랩 할당자는 객체의 크기가 512바이트 보다 작거나 내부 단편화에 의해 슬랩 내에 슬랩 디스크립터와 뒤에서 설명할 객체 디스크립터를 담을 충분한 공간이 있으면 후자의 방법을 선택한다.

 

External slab descriptor : stored outside the slab in one of the general caches

 

 

 

 

 

8.2.5 Interfacing the Slab Allocator with the Zoned Page Frame Allocator

 

Slab alocator는 zoned page frame allocator를 사용한다. 즉, Slab alocator가 new slab을 만들 때는 zoned page frame allocator를 사용하여 free contiguous page를 획득 한다.

 

새로 생성한 cache는 아무런 slab도 포함하지 않으므로 free object들을 포함하지 않는다.

 

Allocating a Slab to a cache only when

1) new object를 할당하라는 요청이 있을 때 그리고

2) cache에 free object가 더이상 없을 때 이다.

 

slab allocator는 new slab을 cache로 할당한다. cache_grow()를 써서

 

 

Cache에서 Slab 해지 하기

 

Slab cache에 너무 많은 free object들이 있을 경우

fully unused slabs의 경우 released 한다.

 

slab_destory() 함수를 이용 한다. 

 

 

Object Descriptor

 

 

Slab Object Descriptor도 위 그림 처럼 두가지 방법으로 저장 할 수 있다.

 

각 객체는 kmem_bufctl_t라는  type 정보에 대한 짧은 디스크립터를 포함한다.

Object Descriptor를 해당하는 Slab Descirptor 뒤에 있는 array에 저장한다.

 

1) External object descriptor

Slab 외부에 Cache Desciptor의 slabp_cache가 가리키는 일반 캐시에 저장한다. 따라서 메모리 영역의 크기는 Slab에 저장하는 객체의 수에 따라 달라진다.

 

2) Internal object descriptor

Slab 내부에 객체 디스크립터가 기술하는 객체 바로 앞에 저장 한다.

 

 

 

Aligning Objects in Memory

 

마이크로 컴퓨터에스는 메모리를 셀단위로 접근해서 좀더 빠르게 처리 한다.

이를 위해 align을 word size로 하게 된다. 4byte의 크기이다.

 

slab allocator에 의해서 boject들은 관리 된다. aligned된 메모리에서

물리주소는 다양한 constant이다. 즉 alignment factor에 따라 다르다.

이 alignment factor artificially하게 increasing한다면 object size가 커지고 따라서 better cache performance를 가지게 된다.

 

그러나 at the cost of some internal fragmentation.

 

Slab Coloring

 

Slab Coloring: Slab에 Color이라는 서로 다른 임의의 값을 할당하는 것을 말한다. 이것을 통해 비 효율적인 Cache 동작을 줄인다.

 

The same hardware chache line maps many different blocks of RAM.

 

같은 하드웨어 캐시 라인은 램의 서로 다른 여러 블록을 매핑 한다고 배웠으며, 크기가 동일한 객체를 캐시에서 동일한 오프셋에 저장하게 된다는 사실도 살펴 보았다. 다른 슬랩에서 동일한 오프셋에 있는 객체는 결국 같은 캐시라인으로 매핑될 가능성이 상대적으로 매우 높다.

따라서 캐시 하드웨어는 램의 서로 다른 위치에 존재하는 두 객체를 같은 캐시 라인으로 번갈아 가져오면서 메모리 사이클을 낭비하고, 다른 캐시 라인을 조금밖에 사용하지 않을 수도 있다.

슬랩 할당자는 이런 비효율적인 캐시 동작을 Slab Coloring이라는 정책으로 줄이려 한다.

 

 

 

Slab allocator는 사용하지 않는 free 바이트를 사용하여 Slab에 컬러를 부여한다. 컬러라는 용어는 단순히 슬랩을 세분화하고 메모리 할당자가 객체를 다른 선형 주소 사이에 퍼뜨릴 수 있도록 사용 한다.

이렇게 해서 커널은 마이크로프로세서의 하드웨어 캐시 성능을 가능한 최대화 한다.

 

 

 

General Purpose Objects 범용 객체

 

앞서 "버디 시스템 알고리즘:"에서 설명 했듯이 드물게 일어나는 메모리 영역 요청은 객체의 크기가 최소 32부터 최대 131,072 Byte까지 geometrically destributed 되어 있는 일반 Cache grop을 통해서 처리 한다.

 

위와 같은 종류의 Object는 kmalloc() 함수를 호출해서 얻으며, 함수는 다음 코드와 같다.

해지는 kfree()를 통해서 한다.

 

 

Memory Pools

 

메모리 풀(Memory Poll)은 리눅스 2.6의 새로운 특징이다.

기본적으로 메모리 풀은 메모리가 부족한 긴급 상황에서 커널의 구성 요소가(블록 디바이스 파일 시스템 같은) 동적 메모리를 어느 정도 할당할 수 있게 한다.

 

reserved page frame과는 다른 내용이다. 이전에 설명한 reserved page frame은 단지 인터럽트 핸들러나 임계 영역에서 발생한 atomic memory allocation 요청만을 satisfy하기 위한 것이다.

 

그러나 Memory Pool은 특정 커널 구성 요소, 즉 pool의 소유자만이 사용할 수 있는 동적 메모리의 예약분이다. 소유자는 정상적으로는 예약분을 사용하지 않는다. 하지만 동적 메모리가 너무 부족해서 모든 일반적인 메모리 할당 요청이 실패할 운명에 처해질 때 커널 구성 요소는 마지막으로 예약분을 가져와 필요한 메모리를 얻는다.

 

 

□ Noncontiguous Memory Area Management

 

Noncontiguous한 메모리 allocation도 생각해봐야한다. 그래야 External Fragmentation을 맊을 수 있다.

당연히 불연속적인 메모리 영역의 크기는 4,096의 배수 이다.

 

리눅스에서 이러한 Noncontiguous memory area를 사용하는 용도는

1) 스왑 영역용으로 자료구조를 할당할 때

2) 모듈용으로 공간을 할당할 때

3) 몇몇 입출력 드라이버용으로 버퍼를 할당할 때

 

3개의 ZONE = ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM

 

One of 3 mechanisms to map page frames in high-memory zone(ZONE_HIGHMEM)

 

연속적인 페이지 프레임이 할당을 선호 한다.

이렇게 cache를 만들경우, 평균 접근 time이 적을 수 있다.

 

noncontiguous page frame의 할당

external fragmentation을 회피 한다.

메모리 요청이 빈번하지 않는 여역에 대해서는 이것이 가능하다.

e.g : module, buffers, I/O driver

 

반드시 이 noncontiguous memory area는 4096byte 단위 이어야 한다.

 

단점(Disadvantage): Kernel page table작업시 연속된 주소가 아니므로 overhead가 발생 한다.

 

8.3.1 Linear Addresses of Noncontiguous Memory Areas

 

Linear address의 빈 범위를 찾기 위해 PAGE_OFFSET 부터 시작하는 영역을 들여다 볼 수 있다.

아래의 그림에서 PAGE_OFFSET0xc0000000이다. 즉 1GB라는 말이다.

 

 

 

영역의 시작 부분에는 램의 처음 896MB를 매핑하는 선형 주소가 들어간다.

high_memory 변수는 직접 매핑하는 물리 메모리의 끝에 해당하는 선형 주소를 저장한다.

 

vmalloc()함수는 커널에 불연속적인 메모리 영역을 할당한다.

 

8.3.2. Descriptors of Noncontiguous Memory Areas

 

vm_struct가 각 불연속적인 메모리 영역마다 연계된다.

 

 

Allocating / Releasing a Noncontiguous Memory Area

 

위 그림에서 VMALLOC_START 매크로는 불연속적인 메모리 영역용으로 예약된 선형 곤간의 시작 주소를 정의하고 VMALLOC_END는 마지막 주소를 정의한다.

 

get_vm_area() 함수는이 VMALLOC_START와 VMALLOC_END 사이에  linear address의 free range를 찾아서 반환해 주게 된다.

 

vmalloc 사용, vmalloc_32()이도 있는데 이것은 ZONE_NORMAL과 ZONE_DMA 메모리 지역 에서만 페이지 프레임을 할당한다.

 

vfree는 vmalloc 또는 vmalloc_32에 의해서 생성된 Noncontiguous 한 memory 영역을 해지 한다.

 

 

 

 

'Computer Science > Linux Kernel' 카테고리의 다른 글

9장 프로세스 주소 공간  (0) 2012.06.08
2장 메모리 주소 지정  (0) 2012.06.07

+ Recent posts