[OS] Virtual Memory

가상 메모리는 물리 메모리 크기의 한계를 극복하기 위해 나온 기술이다.

Demand Paging

Demand Paging은 필요한 부분만 메모리에 적재하는 것이다. 프로세스를 실행할 때, 실행에 필요한 부분만 메모리에 올린다. 이러한 프로세스의 일부분은 페이지 단위일 수 있고, 세그먼트 단위일 수 있지만 대부분은 페이지 단위 사용한다.

이렇게 현재 필요한 페이지만 메모리에 올리는 것을 Demand Page라고 한다.

위의 그림 과정 설명

1. CPU가 page table에서 해당 page에 접근한다.
2. Invalid page를 접근하면 MMU가 interrupt를 발생시킨다. 
   - 커널 모드로 들어가 page fault handler가 invoke된다.
3, 4. 해당 페이지를 disk에서 찾아 메모리로 읽어온다.
   - disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당한다. (block)
5. page table을 업데이트한다.
   - Disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"
   - ready queue에 process를 insert -> dispatcher later
6. 이 프로세스가 CPU를 잡고 다시 running, 아까 중단되었던 instruction 재개

Performance of Demand Paging

cf) Swapping와 Demanding Paging의 공통점은 둘 다 메모리와 backing store 사이를 서로 오고 가는 기능을 수행하지만, Swapping은 프로세스 단위로 이동하고 Demanding Paging은 페이지 단위로 이동하는 차이점이 있다.

Page Fault Rate 0 <= p <= 1.0
probability of a page fault

• p = 0 : Page fault가 없다.
• p = 1 : 모든 접근이 fault

Effective Access Time

(1 - p) x memory access			// fault 생기지 않은 경우
+ p x (OS & HW page fault overhead) 	// fault 생긴 경우
       + [swap page out if needed]	// frame이 모두 찬 경우, 
       					// 하나를 swap out 시킨다.
       + swap page in
       + OS & HW restart overhead)

Page Replacement

메모리가 부족한 경우(Free frame이 더이상 없는 경우) 다른 프로그램이 새로 실행되거나 실행 중인 프로세스가 다른 페이지를 요구하는 경우 이미 메모리에 있는 페이지 중 하나를 다시 backing-store에 보내고, 새로운 페이지를 메모리에 올려야 한다.
이를 Page Replacement라고 한다. 여기서 backing store로 page out 된 페이지를 victim page라고 한다.

Page Replacement Algorithm

• Optimal Algorithm
  • MIN(OPT) : 가장 먼 미래에 참조되는 page를 replace
  • Offline algorithm으로 다른 알고리즘의 성능에 대한 upper bound를 제공한다.
  • Belady's optimal algorithm, MIN, OPT 등으로 불린다.
• FIFO
  • 먼저 들어온 것을 먼저 내쫓는다.
  • FIFO Anomaly(Belady's Anomaly) : 프레임 수가 증가하면(메모리 용량이 증가) page fault가 줄어드는 것이 정상적이지만, 이는 오히려 증갛하는 이상 현상이 발생한다.
• LRU(Least Recently Used)
  • 가장 오래 전에 참조된 것을 지운다.
  • O(1) complexity - LinkedList로 구현
• LFU(Least Frequently Used)
  • 참조 횟수(reference count)가 가장 적은 것을 지운다.
  • 최저 참조 횟수 페이지가 여러 개면 임의로 선정한다. (성능 향상을 위해 가장 오래 전에 참조된 페이지를 지우게 구현할 수도 있다.)
  • 장점 : LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있다.
  • 단점 : 참조 시점의 최근성은 반영하지 못함, LRU보다 구현 복잡
  • O(logN) complexity - heap 구현
• Clock ( = Second chance = NUR = NRU )
  • LRU 근사 알고리즘
  • Reference bit을 사용해서 교체 대상 페이지 선정(circular list)
    • 최근에 참조된 페이지
    • Reference bit이 0인 것을 찾을 때까지 포인터 하나씩 앞으로 이동
    • 포인터 이동하는 중에 Reference bit 1은 0으로 바꾼다.
      한바퀴 되돌아와서도(=second chance) 0이면 그때는 Replace 당함
    • Reference bit이 0인 것을 찾으면 해당 페이지 Replace
    • 자주 사용되는 페이지라면 second chance가 올 때 1이다.
  • Modified bit(Dirty bit) - Clock 알고리즘 개선
    • 최근에 변경된 페이지(I/O를 동반하는 페이지)
      • backing store에 I/O 수행해야하므로 더 많은 시간이 걸린다.
    • Reference와 Modified bit을 함께 사용한다.

Global vs Local Replacement

• Global Replacement
  • Replace 시 다른 프로세스에 할당된 frame을 빼앗아 올 수 있다.
  • Process별 할당량을 조절하는 또 다른 방법이다.
  • Working set, PFF 알고리즘 사용
• Local replacement : 자신(프로세스)에게 할당된 frame 내에서만 replacement

Allocation of Page Frame(프레임 할당)

각 Process에 얼마만큼의 page frame을 할당할 것인가

• Allocation 필요성
  • 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 페이지 동시 참조
    • 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있다.
  • Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리하다.
    • 최소한의 allocation이 없으면 매 루프마다 page fault가 생기게 된다.
• Allocation Scheme
  • Equal allocation : 모든 프로세스에 똑같은 프레임 개수 할당
  • Proportional allocation : 프로세스 크기에 비레에 할당
  • Priority allocation : 프로세스의 priority에 따라 할당
    (ex) sys > user program)

Thrashing

일반적으로 메모리에 올라가는 프로세스가 증가할수록 CPU의 utilization이 증가할 것이라고 생각하지만 일정 범위를 넘어서면 오히려 CPU utilization이 감소하는 현상이다.

이는 프로세스의 원할한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생한다.

1. OS는 낮은 CPU Utilization을 모니터링한다.
2. OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단하여 다른 프로세스를 메모리에 더 많이 올린다. 이는 프로세스당 할당된 프레임의 수가 감소하게 된다.
3. 프로세스로 인해 page-fault가 발생한다. (프레임(메모리) 부족)
4. 프로세스는 page의 swap in / swap out으로 디스크 I/O 작업이 증가하게 된다. 
5. CPU를 사용하지 않은 작업이기 때문에 그동안 CPU는 아무것도 하지 않게 된다. 
    👉 CPU Utilization 감소

Thrashing 해결법

1️⃣ Working-Set Algorithm

Locality of reference

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

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

working set은 현재 시간에서 일정 시간(△) 이전동안 사용되었던 페이지의 집합이다. △(델타)는 OS 내부에서 정하는 기준에 따라 다르고, 이를 working set window라고 한다.
현재 시간이 t_1이면, working set = {1, 2, 5, 6, 7}이다. 이때 working set의 개수는 총 5개이므로 프레임 또한 5개를 할당하면 된다.

2️⃣ PFF(Page-Fault Frequency)

Page-Fault rate의 상한값과 하한값을 둔다

• Page-Fault rate이 상한값을 넘으면 frame을 더 할당한다.
• Page-Fault rate이 하한값 이하이면 할당 frame을 줄인다.
  • 너무 많은 frame을 할당한 경우이다.

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

Page Size

Page 수를 감소시키는 경우

• 페이지 수가 증가
• 페이지 테이블 크기가 증가 (부담이 커짐)
• Internal fragmentation이 감소 👍
• Disk transfer의 효율성이 감소 👎
  • Seek/rotation vs transfer
• 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
  • Locality 활용 측면에서는 좋지 않다.

최근 트렌드는 Larger page table

• 참고 링크