HW5

1.    一個排程法決定了行程的執行順序，假設系統中有n 個不可搶先的行程需要排程，可能產生哪幾種不同的執行順序？請用n 寫出一個公式。

　　當決定開始的1個行程時，有ｎ種排序方式；

當決定開始的2個行程時，有ｎ-1種排序方式；

當決定開始的3個行程時，有ｎ-2種排序方式；

當決定開始的4個行程時，有ｎ-3種排序方式；

…

當決定開始的ｎ-1個行程時，有2種排序方式；

當決定開始的n行程時，只有1種排序方式。

　　將上述描述簡化為公式，

n*(n-1)* (n-2)* (n-3)*…*2*1，此方程式正可寫成n!，

故此公式為　n!。

2.    試說明行程之間為何要同步？

　　同步是當A行程執行出結果，B行程取得A行程結果才可接下去執行的機制。

　　在多行程的系統中，通常會有數個行程相互合作以解決較複雜的問題。行程間的相互合作除了使用執行緒來共享的資料外，可以讓行程間存取一些共享的變數，不過同時存取共享的變數可能會導致材料的不一致，造成結果的錯誤，因此需要同步的機制來解決這些問題。即同一時間只能讓一個行程取存取一個變數，讓一個行程更改資料的動作不會影響到其他行程的執行結果。

3.    說明號誌的作用為何？並分別說明號誌中wait()與signal() 的作用

　　號誌包含一個數值，也就是該號誌的值，作為行程間同步的工具。該值在初始化之後就只能經由兩個不可被中斷的函式去存取，分別是signal()與wait()，所以當一個行程在存取號誌的值，其他行程無法存取同一個號誌的值，號誌讓同步問題變得較容易解決。

4.    試說明為什麼阻隔式的號誌實作能大幅地縮短忙碌等待的時間

　　忙碌等待是有行程進入了臨界區，那其他想要進入臨界區的行程都會在入口區中一直地執行迴圈來等待。

　　為了避免忙碌等待所造成的CPU資源浪費，可修改wait()與signal()兩個函式。組隔式號誌方法是當行程呼叫wait()且號誌的值小於0或等於0的時候，我們不再讓行程作忙碌等待，而是直接讓行程將自己阻隔起來。除了原有的整數可記錄號誌的值，還另外增加了一個串列，紀錄正在該號誌等待的行程。block()和wakeup()兩個函式是大部分作業系統都有提供的基本系統呼叫，block()會將現行行程的狀態更改為等待狀態，並將現行行程由就緒佇列移入等待佇列中；叫醒行程的動作則由wakeup()執行，她會將被叫醒的行程由等待狀態更改為就緒狀態，並將行程放入就緒佇列中。由原來的整個臨界區可縮短到只有實作wait()和signal()的臨界區所造成的忙碌等待時間。