9. Virtual Memory

Motivating Example

n의 주소를 출력하는 예시

• 만약 두 사람이 동일한 프로그램을 동시에 실행 시켰다고 했을 때 결과가 어떻게 되는가?

  결과가 같다.

출력되는 주소는 physical memory가 아니라 logical(virtual) memory이다. 즉 누가 수행하더라도 동일한 logical address가 출력되게 된다. 즉 programmer입장에서는 logical address만 다루게 된다.

💡

logical address는 compile하는 과정에서 이미 결정되어 있다.

Virtual Addresses

Process의 address space는 virtual(logical) address이다. physical address와는 별개이다. logical address는 cpu architecture에 의해서 결정된다.

💡

CPU가 만들어내는 instruction은 virtual address이다.

결국 logical address를 physical address를 바꾸긴 해야한다. 이러한 translation을 hardware하고 OS에 의해서 진행되게 되는 것

기본적으로 partitioning , paging, segmentation 을 이용해서 진행하게 되고, HW와 OS의 지원이 필요하게 된다. (MMU, TLB, Page tables)

Virtual Memory (VM) Techniques

Key concept

Separation of user logical memory from physical memory

Advantages

1. 다른 프로세스와 주소 공간이 철저하게 분리된다. (즉 해당 process에 할당된 page만을 page table을 통해 access할 수 있으므로 protection 효과가 생기는 것이다.)

2. 특정 파일이나 address space를 공유할 수 있다.

   → 예를 들어 paging이나 segmentation의 entry를 공유할 수 있음

3. physical한 memory가 작더라도, physical memory보다 더 큰 logical address를 가지는 여러 process를 실행할 수 있다. (가장 큰 장점)

   → Process의 전체 address space를 physical memory에 다 담지 않고 수행할 수 있기 때문에 가능한 것. (생각해보면 runtime에 process image 전체가 다 필요한 것은 아니기때문에 일부만 physical memory상에 존재해도 무방하다.)

   예를 들어 32bit machine이라서 logical address space는 4GB이지만, 실제 physical ram의 크기는 1GB밖에 안된다고 가정하자. 그래도 1GB보다 큰 process를 실행할 수 있다는 것.

💡

이거를 구현하는 방법이 demand paing이다. 물리 메모리가 부족하고, 많은 process가 이러한 물리 메모리를 공유하고 있는 상황이므로, 필요한 page만 physical memory에 넣겠다는 것.

Demand Paging

Simple paging을 기초로 해서 효율적으로 메모리 관리를 하자는 것

• Simple paging과의 차이점은 무엇인가? (점검)

  Simple paging은 process와 관련된 page가 돌아가기 전에 모두 다 main memory에 있게끔 하는 것이다. 만약 공간이 부족한 경우, 다른 page를 swap-out시킨다.

핵심 아이디어 : Bring a page into memory only when it is needed.

💡

paging 개념 자체는 process의 image를 contiguous하게 physical memory에 저장하지 않아도 되게끔 하는 기법에 불과하다.

즉 내 process에 있는 모든 page를 physical frame에 넣지 않고, PC가 access하고 있는 page만 적절히 physical frame에 넣겠다는 것.

→ 즉 paging system with page-level swapping을 하겠다는 것!

필요없는 page는 하드디스크로 swap-out시키고, 필요한 page는 swap-in되는 것.

💡

이전까지의 swapping은 process 단위로 진행되었다.

즉, OS는 main memory를 page cache로 사용하는 것 (그래서 hit-ratio가 중요해짐)

1. 초기에는 physical frame에 page를 할당한다

2. 만약 physical memory가 다 차면, 특정 page를 swap-out시키고 원하는 page를 swap-in시킨다. (Overhead가 작게끔 swap-out시키는 것이 중요해짐)

   💡

   위 개념은 page-fault 개념과 page 교체 정책과 관련이 되어있다.

이러한 방법을 사용하면, 특정 page는 disk로 swap-out되어야 하고, 이러한 작업은 OS에 의해서 진행된다. (overhead가 발생하게 된다.)

💡

dirty인 경우에만 write가 요구된다. dirty가 아닌 이상 disk에 있는 정보와 동일할 것이기 때문이다.

컴파일된 image는 하드디스크에 존재한다. 위 사진에서 볼 수 있는 것처럼, 모든 page가 전부 다 physical frame에 존재하는 것은 아니다.

💡

valid-invalid bit : 1이면 physical frame에 존재하는 것이고, 0이면 physical frame에 존재하지 않는 것 (해당 정보는 page table에 존재한다.)

• 나머지 빈 frame은 어디에 사용되는가?

  다른 process가 동시에 사용할 수도 있다.

예를 들어 page1 즉 B를 access를 하려고 하면 physical frame에 존재하지 않음. 이러한 경우를 page fault라고 한다. 이 경우에는 일단 interrupt가 발생하고, 이후 하드디스크에 있는 page B를 swap in하고 page table 업데이트 과정을 거친 뒤 계속 진행되게 된다.

사실 page table의 entry는 2개의 부분으로 구분되어있다.

1. Frame number : 20bit

2. 여러 bit를 써서 status 정보를 가지고 있음(access 여부, dirty 여부, 등등) : 12bit

status bit중에 present bit(valid bit)는 해당 page가 physical frame에 존재하는지에 대한 정보를 가지고 있다. 해당 값이 1이면 해당 page가 physical frame에 존재한다는 의미이고, 0이면 해당 page가 physical frame에 존재하지 않는다는 의미이다.

결국 해당 page를 access 하려면 page table을 참고해서 해당 page가 들어있는 physical frame을 참고해야 되는데, 만약 present bit가 0이면 page fault 가 발생한 것.

Page fault handling

사실 page fault는 모든 page를 physical frame에 저장해두는 것이 아니므로 필연적으로 발생할 수 밖에 없다. (여러 process들도 physical memory를 공유한다는 점을 비춰봤을 때, physical memory는 부족할 수 밖에 없다.)

💡

page fault의 정의 : physical frame에 할당이 되지 않은 page를 CPU가 access하는 상황에 발생하는 문제

1. 만약 access하려고 하는 page가 physical frame에 존재하지 않는 경우(i.e. present bit가 0인 경우), cpu내에 있는 MMU라는 hardware가 해당 사실을 인지하고 exception signal를 보낸다.

2. exception signal이 발생하면 user mode에서 kernel mode로 mode switching한 뒤, 해당 page를 storage에서 가져와서 physical RAM에 적재를 한다.

3. page table을 업데이트 한다. (frame number update하고 present bit를 1로 바꾼다.)

4. Handler가 faulted process를 재시작시킨다.

• 해당 page가 physical한 storage 어디에 있는지를 어떻게 알 수 있는가?

  page table entry의 frame number의 위치에 하드디스크의 주소를 저장해둔다. 정확하게는 page가 swap-out될 때, OS는 present bit를 0으로 바꾸고, 해당 page를 하드디스크의 swap space(swap file)에 저장해둔다. 그리고 해당 주소를 frame number에 해당하는 곳에 저장해둔다.

• 만약 page-fault가 발생했지만, 빈 frame이 없는 경우에는 어떻게 하는가?

  기존에 사용되고 있던 특정 frame을 eviction해야 한다.

  → 어떤 기준으로 할 것인지가 page replacement algorithm이 되는 것

위 그림은 Demand paging을 사용하는 상황에서 page-fault가 발생했을 때의 procedure를 나타낸 것이다. 쉽게 확인할 수 있는 것처럼, page-fault가 발생하게 되면 많은 하드웨어 overhead가 발생하게 된다.

• page-fault가 일어날 수 있음에도 불구하고, 왜 demand paing가 쓰이고 있는가?

  Locality때문이다. Program의 control flow를 보면, 적절하게 localize되어 있다.

  1. Temporal locality(시간적인 지역성): locations referenced recently tend to be referenced again soon (즉 최근에 참고한 위치는 다시 참조하는 경향성이 존재한다.)

  2. Spatial locality(공간적인 지역성): locations near recently referenced locations are likely to be referenced soon (최근에 참조한 위치 근방으로 곧 참조하는 경향성이 존재한다.)

  💡

  즉 locality때문에 overhead가 큰 page-fault가 생각보다 자주 일어나지 않는다.

하지만, page-fault가 일어나는 것은 다음과 같은 것에 의존적이다.

1. Degree of locality in application

   → Locality는 program의 특성이다.

2. Page replacement policy

3. Amount of physical memory

4. Application’s reference pattern and memory footprint

   → 프로그램의 특성에 따라 locality의 정도가 결정된다는 의미

   💡

   a memory footprint is the amount of main memory that a program uses or references while running.

Virtual Memory Performance

시간 : service the page-fault interrupt + Read in the page (이게 오래 걸림) + Restart the process

1. Memory access time : 100ns

2. Disk access time : 25 ms

💡

m, $\mu$, n 순으로 간다. (밀리, 마이크로, 나노)

Effective Access Time (EAT)

p : the probability of a page fault

$$EAT = 100*(1-p) + 25000000 * p$$

만약 10%의 degradation을 감수하겠다고 가정했을 때 p가 엄청나게 낮다.

💡

즉, page fault가 발생할때마다 엄청난 overhead가 발생한다. 그렇기 때문에 OS가 page replacement를 잘해야한다. 결과적으로 physical frame이 Locality 을 반영해주면 된다. 나중에 working set 만 잘 관리해주면 된다는 이슈로 변하게 된다.

Page replacement

해당 process가 원하는 page를 physical frame에 넣어야 하는 것이 목표. 만약 다 차 있다면, 어떤 것을 swap-out 시킬 것인지?

→ OS 입장에서는 replacement를 최소한으로 하고 싶은 것 (즉 page-fault가 작게끔 page replacement가 되는 것이 목표)

→ But 미래의 일이기 때문에 예측을 해야하는 문제가 발생한다.

💡

Replacement에 들어가는 overhead가 크다.

💡

victim에 해당하는 page table의 frame쪽에 swap space의 주소를 저장해놓음

그래서 어떤 기준 으로 page replacement 교체정책을 설정할 것인지

→ Metric은 page fault가 일어나는 횟수 (즉 page fault가 잘 안나게끔 교체정책을 펴는 것이 목표)

💡

이상적으로는 앞으로 안 쓸 page를 swap out시키는 것이 좋으나, 그러한 정보는 알 수 없음.

Belady’s proof

가장 나중에 참조가 될 page를 evicting시키는 것이 page fault의 개수를 줄인다는 것을 증명함

💡

이것도 사실 알 수 없으므로 non-feasible함

Page Replacement Algorithms

• Goal : lowest page-fault rate

• Algorithms
  1. Optimal algorithm : 사실상 구현할 수 없음
  2. FIFO algorithm : physical RAM에 먼저 들어온 page부터 swap-out
  3. LRU (Standard) algorithm : Least recently used 즉 최근에 이용을 잘 안한 page를 swap-out시키자
  4. Clock algorithm : LRU와 유사한 algorithm
  5. Counting-based. algorithm

Optimal Algorithm (Ground Truth)

Approach

Replace the one that will not be used for the longest period of time

Problem

Requires the knowledge of the future

→ Therefore, impossible to implement

FIFO Algorithm

Approach

Replace the oldest

(위 그림에서 맨 처음에 a, b, c, d 순서대로 들어왔다고 가정)

Belady’s Anomaly

일반적으로 frame의 개수가 증가하면 page fault의 rate는 높아지지 않는다고 생각

→ 하지만 FIFO의 경우에는 frame을 더 줘도 page fault가 오히려 늘 수도 있다.

💡

$\text{More Frame}\ne\text{Better performance for the FIFO algorithm}$

즉 system 관점에서 적절한 page replacement algorithm이 아니다.

LRU (Least Recently Used) Algorithm

Approach

Replace the page that has not been used for the longest time

💡

현재 쓰는 page replacement algorithm은 기본적으로 LRU의 변형이다.

Implementation

Counter

매 page가 access된 시간을 따로 저장해둠

Stack

참조된 page를 stack의 top에 둔다.

→ Replace는 stack의 가장 바닥에 있는 것을 하면 된다.

💡

구현은 되지만, overhead가 굉장히 커짐.

→ LRU를 그대로 구현하지 말고, LRU 흉내를 나되 implementation이 간단하게끔 효율적으로 짜자는 식으로 방향으로 진행하게 됨 (Approximate computing)

Hardware Support for Replacement

page table에 존재하는 reference bit 를 잘 활용하자

→ 해당 page가 한번이라도 read/write가 되었는지 여부를 저장해놓는 bit이다. (해당 값은 MMU가 알아서 참조하면 1로 세팅함)

💡

결과적으로 reference bit가 0인 page를 swap out시키고 싶은 것.

위 내용을 활용해서 approximiate LRU를 구현하고 싶은 것 (성능은 그렇게 떨어지지 않으면서, 구현의 overhead를 줄이는 것이 목표)

1. Sampled LRU

2. Clock algorithm (Second-chance)

💡

앞에서 살펴본 counter based나 stack based는 정확히 LRU를 제대로 구현하는 방법이지만, overhead가 크다. 그래서 앞으로 나오는 것들은 LRU를 approximate하고자 하는 것.

LRU Approximation : Sampled LRU

모든 페이지마다 reference byte 를 추가로 가짐. (물론 이것도 overhead이다)

time interval마다 reference bit를 검사해서, Reference byte의 앞에 붙인다.

(기존의 reference bit는 0으로 초기화시킨다.)

💡

Reference byte의 값이 가장 작은 page들을 먼저 swap-out시켜주면 된다. (즉 가장 이전에 쓰였다는 것이므로)

💡

LRU는 매 memory access할 때마다 tracking하는 반면, sampled LRU는 매 interval 동안의 LRU를 판단한다는 점에서 approximate한 것이다.

LRU Approximation : Clock(Second-Chance) Algorithm

기본적으로 FIFO이지만, recently referenced page에 대해서는 다시 한번 더 기회를 주는 것 (한바퀴를 돈다는 개념이 FIFO와 연관되어 있다.)

1. page가 참조가 되면 reference bit가 1이됨

2. page fault가 발생하면 clock이 돌아가면서 reference bit가 0인 page를 고름

3. 만약 해당 reference bit가 1이면 0으로 초기화한다.

💡

다시 올 때까지 reference가 안된 page들은 결과적으로 swap-out 될 것이다.

첫번째 bit : valid bit

두번째 bit : reference/used bit

마지막 bit : frame number

💡

clock은 시계방향으로만 돈다.

위 상황에서는 reference bit가 1이기 때문에 넘어가고, 해당 reference bit를 0으로 바꾸게 된다.

→ 위 상황에서는 page 1이 swap out이 된다.

💡

만약 또 page fault가 발생한 경우, 마지막에 멈춘 곳을 기준으로 다시 진행된다.

Replace a page that has not been referenced for one complete revolution of the clock.

LRU Approximation : Two-handed Clock Algorithm (Solaris 2)

Solaris2에서는 clock Algorithm에 변형한 algorithm을 사용함

여기서는 clock-hand를 2개를 사용하고, fronthand와 backhand의 간격은 고정이다. 즉 해당 간격안에 reference된 page는 살아남게 되는 것.

fronthand(resetting pointer) : reference bit를 0으로 만드는 역할

backhand(examining pointer) : reference bit가 0인 page를 swap-out시키는 역할

→ 간격을 넓힐수록 기회를 더 주는 것이고, 좁힐수록 위급한 상황인 것. (상황에 따라서 조정할 수 있게 됨)

💡

scan하는 속도는 scanrate 에 의해서 결정되고 slowscan 부터 fastscan 까지 가능하다.

Procedure

정확하게는 모든 frame이 할당되고 나서 swap-out시키는 것이 아니라, OS는 일정량의 빈 frame을 확보하고 있다. (사실 그래서 page fault가 났을 때 빈 frame이 상항 존재한다.). lotsfree 값에 따라서 얼마나 많은 free frame을 미리 확보해둘 것인지 결정하게 된다. free frame이 lotsfree 보다 작으면 kernel이 page out 절차를 진행하게 된다.

Counting Algorithms

이거는 LRU 계열은 아님. page당 counter를 두고, reference될 때 마다 counter가 증가시킨다. counter값을 기준으로 swap-out 시키는 기준을 결정하겠다는 것.

LFU (Least Frequently Used) Algorithm

Counter값 중 가장 작은 것을 희생하겠다.

MFU (Most Frequently Used) Algorithm

Counter값이 큰 것을 희생하겠다. (가장 많이 쓰인 page를 희생하자.)

• 무슨 의도인가?

  프로그램의 초기 부분에 memory access를 많이 한다. 그 과정에서 counter값이 많이 증가가 된다. 만약 이 과정에서 LFU를 쓰게 되면 해당 page는 쫓아지지 않는다는 단점을 가진다. 그래서 MFU에서는 counter값이 큰 것은 쓸만큼 썼으니까 swap-out하자는 느낌으로 이해하면 된다.

  → counter의 값이 적은 것일수록 아직 덜 쓴 것이므로 추후에 더 많이 쓰일 것 같다는 발상의 전환

Allocation of Frames

프로세스가 결과적으로 frame을 공유하면서 발생하는 문제에 대해서 고려해야 한다. 이때 각 architecture(ISA)별로 process당 필요한 minimum number of pages가 달라진다. 다시 말해서 process별로 최소 얼마만큼의 page를 담보해 줄 것인지를 결정해야 한다.

Local Replacement (Fixed allocation)

자기 process에 할당된 frame 중 하나를 내쫓는 것

💡

각 process별로 할당된 frame이 고정되어있다. 할당된 frame 내부에서 처리해야하는 것이다.

💡

frame을 할당하는 방식에는 equal allocation과 proportional allocation이 있다.

하지만 이 방식은 프로세스의 메모리 요구 사항이 동적으로 변경될 수 있는 현대의 시스템에서는 문제가 될 수 있다. 예를 들어, 한 프로세스가 현재 필요하지 않는 메모리를 많이 가지고 있을 때, 다른 메모리를 많이 필요로 하는 프로세스는 그 메모리를 사용할 수 없게 된다. 그래서 등장한 개념이 Global replacement 이다.

Global Replacement (Priority allocation)

자기보다 약한 process의 frame을 뺏는 것

💡

즉, local replacement와 달리 모든 frame이 교체의 대상에 들어갈 수 있게 된다.

현실적으로는 필요에 의해서 할당을 하면서

1. 자기 process 내부에서 처리하려고 노력.

2. 정 안되면 마지막으로 다른 process의 frame을 뺐는 것

Thrashing

degree of multiprogramming : 현재 얼마나 많은 process가 돌고 있는지

일반적으로 degree of multiprogramming이 커짐에 따라 CPU utilization이 증가하지만, 너무 커지게 되면 오히려 확 떨어지게 된다.

→ 이러한 현상을 thrashing이라고 한다. (Each process is busy moving pages in and out)

💡

즉 계속해서 page in and out만 반복하고 CPU utilization은 떨어지는 상황이다.

• 왜 이런 현상이 발생하는가?

  Page fault가 너무 많이 발생하기 때문이다. 즉 demand paging대비 frame이 적은 것. 대부분의 page가 page-fault된 것. (I/O 하는데 대부분 이용됨)

  즉 size of actively used pages > total memory size

  physical frame의 개수보다 현재 돌고있는 process의 locality를 커버하는 page의 개수가 더 많기때문에 발생하는 것

💡

Memory manage 관점에서는 thrashing이 일어나지 않게끔 해야 한다.

그래서 thrashing이 일어날 조건이 발생하지 않게끔 process를 관리하겠다는 것

위 그림에서 볼 수 있는 것처럼 locality를 가진다.

→ 즉 locality를 커버할 수 있을만큼의 frame을 확보해주면 된다.

이러한 thrashing을 해결하는 방법에는 크게 2가지가 존재한다.

1. Working-set Model

2. Page-Fault frequency Allocation

Working-Set Model

Set of actively used pages = Working Set

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

→ 과거에 얼마만큼의 working set을 고려할 것인지

💡

Working set의 크기는 일반적으로 주어진 window size 내에서 서로 다른 참조된 페이지의 개수로 정의됩니다. 작업의 working set은 프로세스가 최근에 접근한 페이지들의 집합이기 때문에, 이 집합에 포함된 서로 다른 페이지의 개수를 working set의 크기로 간주할 수 있습니다.

$WS(t_1)$의 경우는 5개가 필요하고 $WS(t_2)$는 2개가 필요하다

그래서 모든 process에 대한 working set를 구해보자

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

💡

$D >$ total number of frames in physical memory → thrashing

💡

즉 모든 process에 대한 working set의 크기를 구하고, 이를 바탕으로 thrashing을 막겠다는 것이 목표이다.

Strategy

$D$를 줄이자는 것이 목표

OS는 모든 process의 working set을 잘 monitor한다.

만약 $D$가 더 커지게 되면, degree of multiprogramming을 줄임. (이를 통해 $D$값을 줄이고자 하는 것)

💡

$\Delta$를 결정하는 것도 문제가 됨 (즉 과거 얼마까지 볼 것인지에 대한 문제) 너무 커지면 multiple locality를 가지게 되는 문제가 있고, 너무 작아지면 locality를 충분히 다 포함가기가 어려움.

→ 단 기록을 다 해야한다는 problem이 발생

Keeping Track of the Working Set

interval timer 와 reference bit 를 이용해서 근사적으로 구하고자함.

예를 들어 $\Delta = 10000$으로 잡고, 5000마다 timer interrupt가 들어온다고 가정하자. 그러면 timer interrupt가 들어올때마다 reference bit를 체크하고, 둘 중 하나만 1이면 working set으로 취급해주면 된다.

💡

하지만 언제 참조가 되었는지를 알 수 없다는 측면에서는 부정확하다.

💡

timer interrupt의 주기를 줄이면 더 개선할 수 있다.

Page-Fault Frequency Allocation

page-fault rate를 기준으로 thrashing을 막을 수도 있다. Page fault의 upper bound와 lower bound를 정하고 적절한 page fault frequency 영역에 있게끔 조절한다.

1. page fault frequency가 높은 경우

   → 할당한 frame의 수를 늘린다.

2. page fault frequency가 낮은 경우

   → 할당한 frame의 수를 줄인다.

Other Issues

Prepaging

미리 예측을 해서 내 process가 미래에 활용할 page를 미리 가져다 놓겠다. 즉 기왕 storage에서 정보를 가져올 때, 앞으로 내 proces가 쓰게될 page를 예측해서 미리 가져오겠다는 것.

💡

예를 들어 특정 process가 swap out이 되었다고 가정하자. 이후 swap in 될 때, 1개의 page씩 swap in되는 것이 아니라 swap out 되었을 때의 working set을 미리 저장해두었다가 해당 working set을 전부 다 들고옴. (즉 fault가 발생할 때마다 page를 가져오는 것이 아니라 한번에 들고온다.)

이 상황에서 cost issue가 발생할 수 있는데, 만약 미리 가져온 page의 개수를 $s$개라고 하고, 그 중 $\alpha$의 비율을 사용했다고 가정하자. 그러면 $\alpha s$만큼의 page fault를 막은 것이고, $(1-\alpha)s$만큼은 불필요한 page transfer가 발생한 것이다.

$$\text{pre-paging cost} < \text{cost of handling separate faults}$$

💡

따라서 $\alpha$를 키우는 방식으로 진행해야 한다.

Page Size

Architecture에 따라 page의 크기가 다름

Small Page size

장점

1. Less Internal fragmentation

2. Better memory utilization : 운이 좋으면 적은 메모리로도 잘 관리를 할 수도 있다.

단점

1. Large page table (즉 page table의 크기가 증가함)

2. High page fault handling overheads (frequent page fault)

TLB Reach

하나의 TLB를 가지고서 얼마나 많은 address space를 커버할 것인지

$$\text{TLB Reach} = (\text{TLB Size)}*\text{(Page Size)}$$

💡

page size를 곱하는 이유는 TLB entry 1개가 1개의 page에 해당하는 크기를 커버할 수 있기 때문이다.

💡

따라서 TLB reach가 크면 빠른 시간안에 physical memory를 cover할 수 있게 된다.

이상적으로는 각 process의 working set들이 TLB에 있는 것이 가장 좋다.

이러한 TLB reach를 키우는 방법은 다음과 같다.

1. Increase Page size (Internal fragmentation 문제)

2. TLB의 size를 키움 (돈을 늘려서, TLB의 entry를 늘리겠다는 것)

그래서 현실적인 방법이 여러개의 page size를 섞어쓰는 것이다. 예를 들어 Ultrasparc II 같은 경우에는 8KB, 64KB, 512KB, 4MB로 다양하게 제공된다. Solaris 2의 경우에는 그 중 8KB와 4MB를 사용한다. 이 중 8KB는 대다수의 application을 사용할 때 이용하고, 4MB는 kernel code에 대해서 이용하게 된다.

💡

여러 개의 page size를 쓰게 되면 TLB reach가 늘려지게 되는 효과를 가져온다.

Program Structure

💡

우리가 짜는 코드에 의해서도 page fault가 발생하는 정도가 달라질 수 있다는 것을 보여주는 대표적인 예시이다.

💡

사실 컴파일러가 코드 최적화를 통해 수정하게 된다.

I/O interlock

만약 global page replacement를 진행하고 있고, I/O 작업 중인 process의 page가 replacement의 대상이 되었다고 가정하자. 만약 해당 page가 swap-out되게 되면 I/O operation이 제대로 진행되지 않게된다.

이러한 문제를 해결하기 위해서

1. page table에 lock bit 를 두어서, 해당 page는 page-out가 되지 않게끔 강제한다.

2. system call과 같은 방법으로 I/O 작업을 kernel이 수행하게끔 강제

• 궁극적으로 문제가 되는 이유

  데이터 무결성 문제: I/O를 수행하고 있는 페이지를 swap out 시키면, 해당 페이지의 데이터가 메모리에서 디스크로 옮겨지게 됩니다. 만약 페이지의 데이터가 아직 완료되지 않은 I/O 작업에 의존한다면, 데이터의 무결성이 깨질 수 있습니다. 다시 해당 페이지를 메모리로 로드하더라도 이전 I/O 작업의 진행 상황을 알 수 없기 때문에 데이터의 일관성을 유지하는 것이 어렵습니다.

Benefits of Virtual Memory

Copy-on-Write : fork할 때 얻을 수 있는 장점

fork를 할 때 자식은 부모의 모든 image를 copy하게 된다. 이에 대한 overhead가 큰 편이라서, child에 대한 image를 바로 만들지 않고 둘 중 하나가 write를 할 때까지 만들지 않는다. 즉 write해서 갈라서야하는 시점에 copy하자.

💡

Shared pages are protected as read-only따라서 둘 중 하나에서 write를 시도하게 되면 protection fault가 발생하고 갈라지게 된다.

Memory-Mapped Files

하드디스크에 있는 file이 physical memory에 mapping되어 있는 것. 즉 storage의 일부를 physical memory에 mapping을 하고, CPU가 file access를 할 때 memory-access routine을 이용할 수 있게 된다.

mmap() : bind a file to a virtual memory region

기본적으로 file I/O를 load/store 방식으로 진행할 수 있게됨에 따라, read()/write()에 비해서 overhead가 줄어들게 된다.

💡

이를 위해서 physical memory의 일정부분은 memory mapped I/O를 위해 할당해야 한다.

💡

또한 storage에 있는 file이 paging의 대상이 되면서 공유할 수 있다는 장점이 생기게 된다.

일종의 main memory를 cache로 쓰는 것이다. 아주 빠르게 file의 내용을 쓸 수 있게 된다는 것이다. 특히 critical file을 memory mapped하게 되면 속도가 빨라지게 된다.

VM Data Structures in Linux

mm : image와 관련

1개의 region(정확히는 segmentation)당 vm_area_struct를 가지고 있음

→ Linked list로 이어져 있다.

이러한 vm_area_struct에 대한 정보는 mm_struct 자료구조 안에 들어가 있다.

pgd : page directory base address 정보를 가지고 있는 공간

Page Fault Handling in Linux

start end가 다 들고 있으므로 1번의 경우는 invalid region이다.

💡

각각의 vm area region은 대응되는 vm_area_struct를 가진다. (permission 정보고 포함되어 있다.)

→ 그래서 segmentation fault가 나오는 것

1번의 경우에는 illegal한 address를 읽으려고 시도한 것이므로 fault가 난 것.

2번의 경우에는 권한에 대한 문제때문에 발생한다. (해당 커널 자료구조에 permission에 대한 정보도 가지고 있다.)

3번은 page fault가 실제로 나는 것 (physical frame에 실제로 없는 것)

Page Replacement in Linux

LRU 정책을 사용하고 있다.

1. Active List (활성 리스트):
   • Active List에는 현재 활발하게 액세스되고 사용되고 있는 페이지들이 포함됩니다.
   • 활성 리스트의 페이지들은 최근에 액세스되었거나 최근에 사용된 페이지들로, 액세스 패턴이 자주 발생하는 페이지들이 주로 위치합니다.
   • 이러한 페이지들은 메모리에 머무르며, 필요한 경우에 빠르게 액세스할 수 있도록 캐시되어 있습니다.
   • 활성 리스트의 페이지들은 페이지 캐시에서 자주 사용되는 페이지로 간주되어, LRU(Least Recently Used) 알고리즘 등을 사용하여 관리됩니다.

2. Inactive List (비활성 리스트):
   • Inactive List에는 최근에 액세스되지 않거나 사용되지 않는 페이지들이 포함됩니다.
   • 비활성 리스트의 페이지들은 오랫동안 액세스되지 않은 페이지들로, 현재 사용되지 않는 페이지들이 주로 위치합니다.
   • 이러한 페이지들은 메모리에서 비우여지는 가능성이 있으며, 다른 페이지가 필요한 경우에 메모리에서 해제되어 공간을 확보합니다.
   • 비활성 리스트의 페이지들은 필요한 경우 활성 리스트로 이동하여 다시 캐시될 수 있습니다.

실제 OS에서는 page fault가 발생했을 때 빈 frame을 확보하는 것이 아니라, 항상 일정량의 빈 frame을 확보해둔다.

→ kswapd() 가 주기적으로 메모리가 부족한지 여부를 체크한다.

kswapd는 Linux 운영체제에서 동작하는 백그라운드 스레드입니다. 주요 역할 중 하나는 페이지 스왑 아웃(Swap out)을 관리하여 물리적인 프레임(Physical frame) 부족 상황을 모니터링하는 것입니다.

kswapd는 정기적으로 메모리 상태를 확인하고, 필요한 경우 페이지 스왑 아웃을 수행합니다. 이를 통해 메모리 부족 상황에서도 시스템의 안정성과 성능을 유지할 수 있도록 돕습니다.