메모리 관리 커널

1. 메모리 주소 지정
   ․시스템에서는 메모리에 정보를 저장하기 위해서 메모리 주소 지정이라는 방법을 사용합니다. 
 
 1) 메모리 주소 변환
   ․프로그래머들은 메모리 주소(memory address)를 단순히 메모리 셀(cell) 내용에 접근하는 방법으로 생각합니다. 그러나 80x86 마이크로 프로세서를 다루려면 세 종류의 주소인 논리 주소, 선형 주소, 물리 주소를 구별할 수 있어야 합니다 .  
 

(1) 논리 주소(logical address)
   ․논리 주소(logical address)는 기계어 명령어에서 피연산자나 명령어의 주소를 지정할 때 사용한다.  
   ․논리 주소는 세그먼트와 세그먼트의 시작부터 실제 주소까지의 거리를 나타내는 오프셋(offset)으로 이루어진다. 즉, 세그먼트 식별자(segment identifier)와 세그먼트 내에서 상대적인 주소를 나타내는 오프셋으로 구성된다.  
   ․세그먼트 식별자는 세그먼트 셀렉터(segment selector)라는 16비트 필드이며, 오프셋은 32비트 필드다.  

 

(2) 선형 주소(linear address)  
   ․선형 주소(linear address)는 부호가 없는 32비트 크기의 정수 값으로 4GB, 즉 메모리 셀 4,294,967,296 개까지 주소를 지정할 수 있다.  
   ․가상 주소(virtual address)라고도 한다.  
   ․선형 주소는 보통 16진수로 표기하며, 값의 범위는 0x00000000˜0xffffffff까지이다.  

 

(3) 물리 주소(physical address) 
   ․물리 주소(physical address)는 메모리 칩에 들어있는 메모리 셀을 지정하는 데 사용하는 주소이다. 
   ․마이크로 프로세서에서 주소 핀(address pin)을 통해 메모리 버스(memory bus)에 보내는 전기 시그널에 해당한다. 
   ․물리 주소는 부호가 없는 32비트 크기의 정수로 나타낸다.  

 

(4) CPU의 제어 유닛  
   ․CPU의 제어 유닛은 세그먼테이션 유닛(segmentation unit)이라는 하드웨어 회로를 이용하여 논리 주소를 선형 주소로 변환하고, 계속해서 페이징 유닛(paging unit)이라는 하드웨어 회로를 이용하여 선형 주소를 물리 주소로 변환한다.  
   ․주소 변환 과정을 도식화하면 다음과 같다.

(5) 세그먼테이션 유닛의 역할 
   ․세그먼트 셀렉터의 TI(Table Indicator) 필드를 검사해서 세그먼트 디스크립터가 어떤 디스크립터 테이블에 들어 있는지 확인한다. 
   TI 필드는 디스크립터가 GDT(Global Descriptor Table : 전역 디스크립터 테이블)에 있는지 아니면 현재 활성화된 LDT(Local Descriptor Table : 지역 디스크립터 테이블)에 있는지를 나타낸다. 전자의 경우 세그먼테이션 유닛은 gdtr 레지스터에서 GDT의 시작 선형 주소를 가져오고, 후자의 경우 세그먼테이션 유닛은 ldtr 레지스터에서 LDT의 시작 선형 주소를 가져온다.  

   ․세그먼트 셀렉터의 index 필드로 세그먼트 디스크립터의 주소를 계산한다. index 필드에 8(세그먼트 디스크립터의 크기)을 곱한 값을 gdtr이나 ldtr 레지스터의 내용에 더한다.  
   ․세그먼트 디스크립터의 Base 필드에 논리 주소의 오프셋을 더해서 선형 주소를 얻는다.  

(6) 페이징 유닛  
   ․페이징 유닛은 요청한 접근 종류가 해당 선형 주소의 접근 권한에 맞는지 검사한다. 메모리에 잘못 접근한 경우에는 페이지 폴트 예외(page fault exception)가 발생한다.  
   ․효율적인 메모리 관리를 위해 선형 주소는 페이지(page)라는 고정된 크기로 나뉘어져 있다. 한 페이지에 있는 연속된 선형 주소는 연속된 물리 주소로 매핑된다.  
   ․페이징 유닛은 램의 모든 영역이 페이지 프레임(page frame)이라는 고정된 길이로 나뉘어 있다고 간주한다. 페이지 프레임의 크기와 페이지의 크기는 같다.  
   ․선형 주소를 물리 주소로 매핑하는 자료 구조를 페이지 테이블(page table)이라고 한다.  
   ․페이지 테이블은 주 메모리에 있으며, 커널은 페이징 유닛을 사용하기 전에 페이지 테이블을 초기화해야 한다. 

 

   ※ 리눅스에서의 페이징 유닛
      마이크로 프로세서가 32비트 경우는 2단계 페이징을 사용하고, 64비트 경우는 3단계 페이징을 사용하여 선형 주소를 물리 주소로 변환한다. 3단계 페이징은 뒤의 리눅스 페이징에서 설명하므로 여기서는 2단계 페이징만 언급한다. 
      80386부터 인텔 프로세서의 페이징 유닛은 4KB 크기인 페이지를 사용한다. 32비트 크기인 선형 주소는 디렉토리(상위 10비트), 테이블(중간 10비트), 오프셋(하위 12비트)의 세 필드로 나뉜다. 선형 주소 변환을 위해 각 단계마다 일종의 변환 테이블을 사용한다. 1단계 변환 테이블은 페이지 디렉토리(page directory)라 하고, 2단계 변환 테이블은 페이지 테이블(page table)이라 한다. 

 

      현재 사용 중인 페이지 디렉토리의 물리 주소는 제어 레지스터 cr3에 들어 있다. 선형 주소 내의 디렉토리 필드는 해당하는 페이지 테이블을 가리키는 페이지 디렉토리의 엔트리를 결정한다. 주소의 테이블 필드는 해당 페이지를 포함하는 페이지 프레임의 물리 주소를 담은 페이지 테이블의 엔트리를 결정한다. 오프셋 필드는 페이지 프레임에서 상대 위치를 나타낸다. 오프셋의 길이는 12비트이기 때문에 각 페이지는 4096바이트의 데이터를 가진다. 아래의 그림은 이러한 내용을 도식화한 것이다. 

 

(7) 페이지 엔트리 구조 
   ․디렉토리와 테이블 필드는 모두 10비트이므로 페이지 디렉토리와 페이지 테이블은 각각 1024개의 엔트리를 포함할 수 있다. 그리고 페이지 디렉토리와 페이지 테이블의 엔트리 구조는 똑같다.  
   ․각 엔트리가 가지고 있는 필드는 다음과 같다.  
 

   *Present 플래그
- 이 플래그가 1이면 이 엔트리가 참조하는 페이지(또는 페이지 테이블)는 주 메모 리에 있다. 
- 이 플래그가 0이면 페이지가 주 메모리에 없으며, 엔트리에 있는 다른 비트는 운영체제의 필요에 따라 다른 용도로 사용할 수 있다. 
- 주소 변환을 하는 데 필요한 페이지 테이블이나 페이지 디렉토리 엔트리의 present 플래그가 0인 경우 페이징 유닛은 선형 주소를 제어 레지스터 cr2에 저장한 후 예외 번호 14번인 페이지 폴트 예외를 발생시킨다.  
    *페이지 프레임 물리 주소의 상위 20비트를 포함한 필드
- 각 페이지 프레임의 용량은 4KB이기 때문에 페이지 프레임의 물리 주소는 4096의 배수여야 한다.  
- 따라서 물리 주소의 하위 12비트는 항상 0이다.  
- 이 필드가 페이지 디렉토리를 참조하는 경우 페이지 프레임에 페이지 테이블이 들어가며, 페이지 테이블을 참조하는 경우에는 데이터가 있는 페이지가 들어간다. 
  

  * Accessed 플래그
- 페이징 유닛은 해당 페이지 프레임에 접근할 때마다 이 플래그를 1로 설정한다.  
- 운영체제는 이 플래그를 스왑 아웃(swap out)할 페이지를 선택하는 데 사용할 수 있다.  

 

    * Dirty 플래그
      -  페이지 테이블 엔트리에만 적용된다.  
- 페이징 유닛은 페이지 프레임에 쓰기 작업을 수행할 때마다 이 플래그를 1로 설정한다.  
- 운영체제는 이 플래그를 스왑 아웃할 페이지를 선택하는 데 사용할 수 있다.  

 

    * Read/Write 플래그
- 페이지나 페이지 테이블의 접근 권한(읽기/쓰기 또는 읽기)이 있다. 

 

    * User/Supervisor 플래그
      - 페이지나 페이지 테이블에 접근하는 데 필요한 특권(privilege) 수준을 나타낸다.  
  

  * PCD와 PWT 플래그
      - 하드웨어 캐시가 페이지나 페이지 테이블을 다루는 방법을 제어한다. 

 

    * Page Size 플래그
      - 페이지 디렉토리 엔트리에만 해당한다. 이 플래그가 1이면 엔트리는 2MB 또는 4MB 크기의 페이지 프레임을 가리킨다. 
    * Global 플래그
- 페이지 디렉토리에만 해당한다. 이 플래그는 펜티엄 프로 CPU에서 등장했으며, 자주 사용하는 페이지가 TLB(Translation Look aside Buffer) 캐시에서 사라지는 것을 막기 위한 것이다. 
- 레지스터 cr4의 PGE(Page Global Enable) 플래그를 켠 경우에만 동작한다.  

 

2) 리눅스 세그먼테이션
   ․세그먼테이션과 페이징은 둘 다 프로세스의 물리 주소 공간을 쪼개는 데 사용하기 때문에 다소 중복되는 면이 있습니다. 하지만 세그먼테이션은 각 프로세스에 다른 선형 주소 공간을 할당하고, 페이징은 똑같은 선형 주소 공간을 다른 물리 주소 공간과 매핑 해주는 차이점이 있습니다. 

 

(1) 세그멘테이션과 페이징 
   ․세그먼테이션과 페이징은 둘 다 프로세스의 물리 주소 공간을 쪼개는 데 사용하지만 세그먼테이션은 각 프로세스에 다른 선형 주소 공간을 할당하고, 페이징은 똑같은 선형 주소 공간을 다른 물리 주소 공간과 매핑 해주는 차이점이 있다. 

   ․80x86 마이크로 프로세서는 프로그래머가 애플리케이션을 서브루틴이나 전역 데이터 영역, 지역 데이터 영역 같은 논리적인 부분으로 쪼갤 수 있도록 세그먼테이션이라는 기법을 지원한다.  
   ․그러나 리눅스는 세그먼테이션을 매우 제한적으로 사용한다. 리눅스는 다음과 같은 이유 때문에 세그먼테이션보다는 페이징을 선호한다. 
- 모든 프로세스가 똑같은 세그먼트 레지스터 값을 가지면, 즉 모든 프로세스가 똑같은 선형 주소 공간을 공유하면 메모리 관리가 더 간단해진다.  
- 리눅스 설계의 목적 중 하나는 대중적인 다른 아키텍처와 호환하게 하는 것인데, RISK 아키텍처에서는 세그먼테이션을 매우 제한적으로 지원한다.  

 

(2) 리눅스에서의 세그멘테이션 
   ․리눅스에서 사용하는 세그먼트로는 커널 코드 세그먼트, 커널 데이터 세그먼트, 사용자 코드 세그먼트, 사용자 데이터 세그먼트, 작업 상태 세그먼트(TSS), 기본 지역 디스크립터 테이블(default LDT), 고급 전원 관리(APM : Advanced Power Management) 지원과 관련한 4개의 세그먼트가 있다.

 

   ※ 리눅스에서의 세그먼테이션
      리눅스 2.4 버전에서는 80x86 아키텍처에서 필요로 하는 경우에만 세그먼테이션을 사용한다. 모든 프로세스가 똑같은 논리 주소를 사용하기 때문에 정의해야 하는 세그먼트의 개수는 매우 적다.
      또한 모든 세그먼트 디스크립터를 전역 디스크립터 테이블(GDT)에 저장할 수 있다. GDT는 gdt_table이라는 배열로 구현되어 있고, gdt라는 변수로 참조한다. 이러한 심볼(symbol)은 arch/i386/kernel/head.S 파일에서 정의하고 있다. 
      커널은 지역 디스크립터 테이블(LDT)을 사용하지는 않지만, 프로세스가 자신만의 LDT를 만들 수 있는 modify_ldt() 시스템 콜을 제공한다. 

 

   ․리눅스의 전역 디스크립터 테이블(GDT)는 다음과 같다.

   ․리눅스 GDT는 몇 가지 공용 디스크립터들과 시스템에 있는 각 CPU용 세그먼트 디스크립터 한 쌍(TSS 세그먼트용과 LDT 세그먼트용)을 포함한다. 효율적으로 동작하기 위해 GDT에 있는 몇몇 엔트리는 사용하지 않으며, 이는 보통 같이 접근하는 세그먼트 디스크립터들이 똑같은 32바이트 크기의 하드웨어 캐시 라인에 있게 한다.  
  

 ․cs 레지스터에 저장된 세그먼트 셀렉터의 RPL(Requested Privilege Level) 필드는 프로세서가 사용자 모드에 있는지 커널 모드에 있는지를 나타내는 CPU의 현재 특권 수준(CPL : Current Privilege Level)을 지정한다. CPL이 바뀔 때마다 몇몇 세그먼테이션 레지스터도 따라서 갱신되어야 한다. 예를 들어 CPL이 3(사용자 모드)일 때 ds 레지스터는 사용자 데이터 세그먼트의 세그먼트 셀렉터를 포함해야 하지만, 0일 때는 커널 데이터 세그먼트의 세그먼트 셀렉터를 포함해야 한다. ss 레지스터의 경우도 CPL이 3일 때 사용자 데이터 세그먼트 안에 존재하는 사용자 모드 스택을 참조해야 하지만, 0일 때는 커널 데이터 세그먼트 안에 존재하는 커널 모드 스택을 참조해야 한다.  

 

   ․리눅스는 사용자 모드에서 커널 모드로 전환할 때 항상 ss 레지스터가 커널 데이터 세그먼트의 세그먼트 셀렉터를 포함하는지 확인한다.  

 

3) 리눅스 페이징
   ․리눅스는 3단계 페이징 모델을 선택하여 64비트 아키텍처에도 적합합니다. 리눅스는 페이지 전역 디렉토리(Page Global Directory), 페이지 중간 디렉토리(Page Middle Directory), 페이지 테이블(Page Table)을 정의합니다.
   * STEP1 : 리눅스의 3단계 페이징 모델의 작동방법을 예상해보자. 
     페이지 전역 디렉토리는 여러 페이지 중간 디렉토리의 주소를 포함하고, 페이지 중간 디렉토리는 다시 여러 페이지 테이블의 주소를 포함한다. 

 

     각 페이지 테이블 엔트리는 페이지 프레임을 가리킨다. 따라서 선형 주소는 4부분으로 나뉜다. 아래의 그림은 이러한 리눅스 페이징을 도식화한 것이다. 
리눅스 페이징 모델

    이 그림에서 각 부분의 비트 수를 표시하지 않았는데, 이는 각 부분의 크기가 컴퓨터 아키텍처에 따라 다르기 때문이다. 
 

  *STEP2 : 리눅스는 프로세스를 다룰 때 페이징에 많이 의존한다. 리눅스는 선형 주소를 물리 주소로 자동 변환하는 것은 어떠한 효과를 낼 수 있는지 예상해보자. 
․리눅스는 프로세스를 다룰 때 페이징에 많이 의존한다. 리눅스는 선형 주소를 물리 주소로 자동 변환하여 다음과 같은 설계 목적을 달성한다. 
 - 각 프로세스에 서로 다른 물리 주소 공간을 할당해서 주소 지정 에러를 효과적으로 차단한다.  
 - 페이지(데이터 그룹)를 페이지 프레임(주 메모리에 있는 물리 주소)과 구별한다. 이는 똑같은 페이지를 페이지 프레임에 저장했다가 디스크에 저장하고, 나중에 다른 페이지 프레임으로 로드할 수 있게 하며, 가상 메모리 메커니즘의 기본적인 요소이다.  

 

․프로세스는 자신만의 페이지 전역 디렉토리와 일련의 페이지 테이블을 가진다. 프로세스 전환이 일어나면 리눅스는 cr3 제어 레지스터의 값을 앞서 실행 중이던 프로세스의 디스크립터에 저장하고, 다음에 실행할 프로세스의 디스크립터에 저장된 값을 가져와 cr3을 설정한다. 따라서 CPU가 새로운 프로세스의 실행을 재개할 때 페이징 유닛은 올바른 테이블 집합을 참조하게 된다. 

 

2. 메모리 관리
   ․효율적인 시스템운영을 위해서는 메모리 관리가 필요합니다. 이 단원에서는 메모리의 주소 지정에 대해서 개괄적으로 살펴보겠습니다.

1) 페이지 프레임 관리
   ․리눅스는 페이지 프레임 크기인 4KB를 표준 메모리 할당 단위로 채택합니다. 이는 페이징 회로가 발생시킨 페이지 폴트 예외를 쉽게 해석할 수 있고, 4KB가 대부분의 디스크 블록 크기의 배수인 까닭입니다.  

 

(1) 페이지 프레임 관리 
   ․커널은 각 페이지 프레임의 현재 상태를 계속해서 유지해야 한다. 즉 페이지 프레임이 사용 중인지 아닌지 알 수 있어야 한다.  
   ․페이지 프레임에 사용자 모드 프로세스의 자료나 소프트웨어 캐시 자료, 동적으로 할당한 커널 자료 구조, 장치 드라이버의 버퍼용 자료, 커널 모듈의 코드 등이 들어 있다면 이 페이지 프레임은 사용 중이다.  
   ․struct page 타입인 페이지 디스크립터에 페이지 프레임의 상태 정보를 저장한다. 모든 페이지 디스크립터는 mem_map 배열에 저장된다. 각 디스크립터의 크기는 64바이트보다 작기 때문에 mem_map을 위해 램 1MB 당 페이지 프레임 4개가 필요하다.  

 

(2) 리눅스에서의 페이지 프레임 관리 
   ․리눅스는 물리 메모리를 ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM의 세 지역(zone)으로 쪼개다. 
    * ZONE_DAM
      - ZONE_DMA 지역은 16MB 아래의 메모리 페이지로, 오래된 ISA 기반 장치에서 DMA를 이용할 때 사용할 수 있는 물리 메모리를 포함한다. 
      - 커널이 선형 주소 공간의 마지막 1GB로 선형 매핑하여 직접 접근할 수 있는 일반 메모리 페이지를 포함한다.  
    * ZONE_MORMAL
      - ZONE_NORMAL 지역은 16MB˜896MB 사이의 메모리 페이지이다.  
      - ZONE_DMA 지역과 마찬가지로 커널이 선형 주소 공간의 마지막 1GB로 선형 매핑하여 직접 접근할 수 있는 일반 메모리 페이지를 포함한다. 
    * ZONE_HIGHMEM
      - ZONE_HIGHMEM 지역은 896MB 이상의 메모리 페이지로, 커널이 선형 주소 공간의 마지막 1GB로 선형 매핑하여 직접 접근할 수 없는 메모리 페이지를 포함한다.  
      - 64비트 구조에서는 이 지역을 사용하지 않는다.  
      - 각 메모리 지역은 struct zone_struct(zone_t라는 이름도 있다) 타입인 자신만의 디스크립터를 가진다.  

 

(3) 불균등 메모리 접근(NUMA : Non-Uniform Memory Access) 방식  
   ․리눅스 2.4에서는 불균등 메모리 접근(NUMA : Non-Uniform Memory Access) 방식을 지원한다.  
   ․여기서는 한 CPU에서 다른 메모리 위치를 접근하는 데 걸리는 시간이 다를 수 있다.  
   ․시스템에 있는 물리 메모리는 여러 노드(node)로 쪼개져 들어간다. 어떤 CPU가 한 노드 안에 있는 페이지를 접근하는 데 걸리는 시간은 똑같지만, 이 시간은 서로 다른 두 CPU 사이에서는 다를 수 있다.  
   ․커널은 어떤 CPU가 가장 자주 접근하는 커널 자료 구조를 저장하는 위치를 조심스럽게 선택하여 모든 CPU가 시간이 오래 걸리는 노드에 접근하는 횟수를 최소화하려고 노력한다.  
   ․다음 그림은 동적 메모리와 이를 참조하는 데 사용하는 값을 보여주는 것으로, 메모리의 여러 지역을 일정한 비례로 그려져 있다. 

 

(4) paging_init() 함수  
   ․paging_init() 함수는 페이지 테이블 외에 메모리를 다루는 다른 자료 구조도 초기화한다.  
   ․이 함수는 kmap_init() 함수를 호출하여 커널이 ZONE_HIGHMEM 지역에 접근할 수 있도록 선형 주소의 윈도우(window)를 만드는 kmap_pte 변수를 설정한다.  
   ․그런 후에 세 가지 메모리 지역의 크기를 나타내는 zones_size 배열을 매개 변수로 해서 free_area_init() 함수를 호출하는데, 이 함수는 지역 디스크립터와 페이지 프레임 디스크립터를 모두 초기화한다.  

 

(5) mem_init() 함수 
   ․paging_init() 함수를 실행한 후에 동적 메모리를 사용하기 위해 mem_init() 함수를 호출한다.  
   ․이 함수는 시스템에 존재하는 전체 페이지 프레임 수인 num_physpages의 값을 초기화한다.  
   ․다음으로 동적 메모리에 속하는 모든 페이지 프레임을 훑어본다. 각 페이지 프레임마다 해당 디스크립터의 count 필드를 1로 설정하고, PG_reserved 플래그를 지운다.  
   ․만약 페이지 프레임이 ZONE_HIGHMEM 지역에 속한다면 PG_highmem 플래그를 설정한 후 이 페이지 프레임에 대해 free_page() 함수를 호출한다.  

 

  ․free_page() 함수는 페이지 프레임을 해제하고 해당 페이지 프레임을 소유한 메모리 지역 디스크립터의 free_pages 필드의 값을 증가시킨다.  
   ․모든 지역 디스크립터에 있는 free_pages 필드는 nr_free_pages() 함수에서 동적 메모리에 있는 사용하지 않는 전체 페이지 프레임 수를 계산하는 데 사용한다.  

 

   ․mem_init() 함수는 동적 메모리에 속하지 않는 페이지 프레임의 수도 센다. 커널을 컴파일할 때 만들어지는 여러 심볼 때문에 하드웨어와 커널 코드, 커널 데이터용으로 예약된 페이지 프레임의 수, 커널 초기화 과정에서 사용하고 초기화를 마친 후 해제할 수 있는 페이지 프레임의 수 등을 계산할 수 있다. 
 
    *STEP1 : 리눅스는 이러한 문제를 해결하기 위해 버디 시스템(buddy system) 알고리즘에 기반을 둔 기법을 채택했다. 이 기법이 무엇인지 예상해보자.
              ․리눅스는 이러한 문제를 해결하기 위해 버디 시스템(buddy system) 알고리즘에 기반을 둔 기법을 채택했다. 
              ․사용하지 않는 모든 페이지 프레임을 그룹별로 묶어서 블록 리스트 10개에 넣는다. 각 리스트는 연속된 페이지 프레임 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 개로 구성된 그룹을 담는다. 블록의 첫 번째 페이지 프레임의 물리적인 주소는 그룹 크기의 배수다. 
              ․예를 들어 16-페이지 프레임의 시작 주소는 의 배수다. 
              ․반대 작업인 페이지 프레임 블록을 해제하는 데서 이 알고리즘의 이름이 유래했다. 커널은 크기가 b인 이웃하는 여유 블록 쌍을 크기가 2b인 더 큰 블록 하나로 만들려고 한다. 다음 조건을 만족하면 두 블록은 버디 블록이다. 
 - 두 블록의 크기가 똑같이 b다. 
 - 두 블록이 연속된 물리적인 주소에 위치한다.  
 - 첫 번째 블록의 첫 번째 페이지 프레임의 물리 주소는 의 배수다. 
              ․이 알고리즘은 순환적이다. 커널은 해제된 블록을 합친 후에 b의 값을 두 배로 늘려 더 큰 블록을 만들려고 한다. 

 

   *STEP2 : 버디 시스템(buddy system) 알고리즘의 작동 방법을 적용하여 연속된 페이지 프레임 128개로 구성된 그룹(즉 512KB)을 요청한 경우, 알고리즘의 동작을 설명하시오.
             ․누군가 연속된 페이지 프레임 128개로 구성된 그룹(즉 512KB)을 요청했다고 하자. 
             ․이 알고리즘은 먼저 128-페이지 프레임 리스트에 여유 블록이 있는지 검사한다. 여유 블록이 없으면 다음으로 큰 블록인 256-페이지 프레임 리스트에서 여유 블록을 찾는다. 
             ․여기서 여유 블록을 발견하면 페이지 프레임 256개 중에서 128개를 요청한 쪽으로 할당하고, 나머지 페이지 프레임 128개를 여유 128-페이지 프레임 블록 리스트에 추가한다. 
             ․여유 256-페이지 블록이 없다면 다음으로 큰 블록인 512-페이지 프레임에서 블록을 찾는다. 여기서 블록을 찾으면 페이지 프레임 512개 중 128개를 요청한 쪽으로 할당한다. 
             ․그리고 나머지 384개 중 처음 256개를 여유 256-페이지 프레임 블록 리스트에 넣고, 이를 제외한 페이지 프레임 128개를 여유 128-페이지 프레임 블록의 리스트에 넣는다. 512-페이지 프레임 블록 리스트가 텅 비어 있다면 할당을 포기하고 에러 상황을 알려준다. 

 

2) 메모리 영역 관리

 

(1) 메모리 영역  
   ․메모리 영역이란 연속하는 물리 주소를 가진 임의 길이의 메모리 셀을 말한다.  
   ․버디 시스템 알고리즘은 페이지 프레임을 기본 메모리 영역으로 채택한다. 이는 상대적으로 큰 메모리 요청을 다룰 때는 좋지만, 수 바이트나 수 백 바이트와 같이 작은 메모리 영역(memory area)을 저장하기 위해 한 페이지 프레임 전체를 할당하는 것은 매우 비경제적이다.  
   ․최근의 접근법은 버디시스템의 개념보다 발전해서 한 페이지 프레임 내에서 작은 메모리 영역을 어떻게 할당하고 있는지를 나타내는 새로운 자료 구조를 도입하였다.  
   ․그러나 최근의 접근법은 내부 단편화(internal fragmentation)라는 새로운 문제가 제기되었다. 이 문제는 요청한 메모리의 크기와 해당 요청을 처리하기 위해 할당하는 메모리 영역의 크기가 일치하지 않아서 일어난다.  

 

(2) 슬랩 할당자의 도입 
   ․리눅스는 이를 위해 슬랩 할당자(slab allocator)를 도입했다.  
   ․슬랩 할당자의 개념은 메모리 영역을 일련의 자료 구조와 생성자(constructor)와 소멸자(destructor)라는 메소드, 즉 두 함수를 포함한 객체로 간주한다.  
   ․슬랩 할당자는 객체를 반복해서 초기화하지 않도록 할당했다가, 해제한 객체를 폐기하지 않고 메모리에 그대로 저장한다. 새로운 객체를 요청하면 초기화를 다시 하지 않고 메모리에서 이 객체를 가져올 수 있다.  
   ․리눅스는 효율성 때문에 생성자나 소멸자 메소드가 필요한 객체를 사용하지 않는다. 슬랩 할당자를 도입한 중요한 동기는 버디 시스템 할당자를 호출하는 횟수를 줄이는 것이다. 따라서 커널이 생성자와 소멸자 메소드를 완벽하게 지원하지만, 두 메소드를 가리키는 포인터는 NULL이다.  

 

(3) 슬랩 할당자의 작동  
   ․슬랩 할당자는 객체를 모아서 캐시로 만든다. 각 캐시는 타입이 같은 객체의 저장소(store)이다. 예를 들어 파일을 열면 해당 열린 파일(open file) 객체를 저장하는 데 필요한 메모리 영역을 filp(file pointer)라는 슬랩 할당자 캐시에서 가져온다. 리눅스가 사용하는 슬랩 할당자 캐시는 실행 주에 /proc/slabinfo 파일에서 볼 수 있다.  
   ․슬랩 할당자의 구성 요소들을 도식화하면 다음과 같다.  

 

  ․캐시가 들어 있는 주 메모리 영역을 슬랩으로 나눈다. 각 슬랩은 연속된 페이지 프레임 하나 이상으로 구성되며, 할당한 객체와 여유 객체를 모두 포함한다.  
   ․슬랩 할당자는 빈 슬랩의 페이지 프레임을 절대 스스로 해제하지 않는다. 언제 여유 메모리가 필요할지 모르고, 새로운 객체를 만들 수 있는 여유 메모리가 충분히 있을 때 객체를 해제하는 것은 아무런 이득이 없다. 따라서 커널에 추가로 여유 페이지 프레임이 필요할 때만 슬랩을 해제한다.  

 

(4) 캐시의 구성  
   ․각 캐시는 타입이 struct kmem_cache_s(=kmem_cache_t)인 테이블로 나타낸다.  
   ․이 테이블에서 가장 중요한 필드는 다음과 같다. 

필드

설명

name slabs_full slabs_partial slabs_free spinlock num objsize gfporder ctor dtor next flags dflags Gfpflags

캐시 이름을 저장하는 문자의 배열. 여유 객체가 없는 슬랩 디스크립터의 원형 이중 연결 리스트. 여유 객체와 사용 중인 객체를 모두 포함하는 슬랩 디스크립터의 원형 이중 연결 리스트. 여유 객체만 포함하는 슬랩 디스크립터의 원형 이중 연결 리스트. 멀티프로세서 시스템에서 캐시를 동시에 접근하지 않도록 보호하는 스핀 락. 슬랩 하나에 들어 있는 객체의 수.(캐시의 모든 슬랩은 크기가 같다.) 캐시에 들어 있는 객체의 크기. 슬랩 하나에 들어가는 연속된 페이지 프레임 수에 로그를 취한 값. 캐시 객체와 연계된 생성자 메소드를 가리킨다. 캐시 객체와 연계된 소멸자 메소드를 가리킨다. 캐시 디스크립터의 이중 연결 리스트를 가리킨다. 캐시의 영구적인 속성을 나타내는 플래그 집합. 캐시의 동적인 속성을 나타내는 플래그 집합. 페이지 프레임을 할당할 때 버디 시스템에 전달하는 플래그 집합.

(5) 캐시의 슬랙타입  
   ․캐시의 각 슬랩은 타입이 struct slab_s(=slab_t)인 자신만의 디스크립터가 있다.  
   ․슬랩 디스크립터를 저장할 수 있는 장소는 두 가지이다. 

외부 슬랩 디스크립터	내부 슬랩 디스크립터
- cache_sizes가 가리키는 ISA DMA 용이 아닌 일반 캐시 중 하나에 저장한다	- 슬랩에 할당한 첫 번째 페이지 프레임의 시작 부분에 저장한다.

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

   ․슬랩 디스크립터에서 가장 중요한 필드는 다음의 표와 같다.

필드	설명
inuse s_mem free list	슬랩에서 현재 할당한 객체의 수. 할당 여부에 상관없이 슬랩에 있는 첫 번째 객체를 가리킨다. 여유 객체가 있다면, 슬랩에 있는 첫 번째 여유 객체를 가리킨다. 세 가지 슬랩 디스크립터의 이중 연결 리스트 중에서 하나를 가리키는 포인터.

(6) 캐시 디스크립터와 슬랩 디스크립터 사이의 관계  
   ․캐시 디스크립터와 슬랩 디스크립터 사이의 주요 관계는 다음과 같다. 
    꽉 찬 슬랩과 일부만 찬 슬랩, 텅 빈 슬랩을 서로 다른 리스트로 연결한다. 

   ․새로 만든 캐시는 아무런 슬랩도 포함하지 않으므로 여유 객체 또한 포함하지 않는다.
    새 객체를 할당해달라는 요청을 받을 때와 캐시에 여유 객체가 없을 때에만 캐시에 새로운 슬랩을 할당한다. 버디 시스템이 새로 페이지 프레임 그룹을 할당해달라는 요청을 처리할 수 없을 때(지역에 메모리가 조금만 남은 때)와 슬랩이 비어 있을 때(슬랩에 들어 있는 모든 객체가 사용 가능할 때)에는 슬랩을 해제한다.  

 

(6) 캐시 디스크립터와 슬랩 디스크립터 사이의 관계  
   ․각 객체는 kmem_bufctl_t 타입인 디스크립터를 포함한다. 
    객체 디스크립터를 해당 슬랩 디스크립터 뒤에 있는 배열에 저장한다.  
   ․따라서 슬랩의 객체 디스크립터도 외부 객체 디스크립터와 내부 객체 디스크립터의 두 가지 방법으로 저장할 수 있다. 

외부 슬랩 디스크립터	내부 슬랩 디스크립터
- 슬랩 외부에 cache_sizes가 가리키는 일반 캐시 중 하나에 저장한다. - 따라서 메모리 영역의 크기는 슬랩에 저장하는 객체의 수에 따라 달라진다.	- 슬랩 내부에 객체 디스크립터가 기술하는 객체 바로 앞에 저장한다.

   ․아래의 그림은 슬랩 디스크립터와 객체 디스크립터 사이의 관계를 보여준다. 

   ․배열에 있는 첫 번째 객체 디스크립터는 슬랩에 있는 첫 번째 객체를 기술하며, 나머지도 마찬가지이다.  
   ․객체 디스크립터는 단순히 부호 없는 정수이며, 객체를 사용하지 않을 때만 의미가 있다. 이는 슬랩 내에서 사용할 수 있는 다음 객체의 인덱스를 지정한다. 따라서 이를 통해 슬랩 내에 있는 여유 객체의 단순 리스트를 구현한다.  
   ․여유 객체 리스트에 있는 마지막 요소의 객체 디스크립터는 미리 약속한 값인 BUFCTL_END(0xffffffff)로 표시한다.  
   ․kmem_cache-alloc() 함수를 호출하여 새 객체를 얻을 수 있다. 
   - cachep 매개 변수는 새로운 여유 객체를 가져올 캐시 디스크립터를 가리키고, flag 매개 변수는 버디 시스템 할당자 함수에게 전달한 플래그를 나타낸다.  
   - kmem_cache_free() 함수는 할당된 객체를 해제한다.  
   - 이 함수는 캐시 디스크립터 주소인 cachep와 해제할 객체 주소인 objp를 매개 변수로 받는다.  

 

3) 불연속적 메모리 영역 관리

 

(1) 불연속적 페이지 기반 할당 정책 
   ․불연속적인 페이지 프레임을 기반으로 하는 할당 정책의 가장 큰 장점은 외부 단편화를 피할 수 있다는 것이다.  
   ․반면 커널 페이지 테이블을 다뤄야 하는 단점도 있다. 
    - 불연속적인 메모리 영역의 크기는 4096의 배수여야 한다.  
    - 리눅스는 활성화된 스왑 영역용으로 자료 구조를 할당하거나, 모듈용으로 공간을 할당하거나, 몇몇 입출력 드라이버용으로 버퍼를 할당하는 것 등의 몇 가지 용도 로 불연속적인 메모리 영역을 사용한다.  

 

(2) 선형 주소의 주소 공간 
   ․선형 주소의 빈 범위를 찾기 위해 PAGE_OFFSET(보통은 마지막 1GB의 시작 주소인 0xc0000000)부터 시작하는 영역을 들여다 볼 수 있다.  
 

  ․아래의 그림은 PAGE_OFFSET부터 시작하는 선형 주소 공간을 보여준다. 

   
   ․STEP : 앞페이지 마지막에서 살펴본 PAGE_OFFSET부터 시작하는 선형공간의 각 영역을 설명하시오, 
      ▶선형 주소 공간을 불연속적 메모리 영역 관리 측면에서 접근해 보세요.

 

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

 

․high_memory 변수는 직접 매핑하는 물리 메모리의 끝에 해당하는 선형 주소를 저장한다. 영역의 끝에는 고정 매핑하는 선형 주소가 들어간다. PKMAP_BASE(0xfe000000)부터 커널에서 상위 메모리 페이지 프레임을 매핑하는 데 사용하는 선형 주소가 있다. 

 

․선형 주소의 나머지 구간은 불연속적인 메모리 영역을 위해 사용할 수 있다. 물리적인 메모리의 끝과 첫 번째 불연속적인 메모리 영역 사이에는 안전을 위해8MB(VMALLOC_OFFSET 매크로)의 간격이 있다. 이 간격의 목적은 범위를 벗어난 메모리 접근을 잡아내는 것이다. 같은 목적으로 각 불연속적인 메모리 영역 사이에는 4KB 크기의 안전 간격이 추가로 들어간다. VMALLOC_START 매크로는 불연속적인 메모리 영역용으로 예약된 선형 공간의 시작 주소를 정의하고, VMALLOC_END 매크로는 그 마지막 주소를 정의한다. 

 

․각 불연속적인 메모리 영역마다 struct vm_struct 타입 디스크립터가 연계된다. 이 디스크립터는next 필드를 이용한 간단한 리스트로 들어간다. vmlist 변수는 이 리스트의 첫 번째 요소의 주소를 저장한다. vmlist_lock 읽기/쓰기 스핀 락을 사용하여 이 리스트에 접근하는 것을 보호한다. addr 필드에는 메모리 영역의 첫 번째 메모리 셀의 선형 주소가, size 필드에는 영역의 크기에 4096(영역 사이의 안전 간격 크기)을 더한 값이 들어간다. 

 

․get_vm_area() 함수는 struct vm_struct 타입의 새로운 디스크립터를 만든다. 여기서 매개 변수 size는 새로운 메모리 영역의 크기를 지정한다. 이 함수는 먼저 kmalloc()을 호출하여 새 디스크립터를 위한 메모리 영역을 할당한다. 다음으로 struct vm_struct 타입 디스크립터의 리스트를 검색하여 최소 size+4096 주소를 포함할 수 있는 선형 주소 구간이 있는지 찾는다. 이런 구간이 존재하면 디스크립터에 있는 필드를 초기화하고, 불연속적인 메모리 영역의 시작 주소를 반환하면서 함수를 끝마친다. 만약 addr+size가 VMALLOC_END를 넘어서면, get_vm_area() 함수는 디스크립터에 할당했던 메모리를 해제하고 NULL을 반환한다. 

 

․vmalloc() 함수는 커널에 불연속적인 메모리 영역을 할당한다. size 매개 변수는 요청한 영역의 크기를 나타낸다. 이 함수는 요청한 메모리를 할당할 수 있으면 새 영역의 시작 선형 주소를 반환하고, 그렇지 않으면 NULL 포인터를 반환한다. 반대로 해제할 때에는 vfree() 함수를 사용한다. 여기에 전달하는 매개 변수 addr로 해제할 영역과 시작 선형 주소를 지정한다. 불연속적인 메모리 영역에 할당한 각 페이지 프레임을 해제할 때에는 버디 시스템의 __free_page() 함수를 이용한다. pte_clear 매크로를 사용하여 페이지 테이블의 해당 엔트리를 0으로 설정한다. 

 

3. 프로세스 주소 공간
   ․프로세스에서도 마찬가지로 주소를 할당에서 사용하는 것이 편리합니다. 이 단원에서는 프로세스 주소 공간 대해서 개괄적으로 살펴보겠습니다. 

1) 프로세스 주소 공간
   ․프로세스의 주소 공간(address space)은 프로세스가 사용할 수 있는 모든 선형 주소로 구성됩니다.

 

(1) 프로세스 주소 공간 
   ․프로세스의 주소 공간(address space)은 프로세스가 사용할 수 있는 모든 선형 주소로 구성된다.  
   ․커널은 선형 주소 구간의 시작 선형 주소와 길이, 몇 가지 접근 권한을 기술하는 메모리 구역(memory region)이라는 자원으로 선형 주소 구간을 표현한다.  
   ․효율성을 위해 메모리 구역의 시작 주소와 길이는 모두 4096의 배수여야 한다. 따라서 각 메모리 구역으로 구별하는 데이터로 할당받은 페이지 프레임을 모두 채울 수 있다.  

 

(2) 메모리 디스크립터  
   ․프로세스 주소 공간과 관련한 모든 정보는 메모리 디스크립터라는 자료 구조에 들어 있다.  
   ․이 구조체의 타입은 mm_struct이고, 프로세스 디스크립터의 mm 필드가 이를 가리킨다. 모든 메모리 디스크립터는 이중 연결 리스트로 연결된다.  
   ․메모리 디스크립터에 있는 필드의 목록은 다음과 같다. 

 

   ※ 메모리 디스크립터 내 필드 목록

타입	필드	설명
struct vm_area_struct* rb_root_t struct vm_area_struct* pgd_t* atomic_t atomic_t int struct rw_semaphore spinlock_t struct list_head unsigned long unsigned long unsigned long unsigned long unsigned long unsigned long unsigned long unsigned long unsigned long unsigned long unsigned long unsigned long unsigned long unsigned long unsigned long unsigned long unsigned long unsigned int mm_context_t	mmap mm_rb mmap_cache pgd mm_users mm_count map_count mmap_sem page_table_lock mmlist start_code end_code start_data end_data start_brk brk start_stack arg_start arg_end env_start env_end rss total_vm locked_vm def_flags cpu_vm_mask swap_address dumpable context	메모리 구역 객체 리스트의 헤드를 가리키는 포인터 메모리 구역 객체의 빨강-검정 트리(red-black tree)의 뿌리 노드에 대한 포인터 마지막으로 참조한 메모리 구역 객체를 가리키는 포인터 페이지 전역 디렉토리를 가리키는 포인터 mm_struct 자료 구조를 공유하는 경량 프로세스의 개수 메모리 디스크립터의 1차 사용 횟수 메모리 구역의 수 메모리 구역의 읽기/쓰기 세마포어 메모리 구역과 페이지 테이블의 스핀 락 메모리 디스크립터 리스트에서 인접하는 항목을 가리키는 포인터 실행 코드의 시작 주소 실행 코드의 끝 주소 초기화된 데이터의 시작 주소 초기화된 데이터의 끝 주소 힙의 시작 주소 힙의 현재 끝 주소 사용자 모드 스택의 시작 주소 명령행 인자(command-line argument)의 시작 주소 명령행 인자의 끝 주소 환경 변수의 시작 주소 환경 변수의 끝 주소 프로세스에 할당한 페이지 프레임의 수 프로세스 주소 공간의 크기(페이지의 수) 스왑 아웃(swap out)하지 못하도록 락을 건 페이지의 수 메모리 구역의 기본 접근 플래그 지연 TLB 전환을 위한 비트 마스크 스왑을 하려고 마지막으로 검사한 선형 주소 프로세스가 메모리의 코어 덤프(core dump) 파일을 만들 수 있는지 여부를 나타내는 플래그 아키텍처에 고유한 정보를 저장하는 테이블을 가리키는 포인터

(3) 메모리 디스크립터의 주요 함수  
   ․새 메모리 디스크립터를 얻을 때는 mm_alloc() 함수를 호출한다.  
   ․이 디스크립터를 슬랩 할당자 캐시에 저장하기 때문에, mm_alloc()은 kmem_cache_alloc()을 호출한 후 새로운 메모리 디스크립터를 초기화하고 mm_count와 mm_users 필드를 1로 설정한다.  
   ․반대로 mmput() 함수는 메모리 디스크립터의 mm_users 필드를 감소시킨다. 이 필드가 0이 되면, 이 함수는 지역 디스크립터 테이블, 메모리 구역 디스크립터, 메모리 디스크립터가 참조하는 페이지 테이블을 해제한 후에 mmdrop()을 호출한다. mmdrop() 함수는 mm_count를 감소시키고, 이 값이 1이 되면 mm_struct 자료 구조를 해제한다. 

 

(4) 커널 스레드의 메모리 디스크립터  
   ․커널 스레드는 커널 모드에서만 동작하기 때문에 TASK_SIZE(PAGE_OFFSET과 같은 0xc0000000) 아래에 있는 선형 주소를 접근하지 않는다.  
   ․정규 프로세스와는 반대로 커널 스레드는 메모리 구역을 사용하지 않으므로 메모리 디스크립터에 있는 대부분의 필드는 커널 스레드에 의미가 없다.  
   ․TASK_SIZE 위의 선형 주소를 참조하는 페이지 테이블 엔트리는 항상 똑같아야 하므로 커널 스레드가 어떤 페이지 테이블 집합을 사용하는지는 문제가 되지 않는다.  
   ․리눅스 2.4에서 커널 스레드는 쓸데없이 TLB와 캐시를 비우지 않기 위해 정규 프로세스의 페이지 테이블을 그대로 사용한다.  
   ․이를 위해 모든 프로세스 디스크립터에는 mm과 active_mm이라는 두 종류의 메모리 디스크립터 포인터가 있다.  

 

2) 메모리 구역

 

(1) vm_area_struct 를 이용한 메모리 구역 구현  
   ․리눅스는 vm_area_struct 타입의 객체를 이용하여 메모리 구역을 구현한다.  
   ․각 메모리 구역 디스크립터는 선형 주소 구간을 구별한다. 

vm_start 필드	구간의 첫 번째 선형 주소
vm_end 필드	구간이 끝난 직후의 첫 번째 선형 주소를 저장
vm_mm필드	구역을 소유하는 프로세스의 mm_struct 메모리 디스크립터

   ․그러므로 vm_end - vm_start는 메모리 구역의 길이가 된다. 

 

(2) 선형 주소 구간의 추가와 제거  
   ․아래의 그림은 선형 주소 구간의 추가와 제거에 대해 도식화한 것이다. 

- 새로운 선형 주소 범위를 프로세스의 주소 공간에 추가할 때 커널은 기존의 메모리 구역을 확장할 수 있는지 검사한다(a의 경우).  
- 그렇지 않으면 새로운 메모리 구역을 생성한다(b의 경우).  
- 마찬가지로 프로세스의 주소 공간에서 선형 주소 범위를 제거할 때 커널은 이에 영향을 받는 메모리 구역의 크기를 조정한다(c의 경우).  
- 어떤 경우에는 크기를 조정할 때 한 메모리 구역이 작은 구역 두 개로 나뉘기도 한다(d의 경우).  
- 선형 주소 구간을 제거할 때 새로운 메모리 디스크립터를 할당할 수 있는 여유 메모리가 없으면 이론상 메모리 해제가 실패할 수도 있다.  

 

(3) do_mmap() 함수의 이용  
   ․선형 주소 구간의 할당은 do_mmap() 함수를 이용한다.  
   ․do_mmap() 함수는 current 프로세스용으로 새 메모리 구역을 생성하고 초기화한다. 
    성공적으로 할당한 후 이 메모리 구역을 프로세스의 다른 메모리 구역과 합칠 수 있다.  
   ․반대로 do_munmap() 함수는 현재 프로세스의 주소 공간에서 선형 주소 구간을 제거한다. 이 함수는 구간의 시작 주소인 addr과 구간의 길이인 len을 매개 변수로 사용한다.  
   ․do_mmap() 함수는 크게 두 단계를 거친다. 

1단계
프로세스 소유의 메모리 구역 리스트를 검색하여 선형 주소 구간과 겹치는 모든 구역을 지운다. 

 

2단계
프로세스 페이지 테이블을 갱신하고, 1단계에서 제거한 메모리 구역의 크기를 줄인 지역을 다시 삽입한다. 

(4) 빨강-검정 트리(red-black tree)  
   ․리눅스는 2.4.9 버전까지 AVL 트리라는 종류가 다른 균형 검색 트리를 사용했지만, 그 이후 버전부터는 빨강-검정 트리(red-black tree)를 사용하여 메모리 디스크립터를 저장한다.  
   ․아래의 그림은 빨강-검정 트리의 예를 보여준다. 

  

 ※ 빨강-검정 트리의 예
     *빨강-검정 트리에서 각 요소는 보통 왼쪽 자식 노드와 오른쪽 자식 노드라는 두 개의 노드를 가진다. 트리에 있는 요소는 정렬되어 있다. 각 노드 N에 대해 N의 왼쪽 자식 노드를 루트(root)로 하는 서브트리(subtree)의 모든 요소는 N 이전 값을 포함하고, N의 오른쪽 자식 노드를 루트로 하는 서브트리의 모든 요소는 N 이후 값을 포함한다. 노드 자체에 적은 숫자가 노드의 키 값이다. 

*빨강-검정 트리는 다음과 같은 네 가지 규칙을 지켜야 한다. 
1. 모든 노드는 빨강이나 검정이다.
2. 트리의 루트는 검정이다. 
3. 빨간 노드의 자식은 검정이다. 
4. 어떤 노드에서 후손 잎(leaf)에 이르는 모든 길에는 같은 수의 검은 노드가 있어야 한다 . 
   검은 노드의 수를 셀 때 널(null) 포인터도 검은 노드로 계산한다.  

 

*이 네 가지 규칙에 따라 n 개의 노드를 포함하는 모든 빨강-검정 트리는 높이가 최대 2log(n+1)이다. 따라서 빨강-검정 트리에서 요소를 찾는 작업에 필요한 수행 시간은 트리 크기에 로그를 취한 값에 정비례하기 때문에 매우 효율적이다. 즉 메모리 구역의 수가 2배 되더라도 찾는 작업을 한 번만 더 반복하면 된다. 

 

*리눅스는 프로세스의 메모리 구역을 저장하기 위해 연결 리스트와 빨강-검정 트리를 같이 사용한다. 두 자료 구조 모두 같은 메모리 구역디스크립터를 가리킨다. 메모리 구역 디스크립터를 추가하거나 삭제할 때, 커널은 빨강-검정 트리를 통해 이전 요소와 다음 요소를 빠르게 검색하고, 이를 사용하여 연결 리스트를 검색하지 않고도 연결 리스트를 빠르게 갱신할 수 있다. 

 

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

3) 페이지 폴트 예외 핸들러

 

(1) 페이지 폴트 예외 핸들러의 특징  
   ․메모리 구역 디스크립터는 페이지 폴트 예외 핸들러가 프로그래밍 오류 때문에 발생한 예외와 정당하게 프로세스 주소 공간에 들어 있지만 아직 할당하지 않은 페이지를 참조해서 발생한 예외를 효과적으로 구별할 수 있게 한다.  
   ․80x86 구조용 페이지 폴트 예외 핸들러인 do_page_fault() 함수는 페이지 폴트가 발생한 선형 주소와 current 프로세스의 메모리 구역을 비교한 후 예외를 처리하는 올바른 방법을 결정한다.  
   ․do_page_fault() 함수는 pt_regs 구조체의 주소 regs와 3비트 크기의 error_code를 매개변수로 받는다.  
 

(2) 페이지 폴트 예외 핸들러의 순서도  

 

※ 페이지 폴트 예외 핸들러 순서도 해석
*do_page_fault()는 먼저 잘못된 선형 주소가 마지막 1GB 영역에 들어 있는지, 아니면 커널이 존재하지 않는 페이지 프레임을 접근하다 예외가 발생한 것인지 검사한다. 

 

*vmalloc_fault 레이블 있는 코드는 커널 모드에서 불연속적인 메모리 영역을 접근하다 발생한 폴트를 다음과 같이 처리한다. 먼저 지역 변수 pgd를 cr3 레지스터에 들어 있는 현재 프로세스의 페이지 전역 디렉토리의 주소로 설정하고 지역 변수 pgd_k를 마스터 커널 페이지 전역 디렉토리로 설정한다. 만약 페이지 폴트가 발생한 선형 주소에 해당하는 엔트리가 비어 있으면 no_context 레이블이 가리키는 코드로 점프하고, 비어 있지 않으면 해당 엔트리를 프로세스의 페이지 전역 디렉토리의 해당 엔트리로 복사한다. 이 작업을 마스터 페이지 중간 디렉토리 엔트리와 마스터 페이지 테이블 엔트리에서도 반복한다. 

 

*다음으로 예외가 인터럽트를 처리하거나 커널 스레드를 실행하는 도중에 발생했는지 검사한다. 만약 페이지 폴트가 인터럽트 핸들러나 커널 스레드에서 발생하지 않았다면, 프로세스 소유의 메모리 구역을 조사하여 폴트가 발생한 선형 주소가 프로세스의 주소 공간에 들어 있는지 검사한다. vma의 값이 NULL이면 address 이후에 끝나는 메모리 구역이 없으므로 폴트가 발생한 주소는 잘못된 주소이다. 반면에 address 이후에 끝나는 첫 번째 메모리 구역이 address를 포함하는 경우에는 good_area 레이블에 있는 코드로 점프한다. 

 

*address가 프로세스의 주소 공간에 들어 있지 않으면 do_page_fault()는 bad_area 레이블에 있는 문장부터 실행한다. 사용자 모드에서 에러가 발생하면 current 프로세스에 SIGSEGV 시그널을 보내고 종료한다. 

 

*커널 모드에서 예외가 발생했다면(error_code의 비트 2의 값이 0일 때), 시스템 콜의 매개 변수로 커널에 전달한 선형 주소를 사용하는 중에 예외가 발생했거나 실제 커널 버그 때문에 예외가 발생한 것이다. 전자의 경우는 수선 코드(fixup code)로 점프한다. 이 코드는 대개 current에 SIGSEGV 시그널을 보내거나 적당한 에러 코드를 반환하며 시스템 콜 핸들러를 끝낸다. 후자의 경우는 CPU 레지스터와 커널 모드 스택을 콘솔과 시스템 메시지 버퍼로 덤프한 후, do_exit()를 호출해서 현재 프로세스를 종료시킨다. 이것이 이른바 커널 웁스(kernel oops) 에러로, 출력하는 메시지에서 붙은 이름이다. 

 

*do_page_fault()는 address가 프로세스의 주소 공간에 속하면 good_area 레이블에 있는 문장부터 실행한다. 

 

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

 

*예외가 읽기나 실행 접근 때문에 발생했다면 페이지가 이미 램에 존재하는지 검사한다. 페이지가 존재하면 사용자 모드에 있는 프로세스가 특권이 필요한 페이지 프레임(User/Supervisor 플래그가 0)에 접근하려다 예외가 발생한 것이므로 bad_area로 점프한다. 페이지가 존재하지 않으면 메모리 구역이 읽기나 실행이 가능한지도 검사한다. 만약 가능하다면 요구 페이징(demand paging) 기법에 따라 페이지 프레임을 할당한다.