Demand Paging

 

이 포스트는 서울대학교의 '운영체제의 기초' 강의를 개인 학습용으로 작성한 포스트입니다.

 

 

 

Why Demand Paging?

Swap area : Physical memory에 저장되지 못한 page들을 저장하는 디스크 공간

                file에 비해 OS가 빠르게 접근할 수 있음

 

Demand page policy : Physical memory와 Swap device 사이의 데이터 전송이 최소한으로 발생하도록 함

 

Trashing

Physical memory가 작아 swap-in 하는 page들에 의해 앞으로 사용될 page가 swap-out되면서 반복적으로 page fault가 발생하는 현상

 

Residence Bit

대상 page가 Physical memory에 있는지 표시하는 page table의 flag

 

 

Page Fault

Virtual address가 가르키는 page가 Physical memory에 없어서 OS에 알려주는 인터럽트

수행중인 Instruction을 변화된 상태를 되돌렸다가 Page fault처리가 끝난 후 instruction을 재개해야 함

 

Page fault handler 동작

1. DMA controller에게 page 주소 전달

2. DMA controller는 해당 page를 physical memory 로드

3. DMA controller 작업 끝나면 인터럽트 발생

4. 운영체제는 page fault 일으킨 프로세스 수행 재개

 

 

Demand Paging

Page selection

1. Pure demand paging : page fault가 발생할 때 로드

2. Prepaging : 사용될 page 예측해서 미리 로드

3. Request paging : 논리적으로 연관있는 page 미리 로드 (사용자가 미리 규정)

 

 

Page replacement

1. Random

2. FIFO

3. OPT : 가장 오랫동안 사용되지 않을 page 내보냄, 이론적인 알고리즘

4. LRU (Least Recently Used) : 최근에 가장 사용되지 않은 page 내보냄

 

 

Page frame allocation

1. Global allocation : 모든 page가 같은 pool

2. Per-process allocation : Process 단위로 allocate

3. Per-job allocation : User 단위로 allocate

 

 

In local page frame allocation

Working set algorithm

 

 

* Belady's anomaly : Memory를 늘렸음에도 불구하고 page fault가 더 많이 발생하는 현상

 

Stack algorithm

N개 frame으로 구성된 memory page들이 N+1개 frame으로 구성된 memory page들의 부분집합이 되는 알고리즘

LRU가 이에 포함하며, Belady's anomaly가 발생하지 않음

 

 

LRU approximation

1. reference bit를 shift register로하여 오래된거 선택

2. Clock algorithm

 

Clock algorithm

Reference bit (Use bit) : main memory에 로드된 page가 access되면 set되는 flag

1. 0이면, page 교체

2. 1이면 0으로 바꾸고 다음으로 넘어감

3. 모두 1이면 FIFO 방식으로 해결함

 

 

* Dirty bit : page에 변경이 일어나 디스크와 데이터가 다른 상태를 알려줌

Clock algorithm에서 clean한거 먼저 교체함 (디스크에 업데이트할 필요 없음)

 

 

Frame buffering (FIFO 보완)

Used page list, Free page list로 분리를 함 (Second chance)

Page fault가 일어났을 때 free page list head의 page와 교체

 

 

Thrashing

1. 충분한 많은 process가 동작 중

2. 요구하는 memory가 physical memory보다 많아 page fault 발생

3. Page fault 동안, process는 block 당해 CPU utilization 낮아짐

4. CPU scheduler는 시스템이 한가한 것으로 판단하고 더 많은 process를 동작시킴

5. Memory 부족해짐으로써 악순환 반복

-> Local allocation을 통해 thrashing을 해결할 수는 없음 (다른 process가 영향 받음)

 

 

Working Set & Resident Set

Working set

어느 시점에 특정 process가 access하는 page들의 집합 (Informal definition)

문제점 : Working set window size를 정하기가 어려움

           Shared page일 경우에도 정하기 어려움

 

 

Residence set

어떤 프로세스가 어느 시점에 main memory (physical memory)에 가지고 있는 page들의 집합

Page fault가 많이 발생하면 많은 frame할당

Page fault가 적게 발생하면 몇개 frame 회수

-> 이래도 Thrashing 해결 안되면 swap out 또는 process terminate

 

 

Trends in Memory Management

1. Larger physical memory (page size도 커짐)

2. Larger virtual address spaces (page table 커짐)

3. File I/O using the virtual memory system

 

 

Paging for Large Address Spaces

1. Hierachical page table

Page table을 여러개로 scatter함

여러번의 memory access 필요

 

2. Hashed page table

Hash function 성능 중요

 

 

3. Inverted page table

Physical memory size만큼 page table 크기

Search 해야함 (주로 Hash 사용)

Shared memory 구현 어려움