Demand Paging
- 실제로 필요할 때 page를 메모리에 올리는 것
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
Valid/Invalid bit 의 사용
- 사용되지 않는 주소영역인 경우, 페이지가 물리적 메모리에 없는 경우 : Invalid
- 처음에는 모든 page entry 가 invalid로 초기화
- address translation 시에 invalid bit이 set 되어 있으면(요청한 주소가 메모리에 올라와 있지 않은 경우) page fault 발생
page fault
: 요청한 주소가 메모리에 올라와 있지 않은 경우 발생
invalid page를 접근하면 MMU가 trap을 발생시킨다 (page fault trap)
Kernel Mode로 들어가서 page fault handler 가 invoke된다
page fault 처리 순서
1. Invalid reference ? ( if bad address, protection violation ) abort process
2. get an empty page frame (없으면 뺏어온다)
3. 해당 페이지를 disk에서 memory 로 읽어옴
1) disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당한다(block)
2) Disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"
3) ready Queue에 process를 insert -> dispatch later
4. 이 프로세스가 CPU를 잡고 다시 running
5. 중단되었던 instruction 재개
Page replacement
- Free Frame(비어있는 frame(physical memory 영역))이 없는 경우 수행됨
- 어떤 frame을 빼앗아올지 결정해야 한다 (곧바로 사용되지 않을 page를 쫓아내는 것이 좋다)
- 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음
Page fault를 줄이기 위한 Replacement Algorithm의 종류
page-fault rate을 최소화 하는 것이 목표
알고리즘의 평가기준은 주어진 page reference string에 대해 page fault를 얼마나 내는지
1. Optimal Algorithm (=Min Algorithm)
- 가장 먼 미래에 참조되는 page를 replace (미래를 안다는 가정)
- 다른 알고리즘의 성능을 측정하는 기준점이 됨(실제 사용은 불가한 offline 알고리즘)
- Belady's optimal algoroithm MIN, OPT 등으로 불림
-> 7번째 수행에서 5를 참조 할 때, 미래에서 가장 나중에 참조되는 4(마지막에서 2번째)를 쫓아내고 대신 5를 넣음
2. FIFO Algorithm (first in first out)
먼저 들어온 것을 먼저 내쫓는다
FIFO Anomaly (Belady's Anomaly) : 페이지가 늘어남에도 불구하고 page faults는 증가하는 현상이 발생
3. LRU Algorithm (Least Recently Used)
가장 오래전에 참조된 것을 지운다
4. LFU Algorithm (Least Frequently Used)
참조 횟수(reference count)가 가장 적은 페이지를 지움
* 최저 참조 횟수인 page가 여럿인 경우
- LFU 알고리즘 자체에는 여러 page 중 임의로 선정
- 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있음
* 장단점
- LRU 처럼 직전 참조 시점만 보는게 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
- 참조 시점의 최근성을 반영치 못함
- LRU 보다 구현이 복잡함
※ LRU, LFU 의 비교
LRU
위에 있을 수록 오래된 참조
- linked list 형태
- 참조될 때 맨 아래에 link시킴
- 쫓아낼 경우 맨 위의 페이지 쫓아냄
LFU
LRU 처럼 linked list 형태로 관리하기는 비효율적
: 새로 참조될 때마다 어디에 link 시킬지 판별하기 위해 참조횟수를 비교해야함 (시간 복잡도 O(N)))
linked list 형태 대신 heap 으로 구현, 2진트리로 구성
* 쫓아낼 경우 root를 쫓아내고 heap을 재구성
캐싱 기법
- 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스 하는 방식
- paging system 외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용
캐시 운영의 시간 제약
- 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
- Buffer caching이나 Web caching의 경우
: O(1) 에서 O(long n) 정도까지 허용
- Paging system인 경우
: Page fault인 경우에만 OS가 관여함
: 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
: O(1)인 LRU의 list 조작조차 불가능
* Paging System에서 LRU, LFU는 사용이 불가하다
: page fault 발생시(CPU 제어권이 운영체제로 넘어오면)에만 디스크에서 메모리에 올라온 시간을 알 수 있으며
이미 메모리에 페이지가 있으면 알 수 없음
Clock Algorithm(=Second chance algorithm = NRU(Not Recently Used))
LRU의 근사 알고리즘, LRU/LFU 대신 실제 사용되는 알고리즘
reference bit : 참조여부를 의미(1:최근에 참조된 경우, 0:최근에참조되지 않은 경우)
modified bit(=dirty bit) : write(변경) 여부를 의미(1:write 된 페이지, 0:write 되지 않은 페이지)
1) 최근에 참조된 경우 Reference bit은 1
2) 1인 경우 Reference bit 을 0으로 바꾸고 다음 페이지를 확인(최근에 참조된 페이지인 경우이므로 다음 페이지 확인)
3) 0인 경우를 발견하면 페이지를 내쫓는다
※ 이화여대 반효경 교수님의 운영체제 강의 정리