Move Fast

본 글은 The Linux Kernel 을 정리한 것이며, 출처를 밝히지 않은 모든 이미지는 원글에 속한 것입니다.

페이지 할당 및 해제(Page Allocation and Deallocation)

• 물리 페이지를 할당하는 경우는 2가지
  • 디스크에 있는 실행 이미지를 메모리에 로드할 때
  • 페이지 테이블 같은 커널 특유의 자료구조를 저장할 때
• 물리 페이지는 mem_map_t 구조체의 리스트인 mem_map 자료구조로 관리되며, 부팅 시 초기화됨
• 각 mem_map_t 구조체는 물리 페이지 자료구조의 포인터를 갖고 있고, 각 물리 페이지 자료구조는 다음과 같은 3가지 정보를 포함
  • count 변수 이 페이지를 사용하고 있는 사용자(프로세스)들의 수
  • age 변수 페이지의 나이 (폐기 또는 스왑할 좋은 후보인지 결정하는데 사용)
  • map_nr 변수 물리 페이지의 프레임 번호
• frea_area 자료구조는 할당되지 않은 물리 페이지들을 저장하는 배열이며, i번째 원소는 2^i 개의 연속적인 페이지들을 갖는 연결 리스트의 포인터
  • 페이지들은 2의 제곱수 개수로 묶여서 블럭 단위로 보관됨 (1페이지, 2페이지, 4페이지, 8페이지 등)
  • map 변수는 각 원소마다 있는데, 할당된 페이지 그룹을 추적하여 관리하기 위한 비트맵으로, 비트 N은 1로 설정되면 N번째 페이지 블럭이 프리(free, 할당 가능)라는 의미

• 버디 알고리즘(Buddy Algorithm) 리눅스 페이지 블럭을 효율적으로 할당하고 해제하기 위한 알고리즘
  • 페이지 할당 코드는 하나 이상의 연속적인 물리 페이지로 구성된 블럭 1개를 할당
  • (nr_free_pages > min_free_pages) 시스템에 있는 할당 가능한 페이지 개수가 요청을 처리하기에 충분하다면, 요청한 크기에 해당하는 페이지 블럭을 free_area 에서 탐색
    • 만약 요청된 크기의 페이지를 찾을 수 없다면, 그 다음 크기(요청된 크기의 두 배)의 블럭을 탐색
    • 이 과정은 모든 free_area를 다 검색하거나, 사용할 수 있는 페이지 블럭을 찾아낼 때까지 반복
  • 찾아낸 페이지 블럭이 요청한 크기보다 크다면, 그 페이지 블럭은 요청한 크기가 될 때까지 분할됨
  • 블럭의 남은 부분은 frea_area에 해당하는 크기의 리스트에 추가되고, 요청한 크기의 페이지 블럭은 호출자에게 전달
• 페이지 해제 코드는 페이지 블럭이 해제될 때마다 인접한 프리 페이지들을 더 큰 블럭의 프리 페이지로 병합하여 메모리 조각을 줄임
  • 매 해제 과정에서 같은 크기의 인접한 버디(buddy) 블럭이 프리인지 검사
  • 페이지를 할당하다보면 메모리가 조각나기 쉬운데, 페이지 해제 코드는 계속해서 더 큰 페이지 블럭을 만들려고 하기 때문에 메모리에서 허락하는 만큼 블럭을 병합할 수 있으므로 메모리 조각을 줄이게 됨

메모리 매핑(Memory Mapping)

• 프로그램을 실행할 때, 디스크에 있는 실행 이미지를 프로세스의 가상 주소공간에 연결하는 것
• 실행 파일을 물리 메모리에 모두 로드하지 않고, 프로세스가 실행됨에 따라 참조되는 일부만 메모리에 로드(요구 페이징)
• 모든 프로세스의 가상 주소공간은 mm_struct 자료구조로 관리되며, 이 자료구조는 실행중인 이미지에 대한 정보 및 가상 페이지를 기술하는 vm_area_struct 구조체의 리스트의 포인터(=mmap)를 가지고 있음
• 각 vm_area_struct 구조체는 가상 페이지의 시작(vm_start)과 끝(vm_end), 메모리에 대한 연산(vm_ops), 접근 권한 등의 정보를 나타내며, 실행 이미지의 일부를 기술함
  • 예를 들어, nopage() 는 페이지 폴트를 처리하는 함수로, 특정 루틴의 주소를 참조하지 않으면 커널의 기본 루틴이 호출됨
• 처음에 프로그램을 실행하면, 메모리 매핑 과정에서 vm_area_struct 구조체의 집합이 생성되고, 가상 주소공간은 실행 코드, 초기화된 데이터(변수), 초기화되지 않은 데이터(BSS) 등을 포함

• 페이지 폴트가 발생하면, 커널에서 페이지 폴트 핸들러는 폴트가 발생한 가상 주소를 포함하는 vm_area_struct를 탐색
  • 폴트가 아니더라도 탐색 과정은 자주 발생하기 때문에, 실제로 vm_area_struct 리스트는 AVL 트리 구조
  • AVL은 균형 이진 트리로, 삽입/삭제 과정에서 항상 왼쪽과 오른쪽 서브트리의 높이차가 1보다 커지지 않도록 회전함

• 페이지 폴트가 발생한 곳이 유효한 주소(가상 주소공간 내에 존재)이면, 커널은 PTE를 검사
  • PTE가 값이 0이 아니면,스왑 아웃되어 PTE에 다른 페이지가 저장된 것이므로 그 페이지는 스왑 파일에 존재
  • 위의 경우, PFN 항목은 스왑 파일의(그리고 어떤 스왑 파일의) 어느 부분에 그 페이지가 들어있는 지에 대한 정보를 가짐
  • 요청한 페이지가 물리 메모리로 올라오면, 프로세스의 페이지 테이블을 갱신한 후, 폴트가 발생한 가상 주소에서 재실행

페이지 캐시(Page Cache)

• 디스크에 있는 실행 이미지를 불러오는 횟수를 줄이기 위해 고안된 저장공간으로, 메모리 매핑된 파일은 페이지 단위로 읽혀지는데 물리 메모리에 로드될 때마다 해당 페이지는 페이지 캐시에 저장됨
• 페이지 캐시는 page_hash_table 자료구조로 나타내며, 각 원소는 mem_map_t 구조체의 리스트의 포인터
  • 각 mem_map_t 구조체는 매핑된 페이지가 저장된 파일(inode)과 파일 내 오프셋(offset)을 포함
  • inode는 파일 하나에 1:1로 대응되는 커널 자료구조 VFS inode 번호를 의미
• 실제로 요구 페이징에서 페이지 폴트가 발생할 때마다, 커널은 페이지 캐시를 가장 먼저 참조
  • 페이지가 캐시에 있으면, 그 페이지를 나타내는 mem_map_t 자료구조에 대한 포인터가 페이지 폴트 처리 코드로 전달됨
  • 페이지가 캐시에 없다면, 물리 페이지를 할당하고 디스크 상의 파일로부터 페이지를 읽어와 메모리에 로드
    • 빈 물리 페이지가 없다면 스왑 알고리즘을 실행하여 적절한 페이지를 스왑 아웃
• 페이지 폴트가 발생할 때마다 페이지 캐시에 폴트가 발생한 페이지를 저장하는데 가능한 다음 페이지도 저장하려고 함. 이는 프로세스가 페이지를 순차적으로 접근할 가능성이 높기 때문에 최대한 미리 페이지를 읽어와 메모리 접근을 줄이려는 목적
• 페이지가 어떤 프로세스에 의해서도 사용되지 않으면 캐시에서 제거됨

페이지 스왑 아웃과 폐기(Page Swap-out and Discarding)

• 캐시가 커지면 물리 메모리 공간이 부족할 수 있는데, 이를 위해 커널 스왑 데몬(kswapd)이 불필요한 물리 메모리를 검사하고 해제함
• 커널 스왑 데몬은 커널의 init 프로세스에 의해 시작되는 커널 쓰레드라는 특별한 종류의 프로세스로, 물리 메모리 공간에서 커널 모드로 실행됨 (가상 주소공간을 가지지 않음)
• 커널 스왑 데몬은 커널 스왑 타이머가 주기적으로 만료될 때마다 free_pages_high 과 free_pages_low 라는 2개의 변수를 사용하여 실제 할당되지 않은 페이지 개수(nr_free_pages)가 너무 적지 않은지 검사
  • nr_free_pages > free_pages_high, 타이머가 만료되면 아무 일도 하지 않고 다시 잠듬 (다음 타이머 만료까지 대기)
  • nr_free_pages < free_pages_low, 타이머가 만료되면 물리 페이지를 해제하기 위해 3가지 방법을 시도 (다음 타이머 만료가 절반정도 당겨짐, 이전의 절반 정도 잠듬)
    • 페이지 캐시와 버퍼 캐시 크기 줄이기
    • 시스템 V 공유 메모리 페이지를 스왑 아웃
    • 페이지를 스왑 아웃하고 폐기
  • 매번 실행될 때마다 위 3가지 방법에서 최종적으로 성공한 방법을 기억해서 사용함
  • nr_free_pages 가 low ~ high 사이에 있으면, 다음 타이머 만료가 미뤄짐 (low보다 작을 때 적게 잠들었으니, low보다 커지면 더 오래 잠드는 구조)
• 커널 스왑 데몬은 nr_async_pages 라는 변수로 현재 스왑 파일에 저장될 페이지 개수도 고려하는데, 이 변수는 어떤 페이지가 스왑 파일에 쓰여지기 위해 큐에 들어가면 증가하고, 스왑 파일에 쓰여졌으면 감소
• 페이지 캐시와 버퍼 캐시 크기 줄이기
  • 물리 메모리 공간이 부족하면 가장 먼저 페이지 캐시와 버퍼 캐시에 있는 불필요한 페이지(사용하지 않는 것)를 제거
  • 메모리에서 스왑 아웃하는 경우와 달리 실제 장치에 기록할 필요가 없음
  • 커널 스왑 데몬이 캐시를 줄이려고 할 때마다, mem_map 리스트에 있는 페이지 블럭이 실제로 물리 메모리에서 제거되도 괜찮은지 시계 알고리즘(clock algorithm, 한 번에 몇 페이지씩 차례로 조사)으로 검사
    • 프리 페이지 수가 급격히 떨어져 스와핑이 빈번하게 발생한다면 검사할 페이지 블럭의 크기가 커짐
    • 페이지 블럭은 돌아가며 검사되는데, 각 페이지는 페이지 캐시나 버퍼 캐시에 있는 것만 해당되며, 공유 페이지는 제외
  • 해제되는 페이지는 어떤 프로세스의 가상 메모리에도 속하지 않는 것이므로, 페이지 테이블을 수정할 필요가 없음
• 시스템 V 공유 메모리 페이지 스왑 아웃
  • 커널 스왑 데몬은 캐시된 페이지를 제거하는 걸로 충분하지 않은 경우, 공유 페이지를 스왑 아웃
  • 시스템 V 공유 메모리는 둘 이상의 프로세스가 가상 메모리를 공유하여 정보를 주고 받는 프로세스간 통신 메커니즘(IPC)
    • 공유 메모리는 shmid_ds 자료구조로 표현되며, 각 프로세스마다 대응되는 가상 페이지들(vm_area_struct 구조체의 리스트)을 참조함
    • vm_area_struct 구조체에서는 vm_next_shared 와 vm_prev_shared 포인터로 공유되는 가상 페이지들을 연결
    • 각각의 shmid_ds 자료구조는 공유 가상 페이지가 매핑되어 있는 물리 페이지에 해당하는PTE의 리스트도 가짐
  • 커널 스왑 데몬은 공유 페이지를 스왑 아웃할 때도 시계 알고리즘을 사용하며, 맨 마지막으로 스왑 아웃된 공유 페이지를 기억
  • 공유 물리 페이지의 PFN은 이 페이지를 공유하는 모든 프로세스의 페이지 테이블에 존재하기 때문에 이들을 모두 변경해주어 스왑 아웃되었다고 표시(스왑 파일의 위치와 오프셋을 표시)해야 함
  • 커널 스왑 데몬은 각 프로세스의 페이지 테이블에서 공유 가상 페이지의 번호(VPFN)로 엔트리를 찾아서 스왑 아웃된 PTE로 변환시키고 해당 페이지의 count 변수를 1씩 감소함. 만약 count 변수가 0이 된다면 해당 공유 페이지를 스왑 파일로 스왑 아웃
  • 마찬가지로 shmid_ds 자료구조에 있는 PTE도 스왑 아웃된 PTE로 교체
  • 스왑 아웃된 PTE는 다시 물리 메모리에 해당 페이지를 적재할 때 사용됨
• 페이지 스왑 아웃과 폐기
  • 공유 페이지 스왑 아웃으로도 물리 메모리 공간이 부족한 경우, 커널 스왑 데몬은 각 프로세스의 페이지들을 검사하여 스왑 아웃할 대상을 관찰
  • 스왑 후보가 되는 페이지들은 그 안에 저장된 데이터들을 어떤 방법으로든 가져올 수 없어 저장해야 하는 경우
  • 폐기 후보가 되는 페이지들은 실행 코드처럼 변경되지 않아 스왑 파일에 쓸 필요가 없는 경우
  • 후보 페이지를 가진 프로세스가 결정되면, 그 프로세스의 가상 주소공간을 전부 살펴보면서 공유되거나 락이 걸리지 않은 영역을 탐색 (메모리에 락이 걸려 있는 페이지는 스왑하거나 폐기할 수 없음)
  • 커널 스왑 데몬은 실행될 때마다 후보 페이지의 age 변수를 1씨 증가시켜 오래된 것으로 만듬 (페이지는 자주 사용될수록 젊어지고, 적게 사용될수록 나이 듬, 오래된 페이지들은 스와핑의 좋은 후보)
  • 각 페이지를 나타내는 mem_map_t 구조체는 count 변수도 가지는데, 커널 스왑 데몬이 사용할 때는 count가 1씩 증가
    • 스왑 알고리즘은 count 가 적은 페이지들(사용자 수가 적은 페이지들)만 스왑 아웃
  • 어떤 프로세스는 가상 페이지에서 자신의 스왑 연산(vm_area_struct의 vm_ops 포인터)을 사용할 수 있으며, 연산이 정의되지 않은 경우 스왑 데몬은 스왑 파일에 페이지를 할당하고 스왑 페이지를 스왑 파일에 기록
  • 더티 페이지만 스왑 파일에 저장되며, 더티 페이지가 아닌 경우 해당 물리 페이지는 free_area 에 추가됨
  • 스왑 아웃 후, PTE에 스왑 파일의 위치와 파일 내 오프셋을 표시

스왑 캐시(Swap Cache)

• 동일한 페이지에 대해 스왑 아웃이 반복적으로 발생할 때, 스왑 파일에 기록하는 횟수를 줄이기 위해 사용 (더티 페이지만 해당됨)
• 스왑 캐시는 페이지 테이블 엔트리의 리스트로, 각 리스트 노드당 물리 페이지 하나에 해당됨
  • 커널은 스왑 아웃 요청을 처리할 때 가장 먼저 스왑 캐시에 유효한 PTE 가 존재하는지 파악
• 스왑 아웃되었다가 다시 접근된 페이지는 스왑 파일과 물리 메모리에 모두 존재하게 되는데, 이후 다시 스왑 아웃할 때 페이지가 변경되지 않았으면 스왑 파일에 이미 유효한 페이지가 존재하므로 다시 기록할 필요가 없음
• 스왑 캐시에 있는 PTE는 스왑 아웃된 페이지의 것으로, 스왑 파일의 inode 번호와 파일 내 오프셋을 포함
  • PTE가 값이 0이 아니면, 이미 스왑 아웃되었다는 의미로, 페이지의 변경 유무를 파악
  • 페이지가 변경되었다면, 해당 PTE를 스왑 캐시에서 삭제 (다시 기록해야 함)
• 예를 들어, 최초 실행 시 읽기/실행 작업으로 페이지 폴트가 발생한 경우, 페이지를 메모리로 가져온 뒤 PTE에 읽기만 가능으로 표시
  • 이후 쓰기 작업으로 페이지 폴트가 발생하면, 그 페이지는 더티로 표시되며 스왑 아웃 (메모리 -> 디스크) 후 스왑 캐시에 스왑 파일의 inode 번호 및 파일 내 오프셋을 저장, PTE에 쓰기 가능으로 표시
  • 이후 다시 스왑 아웃이 발생하면, 이미 스왑 파일에 존재하므로 다시 기록하지 않음

페이지 스왑 인(Page Swap-in)

• 스왑 파일에 저장된 더티 페이지들이 다시 물리 메모리에 로드해야 하는 경우를 스왑 인(Swap In)이라고 함
  • 이미 스왑 아웃된 물리 페이지에 매핑된 가상 페이지에, 쓰기 작업을 하는 경우
• RE: 접근하는 페이지(VPFN)에 해당하는 PTE가 유효하지 않으면 페이지 폴트가 발생
  
  • 페이지 폴트 핸들러: vm_area_struct 의 nopage()
  • 가상 주소공간에 유효하지 않은 주소이면 세그멘테이션 폴트 시그널을 프로세스에게 전달
  • PTE 얻기
    • MMU는 TLB가 있으면 TLB를 먼저 참조
    • MMU는 TLB에 엔트리가 없으면 페이지 테이블을 참조
  • 물리 페이지 얻기
    • PTE에 스왑 아웃이 표시되어 있으면, 스왑 파일로부터 물리 페이지를 탐색
    • PTE에 아무 값도 없으면, 페이지 캐시를 참조
    • 그래도 못 찾으면, 디스크에 실행 이미지로부터 해당 페이지를 물리 메모리에 로드하고 페이지 캐시에 저장
• vm_area_struct 에서 루틴 주소(vm_area_struct 구조체의 vm_ops 가 참조하는 swapin 포인터)를 변경하면 해당 루틴을 실행 (공유 페이지의 경우 특별한 처리가 필요하므로, swapin 연산이 정의되어 있음)

본 글은 The Linux Kernel 을 정리한 것이며, 출처를 밝히지 않은 모든 이미지는 원글에 속한 것입니다.

가상 메모리(Virtual Memory)

• 물리 메모리의 크기가 제한적인 단점을 극복하기 위해 도입된 방법으로, 메모리를 필요로 하는 프로세스들 사이에 물리 메모리를 공유하도록 하여, 각 프로세스가 실제 물리 메모리보다 큰 메모리를 가질 수 있도록 하는 소프트웨어 기법
• 메모리 관리 서브시스템은 다음과 같은 기능을 제공
  • 넓은 주소공간 프로세스마다 할당된 가상 주소공간은 물리 메모리보다 몇 배 더 클 수 있음
  • 보호 각 프로세스는 독립된 가상 주소공간을 가지기 때문에, 어떤 프로세스도 다른 프로세스에게 영향을 줄 수 없음
  • 메모리 매핑 실행 이미지와 데이터 파일을 프로세스의 주소공간에 매핑시켜 실제로 필요할 때 물리 메모리에 로드
  • 공정한 물리 메모리 할당 프로세스들이 물리 메모리를 공정하게 공유할 수 있도록, 현재 실행중인 프로세스에게 메모리를 할당
  • 공유 가상 메모리 서로 다른 프로세스들은 동일한 물리 메모리 영역을 각자의 주소공간에 매핑해서 사용 가능
• 프로세스들은 물리 메모리를 공유하기 위해 각자의 페이지 테이블(Page Table)을 가지며, 페이지 테이블 엔트리(Page Table Entry, PTE)는 매핑된 가상 메모리 주소에 대응하는 물리 메모리 주소를 포함
  • CPU가 프로세스를 실행하면서 접근하는 메모리 주소는 모두 가상 메모리 주소이며, 가상 메모리 주소로 접근할 때 페이지 테이블을 이용하여 물리 메모리 주소로 변환
  • 주소 변환을 쉽게 하기 위해, 메모리는 페이지(Page)라는 작은 단위로 나뉘는데 모든 페이지들은 같은 크기 (보통 4KB나 8KB)
  • 각 페이지는 페이지 프레임 번호(Page Frame Number, PFN)로 식별 가능하며, 가상 메모리에서는 가상 페이지 프레임 번호(Virtual PFN, VPFN)라고 함
  • 가상 주소는 가상 페이지 프레임 번호와 해당 페이지에서의 오프셋으로 구성되며, 이 오프셋은 물리 페이지에서도 동일
  • 페이지 크기는 2의 제곱수인데, 그 이유는 주소 변환을 할 때 비트 마스킹과 쉬프트 연산으로 쉽게 처리하기 위함
• 주소 변환 과정
  • CPU가 가상 주소를 메모리 관리 장치(MMU)에게 전달
  • MMU가 가상 주소로부터 VPFN과 페이지 오프셋을 추출하여 페이지 테이블에서 VPFN으로 인덱싱
  • MMU는 엔트리에서 물리 페이지 프레임 번호(PFN)를 얻음
  • PFN와 페이지 크기를 곱하여 물리 메모리에서 베이스 주소를 계산한 뒤, 베이스 주소에서 페이지 오프셋을 더하여 실제 물리 메모리의 위치로 접근

• 페이지 테이블은 3가지 정보를 포함
  • 유효 플래그 PTE가 유효한지를 나타내며, 유효하지 않다면 페이지 폴트(Page Fault) 발생
  • 물리 페이지 프레임 번호 VPFN 에 대응하는 물리 페이지 인덱스
  • 접근 제어 정보 해당 페이지가 가지고 있는 읽기/쓰기/실행 권한
• 페이지 폴트(Page Fault) 프로세스가 물리 메모리에 매핑되지 않은 가상 페이지에 접근하는 것
• 접근 제어(Access Control) PTE는 프로세스가 허용되지 않은 방식으로 물리 메모리에 접근하는 것을 막기 위해 접근 제어 정보를 포함 (접근 제어 정보는 프로세서마다 다름)
  • 예를 들어, 쓰기 권한이 없는 위치(코드 영역)에 쓰려는 경우, 실행 권한이 없는 위치(데이터 영역)에서 실행하려는 경우
  • 대부분 프로세서는 커널 모드와 유저 모드를 지원하며, 유저 모드에서 실행 중일 때 커널 코드나 자료구조에 접근할 수 없음
• 페이지 테이블을 이용하면 가상 메모리는 물리 메모리에서 페이지 단위로 임의의 순서로 배열될 수 있음. 즉, 가상 페이지들은 물리 메모리에서 어떤 특정 순서로 존재할 필요가 없음
• 대부분 범용 프로세서들은 물리 주소 모드와 가상 주소 모드를 제공하는데, 물리 주소 모드에서는 페이지 테이블이 필요 없기 때문에 주소 변환을 하지 않음. 커널 코드는 물리 모드에서 실행(물리적 주소 공간에 바로 매핑)되도록 링크되어 있음

요구 페이징(Demand Paging)

• 실행중인 프로그램이 현재 사용하는 가상 페이지만을 물리 메모리에 로드하는 것
  • 예를 들어, DB 프로그램이 DB에 검색할 때, DB의 모든 내용이 메모리에 로드될 필요는 없으며, 검색할 데이터 레코드들만 필요. 즉, DB 프로그램에서 새로운 레코드를 추가하는 것을 처리하는 코드를 메모리로 읽어들일 필요는 없을 것
• 프로세스의 페이지 테이블에서 VPFN으로 엔트리를 찾았을 때, 해당 엔트리에 대응하는 물리 페이지가 없다면 페이지 폴트(Page Fault)가 발생하고, 프로세스는 리눅스 커널에게 폴트가 발생한 가상 주소와 폴트의 원인을 통보
  • 가상 주소가 프로세스의 가상 주소공간 내 유효하지 않다면, 커널은 SIGSEGV 시그널(세그멘테이션 폴트)을 프로세스에게 전달 (프로세스가 그 시그널에 대한 핸들러를 정의하고 있지 않다면 기본 동작으로 프로세스는 종료됨)
  • 가상 주소가 프로세스의 가상 주소공간 내 유효하다면, 커널은 폴트가 발생한 가상 페이지를 디스크의 실행 이미지에서 찾아서 물리 메모리에 로드한 뒤, 페이지 테이블에 PTE를 추가
    • 이 과정은 디스크에 접근하기 때문에 시간이 걸리므로, 그 시간동안 다른 프로세스를 실행
    • CPU는 페이지 폴트가 발생했던 기계어 명령부터 재실행 (아래 그림의 7번)

• 스와핑(Swapping) 프로세스의 가상 페이지를 물리 메모리에 로드할 때 빈 물리 페이지가 없는 경우, 기존 물리 페이지를 제거하여 공간을 마련하는 과정
  • 커널은 물리 메모리에서 더티 페이지(dirty page, 변경된 페이지)를 제거할 때, 내용을 보존하기 위해 스왑 파일(swap file)에 페이지를 저장
  • 스왑 알고리즘(swap algorithm)은 어떤 페이지를 제거하거나 스왑할 지 결정하는데, 반복적인 스왑으로 디스크에 접근하느라 커널이 다른 일을 하지 못하는 쓰래싱 상태(thrashing)를 피하는 것이 중요
  • 따라서, 효율적인 스왑 알고리즘은 프로세스가 현재 사용하고 있는 페이지들의 집합(작업 집합)을 모두 물리 메모리에 있게 함
  • 페이지 교체 알고리즘으로 Least Recently Used(LRU) Page Aging 기법을 사용
  • 페이지마다 나이(age)가 있고, 페이지가 자주 접근될수록 젊어지고, 적게 접근될수록 나이가 드는 구조
  • 나이든 페이지는 스와핑의 좋은 후보이며, 연결 리스트로 구현됨 (사용된 페이지를 참조하는 노드는 리스트의 맨 뒤로 이동하며, 결국 리스트의 맨 앞에 있는 노드는 가장 적게 참조된 페이지를 가리키게 됨, 리스트가 꽉 차면 맨 앞의 노드를 제거)

캐시(Cache)

• CPU가 메모리에 접근하는 것은 디스크보다는 빠르지만 시간이 걸리는 작업이기 때문에, 커널은 메모리 관리와 관련하여 몇 가지 캐시를 사용. 하드웨어 장치에 접근하는 횟수를 줄임
• 버퍼 캐시(Buffer Cache) 디스크에 데이터를 읽어오거나 쓰기 전에, 블럭 디바이스 드라이버가 데이터 버퍼들을 저장하기 위해 사용
• 페이지 캐시(Page Cache) 디스크에서 메모리로 페이지들을 읽어들일 때 디스크 접근 횟수를 줄이기 위해 파일의 논리적인 내용을 페이지 단위로 저장하는 용도

• 스왑 캐시(Swap Cache) 더티 페이지들만 저장하는 디스크 파일
  
  • 스왑 파일에 기록된 이후 페이지가 더 이상 변경되지 않았다면, 그 페이지가 다음에 스왑 아웃(메모리 → 디스크)될 때는 이미 스왑 파일에 동일한 내용이 있으므로 디스크에 기록하지 않고 폐기
  • 스와핑이 자주 발생하면, 불필요하고 값비싼 디스크 연산을 많이 줄일 수 있음
  • 반면, 변경된 페이지는 스왑 아웃할 때마다 다시 스왑 파일에 기록
• 하드웨어 캐시(Hardware Cache) 페이지 테이블 엔트리(PTE)를 저장하는 용도로 CPU 내부에 존재하는 저장공간이며, 변환 참조 버퍼(Translation Look-aside Buffers, TLB)라고도 함
  • TLB는 시스템의 여러 프로세스로부터 PTE의 복사본을 저장
  • 프로세서는 항상 (메모리에 있는) 페이지 테이블을 직접 읽는 것이 아니라, PTE를 필요로 할 때마다 TLB에서 페이지에 대한 변환 결과를 가져옴 (CPU에서 메모리보다 가까우므로 속도가 빠름)
    • CPU가 요청한 PTE에 대한 TLB 엔트리를 찾지 못하면, 커널에게 TLB를 찾지 못했다는 신호(TLB miss)를 보냄
    • 커널은 주소 변환을 위해 새로운 TLB 엔트리를 생성해서 추가
    • 예외 처리 이후, CPU는 같은 가상 주소 변환을 재시도
    • TLB Hit으로 처리 (아래 첫번째 그림은 TLB Hit, 두번째 그림은 TLB Miss)

• 캐시는 관리하는데 더 많은 시간과 공간을 사용해야 하며, 캐시가 망가지는 경우 시스템이 죽는다는 단점이 존재

3단계 페이지 테이블

• 리눅스 커널은 3단계 페이지 테이블을 사용하며, 가상 주소는 각 단계의 페이지 테이블에서의 오프셋을 포함
• 1단계 페이지 테이블의 경우, 페이지 글로벌 디렉토리(PGD)의 주소에 가상 주소에 포함된 오프셋을 더해서 엔트리를 탐색
• 매 단계마다 오프셋으로 페이지 테이블 엔트리를 찾아서, 엔트리에 저장된 페이지 프레임 번호에 페이지 크기를 곱해 다음 페이지 테이블의 베이스 주소를 계산
• 마지막 페이지 테이블의 경우, 엔트리에 저장된 PFN은 물리 페이지 프레임 번호이며, 베이스 주소에 가상 주소의 마지막 바이트 오프셋을 더해 실제 물리 메모리 주소를 계산
• 커널을 실행하는 플랫폼은 커널이 특정 프로세스의 페이지 테이블을 탐색할 수 있도록 하는 매크로들을 지원해야 함
  • 인텔 x86은 2단계 페이지 테이블을 지원하며 AMD의 x86-64는 4단계 페이지 테이블을 지원, 그러나 리눅스 커널은 동일한 페이지 테이블 처리 코드를 사용

본 글은 The Linux Kernel 을 정리한 것이며, 출처를 밝히지 않은 모든 이미지는 원글에 속한 것입니다.

컴퓨터 언어

• 어셈블리어 CPU가 메모리에서 가져와 실행하는 가장 작은 단위의 명령어
  • 레지스터와 데이터에 대한 연산을 명시적으로 다루며, CPU 아키텍처마다 문법이 다름
  • 예를 들어, 인텔 80486 CPU에서 16진수 0x89E5는 ESP 레지스터의 내용을 EBP 레지스터로 복사하라는 의미
• 어셈블러(Assembler) 어셈블리어로 작성된 코드를 기계어 코드로 변환하는 프로그램
  • nasm: interl, AT&T 문법 모두 지원
  • mlps: mlps 문법
  • intel: intel 문법
  • gcc: AT&T 문법 (컴파일러이지만, 소스코드를 바로 기계어 코드로 변환해줌)
  • 반대로 기계어 코드를 어셈블리어로 바꿔주는 것을 디스어셈블(Disassemble)이라고 함
• 리눅스 커널의 소스코드는 대부분 C로 작성되었으며, 효율성을 위해 어셈블리어로 작성된 부분이 극히 일부분 존재
• 고수준 언어의 필요성
  • 어셈블리어로 프로그램을 작성할 경우, 어렵고, 시간이 오래 걸리며, 오류를 범하기 쉬움
  • 특정 프로세서에만 국한되므로 이식성이 없음
  • C언어 같은 고수준 언어로 작성할 경우, 프로그램의 동작을 논리적인 자료와 알고리즘으로 표현 가능
• 컴파일러(Compiler) 인간이 읽기 쉬운 문법으로 작성된 코드를 어셈블리어로 변환하는 프로그램
  • 반대로 어셈블리어로 작성된 것을 소스코드로 바꿔주는 것을 디컴파일(Decompile)이라고 함
• C/C++ 같은 native 언어는 컴파일러가 즉시 소스코드를 기계어 코드로 변환해주지만, 파이썬이나 자바, C# 과 같은 가상 언어들은 가상 머신에서 실행되는 언어로 변환되어야 함. 따라서, 가상 머신만 있다면 운영체제 종류에 상관없이 가상 언어들로 작성된 프로그램은 실행 가능
• 링커(Linker) 여러 개의 오브젝트 모듈과 라이브러리를 연결하여 하나의 프로그램을 만들어내는 프로그램
  • 오브젝트 모듈: 어셈블러나 컴파일러가 만들어 낸 기계어 코드 결과물로, 기계어 코드와 자료, 그리고 링커가 다른 모듈을 합치는데 필요한 정보를 포함
  • 리눅스 커널은 많은 종류의 오브젝트 모듈들을 링크하여 만들어진 거대한 프로그램
  • 리눅스 바이너리에서 링커의 동작 과정: 정적 라이브러리는 링커에 의해 하나의 파일에 함수 내용이 모두 포함되지만, 동적 라이브러리를 링킹하면 런타임(실행 환경)에서 필요한 정보(오프셋, 심볼명 등)만 포함되고, 실제 함수 내용은 이미 커널 메모리에 있다고 가정. 이후 로더에 의해 실행될 때 라이브러리 베이스 주소를 계산하고 함수가 호출되는 순간 메모리 주소를 계산

운영체제

• 사용자가 응용 프로그램을 실행할 수 있도록 해주는 시스템 프로그램들의 집합
• 운영체제는 하드웨어를 추상화하여 사용자에게 모든 기능들을 하나로 모아서 장치 종류에 상관없이 일관된 모습으로 제공
• 하드웨어를 관리하는 부분(서브시스템)은 크게 4가지
  • 메모리 관리(Memory Management) 메모리 자원 추상화 인터페이스 (캐시, RAM 등)
  • 디바이스 드라이버(Device Driver) 주변장치 추상화 인터페이스
  • 파일 시스템(File System) 저장 공간 추상화 인터페이스, 하나의 장치에 대응하는 파일이 존재 (디스크 등)
  • 프로세스(Process) 위 3개와 CPU 자원을 사용하는 상위 계층의 인터페이스

커널 자료구조

• 리눅스 커널은 시스템의 현재 상태에 대해 많은 정보를 가지고 있어야 하며, 시스템 내부에서는 어떤 사건이 발생하면 현재 상태에 변화를 반영하기 위해 자료구조를 변경
  • 예를 들어, 한 사용자가 시스템에 로그인하면, 새로운 프로세스가 생성되는데, 커널은 이 프로세스를 나타내는 자료구조를 생성하고, 이를 시스템 내의 프로세스를 나타내는 모든 자료구조와 연결해야 함
• 자료구조의 대부분은 실제 메인 메모리에 존재하는 것이며, 커널과 커널의 서브시스템만이 접근 가능
  • 자료구조는 데이터와 포인터를 포함하며, 이 포인터는 다른 자료구조나 루틴(함수)을 참조
• 연결 리스트(Linked List) 탐색은 선형 시간 O(N), 삽입/삭제는 상수 시간 O(1)

• 해시 테이블(Hash Table) 탐색은 상수 시간 O(1), 삽입/삭제는 구조에 따라 다르며 최악의 경우 선형 시간 O(N)
  • 자료구조에 대한 포인터의 배열로, 인덱스는 자료구조의 내용으로부터 만들어지며 해시 함수(hash function)로 계산
  • 자주 사용하는 자료구조로의 접근 속도를 높이기 위해 사용 e.g., 캐시(cache)

• 해시 충돌(hash collision) 해시 테이블의 크기는 제한적이므로, 해시 함수의 결과가 동일한 경우가 존재
  • 해시 충돌을 최대한 줄이기 위한 해시 테이블 구조가 2가지 있음
• Separate Chaining 버켓은 자료구조의 리스트 헤드를 저장
  • 삽입 시 리스트의 끝에 추가
  • 리스트 노드를 따라가며 원하는 자료구조를 탐색 (충돌이 자주 발생하면 리스트 탐색 시간이 길어짐)
  • 해시 테이블의 크기를 키울 때, 버켓의 개수를 늘려서 리스트를 나누어 저장

•  Open Addressing 버켓에 자료구조의 포인터가 아닌, "키, 값"으로 자료구조 자체를 저장
  • 리스트 포인터가 없으므로 추가 메모리 사용이 없음
  • Linear Probing 충돌이 발생한 위치에서 다음 빈 자리까지 선형 탐색. 데이터 삭제 시 빈 공간이 생겨서 다음 충돌에 탐색이 막히는 것을 막기 위해 더미값을 넣어 탐색이 끊기지 않도록 함
  • 해시 테이블의 크기를 키울 때, 버켓의 개수를 늘림

추상 인터페이스

• 인터페이스(interface) 특정 방법으로 동작하는 루틴과 자료구조의 모음
  • 예를 들어, 모든 네트워크 디바이스 드라이버는 특정 자료구조를 이용하여 정해진 루틴들을 커널에게 제공해야 함.
• 하드웨어 장치마다 다른 코드로 된 하위 계층에서 제공하는 인터페이스(또는 서비스)를 사용하는 코드 계층이 존재
  • 장치마다 고유한 코드는 표준 인터페이스를 제공하여 일반적인 코드 계층을 지원
  • e.g., 네트워크 계층
• 보통 하위 계층은 시스템 부팅 과정에서 자신을 상위 계층에 등록하는데, 이 과정은 어떤 연결 리스트에 자료구조를 추가하는 일을 포함
  • 예를 들어, 커널에 존재하는 각 파일 시스템은 부팅할 때 자신을 커널에 등록하며, 모듈을 사용하는 경우에는 처음으로 그 파일 시스템이 사용될 때 등록
• 등록된 자료구조가 함수를 가지고 있는 경우, 포인터는 특정 작업을 수행하는 소프트웨어 함수의 주소
  • 예를 들어, 각 파일 시스템이 등록할 때 리눅스 커널에 넘겨주는 자료구조에는 파일 시스템이 마운트될 때마다 불리는 파일 시스템에 고유한 루틴의 주소가 있음

본 글은 The Linux Kernel 을 정리한 것이며, 출처를 밝히지 않은 모든 이미지는 원글에 속한 것입니다.

중앙 처리 장치(Central Processing Unit, CPU)

• 프로세서(Processor) 또는 마이크로프로세서(Microprocessor)
• 기계어 코드를 실행하는 하드웨어, 어셈블리어 1줄은 실행되는 가장 작은 단위의 명령어
  • 아래 그림은 Hello World 를 출력하는 바이너리 파일의 어셈블리 코드
  • 0000000100003f60 <_main> 섹션의 첫번째 명령어 pushq %rbp 부터 실행 (기계어 코드 0x55)

• 사칙 연산과 논리 연산(>, <, =) 뿐만 아니라 "메모리 위치 X에 있는 내용을 레지스터 Y로 읽어들여라" 같은 단순한 명령어를 실행
• 기계어 코드는 16진수로 표현되며, 어셈블리어 문법은 CPU 아키텍처마다 다름 (프로그램은 16진수로 작성되어 있음)

레지스터(Register)

• 어셈블리어를 실행할 때, 데이터를 저장하고, 연산하기 위해 사용하는 CPU 내부에 있는 저장소 (위 그림의 R0 ~ Rn, PC)
  • CPU는 바로 메모리에 값을 쓰거나, 메모리로부터 값을 가져올 수 없으며, 반드시 레지스터를 거쳐야 메모리에 접근 가능
• 레지스터의 크기와 개수 및 종류는 CPU 아키텍처마다 다름
• 일반 목적 레지스터와 특수 목적 레지스터 2가지 유형이 있음
• 특수 목적 레지스터는 반드시 다음과 같은 3개를 포함
  • 프로그램 카운터(Program Counter, PC) CPU가 다음에 실행할 명령어의 주소, 명령어를 실행할 때마다 값이 증가
  • 프로세서 상태(Processor Status, PS) 논리 연산처럼 명령어 실행 후 결과가 나오는 경우 그 값을 저장할 때 사용 또는 CPU의 현재 상태를 나타내는 정보도 포함(커널 모드 vs 유저 모드)
  • 스택 포인터(Stack Pointer, SP) 스택에 데이터를 저장할 주소
    • 스택: CPU가 프로그램을 실행할 때 데이터를 임시로 저장하기 위한 메모리(RAM)의 공간
    • 스택은 LIFO(Last-In-First-Out) 구조로, 마지막에 삽입한 값을 먼저 가져올 수 있음
    • 스택은 메모리 주소가 감소하는 방향으로 증가하며, 어셈블리어로 push 명령어를 실행하면 메모리 주소가 감소하면서 값이 삽입되고, pop 명령어를 실행하면 메모리 주소가 증가하면서 값을 가져옴

메모리(Memory)

• 메인 메모리(Main Memory) RAM이라는 CPU 외부에 있는 저장 공간
• 캐시 메모리(Cache Memory) CPU 내부에 있는 소량의 메모리로, 메인 메모리보다 접근 속도가 빠르고 비쌈
  • L1 캐시 메모리 하나의 캐시에 명령어와 데이터를 같이 저장하거나, 명령어와 데이터를 별도로 저장
  • L2 캐시 메모리 메인 메모리의 내용을 임시로 보관할 때 사용하며, L1 보다 용량이 큼
  • L3 캐시 메모리 멀티코어 시스템에서 코어간 작업 속도를 향상시키기 위해 여러 코어끼리 공유하는 메모리
  • CPU에서 L1, L2, L3 순서대로 멀리 있고 속도는 L1이 가장 빠르고 L3가 가장 느림

• 일치성: CPU는 메인 메모리에 접근하기 전에, 캐시에 필요한 데이터가 있는지 먼저 확인하며 데이터가 없을 때 메인 메모리에 접근, 캐시와 메인 메모리는 동일한 데이터에 대해 같은 값을 유지해야 함
  • 캐시에서 바로 값을 가져다 쓰는 것보다, 값이 없어서 메모리에서 캐시로 값을 가져와서 쓰는 것이 더 느림
• 시간 지역성: 자주 참조하는 데이터를 보관, 읽고 쓸 때마다 데이터의 참조 카운트가 증가
• 공간 지역성: 자주 사용하는 데이터의 인접한 데이터들까지 보관 (그 주변도 자주 사용할 것이라는 가정)
  • 캐시가 동작하는 아주 구체적인 원리
  • 2차원 행렬 M[256][256] 을 연산할 때, r을 행 인덱스, c를 열 인덱스라고 하자. 같은 행에 있는 원소는 인접하기 때문에 메모리에서 캐싱할 때 같은 행에 있는 원소들을 캐시 메모리로 가져올 것이고, for(c = 0; ...; c++) for(r = 0 ...; r++) 순서로 중첩 반복문을 작성하는 것보다 for(r = 0; ...; r++) for(c = 0; ...; c++) 순서로 작성하는 것이 캐시 히트(cache hit)를 높게 함
  • The impact of cache locality on performance in C through matrix multiplication

버스(Bus)

• 메인 보드에 있는 각 구성 요소들은 여러 개의 버스로 연결되어 있음
• 시스템 버스
  • 데이터 버스(data bus) 양방향(CPU로 읽어들이거나 CPU에서 쓸 때)으로 전송되는 데이터를 가지고 있는 버스
  • 주소 버스(address bus) 데이터를 전송할 메모리의 위치(=주소)를 가지고 있는 버스
  • 제어 버스(control bus) 시스템 전체에 타이밍 신호와 제어 신호를 전달하는 선들을 가지며, ISA나 PCI 버스가 주변장치를 시스템에 연결하는 대중적인 방법으로 사용되는 버스 (모든 장치가 제어 버스에 데이터를 송신, 제어 버스로부터 데이터를 수신)

컨트롤러와 주변장치

• 주변장치 메인 보드에 있는 장치 또는 메인 보드에 꽂힌 카드에 있는 컨트롤러 칩에 의해 제어되는 장치
• 컨트롤러 하드웨어 장치를 제어하는 CPU와 비슷한 하나의 프로세서이지만, CPU는 시스템 전체를 제어한다는 점에서 차이가 있음
• 컨트롤러는 여러 종류의 버스(요즘은 ISA 버스, PCI 버스를 사용)를 통해 CPU 및 다른 컨트롤러들과 상호 연결되어 있음
• 모든 컨트롤러는 CPU가 제어할 수 있도록 제어 레지스터를 제공하며, CPU에서 실행되는 소프트웨어(=디바이스 드라이버)는 제어 레지스터를 읽고 쓸 수 있어야 함 (레지스터는 컨트롤러 종류에 따라 다름)

주소 공간

• CPU는 주변장치를 사용하기 위해 메인 메모리에 장치 관련 자료구조를 생성해야 되기 때문에, CPU와 메인 메모리를 연결하는 시스템 버스는 CPU와 다른 주변장치를 연결하는 버스와는 분리되어 있음
• 하드웨어 주변장치가 존재하고 있는 메모리 공간은 I/O 공간, 그 외 프로세스나 커널이 있는 메모리 공간은 시스템 메모리 공간
• CPU는 시스템 메모리 공간과 I/O 공간에 모두 직접적으로 접근 가능하나, 컨트롤러는 I/O 공간에만 접근 가능
  • 컨트롤러가 CPU의 도움을 받아 시스템 메모리 공간에 간접적으로 접근할 수는 있음

• I/O 공간을 메인 메모리에서 분리 할 수도 있고, 메인 메모리 내부의 공간 일부를 할당할 수도 있음

• 일반적으로 CPU는 시스템 메모리 공간과 I/O 공간을 접근하는데 다른 명령어를 사용
  • 예를 들어, "I/O 공간 0x3f0 주소에서 한 바이트를 읽어 레지스터 X에 저장하라"같은 명령이 있는 것인데, 이는 CPU가 I/O 공간에 있는 주변장치의 레지스터를 읽고 씀으로써, 하드웨어 주변장치를 제어하는 방법
• 컨트롤러가 메인 메모리에서 많은 양의 데이터를 읽어야 하거나, 메인 메모리로 많은 양의 데이터를 써야할 때, CPU의 도움 없이 직접 메모리 접근(Direct Memory Access, DMA)이라는 장치를 이용
  • 단, DMA 컨트롤러를 사용할 때 CPU의 엄격한 제어와 감시가 이루어짐 

타이머

• 모든 운영체제는 현재 시각을 알 필요가 있기 때문에, 요즘 PC들은 실시간 클럭(Real Time Clock, RTC)이라는 특수한 장치를 사용
• RTC는 자체 배터리를 가지고 있어 PC의 전원을 끄더라도 계속 동작하기 때문에 운영체제는 항상 정확한 날짜와 시간을 알 수 있음