---
title: Ch9:Virtual Memory Management
---
# 作業系統Ch9: Virtual Memory Management
###### tags: `Operating System` `Review` `Ch9`

## Background
- Virtual memory - separation of user logical memory from physical memory.
- 為了跑極大的 process
- 為了增加 CPU/resources utilization
- 為了簡化 programming tasks
> 使 programmer 免於記憶體限制
- 為了更快跑程式
- Virtual memory can be implemented via
- Demand paging
- Demand segmentation - 更加複雜，因為 variable sizes

> 透過將不常用到的 page 搬移到 disk ，可以使 free frames 給予其他需要的 processes 使用，達到增加 multiprogramming degree。

## Demand Paging

- 只有當它 (pages) 被需要時，A page 會被帶入到 memory 而不是整個 process
- Less I/O needed $\rightarrow$ Faster response
- Less memory needed $\rightarrow$ More users (processes)
- 當參考 the page 時，page is needed。
- Invalid reference $\rightarrow$ abort
> 存取記憶體位址，沒有 allocate，也就是超過那個存取的範圍。
- Not-in-memory $\rightarrow$ bring to memory via paging
> 這個 page 不在 physical memory，而是在 disk 上，此時需要先中止，將 page load into physical memory。
- pure demand paging
- Start a process with no page (完全沒有 pages)
- Never bring a page into memory until it is required
- A swapper (midterm scheduler) manipulates the entire process, 反之 a pager 關心的是 a process 的 個別的 pages。
- Hardware support
- Page table: <font color=red>a valid-invalid bit</font>
- 1 $\rightarrow$ page in memory
- 0 $\rightarrow$ page not in memory
- 一開始，所有的 bits 都設成 0。
- Secondary memory (swap space, backing store): SSD
<br>
<br>

**沒有用到 Demand Paging**:
1. Initialize PCB, PC registers and Page table.
2. Load Code into memory.
3. Running.
4. Finish.


> 將 compile 後的 binary memory image，全部 load 到 memory。

> 下圖是簡化過後的示意圖，一個 page 只有一個 instruction。

> 如果不需要使用時，可以藉由 swapper 將整個 process 搬到 disk 上。

<br>
<br>
<br>
<br>

**有用到 Demand Paging**


> 一開始就 create a page table (以及其餘的像是 PCB 等)，然後什麼都沒有就 load 結束了。
> 當執行到第一個指令時，想要做 memory access，這時候就會發現 page table 的 Valid bit 是 invalid，會產生 page fault。

- Page Fault
- First reference to a page will trap to OS
- page-fault trap
1. OS 會查看 PCB 內資訊去決定
- invalid reference $\rightarrow$ abort
- Just not in memory $\rightarrow$ continue
2. 得到一個新的 empty frame
> free list $O(1)$
3. Swap the page from disk (swap space) into the frame
> copy 到 memory
4. Reset page table, valid-invalid bit = 1
5. Restart instruction
> 一開始執行指令時， PC (program counter) 會加 4B 移動到下一個指令，更新 page table 後需要 PC 減 4B ，然後再重新執行指令一次。

<br>
<br>

>所以上面那個圖會依序執行指令，遇到 page fault trap，paging 處理直到完成，如下圖所示。


### Page Fault Handling Steps


### Page Replacement
- 當 page fault 發生時， 如果沒有一個 free frame
- 要用 different page **replacement algorithms** 挑選要被取代的 frames。

### Demand Paging Performance
- Effective Access Time (EAT):
- $(1-p)\ \times\ ma\ +\ p\ \times\ pft$
- p: page fault rate
- ma: mem. access time (非固定，跟 TLB 有關)
- pft: page fault time
- Access time 與 page fault rate 成正比
- Programs 傾向於有 <font color=red>locality</font> of reference
- locality 意思是 program 常存取相近的記憶體位址
- 因為一個 single page fault 會帶入 4KB memory content，會有一連串的指令在那塊 4KB 裡面，因此大量減少產生 page fault。
- major components of page fault time (about 8 ms)
- <font color=red>read in the page from **disk** (most expensive)
</font>

## Process Creation
### Process & Virtual Memory
- Demand Paging: only bring in the page containing the first instruction.
> load time 會很小，paging 的 swapping 相對於 swapper 的會很快。
- Copy-on-Write: the parent and the child process share the same frames initially, and frame-copy when a page is written.
> 當 page 有更改時，會複製原先的一份並改寫，使 child 和 parent 的內容不同。
- Memory-Mapped File: map a file into the virtual address space to bypass file system calls (e.g., read(), write())
> 跳過 file system calls 會很快

<br>
<br>

### Copy-on-Write
- 允許 parent and child process 共享相同的 frames 在 physical mem.
- 如果兩者其中一個修改 a frame，那麼只有那個 frame 被 copied
- COW 允許有效率 process creation (e.g., fork())
- 自一個 zeroed-out (內容清零) 的 pool 分配 free frames，基於安全理由。

**When a child process is forked**

#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>

int main()
{
    pid_t pid;
    
    /* fork a child process*/
    pid = fork();
    
    if (pid != 0) {
        /* parent process */
        int test1 = 0;
    }
    printf("process ends");
        
    return 0;
}


**After a page is modified**

當執行到 `int test1 = 0;` 時，會複製一份將要修改、原先的 frame，進行修改。


<br>
<br>

### Memory-Mapped File
- Approach:
- MMF 允許 file I/O 視為 routine(function) memory access，藉由將mapping a disk block 到 a memory frame。
- A file 一開始讀取是用 demand paging，接下來 reads/writes to/from the file 視為傳統 memory accesses。
- Benefit:
- 藉由使用 memory access 來達到更快的 file access，比起透過 `read( )` and `write( )` system calls。
- 允許多個 processes 映射同樣的 file 到 pages，在記憶體中的 pages 要 **shared**。
- Concerns:
- Security、data lost、more programming efforts。

**透過 file system**

/* pseudocode */

int buf;
int fd = open(filename, O_RDWR);
lseek(fd, 1024, SEEK_SET);
read(fd, &buf, sizeof(int));
buf++;
lseek(fd, 1024, SEEK_SET);
write(fd, &buf, sizeof(int));
close(fd);

**透過 Memory-Mapped File**

/* pseudocode */

int fd = open(filename, O_RDWR);
int *area = mmap(0, BUFSIZE, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 1024);
area[0]++;
close(fd);
munmap(area, BUFSIZE);

<br>

**原先 file 的內容是** $1234$


## Page Replacement
### Page Replacement Concept
- 當 page fault 發生且沒有 free frame
- swap out a process
- page replacement: find one not currently used and free it
- dirty bit: 減少 page transfers 的開銷，只有被改過的 pages 需要寫到 disk。
- 對於 demand paging 要解決兩個主要問題
- frame-allocation algorithm:
- 決定一個 process 到底可以被分配到多少個 frames。
- page-replacement algorithm:
- 選擇哪一個 frame 可以替代。
### Page Replacement (Page Fault) Steps
1. 找到在 disk 上想要的 page 的位置
2. 找到 free frame
- 如果有一個 free frame， 使用它
- 如果沒有任何 free frame，使用 page replacement algorithm 去選擇要替代的 frame
3. 讀取需要的 page 到 free frame。更新 page & frame tables
4. 重新開始 process


### Page Replacement Algorithms
- 目標: 最小 page-fault rate
- 評估: 執行 a string of memory references (**reference string**: page id)且計算 page faults 的數量。

#### FIFO algorithm
- 最老的 page 在 FIFO queue 被取代。

<br>

考慮例子
- Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 且只有 3 frames
- 結果產生 9 page faults


**Belady's anomaly (異常)**
- Greater allocated frames $\rightarrow$ more page fault

考慮同一例子
- 改變成有 4 frames
- 結果產生 10 page faults


<br>

**FIFO Illustrating Belady’s Anomaly**

<br>


#### Optimal (Belady) Algorithm
- 替代將會最長時間不會被用到的 page
- 需要 future knowledge
- 4 frames: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 $\rightarrow$ 6 page faults
- 實際上，不可能有 future knowledge


<br>

#### LRU Algorithm (Least Recently Used)
- 最佳演算法的估計
- 往後看(過去)，而非往前看(未來)
- 取代過去最長未被使用到的 page
- LRU Algorithm Implementations
- Counter implementation
- page referenced: time stamp 複製到 counter
- replacement: 移除擁有最老的 counter 的 page
- 需要 linear search

- Stack implementation
- page referenced: 搬到 double-linked list 的最頂端。
- replacement: remove the page at the bottom
> 透過 hash map $O(1)$

考慮 4 frames: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 $\rightarrow$ 8 page faults


<br>

#### Stack Algorithm
- 是指演算法的特性
- Stack algorithm: 原先有 $n$ frames 擁有一組 pages 在 memory 中，如果今天變成有 $n+1$ frames，則原先的那組 pages 會是現在的這組 pages 子集。
- $page\_set_{old}\ \subset\ page\_set_{new}$
- Stack algorithms do not suffers from Belady's anomaly.
- Optimal and LRU algorithms are stack algorithm.
- <font color=red>Few systems</font> provide sufficient hardware support for the LRU page-replacement.

#### Counting Algorithms
- LFU Algorithm (least frequently used)
- keep a counter for each page
- Idea: An actively used page should have a large reference count
> 最不常用代表日後用到機會也少，所以當 victim page。
- MFU Algorithm (most frequently used)
- Idea: The page with the smallest count was probably just brought in and has yet to be used.
> 最常用反而之後不容易用到，所以當 victim page。
- 這兩者演算法都不常見
- implementation is expensive
- do not approximate OPT algorithm very well

## Allocation of Frames
### Introduction
- 每個 process 需要 minimum 數量的 pages
- E.g., IBM 370 - 6 pages to handle Storage to Storage MOVE instruction
- Both operands are in main storage, the first operand is B1(Reg.ID)+D1, the second operand is B2(Reg. ID)+D2, L plus 1 is the length.
- 指令是 6 bytes， 可能跨越 2 pages。
- Moving content 也可能跨越 2 pages。


> 各佔 2 pages，所以總共 6 pages


### Frame allocation
- Fixed allocation
- Equal allocation - 100 frames, 5 processes $\rightarrow$ 20 frames/process
- Proportional allocation - Allocate according to the size of the process
- **Priority** allocation (在 runtime 做決定)
- using proportional allocation based on priority, instead of size
- 如果 process P 產生 page fault
- 選擇它其中一個 frame 去做替代。
- 選擇從較低優先權的 process 做替代。

- Local allocation: each process 自它本身已經分配到的 frames 集合中去選擇

- **Global** allocation: process 從所有 frames 的集合中選擇 replacement frame
- 一個 process 可以從另一個 process 拿走 frame
- e.g., 允許高優先權的 process 拿走低優先權的 process 的 frame
- 良好的系統 performance， 因此較常被使用
- 對於每一個 process 而言，避免 **<font color=red>thrashing</font>** 而維護最小數量的 frames。

### Thrashing
#### Definition of Thrashing
- 如果一個 process 沒有足夠多的 frames $\rightarrow$ **very high paging activity**
> 沒有足夠它所需要的 frames ，也就是用於 active use 的 pages 不夠

- 當 process 正在 thrashing 意思是如果比起正在執行，它花更多時間在做 paging
> 將導致 CPU utilization


<br>

- Performance 問題由 thrashing 產生的 (Assume global replacement is used)
- process queued for I/O 去 swap (page fault)
- low CPU utilization
- OS 增加 multiprogramming 的程度
- new processes 會從 old processes 拿走 frames。
- 產生更多 page fault，因此更多 I/O
- CPU utilization 掉落更多

- 為了避免 thrashing, 一定要提供對於每個 process 而言足夠多 frames
- Sol: <font color = blue>Working-set model, Page-fault frequency</font>

#### Working-Set Model

- **Locality**: a set of pages that are actively used together
> 積極使用的 pages 應該是靠近彼此

- **Locality model**: 當 process 執行時， 它從一個 locality 到另一個 locality
- program structure (subroutine, loop, stack)
- data structure (array, table)
- <font color=red>Working-set model</font> (based on locality model)
- working set <font color= red>window</font>: a parameter $\Delta$ (delta)
> 給定一段時間
- working set: set of pages in most recent $\Delta$ page references <font color = red>(an approximation locality)</font>
> 最近一段時間，有多少 page references (page id)

if $\Delta\ =\ 10$


- 運用 working-set size 來避免 thrashing
- $WSS_{i}$: working-set size for process $i$
- $D\ =\ \Sigma\ WSS_{i}$ (total demand frames)
- <font color = red>if $D\ >\ m$ (available frames) $\rightarrow$ thrashing</font>
- OS 會監視每個 process 的 $WSS_{i}$ 且分配足夠的 frames 給 process。
- if $D\ \ll\ m$, 增加 degree of multiprogramming
- if $D\ >\ m$, 暫停 a process

**pros**:
- 盡可能保持高的 multiprogramming 避免 thrashing
- 最佳化 CPU utilization

**cons**:
- <font color = red>too expensive for tracking</font>

#### Page Fault Frequency Scheme

- 直接測量並控制 page fault rate 避免 thrashing
- 對於一個 process 建立想要的 page fault rate 的 上下限
- 如果 page fault rate 超過上限
- 允許另一個 frame 給這個 process
- 如果 page fault rate 低於下限
- 從這個 process 移除一個 frame


#### Working Sets and Page Fault Rates

- Memory has locality 特性
- 當 process 跑到一個新的 WS， page fault rate 會直衝頂峰。


## Ref

[1] [上課影片 link](https://www.youtube.com/playlist?list=PLS0SUwlYe8czigQPzgJTH2rJtwm0LXvDX)
[2] [投影片 link](https://ocw.nthu.edu.tw/ocw/index.php?page=course_news_content&cid=141&id=999)