메모리 주소변환은 운영체제가 관여하지 않지만, 이 가상 메모리 기법은 전적으로 운영체제가 관여한다.
Demand Paging
프로그램에서 빈번히 사용되는 부분은 지극히 제한적이다. 그렇기 때문에 메모리에 이 페이지들을 올리는 것은 분명한 낭비이다. 따라서 필요할 때만 페이지를 메모리에 올리는 것이 Demand Paging이다
- 실제로 필요할 때 page를 메모리에 올리는 것
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
- Valid/Invalid의 사용
- Invalid의 의미
- 사용되지 않는 주소 영역인 경우
- 페이지가 물리적 메모리에 없는 경우
- 처음에는 모든 Page Entry가 invalid로 초기화
- address translation 시에 invalid bit이 set 되어 있으면 → "page fault" → CPU는 자동적으로 운영체제로 넘어가며 운영체제에는 Page fault에 대한 처리 루틴이 정의되어 있다
- Invalid의 의미
Page Fault 처리루틴
- invalid page에 접근하면 MMU가 trap 을 발생 시킨다
- Kernel mode로 들어가서 page fault handler가 invoke된다
- 다음과 같은 순서로 page fault를 처리한다
- invalid reference? (e.g. bad address, protection violation) -> abort process
- Get an empty page frame (없으면 뺏어온다. replace)
- 해당 페이지를 disk에서 memory를 읽어온다 (시간이 오래걸린다)
- disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함 (block)
- Disk read 가 끝나면 page tables entry 기록, valid/invalid = 'valid'
- ready queue에 process를 insert -> dispatch later
- 이 프로세스가 CPU를 잡고 다시 running
- 아까 중단되었던 instruction을 재개
Free frame 이 없는 경우
가능하면 페이지 디폴트가 나지 않고 직접 메모리를 처리하면 좋다
- Page replacement
- 어떤 frame을 빼앗아올지 결정해야함
- 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
- 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음
- Replacement Algorithm
- Page fault rate를 최소화하는 것이 목표
- 알고리즘의 평가
- 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사
- reference string의 예
- 1,2,3,4,1,2,5,1,2,3,4,5
Replacement Alogorithm 1번 - Optical Algorithm (제일좋다)
실제로 적용을 못하는 알고리즘이다 - 다른 알고리즘에 대한 성능을 참고하는 척도로 사용가능
미래에 참조될 페이지를 미리 전부 안다고 가정하고 사용
- MIN(OPT): 가장 먼 미래에 참조되는 page를 replace
- 미래의 참조를 어떻게 아는가?
- Offline algorithm
- 다른 알고리즘의 성능에 대한 upper bound 제공 (아무리 좋은 알고리즘을 만들어도 이것보다 좋지 않다)
- Belady's optical algorithm, MIN, OPT 등으로 불림
Replacement Alogorithm 2번 - FIFO (First In First Out) Algorithm
먼저 들어온 것을 먼저 내쫓음
- FIFO Anomaly(Belady's Anomaly) => 페이지 수가 늘어나면 page fault가 늘어난다
- more frames => less page faults
Replacement Alogorithm 3번 - LRU (Least Recently Used) Algorithm
가장 오래전에 참조된 것을 내쫓는다
- 최근에 참조된 페이지가 다시 참조될 가능성이 높다는 뜻
- 미래를 모르기 때문에 과거를 보고 무슨 페이지를 쫓아낼지 결정한다
Replacement Alogorithm 4번 - LFU (Least Frequently Used) Algorithm
- 참조 횟수 (reference count)가 가장 적은 페이지를 지움
- 최저 참조 횟수인 page가 여럿 있는 경우
- LFU 알고리즘 자체에서는 여러 page 중 임의로 선정한다
- 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다
- 장단점
- LRU 처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
- 참조 시점의 최근성을 반영하지 못함
- LRU보다 구현이 복잡합
- 최저 참조 횟수인 page가 여럿 있는 경우
LRU, LFU 예제)
오른쪽 화살표가 그려진 그림은 지금까지의 page 참조시간과 횟수를 기록한 그림이다.
- LRU의 경우는 1번 page를 삭제할 것이다.
- LRU는 1번과 같이 예전에 인기 있었던 Page를 선별하지 못한다
- 반면 LFU는 4번 page를 삭제할 것이다.
- LFU는 4번 Page와 같이 최근에 인기 있어지기 시작한 Page를 선별하지 못한다.
LRU, LFU Implementation
- LRU는 어떤 페이지가 한번만 참조되어도 그 노드의 우선순위가 가장 높아진다.
- O(1) Complexity
- 그러나 LFU는 어떤 페이지가 참조되더라도 MFU로 바로 내려갈 수 없고 비교를 하면서 내려갈 수 있게 된다
- O(log n)
'운영체제[반효경] > Ch09. Virtual Memory' 카테고리의 다른 글
| Virtual Memory (2) (0) | 2024.11.12 |
|---|