海大作業系統(下)

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

ch6：如何處理多行程

• Race Condition

多個Process共同存取同一個資料，
會因為Process的執行順序不同、context switch的發生時間不同，
而造成結果不同。

• Critical section

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

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

• Context switch
  
  
  context switch的發生時間不同，造成Race Condition。

從process A 切換到 B 的過程

---

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

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

---

• test_and_set
  　
  

true

$\to$ return true, lock改為true
false

$\to$ return false, lock改為true

• bounded waiting mutual exclusion (test_and_set)

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的概念。

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

• compare_and_swap
  　
  
  

true

$\to$ return true, 跟 expected 不一樣改new_value
false

$\to$ return false, 跟 expected 不一樣改new_value

---

• Mutex Locks

防止程序同時使用同一個記憶體資源。

• acquire()
  $\to$ 等待資源釋放
• release()
  $\to$ 釋放資源

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

• Semaphores

S是號誌(可用資源的數量)：>0就可用，<=0就進入等待

• wait()
  $\to$ 等待資源釋放
• signal()
  $\to$ 釋放資源

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

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

• 總結

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

ch8：多行程的問題Deadlock

• Deadlock
  兩個以上的行程，等待一項只能等待的行程，導致系統資源無法使用。

• 只發生在有兩個或兩個以上優先權的系統。
• 優先權繼承協定：讓優先度高的先執行。
• 哲學家晚餐問題。

• Deadlock條件(哲學家晚餐問題)

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

• Deadlock如何防範

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

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

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

---

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

1. First-fit：分配第一個足夠大的hole

2. Best-fit：足夠大的最小hole(lower_bound)

3. Worst-fit：最大的hole

---

• Fragmentation(記憶體的浪費)
  分為程序內部與外部的斷裂。

1. External fragmentation
   process來去的過程中，會在Process跟process間留下可用的記憶體片段

破碎的記憶體總和足夠讓新程序進來，但因為不連續無法放入。
可以用 compaction 壓縮(將程序全部往前挪)。

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

可以用 Paging 減緩問題(無法解決)。

---

• Paging

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

• 透過Paging 減緩Internal fragmentation

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

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

---

• 如何更有效率地使用Paging與設計page table。

1. Hierarchical Paging

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

2. Hashed Page Tables

• Virtual page number
• Mapped page frame
• 下一個element的指標

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

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

• process id
• page number

ch10：Virtual Memory

• FIFO Page Replacement

• 將queue的front取代

• Optimal Page Replacement(預測未來)

• 將未來最常沒用到的取代(最右邊)

• Least Recently Used(LRU)(以古鑑今)

• 將過去最不常使用到的取代(最左邊)

• Global Replacement：可以取代所以有的frame。
• Local Replacement：只能取代自己記憶體中的frame。