[OSTEP] Virtualization) 18. Introduction to Paging

[OSTEP] 18. Introduction to Paging

이 포스팅은 $<$Operating Systems: Three Easy Pieces$>$, Remzi H. Arpaci-Dusseau & Andrea C. Arpaci-Dusseau을 읽고 개인 학습용으로 정리한 글입니다.

CH 21. 페이징

운영체제의 공간 관리 문제 해결 방법

• 공간을 가변 크기의 조각들로 분할하는 것
  -> 세그멘테이션(segmentation)
  -> 단점: 외부 단편화(external fragmentation) 발생

• 공간을 동일한 크기의 조각으로 분할하는 것
  -> 페이징(paging)

페이징

• 페이지(page): 프로세스의 주소 공간을 나눈 고정 크기의 단위

• 페이지 프레임(page frame): 페이지에 상응하여 물리 메모리 공간을 나눈 고정 크기의 단위
  -> 물리 메모리를 고정 크기의 슬롯의 배열로 생각
  -> 물리 메모리 프레임 각각은 하나의 가상 메모리 페이지를 저장

1. 간단한 예제 및 개요

• 총 64 바이트의 4개의 16바이트 페이지로 구성된 주소 공간

• 총 128 바이트의 8개의 16바이트 페이지 프레임으로 구성된 물리 메모리
  -> 가상 주소 공간의 페이지들 물리 메모리 전체에 분산되어 저장됨
  -> 운영체제가 자기자신을 위해 물리 메모리의 일부를 사용함

장점

• 유연성
  -> 프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념 지원
  (ex. 힙과 스택이 어느 방향으로 커지는가, 어떻게 사용되는가에 상관 X)

• 단순함
  -> 운영체제는 모든 비어있는 프레임의 빈공간 리스트를 유지
  -> 비어있는 프레임만 찾으며 주소 공간을 물리 메모리에 배치 가능

페이지 테이블

• 페이지 테이블(page table): 주소 공간의 각 가상 페이지에 대한 물리 메모리 위치 기록
  -> 가상 페이지 주소 변환 정보 저장 역할

• 운영체제가 프로세스마다 각각의 페이지 테이블 유지

주소 변환

• 가상 주소를 가상 페이지 번호(virtual page number, VPN)와 페이지 내의 오프셋으로 분할

• 가상 주소 공간의 크기 64Byte = 2^6Byte
  -> 가상 주소 6비트
  

• 가상 주소 내 페이지 개수 2^6 / 2^4 = 2^2
  -> 가상 페이지 번호 2비트
  -> 가상 주소의 최상위 두 비트 사용

• 페이지 크기 16Byte = 2^4Byte
  -> 페이지 내 오프셋 4비트

• 예. 가상 주소 21 (010101)
  -> 가상 페이지 번호 1(01), 오프셋 5(0101)
  -> 가상 주소 공간의 1번째 페이지의 5번째 바이트 항목에 해당하는 가상 주소

• 페이지 테이블에 (VP 1 -> PF 7)이 저장되어 있는 경우
  -> 물리 페이지 번호(Physical frame number, PFN) 7(111)
  -> VPN을 PFN으로 교체하여 가상 주소를 물리 주소로 변환할 수 있다
  -> 오프셋은 동일하다

2. 페이지 테이블은 어디에 저장되는가

페이지 테이블은 매우 커질 수 있다

• 4KB 크기의 페이지를 가지는 전형적인 32비트 주소 공간

• 페이지의 크기 4KB = 4 10^3 = 2^2 2^10 = 2^12 Bytes
  -> 오프셋 12비트

• 주소 공간 내 페이지 개수 2^32 / 2^12 = 2^20
  -> VPN 20비트

• 페이지 테이블 항목(page table entry, PTE)마다 4바이트 필요하다고 가정
  -> 페이지 테이블 저장하기 위해 2^20 * 4 Bytes = 4194304 = 4MB 메모리 필요

• 프로세스가 100개 실행중인 경우
  -> 주소 변환을 위해 운영체제가 400MB의 메모리를 필요하게 된다

메모리에 저장

• 현재 실행중인 프로세스의 페이지 테이블 매우 클 수 있음
  -> MMU안에 유지하지 않는다

• 페이지 테이블은 운영체제가 관리하는 무릴 메모리에 상주한다고 가정한다

3. 페이지 테이블에는 실제 무엇이 있는가

• 선형 페이지 테이블(linear page table): 페이지 테이블의 가장 간단한 형태
  -> 원하는 PFN을 찾기 위해 VPN으로 배열 항목에 접근 & 그 항목의 PTE 검색

Valid bit

• 특정 변환의 유효 여부를 나타냄
  -> 사용 중인 코드,힙,스택의 공간은 유효(valid)
  -> 그 사이의 모든 미사용 공간은 무효(invalid)

• 프로세스가 invalid한 메모리를 접근하려고 하면 운영체제에 트랩을 발생시킴

• valid bit은 주소 공간의 미사용 페이지들에게 물리 프레임을 할당할 필요를 없앰
  -> 대량의 메모리 절약

protection bit

• 페이지가 읽을 수 있는지, 쓸 수 있는지, 실행될 수 있는지를 표시

• protection bit가 허용하지 않는 방식으로 페이지에 접근하려고 하면 운영체제에 트랩을 발생시킴

present bit

• 이 페이지가 물리 메모리에 있는지 디스크에 있는지(swap-out된 경우) 가리킴

dirty bit

• 메모리에 반입된 후 페이지가 변경되었는지 여부 나타냄

reference bit (accessed bit)

• 페이지가 접근되었는지 추적하기 위해 사용
• 어떤 페이지가 인기가 있는지 결정하여 메모리에 유지되어야 하는 페이지를 결정하는 데에도 도움

x86의 페이지 테이블 항목(PTE)

4. 페이징: 너무 느림

5. 메모리 트레이스