본문 바로가기
CS/Operating System

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

by JHyun0302 2023. 8. 31.
728x90

요구 페이징 (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

 

반응형

'CS > Operating System' 카테고리의 다른 글

디스크 할당  (0) 2023.09.01
디스크 스케줄링  (0) 2023.08.31
메모리 주소 & 메모리 할당  (0) 2023.08.31
프로세스 간 통신 & 임계 영역  (0) 2023.08.31
Process Priority  (0) 2023.08.31