Demand Paging
basic concept
실제로 필요할 때 page를 메모리에 올리는 것이다.
•
Disk I/O 양의 감소
•
Memory 사용량 감소
•
(시스템 전체적으로) 빠른 응답 시간
•
더 많은 프로세스 수용
Valid / Invalid bit의 활용
•
Invaild의 의미
◦
사용되지 않는 주소 영역
◦
페이지가 물리적 메모리에 없다
•
처음에는 모든 Page Entry를 Invalid로 초기화 한다.
•
address translation 시에 invalid bit가 set되어 있다면, page fault라고 부르는 트랩이 발생하게 된다.
page fault
1.
invalid page로 접근하면 MMU가 trap을 발생시킴 (page fault trap)
2.
커널 모드로 들어가서 page fault handler가 invoke 된다.
•
Invalid Reference인지 확인한다. (address가 잘 못 되었는지, 권한이 잘못되었는지)
◦
맞다면 취소한다.
•
메모리에서 빈 페이지 프레임을 찾아 가져온다. (없으면 페이지 하나를 대체한다.)
•
해당 페이지를 disk에서 memory로 읽어온다.
◦
disk I/O가 끝나기까지 이 프로세스는 CPU를 선점당함
◦
Disk read가 끝나면 page tables entry를 기록하고, valid bit를 valid로 설정한다.
◦
프로세스를 job queue로 돌려 보낸다.
•
프로세스가 CPU를 잡고 다시 재개된다.
•
trap이 발생하기 전 중단되었던 instruction이 재개된다.
Page fault 흐름도
page fault는 운영체제 문맥교환 오버헤드, 페이징 스왑 아웃 & 스왑 인으로 인해 메모리 접근 시간을 매우 늘리게 된다. page fault를 얼마나 줄이느냐가 관건
Page replacement
Free frame이 없는 경우 어떤 페이지를 빼앗아올지 결정해야 하는데, 이를 page replacement라고 한다.
곧바로 사용되지 않을 페이지를 쫓아내는 것이 좋다.
page replacement 흐름도. victim에 write 작업이 없었다면, swap out없이 비워주어도 무방하다.
Replacement Algorithm
page-fault rate를 최소화하는 것이 목표이다.
알고리즘의 평가는 무작위로 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사한다. (예. 1,2,3,4,1,2,5,1,2,3,4,5)
•
MIN (Optimal) : 가장 먼 미래에 참조되는 page를 replace.
5번이 들어왔을 때, 가장 뒤에 참조되는 4번 메모리가 replace 됨을 볼 수 있다.
◦
미래의 참조를 어떻게 아는가? 알 수 없기 때문에, 온라인 환경에서는 쓸 수 없고 미리 알 수 있는 offline 환경에서만 쓸 수 있는 offline algorithm이다.
◦
다른 알고리즘에 성능에 대한 upper bound를 제공하는 역할이다 (가장 빠른 알고리즘)
•
FIFO : 가장 먼저 들어온 것을 먼저 내쫓는다.
◦
특이하게도, 페이지 프레임을 늘리면 페이지 폴트가 더 늘어나는 상황이 발생할 수 있다.
•
LRU : Least Recently Used Algorithm, 가장 오래전에 참조된 것을 지운다.
•
LFU : Least Frequently Used Algorithm, 가장 참조횟수가 적은 페이지를 지운다.
◦
최저 참조 횟수인 page가 여럿 있는 경우
▪
LFU 알고리즘 자체에서는 여러 페이지 중 임의로 선정한다.
▪
실제로 활용할 때는 가장 오래전에 참조된 page를 지우게 구현할 수 도 있다.
◦
장점
▪
LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있다.
◦
단점
▪
참조 시점의 최근성을 반영하지 못한다.
▪
LRU보다 구현이 복잡하다.
LRU와 LFU의 구현, LRU는 참조된 페이지를 가장 끝으로 보내고, LFU는 트리구조에서 순회한다.
LRU, LFU의 한계점
페이지 폴트가 날 때에만 OS에게 CPU가 넘어가기 때문에, OS가 어떤 페이지가 가장 오래된 것인지, 가장 많이 참조된 것인지는 알 수 가 없다.
Clock Algorithm
•
LRU의 근사(apporximation) 알고리즘
•
Second chance Algorithm, NUR(Not Used Recently), NRU(Not Recently Used) 등으로도 불린다
•
reference bit를 사용해서 교체 대상 페이지 선정 (circular list)
◦
참조된 페이지는 reference bit가 1이 된다.
◦
알고리즘은 reference bit가 0인 것을 찾을 때 까지 포인터를 하나씩 앞으로 이동한다.
◦
포인터 이동 중에 reference bit 1은 모두 0으로 바꾼다.
◦
Reference bit이 0인 것을 찾으면 그 페이지를 교체한다.
◦
한 바퀴 되돌아와서도 (=second chance) 0이면 그 때는 replace 당한다.
◦
자주 사용되는 페이지라면 second chance가 올 때 1일 것 이다.
시계 모양의 circular list를 쓰기 때문에 clock algorithm 이다.
•
Clock algorithm 의 개선
◦
reference bit와 modified bit (dirty bit)를 함께 사용한다.
◦
reference bit = 1 : 최근에 참조된 페이지
◦
modified bit = 1 : 최근에 변경된 페이지, 변경되었다면 backing store에 write를 해주고 아니라면 메모리에서 쫓아낸다.
Page frame의 allocation
allocation problem : 각 process에 얼마만큼의 page frame을 할당할 것인가?
allocation의 필요성
•
메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지를 동시에 참조한다.
◦
명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있다.
•
loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리하다.
◦
최소한의 allocation이 없으면 매 loop 마다 page fault를 겪을 것!
Allocation Scheme
•
Equal allocation : 모든 프로세스에 똑같은 갯수 할당
•
Proportional allocation : 프로세스 크기에 비례하여 할당
•
Priority allocation : 프로세스의 priority (자주 사용되는 빈도)에 따라 다르게 할당
global replacement VS local replacement
global
•
replace 시 다른 process에 할당된 frame을 빼앗아 올 수 있다.
•
process 별 할당량을 조절하는 또 다른 방법
•
FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당된다.
•
Working set, PFF 알고리즘 사용
local
•
자신에게 할당된 frame 내에서만 replacement한다.
•
FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영한다.
Thrashing
basic concept
기본적으로 멀티프로그래밍에 동시에 사용하는 프로세스를 늘려주면, IO 도중에 다른 프로세스가 CPU를 활용할 것이므로 CPU utilization(사용률)은 증가할 것이다.
그러나 프로세스가 지나치게 많아지면 되려 CPU utilization은 낮아진다. 왜? Thrashing 때문이다.
thrashing은 프로세스에 원할한 수행에 필요한 최소한의 page frame 수를 할당 받지 못하여 page fault가 빈번하게 발생하는 현상을 뜻한다.
Thrashing Diagram
현상
•
page fault rate가 매우 높아짐
•
CPU utilization이 낮아짐
•
OS는 MPD (Multiprogramming degree)를 높여야 한다고 판단 (CPU utilization이 낮으므로)
•
또 다른 프로세스가 시스템에 추가된다. (higher MPD)
•
프로세스 당 할당된 frame의 수가 더욱 감소한다.
•
프로세스는 page의 swap in / swap out으로 매우 바쁘다.
•
대부분의 시간에 CPU는 한가해진다. → low throughput
Thrashing의 방지
Working-set Model
Locality of reference
•
프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다.
•
집중적으로 참조되는 해당 page들의 집합을 locality set이라 함
working-set model
•
Locality에 기반하여 프로세스가 일정 시간 동안 원할하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working Set이라고 한다.
Working Set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out(suspend)된다.
Thrashing이 방지되고, Multiprogramming degree를 결정한다.
working-set의 결정
•
그러면 working-set에 포함된 페이지가 어떤 것인지는 어떻게 알아낼까?
•
working set window를 통해 알아냄
◦
window는 별도로 설정된 시간단위이다. 한번의 윈도우가 진행될 동안 참조된 서로 다른 페이지의 목록을 working-set으로 삼는다.
window size = WS, 한번의 윈도우 동안 참조된 서로 다른 페이지가 Working-set이 된다.
◦
working set에 속한 page는 메모리에 유지하고, 속하지 않은 것은 버린다.
Working-set algorithm
•
process들의 working set size의 합이 page frame의 수보다 큰 경우
◦
일부 process를 swap out 시켜 남은 process의 working set을 우선적으로 충족시켜준다. (MPD를 줄임)
•
working set을 다 할당하고도 page frame이 남는 경우
◦
swap out 되었던 프로세스에게 working set을 할당 한다. (MPD를 키움)
PFF
Page-Fault Frequency Scheme.
•
page-fault rate의 상한값과 하한값을 둔다.
◦
page fault rate이 상한값을 넘으면 frame을 더 할당한다.
◦
page fault rate이 하한값 이하이면 할당 frame 수를 줄인다.
•
빈 frame이 없으면 일부 프로세스를 swap out한다.
Page Size의 결정
Page size를 감소시키면 페이지 수가 증가하게 된다. (메모리 전체 크기가 달라진 게 아니라 더 잘게 써는 거니까)
장점 | 단점 |
내부 조각 감소 | 페이지 테이블 크기 증가 |
필요한 정보만 메모리에 올라와 메모리 이용이 효율적 | Locality, 즉 프로세스 개개로 보면 큰 뭉치로 올라와있는 것이 page fault를 줄일 수 있기에 비효율적일 수 있음. |
disk transfer의 효율성 감소 |
트렌드는 페이지를 크게 가져가는 것이다. (4kb)
