Move Fast

본 글은 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단계 페이지 테이블을 지원, 그러나 리눅스 커널은 동일한 페이지 테이블 처리 코드를 사용