# 作業系統功課
此份作業旨在描述**program**從進入系統到執行完所經過的過程。上圖為一個program變成process後的執行經過流程。
## 創建新的process
一個可執行的程式需要被載入記憶體才可以被執行並且變成process，當系統發現有新的process被創建時，需要進行
1. 創建一個空白的PCB，用於儲存**process state**、**preocee number**、**program counter**、**register**、**memory limits**、**list of open file**等等。
2. 分配資源。系統需要知道process的內存大小。
3. 初始化PCB
4. 將procee放入ready state。
## CPU scheduler
從process進入ready queue開始，就開始等待cpu使用權轉移到自己身上並開始執行，但是還有其他process要執行，所以會有schedule的方式 :
1. **FCFS**(First Come First Serve): 由最先來的開始分配資源，FCFS最大的好處就是公平及簡單。
2. **Round Robin Scheduling Algorithm** : 跟**FCFS**類似，分配給第一個要求的process，但是可以加入一些插隊的規則使系統在process間做cpu使用權轉移。哪個process接著用，也有其他演算法可以參考(如: **Shortest Job First**、**Priority Scheduling**等)。
## CPU使用權轉移
有兩種情況:
1. 分配的時間 >= 實際需求的時間:這種情況process會自然執行完，並將使用權讓出，供下一個process使用。
2. 分配的時間 > 實際需求的時間:這種情況發生時，需要進行進行**Context Switch**(把舊process的狀況儲存下來，並且載入新process的狀態)。
## Process執行時可能遇到的問題
### Race Condition
多個Process使用同一個Shared Data，但由於Context Switch發生的時機不恰當，造成得到的結果取決於存取Shared Data的順序，這種情況就叫Race Condition。
解法 : 在每個process執行間加入**Critical Section**，當存取shared data時就進入Critical Section並進行演算法。演算法需盡量滿足三個條件。
1. **Mutual Exclusive** : 一次至多一個人進入Critical Section。
2. **Progress** : 沒人使用時，如果有Process要進入Critical Section便馬上可以進入。
3. **Bounded Waiting** : 不能無限期等待(不能有人連續占用)。
### Peterson Algorithm

1    //Process i
2    do{
3        flag[i] = true;
4        turn = j;
5        while(flag[j] && turn == j);
6        CRITICAL SECTION;
7        flag[i] = false;
8        remainder section
9    }while(true);
10    //Process j
11   do{
12        flag[j] = true;
13        turn = i;
14        while(flag[i] && turn == i);
15        CRITICAL SECTION;
16        flag[j] = false;
17        remainder section
18    }while(true);

每次進入時，會先將flag變成true，但是把使用權推給對方，也因此一次只會有一個人使用(滿足**Mutual Exclusive**)。
在第5行、第14行演算法中，檢查對方是否要使用及使用權是否在對方身上，如果有其中一項不符，便會直接進行(滿足**Progress**)。
第7行、第16行演算法中，使用完立刻將flag變回false，且程式開頭又會將turn推給對方，因此不會連續占用share data使用權(滿足**Bounded Waiting**)
其中:
**turn** : 用來決定誰可以進Critical Section。
**flag[]** : 布林值，用於表示process需不需要進Critical Section。
綜合來說，Peterson Algorithm滿足三個需求，但Peterson只能用於兩個Process使用share data的情況。
### Test and Set Algorithm

1    do{
2        acquire lock;
3            critical section;
4        release lock;
5            remainder section;
6    }while(true);

在test and set中，必須使用lock來確認是否有人在進行critical section，因此有了lock這個結構。

1    do{
2        while(test_and_set(&lock));//do nothing
3        lock = true;
4        critical section;
5        lock = false;
6        remainder section;
7       }while(true);

當map到一個cpu指令，先檢查lock是否鎖上，如果為否的話進行critical section，並在執行完critical section後將lock設回false，讓其他要進critical section的人可以進入。

1    do{
2        waiting[i] = true;
3        key = true;
4        while(waiting[i] && key) key == test_and_set(&lock);
5        waiting[i] = false;
6        //Critical Section;
7        j = (i + 1) % n;
8        while(j != i && !waiting[j]) j = (j + 1) % n;
9        if(j == i) lock = false;
10       else waiting[j] = false;
11       //Remainder Section;
12  }while(true);

## Interrupt、Waiting State
當process執行到一半可能需要某項資源的I/O，就會中斷執行直到完成I/O，等待的期間會進入Waiting State。如前面所述，如果進入Waiting State就必須在PCB內紀錄process執行狀況。
### Deadlock
Process之間，彼此握著對方需要的不可共用的資源，互相等待彼此釋出，永遠執行不完。
解法:把Deadlock發生的4個要件打破其中一個，即可預防。
1. **Mutual Exclusive** : 由於Deadlock只產生在不可共用的資源使用上，這點沒有辦法被打破。
2. **Hold And Wait** : 握著資源等待資源，最簡單的解法為將資源一次全給、一次全收，但這樣會造成資源使用率低落。
3. **No preemption** : 沒使用完不會釋出(印表機一次只能印一份，沒辦法同時印兩放不同的檔案)。解法為檢查process有沒有要立即執行，如果沒有就將資源變成preemptive。
5. **Circular Wait** : P0等P1、P1等P2、...、Pn等P1，繞了一圈沒半個Process執行的完。解法為把resource編號，設**f(resource) = hold著這個resource的Process**，且**f(Ri+1) > f(Ri)** 如果條件成立就不會產生circular。
### Resource Allocation Graph Algorithm
用**Claim Edge**來假設把資源分給這個Process，並檢查是否會發生Deadlock，如果可能發生Deadlock表示不能做這樣的分配。
### Banker's Algorithm
1. if **Request[i] > Need[i]** 踢出系統，表示Process想使用超過自己需求的資源。
2. if **Request[i] > Available** 表示系統無法負荷這個Process所需，只能先執行其他Process。
3. 到了第三步，表示系統可以負擔的起這個Process的資源使用，進行資源分配後，繼續檢查是否會有資源分配不足的問題，一旦發現分配了之後便無法讓所有Process執行完，就會進入unsafe state。

其中 :
**Available[resource type]** : 表示系統所能提供的資源。
**Max[process][resource type]** : process對某個resource最大的需求量。
**Allocation[process][resource type]** : process對某個resource已經被分配到的量。
**Need[process][resource type]** : process對某個resource未滿足的需求量。(Need = Max - Allocation)
**Request[process][resource type]** : process對某個resource所要求的量。
以上皆為**避免**Deadlock發生的方法。
在實際運作上，Deadlock可以藉由:
1. 發生後偵測，再進行解決，需要其他的解決Deadlock的演算法。
2. 由於現今的系統發生頻率較低，而採用避免Deadlock的演算法又較費時，因此選擇忽視。

## CPU使用權轉移的時間點
當Process結束Waiting狀態(獲得I/O或是某事件完成)便會再度回到ready queue，便又回到決定哪個process可以取得使用權的狀況了。
可能發生cpu轉移的時間點:
1. Running State -> Waiting State : 有I/O要求。
2. Running State -> Ready State : 使用時間結束，或是有更高優先權的搶奪使用權。
3. Waiting State -> Ready State : I/O結束。
4. 程式執行結束，將使用權轉移。

上面4個狀況中，1、4為**自願轉移**;2、3為**被迫轉移**。

## Process執行及Memory管理策略
Process執行時，牽扯最大的不外乎就是記憶體，為了提升效能，會將多個Process都放在記憶體裡(共用記憶體)。在處理記憶體位址時，會有一個Relocation Register，將城市內的logical address轉換成實際在記憶體位置的physical address。
### Fragmentation
由於系統記憶體分配問題，所造成問題使記憶體中有一些空間是沒辦法配置給其他人的。
**Internal Fragmentation** : 空間事先分配給了一個Process，但是Process沒有要用到這麼多。變成Process也不能使用這塊空間(超出當初要求範圍)，其他Process也不能用這塊空間(已經被分配給其他Process)。
**External Fragmentation** : 空間沒被分配給其他人，但是因為不連續而無法使用。
#### Paging
Program在進入系統變成Process時會被切成相同大小的多塊**Page**，系統的記憶體也會被切成大概是一個Page大小的**Frame**，讓一個Page剛好塞到一個Frame。
由於被切成Page，只要有剛好有一個Page大小的空間即可執行，不用整個程式都連續，可以解決External Fragmentation，但無法解決Internal Fragmentation。
### Demand Paging Virtual Memory Management Algorithm
由於有些Process比較龐大，沒辦法完全放入主記憶體，因此才有這個作法。
採用了**Virtual Memory**(backing store)的技術，載入程式不完全載入，當在執行過程中要用到時，如果在主記憶體沒有找到就表示在Hard Disk內還未被載入，這種狀況叫**Page Fault**，會將手邊工作先執行完，將Page載入後再繼續執行下去。
一般在載入Page會放進空白的Page，但是當主記憶體滿了，會選擇一個Victim，把她swap回Hard Disk並把空間釋出，這個動作叫作**Page Repalcement**，而怎麼選擇Victim就需要演算法的輔助了。
### LRU(least recently used)
最久沒被使用到的優先剃除，但還是有例外狀況。一般而言效果不錯。但由於太浪費記憶體(要記住哪時候用到哪個資料)及太浪費時間，因此實際上沒人這樣做
### Second Chance Algorithm
圍成一圈檢查，如果reference bit為0，直接被選為Victim;如果遇到reference bit為1的，就將其設為0，跳到下一個(這樣下次在遇到時就會被剔除)。Enhanced版本的會在多參考一個Modify bit(Dirty bit)。
其中:
**Reference bit** : 為1表示最近有被參考到。
**Dirty bit** : 為1表示最近有被修改。
兩者都沒有時，是最優先被選為Victim的Page。
### Thrashing
希望一個單位中所有資源的使用率盡可能提高，當使用率不夠高，OS會覺得Process不夠多，會叫Process進來，但過來一個臨界點之後，cpu使用率會急遽下降(因空間不足而不斷發生Page Replacement)，OS又更覺得使用率不足而加入新的Process的惡性循環。
最根本產生Thrashing的原因就是因為Memory太小，解法即為減少Process或者將Memory加大。
## Process結束
當Process執行結束，會釋出所有占用的資源，清空PCB最後離開系統。