19. Paging and Page Tables

 

★★★★★★★

 

1. Contiguous memory allocation
   1. Fixed partition : Internal fragmentation
   2. Variable partition : External fragmentation
   3. Segmentation : External fragmentation
2. Paging 
   1. Physical Address를 non-contiguous하게 쪼개는 것
   2. 고정된 사이즈로 잘리며, “Frame” 으로 불린다.
   3. Logical Address는 “Page” 로 쪼개진다.
   4. Page 사이즈가 클수록 Internal fragmentation이 날 가능성이 크다.
3. Page Table
   1. OS 가 관리한다. 
   2. MMU 가 Translate한다.
   3. Virtual address는 Page Table을 통해 Physical address로 translate 된다.
   4. 각각의 프로세스는 자신만의 Page Table을 갖는다.
   5. 쓰레드들은 Address space를 공유하므로 Page Table을 공유한다.
   6. 프로세스 수준에서 정의된다.
   7. 프로세스A는 프로세스B의 Page Table을 읽을 수 없다.
4. Page Table Entry : Page Table의 각 행 
   1. VPN (Virtual Page Number)
   2. PFN (Physical Frame Number)
   3. Virtual Address = < VPN | Offset >
   4. Physical Address = < PFN | Offset >
   5. Page Table은 VPN을 PFN으로 translate 한다.
   6. Offset 부분은 그대로 가지고 온다.
5. Linear Page Table
   1. PTER로 읽어서 처음부터 차례대로 보자
6. Hierarchical Page Table
   1. Page Table도 Contiguous 하게 있을 필요가 없으므로 Page 단위로 쪼개자.
   2. Outer Page Table을 하나 더 두어서 Page Table을 가리키도록 한다.
   3. Virtual Address = < Outer page number | Page number | Offset >

 

 

 

---

 

프로세스의 Virtual address space를 일정한 크기의 Page 라는 것으로 쪼갠다.

컴퓨터는 Physical Memory를 Page와 같은 크기의 Page Frame 이라는 것으로 쪼갠다.

그리고 얘내들을 운영체제가 Page를 Page Frame으로 매핑해서 메모리를 allocate하는 방식을 Paging 이라고 한다.

Page Number는 Virtual Page Number로 Page Table을 통해 Translate가 되고,

Page Table은 운영체제가 관리한다. Translate는 MMU가 한다.

Page Table은 Page Table Entry로 구성되어 있다.

Page Table Entry는 V,R,M,Prot, PFN의 구조를 갖는다.

 

---

---

 

 

페이지 사이즈 4KB 정도 된다.

페이지가 클수록 Internal fragmentation이 날 가능성이 크다.

---

 

 

매핑해줄 때 표를 보고 매핑을 해준다.

그 표가 Page Table 이다.

 

각각의 프로세스는 자신만의 Page Table 가지고 있다.

쓰레드들은 Address Space 를 공유한다.

그러니까 쓰레드들은 Page Table 을 공유한다.

따라서 프로세스 수준에서 정의가 되는 표이다.

---

 

각각의 Low (행)를 Page Table Entry 라고 한다.

 

Virtual address space는 Page Table을 통해서 Physical Memory로 매핑이 (translate) 되고
Page Table 자체는 Page Table Enrty로 구성되어 있고,
각각의 Page Table Entry는 해당하는 Entry가 커버하는 Virtual address 나 Physical Memory의 상태를 기록하는 형태로 구성되어 있다. 

프로세스들은 Virtual address를 뿜어내는데 MMU가 Physical Address 로 Translate 한다.

 

Page Table은 운영체제가 관리 한다. 만들고 고쳐주는 것

실제로 Address를 Translate하거나 읽어가는 일은 MMU가 한다.

---

특정위치를 가리키는 것을 Physical Frame Number 라고 부르고, Physical Page Number라고 한다.

Virtual Page Number을 Physical Page Number 몇번에 저장할 것이냐?

 

10 | 40

Virtual Address = < Virtual Page Number | Offset >

Page Number는 어디론가 translate 해서 가고

옵셋은 유지가 되는 것이니 계속 가져가면 되는 것이다. (노란선)

 

VPN을 Page Table을 참고하여 PFN 으로 바꿔준다. 

 

Physical Address = < Page Frame Number | Offset >

Page Table의 역할 : VPN 을 PFN으로 Translate 

---

 

 

어떤 컴퓨터가 뿜어내는, 프로세스가 뿜어내는 Virtual Address는

Paging을 쓴다고 했을 때, 이 중에 VPN 파트가 있을 것이고, 남아있는 Offset 부분이 있을 것이다.

VPN을 PPN으로 translate 해야한다. 이 때 Page Table에 가서 읽어야 한다.

V번째로 가면 PPN이 있고 그것을 P에 넣고 Offset 부분은 그대로 가지고 오면 Physical Address가 된다.

 

---

 

 

Virtual Address = 32 bit = 2^32 → 8자리 수

32 - 12 = 20 bit

Physical Address = 20 bit = 2^20 → 5자리 수

20 - 12 = 8 bit

Page Size : 4KB = 2^2 x 2^10 = 12 bit = 2^12 → 3자리 수

VPN = 8자리 - 3자리 → 5자리 수

PFN = 5자리 - 2자리 → 3자리 수 

 

 

---

가상 메모리

 1) 가상 메모리의 정의

  - 메모리로서 실제 존재하지는 않지만, 사용자에게 메모리로서의 역할을 하는 메모리

 2) 가상 메모리의 basic idea

   - 프로세스가 수행되기 위해서 프로그램의 모든 부분이 실제 물리 메모리에 있을 필요가 없다.
   - 현재 실행되고 있는 코드 부분만이 실제 물리 메모리에 있으면 프로세스는 실행할 수 있다.

 3) 가상 메모리와 물리 메모리의 관계를 저장해야하며, 이를 위한 기법(mechanism)이 필요하다.
   - 페이지 테이블 "page table"

 

4. 페이징 (Paging)

1) 페이징 개요 및 특징
  (1) 페이지 (Page)는, Virtual Address Space를 고정된 크기로 나누었을 때, 하나의 블록을 의미한다.
   - 보통 하나의 page 크기는 4KB이다.
   - 주소 공간을 동일한 크기인 페이지(page)로 나누어 관리한다.

cf. 프레임 (Frame)은, Physical Address Space를 고정된 크기로 나누었을 때, 하나의 블록을 의미한다.
 - 각각의 프레임 크기와 페이지 크기는 같다.

 (2) 페이지가 하나의 프레임을 할당 받으면, 물리 메모리에 위치하게 된다. 
   - 프레임을 할당 받지 못한 페이지들은 외부 저장장치 (Backing store)에 저장된다. 
   - Backing store도 페이지, 프레임과 같은 크기로 나누어져 있다.

 2) 페이지 번호 (page number)와 페이지 오프셋 (page offset)

  - CPU가 관리하는 모든 주소는 두 부분으로 나뉜다.
  (1) 페이지 번호 (page number) p는 각 프로세스가 가진 페이지 각각에 부여된 번호다.
  (2) 페이지 오프셋 (page offset) d는 각 페이지의 내부 주소를 가리킨다.

* 128MB의 물리 메모리를 4KB 단위로 페이징 하려고 하면, 몇 개의 frame이 필요 한가? 
 - 128 MB = 2^7 * 2^20 = 2^27
 - 4KB = 2^2 * 2^10 = 2^12
 - 2^27 / 2^12 = 2^15 = 32 K
 - 즉, 32K 개의 프레임이 필요하다.

* CPU의 주소 버스가 32 bit인 시스템에서 4GB의 logical address를 페이징 하려고 하면, 총 몇 개의 page가 필요 한가? 
 - 페이지 크기는 4KB로 가정한다.
 - 주소 공간의 크기는 2^32 바이트 = 4GB 이다. 
 - 전체 주소 공간을 페이지 크기로 나누면,  4GB / 4KB = 100,000 
 - 즉, 전체 페이지의 개수가 10만 개가 된다.

* page의 크기가 4KB일 때, 한 페이지의 메모리를 access하기 위한 주소 bit는 몇 비트인가?
 - 12 비트

 3) 페이지 테이블 (page table)

  (1) 페이지 테이블 개요 및 특징
   - 각 프로세스의 페이지 정보를 저장한다.
   - 프로세스마다 하나의 페이지 테이블을 가지며, 프로세스가 만들어질 때 페이지 테이블도 만들어진다.
   -  페이지 번호 (page number) p로 인덱스하며, 인덱스를 하고 나면 해당 페이지에 할당된 물리 메모리(프레임)의 시작 주소 f를 알 수 있다.
   - 이 시작 주소 f와 페이지 오프셋 d를 결합하여 원하는 데이터가 있는 물리 메모리 주소를 알 수 있다.

  (2) 페이지 테이블의 구현 
   - 페이지 테이블은 물리 메모리에 위치한다.
   - 페이지 테이블 기준 레지스터 (PTBR: Page-table base register)가 물리 메모리 내의 페이지 테이블을 가리킨다.
   => 위 그림에서, 페이지 테이블의 시작 주소를 가리킨다. 
   => PTBR은 프로세스의 개수 만큼 (페이지 테이블의 개수 만큼) 있어야 할 것 같지만, 실제로는 코어 하나당 하나씩 가지며, 컨텍스트 스위칭을 할 때 PTBR의 내용을 바꾸어주어 페이지 테이블에 접근할 수 있도록 한다.
   - 페이지 테이블 길이 레지스터 (PTLR: Page-table length register)가 페이지 테이블의 사이즈를 나타낸다. 

 

4) 페이지 테이블 엔트리 (Page Table Entry, PTE)

  - PTE란 페이지 테이블에 들어 있는 레코드 하나를 의미한다.
  - PTE의 각 필드는 다음과 같다.
  (1) Page base address 
   => 해당 페이지에 할당된 프레임의 시작 주소이며, 이를 통해 물리 메모리에 접근할 수 있다.
  (2) Flag bits 
   => Accessed bit를 통해 페이지에 대한 접근이 있었는지 표시한다.
   => Dirty bit를 통해 페이지 내용의 변경이 있었는지 표시한다.
   => Present bit를 통해 현재 페이지에 할당된 프레임이 있는지 표시한다.
   => Read/Write bit를 통해 읽기/쓰기에 대한 권한을 표시한다.
  - 그 외 구성에 따라 여러 가지 내용들이 포함될 수 있다.

 

---

---

 

 

---

프로세스A는 프로세스B의 Page Table을 읽을 수 없다.

다른 프로세스를 참조하기가 쉽지 않다.

 

---

그냥 PTER 로 읽어서 처음부터 차례대로 보자.

 

---

 

Page Table을 첫 시작 위치를 PTBR이 가리킨다.

 

32 bit Address space 를 4KB page로 관리를 한다고 하자. 각각의 PTE가 4 byte 라고 가정해보자.

2^32 / 2^12 = 2^20

2^20개 만큼의 PTE가 있는 것이고, 각각의 PTE는 4 byte 이다.

2^20 x 4 = 4MB 

한 프로세스마다 4MB의 Page Table을 갖는다.

 

---

Linear하게 쓰지 않고 쪼개서 쓴다.

 

전체 Page Table을 작은 Page 크기로 쪼갠 다음에

그중에서 내가 사용하는 부분만 매핑해서 사용하고,

내가 사용하지 않는 부분은 비워두는 방식을 forward-mapped page table 이라고 한다.

 

Virtual Address Space는 Contiguous할 필요가 없었다.

마찬가지로 Page Table도 Page 단위로 쪼개서 놓음으로써 Contiguous 하게 있을 필요가 없어진다. 

Page Table도 쪼개는 방식 >> Hierarchical Page Table

 

---

 

 

---

Virtual address 는 원래  < VPN + Offset > 으로 구성되었다.

Hierarchical Page Table을 이용하면 < Outer page number + Page number + Offset > 으로 구성된다.

PTBR이 가리키는 것은 Outer page 의 시작위치를 가리키게 된다.

 

---

Outer Page table을 하나 더 두어서, Page Table을 가리키도록 한다.

 

 

원래 2^32 / 2^12 = 2^20 므로

2^20개의 PTE가 필요하다.

이걸 통째로 갖다 놓으면 Linear Page Table이 된다.

 

이것을 Page 크기인 4 KB로 다시 쪼갠다. 

PTE 하나하나는 각각 4 byte 이다.

4 KB / 4 byte = 1K = 2^10 개의 PTE가 들어갈 수 있다.

 

하나의 Page에는 2^10개 만큼의 PTE를 커버할 수 있으니까 

2^20 / 2^10 = 2^10

따라서 2^10 개 만큼의 Page가 필요하다.

그래서 Page의 크기는 10 bit가 된다.

 

32 bit = 10 bit(Outer page) + 10 bit(page) + 12 bit (Offset)

이처럼 구현하면, Page Table의 크기는 4MB에서 16KB로 줄어든다. 

 

---

 

 

 

---

 

 

---

 

---

 

 

---

 

 

---

 

 

---

 

 

---

 

 

---

 

 

---

 

 

---

 

 

---