물리적인 메모리 주소 변환은 하드웨어가 도맡아 진행한다.
가상 메모리 주소 변환에서는 운영체제가 관여.
어떤 로직으로 운영체제가 가상메모리를 관리하는지 알아보자
Demand Paging
- 실제로 필요할 때 page를 메모리에 올리는 방식
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답시간
- 더 많은 프로세스 수용 가능
프로그램이 실행될 때 프로세스를 구성하는 주소공간의 페이지를 통째로 메모리로 올리는 것이 아니라 디맨드 페이징 기법을 이용하여 특정 페이지가 요청되었을 때 메모리에 올린다는 의미.
- Valid / Invalid bit 사용
- invalid의 의미 : 사용되지 않은 주소 영역이거나 페이지가 물리적 메모리에 없는 경우.
- 처음에는 모든 페이지 엔트리가 invalid로 초기화
- address translation 시, invalid bit이 set되어 있다면 ->
page fault발생
Page fault
- invalid page 를 접근하면 MMU가 trap을 발생시킴 (page fault trap)
- Kernel mode(운영체제가 CPU 잡음)로 들어가서 page fault handler 호출
- 다음과 같은 순서로 page fault를 처리한다.
1. Invalid reference? (ex. bad address, protection violation) => abort process
2. Get an empty page frame (없으면 뺏어온다: replace)
3. 해당 페이지를 disk에서 메모리로 읽어온다. (대단히 느린 작업)
(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을 재개
대부분의 경우 페이지폴트 나지 않고 메모리로부터 직접 주소변환 가능. (약 p = 0.01)
그렇지 않은 경우 디스크접근 필요.
- Effective Access Time
= ( 1 - p ) * memory access + p (OS & HW page fault overhead + [swap page out if needed] + swap page in + OS & HW Restart overhead)
페이지 폴트 시 오버헤드가 크다.
Free frame이 없는 경우
-
Page replacement
(1) 어떤 프레임을 빼앗아올지 결정해야함
(2) 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
(3) 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음 -
Replacement Algorithm
(1) page-fault rate를 최소화하는 것이 목표
(2) 알고리즘의 평가
-> 주어진 page reference string 에 대해 page fault를 얼마나 내는지 조사
(3) reference string의 예
: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
시간 순서에 따라 페이지들이 참조된 순서를 나열한 것.
어떤것을 쫓아낼지(victim)를 결정하고, 그 자리에 새로운 페이지를 올려야함.
올라간/쫓겨난 페이지에 대한 페이지 테이블의 valid-invalid bit 업데이트 해야함
Optimal Algorithm
페이지 폴트를 가장 적게하는 알고리듬
- MIN (OPT) : 가장 먼 미래에 참조되는 페이지를 replace
-
미래의 참조를 어떻게 아는가? (실제론 불가능한 이론적인 알고리즘)
=> offline algorithm -
다른 알고리즘의 성능에 대한 upper bound 제공 (이보다 더 좋은 성능의 알고리즘은 존재하지 못함)
=> Belady's optimal algorithm, MIN, OPT 등으로 불림.
FIFO(First In First Out) Algorithm
미래를 모르는 상황에서의 알고리듬
미래를 잘 예측하는 것이 중요하다.
- FIFO: 메모리에 먼저 들어온 것을 먼저 내쫓음
- FIFO Anomaly (Belady's Anomaly)
more frames =/> less page faults
메모리를 더 할당해서 더 많은 페이지 프레임을 가지게 했을 때, 상식적으론 페이지 폴트가 덜 나야하겠지만, 해당 알고리듬에선 더 많아진다.
LRU(Least Recently Used) Algorithm
- LRU : 가장 오래전에 참조된 것을 지움
참조된 페이지들을 참조시점에 따라 연결 리스트 형태로 보관. -> 참조시점에 따라 추가/제거/삽입 진행
O(1) complexity 를 가진다.
LFU(Least Frequently Used) Algorithm
- LFU: 참조 횟수가 가장 적은 페이지를 지움
- 최저 참조 횟수인 page가 여럿 있는 경우
(1) LFU 알고리즘 자체에서는 여러 페이지 중 임의로 선정한다
(2) 성능 향상을 위해 가장 오래전에 참조된 페이지를 지우게 구현할수도 있다. - 장단점
LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 페이지의 인기도를 좀 더 정확히 반영할 수 있음
참조 시점의 최근성을 반영하지 못함
LRU보다 구현이 복잡함
최소힙으로 구현하여 O(log n) complexity 를 가짐
