Paging

Concept of paging

Ch6에서, Segmentation의 문제로 internal fragmentation이 발생한다는 것을 알았다.
fragment에 가변적인 공간을 할당했기에 이 문제가 발생했다.
Paging은, page라고 부르는 fixed-size의 address space로 process를 쪼갠다 (page는 virtual address space 공간임)
- Segmentation은 logical segment의 가변적인 크기로 할당
또한, Physical memory는 page frame이라고 부르는 # of pages로 split 됨.
Page나 page frame의 크기는 2의 거듭제곱 사이즈임 (보통 512B - 8KB )
이 때, virtual address를 physical address로 변환하기 위해 Page table이 process마다 필요함.

Page Overview

⇒ 그렇다면, 이러한 Address translation은 어떻게 이루어질까

Address Translation

Translating virtual addresses
- Virtual address는 2개의 part로 나누어진다
  1. Virtual Page Number(VPN) : page table의 index를 나타냄
  2. Offset
- 이후 Page table의 index가 **Page Frame Number(PFN)**을 결정한다.
- 이후 연결되는 physical address는 <PFN,offset>임
  - 보통, VPN의 수 ≥ PFN의 수
이때 Page table은 OS에 의해서 관리되며,
OS는 VPN을 PFN으로 mapping하게 된다( 일종의 level of indirection)
하나의 page당 하나의 **Page Table Entry(PTE)**를 virtual address space상에 갖게 된다. ( 하나의 row)

p: VPN(page table에서 몇 번째 row인지), f: PFN, d: offset

Page table의 크기

우선, Virtual address의 크기는 32bits이고, Physical address의 크기는 20bits이다.
Page의 size는 4KB ( 2^12)이고, PTE의 크기는 각 PTE당 4B이다.
이때 offset의 크기는 page의 size와 같을 수 밖에 없다. (12bits)
VPN의 크기는, Virtual address의 크기 % page의 size이므로 2^32%2^12 = 20bits이다
# of PTES는 2^20 = VPN의 수다.
따라서, Page table의 size는 (PTE의 size) x (# of PTE) = 4B X 2^20 = 4MB이다.
이해가 안가면 그냥 개 단순하게 생각해라. 어렵게 생각하면 이해가 안된다. 왜냐고? 내가 그랬거든

⇒ 그렇다면, 이렇게 용량이 큰 4MB의 Page table은 어디에 저장되는가?

Where are Page tables stored?

Page table의 크기는 크다.
- 32-bit의 address space가 4KB의 page와 VPN을 표현하기 위한 20bit가 합쳐져서 필요하다.
- 이때 page offset의 크기는 4KB인데, PTE의 수는 20bit이므로
- 위에서 설명한 대로 page table의 크기는 4MB이다.
이처럼 용량이 매우 크기 때문에, each process의 page table들은 main memory에 저장된다.
이 때 Hardware들은 page table base register을 이용해서 page table을 찾는다. ( xv6에선 CR3 )
그럼 만약 Context switch가 일어나면 어떡함? 주소 변환 정보 갱신해야하잖아
- page table base register 내용을 새롭게 scheduled된 process의 정보로 바꿈
- 원래 것의 page table base register 정보는 descheduled된 process의 PCB에 저장

Protection in Page table

각 Process마다 개인의 page table을 갖고 있어 virtual memory로만 P.M에 접근할 수 있으므로, 다른 process의 physical memory에 접근할 방법은 없다.
MMU register가 context switch 시 현재 process의 page table base address 주소를 바꿈
Page-level의 protection에서는, Valid / Invalid bit를 이용한다.
- PTE에 부여되는 bit로, Valid면 그 page가 process의 address space에 있고 사용 가능 Invalid면 그 page는 아직 할당되지 않았음을 의미한다.
Page가 유효한 경우, 더 상세한 Protection을 설정할 수 있음
- Read only, Read-write, execute-only 등

Page Table Entry ( PTE )

Accessed bit에서, 접근되면 1 (주소 변환으로 사용되었을 때)
Dirty bit에서, 쓰기 수행이 이루어졌으면 1
U/S bit에서, 주소 변환 시 현재 mode와 memory의 mode가 같을 때에만 연산을 수행함.

⇒ 그럼, 이런 Page들을 모두 main memory에 저장해놓고 사용하나? 그건 아님

Demand paging

OS는, main memory를 일종의 cache로 사용함으로서 process의 data를 가져온다. (필요한 page만 사용)
Page는, 사용되지 않으면 physical memory frame에서 evicted될 수 있음 (대신 disk에 저장)
그리고 disk에 옮겨놓았다가, 사용자가 요구하면 그제서야 다시 memory로 가져옴
이때 이렇게 page의 movement들은 process에게 transparent하도록 이루어짐 (지 data가 virtual memory에 있는지, disk에 있는지 process들은 알 수가 없음 )
page 접근하려다 접근하는 page가 없는 경우 다음과 같은 로직을 따른다.

App이 멈추고, Page fault handler가 작동하며 이후 P.M에서 page의 data를 page로 가져온 후, P.M에 있던 부분 zero로 만듬. 이후 page를 page table에 mapping한 후 다시 App이 작동
이러한 Demand paging의 장점
- I/O가 덜 필요하다
- 메모리가 덜 필요하다
- Response가 빠르다
- 더 많은 Process를 동시에 동작시킬 수 있다. (메모리 효율적으로 사용하기 때문)

⇒ 그렇다면, Page fault는 무엇일까

Page fault

Invalid PTE에 접근함으로서 CPU가 raise하는 Exception이다. 종류는 3가지가 있음
- Major page faults, Minor page faults, Invalid page faults
- Major / minor page fault는 demand paging 수행 과정에서 발생, Invalid page fault는 page 접근할 때 발생
Major page fault (필요한 page disk로부터 읽어와야하는 상태)
- Page는 Valid 하나, memory에 load되지 않은 상태 : OS가 어디 저장되어있는지 찾아야
- Disk I/O가 필요함
Minor page fault ( heap이나 stack에 할당할 때 )
- Page fault는 disk I/O 없이도 발생할 해결할 수 있는 문제
- Lazy allocation에서 주로 발생 : memory 할당 요청을 받았지만, 실제로는 사용할 때까지 메모리를 할당하지 않는 기법 (stack이나 heap에 대한 초기 접근 시 발생 가능)
- Prefetched page에 접근할때도 발생 가능 :해당 페이지를 프로세스 아직 “접근 가능”으로 표시하지 않았을 수도 있음.
Invalid Page fault (page 접근할 때)
- Segmentation violation이 일어날 때(Segmentation fault) : page를 사용할 수 없을 때 및 유효하지 않은 공간 접근 시 발생

Handling page Faults

처음엔 page table의 valid bit가 I였다가, Page fault handler 처리 후 V로 변함.

Paging : Pros

External fragmentation이 없음
Allocate 및 Release하는 속도가 빠름
- 해제는 list와 bitmap을 통해서 진행, 또 인접한 빈 공간과의 병합을 고려할 필요가 없음
- 할당은 연속적인 공간을 찾을 필요가 없기에 빠름
디스크로 메모리의 일부를 page out 하기 쉬움 (필요 없는 거 disk로 보내기 )
- 페이징 시스템에서 Page size는 disk block size의 배수로 설정된다 (4KB = 8 x disk 블록 크기임)
- Valid bit를 이용하여 paged-out 된 page를 쉽게 찾을 수 있음.
- page가 disk에 있을 때에도 process를 실행할 수 있음
페이지 보호 및 공유가 용이

Paging: Cons

External 대신 Internal fragmentation이 발생
Memory reference overhead가 발생할 수 있음
- Page table이 커 main memory에 저장해야하기 때문에, Memory에 접근 위한 주소 변환 때문에 또 Page table이 있는 main memory에 접근해야 해 overhead가 발생할 수 있음
- 이 Overhead에 대한 해결책으로, TLB ( 시험때 장단점 잘 파악하기)라는 hardware의 도움을 받음
Page table을 저장하기 위한 저장공간이 필요함 (이새끼 4MB라 용량 개큼)
- Process 별로 4MB가 할당되는데, 100개의 process가 있다고 하면 총 400MB를 page table에 사용하는거임
- 이거에 대한 solution으로, valid PTE만 저장하거나 Multilevel page-table이 나옴

⇒ 더 발전된 VM trick으로, Shared memory / Copy on write / Memory-mapped file 등이 있음

Shared Memory

Direct memory reference를 이용 share data에 접근할 수 있게 하는 방법
Implementation
- 같은 physical frame에 연결 PTE가 두 Process의 table에 존재함
- 하지만 각각의 PTE는 다른 protection value를 가질 수 있음
- Page가 Invalid해지면, 반드시 두 PTE를 invalid하게 바꿔야함.
각각의 Virtual address space에 shared memory를 매핑할 때,
- 두 virtual address space상의 주소는 다를 수 있음 : flexible하지만, shared memory 내부의 pointer가 invalid할 수도 있음.
  - Ex) p1의 VM의 PTE에는 shared memory가 A의 공간 기준 0x1000으로 mapping되어있는데, p2의 VM의 PTE에는 B의 공간 기준 0x2000로 mapping되어있을 수 있음. 이때 B에서 shared memory에 접근하기 위해 0x1000를 참조하면 error가 발생
- 두 virtual address space상 주소가 같으면 덜 flexible하지만 shared pointer가 valid한 장점이 있음
Example

int fd = shm_open(“/shm1”, O_CREAT | O_EXCL | O_RDWR, 0600);
- 이름이 /shm1 공유 메모리 객체 생성 or open →존재하지 않으면 생성, 이미 존재하면 error 반환, 읽기와 쓰기 허용→ 0600은 파일 권한으로 사용자에게만 읽기 쓰기 권한부여

Copy-on-Write

Write 연산이 생기기 전까진 용량 절약을 위해 서로 공유하다, write가 생기면 새로 하나 Copy
메모리 복사를 최대한 지연시키고, 실제로 필요할 때까지 복사 피함
구현
- page를 copy해 2개로 만드는 대신, shared mapping을 만들어 physical memory의 같은 page frame에 mapping한다.
- 이때 shared page는 read-only로 보호된다.
- data가 이 페이지에 쓰여지면, OS는 physical memory 상에 새로운 공간을 만들고 쓰려는 연산을 만들어낸 공간에 수행함.
fork()를 사용
data와 heap page 등등을 할당함.

Copy-on-Write during fork()

COW에서 두 프로세스가 모두 서로의 change를 보지 못한다.
- 모든 page를 copy하기 보단, parent 의 page를 shared mapping을으로 만들어 child address space에도 연결시킨다.
- shared page는 read-only로 보호된다. ( 보통 read가 usual하게 발생)
- 만약 쓰기 연산이 들어오면, Page fault exception 수행 (R.O인데 W연산 요청했기 떄문)
- ⇒ 이후 OS가 COW 상황 인지 후 PM에서 copy를 해준다.
- 이후 page table에있는 page mapping(R.O에서 R.O끔) 을 바꾸고, write instruction을 재시행한다.
chile process가 fork() 다음에 즉시 exec()을 하는 상황에서 효율적이다
- fork()시 parent의 data를 복사하지 않고 share하고 있다가 exec() 연산이 들어오면 shared space를 pointing하던 것을 새로운 프로그램으로 바꾸기만 하면 되니까 효율적임.

Syscall : mmap

Calling process의 새로운 mapping을 virtual address space에 만드는 것
addr : new mapping의 시작 주소 (page boundary 안에 있어야함)
- 만약 NULL이면 kernel이 임의로 주소 선택 : 아무거나 선택해주세요
- 프로그래머가 제공한 주소가 꼭 사용되리라는 보장은 없으며, 시스템의 메모리 상태와 다른 제약사항을 고려하여 최종 매핑 주소가 결정
length: mapping의 길이
prot : protection 정보 (PROT_EXEC, PROT_READ, PROT_WRITE, PROT_NONE)
flags:mapping flag ( Private, shared,anonymous 등)
fd, offset : file descriptor & file offset

Memory-Mapped File : Example

Process에게 memory 참조를 이용해 file I/O 수행을 가능학 한다.
- open(), read(), write(), close() 대신 사용 가능

open()함수를 통해 /bin/ls 파일을 readonly로 연다. 성공적으로 open하면 파일 디스크립터를 리턴한다.
이후 mmap()함수에 open을 통해 얻은 fd에 대해 첫 4096이트를 메모리에 매핑한다.
- 마지막 0 파일의 시작에서부터 매핑함을 의미
이후 printf()함수를 통해 매핑된 메모리의 처음 4바이트 16진수 형태 출력한다.

Memory-Mapped file

파일의 내용을 Virtual memory에 매핑 파일 I/O를 메모리 접근처 수행할 수 있게 해주는 기
implementation
- 처음엔, mapping된 지역은 모두 invalid로 표시되어 있다. ( 아직 load되지 않았음)
- OS는 메모리 영역 내 유효하지 않은 page에 접근하면 page fault를 발생시킨다.
- 이후 PTE에서 file data를 보유하고 있는 page frame에 virtual address를 mapping한다.
- <Virtual address base + n> 이 file에서의 offset + n에 대응된다. (파일의 offset + n 위치 참조 가능)
만약에 memory mapping된 지역에 wirte를 수행한다면,
- MAP_SHARED라면
  - OS는 page에 쓰고, physical memory에서 해제될 때에도 변경된 내용이 실제 파일에 반영된다.
  - 프로세스가 파일 데이터를 공유하 변경사항을 파일에 반영하길 원할 때 사용
- MAP_PRIVATE라면
  - OS는 private copy를 만들고 거기에 data를 write 한다. (a.k.a Copy-on-write)
  - FIle은 수정되지 않는다.

File I/O Comparisons

사실 I/O 접근 함수마다, 각각 메모리 접근과 같은 미묘한 차이가 있는데, 궁금하면 저 사진 지피티한테 설명해달라 해라.

Memory-Mapped File pros and cons

Pros
- pointer만을 사용해 file과 memory에 대한 접근을 가능하게 한다.
  - 즉 프로그래머는 파일 데이터를 마치 일반 메모리 데이터처럼 취급할 수 있다.
- 메모리 복사량 감소
  - 파일의 데이터를 메모리에 직접 매핑함으로 데이터를 읽고 쓰는데 발생하 오버헤드를 줄일 수 있다.
- 다중 프로세스 공유: 여러 프로세스가 동일 파일을 매핑하여 공유할 수 있다. (MAP_SHARED 옵션을 킬 시)
CONS
- Data 이동에 대한 제어가 부족하다 (Swapping 관련)
  - 프로세스는 운영체제가 언제 어떻게 데이터를 메모리와 디스크 사이에서 이동시키는지 모르므로, 세밀한 메모리 관리가 필요한 경우 이를 수동으로 조절하기 어려울 수 있다.
- 스트리밍 I/O와의 일반화 부족
  - 스트리밍 데이터는 연속적인 데이터 흐름을 다루기 때문에, 미리 정의된 파일 크기나 위치에 기반한 메모리 매핑 방식과는 맞지 않는다.
    - 1번 쓰고 지나가는건데, memory mapping을 하긴 애매한 상황이 발생할 수 있다.

슬기로운 CS생활