Virtual Memory

Demand Paging

필요할 때 Page를 메모리에 올리는 것

• I/O 감소

• Memory 사용량 감소

• 빠른 응답 시간

• 더 많은 사용자 수용

• Valid / Invalid Bit 사용
• Invalid의 의미
• 사용되지 않는 주소 영역인 경우
• Page가 물리적 메모리에 없는 경우
• 처음에는 모든 Page Entry가 Invalid로 초기화
• Address Translation 시에 Invalid Bit이 Set 되어 있으면
→ Page Fault

Memory에 없는 Page의 Page Table

Page Fault 루틴

• Invalid Page를 접근하면 MMU가 Trap을 발생시킴(Page Full Trap)

• Kernel Mode로 들어가서 Page Fault Handler가 Invoke됨

• Routine
• Invalid Reference? (eg. Bad Address, Protection Violation) → Abort Process
• 빈 Page Frame을 가져온다. (없으면 뺏어온다: Replace)
• 해당 페이지를 Disk에서 Memory로 읽어온다.
• Disk I/O가 끝나기까지 이 프로세스는 CPU를 Preempt 당함(Block)
• Disk Read가 끝나면, Page Tables Entry 기록, Valid/Invalid Bit = Valid
• Ready Queue에 Process를 Insert → Dispatch Later
• 이 프로세스가 CPU를 잡고 다시 Running
• 아까 중단되었던 Instruction 재개

Demand Paging 성능

• Page Fault Rate 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
• 어떤 frame을 빼앗아올지 결정해야 함
• 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
• 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음

• Replacement Algorithm
• page fault rate를 최소화하는 것이 목표
• 알고리즘의 평가
• 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사

Page Replacement

Optimal Algorithm

미래를 다 알고있다고 가정했을 때 최적의 알고리즘

• 실제 시스템에 사용 불가

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

• 4 frames example

• 미래의 참조를 어떻게 아는가
• Offline Optimal Algorithm

• 다른 알고리즘의 성능에 대한 Upper Bound 제공
• Belady’s Optimal Algorithm, MIN, OPT 등으로 불림

FIFO Algorithm

• FIFO Anomaly(Belady’s Anomaly)
• Page Frame을 늘려줘도 성능이 나빠짐

LRU(Least Recently Used) Algorithm

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

• O(1) Time Complexity

LFU(Least Frequently Used) Algorithm

참조 횟수(Reference Count)가 가장 적은 페이지를 지움

• 최저 참조 횟수인 page가 여럿 있는 경우
• LFU 알고리즘 자체에서는 여러 page 중 임의로 선정
• 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있음

• Heap을 사용하면 O(log n) Time Complexity

• 장점
• LRU처럼 직전 참조 시점만 보는 것이 아니라, 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음

• 단점
• 참조 시점의 최근성을 반영하지 못함
• LRU보다 구현이 복잡

Example of LRU and LFU

Implementation of LRU and LFU

• 단순히 제일 최근으로 옮기면 되기 때문에 시간 복잡도 낮음

다양한 캐싱 환경

캐싱 기법

한정된 빠른 공간에 요청된 데이터를 저장해두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식

• 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 조작조차 불가능

Paging System에서 LRU, LFU 가능한가?

페이징 시스템에선 사용 불가능

• Page Fault인 경우에만 OS가 정보를 알고 관여할 수 있음

• 페이지가 이미 메모리에 존재하는 경우, 참조 시각 등의 정보를 OS가 알 수 없음

• O(1)인 LRU의 list 조작조차 불가능

Clock Algorithm

LRU의 근사(Approximation) 알고리즘

• Second Chance Algorithm

• NUR(Not Used Recently) or NRU(Not Recently Used)
• Reference Bit을 사용해서 교체 대상 페이지 선정(Circular List)
• Reference Bit이 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
• 포인터 이동 중, Reference Bit 1은 모두 0으로 바꿈
• Reference Bit이 0인 것을 찾으면, 그 페이지로 교체
• 한 바퀴 되돌아와서도(Second Chance) 0이면 그 때는 Replace 당함
• 자주 사용되는 페이지라면, Second Chance가 올 때 1

• Clock Algorithm의 개선
• Reference Bit과 Modified Bit(Dirty Bit)을 함께 사용
• Reference Bit = 1: 최근에 참조된 페이지
• Modified Bit = 1: 최근에 변경된 페이지(I/O를 동반하는 페이지)

Page Frame의 Allocation

각 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 등의 알고리즘을 Process 별로 운영 시

Thrashing

프로세스의 원활한 수행에 필요한 최소한의 Page Frame 수를 할당 받지 못해 Page Fault가 많이 발생하는 상황

• Page Fault Rate가 매우 높아짐

• CPU Utilization이 낮아짐

• OS는 MPD(Multi Programming Degree)를 높여야 한다고 판단

• 또 다른 프로세스가 시스템에 추가됨(Higher MPD)

• 프로세스 당 할당된 Frame의 수가 더욱 감소

• 프로세스는 Page의 Swap In / Swap Out으로 매우 바쁨

• 대부분의 시간에 CPU는 한가함

• Low Throughput

Working-Set Model

Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야하는 Page들의 집합

• Locality of Reference
• 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다.
• 집중적으로 참조되는 해당 Page들의 집합을 Locality Set이라 함

• 이 모델에서는 Process의 Working-Set 전체가 메모리에 올라와 있어야 수행이 되고, 그렇지 않을 경우 모든 Frame을 반납한 후 Swap Out(Suspend)

• Thrashing을 방지

• Multi Programming Degree를 결정함

Working-Set Algorithm

• Working-Set의 결정
• Working-Set Window를 통해 알아냄
• Window Size가 Δ인 경우
• 시각 ti에서의 Working-Set WS(ti)
• Time Interval[ti - Δ, ti] 사이에 참조된 서로 다른 페이지들의 집합
• Working-Set에 속한 Page는 메모리에 유지, 속하지 않은 것은 버림 (즉, 참조된 후 Δ 시간 동안 해당 Page를 메모리에 유지한 후 버림)

• Process들의 Working Set Size의 합이 Page Frame의 수보다 큰 경우
• 일부 Process를 Swap Out 시켜 남은 Process의 Working Set을 우선적으로 충족시켜준다. (MPD를 줄임)
• Working Set을 다 할당하고도 Page Frame이 남는 경우
• Swap Out 되었던 프로세스에게 Working Set을 할당(MPD를 키움)

• Window Size Δ
• Working Set을 제대로 탐지하기 위해서는 Window Size를 잘 결정해야 함
• Δ값이 너무 작으면 Locality Set을 모두 수용하지 못할 우려
• Δ값이 너무 크면 여러 규모의 Locality Set 수용
• Δ이 무한대면, 전체 프로그램을 구성하는 Page를 Working Set으로 간주

PFF(Page-Fault Frequency) Scheme

Working Set을 추정하는 것이 아니라, Page Fault Rate를 직접 보면서 조절

• Page-Fault Rate의 상한값과 하한값을 둔다.
• Page Fault Rate가 상한 값을 넘으면, Frame을 더 할당한다.
• Page Fault Rate가 하한 값 이하이면, 할당 Frame 수를 줄인다.

• 빈 Frame이 없으면, 일부 프로세스를 Swap Out

Page Size의 결정

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

• Trend
• 최근에는 4kB 보다 큰 Larger Page Size

출처