가상 메모리 - (1)

Demand Paging

실제로 필요할 때에 페이지를 메모리에 올리는 것
- I/O 양 감소
- 메모리 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
Valid/ Invalid bit 사용 -> 메모리에 있는가/backing store에 있는가
요청한 메모리가 없는 경우 = Page Fault

Page Fault

invalid page를 접근하면 MMU가 trap 발생
커널모드로 들어가서 page fault handler가 invoke
대부분의 경우는 page fault 나지 않음 하지만 나면 시간 오래 걸림

invalid임
trap 걸려
CPU가 OS에게 넘어감
OS는 backing store에 있는 페이지를 물리적 메모리에 올려놓음
valid로 바꿈
CPU 다시 얻음

페이지 교체 알고리즘

Optimal Algorithm(OPT)

가장 먼 미래에 참조되는 페이지 교체
실제로 수행은 어려움
다만 다른 알고리즘 성능에 대한 upper bound 제공 -> 아무리 좋은 알고리즘 가져와봤자 OPT가 성능 젤 좋음

Fisrt In First Out (FIFO)

먼저 들어온거 먼저 내쫓음

Least Recently Used (LRU)

가장 오래전에 사용된거 내쫓음
링크드리스트 사용해서 오래된거 뒤로보냄, 쫓아낼때는 맨 위 쫓아냄 -> O(1) : 비교는 필요없고 삽입 삭제만

Least Frequently Used (LFU)

참조 횟수 가장 적은 페이지
참조 횟수로 해야하기 때문에 maxHeap 사용 -> O(log N)