Virtual Memory(1)

Demand Paging

• 실제로 필요할 때(요청이 들어올 때) page를 메모리에 올리는 것
  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용
• Valid / Invalid bit의 사용
  • Invalid의 의미
    • 사용되지 않는 주소 영역인 경우
    • 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 page entry가 invalid로 초기화
  • address translation 시에 invalid bit이 set 되어 있으면 ⇒ “page fault”

 

Memory에 없는 Page의 Page Table

• 0, 2, 5번 page는 Physical memory에 존재하기 때문에 valid로 표시
• 6, 7의 G, H는 사용되지 않는 page이기 때문에 invalid로 표시
• page fault 발생 시, CPU는 운영체제로 넘어가게 됨 (page fault trap, 일종의 interrupt)

 

Page Fault

• invalid page를 접근하면 MMU가 trap을 발생시킴 (page fault trap)
  • CPU가 자동적으로 운영체제로 넘어감
• Kernel mode로 들어가서 page fault handler가 invoke 됨
• 다음과 같은 순서로 page fault를 처리한다
  1. Invalid reference? (eg. bad address, protection violation) ⇒ abort process
     • 잘못된 요청인지 확인. (접근 권한, 잘못된 주소 등인지 확인한다)
     • 잘못된 요청이라면 강제로 abort
  2. Get an empty page fram. (없으면 뺏어온다: replace)
  3. 해당 페이지를 disk에서 memory로 읽어온다.
     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을 재개

 

Steps in Handilng a Page Fault

• 위 Page Fault 발생시 처리과정을 시각화한 것임

 

Performance of Demand Paging

• Page Fault Rage 0 ≤ p ≤ 1.0
  • if p = 0, no page faults
  • if p = 1, every reference is a fault
• Effective Access Time
  • (1-p) x memory access + p(OS & HW page fault overhead + [swap page out if needed] + swap page in + OS & HW restart overhead)

 

Free frame이 없는 경우

• Page replacement
  • OS의 업무
  • 어떤 frame을 빼앗아올지 결정해야 함
  • 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
    • page를 다시 사용할 때 발생하는 I/O로 overhead가 크기 때문
  • 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음
• Replacement Algorithm
  • page-fault rate을 최소화하는 것이 폭표
  • 알고리즘의 평가
    • 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사
  • reference string의 예
  • 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 4, 5

 

Page Replacement

• victim: 쫓아낼 frame
• 아래의 역할을 운영체제가 하게 됨

1. victim 선정 후, backing storage에 보관
   • 만약, 값이 변하지 않았다면 그냥 physical memory에서 삭제
   • 값이 변했다면 replace
2. victim에 대한 page table의 valid-invalid bit을 invalid로 변경
3. backing storage에서 가져올 page swap in
4. 가져온 page에 대해 page table의 valid-invalid bit을 valid로 변경

 

Optimal Algorithm

• page fault를 가장 적게 하는 알고리즘
• MIN을 알고 있다는 가정하에 사용되는 알고리즘으로 실제로 사용될 수는 없음
• MIN (OPT): 가장 먼 미래에 참조되는 page를 replace
• 4 frames exmaple

• 빨간색: PageFault의 발생
• 파란색: PageFault 없이 Memory에서 직접 참조
• 총 6번의 Page Fault 발생
• 미래의 참조를 어떻게 아는가?
  • Offline algorithm(실제 사용 불가능)
• 다른 알고리즘의 성능에 대한 upper bound 제공
  • Belady’s optimal algorithm, MIN, OPT 등으로 불림

 

실제 사용 가능한 알고리즘

FIFO( First In First Out ) Algorithm

• 먼저 들어온 것을 먼저 내쫓는 방법의 알고리즘

• FIFO Anomaly (Belady's Anomaly)
  
  • more frames ⇒ less page faults
  • FIFO 알고리즘의 특이한 현상으로, 프레임을 늘렸는데 오히려 성능은 하락하는 현상

 

LRU( Least Recently Used ) Algorithm

• 가장 오래전에 참조(사용)된 것을 지움
• 가장 많이 사용되는 알고리즘

 

LFU( Least Frequently Used ) Algorithm

• 참조 횟수(reference count)가 가장 적은 페이지를 지움
  • 최저 참조 횟수인 page가 여럿 있는 경우
    • LFU 알고리즘 자체에서는 여러 page 중 임의로 선정
    • 성능 향상을 위해 가장 오래전에 참조된 page를 지우게 구현할 수도 있음
• 장점
  • LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
• 단점
  • 참조 시점의 최근성을 반영하지 못함
  • LRU보다 구현이 복잡함

 

LRU와 LFU 예제

 

LRU와 LFU 알고리즘의 구현

• LRU: 최근에 참조된 페이지를 가장 아래로, replace는 위에서부터 구현 시 O(1)의 시간 복잡도
• LFU: heap을 이용하여 트리 형태로 구현 시 O(log n)의 시간 복잡도로 적용 가능

 

 

 

 

 

출처

KOCW :  이화여대 반효경 교수님 <운영체제, 2014>