# 作業系統筆記
## CH 5.8 演算法的評估
### 定量模式
平均等待時間
### 佇列模式
李特氏公式：$n$ = $λ$ * $W$
$n$ ： 平均佇列長度
$λ$ ： 新行程平均到達比率
$W$ ： 在佇列平均等待時間
離開佇列的行程數量必須等於到達行程的數量，才能達成系統穩定。
### 模擬
收集資料指出演算法的效能，更精確。
### 實做
高風險、高代價，環境會改變。
---
## CH 6 同步
### 背景
1. 行程並行執行
2. 但並行的行程如果同時存取相同資料，會造成資料不一致，稱為**競爭情況**（race condition)。
### 臨界區間問題
每個行程含有一段區間稱為**臨界區間**（critical section）的程式碼，讓行程可以改變共用變數、更新表格等工作。
解決臨界區間必須滿足三項條件：
1. **互斥**
有行程正在臨界區間內執行，其他行程不可以在其臨界區間內執行。
2. **進行**
如果有行程正等待進入臨界區，且目前臨界區中沒有行程在執行，則等待行程之ㄧ必須能在有限時間內進入臨界區。
3. **限制性的等待**
在一個行程要求進入臨界區間，而此要求尚未答應前，允許其他行程進入其臨界區內的次數有限制。
### Peterson 解決方案
1. **兩個行程**的解答。
2. 行程共用兩個變數：`int turn` 和 `boolean flag[2]`
`turn` ： 表示輪到誰執行。
`flag[]`：表示是否準備進入其臨界區間。
### 同步之硬體
以**硬體方式**解決，藉由 `鎖（lock）` 保護臨界區間。
- test and set
只有滿足互斥性
```c=
boolean test_and_set(boolean *target){
boolean rv = *target;
*target = true;
return rv;
}
```
```c=
do {
while (test_and_set(&lock));
/* do nothing */
/* critical section */
lock = false;
/* remainder section */
} while (true);
```
- compare and swap
只有滿足互斥性
```c=
int compare_and_swap(int *value, int expected, int new_value){
int temp = *value;
if (*value == expected){
*value = new_value;
}
return temp;
}
```
```c=
do {
while(compare_and_swap(&lock, 0, 1) != 0);
/* do nothing */
/* critical section */
lock = 0;
/* remainder section */
} while (true);
````
### 互斥鎖
解決臨界區間最簡單的是`互斥鎖（mutex lock）`。
為避免競爭狀況，行程在進入臨界區間前必須取得鎖，離開時釋放鎖。
```c=
do {
acquire lock;
critical section;
release lock;
remainder section;
} while (true);
```
`acquire()` 的定義如下：
```c=
acquire() {
while(!available);
/* busy wait */
available = false;
}
```
`release()` 的定義如下：
```c=
release() {
available = true;
}
```
以上主要缺點是**忙碌等待（busy waiting）** // 也稱為**自旋（spinning）**
缺點：等待鎖釋放的時候，不停地執行空迴圈無法做其他事，直到鎖釋放後才會脫離空迴圈，進入critical section。
優點：當行程等待一個鎖時不需要內容轉換。
### 號誌
號誌 S 是一個整數變數，除了初值（1），只能藉由 `wait()` 和 `signal()` 存取。
`wait()` 的定義如下：
```c=
wait(S) {
while (S <= 0);
/* busy wait */
S--;
}
```
`signal()` 的定義如下：
```c=
signal(S) {
S++;
}
```
1. 計數號誌
- 值的範圍不受限制
- 能用來對有限數量的例證組成的資源做控制存取
2. 二元號誌
- 數值可以是 0 或 1
- 行為類似互斥鎖，在沒提供互斥鎖的系統可以取代互斥鎖。
可以用號誌解決同步問題，兩個並行的行程：
P<sub>1</sub> 具敘述 S<sub>1</sub> ； P<sub>2</sub> 具敘述 S<sub>2</sub>
假設我們要求 S<sub>2</sub> 必須在 S<sub>1</sub> 完成後才可執行
```c=
synch = 0; // 共同號誌
S1;
signal(synch);
wait(synch);
S2;
```
- 同步號誌初始值 = 0;
- 互斥號誌初始值 = 1;
---
## CH 7 死結
### 死結定義
一組行程陷入互相等待的情況造成行程無法繼續執行，使 CPU 使用率和產出大幅降低。
### 系統模型
一個系統包含可分配可給競爭行程的有限資源。這些資源可以區分成許多形式或類別，每種形式含有數種相同的**例證**。例如：一個系統有兩個 CPU，則 CPU 這種形式的資源具有兩個例證。
正常模式下，一個行程只能依據以下順序使用資源：
1. **要求**： 必須等候獲得資源。
2. **使用**： 行程能夠在此資源上運作
3. **釋放**： 用完後行程釋放資源。
### 死結的特性
P = 行程， R = 資源
1. 互斥
一個 R 一次只能被一個 P 使用。
2. 佔用與等候
一個 P 佔用一個 R， 且正在等候其他 P 已佔用的 R。
3. 不可搶先
R 不能被搶先。
4. 循環式等候
R<sub>1</sub> → P<sub>1</sub> → R<sub>2</sub> → P<sub>2</sub> → R<sub>1</sub> → ...
以上**四個條件都成立**，才會產生死結。
### 資源配置圖
系統資源配置圖 = (V, E)
頂點組合的 V 又可以區分為兩個不同的集合：
1. P = { P<sub>1</sub>, P<sub>2</sub>, ..., P<sub>n</sub> } 行程的集合
2. R = { R<sub>1</sub>, R<sub>2</sub>, ..., R<sub>n</sub> } 資源的集合
有向圖的有向邊代表不同的含意：
1. P<sub>i</sub> → R<sub>j</sub>，**要求邊**，P<sub>i</sub> 已要求 R<sub>j</sub> 中的一個例證，且正等候此資源。
2. R<sub>j</sub> → P<sub>i</sub>，**分配邊**，P<sub>i</sub> 已佔用 R<sub>j</sub> 中的一個例證。
1. P1 已經有 R2 的資源，P1 要求 R1 的資源
2. P2 已經有 R1、R2 的資源，P2 要求 R3 的資源
3. P3 已經有 R3 的資源
4. 並沒有形成 cycle，所以沒有 deadlock。
1. 承例子 1，只多了一條線，P3 要求 R2 資源
2. 這時候會形成 cycle
P1 → R1 → P2 → R3 → P3 → R2 → P1
P2 → R3 → P3 → R2 → P2
3. deadlock
1. 雖然有 cylce，P1 → R1 → P3 → R2 → P1
2. 但是 P4 可以 release R2 的某一個 instance
3. 那 P3 就可以獲得 P4 release 出的那個 instance
4. 不會 deadlock
#### 資源配置圖結論
1. 如果沒有 cycle → 沒有 deadlock
2. 如果有 cycle，不一定有 deadlock
- 如果每個 resource 只有一個 instance → deadlock
- 如果每個 resource 有多個 instance → 可能 deadlock
### 處理死結
1. 確定系統永遠不會進入死結狀態（deadlocked state）
- 預防死結（Prevention）
- 避免死結（Avoidance）
2. 允許系統進入死結狀態（deadlocked state），偵測並恢復它
3. 完全無視這些問題，假裝這些問題從來不曾發生過
- 最多作業系統使用的方式，包括 Linux、Windows，它讓程式開發者自己來處理這些問題
### 預防死結
只要死結四個特性有一不成立，就可以預防死結的發生。
1. 互斥
對可共用資源而言，互斥一定成立；而唯讀檔案因為可以同時讀取相同檔案，所以一定不會產生互斥。因此**不能**藉由排除互斥達到預防死結。
2. 佔用與等候
必須保證一個行程在要求一項資源時，不可以佔用任何其它的資源。兩種可能策略：
- 行程在執行前需要求並取得所需資源。
- 行程在未佔用資源的情況下才能要求資源，如要求新資源，必須先釋放所佔用資源。
會造成**資源利用率低**，也可能會有**飢餓現象**。
3. 不可搶先
變成可搶先，行程可以搶奪 waiting process 所持有的資源。
解決：採取類似 "Aging" 技術（將被搶奪的次數，列為提高優先權之依據）
4. 循環式等候
確保循環式等候的條件不成立，對所有的資源型式強迫**安排線性的順序**。
行程要求資源時必須依照數字大小，遞增地提出要求。
優點：保證系統絕不會有死結存在
缺點：資源可用率低、throughput 低
### 避免死結
#### 安全演算法
如果找不出一組 Safe state 就是在不安全的狀態
1. 剩下 12 - (5 + 2 + 2) = 3，free
2. 剛好 B 需要 2 個就給他，等他做完會釋放 ( 3 + 2 = ) 5 個資源
3. 5 個可以給 A，A 做完釋放 10 個
4. 剩下就可以給 C 用了
5. <B, A, C>是一個 safe state
1. 剩下 12 - (5 + 2 + 3) = 2，free
2. 剛好 B 需要 2 個就給他，等他做完會釋放 4 個
3. 但是 A、C 都的需要都 > 4
4. 所以會有 deadlock
#### 資源配置圖演算法
在資源配置圖中多加入一種邊，稱為 claim edge（宣告邊）做法:
1. 當 Pi 要求 Rj 時
2. 將 claim edge Ri 虛線 → Rj 改為要求邊 Pi → Rj
3. 再將要求邊改為分配邊 Pi ← Rj
4. 查看是否有 cycle 存在，若有就是 unsafe state
#### 銀行家演算法
$n$ 為系統中行程數目， $m$ 為資源形式的數量
- `Available` ： 長度為 $m$ 的向量，表示可用資源量。
- `Max` ： 為 $n * m$ 的矩陣，定義行程最大需求量。
- `Allocation` ： 為 $n * m$ 的矩陣，定義每一行程所佔用的資源數量。
- `Need` ： 為 $n * m$ 的矩陣，表示每一行程剩餘的需求量。
`Need` = `Max` - `Allocation`
1. 寫出 Need (Max - Allocation)
2. 分配後行程釋放資源，Work = ** Available + Allocation**
3. 重複找資源
1. 寫出 Need 
2. 把資源給 P1，等到 P1 做完會釋放 (2,0,0)，下次資源就有 (3,3,2) + (2,0,0) = (5,3,2)
3. (5,3,2) 的資源可以給 P3，等到 P3 做完會釋放(2,1,1)，下次資源就有(5,3,2) + (2,1,1) = (7,4,3)
4. (7,4,3) 的資源可以給 P4，等到 P4 做完會釋放(0,0,2)，下次資源就有(7,4,3) + (0,0,2) = (7,4,5)
5. (7,4,5) 的資源可以給 P1，等到 P1 做完會釋放(0,1,0)，下次資源就有(7,4,5) + (0,1,0) = (7,5,5)
6. (7,5,5) 的資源可以給 P2，等到 P2 做完會釋放(3,0,2)，下次資源就有(10,5,7)
7. <P1, P3, P4, P1, P2> 是一個 safe sequence
### 死結偵測
1. **多久**會產生死結？
2. **多少**行程受死結發生影響？
優點：resource utilization 較高，Throughput 高
缺點：cost 太高
### 死結恢復
1. 取消所有死結中的行程
2. 一次取消一個行程，直到死結循環消除為止
選擇花費代價最小的行程中止：
- 使用最少處理器時間的進程。
- 使用最少輸出工作量的進程。
- 具有最多剩餘時間的進程。
- 分的最少資源進程。
- 具有最小優先級的進程。
### 資源搶先
若使用搶先處理死結，考慮以下：
1. 選擇犧牲者
2. 回撤
3. 飢餓
---
## CH 8 記憶體管理
### 基本硬體
1. Base register：程式的起始記憶體地址，稱為**基底暫存器**
2. Limist register：程式所佔記憶體地址大小，稱為**界限暫存器**
### 位址連結
1. 編譯時間（compile time）
編譯時，已知程式在記憶體中的位址，可產生**絕對碼**。
缺點：起始位址有變就必須**重新編譯**。
2. 載入時間（load time）
編譯時不能確定程式在記憶體中的位址，編譯程式必須產生**可重定位碼**，連結動作會被延遲到載入時間才進行。
缺點：起始位址改變需**重新載入**。
3. 執行時間（execution time）
連結的動作被延到執行時間才發生，硬體需要支援 MMU。
### 邏輯位址和實體位址
1. 邏輯位址
- **CPU** 產生的
- 虛擬位址
2. 實體位址
- 載入到**記憶體**的記憶體位址暫存器所看到的
- 編譯時間和載入時間的位址連結
邏輯位址 = 實體位址
- 執行時間的位址連結
邏輯位址 != 實體位址
### 記憶體管理單元（MMU）
行程所產生的位址被送往記憶體，加上重定位暫存器的值，就會被對映到實體位址。
### 動態載入
因為程式和資料都須在實體記憶體中執行，所以行程大小會受限於實體記憶體的大小。
要得到較佳的記憶體空間使用率，可採用**動態載入**。
某個常式**需要時才會被載入**，目的是想節省記憶體空間。
### 動態連結與共用程式庫
當程式被呼叫時才將他載入到記憶體中，也就是**連結被延遲到執行時間**。
節省不必要的連結時間，對於程式庫特別有用，也可以說是**共用程式庫**。
### 置換
1. 備份儲存體（backing store）
2. 記憶體不夠用了，優先權（priority）較低的會先被 swap out
#### 行動系統的置換
- 不支援置換（用快取記憶體取代硬碟）
- IOS 要求 APP 放棄配置記憶體
- Android 會寫入 APP 狀態到快取記憶體
### 連續記憶體配置
1. fix partition
固定分割，大家都配置一樣的記憶體大小，空間不會釋放
2. Variable partition
配置的記憶體大小符合 process 大小，空間會釋放
### 動態儲存體配置
1. first-fit
從第一個洞開始找，找到可以塞進去的洞
2. best-fit
檢查所有洞，找出最小的洞，且可以塞進去的洞
3. worst-fit
檢查所有洞，找出最大的洞
### 斷裂
- 外部斷裂
記憶體的空間被分割成許多小區間，因為行程的載入和移出記憶體，讓區間變成非連續的，不足以分配給其他行程使用，浪費記憶體空間。
- 內部斷裂
記憶體分成固定大小區間，配置給行程使用。但行程沒用到的區間不會釋放給其他行程使用，造成空間的浪費。
### 百分之五十規則
外部斷裂的問題，配置 N 個區段，有 0.5N 因為斷裂而損失，進而導致記憶體 1/3 沒被利用。
### 解決外部斷裂 — 聚集
聚集是收集記憶體中零散的可用空間，使其成為一大區間。
不可使用聚集的情況：靜態重定位（絕對程式、可重定位程式）
可以使用聚集的情況：動態可重定位程式
### 分段
分段表管理位址，每一項都有：
1. 分段基底值
主記憶體中實際開始位址
2. 分段界限值
設定分段的長度
- 優點
- 允許實體位址不連續
- 沒有內部斷裂
- 缺點
- 可能產生**外部斷裂**
- 較多記憶體存取時間
* 如何轉換
1. 取得 segement number 之後
2. 利用 segement table 去找到他的 base，就才可以計算起始位置
3. 把 base+offset 才是真的起始位置
4. 加上 limit 就是他在實體位址結束位置
### 分頁
- 欄（frame）
- 將實體位址分成固定大小的區段
- 頁（page）
- 邏輯位址分成一樣大小的區塊
- page size = frame size
- 利用 page table，儲存 page、frame 關係
- 一個 page 對應一個 frame
- 在 os 裡面
- 每一個 process 有自己的 page
- 優點
- 可以配置不連續實體位址
- 沒有外部斷裂
- 缺點
- 可能產生**內部斷裂**
一頁的大小一般是 2 的次方，範圍可以自每頁 512B ~ 1G
如果邏輯位址空間是 2<sup>m</sup>，而頁的大小是 2<sup>n</sup> 位元組，
則邏輯位址高階 m - n 個位元代表頁數，低階位元代表頁偏移量，邏輯位址成為：
問題： Given a computer system with a 52-bit virtual address, 4KB pages, and 4 bytes per page entry. Suppose that the maximum physical memory size is 512GB, and the system is byte-addressable. Let paging be implemented for the system. What is the number of bits for physical addresses, and what is the maximum number of pages for a process?
答案
a. 39 maximum physical memory size is 512GB
512GB = 2^9 * 2^30 = 2^39 => 39 個 bit
b. 2^40 virtual address 是 52-bit page-offset 的長度
=> page-size 是 4KB = 2^12 bit page-number 的長度
=> 52-12 = 40 page 最大數是 2^40
### 保護
- 分頁表的每一項都會額外加上另外的位元：**有效 — 無效**位元
有效（v）或無效（i）位元
- 分頁表長度暫存器（PTLR）提供分頁表大小
### 共用分頁
- 程式碼都是**可重進入程式碼**（text code OR pure code）
- 可以不同的邏輯位址但都指到相同的實體位址
### 分頁表的結構
1. 階層式分頁
- 將分頁表也分頁
2. 雜湊式分頁
- 位址空間大於 32 位元常用
- H(P) = address
3. 反轉分頁表
題目：邏輯位址 48 位元，實體位址 32 位元，分頁大小 16K，
(1) 若採用單層分頁，會有多少分頁項目？
(2) 採反轉分頁表，會有多少項目？
ANS：
(1) 16K = 2<sup>14</sup>，偏移量 14 位，頁號有 34(48 - 14) = 2<sup>34</sup>
(2) 2<sup>32</sup> / 2<sup>14</sup> = 2<sup>18</sup>
---
## CH 9 虛擬記憶體管理
使用者邏輯記憶體與實體記憶體間的分隔。
- 比主記憶體大，佔用較少實體記憶體
- 載入和置換較少，加速 CPU 和資源使用率
製作方式：
- 需求分頁
- 需求分段
### 虛擬位址空間
- 行程間可以共享記憶體
- 鬆散的位址空間。
### 需求分頁
以分頁為基礎，採用 lazy swapper 技巧。即程式執行之初不將全部的分頁載入記憶體，僅載入執行所須的 分頁，如要處理 page fault 問題，由 OS 另行處理。
（多加一個**有效－無效位元**欄位，用以指示分頁是否在記憶體中）
- 需要分頁才把他放進記憶體
- 較少 I/O 需求，甚至不用
- 更快的反應
- 較少記憶體需求
- 更多使用者
- Lazy swapper
- 需要某一頁才置換那頁
- 以**頁**為單位，不是以 process
利用**有效 — 無效位元** 檢查有沒有此分頁
如果是 bit 的值是 i 就叫做 page fault（分頁錯誤）
#### 分頁錯誤
當行程要使用不在記憶體中的分頁時，會產生**分頁錯誤**。
處理方式：
1. 檢查分頁在分頁表的有效無效位元欄位，發出 trap 給 os
2. 如果參考...
- 是非法的，無效記憶體位址 → 停止
- 有效參考，但未將該頁載入 → 將該頁載入
3. 找到空的欄
4. 將分頁從 disk swap in 進記憶體
5. 重設表，把 validation bit 改為 v
6. 重新啟動指令
#### 性能
- 存取時間（$ma$）
如果沒有分頁錯誤，有效存取時間 = 記憶體存取時間
- 分頁錯誤機率（$p$）
$0 ≦ p ≦ 1$
$有效存取時間 = (1-p) * ma + p(分頁錯誤時間)$
平均分頁錯誤處理時間是 $8ms$ 和記憶體存取時間是 $200ns$，有效存取時間是：
$(1-p) * 200ns + p(8ms) = 200 + 7,999,800 * p$
有效存取時間和**分頁錯誤比率呈正比**。
若希望可以小於百分之十的減緩，則：
$200ns * 1.1 = 220$
$220 > 200 + 7,990,800 * p$
$p < 0.0000025$
### 寫入時複製 copy on write
- 父行程和子行程在最初時分享相同的分頁。
- 子行程若修改共用分頁，則此分頁需要複製（只有修改的才要複製）
`fork()` vs. `vfork()`
- `fork()` 使用 copy-on-write
- 父行程會和子行程同時執行，要達到這種效果，CPU 要有 MMU 硬體支援。
- `vfork()` 不使用 copy-on-write
- 父子行程除了 stack 其他都共享。
- vfork() 通常用於沒有 MMU 的 OS，此時父行程會被暫停，直到子行程執行了 exec() 或 exit()。
### 分頁替換
當分頁錯誤發生，且記憶體無可用欄時，則 OS 必須執行分頁替換。
OS 必須選擇一個**犧牲分頁（victim page）**，將其 swap out 到 disk 來空出一個可用欄，再將 lost page swap in 到此欄。
分頁替換方法：
#### 修改位元
如果沒有空白欄可以使用，我們就必須轉移兩頁（一頁進一頁出）。可以藉由**修改位元**（modify bit，或是髒位元）減少負擔。
- 0：沒被修改過
- 1：從硬碟讀入後被修改過
### 分頁替換演算法
執行需求分頁必須解決兩個主要問題：
1. 欄的配置演算法
2. 分頁替換演算法
評估一個演算法好壞藉由一連串的記憶體參考，並計算分頁錯誤的次數來評估，一連串的記憶體參考稱為**參考串**。
以下演算法使用參考串為：
### FIFO 分頁替換
先進先出演算法
當要替換頁時，選擇在記憶體中**最老**的那頁換掉。
以上總共有 15 次分頁錯誤。
FIFO 會造成**畢雷地異常**，配置欄越多，分頁錯誤比率可能會增加。
### 最佳分頁替換
把未來最長時間之內不會用到的那一頁替換掉。
此演算法分頁錯誤次數為 9 次，永遠不會遭遇畢雷地異常的問題。
### LRU 分頁替換
最佳演算法實際上並不可行，所以可以找一種近似最佳演算法的方法：**近來最少使用演算法（LRU）**。
LRU 是選擇**最久未被使用**的那一頁作為替換。
LRU 和最佳替換一樣，都不會遭遇畢雷地異常現象。它們都是屬於**堆疊演算法**。
堆疊演算法，越上面代表近來最常用到。
### LRU 近似分頁替換
很少電腦提供足夠硬體真正支援 LRU 分頁替換，所以必須採用其他方法代替。許多系統都會提供**參考位元**提供一點幫助。
參考位元代表的是此分頁近來有無被使用過，為 1 代表有使用過， 0 則是無。
1. 額外參考位元演算法
2. 第二次機會演算法
3. 加強第二次機會演算法
### 計數基礎分頁替換
### 頁緩衝演算法
在 Disk 或 I/O 方便時先選出犧牲者進入 Page buffer，降低分頁錯誤時額外的處理。
### 欄配置法
### 輾轉現象
CPU 排班程式發現 CPU 使用率降低，就會增加多元程式規劃的程度。新行程就會搶其他行程的頁以工作，造成分頁錯誤，導致 CPU 使用率又降低 → 提升多元程式規劃程度 → ... ，造成輾轉現象，行程忙於置換。
若要使 CPU 使用率能增加，就必須**降低**多元程式規劃程度。
### 工作組模式
### 分頁錯誤頻率
Sign in with Wallet
Connect another wallet