Virtual Memory

: logical memory를 physical memory로 부터 분리시켜주는 역할로 메모리가 실제 메모리보다 더 많아보이게 만들어준다.

• 이론적으로는 모든 process의 address space가 memory에 올라와 있어야 하지만, 실제로는 Program이 실행될 때 CPU가 access하는 부분만 memory에 올라가 있으면 된다.
  $\Rightarrow$ 메모리 낭비 X + 동시 실행 가능한 process의 개수 증가
• 여러 program들에 의해 주소 공간이 공유될 수 있게 만들어준다
  e.g) fork : 자식의 부모의 address space를 공유 $\rightarrow$ 복사할 필요 없이 공유하면 됨
• 더 효율적인 process 생성이 가능하다
• Page들이 swap in/out 되도록 만들어주어야 한다.

이를 가능하게 만들어주는 것이 Demand Paging과 Demand Segmentation이다.

Demand Paging

: CPU가 실제로 page에 access 할 때 해당 page를 memory에 올리는 기법

장점

• I/O가 덜 필요하다
• Memory 사용량이 줄어든다
• 반응 속도가 빨라진다
• 동시에 많은 process를 실행할 수 있다.

Demand Paging의 경우 reference bit로 이 page를 memory에 올릴지 말지를 결정한다. Reference bit의 경우 이 page가 memory에 올라가 있는지 여부와 합법적인 접근을 하고 있는지에 대한 정보를 담고 있다. 그 이유는 이미 memory에 올라가 있는 경우 또 다시 memory에 올릴 필요가 없고 그렇지 않은 경우 demand paging에 의해 memory로 올려야 하기 때문이다. 또한 만약 CPU가 다른 process의 page를 참조하고 있다면 invalid reference이기 때문에 abort 해주어야하기 떄문이다.

Lazy Swapper

: CPU가 사용할 부분만 swapping을 하는 방법으로 page가 필요하기 전까지는 전혀 swap을 하지 않다가 필요성이 생겼을 때 page 단위로 swap in/out 한다.

Valid/Invalid bit

위에서 demand paging의 경우 valid/invalid bit로 올바른 참조를 하고 있는지를 나타낸다고 언급했었다. 이에 대해 자세히 알아보도록 하자.
Valid/Invalid bit의 경우 각각의 PTE (Page Table Entry)마다 존재한다. Bit가 valid인 경우는 올바른 참조를 하고 있다는 의미로 이미 memory에 존재하는 page를 나타낸다. 만약 invalid일 경우, 이 경우는 3가지 case로 구분된다.

Invalid

1. logical address > process size
   : page가 process의 주소 공간 안에 있지 않아 잘못된 주소 접근을 하고 있는 경우
2. 메모리에 올라가 있지 않은 경우
3. Obsolete
   : Memory에 올라가 있고 합법적인 주소 영역을 갖고 있음에도 invalid 표시가 되어 있는 page이다. 이는 Memory에 올라가 있는 page의 data를 같은 page를 복사한 다른 누군가가 update를 했는데 원본의 경우 update가 되어 있지 않아 obsolete 상태로 존재하고 있는 경우를 일컫는다.
   이러한 경우 update를 해서 memory에 올려야 한다.

만약, address translation 도중에 page가 invalid 상태라면 이 경우는 "page fault"로 처리를 한다.

Page Fault

: 잘못된 page를 접근하면 MMU trap (page fault trap)이 발생한다. Page fault trap의 경우 OS의 page fault handler가 처리를 하는데 이 과정은 다음과 같다.

1. Page table 조회
   - 만약 illegal reference (e.g. 잘못된 주소 접근, protection violation) 라면 process를 abort 시킨다.
   - Not in memory라면 계속 진행한다.

2. Frame 확보
   : 비어있는 frame이 있는 경우 그 frame을 확보하고, 만약 비어있는 page frame이 존재하지 않는 다면 swap in/out으로 빈 frame을 만들어준다.

3. Disk에서 page 읽기
   - I/O가 끝날 때까지 process는 'wait' 상태로 대기한다.
   - disk I/O가 끝나면 PTE의 frame 개수와 valid/invalid bit가 update 된다.
   - Process를 ready queue로 옮긴 뒤 나중에 dispatch한다.

4. CPU Scheduler가 process에게 CPU를 할당하면 page fault trap이 종료된다.

5. Page fault가 발생한 시점부터 instruction을 다시 시작한다.

이 과정을 그림으로 나타내면 다음과 같다.

Performance of Demand Paging

Page Fault Rate

$0\le p\le 1.0$

• $p=0$ : No page fault
• $p=1$ : 모든 참조가 곧 page fault

EAT (Effective Access Time)

$\text{EAT} = (1-p) *\text{memory access} + p*(\text{page fault overhead}+[\text{swap page out if needed]}+\text{swap page in}+\text{restart overhead})$

Demand paging의 예시를 들면,

• Memory access time = 200ns
• Average page-fault service time = 8ms

$\text{EAT}=(1-p)*200+p*8ms=200+p*7,999,800ns$

이런 값이 나온다. 이 말인 즉슨 1000번 page fault가 발생하면 $\text{EAT}$는 $8.2\mu s$라는 의미이다. 이게 별로 안커보일 수도 있는데 생각을 해보면 일반적인 memory access time이 $200ns$인 것을 감안하면 거의 40배나 느려진다는 의미가 된다. 따라서 $\text{EAT}$를 줄이기 위한 다른 방법이 필요하다.

이에 locality를 적용하게 되었다.

locality의 경우 free frame이 없을 때 page replacement algorithm을 통해 victim page를 선정할 때 사용된다. Replace를 할 때 아무 page나 선택하게 되면 worst case의 경우 방금 swap out 된 page를 바로 직후에 참조하게 되면 page fault가 발생하게 되기 때문에 최대한 page fault 횟수를 줄이면서 page를 교체하기 위해 locality가 사용된다.

Page Replacement Algorithm

Page Replacement Algorithm의 경우 다음과 같은 과정으로 진행된다.

1. Disk에 존재하는 원하는 page의 위치를 찾는다.
2. Free frame을 찾는다.
   • 만약 free frame이 존재한다면 그냥 그걸 쓰면 되고
   • 그렇지 않다면 page replacement algorithm으로 victim frame을 찾는다.
3. Page를 free frame에 가져온 뒤, page와 free frame table을 update 한다.
4. Process를 재시작한다.

FIFO (First-In-First-Out) Algorithm

Scheduling이든 Page replacement든 어딜가던지 FIFO는 빠질 수 없는 대표적인 알고리즘이다.
FIFO algorithm의 동작과정을 보면 다음과 같다.

1,2,3,4,1,2,5,1,2,3,4,5 순서대로 참조를 하고 각각 3개와 4개의 page frame이 존재한다.
첫 번째 3개의 frame이 있는 경우 9번의 page fault가 발생한다. 그런데, 4개의 frame이 있는 경우 일반적인 상식으로는 더 많은 frame이 존재하기 때문에 3개일 때 보다 더 적게 page fault가 발생할 것이라고 생각을 하지만 10번의 page fault로 3개일 때 보다 더 많이 발생한 것을 확인할 수 있다.

따라서 FIFO는 적합하지 않다는 결론에 도달한다.

Optimal Algorithm

사실 이 알고리즘의 경우 '신'이 존재한다는 가정하에 가장 최적의 알고리즘을 찾는 방식이다. 다시 말해 앞으로 일어날 일들을 모두 알고 있다는 가정하에 다음에 참조될 page는 victim으로 선정하지 않고 제일 나중에 접근될 page나 접근될 일이 없는 page를 victim으로 선정하여 page fault의 횟수를 최소화하는 알고리즘이다.

이 경우, 6번의 page fault로 FIFO보다 훨씬 적은 page fault가 발생한다는 것을 확인할 수 있다. 그러나, 미래에 어떤 page가 쓰이고 안쓰일지는 아무도 모르기 때문에 이 알고리즘은 현실적으로 구현이 불가능하다.

LRU (Least Recently Used) Algorithm

그래서 나온 알고리즘이 그 유명한 LRU algorithm이다.
이 알고리즘의 경우 Optimal algorithm과 이론적으로 유사하지만, 미래를 예측할 수 없다는 단점을 보완하기 위해 과거에 page에 대한 접근 형태를 보고 미래에 접근될지 안될지를 예측하는 알고리즘이다. 그렇기 때문에 victim page의 경우 가장 최근에 사용되지 않은 page가 선택되게 된다.

이 경우 6개인 optimal 보다는 많지만 9개인 FIFO 보다는 적은 8번의 page fault가 발생한다.

그렇다면 LRU algorithm은 어떻게 구현해야할까?
LRU가 완벽해보이지만, 단점들이 존재한다.

단점

1. 모든 page마다 최근 접근 동향을 파악하기 위한 timestamp가 필요하기 때문에 추가적인 memory traffic이 발생할 가능성이 높다.
   (timestamp가 가장 작은 page를 찾아야 하기 때문에 $O(n)$의 시간 복잡도가 발생한다.)
2. Space/Time overhead가 과도하게 커진다.

결론적으로 overhead가 너무 커진다는 문제점이 존재한다. 따라서 LRU보다 성능은 뒤떨어지지만 overhead를 줄일 수 있는 Approximation model이 필요하다.

LRU Implementation Algorithms

1. Counter Implementation
   : 모든 page entry가 counter를 갖고 있어서 memory 참조가 발생할 때마다 증가한다.

• A page가 접근되게 되면 CPU counter를 A의 counter로 복사한다.
• Replacement를 할 때, 가장 작은 counter를 갖고 있는 page를 찾는다.
  • 각각의 memory에 접근할 때마다 추가적인 counter를 적어야하기 때문에 overhead가 존재한다.
  • Replacement를 할 때 가장 작은 counter를 가진 page를 찾는데 걸리는 overhead가 존재한다.
  • Counter를 저장하기 위한 space overhead가 존재한다.

2. Stack Implementation
   
   

: Page number의 stack을 double link 형태로 관리한다.

• A page가 참조되면,
  • A를 top으로 이동시킨다.
  • 이 과정에서 pointer를 6번이나 바꿔야 한다.
  • 그러나, replace를 할 때 탐색을 하지 않아도 된다는 장점이 있다.

LRU Approximation Algorithms

Reference bit

• 각각의 page의 reference bit은 0으로 초기화 되어 있따.
• page가 참조가 될 때 1로 변경
• reference bit가 1인 경우 접근한 적이 있는 page이므로 victim 선정 과정에서 배제하고 0인 page를 victim으로 선정한다.
  • 그러나 이 경우 reference bit가 0이라는 정보만 존재하기 때문에 0인 page들 중 어떤 page가 참조 된지 더 오래되었는지 구분할 방법이 었다.

Additional Reference bit

• Reference bit에서의 단점을 보완하기 위해 추가적으로 8 bit의 reference bit를 추가한다.
• Reference bit은 주기적으로 가장 높은 순서의 bit 쪽으로 shift 된다.
• 가장 낮은 순서의 bit를 버린다.
• Ex )
  00000000 : 한번도 접근된 적 없는 page
  10101010 : 2 주기 단위로 접근되는 page

Second chance (clock) algorithm

• Reference bit가 필요함
• Circular queue of pages
• Reference bit=0인 page를 찾을 때까지 pointer를 이동시킴
  (한 번도 참조가 된 적이 없다는 의미)
• Pointer가 가리키는 page의 reference bit가 1인 경우
  • Page가 memory에서 나갈 수 있도록 reference bit를 0으로 설정
  • 시계 방향으로 이동하면서 같은 규칙으로 page를 replace

특징

• Pointer가 이동하는 도중에 reference bit이 1인 page는 전부 0으로 변경
• Pointer가 한 바퀴 돌고 나서 다시 같은 위치로 왔을 때 (second chance)도 reference bit가 0이면 한 바퀴 돌 동안 참조된 적이 없다는 의미이므로 replace 시킴
• 자주 사용되는 page라면 second chance가 올 때 reference bit가 1이다
• Worst case의 경우 모든 page의 reference bit가 1이면 FIFO로 replace 시킴

Enhanced Second chance algorithm
Reference bit + Modify bit
(0,0) : 최근에 사용 x, 수정 x $\rightarrow$ 가장 먼저 replace
(0,1) : 최근에 사용 x, 수정 o $\rightarrow$ 전자만큼 좋진 않음, replacement 전에 반드시 백업(write out)
(1,0) : 최근에 사용 o, 수정 x $\rightarrow$ 곧 사용될 예정
(1,1) : 최근에 사용 o, 수정 o $\rightarrow$ 곧 사용될 예정, replacement 전에 반드시 백업(write out)

Frame Allocation

Fixed Allocation

Equal Allocation

• 각각의 process에게 같은 수의 frame들을 할당
  e.g., $\#\text{frame}=100, \#\text{Process}=5\Rightarrow 20 \text{ pages each}$

Proprotional Allocation

• Process의 size에 비례하기 frame을 할당

  $s_i = \text{size of process } p_i$

  $S=\Sigma s_i$

  $m = \text{total }\#\text{frames}$

  $a_i=\text{allocation for }p_i={s_i\over S}*m$

  $m=64, s_i=10, s_2=127$ 일 때
  $a_1={10\over137}*64\sim5$
  $a_2={127\over137}*64\sim59$

Priority Allocation

Priority Allocation의 경우 proportional allocation을 사용한 방법이지만, process의 size 대신 priority를 사용하는 할당 방식이다.

더 높은 우선순위를 갖는 process의 경우 더 많은 memory를 할당해서 더 빨리 끝날 수 있도록 해준다. 이렇게 될 경우 I/O의 횟수가 감소하고 그에 따라 I/O를 기다리기 위해 'waiting' 상태로 존재하는 시간도 줄어들게 된다.

만약 process $P_i$가 page fault를 발생시킨다면

• $P_i$의 frame들 중 victim을 선택한다
• 더 낮은 우선순위를 갖는 process의 frame을 victim으로 선택한다

Global vs Local Replacement

1. Global Replacement

: 모든 process의 page frame을 대상으로 page를 교체하는 방법

• Circular queue의 크기가 커지지만 system-wide로 1개의 circular queue만 존재하면 된다.

<특징>
1. 공유 memory frame
: 모든 process가 사용할 수 있는 page frame을 공유
$\Rightarrow$ 특정 process가 필요로 하는 page를 load 하기 위해 다른 process의 page를 교체할 수 있음
2. 자유로운 선택
: page replacement algorithm이 victim page를 선택할 때 system-wide 하게 page를 고려할 수 있다.
3. 유연성
: process 간에 memory를 동적으로 사용하도록 조정할 수 있기 떄문에 memory utilization이 증가한다.
$\Rightarrow$ 특정 process가 더 많은 page를 필요로 할 때 다른 process의 page를 사용할 수 있다.
4. 복잡성
: System-wide하기 때문에 구현이 복잡하다

---

<장점>
1. Memory Utilization 증가
2. Process가 요구하는 memory size가 다를 때 flexible하게 대처 가능

---

<단점>
1. 하나의 process의 page가 다른 process에 의해 replace 될 수 있기 떄문에 특정 process의 성능을 예측하기 어려워질 수 있음
2. Process끼리 간섭이 발생할 수 있음

2. Local Replacement

: 특정 process의 page frame만을 대상으로 page replacement를 실행하는 방법

• Circular queue가 각각의 process마다 존재해야 한다.

<특징>
1. Independent memory frame
: 각 process는 고정된 수의 page frame을 할당 받는다
2. Process limitation
: 각각의 process는 자신의 Page replacement로 독립적으로 page를 관리한다
e.g. A process - FIFO / B process - LRU
3. 단순성
: 특정 process의 page 내에서만 교체가 이뤄지기 때문에 구현이 단순하다
4. 격리
: Process간 간섭이 없기 때문에 한 process의 성능이 다른 process에 의해 영향을 받지 않는다

---

<장점>
1. Process간 간섭이 없기 때문에 안정적이다
2. 성능 예측이 편리하다
3. Page Replacement Algorithm이 단순하다

---

<단점>
1. Memory utilization 효율이 비효율적일 수 있음
e.g. 많은 page를 필요로 하는 process가 추가적인 page frame을 할당 받지 못할 수도 있음
2. 전체 system의 memory 사용량이 바뀔 때 flexible하게 대처하기 힘듦

Thrashing

만약 1개의 process에게 할당된 page frame의 개수가 과도하게 적을 경우 아무리 좋은 victim을 선정한다고 할 지언정 급격한 page-fault의 발생을 막을 수 없다.

• CPU utilization 감소
• OS ... degree of multiprogramming을 증가시켜야 한다고 생각
  * degree of multiprogramming : Long-term scheduler가 관리
• 또 다른 process가 system에 추가된다 (degree of multiprogramming 증가)

Thrashing

: Process가 page를 swap in/out 시키느라 바쁘다
$\rightarrow$ CPU는 이 시간동안 놀게 되기 때문에 throughput이 감소하게 된다.


Thrashing을 그래프로 표현하면 위와 같다. $x$축은 degree of multiprogramming, $y$축은 CPU utilization이고 일정 기간 그래프가 증가하다가 어느 순간 급감하게 된다. 그 이유를 수식으로 표현하면, $\Sigma\text{size of locality}\gt\text{total allocated memory size}$이기 때문에 thrashing이 발생해서 CPU utilization이 급감하게 되는 것이다.

Locality

여기서 Locality의 크기가 할당된 memory size의 합보다 클 때 thrashing이 발생한다고 했는데, 그럼 locality란 무엇일까? 지금까지 locality는 꽤나 많이 등장한 개념이다. 위에서도 언급이 되었었지만, page replacement algorithm에서의 locality는 가장 최근에 참조된 page를 의미했다. Locality의 경우 쉽게 말해 한 놈만 팬다를 생각하면 쉽다.

Temporal Locality

: 현재 참조된 메모리가 가까운 미래에도 참조될 가능성이 높음
e.g. loop, subroutine, stack

Spatial Locality

: 하나의 메모리가 참조되면 주변의 메모리가 계속 참조될 가능성이 높음
e.g. Array Traversal, 명령의 순차적인 실행

Working-Set Model

$\Delta=\text{Working-set window}=\text{fixed number of page references}$

: Memory에 올라온 page들 중 일을 하고 있는 (CPU가 access하는) page들의 집합

$WS(t_i)=\lbrace\text{pages referenced in} \lbrack t_i, t_i-\Delta \rbrack\rbrace$

: 만약 페이지 P가 $t_i$일 때 $WS(t_i)$에 속하였다면 keep in memory 상태를 유지하고 그렇지 않으면 memory 밖으로 보내버린다. 또한 $WS(t_i)$가 모두 보장 되어야만 run을 하고 그렇지 않으면 suspend시킨다.

• $\Delta$가 너무 작으면 locality에는 포함되는데 WS에는 포함되지 않을 수도 있다.
• $\Delta$가 너무 크면 현시점 ($t_i$)의 locality가 아닌 page가 WS에 포함될 수도 있다.
• $\Delta=\infin$인 경우 전체 program을 넘게 된다.

$WSS_i=\text{Working set size for process }P_i$

$D=\Sigma WSS_i=\text{total demand frames}$

만약, $D\gt m$인 경우 Thrashing이 발생하게 된다 ($m=\text{total number of available frames}$. 따라서 process들 중 하나를 suspend시킨 뒤 $D\le m$이 될 때까지 이 과정을 반복한다.

Copy-On-Write (COW)

: Page를 공유하고 있는 경우 공유하고 있는 page에 write하지 않고 copy본에 write하는 방식이다.
예를 들어, fork()에 의해 부모와 자식이 memory 상에서 같은 page를 공유하고 있는 경우 둘 중 하나의 process가 공유하고 있는 page를 수정하게 되면 그 순간 page를 복사해서 복사한 page에 수정을 하게 하는 방식이다.

이를 그림으로 나타내면 아래와 같다.

Write를 하지 않는 경우 위와 같이 page를 공유하고 있다가

Process1이 Page C를 수정하려고 하면 Page C의 복사본을 만들어서 Process1은 복사본에서 write 작업을 하고 Process2는 그대로 Page C를 참조하고 있게 만든다.

Memory-Mapped Files

Memory-mapped file I/O

: File의 내용을 memory에 mapping해서 File I/O를 memory access 처럼 다루게 한다.

<장점>
1. 메모리 접근 속도로 file에 접근할 수 있기 때문에 file I/O의 성능이 크게 향상된다
2. Array나 pointer를 통해 file 내용을 쉽게 다룰 수 있다.
3. OS의 Cache나 Virtual Memory를 사용하면 더 효율적인 I/O 관리가 가능하다

---

<단점>
1. Mapping된 file의 크기만큼만 memory를 사용하기 때문에 file의 크기가 클 경우 공간이 부족할 수도 있다.
2. 여러 process들이 같은 file을 mapping하여 접근하게 될 경우 synchronization 문제가 발생할 수도 있다.
3. OS마다 구현이 다르기 때문에 호환성이 떨어진다.

이렇게 Virtual Memory에 대해 알아보았다. 내용이 굉장히 많다....
그래도 Virtual Memory가 운영체제에서 차지하는 비중이 무시할 수 없기 때문에 반드시 알아둬야할 개념임에는 분명하고 이해를 해야 한다.

다음 posting에서는 File-system에 대해 다루도록 하겠다.

긴 글 읽어주셔서 감사합니다😊