9장 Virtual Memory

 

reference: kocw의 반효경 교수님 강의와 권진욱 교수님 강의(대학 정규 수업)
수업을 듣고나서 강의 교재를 타이핑하고 필기한 부분을 추가적으로 정리하였습니다.
웹뷰에서 toc를 제공합니다.
github의 md 파일로 보는 게 편하시다면, 여기로 이동해주시면 됩니다.

---

1 Demand Paging

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

그림에서 제일 오른쪽의 원통형은 backing store로 HDD나 SDD가 이에 해당한다.

프로그램에서 자주 사용되는 부분은 극히 적다. 하지만 자주 사용하는 부분이 재사용 될 확률(hit ratio)가 90% 이상이다. 그래서 필요할 때만 페이지를 메모리에 올리는 것을 효율적이다.

한정된 메모리에서 모든 페이지를 올리는 것보다 필요할 때만 올리는 것이 응답이 빠르다

• I/O 양의 감소
• Memory 사용량 감소
• 빠른 응답 시간
• 더 많은 사용자 수용

Valid / Invalid bit의 사용

• Invalid의 의미
  1. 사용되지 않는 주소 영역인 경우
  2. 페이지가 물리적 메모리(physical memomy)에 없는(올라오지 않은) 경우
  3. 요청한 페이지가 물리적 메모리에 없는 경우 → page fault
• 처음에는 모든 page entry가 invalid로 초기화
• address translation 시에 invalid bit이 set되어 있으면 → Page Fault
• (physical memory에 로딩이 안 되어 있네? 빨리 backing store에서 가져와! 라고 선언하는 것)

2 Page Fault

(① 와 같은 표시는 그림에서의 번호를 표시했습니다)

CPU가 3번 페이지 메모리 접근을 시도해서

① invalid page를 접근하면 MMU(memory manage unit - HW)가 ② trap(interrupt)을 발생시킴 (page fault trap)

kernel mode(OS가 cpu를 잡고 있는 모드)로 들어가서 page fault handler가 invoke됨

다음과 같은 순서로 page fault handler가 page fault를 처리한다.

1. Invalid Reference냐? (eg. bad address, protection violation) → abort(중단) process
2. Get an empty page frame (free frame이 없으면 뺏어온다: replace 알고리즘)
3. 해당 페이지를 disk에서 memory로 읽어온다.
   1. disk I/O가 끝나기까지 해당 프로세스는 CPU를 preempt 당함(Blocked)
   2. ③, ④ Disk read가 끝나면 ⑤ page tables entry 기록, valid/invalid bit = "valid"
   3. ready queue에 Process (Ready) 를 insert → dispatch later
4. 이 프로세스가 CPU를 잡고 다시 Running
5. ⑥ 아까 중단되었던 instruction을 재개

3 Performance of Demand Paging

Page Fault Rate (page fault가 발생하는 비율) 0 ~ 1.0

if p = 0: no page faults

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)

4 Page Replacement Algorithm

Page Replacement

Free Frame이 없는 경우

• 어떤 frame을 빼앗아올지 결정해야 함
• 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
• 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 돌아올 수 있음

Page Replacement Algorithm

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

Optimal Algorithm

• MIN (OPT) : 가장 먼 미래에 참조되는 page를 replace
• 미래의 참조를 어떻게 아는가?
  • Offline algorithm (=실제로 online에서 작동할 수 없다. 미래에 어떤 것이 사용될지 알기 힘들기 때문에)
• 다른 알고리즘 성능에 대한 upper bound 제공
  • Belady's Optimal Algorithm, MIN, OPT 등으로 불림

FIFO (First In First Out) Algorithm

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

FIFO Anomaly (Belady's Anomaly) : more frames → not less page faults, more page faults

역효과가 남. 좋은 알고리즘이 아닌 게 판명됨.

* Anomaly: 변칙이란 뜻

LRU (Least Recently Used) Algorithm

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

그림 설명

1번 page fault가 나서 loading (swap in)

2번, 3번 4번도 page fault가 나서 loading

1번, 2번 있는 것 참조

5번 page를 참조해야하는데 없음. 최근에 사용되지 않은 친구인 3번을 지우고(swap out) 5번을 가져다놓음.

1번, 2번 있는 것 참조

3번 page가 없고, 가장 참조가 적게된 4번과 교체

이렇게 하니 8번의 page fault가 발생했다. 앞선 FIFO 방법보다 낫다는 것을 알 수 있다.

LFU (Least Frequently Used) Algorithm

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

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

LRU와 LFU 알고리즘의 구현

* LRU (참조가 오래전) MRU (참조가 최근)

LRU는 linked list로 구현되었을 시, O(1)

LFU는 count 값에 따라서 정렬을 다시 해야함

새롭게 삽입되는 친구의 위치를 찾아야 함 O(n) 이는 시간이 너무 많이 들고, 조금 더 발전되어서

힙 구조로 O(log n)까지 줄일 수 있음.

5 다양한 caching 환경

caching 기법

• paging system처럼 한정된 빠른 저장 공간을 가지고 계속적으로 요청되는 새로운 객체를 저장 공간에 읽어들였다가 후속 요청시 cache(저장 공간)로부터 직접 서비스하는 방식
• Paging System 외에도 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용

캐쉬 운영의 시간 제약

• 교체 알고리즘(swap in/out)에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
• Buffer caching이나 Web caching의 경우: O(1)에서 O(log n) 정도까지 허용
• Paging System인 경우
  • Page Fault인 경우에만 OS가 관여함
  • 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
  • 페이지 요청이 너무 빈번하여 O(1)인 LRU 알고리즘의 list 조작도 부담

6 Clock Algorithm

• LRU의 근사(approximation) 알고리즘
• 실제 페이징에서 사용하는 알고리즘
• 여러 명칭으로 불림 : second change algorithm, NUR (Not Used Recently), NRU (Not Recently Used)
• Reference bit을 사용해서 교체 대상 페이지 선정 (Circular list)

clock algorithm

• Reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
• 포인터 이동하는 중에 Reference bit 1은 모두 0으로 바꿈 (아직 swap out은 안함)
• Reference bit이 0인 것을 찾으면 그 페이지를 교체 (swap out, 다른 페이지로 swap in)
• 한 바퀴 되돌아와서도(=second chance) 0이면 그때는 replace 당함
• 자주 사용되는(MMU를 통해서 자주 접근되는) 페이지라면 second change가 올 때 1이 유지됨 (MMU가 0에서 1로 바꾸기에)

Clock algorithm의 개선

• reference bit와 modified bit (dirty bit)을 함께 사용 (부담 별로 X)
• reference bit=1 : 최근에 참조된 페이지
• modified bit=1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지) → 0이면 백업 과정 생략

7 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에 따라 다르게 할당

8 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 별로 운영시

9 Thrashing

• Thrashing의 사전적 의미: 뒹굴다, 굴리다
• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생

degree of multiprogramming: 프로세스의 개수 / CPU utilization:얼마나 사용하고 있는가

여러개의 프로그램이 동시 올라갈수록 cpu 이용률이 높아진다.

그런데 어느 순간부터 프레임이 부족하게 되면 계속 Page fault가 나서 계속 backing store에 접근을 해야하는 I/O가 발생한다. 그러면 어느 순간 cpu는 일하는 시간이 적어져 이용률이 뚝 떨어진다. 이것을 Thrashing이라고 한다.

쉽게 말해 cpu가 프로세스를 수행해야할 시간에 오래 걸리는 I/O 작업 때문에 일정 시간 못쓰게 되는 현상이다.

1. Page Fault Rate이 매우 높아지고 CPU Utilization이 낮아짐
2. OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단
3. 또 다른 프로세스가 시스템에 추가됨 (Higher MPD)
4. 프로세스 당 할당된 frame의 수가 더욱 감소 - 악순환

따라서 프로세스는 page의 swap in / swap out으로 매우 바쁨

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

결론적으로, low Throughput

10 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을 방지함
  • 왜? page fault를 줄일 수 있기 때문
• Multiprogramming degree를 결정함
  • 어떻게? 통째로 메모리에서 내려가 있으면 Multiprogramming degree (프로세스의 개수)를 낮추게 됨.

Working Set Algorithm

그림: 한마디로 working set인 1,2,5,6,7을 한 그룹으로, 3.4를 한 그룹으로 paging (swap in/out) 해주는 것이 좋다.

Working Set의 결정

• Working Set Window를 통해 알아냄
  • window는 볼 수 있는 시야, 시각 의 뜻
• Window Size가 ∆인 경우
  • 시각 t에서의 working set WS(t)
    • Time Interval [t-∆, t]사이에 참조된 서로 다른 페이지들의 집합
  • Working Set에 속한 page는 메모리에 유지, 속하지 않은 것은 버림
  • (즉, 참조됨 후 ∆시간 동안 해당 page를 메모리에 유지한 후 버림)

Working-Set Algorithm

1. Process들의 working set size의 합이 page frame의 수보다 큰 경우
   • 일부 process를 swap out 시켜 남은 process의 working set을 우선적으로 충족시켜 준다 (MPD를 줄임)
   • 쉽게 말해 MPD을 줄여 하나라도 돌려야지~
2. Working set을 다 할당하고도 page frame이 남는 경우
   • Swap out 되었던 프로세스에게 working set을 할당 (MPD를 키움)
   • multi programming degree를 키워 더 많은 working set이 들어오도록 해준다고~

Window size

(를 결정하는 것이 매우 중요하다 !)

• Working set을 제대로 탐지하기 위해서는 window size를 잘 결정해야 한다.
• ∆ 값이 너무 작으면 locality set을 모두 수용하지 못할 우려가 있다.
• ∆ 값이 크면 여러 규모의 locality set 수용할 수 있다.
• ∆ 값이 ∞이면 전체 프로그램을 구성하는 page를 working set으로 간주하는 것과 같다.

11 PFF (Page Fault Frequency) Scheme

Page Fault의 빈도를 보고 frame 할당 부분을 조절하자!

*# of frames: application에 할당한 frame의 수

frame 수가 적으면, 즉 메모리 사이즈가 작다면 page-fault가 많이 발생 (A라는 어플에 할당된 frame 수가 너무 작다!)

Page Fault Rate의 상한값과 하한값을 둔다.

• Page Fault Rate이 상한값을 넘으면 frame을 더 할당한다.
• Page Fault Rate이 하한값 이하이면 할당 frame 수를 줄인다.

빈 frame이 없으면 일부 프로세스를 swap out

12 Page Size의 결정

page는 일반적으로 4K

Page Size를 감소시키면 (= 메모리를 잘게 자름)

• 페이지 수 증가
• 페이지 테이블 크기 증가 (cpu는 page table을 통해 page에 접근)
• Internal Fragmentation 감소 (남는 친구들)
• Disk Transfer의 효율성 감소
  • Seek/Rotation (여러번 찾기에 증가) vs Transfer (전송 시간은 감소)
  • 일반적으로 Seek/Rotation 이 훨씬 길기에 효율성 감소
• 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
  • Locality의 활용 측면에서는 좋지 않음

Trend : Larger Page Size

하지만 트렌트는 트렌드일 뿐, 장단점을 파악하고 있고, 주어진 상황에 알맞는 page size를 선택해야 한다.