CS/운영체제

08. Virtual Memory

호프 2023. 11. 30. 03:10

Demand Paging

Demand Paging

  • 실제로 필요할 때 page를 physical memory에 올리는 방법
    • I/O 감소, Memory 사용량 감소, 빠른 응답 시간, 더 많은 process 수용
  • Valid / Invalid bit 사용
    • Invalid = 페이지가 물리적 메모리에 없는 경우, 처음에는 모든 page entry가 Invalid로 초기화

 

Page Fault

Page Fault

  • Invalid page를 접근하면 MMU가 interrupt 발생시킴
  • Kernel mode로 들어가서 page fault handler가 invoke 됨

Page Fault 처리 순서

  1. if invalid reference: abort process
  2. Get an empty page frame (없는 경우 replace = 기존에 존재하는 page를 backing store로 쫓아냄)
  3. 해당 페이지를 disk(backing store)에서 memory로 읽어온다.
    3-1. disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함 (block)
    3-2. Disk read가 끝나면 page table entry에 기록, valid/invalid bit = 'valid'
    3-3. ready queue에 process를 다시 삽입 -> dispatch later
  4. 추후 이 프로세스가 CPU를 잡고 다시 running
  5. 아까 중단되었던 Instruction 재개

 

 

Performance of Demand Paging

Page Fault Rate 0 <= p <= 1.0

  • if p == 0 : no page fault (ex. memory가 매우 커서 page가 모두 올라와 있을 때)
  • if p == 1, every reference is a fault (처음 시작할때)

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

Page Replacement Algorithm

Free Frame이 없는 경우 -> Page Replacement

  • 어떤 frame을 빼앗아올지 결정해야 함 -> Replacement Alogorithm 사용
  • page-fault rate을 최소화하는 것이 목표

Optimal Algorithm

Belady's optimal algorithm, MIN, OPT

  • 가장 먼 미래에 참조되는 Page 를 replace
  • 미래의 참조를 어떻게 아는가? -> offline algorithm (online 컴퓨터에서 적용 못함)
  • 다른 알고리즘의 성능에 대한 upper bound 제공

 

FIFO (First In First Out)

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

  • 메모리가 증가할 수록 page fault가 증가함

 

LRU (Least Recently Used) & LFU (Least Frequently Used)

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

 

LFU: 참조 횟수가 가장 적은 객체를 지움

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

LRU와 LFU 알고리즘의 구현

  • LRU: Linked List로 구현: O(1) complexity
  • LFU: tree구조로 구현 (heap): O(log n) complexity
    • Linked list로 구현하면 O(n) complexity

 

Clock Algorithm

Caching

  • paging system 처럼 한정된 빠른 저장 공간을 가지고 계속적으로 요청되는 새로운 객체를 저장 공간에 읽어들였다가 후속 요청 시 직접 서비스하는 방식
  • 저장 공간 = cache
  • paging system, cache memory, buffer caching, Web caching ...

캐쉬 운영의 시간 제약

  • Replacement Algorithm에서 삭제할 객체를 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
  • Buffer caching이나 Web caching의 경우 O(1) ~ O(log n)정도까지 허용
  • Paging system의 경우: 페이지 요청이 매우 비번하여 O(1)인 LRU 알고리즘도 부담 👉 Clock Alogorithm

Clock Algorithm (= Second chance algorithm, NUR(Not Used Recently), NRU(Not Recently Used))

  • LRU의 근사 알고리즘
  • 동작 방식
    • Reference bit을 사용해서 교체 대상 페이지 선정 (circular list)
    • reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
    • 포인터가 이동하는 중에 reference bit 1은 모두 0으로 바꿈 (first chance)
    • Reference bit가 0인 것을 찾으면 그 페이지를 교체
    • 한 바퀴 되돌아와서도 (=second chance) 0이면 그때에는 replace 당함
    • 자주 사용되는 페이지라면 second chance가 올 때 reference bit = 1일 것이다.
  • 개선 방법
    • reference bit와 modified bit(dirty bit)을 함께 사용
    • refernce bit = 1 : 최근에 참조된 페이지
    • modified bit = 1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지) -> 추후 메모리에서 쫓아내기 전에 디스크에 먼저 써주어야 함

 

Page Frame의 Allocatioin

Allocation problem: 각 process에 얼마만큼의 page frame을 할당할 것인가?

  • 명령어 수행을 위해 최소한 할당되어야 하는 frame 수가 있음
  • Loop를 구성하는 page 들은 한 번에 allocate되는 것이 유리함: 아니면 매 loop마다 page fault 발생할 것이므로

Allocation Scheme

  • Equal allocation: 모든 프로세스에 똑같은 개수 할당
  • Proportional allocation: 프로세스 크기에 비례하여 할당
  • Priority allocation: 프로세스의 priority에 따라 다르게 할당

 

Global vs Local Replacement

Global Replacement

  • Replace 시 다른 process에 할당된 frame을 빼앗아올 수 있음 (메모리 전체를 대상으로 함)
  • Process 별 할당량을 조절하는 또 다른 방법
  • Working set, PFF 알고리즘 사용

Local Replacement

  • 자신에게 할당된 frame 내에서만 replacement

Thrashing

Thrashing

  • 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우 발생
  • Page fault rate 매우 높아짐 -> CPU utilization 낮아짐 -> OS는 MPD (Multiprogramming degree)를 높여야 한다고 판단하고 또 다른 프로세스가 시스템에 추가됨 -> 프로세스 당 할당된 frame 수 더욱 감소 -> 프로세스는 page 의 swap in/out으로 매우 바쁨 -> 대부분의 시간에 CPU는 한가함 -> low throughput

 

Working-Set Algorithm

Locality of reference (참조의 지역성)

  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다.
  • Locality set = 집중적으로 참조되는 해당 page들의 집합

Working-Set Model

  • Working Set: Locality에 기반하여 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번해 메모리에 올라와 있어야 하는 page들의 집합
  • Working Set Model에서는 프로세스의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out (suspend)
  • Thrashing을 방지하고 MPD(Multiprogramming degree)를 결정

Working-Set Algorithm

  • 프로세스들의 working set size 합이 page frame 수보다 큰 경우
    • 일부 프로세스를 swap out시켜 남은 process의 working set을 우선적으로 충족 (MPD를 줄임)
  • Working set을 다 할당하고도 page frame이 남는 경우
    • Swap out 되었던 프로세스에게 working set 할당 (MPD를 키움)
  • Working set을 제대로 탐지하기 위해서는 window size를 잘 결정해야 함
    • window size 너무 작으면 locality set을 모두 수용하지 못할 우려, 너무 크면 여러 규모의 Locality set 수용

 

PFF (Page-Fault Frequency) Schema

PFF

  • page-fault rate의 상한값과 하한값을 두고 상한값을 넘으면 frame을 더 할당하고 하한값 이하이면 할당 frame 수를 줄인다.
  • 빈 frame이 없으면 일부 프로세스를 swap out

 

Page Size의 결정

Page size를 감소시키면

  • 페이지 수, 페이지 테이블 크기 증가
  • Internal fragmentation 감소
  • Disk transfer 효율성 감소
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적 <-> Locality의 활용 측면에서는 좋지 않음

👉 요즘 트렌드: Larger page size

저작자표시 (새창열림)