[운영체제] KOCW 11.1 - Ch9: Virtual Memory

Paging

: 실제로 필요할 때 page를 물리적 메모리에 올리는 것

• I/O 양의 감소
• Memory 사용량 감소
• 빠른 응답시간
• 더 많은 사용자 수용 가능

 

Physical memory에 없는 Page의 Page table: valid-invalid bit = 0 (Invalid)

valid-invalid bit = 0 (Invalid)

▶ valid-invalid bit = 0(Invalid)

• 사용되지 않는 주소 영역인 경우
• page가 물리적 메모리에 없는 경우: swap area(disk)

1. 처음에는 모든 page entry가 invalid로 초기화된다.
2. 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가 처리된다.

1. Invalid reference?: 잘못된 요청이 아닌지 확인한다. --> 잘못된 요청이면, abort process
2. Get an empty page frame: physical memory에서 empty page frame을 가져온다. 없으면 뺏어온다(replace).
3. 해당 page를 disk에서 memory로 읽어온다. (disk/IO는 매우 느린 작업이기 때문에, 이떄 프로세스는 CPU 제어권을 가지고 있어도 할 수 있는 일이 없다. --> disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당한다(block).)
4. Disk read가 끝나면, page tables entry에 기록한다: invalid --> valid.
5. ready queue에 프로세스를 insert --> dispatch later

4. 이 프로세스가 CPU를 잡고 다시 running한다.

5. 아까 중단되었던 instruction을 재개한다.

 

** Free frame이 없는 경우: Page Replacement

** Free frame이 없는 경우: Page Replacement

▶ Page replacement: Physical memory에서 어떤 frame을 쫓아낼지 결정해야 한다.

▶ Replacement Algorithm: page-fault rate를 최소화하는 것이 목표이다.

 

 

Performance of Demand Paging

• page port: disk에 접근해야 한다. 그런데 이때, disk 접근은 매우 오래 걸리는 작업이다. 따라서 page port가 얼마나 자주 발생하는지에 따라, 메모리 접근 시간이 크게 달라진다.

Performance of Demand Paging

• p가 작을수록, page port가 적게 발생하기 때문에, 메모리 접근 시간이 줄어든다.

 

 

Page Replacement Algorithm

MIN(OPT): Optimal Algorithm

▷ 가장 먼 미래에 참조되는 page를 replace한다.

• Offline algorithm: reference string을 미리 다 알고 있다고 가정한다.

--> page port를 가장 적게 하는 알고리즘(다른 알고리즘 성능에 대한 upper bound)

MIN(OPT): Optimal Algorithm

 

미래를 모르는 상황에서의 알고리즘

FIFO(First In First Out) Algorithm

▷ 가장 먼저 들어온 것을 먼저 내쫓는다.

• FIFO Anomaly: more frames =/=> less page faults

FIFO(First In First Out) Algorithm

 

LRU(Least Recently Used) Algorithm

▷ 가장 오래 전에 참조된 것을 지운다.

LRU(Least Recently  Used) Algorithm

 

LFU(Least Frequently Used) Algorithm

▷ 참조 횟수(reference count)가 가장 적은 객체를 지운다.

-- 최저 참조 횟수인 page가 여럿인 경우

• LFU 알고리즘에서는 여러 page 중 임의로 선정하여 지운다.
• 성능 향상을 위해, 가장 오래 전에 참조된 page를 지우게 구현(LRU)할 수도 있다.

 

LRU vs. LFU

LRU vs. LFU

▶ LRU(Least Recently Used) --> O(1) complexity

 

▶ LFU(Least Frequently Used): heap --> O(log n) complexity

• 장점: LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에, page의 인지도를 좀 더 정확히 반영할 수 있다.
• 단점: 참조 시점의 최근성을 반영하지 못한다.
• 단점: LRU보다 구현이 복잡하다.