---
tags: 大三筆記
---

# 海大作業系統(下)

> 內容節錄於：林致宇教授的課程。

## ch6：如何處理多行程

* **<font color=red>Race Condition</font>**
:::success
多個Process共同存取同一個資料，
會因為Process的執行順序不同、context switch的發生時間不同，
而造成結果不同。

:::

* **<font color=red>Critical section</font>**

:::success
每個Process有屬於自己的critical section。

Process會把共同存取到的程式碼，放入Critical section中。
同一時間只能讓一個Process進入自己的Critical section，來避免Race Condition。
:::

:::spoiler
* **Context switch**
context switch的發生時間不同，造成Race Condition。
:::success
從process A 切換到 B 的過程
:::

<hr>

:::spoiler
* **Peterson’s Solution**
flag 有沒有process想進入critical section
turn 有沒有process在Critical section

:::success
讓Critical section同時只會有一個程序執行。
不過在multi processor，會受到Reordering影響。
:::

<hr>

* **test_and_set**

:::success
true $\rightarrow$ return true, lock改為true
false $\rightarrow$ return false, lock改為true
:::

* **<font color=red>bounded waiting mutual exclusion (test_and_set)</font>**

while(true){
    waiting[i] = true; //欲想進入，排進等待
    while(waiting[i] && test_and_set(&lock));
        /* do nothing */
    waiting[i] = false;
    
    /*critical section*/
    
    j = (i+1)%n; // 找下一個進入者
    while((j!=i) && !waiting[j]) // 問一輪
        j = (j+1)%n;
    if(j==i) // 大家都不想進入的話
        lock = 0;
    else // 讓j進入
        waiting[j] = false;
    
    /*remainder section*/
}

利用了Peterson’s Solution的概念。
:::spoiler
:::success
* Mutual exclusion(互斥)：任一時間點，只允許一個 process 進入他自已的 critical section。
* Bound waiting：自 process 提出進入 critical section 的申請到獲准進入 critical section 的等待時間是有限的。即若有 n 個 processes 想進入，則任一 process 至多等待 n-1 次即可進入，隱含 No starvation。
:::

:::spoiler
* **compare_and_swap**

:::success
true $\rightarrow$ return true, 跟 expected 不一樣改new_value
false $\rightarrow$ return false, 跟 expected 不一樣改new_value
:::

<hr>

* **Mutex Locks**
:::success
防止程序同時使用同一個記憶體資源。
* acquire() $\rightarrow$ 等待資源釋放
* release() $\rightarrow$ 釋放資源


問題：Busy waiting (Spinlock) 無謂的等待，瞎忙的迴圈(佔用CPU資源)。
:::

* **Semaphores**
:::success
S是號誌(可用資源的數量)：>0就可用，<=0就進入等待
* wait() $\rightarrow$ 等待資源釋放
* signal() $\rightarrow$ 釋放資源



透過sleep()暫停自己，而避免Busy waiting的問題。


:::spoiler
* wait()：希望使用資源的行程，對semaphore 執行wait()
* signal()：當行程釋放資源時，執行signal()
:::

* **總結**
:::success
* Mutex Locks的問題：Busy waiting (Spinlock) 無謂的等待。
* Semaphores的解法：紀錄可用資源的數量，用sleep()暫停自己，避免Busy waiting。
* 多核處理器，在Busy waiting下不需切換執行緒(減少切換的資源浪費)，反而可以降低功耗。
:::

## ch8：多行程的問題Deadlock

* **Deadlock**
兩個以上的行程，等待一項只能等待的行程，導致系統資源無法使用。
:::success
* 只發生在有兩個或兩個以上優先權的系統。
* 優先權繼承協定：讓優先度高的先執行。
* 哲學家晚餐問題。


:::

* **Deadlock條件(哲學家晚餐問題)**
:::success
1. Mutual exclusion(mutex)：筷子一次只能一人使用(至少一個資源不共享)
2. Hold and wait：拿著一隻筷子，等待另一隻筷子(需要拿到兩個資源才能執行)
3. No preemption：不可以搶別人的筷子(不可搶佔資源)
4. Circular wait：大家都互相等待其他人的筷子，成為一個閉環($T_1>T_2>...>T_n>T_1$)


:::

* **Deadlock如何防範**
:::success
1. Prevention預防：解決其中一個發生條件
* Mutual exclusion：如果資源可共享，就能避免。
* Hold and wait：哲學家只能拿一雙筷子或不拿(執行前，不佔用資源)。
有可能Starvation，資源使用率低。
* No Preemption：哲學家拿不到另一隻筷子，就把筷子禮讓給別人。
* Circular Wait：讓使用筷子的順序不是閉環。

2. Avoidance避免：要求OS給出請求資源的額外資訊。

3. Detection/Recovery偵測並回復：發生後再解決。
* Detection去偵測死結。
* Recovery(搶佔或終止)去回復正常。

4. Ignorance無知：重開機。
:::

## ch9：Main Memory

* **Memory**
:::success
Program Codes：利用program counter紀錄執行的指令。
Data：利用指令，將加載、儲存到特定位址。
:::

:::success
* 整個 process 的資料連續存放在記憶體中。
* 新來的 process，被放入 hole 中。

:::

<hr>

* **如何插入hole中**：
**First-fit, Best-fit, and Worst-fit**

1. **First-fit：分配第一個足夠大的hole**
:::success
:::
2. **Best-fit：足夠大的最小hole(lower_bound)**
:::success
:::
3. **Worst-fit：最大的hole**
:::success
:::

<hr>

* **Fragmentation(記憶體的浪費)**
分為程序內部與外部的斷裂。
1. **External fragmentation**
process來去的過程中，會在Process跟process間留下可用的記憶體片段
:::success
破碎的記憶體總和足夠讓新程序進來，但因為不連續無法放入。
可以用 compaction 壓縮(將程序全部往前挪)。
:::

2. **Internal fragmentation**
程序放入hole中，仍要將整個單位的空間取走所形成的小塊空間。
這些小塊因為太小而無法容納任何資料。
:::success

可以用 Paging <font color='red'>減緩</font>問題(無法解決)。
:::

<hr>

* **Paging**
:::success
* 把‌Memory分成多個frames。
* 把‌Process分成多個pages，來放入可用的記憶體片段。

:::
* **透過Paging <font color='red'>減緩</font>Internal fragmentation**
:::success

We expect internal fragmentation to average **one-half** page per process.

調小page size可以減緩內部斷裂，但維護page/frame tables的開銷大。
:::

<hr>

* **如何更有效率地使用Paging與設計page table。**
1. **Hierarchical Paging**
:::success

* 因為page太大，所以不去連續分配page。
* 透過階層式向下尋找：
從最上層的page table找到下一層的page table，直到最下層的記憶體位址。
:::

2. **Hashed Page Tables**
:::success
* Virtual page number
* Mapped page frame
* 下一個element的指標
:::

3. **Inverted Page Tables(反轉分頁表)**
:::success

對physical address建立page table，去紀錄被哪個process的page所使用。
* process id
* page number
:::

## ch10：[Virtual Memory](https://ithelp.ithome.com.tw/articles/10208354)
* FIFO Page Replacement
:::success
* 將queue的front取代
:::

* Optimal Page Replacement(預測未來)
:::success
* 將未來最常沒用到的取代(最右邊)
:::

* Least Recently Used(LRU)(以古鑑今)
:::success
* 將過去最不常使用到的取代(最左邊)
:::
* Global Replacement：可以取代所以有的frame。
* Local Replacement：只能取代自己記憶體中的frame。