Paging
: 실제로 필요할 때 page를 물리적 메모리에 올리는 것
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답시간
- 더 많은 사용자 수용 가능
Physical memory에 없는 Page의 Page table: valid-invalid bit = 0 (Invalid)
▶ valid-invalid bit = 0(Invalid)
- 사용되지 않는 주소 영역인 경우
- page가 물리적 메모리에 없는 경우: swap area(disk)
- 처음에는 모든 page entry가 invalid로 초기화된다.
- address translation 시에 invalid bit이 set되어 있으면 --> "page fault"
Page Fault
1. invalid page를 접근하면, MMU(주소변환 하드웨어)가 trap을 발생시킨다: page fault trap --> CPU 제어권이 운영체제로 넘어간다.
2. 커널 모드로 들어가서 page fault handler가 invoke된다.
3. page fault가 처리된다.
- Invalid reference?: 잘못된 요청이 아닌지 확인한다. --> 잘못된 요청이면, abort process
- Get an empty page frame: physical memory에서 empty page frame을 가져온다. 없으면 뺏어온다(replace).
- 해당 page를 disk에서 memory로 읽어온다. (disk/IO는 매우 느린 작업이기 때문에, 이떄 프로세스는 CPU 제어권을 가지고 있어도 할 수 있는 일이 없다. --> disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당한다(block).)
- Disk read가 끝나면, page tables entry에 기록한다: invalid --> valid.
- ready queue에 프로세스를 insert --> dispatch later
4. 이 프로세스가 CPU를 잡고 다시 running한다.
5. 아까 중단되었던 instruction을 재개한다.
** Free frame이 없는 경우: Page Replacement
▶ Page replacement: Physical memory에서 어떤 frame을 쫓아낼지 결정해야 한다.
▶ Replacement Algorithm: page-fault rate를 최소화하는 것이 목표이다.
Performance of Demand Paging
- page port: disk에 접근해야 한다. 그런데 이때, disk 접근은 매우 오래 걸리는 작업이다. 따라서 page port가 얼마나 자주 발생하는지에 따라, 메모리 접근 시간이 크게 달라진다.
- p가 작을수록, page port가 적게 발생하기 때문에, 메모리 접근 시간이 줄어든다.
Page Replacement Algorithm
MIN(OPT): Optimal Algorithm
▷ 가장 먼 미래에 참조되는 page를 replace한다.
- Offline algorithm: reference string을 미리 다 알고 있다고 가정한다.
--> page port를 가장 적게 하는 알고리즘(다른 알고리즘 성능에 대한 upper bound)
미래를 모르는 상황에서의 알고리즘
FIFO(First In First Out) Algorithm
▷ 가장 먼저 들어온 것을 먼저 내쫓는다.
- FIFO Anomaly: more frames =/=> less page faults
LRU(Least Recently Used) Algorithm
▷ 가장 오래 전에 참조된 것을 지운다.
LFU(Least Frequently Used) Algorithm
▷ 참조 횟수(reference count)가 가장 적은 객체를 지운다.
-- 최저 참조 횟수인 page가 여럿인 경우
- LFU 알고리즘에서는 여러 page 중 임의로 선정하여 지운다.
- 성능 향상을 위해, 가장 오래 전에 참조된 page를 지우게 구현(LRU)할 수도 있다.
LRU vs. LFU
▶ LRU(Least Recently Used) --> O(1) complexity
▶ LFU(Least Frequently Used): heap --> O(log n) complexity
- 장점: LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에, page의 인지도를 좀 더 정확히 반영할 수 있다.
- 단점: 참조 시점의 최근성을 반영하지 못한다.
- 단점: LRU보다 구현이 복잡하다.
'운영체제' 카테고리의 다른 글
[운영체제] KOCW 12.1 - Ch10: File System (0) | 2023.06.10 |
---|---|
[운영체제] KOCW 11.2 - Ch9: Virtual Memory (0) | 2023.06.10 |
[운영체제] KOCW 10 - Ch8: Memory Management (0) | 2023.06.10 |
[운영체제] KOCW 9 - Ch8: Memory Management (0) | 2023.06.10 |
[운영체제] KOCW 8 - Ch8: Memory Management (0) | 2023.06.09 |