요구 페이징 & 페이지 교체 알고리즘

요구 페이징 (demand paging) 

→  프로세스의 요구에 일치하는 페이지만 물리 메모리로 가져오고 나머지 페이지는 swap 영역에 저장

 

 

Pre-paging : 프로세스가 요구 할 것으로 예상되는 페이지를 미리 물리 메모리로 가져옴

 

 

 

 

---

페이지 교체 알고리즘

 

목적 : 낮은 page fault rate 위해

 

 

 

페이지 부재(page fault) : 프로세스가 요구하는 페이지가 물리 메모리에 없고 swap 영역에 있는 경우

 

 

 

 

---

Random 페이지 교체 알고리즘

 

 

임의로 정한 페이지 (대상 페이지) swap out 함

 

 

 

 

 

---

FIFO 페이지 교체 알고리즘

 

 

가장 먼저 swap in한 페이지(대상 페이지)를 먼저 swap out

 

 

 

 

단점 : 가장 오래된 페이지도 많이 사용 할 수 있음

 → page fault rate 증가 시킬 수 있음

 

 

 

 

 

---

최적 페이지 교체 알고리즘

 

미래에 가장 오랫동안 사용되지 않을 페이지 (대상 페이지) swap out

 

 

 

단점 : 미래의 페이지 사용 예측 불가능해서 구현 불가

 

 

 

 

 

---

LRU 페이지 교체 알고리즘 (Least Recently Used)

 

최근에 오랫동안 사용되지 않은 페이지 (대상 페이지) swap out

 

 

 

성능 : FIFO보다 우수

 

 

 

 

 

---

LFU 페이지 교체 알고리즘 (Least Frequently Used)

 

사용 빈도가  가장 낮은 페이지 (대상 페이지) swap out

 

 

 

성능 : LRU와 비슷, FIFO보다 우수

 

 

단점 : 각 페이지 접근 빈도를 PTE에 저장해야 해서 추가 메모리 요구됨

 

 

 

 

 

---

NUR 페이지 교체 알고리즘 (Not Used Recently)

 

level이 작을 수록 먼저 대상 페이지로 선정되어 swap out

 

 

• reference bit : 페이지 참조 (읽기/실행)한 경우 1
•  modify bit : 페이지 수정(쓰기)한 경우 1

 

(reference bit, modify bit)	Level
(0, 0)	1
(0, 1)	2
(1, 0)	3
(1, 1)	4

 

 

장점 : LRU와 비슷, LFU와 비슷 (메모리 낭비 적음 - 2bit)

 

 

 

 

 

 

 

---

Thrashing

 

CPU 사용률 급격히 저하

이유 : 물리 메모리 부족해서 swap out → 잦은 page fault → 잦은 page 교체

 

 

 

 

Thrashing 피하는 법

1. 물리 메모리의 크기 증가

 

 

 

2. 작업집합 모델(working set model) 사용

    → 최근에 참조된 페이지들의 집합(작업집합)을 만들고 물리 메모리에 유지시킴

 

 

 

작업집합 모델

 

 

• 작업집합 크기: 작업집합에 포함되는 최대 페이지 수
• 작업집합 윈도우(∆): 현재 시점을 기준으로 작업집합에 포함되는 페이지의 범위

 

 

 

3. Page fault frequency 사용

    → page fault rate 계산

 

1. page fault rate > upper bound : 프로세스에 추가적인 frame을 할당해야 함

2. lower bound < page fault rate < upper bound :  프로세스에 적당한 frame이 할당됨

3. page fault rate < lower bound : 프로세스에 할당된 frame을 회수해야 함

 

 

 

 

 

Page fault frequency