Virtual Memory
paging 기법을 사용하는 것으로 가정
(실제로 대부분의 시스템이 paging 기법을 사용)
Demand Paging
요청이 있을 때 page를 메모리에 올리기
효과
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
Valid / Invalid
- 페이지 테이블의 엔트리 중 하나로
Valid / Invalid표시 - Invalid : 물리 메모리에 올라와있지 않은 경우
- backing store에 존재- 사용되지 않는 페이지
- 처음에는 모든 page 엔트리가 invalid로 초기화
요청한 페이지가 메모리에 없는 경우 = page fault -> 운영체제가 메모리에 올려줘야 함
Page Fault
invalid page에 접근하면 MMU가 trap을 발생시킴
---> CPU가 운영체제로 넘어감
---> page fault handler 실행
Page Fault처리 순서
- 잘못된 접근인지 확인 ex) 프로세스가 사용하지 않는 주소, 접근 권한이 없는 경우 => abort
- 페이지를 올리기 위한 빈 페이지를 찾기 -> 없으면 뺏어오기
- 디스크에서 메모리로 읽어오기 (그 동안 다른 프로세스 실행)
- 디스크 읽기가 끝나면 페이지 테이블 엔트리에 기록 -
invalid --> valid- 프로세스가 다시 CPU를 잡음
- 아까 중단되었던 명령을 다시 실행
Demand Paging의 성능
- page fault가 얼마나 자주 발생하냐에 따름
- page fault 비율 : p (0 <= p <= 1)
- 일반적으로 잘 발생하지 않음 (0에 가까움)
- 메모리 접근 시간 = (1-p)메모리 접근 시간 + p (page fault 오버헤드 + 스왑비용... 큰 비용)
Page replacement(페이지 교체 알고리즘)
- 새로운 페이지를 올릴 자리가 없으면 이미 있는 페이지를 내쫓기 -> 운영체제가 함
- 어떤 frame을 빼앗을지 결정해야 함
- page fault가 낮아지도록 하는 것이 좋음
- 내쫓은 페이지를 다시 참조하게 될 경우 낭패
1) Optimal Algorithm
가장 먼 미래에 참조되는 페이지를 쫓아냄
- page fault를 가장 낮게 하는 알고리즘
- 미래의 참조되는 페이지를 다 안다고 가정 (실제로는 불가능)
- 아무리 좋은 알고리즘을 만들어도 이 보다 좋을 수는 없지만 만약 이 만큼 성능을 낸다면 효율적이라는게 증명됨
2) FIFO
First In First Out
먼저 들어온 것을 먼저 내쫓음
- 메모리 크기를 늘려줘도 오히려 성능이 나빠지는 기현상이 발생 가능 -> FIFO Anomaly
3) LRU
Least Recently Used
가장 오래 전에 사용된 것을 내쫓음
- 가장 많이 쓰는 알고리즘
- 미래를 알지 못하니 과거를 보자
- 최근에 참조된 페이지가 다시 참조될 성향이 높을 것이다!
문제
마지막 참조 이전의 기록은 신경쓰지 않는다는 문제
방법 및 시간 복잡도
페이지를 참조 시간에 따라 list로 관리 -> O(1)
4) LFU
Least Frequently Used
가장 덜 참조된 것을 내쫓음
- 과거에 많이 참조된 페이지는 앞으로도 참조될 성향이 높을 것이다!
문제
- 바로 직전에 처음으로 참조된 페이지의 성향을 알지 못해도 내쫓는다는 문제
방법 및 시간 복잡도
- 페이지를 참조 횟수에 따라 list로 관리하려면 참조 횟수를 비교하는 작업이 필요 -> O(n)
-> Heap으로 구현 = O(log n)
Paging System에서 LRU, LFU
- 주소를 변환하는건 하드웨어적 작업
- page fault가 발생해서 페이지 교체가 필요할 때는 운영체제로 CPU가 넘어감
- 과연 운영체제가 가장 오래된, 참조횟수가 적은 페이지를 알 수 있나? -> 없다
- 페이지가 메모리에 존재하는 경우에는 운영체제는 알 수가 없음
- page fault가 발생해야만 정보를 얻을 수 있어 페이지가 사용할 때 참조횟수나 시기를 기록해둘 수 없음
➡️ 그럼 실제로는 뭘 사용할까?
Clock Alogorithm
- LRU의 근사 알고리즘
- NUR (Not Used Recently) 또는 NRU로 불림
- 페이지 프레임을 시계처럼 가리킴
Reference bit
- 페이지가 참조가 되면 1로 세팅됨
- 운영체제가 아니라 하드웨어가 하는 작업
Reference bit == 1--> 최근에 사용되었다- 운영체제가 0으로 바꾸면서 이동하다 0인 페이지를 교체
-> 돌고 왔는데 여전히 0이다? 그동안 참조되지 않았다 Reference bit == 0인 최근에 참조가 되지 않는 페이지를 내쫓음
Modified bit (Dirty bit)
- 페이지에 저장된 내용이 변경된 경우 그냥 쫓아내는 것이 아니라 backing store에 저장도 해야 함
Modified bit == 1: 최근에 변경된 페이지 -> 디스크에 저장하고 내보내야 함Modified bit == 0이면 그냥 메모리에서 내보내면 됨- 가능하다면 0인 페이지를 내쫓는 것이 빠름
참고 링크
반효경 교수님 강의
페이지 교체 알고리즘
iOS Developer