[Operating System] Virtual Memory 2

Allocation of Frames

process가 실행될 때 할당되는 frame의 개수

• local replacement : frame 할당식
• global replacement : 전체 frame 사용

각 process는 실행되기 위해 최소한의 page가 필요하다.

• HW 측면 : kernel instruction을 실행하기 위한 최소한의 page가 필요
  • MOVE 명령어의 경우, instruction 저장을 위한 2page, source data 2page, dest data 2page 총 6 page가 필요
    ⇒ 아무리 작은 데이터도 운이 좋지 않게 2 page에 걸쳐서 저장될 수 있으므로
• SW 측면 : loop 내의 page는 한 번에 allocate되어야 한다.
  • locality를 보장할 수 있어야 한다.

Fixed Allocation

1. equal allocation : 각 process에 균등하게 page를 할당
2. proportional allocation : process의 크기에 비례해 page를 할당

• $a_1,a_2=?$

Priority allocation

process의 priority에 따라 page를 할당

• high priority process → more memory → finish early

💡 위의 방식 모두 locality를 고려하지 않고 page를 할당한다는 문제점이 있다.

 

Thrashing

thrashing : 특정 시점에서 갑자기 page-fault rate가 급격히 올라가는 현상

 

다음과 같은 과정으로 인한 악순환이 반복

1. page-fault로 인해 I/O 연산이 많아짐
2. CPU utilization이 낮아짐
3. CPU utilization이 낮아 long-term scheduler가 MPD(Multi-Programming Degree)을 높힌다.
4. MPD가 높아져 각 process 별 할당받을 수 있는 memory(page)의 수가 줄어든다.
5. page-fault rate가 다시 증가

thrashing이 발생하는 이유

$\sum\text{size of locality}>\text{total allocated memory size}$

$\sum\text{size of locality}>\text{total allocated memory size}$

• locality 덕분에 page/cache를 사용할 수 있다.
  ⇒ 계층화 구조의 필수 조건

locality

• Temporal Locality(시간지역성) : 방금 참조된 것이 금방 다시 참조될 확률이 높다.
  ⇒ loop, subroutine …
• Spatial Locality(공간지역성) : 방금 참조된 것의 주변이 참조될 확률이 높다.
  ⇒ array, 순차실행 …

\

1. 공간지역성
2. 시간지역성

Working-set Model

working-set model : active하게 실행되는 page를 찾아내는 기법

 

working-set window : 현재를 기점으로 몇 번째까지 정보를 참고할 것인지를 설정

• memory 접근 횟수를 기준

 

working-set(WS) : 현재 active하게 실행되는 page

• window size가 작을 경우, 실제 active page를 포함할 수 없다.
• window size가 클 경우, 현재 active page가 아닌 것도 포함

working-set size(WSS) : ws의 사이즈

 

total demand frames(D) : 전체 process의 locality page를 memory에 올리기 위한 frame의 수

m : total number of available frames

$D>m$인 경우 thrashing이 발생할 수 있다.

• 따라서 $D>m$인 경우 process를 suspend해 MPD를 낮춰준다.

• replacement 시 victim을 결정할 수 있다.
  • WS에 포함되지 않은 page 중 하나의 page를 victim으로 선정
• allocation 시 현재 WS 사이즈 만큼의 page를 할당받음으로써 locality를 고려해 동적으로 page를 할당받을 수 있다.
• WS의 page를 모두 할당받을 수 없는 경우에는 해당 process를 suspend시키는 방식

Implementation of Working set

base

각 page를 참조할 때마다 WS을 수정해줘야 한다.

• 각 page가 참조될 때마다 time I/O를 통해 time stamp를 기록
• time stamp를 비교해 현재 시간과 가장 가까운 window size 만큼의 page를 WS로 설정

⇒ 실제로 사용이 불가능

approximate with interval timer + a reference bit

$\Delta=10k$라고 하고, R-bit 1개와 Additional Reference bit가 2개가 있다고 가정

1. 가장 초기 R-bit를 1로 설정한다.
2. timer interrupts를 5k time마다 발생시킨다.
3. timer interrupts가 발생할 때마다 bit를 left shift을 해주고, R-bit를 0으로 만든다.
4. 해당 page가 참조되면 R-bit를 1로 setting

이렇게 함으로써 window size 동안 해당 page가 reference되었는지 안되었는지를 time stamp 없이 알 수 있게 된다.

• 위 bit 중 한 개라도 1인 경우 WS에 포함

단점

실제 window size와의 오차가 존재

• 위 가정에서 window size=10k인 반면에, R-bit = 0~4999, AR1 = 5000~9999, AR2 = 10000~14999 동안 bit가 유지되므로 14.9k 동안 유지된 page도 WS에 포함될 수 있게 되는 문제점이 발생

이러한 오차를 줄이기 위해서는 AR bit 수를 눌리고 time interrupt 간격을 줄임으로써 해결할 수 있다.

 

💡 working set model에서 window size를 각 process마다 적절하게 정해주는 것이 필요한데, 이것이 어렵다. 따라서 실제로 적용가능한 방법은 아님

 

Page-Fault Frequency Scheme

특정 process의 working set을 고려하지 않고, 단순히 해당 process의 page-fault rate를 확인함으로써 현재 process가 어떤 상황인지 짐작할 수 있다.

• page fault rate이 지나치게 높다면, 해당 process에 frame을 더 할당
• page fault rate이 지나치게 낮다면, 해당 process에 할당된 frame을 회수

• 해당 PFF 기법은 특정 process의 page fault 시에만 해당 process의 page fault rate을 수정시켜줌으로써 필요한 정보를 갱신시킬 수 있다.
• working set에서는 page 참조 시마다 working set을 수정시켜줘야 하는 것에 비해 overhead가 훨씬 적다.
• working set은 allocation과 replacement에서 둘 다 사용할 수 있지만, replacement는 LRU를, allocation은 PFF를 사용하는 것이 훨씬 간단

Other benefits of VM

Copy-on-Write(CoW)

child와 parent가 기본적으로 page를 공유하고, write가 발생하면 그제서야 수정된 page만 copy를 하는 것

• 원칙적으로는 process creation 시 두 process는 같은 내용을 복사해 가지고 있는다.
• CoW에서는 process creation 시(fork, exec) 기본적으로 모든 내용을 share해 가지고 있고, 특정 page에 write이 발생하면 그 때 copy를 하는 방식을 사용
• process creation이 매우 효율적으로 동작한다.

process creation 시

page c에 write가 발생 시

 

💡 virtual memory를 사용함으로써 process는 자신의 page가 공유되어 있는지 아닌지를 모른 상태로 os가 memory를 공유시킬 수 있어 더욱 효율적으로 memory 관리가 가능해짐

 

memory-mapped files

특정 page에 disk block을 mapping 방법

1. 초기 file read가 발생하면 disk에서 읽어온 뒤, page size만큼의 file을 page에 저장하게 된다.
   • 즉, file에 memory가 부여됨
2. 다음 file read부터는 cpu는 해당 file이 memory에 존재하는 것처럼 동작
3. file access를 memory access와 마찬가지로 취급해 파일에 접근할 수 있게 된다.
   • read(), write() 등의 system call을 호출하지 않아도 되므로 overhead가 감소

Other Issue

Prepaging

• 처음 process가 시작될 때 page fault가 많이 발생하는 현상을 막기 위함
• process가 시작될 때, 앞으로 참조할 것 같은 page를 미리 올려놓는다.
• prepage가 많다고 반드시 좋은 것은 아니다.
  • 올려놓은 뒤 사용되지 않으면 I/O와 memory가 낭비됨

page size

page size가 작은 경우

1. internal fragmentation이 감소
   • 마지막에 남는 공간이 더 적으므로
2. locality를 더 섬세하게 얻을 수 있다.
   • 정말 필요한 부분만 locality page로 가져갈 수 있으므로
3. address translation overhead가 증가
   • page의 개수가 많아지므로 TLB에서 page lookup할 때 효율성이 떨어짐
4. page table size 증가
   • page의 개수가 많아지므로
5. I/O 횟수가 많아지고 효율성이 떨어진다.
   • page size가 작기 때문에 한 번 I/O 연산을 할 때, 가져오는 데이터의 크기가 작으므로

따라서 page size가 작은 경우 장점도 있지만 단점이 훨씬 많기 때문에 일반적으로 page size가 큰 것이 좋다

⇒ 지나치게 크지만 않으면 된다!

⇒ 또 최근에는 page size를 여러 단위로 두기도 함

TLB Reach

TLB Reach : TLB가 접근할 수 있는 memory의 크기

 

• 전체 TLB size에 각 entry가 1개의 page 주소를 갖고 있으므로, TLB가 접근할 수 있는 memory의 크기는 위와 같다.

TLB reach를 늘릴 수 있는 방법

1. TLB size를 증가
2. page size를 증가
   • 단점 : internal fragmentation 증가

program structure

program이 데이터를 어떤 식으로 저장하는지에 맞춰 코드를 짤 필요가 있다.

• int data[128][128]에 각 row가 1 page에 저장이 된다고 가정
• 전체 free frames의 수가 128보다 작다고 한다.

Q1. page fault의 수

• 정답 : 128 * 128 = 16.384 page faults가 발생 

 

Q2. page fault의 수

• 정답 : 128 page faults가 발생

I/O interlock

몇몇 page는 특정 시간동안 victim이 되지 않을 수 있도록 설정할 수 있어야 한다.

따라서 page에 lock(pin)을 걸어 victim이 되지 않도록 할 수 있어야 한다.

예시

usb → cpu → disk로 데이터를 쓸 때, usb의 데이터가 모두 page로 올라간 뒤 disk에 쓰여지기 위해서 중간에 해당 page가 victim이 되어서는 안된다.