08. paging

Paging

Review: Segmentation

• paging은 segmentation의 한계를 해결하려고 나온다.
• segmentation에서는 code, heap, stack처럼 논리적으로 의미 있는 segment를 따로 관리할 수 있다는 장점이 있었다.
• 하지만 각 segment가 physical memory에 연속적으로(contiguously) 들어가야 해서 external fragmentation이 생긴다.
• 슬라이드 review 예시에서는 14-bit virtual address에서 상위 2비트가 segment를 나타내고, 0 → Code, 1 → Heap, 2 → Stack으로 구분한다. 즉 segmentation은 주소 공간을 “논리 조각”으로 나누는 방식이다.

Concept of Paging

• paging의 핵심은 주소 공간을 고정 크기 단위로 자르는 것이다.
• process의 virtual address space는 page로 나누고, physical memory는 같은 크기의 page frame으로 나눈다.
• page나 frame의 크기는 보통 2의 거듭제곱이다. 슬라이드에는 대략 512B ~ 8KB 범위가 적혀 있다.
• 그리고 각 process는 자기 page table을 가지고, 이 page table이 virtual page를 어느 physical frame에 둘지 알려 준다.
• segmentation과의 가장 큰 차이는 이거다.
  • segmentation
    • code, heap, stack처럼 가변 크기의 논리 단위
  • paging
    • 의미와 상관없이 고정 크기 page 단위
• 그래서 paging은 external fragmentation을 크게 줄인다.

Paging Overview

• paging에서는 process의 page들이 physical memory에 흩어져서 들어갈 수 있다.
• 예를 들어 Process A의 Page 0, Page 1, Page 2, Page 3이 각각 전혀 다른 frame에 들어가도 된다.
• 즉 process 전체가 physical memory에서 한 덩어리일 필요가 없다.
• 이게 segmentation/base-and-bounds와 가장 다른 점이다. contiguous한 큰 공간을 찾을 필요가 없기 때문이다.

Segmentation vs. Paging

• segmentation은 주소 공간의 논리 구조를 잘 반영한다.
  • code
  • data
  • heap
  • stack
• 하지만 각 segment가 physical memory에 연속적으로 있어야 해서 external fragmentation이 생긴다.
• paging은 논리 구조를 그대로 따르지는 않지만, virtual address space를 균일한 page들로 잘라서 각 page를 아무 frame에나 둘 수 있다.
• 그래서 allocation/free가 훨씬 단순해진다.

Address Translation

• paging에서 virtual address는 두 부분으로 나뉜다.

• VPN은 Virtual Page Number
• Offset은 page 내부 위치다.
• page table은 VPN을 보고 대응되는 PFN을 찾는다.
• 그러면 physical address는 다음처럼 된다.

• 즉, offset은 그대로 두고, page 번호만 physical frame 번호로 바꾸는 방식이다.
• 슬라이드 표현을 그대로 따르면
  • VPN은 page table의 index다.
  • page table이 PFN을 결정한다.
  • 보통 |VPN| >= |PFN|이다.

Address Translation Example

• 슬라이드 예시는 다음 조건을 준다.
  • virtual address: 32 bits
  • physical address: 20 bits
  • page size: 4KB
  • PTE 크기: 4 bytes
• page size가 4KB이므로 offset 비트 수는

• 따라서 VPN 비트 수는

• virtual address space 전체 page 수, 즉 PTE 개수는

• page table 크기는

• 즉 프로세스 하나당 page table만 4MB가 될 수 있다는 뜻이다. 이게 뒤에서 page table overhead 문제로 이어진다.

Where Are Page Tables Stored?

• page table은 생각보다 크다.
• 위 예시처럼 32-bit address space, 4KB page, 4-byte PTE면 process 하나당 4MB다.
• 프로세스가 아주 많아지면 page table만으로도 엄청난 메모리를 잡아먹는다. 슬라이드도 “10,000 processes라면?” 같은 질문을 던진다.
• page table은 보통 memory에 저장된다.
• hardware는 page table base register를 통해 현재 process의 page table 위치를 찾는다.
  • x86에서는 CR3
• context switch가 일어나면
  • 새 process의 page table base register 값으로 바꾸고
  • 이전 process의 값은 PCB에 저장한다.

Protection

• paging에서는 process마다 separate page table을 가진다.
• 따라서 다른 process의 physical memory를 직접 접근할 방법이 없다.
• context switch 때 MMU register가 현재 process의 page table base를 가리키도록 바뀌므로, 현재 process 관점에서만 translation이 일어난다.
• protection은 PTE마다 protection bits를 붙여서 구현한다.
• 대표적으로
  • Valid / Invalid bit
  • Read-only / Read-write / Execute-only
  • User / Supervisor
    같은 식으로 page 단위 권한을 줄 수 있다.

Page Table Entry (PTE)

• PTE에는 여러 정보가 들어간다.
  • PFN
    • page frame number
  • P
    • present 또는 valid
    • 이 page가 physical memory에 있는지
  • R/W
    • read/write bit
  • U/S
    • user / supervisor
    • user-mode 접근 허용인지, kernel-only인지
  • A
    • accessed bit
    • 최근 접근된 적 있는지
  • D
    • dirty bit
    • 수정된 적 있는지
• 여기서 A와 D는 뒤에서 replacement policy나 eviction 때 중요해진다.
  • A
    • 최근에 사용되었는지 판단하는 힌트
  • D
    • 내보낼 때 disk에 다시 써야 하는지 판단하는 힌트

Demand Paging

• OS는 main memory를 모든 process 데이터의 page cache처럼 쓴다.
• 즉 page를 정말 필요할 때만 physical memory로 가져온다.
• 어떤 page는 메모리에 없다가, 접근 시점에 처음 들어올 수도 있다.
• 반대로 메모리에 있던 page도 나중에는 frame에서 쫓겨날 수 있다.
• dirty page만 disk에 다시 쓰면 된다.
• 이러한 movement는 process 입장에서는 투명해야 한다.
• 슬라이드가 드는 장점은 다음과 같다.
  • Less I/O needed
  • Less memory needed
  • Faster response
  • More processes

Page Fault

• page fault는 CPU가 invalid PTE를 접근했을 때 발생하는 exception이다.
• 슬라이드는 page fault를 세 가지로 나눈다.
  • Major page fault
    • page는 유효하지만 아직 physical memory에 없다.
    • OS는 그 내용이 disk 어디 있는지 알고 있고, disk I/O가 필요하다.
  • Minor page fault
    • disk I/O 없이 해결 가능하다.
    • lazy allocation으로 아직 실제 page를 안 만들었거나, prefetched page를 쓸 수 있는 경우 등이다.
  • Invalid page fault
    • 애초에 그 page가 process address space 안에 없다.
    • 즉 segmentation violation이다.

Handling Page Faults

• page fault 처리 흐름은 대략 다음과 같다.
  • CPU가 memory reference를 시도한다.
  • page fault trap이 발생한다.
  • OS가 그 page가 backing store에 있는지 확인한다.
  • free frame을 하나 확보한다.
  • disk에서 해당 page를 memory로 가져온다.
  • PTE를 갱신한다.
  • 원래 instruction을 다시 시작한다.
• 중요한 점은 page fault가 나도 그것이 항상 “프로그램 에러”는 아니라는 것이다.
• demand paging에서는 정상적인 page-in 과정의 일부일 수 있다.

Paging: Pros

• No external fragmentation
  • fixed-size frame에 아무 page나 넣을 수 있으므로 contiguous free space를 찾을 필요가 없다.
• Fast to allocate and free
  • free frame list나 bitmap만 있으면 된다.
  • contiguous free space를 찾거나, 인접 영역을 coalesce할 필요가 없다.
• Easy to page out
  • page 단위로 disk에 내보내기 쉽다.
  • valid bit 등으로 paged-out page 접근을 감지할 수 있다.
• Easy to protect and share pages
  • page 단위 protection
  • page 단위 sharing이 자연스럽다.

Paging: Cons

• Internal fragmentation
  • page는 고정 크기라 마지막 page 내부에 남는 공간이 낭비될 수 있다.
  • page size가 커질수록 wasted memory가 커진다.
• Memory reference overhead
  • 한 번의 memory access마다 page table lookup이 추가될 수 있다.
  • 그래서 translation이 느려진다.
  • 이 문제를 해결하려고 뒤 단원에서 TLB를 배운다.
• Page table storage overhead
  • virtual address space의 모든 page마다 PTE가 필요하다.
  • 32-bit address space, 4KB page size, 4B/PTE면 page table 하나가 4MB다.
  • process가 많으면 page table memory가 엄청 커진다.

Advanced VM Functionality

• paging 위에서 더 고급 기능들을 만들 수 있다.
• 슬라이드가 대표적으로 드는 것은
  • Shared memory
  • Copy on write
  • Memory-mapped files
    다.

Shared Memory: Example

• shared memory는 관련 없는 process끼리도 직접 메모리 참조로 데이터를 공유하게 해 준다.
• 슬라이드 예시에서는
  • shm_open()으로 shared memory object를 만들고
  • ftruncate()로 크기를 4096 byte로 잡고
  • mmap()으로 MAP_SHARED mapping을 만든 뒤
  • 정수 배열처럼 p[i] = i를 수행한다.

#include <sys/mman.h>
#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>

int main(int argc, char *argv[]) {
	int fd = shm_open("/shm1", O_CREAT | O_EXCL | O_RDWR, 0600);
	ftruncate(fd, 4096);
	int *p = (int *) mmap(0, 4096, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);

	for (int i = 0; i < 1024; i++) p[i] = i;

	close(fd);
}

Shared Memory

• shared memory 구현의 핵심은 간단하다.
• 서로 다른 process의 page table에서 같은 physical frame을 가리키게 만들면 된다.
• 즉 두 process의 PTE가 같은 PFN을 갖도록 하면 된다.
• 추가로 알아둘 점
  • 각 process의 PTE는 서로 다른 protection 값을 가질 수도 있다.
  • page가 invalid해질 때는 관련된 모든 PTE를 함께 갱신해야 한다.
• virtual address space에 shared memory를 매핑할 때는 두 방식이 있다.
  • 다른 주소에 매핑
    • 더 유연하다.
    • address conflict가 덜하다.
    • 하지만 shared region 안의 pointer는 깨질 수 있다.
  • 같은 주소에 매핑
    • 덜 유연하다.
    • 하지만 shared pointer가 그대로 유효하다.

Copy-on-Write

• copy-on-write는 “실제로 write가 일어날 때까지 복사를 미루는” 최적화다.
• 핵심은 다음과 같다.
  • 처음에는 shared mapping처럼 같은 physical page를 함께 쓴다.
  • 다만 page를 read-only로 둔다.
  • 누가 write하려고 하면 protection fault가 난다.
  • 그 순간 OS가 새 physical memory를 만들어 진짜 복사를 하고, 그 process 쪽 mapping만 바꾼다.
• 즉 copy-on-write는
  • read할 때는 공유
  • write할 때만 복사
    라는 전략이다.

Copy-on-Write during fork()

• fork() 직후 부모와 자식의 address space는 거의 동일하다.
• 이걸 처음부터 전부 복사하면 너무 비싸다.
• 그래서 보통은 부모와 자식이 read-only로 page를 공유하게 두고, 실제 write가 일어나는 page만 복사한다.
• 특히 fork() 직후 곧바로 exec()를 하는 경우, 대부분의 page는 실제로 write 없이 버려지므로 copy-on-write가 매우 효율적이다.

System calls: mmap

• mmap()은 process의 virtual address space 안에 새 mapping을 만드는 system call이다.
• paging 위에서 shared/private mapping, file mapping, anonymous mapping 같은 것들을 다 구현할 수 있다.
• 즉 paging은 단순한 translation mechanism일 뿐 아니라, user-visible API인 mmap()의 기반이기도 하다.

Shared vs. Private Mapping

• 여러 process가 같은 backing store를 map할 수 있다.
• 이때 두 가지 의미가 있다.
  • Shared
    • 한 process의 수정이 다른 process에도 보인다.
  • Private
    • 수정은 다른 process에 보이지 않는다.
    • 보통 copy-on-write로 구현된다.

Memory-Mapped File: Example

• memory-mapped file은 file을 virtual memory region에 연결하는 기능이다.
• 슬라이드 예시는 /bin/ls를 읽기 전용으로 map한 뒤, 첫 4 byte를 그냥 pointer dereference로 출력한다.
• 즉 read() 대신 ordinary memory load로 file 내용을 읽는 것이다.

#include <sys/mman.h>
#include <stdio.h>
#include <unistd.h>

int main(int argc, char *argv[]) {
	int fd = open("/bin/ls", O_RDONLY);
	char *p = (char *) mmap(0, 4096, PROT_READ, MAP_SHARED, fd, 0);

	printf("0x%02x 0x%02x 0x%02x 0x%02x\n",
		*p, *(p+1), *(p+2), *(p+3));

	close(fd);
}

Memory-Mapped File

• memory-mapped file은 file region을 virtual address space의 어떤 page들과 대응시킨다.
• 그 결과 process는 file 내용을 포인터처럼 접근할 수 있다.
• file-backed page는 처음에는 not-present일 수 있고, 접근 시 page fault가 나면 OS가 file에서 읽어 와서 page를 채운다.
• 즉 mmap() + paging + page fault handling이 합쳐져서 작동하는 기능이다.

File I/O Comparisons

• 슬라이드는 ordinary file I/O와 memory-mapped file I/O를 비교한다.

• read() 기반 방식은

  • kernel buffer
  • user buffer
  • 경우에 따라 C library buffer
    사이에서 memcpy가 여러 번 일어날 수 있다.

• 반면 mmap()은 file-backed page를 주소 공간에 바로 연결하므로, 불필요한 copying을 줄일 수 있다.

Summary: Memory-Mapped File

• 장점
  • 파일과 메모리를 같은 방식으로 접근할 수 있다.
    • 그냥 포인터를 쓰면 된다.
  • memory copying이 적다.
  • 여러 process가 같은 file을 map하면 page를 shared할 수 있다.
• 단점
  • process가 data movement를 직접 제어하기는 어렵다.
  • pipe, socket 같은 streamed I/O에는 일반화되지 않는다.

마지막 정리

• 이 단원은 segmentation의 external fragmentation 문제를 해결하기 위해 paging을 도입한다.

• paging의 핵심은 다음 네 줄로 요약할 수 있다.

  • virtual address space를 fixed-sized page로 나눈다.
  • physical memory를 fixed-sized frame으로 나눈다.
  • page table이 VPN → PFN translation을 담당한다.
  • demand paging과 page fault를 통해 page를 필요할 때만 메모리에 올린다.

• 그리고 paging 위에서

  • page-level protection
  • shared memory
  • copy-on-write
  • memory-mapped file
    같은 고급 기능을 만들 수 있다.

• 다만 page table 크기와 address translation overhead는 여전히 문제다.

• 그래서 다음 단원에서는 Advanced Page Tables와 TLB를 통해 이 overhead를 줄이는 방법으로 이어진다.