운영체제 11 - Paging [Memory Virtualization]

OS는 거의 모든 공간 문제를 해결할 때 두가지 방법이 있다. ↓

• Segmetation
  가변 크기의 조각들로 분할하는 것, 공간을 다양한 크기의 청크로 분할 할때 공간 자체가fragmented(단편화) 될 수 있고, 할당은 더 어려워진다.
• Paging
  프로세스의 주소 공간을 고정 크기의 단위로 나눈다. 고정 크기의 단위를 page라 부른다. 이에 맞게 Phsycal Memory를 page frame이라고 불리고 고정 크기의 슬롯의 배열이라고 생각한다.
  각각의 frame에 하나의 가상 메모리 페이지를 저장할 수 있다.

우리의 문제: Page를 사용하여 어떻게 Memory를 가상화할 수 있을까?

---

간단한 예제 및 개요

총 크기 64bite, 각 page는 16bite 페이지로 구성된 작은 주소 공간을 통해 이해해보자.
단위 이야기 1B = 8bit

Physical Memory는 위와 같이 고정 크기의 슬롯들로 구성되고 위 경우 8개의 page frame, 총 128bite로 이루어진 비현실적인으로 작은 physical memory다. 가상 주소 공간의 page들은 physical memory 전체에 분산 배치 되어있다. (18.1 그림이 phsical memory에 배치되어있다고 생각해보자)

paging은 이전 방식(segmention, base-bound pair)에 비해 많은 장점을 가지고 있다.
가장 중요한 개선은 유연성(flexibility)이다. paging을 사용하면 process의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다. - heap, stack이 어느 방향으로 커지는가, 어떻게 사용하는 가에 대해서 가정을 하지 않아도 된다.-
또 다른 장점은 free space 관리의 단순함이다. 예를 들어 OS가 우리의 작은 64bite 주소 공간을 8개의 8 page 물리 메모리에 배치하기를 원한다고 할 때, OS는 비어있는 네개의 page만 찾으면 된다. 아마 이를 위해 OS는 모든 비어 있는 page의 free space list를 유지하고 리시트의 첫 네 개의 페이지를 선택할 것이다. ← 이를 위해서 OS는 모든 비어 있는 페이지의 free list를 유지하고 list의 첫 4개 페이지를 선택할 것이다.

Page table
주소 공간의 각 가상 page에 대한 phsical memory 위치 기록을 위하여 os는 process마다 page table이란 자료구조를 유지한다.
주요 역할: 주소 공간의 가상 페이지 address translation 정보를 저장하는 것이다.
각 페이지가 저장된 physical memory가 어디인지 알려준다. 위에 예제에서는 4개의 항목을 가진다.
(vp 0→ pf 3), (vp 1→ pf 7), (vp2→pf 5), (vp 3→pf2)
vp = virtual page, pf = physical frame

page table은 process마다 존재한다는 사실을 숙지해야한다.

위에 예에서는 다른 프로세스를 실행해야한다면 os는 이 process를 위한 다른 page table이 필요하다. → 새 process의 virtual page는 다른 physical page에 존재하기 때문이다.(공유 page가 없다는 가정하에)

---

address translation

작은 주소 공간(64bite)을 가진 procee가 다음 메모리 접근을 수행한다고 가정하자.
movl <virtual address>, %eax 구체적으로 의 데이터를 eax 레지스터에 load하는데에 집중하자.
process가 생성한 가상 주소의 변화를 위해 먼저 가상 주소를 VPN(virtual page number)와 page내의 offset 2개의 구성 요소로 분할한다.

Virtual address → Virtual Page Number
→ offset

이 예에서는 address space가 64bite라 각 address space는 6bit가 필요하다 (2^6=64)

Va5가 최상위 비트이고 Va0은 최하위 비트이다. 우리는 page 크기를 알고 있어서 총 16bite 다음과 같이 표기한다.

VPN은 2비트를 가졌고, 나머지 비트(4페이지) offset은 우리가 원하는 bite의 위치를 나타낸다.
21을 이진 형식으로 변환하면 010101을 얻고 이 가상 주소를 검사하고 vpn과 offset으로 나눈다.

VPN에 해당하는 1을 Address Translation을 한다면 7 이진수 → 111을 얻는다.

VPN을 PFN으로 교체하여 교체하여 가상 주소를 변환한다. offset은 그대로다
최종 physical address는 1110101(117)이고 이곳이 load할 데이터가 저장된 정확한 위치다..

---

Page Table은 어디에 저장될까?

이전 segment talbe이나 base-bound pair에 비해서 Page table은 매우 커질수 있다.
예를들어 4KB 크기의 Page를 가지는 32bit 주소 공간을 생각해보면, 이 가상 주소는 20비트의 VPN과 12 bit의 offset으로 구성된다. 1KB Page 크기를 위해 10Bit가 필요하다. 여하튼 page table크기는 매우 크고 이를 MMU 안에 존재할 수가 없다. 그래서 OS가 있는 곳에 저장되고 점점 os가 차지하는 공간이 커지는 것이다.

---

Page Table에 무엇이 저장되어있을까?

🛎페이지 테이블은 가상주소를 물리 주소로 mapping하는데 사용되는 자료구조다.
가장 간단한 형태로 linear page table이 있다. PFN(Physical Table Number)을 찾기 위해 VPN(virtual page number)로 배열의 항목에 접근하고 그 항목의 PTE( Page table entry(항목) )를 검색한다.

각 PTE에는 심도 있는 이해가 필요한 비트가 존재한다.
Valid bit: 할당되지 않은 주소 공간 표현
Protection bit: 페이지가 읽기, 쓰기, 실행 중에 어느 것을 허용하는지 표현.
Present bit: 이 페이지가 물리 메모리 혹은 disk에 있는지 표현.
dirty bit: 메모리에 반입된 후 페이지가 변경되었는지 여부를 나타낸다.
reference bit: 때때로 페이지가 접근되었는지를 추적하기 위해 사용된다.

PAGE TABLE은 PAGE TABLE ENTRY로 구성된다.