[CSAPP] Virtual Memory -(2) Page Table, PTE, Page (Hit, Fault, Allocation)

리마인드

https://anggeum.tistory.com/entry/가상-메모리Virtual-Memory-1-메모리-관리-문제점-및-해결

 

가상 메모리는 기존 메모리 시스템에서 발생하는 문제점들을 해결하기 위해 나온 여러 해법들 중 하나이다.

 

기존 메모리 시스템에서 (1) 실행되는 프로그램이 실제 물리 메모리 크기보다 큰 경우 (2) 메모리 주소 공간에서의 Memory Hole 발생 (3) 메모리 영역 침범과 같은 문제점을 가지고 있었으며 가상 메모리에서는 이러한 문제점을 Mapping(사상)을 통해 해결하였다.

 

가상 메모리를 사용하는 이유로써는 프로그램 내 어떤 Option이나 기능들은 사용빈도가 제각각 다르며 프로그램 실행에 있어 모든 부분이 동시에 요구되지 않는다. 만약 프로그램을 일부 메모리에 올려놓고 실행할 수 있다면 많은 이점을 가져갈 수 있기 때문이다. 가상 메모리를 사용함으로써 보다 효율적인 자원 관리를 할 수 있는 이점을 제공받는다.

 

1. 캐싱 목적으로 사용되는 Virtual Memory

 

1-1. 가상 메모리(Virtual Memory)

 

이론적으로, 가상 메모리는 N개의 연속적인 바이트 단위 셀들로 이루어진 배열이 Virtual Memory(disk)에 저장된 것을 의미한다. 각 바이트는 고유한 가상 주소(virtual address)를 소유하며 인덱스 구조로 배열에 제공된다.

 

이러한 Virtual Memory(disk)에 저장된 배열은 메인메모리(DRAM)에 캐시로 사용되어 진다. 메모리 계층구조에서 사용되어지는 캐시 구조와 같이 Virtual Memory(disk)에 저장된 데이터(low-level)는 블록(Block) 단위로 파티셔닝되어 메인메모리(DRAM, upper-level)에 저장된다. 

 

가상 메모리 시스템에서는 고정 크기의 블록으로 나누게 되는데 이를 가상 페이지(Virtual Page(VP)) 라고 하며 페이지(Page)라는 단위를 사용한다. 마찬가지로 물리메모리에서는 Frame이라 불리는 같은 크기의 블록으로 나누어지게 되는데, 이를 물리 페이지(Physical Page(PP))라고 한다.

 

가상 페이지(Virtual Page)는 3가지 상태로 분류된다.

① Unallocated
VM 시스템으로부터 아직 할당(혹은 생성)되지 않은 Page들을 의미한다. 할당되지 않은 블록들은 어느 데이터와 연동되어 있지 않았기에 디스크 공간을 차지하지 않는다.

② Cached
VM 시스템으로부터 사용되며 물리메모리(Physical Memory, DRAM)에 할당된 페이지를 의미한다.

③ Uncached
VM 시스템으로부터 사용되지만, 아직 물리메모리(Physical Memory, DRAM)에 할당되지 않은 페이지를 의미한다.

 

Fig. VM System이 메인 메모리를 Cache로 사용

 

1-2. DRAM 캐시

(1) DRAM과 SRAM은 10배 이상 속도차가 존재한다.

(2) DRAM은 Disk와 100,000 배 정도의 속도차가 존재한다.

(3) DRAM ↔ Disk 에서 발생하는 Miss Penalty는 SRAM ↔ DRAM 에서 발생하는 Miss Penalty 보다 매우 크다.

(※ 여기서, SRAM은 CPU와 메인메모리 사이에 존재하는 캐시 메모리로 의미한다.)

 

1-3. DRAM Cache 구조 특징

 

첫째, 4KB ~ 2MB 큰 크기의 Page 크기

첫 byte에 접근하는데 매우 큰 비용(Expense)가 발생하기에 Virtual Page는 일반적으로 4KB ~ 2MB의 사이즈로 블록에 비해 큰 사이즈를 가진다.

 

둘째, Fully Associative 구조

Fully Associative 의 구조를 지녔으며, 각각의 가상 페이지는 어떤 물리 페이지와도 맵핑될 수 있으며, 어느(Any) Virtual Page는 어느(Any) Physical Page로 대체될 수 있다.

 

셋째,  DRAM을 위한 정교한 Replacement 알고리즘 

SRAM 캐시에 비해 DRAM 캐시는 Miss Penalty 가 매우 크기 때문에, SRAM 보다 더 정교한 Replacement 알고리즘을 사용한다.

 

---

2. 페이지 (Page)

 

2-1. 페이지 테이블(Page Table)

페이지 테이블(Page Table)은 가상 페이지와 물리 페이지 사이의 맵핑 정보를 담은 테이블로 메인 메모리의 커널 영역에 저장되는 자료 구조중 하나이다.

 

각 프로세스는 자신만의 페이지 테이블을 가지며, 문맥 전환(Context Switching)을 진행할 때 저장 및 복원해야 하는 Context 정보에도 해당 프로세스의 테이블 정보가 포함된다.

• 테이블 크기는 해당 프로세스의 페이지 개수에 비례한다.
• 메인메모리 커널 영역에 저장되는 자료구조이다.
• 각 프로세스는 자신만의 페이지 테이블을 보유하며 Context Switching을 수행할 때 저장 및 복원하는 Context 정보에도 해당 프로세스 페이지 테이블 정보가 포함된다.
• 실행중인 프로세스 테이블 시작 주소는 페이지 테이블 기준 레지스터(Page Table Origin Register)에 들어있다.

 

Fig. Page Table

 

2-2. Page Table Entry (PTE)

Page Table에 존재하며 Page가 물리 메모리의 어느 Frame에 위치하는지 알 수 있다.

 

물리 메모리에 맵핑되어 있는지에 대한 정보와 물리 메모리 주소로 맵핑되어 있지 않은 경우 디스크 어느 위치에 존재하는지에 대한 정보를 담고 있다.
(※ 만약 프로그램이 사용중에 있지 않아 할당되지 않은 가상페이지 경우 null 값을 저장한다.)

Fig. Page Table Entry

 

2-3. Page Hit

접근하고자 하는 가상 주소에 해당하는 PTE Valid bit가 1인 경우 가상 페이지가 물리 페이지에 맵핑되어 있음을 의미한다. 이를 Page Hit 혹은 DRAM 캐시 히트라고 부른다.

 

VM Page hit // VP 2 에서 hit

 

2-4. Page Fault

접근하려는 가상 주소에 해당하는 PTE Valied 비트가 0이고 그곳에 디스크의 특정 위치 정보가 저장되어 있다면, 가상 페이지가 물리 페이지에 맵핑되어 있지 않음을 의미한다. 이를 페이지 미스(Page Miss) 혹은 DRAM 캐시 미스라고 부른다.

 

Page Fault가 발생시 VM 에서 일어나는 과정

새로운 Virtual Page를 할당하는 과정

 

① CPU가 DRAM에서 캐싱 되어 있지 않은 VP 3을 참조한다.

 

② CPU는 Address translation을 통해 Page Table로부터 PTE 3를 읽어들이며, VP 3에서 Cache가 되어 있지 않은 것을 인지하게 되고 Page Fault Exception을 트리거한다.

 

③ Page Fault Exception은 커널내 존재하는 Page Fault Handler를 호출한다.

 

④ Page Fault Handler는 현재 메인 메모리에서 특정 물리 페이지(PP 3에 저장된 VP 4)를 선택하고 PTE에 VP 4는 더이상 메인 메모리에서 사용되지 않음으로 정보를 갱신한다. (Valid bit 1 → 0)

 

⑤ 커널은 VP 3을 PP 3으로 복제한 뒤 PTE 3을 갱신한다. (Valid bit 0 → 1)

 

⑥ Page Fault Handler는 Page Fault를 일으켰던 명령어 위치로 다시 리턴하여 해당 명령어를 재실행한다.

 

⑦ VP 3이 Main Memory(DRAM)에 정상적으로 캐싱되어 졌기에 정상적으로 Address Translation 과정을 걸칠 때 Page Hit가 발생할 것이고 메모리 참조를 진행한다.

 

2-5. Page Allocation

유저 프로세스로 실행되는 프로그램이 추가적으로 malloc 함수와 같이 힙 영역을 할당하려고 시도하면, 커널은 적절한 크기의 연속적인 가상 페이지들을 디스크에 할당하고 그것들에 해당하는 PTE들을 페이지 테이블에 새로 만들어 준다.

 

여기서 생성된 각각의 PTE Valid 비트는 0이며, 가상 페이지가 어느 위치에 할당되어 있는지에 대한 정보를 담게 된다. 페이지 테이블(Page Table)은 가상 페이지와 물리 페이지 사이의 맵핑 정보를 담은 테이블로 메인 메모리의 커널 영역에 저장되는 자료 구조중 하나이다.

 

각 프로세스는 자신만의 페이지 테이블을 가지며, 문맥 전환(Context Switching)을 진행할 때 저장 및 복원해야 하는 Context 정보에도 해당 프로세스의 테이블 정보가 포함된다.

 

---

Reference

• CSAPP - Computer Systems A Programmers Perspective 3rd Edition
• https://it-eldorado.tistory.com/52