09. Virtual Memory (1/2)

전적으로 운영체제가 관리함

Demand Paging: 요청이 왔을 때, page를 메모리에 올림

(Paging 기법을 쓴다고 가정 -> 실제로 대부분 그렇다)

Invalid: 물리적 메모리에 없는 것 (Backing store에 존재) 또는 사용하지 않는 것 (주소공간에는 넉넉하게 지원해주기 때문)

Page Fault: 요청한 것이 메모리에 없는 경우

-> Invalid page에 접근하면 MMU가 trap을 발생시킴

-> Kernel mode로 된 뒤, Page fault handler가 invoke됨

Page Frame이 없는 경우: 사용하는 Page Frame 중 쫓아낸 뒤 차지하는 것

-> 쫓아낸 Page가 다시 사용되지 않을 수록 성능이 좋으므로 잘 결정해야 한다.

Min (OPT): 가장 먼 미래에 참조되는 Page를 replace (미래를 알 수 없으므로 실제 사용은 불가)

-> Upper bound를 제공하는 역할

FIFO Algorithm: 먼저 들어온 것을 먼저 내쫓음 (FIFO Anomaly: 메모리가 늘어나도 Page Fault가 더 발생할 수 있는 단점이 있음)

LRU Algorithm: Least Recently Used 의 약자로, 가장 오래된 것을 쫓아냄 (가장 많이 사용됨)

-> 한 줄로 줄 세워서 linked lisst 형식으로 O(1) 복잡도

LFU Algorithm: 참조 횟수가 가장 적은 페이지를 지움

-> 한 줄로 할 경우 계속해서 비교하면서 정렬해줘야 함 O(n) 복잡도임 -> Heap을 활용하여 O(logN) 복잡도로 할 수 있음