冷笑話
1.什麼數字最聽話呢?
100(因為[百]依[百]順)
2.糖與醋有什麼不同?
你可以請人吃糖,但不可以請人吃醋
3.什麼東西外國人比較長,中國人比較短,而和尚卻用不到?
姓名的[姓]
4.鉛筆姓什麼?
蕭,因為:削(蕭)鉛筆
2010年5月6日 星期四
第三章 行程間通訊與同步
作業系統 第三章 行程間通訊與同步
一、 是非題
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。
訂閱：
文章 (Atom)