[운영체제] 9. Virtual Memory (1)

kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다.

1. Demand Paging

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

• I/O 양의 감소
• Memory 사용량 감소
• 빠른 응답 시간 (메모리에서 직접 서비스하는 비율이 높아지므로)
• 더 많은 사용자 수용

Valid/Invalid bit의 사용

• Invalid의 의미
  • 사용되지 않는 주소 영역인 경우
  • 페이지가 물리적 메모리에 없는 경우
• 처음에는 모든 page entry가 invalid로 초기화 
• address translation 시에 invalid bit이 set되어 있으면 page fault 발생

Page Fault

• Invalid page를 접근하면 MMU가 trap(sw interrupt)을 발생시킴 (page fault trap) -> CPU가 OS로 넘어감
• Kernel mode로 들어가서 page fault handler가 invoke 됨
• 다음과 같은 순서로 page fault를 처리한다.
  1. Invalid reference인지 확인 (eg. bad address, protection violation) -> abort process
  2. Get an empty page frame. (없으면 뺏어온다. replace)
  3. 해당 페이지를 disk에서 memory로 읽어온다.
     1. disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함 (block 상태)
     2. Disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"
  4. 이 프로세스가 CPU를 잡고 다시 running
  5. 중단되었던 instruction 재개

 

Performance of Demand Paging

• Page fault rate 0<=p<=1.0 
  • if p=0, no page faults -> 메모리가 엄청 큰 경우
  • if p=1, every reference is a fault -> 처음 시작할 때
  • p는 일반적으로 대략 0.02
• 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 (swapping, OS의 역할)
  • 어떤 frame을 빼앗아올지 결정해야 함 
  • 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
  • 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음 -> 매우 비효율적
• Replacement Algorithm
  • page-fault rate을 최소화하는 것이 목표
  • 알고리즘의 평가
    • 주어진 page replacement string에 대해 page fault를 얼마나 내는지 조사

2. Page Replacement Algorithms

Optimal Algorithm (Belady's optimal algorithm, MIN, OPT)

MIN(OPT): 가장 먼 미래에 참조되는 page를 replacement

미래에 참조를 어떻게 아는가? 

실제 s/w 작동이 불가능하고, 알고 있다는 가정 하에 paper 상에서만 가능한 알고리즘.

Offline Algorithm -> 다른 알고리즘의 성능에 대한 upper bound 제공

 

FIFO (First In First Out) Algorithm

FIFO: 먼저 들어온 것을 먼저 내쫓음

FIFO Anomaly (Belady's Anomaly): more frames  ≠ less page faults. 원래는 frame 수가 늘어나면 메모리에 더 많이 올릴 수 있기 때문에 page fault가 줄어야 하지만, FIFO를 사용하면 page faults도 증가하는 경우가 발생함.

LRU (Least Recently Used) Algorithm

LRU: 가장 오래 전에 참조된 것을 지움

 

LFU (Least Frequently Used) Algorithm

LFU: 참조 횟수(reference count)가 가장 적은 객체를 지움

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

LRU와 LFU 알고리즘의 구현

 

LRU의 경우 swap out 시 가장 위에 있는 LRU Page를 선택하면 된다. search가 필요 없으므로 O(1) complexity를 가진다.

LFU의 경우 count 값을 증가시킨 후 연결되어 있는 노드를 이동해가며 count 값을 계속 비교하여 정렬하는 과정이 필요하므로 O(n)의 complexity를 가진다. Heap으로 구현하면 이진트리의 높이만큼만 비교하면 되므로 O(log n)이 된다.

 

그러나 Paging System에서 운영체제가 LRU, LFU 페이지를 알 수 있는가?

No. 프로세스가 요청한 페이지가 이미 메모리에 있는 경우, CPU가 운영체제로 넘어가지 않고 하드웨어적으로 주소변환한 후 해당 정보만 CPU가 읽어들인다. Page fault가 발생해야만 CPU가 운영체제로 넘어가고, 디스크에 있던 페이지가 메모리에 올라오는 시간 정보를 알 수 있게 된다. 즉 LRU, LFU 페이지를 카운팅하는 일은 운영체제가 해야하는 일이지만 운영체제는 그 정보를 모른다!

다양한 캐슁 환경

• 캐슁 기법
  • Paging system처럼 한정된 빠른 저장 공간을 가지고 계속적으로 요청되는 새로운 객체를 저장 공간에 읽어들였다가 후속 요청 시 직접 서비스하는 방식을 캐슁(caching) 기법이라고 하고 저장 공간을 캐쉬라고 부름
  • 캐슁 기법은 paging system 외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용됨
• 캐쉬 운영의 시간 제약
  • 교체 알고리즘에서 삭제할 객체를 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
  • Buffer caching이나 Web caching의 경우 O(1)에서 O(log n) 정도까지 허용함
  • Paging system인 경우
    • page fault인 경우에만 OS가 관여함
    • 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
    • 페이지 요청이 너무 빈번하여 O(1)인 LRU 알고리즘의 list 조작도 부담

Clock Algorithm

• Clock algorithm (=Second chance algorithm, Not Used Recently 또는 Not Recently Used)
  • LRU의 근사(approximation) 알고리즘
  • Reference bit을 사용해서 교체 대상 페이지 선정(circular list)
  • Reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
  • 포인터 이동하는 중에 reference bit 1은 모두 0으로 바꿈 (First chance)
  • Reference bit이 0인 것을 찾으면 그 페이지를 교체(한 cycle을 돌 동안 사용되지 않는 페이지로 간주)
  • 한 바퀴 되돌아와서도(=Second chance) 0이면 그때에는 replace 당함
  • 자주 사용되는 페이지라면 second chance가 올 때 1로 바뀌어있음 
• Clock algorithm의 개선
  • Reference bit과 modified bit(dirty bit)을 함께 사용
  • Reference bit = 1 -> 최근에 참조된 페이지
  • Modified bit = 1 -> 최근에 변경된 페이지 (I/O를 동반하는 페이지)
  • Modified bit = 0 -> 최근에 수정되지 않은 페이지. invalid로 처리 후 변경되지 않았으므로 backing store에 수정된 내용을 반영해주는 과정이 필요 없음. (백업 시간 절약)

 

 

Reference bit은 HW(MMU)가 관리해줌