반효경 운영체제 - 8. 가상 메모리

Demand Paging

• 실제로 필요할 때 page를 메모리에 올리는 것
  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용
• Valid/Invalid bit의 사용
  • Invalid의 의미
    • 사용되지 않는 주소 영역인 경우
    • 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 page entry가 invalid로 초기화
  • address translation 시에 invalid bit이 set되어 있으면 → “Page Fault” 발생
    • Page fault trap이 발생하여 운영체제로 권한이 넘어간다.

Page Fault

• invalid page를 접근하면 MMU가 trap을 발생시킨다.(page fault trap)
• Kernel mode로 들어가서 page fault handler가 invoke된다.

1. Invalid reference? (잘못된 주소, 권한이 없는 접근) → 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”
   3. ready queue에 process를 insert → dispatch later
4. 이 프로세스가 CPU를 잡고 다시 running
5. 아까 중단되었던 instruction을 재개

Performance of Demand Paging

• Page fault rate 0≤ p ≤ 1.0
  • page fault 비율이 0이면, 페이지 폴트가 발생하지 않는다.
  • 1이라면 모든 참조에서 발생한다.
• 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(페이지를 쫓아내기)
  • 어떤 frame을 빼앗아올지 결정해야함
  • 곧바로 사용되지 않을 page를 쫓아내는 것이 좋다.
  • 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 들어올 수 있다.
• Replacement algorithm
  • page fault를 최소화하는 것이 목적
  • 알고리즘의 평가
    • 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사
  • reference string의 예
    • 1,2,3,4,1,2,5,1,2,3,4,5

Optimal Algorithm

• MIN (OPT) : 가장 먼 미래에 참조되는 page를 replace
• 미래의 참조를 어떻게 아는가? → Offline algorithm(안다는 가정하에)
• 다른 알고리즘의 성능에 대한 upper bound 제공
  • Belady’s optimal algorithm, MIN, OPT 등으로 불린다.

FIFO(First In First Out) Algorithm

• 먼저 들어온 것을 먼저 내쫓음
• FIFO Anomaly(Belady’s Anomaly)
  • 프레임이 늘어났는데 page fault가 오히려 더 늘어나는 현상이 발생할 수 있다.

LRU(Least Recently Used) Algorithm

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

LFU(Least Frequently Used) Algorithm

• 참조 횟수가 가장 적은 페이지를 지움
  • 최저 참조 횟수인 page가 여럿 있는 경우
  • 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다.
• 장단점
  • LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있다.
  • 참조 시점의 최근성을 반영하지 못함
  • LRU보다 구현이 복잡함

LRU와 LFU 알고리즘 구현

• LRU
  • Doubly-Linked-List 타입으로 쫓아낼 때/새로 참조할 때 O(1) complexity으로 구현된다.
• LFU
  • Doubly-Linked-List 타입으로 동일하게 구현할 수 있지만, 새로운 참조시 다른 원소들과 비교를 해야하므로 worst-case O(n)이다.
  • 따라서 Heap으로 구현하여 삽입/제거 시 O(log n) 시간 복잡도로 구현한다.

다양한 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

• LRU의 근사 알고리즘
• 여러 명칭으로 불림
  • Second chance algorithm
  • NUR (Not used recently) 또는 NRU(Not recently Used)
• Reference Bit을 사용해서 교체 대상 페이지 선정 (circular list)
• reference bit이 0인 것을 찾을 때까지 포인터를 하나 씩 앞으로 이동
• 포인터 이동하는 중에 reference bit 1은 모두 0으로 바꿈
• Reference bit이 0인 것을 찾으면 그 페이지를 교체
• 한 바퀴 되돌아 와서도 0이면 그때는 replace 당함(second chance)
• 자주 사용되는 페이지라면 second chance가 올 때 1
• 개선
  • reference bit과 modified bit(dirty bit)을 함께 사용
  • reference bit = 1 : 최근에 참조된 페이지(read)
  • modified bit = 1 : 최근에 변경된 페이지(write로 참조되는 경우, I/O 동반 페이지)
    • modified가 0이면 수정이 안되었으므로 메모리에서 제거하기만 하면 된다.

Page frame의 allocation

• Allocation problem : 각 process에 얼마만큼의 page frame을 할당할 것인가?
• Allocation의 필요성
  • 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 페이지 동시 참조
    • 명령어 수행을 위해 최소한 할당하는 frame의 수가 있음
  • Loop을 구성하는 page는 한꺼번에 allocate되는 것이 유리함
    • 최소한의 allocation이 없으면 매 loop마다 page fault
• Allocation Scheme
  • Equal allocation : 모든 프로세스에 동일한 개수 할당
  • Proportional allocation : 프로세스 크기에 비례하여 할당
  • Priority allocation : 프로세스의 priority에 따라 할당

Global vs Local Replacement

• Global replacement
  • Replace시 다른 process에 할당된 frame을 빼앗아 올 수 있다.
  • Process별 할당량을 조절하는 또 다른 방법임
  • FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당
  • Working set, PFF 알고리즘 사용
• Local replacement
  • 자신에게 할당된 frame 내에서만 replacement
  • FIFO, LRU, LFU 등을 프로세스 별로 운영 시

Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우 발생
• page fault rate가 매우 높아짐
• CPU utilization이 낮아짐
• OS는 MPD(Multiprogramming degree)를 높여야한다고 판단
• 또 다른 프로세스가 시스템에 추가됨 (higher MPD)
• 프로세스 당 할당된 frame의 수가 더욱 감소
• 프로세스는 page의 swap in / swap out으로 매우 바쁨
• 대부분의 시간에 CPU는 한가함
• 메모리에 프로그램을 1개(다른 프로그램 실행할 때마다 I/O해서 CPU 사용률이 낮음), …, 3개… 100억개(page frame 수가 모자라 I/O만 기다리게됨) 올리는 경우

Working-set model

• Locality of reference
  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다.
  • 집중적으로 참조되는 해당 page들의 집합을 locality set이라고 한다.
• Working-set model
  • Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와있어야 하는 page들의 집합을 working set이라고 한다.
  • Working Set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납 후 swap out(suspend)
  • Thrashing을 방지함
  • Multiprogramming degree를 결정

Working-set algorithm

• Working set의 결정 : 과거 Delta 시간 동안 참조된 데이터를 working-set(window)라고 본다.

PFF (Page-Fault Frequency) Scheme

Page Size의 결정

• Page Size를 감소시키면
  • 페이지 수 증가
  • 페이지 테이블 크기 증가
  • Internal Fragmentation 감소
  • Disk transfer 효율성 감소
    • Seek/rotation vs. transfer
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
    • Locality 활용 측면에서는 좋지 않음
• Trend
  • Larger page size

•