第三章 行程間通訊與同步

作業系統 　第三章　行程間通訊與同步

一、          是非題

1.      　╳使用檔案（共享記憶體）進行行程間通訊，雖然方便，但傳遞的資料量比較受到限制（僅受檔案系統最大長度限制）。

2.      　○使用信號來進行行程間通訊時，可以用來傳送少量的資料。

3.      　╳（非）阻隔式傳送會讓行程在完成傳送動作後立刻離開，非阻隔式（阻隔式）傳送則會在接收端收到資料之後，才讓行程繼續後面的運算。

5.      　╳在傳輸過程中，如果接收的行程片面結束，則對方行程仍可以繼續把自己的資料傳完（透過執行的傳送或接收函式傳回錯誤代碼，或一併結束該等待行程的執行）。

6.      　○緩衝技術可以提升系統的效率。

二、          問答題

1.請說明獨立的行程與合作的行程之間有那些不同點。

答：

獨立行程不能影響其他行程或被其他行程影響；互相合作的行程可以彼此相互影響。

2.為什麼合作的行程需要同步的機制。

答：

以確保在多個合作行程同時執行的環境中，不同行程的運算不會互相干擾。

4.試解釋何謂競賽狀況？要如何避免競賽狀況的發生？

答：

當多個合作行程同時去存取相同的資料時，會因不同的指令執行順序得到不同的結果，就稱為競賽狀況。

假設某個行在正在修改一些和其他行程共享的資料，而不希望有別的行程也在修改資料，就可以將修改共享資料的程式寫在臨界區之中，來避免競賽現象

5.何謂臨界區、入口區、及出口區？

答：

臨界區：合作行程所執行的程式碼中，有些區段會涉及共用資源的使用；這些區段在執行時，不能讓其他行程也同時存取相同資源，就將這種區段稱臨界區。

入口區：確保行程執行臨界區的過程中，不會有其它行程再使用臨界區內的資源

出品區：在這個區段中，行程會釋放當初取得的許可權，讓其他行程可以進入臨界區。

6.試說明並解釋滿足臨界區的3項條件。

答：

互斥：如果某個行程正處於臨界區中，且該區段會存取一組共爭資源，則其他行程都不能進入，否則會存取到相同資源。

進行：如果目前沒有行程處於臨界區中，且有行程等待進入，則必須讓其中一個行程在有限的時間內進入。設有行程在臨界區外結束，也不能影響其它行程進入臨界區。

有限等待：行程從進入臨界區到獲准進入的時間必須有限，不能因飢餓或死結等問題而被拒進入臨界區。

7.分別說明Test-and-Set與Swap指令的作用為何？這類硬體令有何特性？

答：

◎Test-and-Set：為不可分割性的指令運算，可以確保指令只要開始執行，所有的運算就一定會全部完成。

◎Swap：可以交換兩個字組的內容。

◎都具有原子式運作的特性。

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

答：

利用佇列來實施阻隔式的等待，以完成目的。

wait( )：類似拿鑰匙的動作，拿到的人進入臨界區，其它人則開始排隊。

signal( )：類似還鑰匙的動作，將鑰匙交給下一個行程。

9.試說明使用忙碌等待的缺點。

答：

較浪費CPU時間

11.試說明在有限緩衝區問題中，empty與full號誌的功用與兩者的初始值。

答：

empty：代表緩衝區中的空白欄位，初值為n

full：代表已填入欄位的總數，初值為0

12.試說明在讀取者與寫入者問題之中，wrt與mutex號誌以及 read_cnt變數的功用。

答：

wrt：控制寫入資料時的同步。

mutex：控制read_cnt的存取。

read_cnt：記錄目前正在讀取共用資料的讀取者數目。

13.在哲學家晚餐問題中，除了本節所列的方法之外，試說明還有什麼方法可以避免死結的發生。

答：

第一回先1,3 用餐, 其它休息; 等到1,3用餐都結束了.接著 (2,4)用餐 => (3,5) 用餐 => (4,1)用餐 => (5, 2) 用餐, => (1,3)用餐...

15.何謂死結？請說明死結成立的4項條件。

答：

只要雙方都掌握了某些資源，也都需要對方的另外一些資源，就可能發生無限期地等待，造成死結。

死結成立的4項條件：

1.互斥。

2.佔用且等候：行程在等待其他資候的時候也同時佔用某些資源沒有釋放。

3.不可搶先：不能強制從已經取得資源的行程手中搶走它的資源。

4. 循環等待：兩個或更多行程形成一個封閉迴路，且其中的每個行程都在等待迴路中下個行程所佔用的某些資源。

16.試說明資源分配圖的畫法與功用。

答：

功用：利用有向邊來表示資源的佔用與請求狀況，用來描述系統中行程與資源間的狀態。

畫法：行程往資源的箭頭代表行程正在等取得資源，從資源往行程的箭頭表示行程已取得資源，資源方塊中的黑點代表資源的數量。

17.請說明如何可以解除死結？需考慮什麼因素？

答：

一、直接終止一個行程或全部行程：一次終止全部行程，則全部行程可能要重新執行，會浪費許多ＣＰＵ時間；而一次終止一個，則每次終止後，都必須執行一次死結偵測來判斷是否已解除死結狀況。

二、終止哪些行程：通常是考慮優先權較低、或是成本最低的行程。

18.請說明如何預防死結？其中的哪項條件是無法避免的？

答：

要發生死結需四項條件都成立，因此，只要防止其中一項成立，就能預防死結。

要由排除互斥條件來預防死結，基本上是不可行的。

19.請說明如何使死結的佔用且等候條件不成立。

答：

確保每個行程只有在不佔用資源的情況下，才可以請求資源。

20.請說明如何使死結的不可搶先條件不成立。

答：

當行程在等候某個資源時，允許其他行程搶先使用該行程原本佔用的資源，也就是在行程等候時，佔有的資源相當是被釋放出來；而這個行程只有在重新獲得原有的資源，加上新資源後，才能重新開始執行。

21.請說明如何使死結的循環等待條件不成立。

答：

為資源定義一個線性的優先權順序，並且規範行程在請求資源的時候，必須依照優先順序，由小到大的提出請求。

22.請解釋何謂安全狀態？為什麼系統在不安全狀態下不見得會進入死結？

答：

當系統能夠以某種安全執行序列為每個行程配置資源，並且避免死結時，就稱為安全狀態。

因為系統使用資源的時間是無法確定的，可能行程正好錯開而沒發生死結。

23.請說明為何有了資源配置圖演算法，仍然需要銀行家演算法來避免死結。

答：

資源配置圖演算法只適用於同種資源都只有一項的系統中，在有多項同種資源的系統之中，則需要以銀行家演算法來避免死結。

三、          進階題

3.請利用swap指令，完成符合有限等待條件的臨界區設計。

答：

 #程式

waiting[pid] = true; key = true; while (waiting[pid] && key) swap (lock, key);

next_pid = (pid+1) % MAX_PID; while (next_pid != pid && waiting[next_pid] == false) next_pid = (next_pid+1) % MAX_PID; if (next_pid == pid) lock = false; else waiting[next_pid] = false;

###程式

4.請說明臨界區必須滿足的三項條件，並說明下列程式段不能滿足其中哪一項條件(96台師大)

Do {

        While (TestAndSet(&lock));

        //critical section

        Lock = FALSE;

        //remainder section

} while (TRUE);

答：

(1)互斥(Mutual Exclusion)：某個行程處於臨界區並且存取一組共同資源，例如R1、R2、R3……，其他行程無法進入可存取相同資源的臨界區，即稱為互斥。

(2)持續進行(Progress)：當沒有任何行程在臨界區裡，並且有行程在等待進入臨界區，則系統必須讓其中一個等待的行程在有限的時間裡進入臨界區。如果有些行程在臨界區外就結束了，這不能影響其他行程進入臨界區。

(3)有限等待(Bounded Waiting)：行程從請求進入臨界區到獲准進入之間的時間必須是有限的。行程不能因為飢餓或死結等問題而被拒絕進入臨界區。

◎此程式段不能滿足有限等待(Bounded Waiting)的條件。

6.在下面的程式片段中，當下列執行緒執行期間，x的值可能為多少（假設x的初值為０）(96中山)

Thread 1: { for (i=0; i<10;i++) x = x + 2; }

Thread 2: { for (j=0; i<10;i++) x = x - 1; }

答：

如果完全由Thread 1先做，則過程中x可以到20。反之，如果完全由Thread 2先做，則過程中x可以到-10，因為這兩者的執行過程中可能會發生競賽狀況，所以x值可能會落在-10到20之間。

7.在下列程式中，假設有兩個具有相同臨界區的行程P0、P1，下面是P0的虛擬程式碼，請檢查這個設計可能會有什麼問題？

While (flag[1]);

Flag[0] = true;

Flag[0] = false;

答：

兩個行程同時進入臨界區

13.說明在下面的讀取程式中，if(readcount == 1) wait(wrt); 的效果。並說明寫入者程式中為什麼沒有寫入計數(writecount)？(96清大)

寫入者程式如下：

Wait(wrt);

:

:

        Writing is performed

:

:

Signal (wrt);

讀取者程式如下：

wait(mutex);

readcount++

if (readcount == 1)

        wait(wrt0;

signal(mutex);

:

:

Reading is performed

:

:

wait(mutex);

readcount--;

答：

                如果是第一個讀取者，必須去檢查寫入者是否正在寫入，所以要去wait(wrt)。

                因為一次只能有一個寫入者，其他寫入者必須等到目前沒有正在寫入者，也沒有讀取者時才能進入臨界區執行寫入，所以不需要計數。

15.假設有三個並行執行的行程，P1包含敘述S1，P2包含敘述S2，P3包含敘述S3。請利用號誌來解決同步問題，以確保S3執行後才會執行S1，且S2執行後才會執行S3。(95清大)

答：

P1:	P2:	P3:
: S1	: S2	: S3

則：

假設存在號誌A、B，將P1、P2、P3修改為：

P1:	P2:	P3:
: Wait(B) S1	: S2 Signal (A)	: Wait(A) S3 Signal(B)

18.假設資源配置圖中存在有封閉迴路，請問是否一定會發生死結呢？(96台師大)

答：

不一定。假設封閉迴路中等待資源的行程，還有其他資源可以滿足，則未必會發生死結。例如下圖：

雖然存在封閉迴圈，但是因為資源R2有兩個，而迴圈中行程P1只佔用了其中一個，所以等到P3釋放另一個R2之後，P2就可以取得所需的資源繼續執行，而不會發生死結。

19.某系統包含四個行程P1、P2、P3、P4，和三種必須循序使用的資源R1、R2、R3。這些資源的數量為(3, 2, 2)。

●P1佔用1個R1，並且請求1個R2

●P2佔用2個R2，並且請求1個R1和1個R3

●P3佔用1個R1，並且請求1個R2

●P4佔用2個R3，並且請求1個R1

請使用資源配置圖來表示該系統的狀態。請問會發生死結嗎？如果會的話，請問有哪些行程是處於死結狀態。如果不會，請舉出一個安全序列。(94雲科大)

答：

不會形成死結。

當前系統閒置資源為1個R1，可執行P4。P4執行後，閒置資源為1個R1，2個R3，可執行P2。P2執行後，閒置資源為1個R1，2個R2及2個R3，可執行P1。P1執行後閒置資源為2個R1，2個R2及2個R3，可執行P3。P3執行後閒置資源為3個R1，2個R2及2個R3。

安全執行序列為P4＞P2＞P1＞P3。

23.一個系統行程與資源的配置如下所示：

行程	需要資源數目 Ａ　Ｂ　　Ｃ　Ｄ	持有資源數目 Ａ　Ｂ　　Ｃ　Ｄ	系統未配置資源數目 Ａ　Ｂ　　Ｃ　Ｄ
P1	０　１　　１　２	１　２　　１　０	１　４　　１　２
P2	１　２　　１　１	５　１　　３　１
P3	１　５　　２　４	２　１　　４　２
P4	０　２　　６　３	５　３　　０　２
P5	４　０　　４　４	１　４　　２　０

請利用銀行家演算法回答下列問題：

a.       系統是否目前處於安全狀態之中？

b.      系統是否可以允許P3所提出的(0, 1, 0, 2)的資源要求？

c.       系統是否可以允許P2所提出的(1, 2, 1, 1)的資源要求？

答：

a. 是。系統目前處於安全狀態，而且有多個可能的安全序列(只要存在至少一個，系統就是安全的了)。例如，其中的一個安全序列為P1-P2-P3-P4-P5。

b. 如果將(0,1,0,2)配置給P3之後，就不存在安全序列，所以不能允許要求。

c. 將(1,2,1,1)配置給P2之後，P2具有執行所需的max資源數目，所以可以順利執行完，並且釋放其持有之所有資源。因此，配置之後系統仍可以找到不只一組安全序列(都是以P2開始)，例如P2-P1-P3-P4-P5等，所以可以允許。

26.假設某系統共有R的總數為8，請判斷下列系統是否處於安全狀態，如果是的話，請寫出它的一個安全執行序列。

行程	需要 R 的總數	持有 R 的數目
P1	8	1
P2	5	2
P3	1	1
P4	7	2
P5	3	0

答：

目前系統閒置資源為2，P3不需請求資源，可先執行，執行後閒置資源為3，可執行P5，執行後閒置資源為3，可執行P2，執行後閒置資源為5，可執行P4，執行後閒置資源為7，可執行P1。

因此安全執行序列為P3＞P5＞P2＞P4＞P1。