習(xí) 題
0?進程和線程的本質(zhì)區(qū)別是什么？
答：進程是一組相關(guān)資源的集合。進程有一個存放程序正文和數(shù)據(jù)以及其他資源的地址空間。這些資源包括打開的文件、子進程、未處理的定時器、信號處理器和審計信息。通過進程形式把他們放在一起，方便進行管理。
線程是進程的一個執(zhí)行流。線程有一個程序計數(shù)器，用來跟蹤下一條將要執(zhí)行的指令。它有寄存器，存儲當(dāng)前使用的變量。它有堆棧，存儲著執(zhí)行的歷史，其中每一棧幀保存了沒有返回的過程調(diào)用。
盡管線程必須在進程中執(zhí)行，但線程和它的進程是可以分別對待處理的兩個不同概念。進程用來集合資源，而線程是CPU中的調(diào)度的實體。
1 假設(shè)你正在設(shè)計一種先進的計算機體系結(jié)構(gòu)，它使用硬件而不是中斷來完成進程切換，則CPU需要哪些信息？請描述用硬件完成進程切換的工作過程
答：應(yīng)該有一個寄存器包含當(dāng)前進程表項的指針。當(dāng)I/O結(jié)束時，CPU將把當(dāng)前的機器狀態(tài)存入到當(dāng)前進程表項中。然后，將轉(zhuǎn)到中斷設(shè)備的中斷向量，讀取另一個過程表項的指針（服務(wù)例程），然后，就可以啟動這個進程了。
2 目前的計算機上，中斷處理程序至少有一小部分用匯編語言編寫，為什么？
答：通常，高級語言不允許訪問CPU硬件，而這種訪問是必需的。例如，中斷處理程序可能需要禁用和啟用某個特定設(shè)備的中斷服務(wù)，或者處理進程堆棧區(qū)的數(shù)據(jù)。另外，中斷服務(wù)例程需要盡快地執(zhí)行。
3 書中認(rèn)為圖2－6（a）的模型不適用于在內(nèi)存進行高速緩存的文件服務(wù)器，為什么？可否使每個進程擁有自己的cache？
答：（進程相互獨立，當(dāng)兩進程同時操作內(nèi)存，一個寫一個讀，可能造成不一致。）即使是有可能實現(xiàn)，也是很難保持文件系統(tǒng)的一致性。假設(shè)某個客戶進程給服務(wù)器進程1發(fā)送請求要更新文件。該進程更新其內(nèi)存的cache項。然后，另一個客戶進程給服務(wù)器進程2發(fā)送請求讀取該文件。不幸的是，如果該文件還在 cache中，服務(wù)器進程2對此毫不知情，將返回過時的數(shù)據(jù)。如果第一個進程在緩沖后將文件寫到磁盤中， 而服務(wù)器進程2每次讀取時檢查磁盤其緩存的備份是否是最新的，系統(tǒng)還可以工作，但是需要避免磁盤訪問的所有緩存系統(tǒng)。
4 在使用線程的系統(tǒng)中，是每個線程有一個堆棧還是每個進程有一個堆棧，說明原因。
答：每個線程都是自己調(diào)用例程，因此它必須有其自己的堆棧以保存局部變量、返回地址等等。這一點用戶級線程和內(nèi)核級線程是一樣的。
5 什么是競爭條件？
答：兩個或多個進程讀寫某些共享數(shù)據(jù)，而最后的結(jié)果取決于進程運行的精確時序，就稱為競爭條件(race conditions)。
6 寫一個shell程序，其功能是產(chǎn)生一個內(nèi)容為一個整數(shù)序列的文件，要求它先讀取文件中的最后一個整數(shù)，將其加1，然后將這個新整數(shù)追加到文件的末尾。在系統(tǒng)前臺和后臺同時運行它并使用相同的文件名。在因競爭而造成的故障發(fā)生之前它能運行多久？此處的臨界區(qū)是什么？請對其進行修改以防止發(fā)生競爭。（提示：使用ln file file.lock來將數(shù)據(jù)文件加鎖）
7 對于前一問題，如下的語句 ln file file.lock 是一種很有效的加鎖機制嗎？說明原因。
答：
一個可行的shell腳本應(yīng)該如下：
if[ ! –f numbers ]; then echo0> numbers; fi
count=0
while(test $count !=200)
do
count=‘expr $count +1’
n=‘tail –1numbers’
expr $n +1>>numbers
done
??同時運行該腳本兩次，通過后臺啟動它一次（使用）和再次在前臺啟動。然后檢查文件編號。它可能開始看起來會像數(shù)字的有序列表，但在某一時刻，由于運行腳本的兩個副本而創(chuàng)建的競爭條件，它就失去了它的規(guī)律。通過對腳本的每一個副本測試，并在進入關(guān)鍵區(qū)域之前設(shè)置一個鎖，在離開關(guān)鍵區(qū)域時打開它，可以避免競爭?？梢赃@樣做：
ifln numbers numbers.lock
then?
n=‘tail –1numbers’
expr $n +1>>numbers
? ? rm numbers.lock?
fi
此版本只是當(dāng)文件無法訪問時直接跳過，不同的解決方案可以讓進程休眠，忙等待，或僅僅循環(huán)計數(shù)，使得操作成功。
8 兩個進程在一臺共享內(nèi)存的多處理機（即共享同一個存儲器）上運行時，圖2－8所示的采用變量turn的忙等待方案還奏效嗎？
答：可能一個進程儲存的內(nèi)容在其掛起時被另一個進程修改。忙等待應(yīng)該被避免，浪費CPU時間，輪流進入臨界區(qū)如果一個進程比另一進程慢很多時，不適用。
9 現(xiàn)有一臺計算機，不具備TEST AND SET LOCK指令，但有一條指令可以按原子操作方式將一個寄存器的值和一個存儲器字進行交換，能否利用該指令寫一個與圖2－10中enter_region類似的例程？
第一條指令將lock原來的值拷貝到寄存器中并將lock置為1，隨后這個原先的值與0相比較。如果它非零，則說明先前已被上鎖，則程序?qū)⒒氐介_頭并再次測試。經(jīng)過或長或短的一段時間后它將變成0（當(dāng)前處于臨界區(qū)中的進程退出臨界區(qū)時），于是子例程返回，并上鎖。清除這個鎖很簡單，程序只需將0存入lock即可，不需要特殊的指令。
進程在進入臨界區(qū)之前先調(diào)用enter_region。這將導(dǎo)致忙等待，直到鎖空閑為止。隨后它獲得鎖變量并返回。在進程從臨界區(qū)返回時它調(diào)用leave_region，這將把lock置為0。與臨界區(qū)問題的所有解法一樣，進程必須在正確的時間調(diào)用enter_region和leave_region，解法才能奏效。如果一個進程有欺詐行為，則互斥將會失敗。
10 給出一個框架，來描述一個可禁止中斷的操作系統(tǒng)如何實現(xiàn)信號量。
11 請說明如何只利用二進制信號量和普通的機器指令來實現(xiàn)計數(shù)信號量（即可以擁有任意大的數(shù)值的信號量）。
答：將每個計數(shù)信號量與2個二值信號量聯(lián)合：M用于互斥；S用于阻塞。另外，每個計數(shù)信號量都組合一個用于保存up次數(shù)減去down次數(shù)的計數(shù)器，以及在該信號量上阻塞的進程列表。為了實現(xiàn)down操作，進程首先通過對M執(zhí)行down操作，以獲得對信號量、計數(shù)器以及列表的獨占訪問權(quán)。然后，將計數(shù)器減 1。如果大于等于0, 只需對M執(zhí)行up操作并退出即可。如果M為負(fù)數(shù)，就將該進程放入阻塞進程列表中。接著，對M執(zhí)行up操作，對S執(zhí)行down操作來阻塞該進程。為了實現(xiàn)up操作，首先對M執(zhí)行down操作以獲得互斥，然后將計數(shù)器加1。如果計數(shù)器大于0, 則沒有進程阻塞，就只需對M執(zhí)行up操作。不過， 如果計數(shù)器小于等于0, 則必須從列表中移出某些進程。最后，按次序?qū)和M執(zhí)行up操作。
12 在 2.2.4節(jié)中描述了一個高優(yōu)先級進程H和低優(yōu)先級進程L的情況，它最終導(dǎo)致H陷入死循環(huán)，若采用時間片調(diào)度而不是優(yōu)先級調(diào)度，還能發(fā)生這種情況嗎？請進行討論。
考慮一臺計算機有兩個進程，H優(yōu)先級較高，L優(yōu)先級較低。調(diào)度規(guī)則規(guī)定只要H處于就緒態(tài)它就可以運行。在某一時刻，L處于臨界區(qū)中，此時H變到就緒態(tài)準(zhǔn)備運行（例如，一條I/O操作結(jié)束）?，F(xiàn)在H開始忙等待，但由于當(dāng)H就緒時L不會被調(diào)度，也就無法離開臨界區(qū)，所以H將永遠忙等待下去。這種情況有時被稱作優(yōu)先級翻轉(zhuǎn)問題(priority inversion problem)。
時間片調(diào)度：每個進程被分配一個時間段，稱作它的時間片，即該進程允許運行的時間。如果在時間片結(jié)束時進程還在運行，則CPU將被剝奪并分配給另一個進程。如果進程在時間片結(jié)束前阻塞或結(jié)束，則CPU當(dāng)即進行切換。時間片輪轉(zhuǎn)調(diào)度很容易實現(xiàn)。調(diào)度程序所要做的就是維護一張就緒進程列表，當(dāng)進程用完它的時間片后，它被移到隊列的末尾。
答：不會。
13 管程內(nèi)部的同步機制使用條件變量和兩個特殊操作WAIT和SIGNAL，一種更一般的同步方式只有一條原語WAITUNTIL，它以任意的布爾表達式作為參數(shù)。例如 WAITUNTIL x<0 or y+z<n 這樣便不再需要SIGNAL原語。很顯然這個方案比 Hoare 和Brinch Hansen的方案更通用，但它從未被采用過，為什么？（提示：從實現(xiàn)考慮）
答：其實現(xiàn)的代價很高。 每次在某些等待變化的進程的謂詞中出現(xiàn)的任何變量， runtime系統(tǒng)都必須重新計算該謂詞，以判斷該進程是否能夠被解鎖。而對于 Hoare和Brinch Hansen管程，則只需signal原語即可喚醒進程。
14 一個快餐廳有四種職員：（1）領(lǐng)班，他們接收顧客點的菜單（2）廚師，準(zhǔn)備飯菜（3）打包工，將飯菜裝在袋子里（4）出納員，收錢并將食品袋交給顧客。每個職員可被看作一個進行通信的串行進程，它們采用的進程間通信方式是什么？將該模型與MINIX中的進程加以比較。
答：雇員之間通過消息傳遞進行通信：在該例中，消息為訂單、食物和袋子。在UNIX中，該4個進程通過管道連接。
15 假設(shè)有一消息傳遞系統(tǒng)使用信箱，一個進程向滿信箱發(fā)消息或從空信箱收消息都不會阻塞，進程對錯誤碼的處理方式為重試，直到成功為止，這種方案會帶來競爭嗎？
答：它不會導(dǎo)致競爭條件（不會丟失任何東西），不過它是完全的忙等待。
16 在圖2－20所示的哲學(xué)家用餐問題的解法中，為什么過程take_forks將狀態(tài)變量置為HUNGRY？
使用一個數(shù)組state來跟蹤一個哲學(xué)家是在吃飯、思考還是正在試圖拿叉子。一個哲學(xué)家只有在兩個鄰居都不在進餐時才允許轉(zhuǎn)移到進餐狀態(tài)。第i位哲學(xué)家的鄰居由宏LEFT和RIGHT定義，換言之，若i為2，則LEFT為1，RIGHT為3。哲學(xué)家在拿起叉子take_forks時，將其狀態(tài)status[i]=HUNGER。
17 考慮圖2－20中的過程put_forks，假設(shè)變量state[i]在對test的兩次調(diào)用之后被置為THINKING，而不是在調(diào)用之前。對于3位哲學(xué)家的情況這個改動有什么影響？對于100位哲學(xué)家的情況呢？
答：可能發(fā)生阻塞的情況。該變化將意味著在哲學(xué)家停止進餐后，他的鄰居都不能接著被選擇。事實上，他們永遠不會被選擇。假設(shè)哲學(xué)家2完成了進餐，他將為哲學(xué)家1和3運行test，而兩者都不會被啟動，即使他們兩個都餓了而且兩個叉子都是可用的。類似的，如果哲學(xué)家4完成進餐，哲學(xué)家3也不會被啟動。他將無法啟動。
哲學(xué)家問題對于多個競爭進程互斥地訪問有限資源（如I/O設(shè)備）這一類問題的建模十分有用。
18 從何種類型的進程可以在何時被啟動的角度來看，讀者－寫者問題可以通過幾種方式進行形式化。根據(jù)優(yōu)先哪幾類進程的不同，請詳細(xì)地描述該問題的三種變體。對每種變體，請說明當(dāng)一個讀者或?qū)懻吣軌蛟L問數(shù)據(jù)庫時情況將會怎樣，以及當(dāng)一個進程對數(shù)據(jù)庫訪問結(jié)束后又將會怎樣。
讀者－寫者問題，它為數(shù)據(jù)庫訪問建立了一個模型。例如，設(shè)想一個飛機定票系統(tǒng)，其中有許多競爭的進程試圖讀寫其中的數(shù)據(jù)。多個進程同時讀是可以接受的，但如果一個進程正在更新數(shù)據(jù)庫，則所有其他進程都不能訪問數(shù)據(jù)庫，即使讀操作也不行。
答：變種1：讀者優(yōu)先。當(dāng)讀者活躍時，寫者都無法啟動。當(dāng)一個新的讀者出現(xiàn)時，它可以立即開始除非當(dāng)前有寫者是活躍的。當(dāng)寫者完成時，如果有讀者在等待，他們?nèi)紗?，無論是否有寫者存在。
變種2：寫者優(yōu)先。當(dāng)有寫者等待時，讀者都不會開始。當(dāng)最后活躍的進程結(jié)束，如果有寫者，就啟動它；否則，所有讀者（如果有）全部開始。
變種3：平衡的版本。當(dāng)有讀者是活躍的，新的讀者可以立即開始。當(dāng)寫者完成時，新的寫者優(yōu)先，如果有寫者等待的話。也就是說，一旦開始讀，就一直讀到?jīng)]有讀者為止。同樣地，一旦開始作，所有掛起的寫者都被允許運行。
19 CDC6600計算機使用一種有趣的稱作處理器共享的時間片調(diào)度算法，它可以同時處理多達10個I/O進程，每條指令結(jié)束后都進行進程切換，這樣進程1執(zhí)行指令1，進程2執(zhí)行指令2，等等。進程切換由特殊的硬件完成，所以沒有開銷。如果在沒有競爭的條件下一個進程需要T秒鐘完成，那么當(dāng)有n個進程共享處理器時需要多長時間完成？
答：它需要nT sec。
20 時間片調(diào)度程序通常維護一個有所有就緒進程組成的隊列，每個進程在隊列中出現(xiàn)一次。如果一個進程在隊列中出現(xiàn)兩次以上，情況將會怎樣？你能設(shè)想出這種情況出現(xiàn)的原因嗎？
答：間片調(diào)度：每個進程被分配一個時間段，稱作它的時間片，即該進程允許運行的時間。如果在時間片結(jié)束時進程還在運行，則CPU將被剝奪并分配給另一個進程。如果進程在時間片結(jié)束前阻塞或結(jié)束，則CPU當(dāng)即進行切換。時間片輪轉(zhuǎn)調(diào)度很容易實現(xiàn)。調(diào)度程序所要做的就是維護一張就緒進程列表，如圖2-22（a）所示，當(dāng)進程用完它的時間片后，它被移到隊列的末尾，如圖2-22（b）所示。
21 對某系統(tǒng)進行監(jiān)測后表明平均每個進程在I/O阻塞之前的運行時間為T。一次進程切換需要的時間為S，這里S實際上即為開銷。對于采用時間片長度為Q的時間片調(diào)度法，對以下各種情況給出CPU利用率的計算公式。
(a) Q=∞
(b) Q>T
(c) S<Q<T
(d) Q=S
(e) Q 趨近于0
答：CPU的效率就是有用的CPU時間除以整個的CPU時間。當(dāng)Q > T時，基本的周期就是進程運行T，然后進程切換S。因此，（a）和（b）的效率都是T/(T+S)。當(dāng)時間片比T短時，每運行一次T就要求T/Q次進程切換，浪費時間為ST/Q。因此，其效率為T/(T+ST/Q)也就是下降到 Q/(Q+S)，這就是（c）的答案。至于（d），只需以S替代Q，就可以計算出其效率為50%。最后，（e)的效率趨近于0。
22 有5個待運行任務(wù)，各自預(yù)計運行時間分別是9, 6, 3, 5和X。采用哪種運行次序?qū)⑹蛊骄憫?yīng)時間最短？ （答案依賴于X）
答：最短作業(yè)優(yōu)先可以使得平均響應(yīng)時間最短。
0 < X ≤ 3: X, 3, 5, 6, 9.
3 < X ≤ 5: 3, X, 5, 6, 9.
5 < X ≤ 6: 3, 5, X, 6, 9.
6 < X ≤ 9: 3, 5, 6, X, 9.
X > 9: 3, 5,6, 9, X.
23 有5個批處理任務(wù)A到E幾乎同時到達一計算中心。其預(yù)計運行時間分別為10， 6， 2， 4和8分鐘。其優(yōu)先級（由外部設(shè)定）分別為3，5，2，1和4，這里5為最高優(yōu)先級。對于下列每種調(diào)度算法，計算其平均進程周轉(zhuǎn)時間，進程切換開銷可忽略。
(a) 時間片輪轉(zhuǎn)
(b) 優(yōu)先級調(diào)度
(c) 先來先服務(wù)（按照次序 10， 6， 2， 4， 8）
(d) 最短作業(yè)優(yōu)先
對（a），假設(shè)系統(tǒng)具有多道處理能力，每個作業(yè)均獲得公平的CPU份額，對（b）到（d）假設(shè)一時刻只有一個作業(yè)運行，直到結(jié)束。所有的作業(yè)都是完全的CPU密集型作業(yè)。
答：對于時間片輪轉(zhuǎn)，在頭10分鐘里，每個作業(yè)獲得1/5的CPU時間。在第10 分鐘時，C結(jié)束。在接下來的8分鐘里，每個作業(yè)獲得 1/4 的CPU時間，然后D完成，然后，在接下來的6分鐘內(nèi)，余下的3個作業(yè)各獲得1/3的CPU時間，直到B結(jié)束，以此類推。因此，5個作業(yè)的完成時間分別為是10, 18, 24, 28和30, 平均為22分鐘。
對于優(yōu)先級調(diào)度，5最先運行，6分鐘完成。其它作業(yè)分別在第14, 24, 26和30分鐘完成，平均為18.8分鐘。
如果作業(yè)按A->E的次序執(zhí)行，則分別在第10,16, 18, 22和30分鐘完成，因此，平均為19.2分鐘。
最后，最短作業(yè)優(yōu)先調(diào)度的完成時間分別為第2, 6, 12, 20和30分鐘，平均為14分鐘。
24 在CTSS上運行的一個進程需要30個時間片方能結(jié)束，則它需要被換入多少次？包括第1次，即開始運行之前。
CTSS（多重隊列）是最早使用優(yōu)先級調(diào)度的系統(tǒng)之一。但是CTSS存在進程切換速度太慢的問題，其原因是IBM 7094內(nèi)存中只放得下一個進程，每次切換都需要將當(dāng)前進程換出到磁盤，并從磁盤上讀入一個新進程。CTSS的設(shè)計者很快便認(rèn)識到為CPU密集的進程設(shè)置較長的時間片，比頻繁地分給它們很短的時間片要高效（減少交換次數(shù)）。另一方面，如前所述，給進程長時間片又會影響響應(yīng)時間。他們的解決辦法是設(shè)立優(yōu)先級類。屬于最高級類的進程運行一個時間片，屬于次高優(yōu)先級類的進程運行2個時間片，再次一級運行4個時間片，依次類推。當(dāng)一個進程用完分配的時間片后，它被移到下一類。
答：第一次得到 1 個時間片。隨后獲得 2, 4, 8 和 15 個時間片，因此必須經(jīng)過 5 次交換。
25 使用一個參數(shù) a=1/2的老化算法來預(yù)測運行時間。從最早到最近的前4次執(zhí)行時間分別為40，20，40和15毫秒，則下次運行時間預(yù)計為多長？
答：預(yù)測值的順序為40，30，35，所以下一次是25。（把前兩個數(shù)據(jù)加一起，除以2，然后把結(jié)果和下一個數(shù)據(jù)加一起，除以2。）
26 一個軟實時系統(tǒng)有4個周期性事件，其周期分別為50，100，300和250毫秒。假設(shè)其處理分別需要35， 20，10和X毫秒，則該系統(tǒng)可調(diào)度所允許的X值最大是多少？
答：所使用的 CPU 的片斷為 35/50 + 20/100 + 10/200 + x/250。為了使得進程可調(diào)度，必須是總和小于1。因此，x必須小于等于2.5ms。
27 解釋兩級調(diào)度為什么被廣泛采用？
答：當(dāng)內(nèi)存太小不能載入所有就緒進程時，就需要使用兩級調(diào)度。某些進程被載入內(nèi)存，并且從中選擇一個運行。內(nèi)存中進程會隨著時間調(diào)整。這種算法容易實現(xiàn)也非常有效，另外，時間片輪轉(zhuǎn)調(diào)度并不管進程是否在內(nèi)存中。
28 MINIX在執(zhí)行期間維護一個變量proc_ptr，它指向當(dāng)前進程的進程表項，為什么？
29 MINIX對消息不加緩沖，請解釋這樣的設(shè)計會對時鐘和鍵盤中斷帶來什么問題？
30 在MINIX中當(dāng)一條消息被發(fā)送給一個睡眠進程時，將調(diào)用過程ready來將該進程掛入適當(dāng)?shù)恼{(diào)度隊列中，該過程首先要關(guān)中斷，為什么？
31 MINIX中的mini_rec過程包含一個循環(huán)，請解釋為什么需要該循環(huán)。
32 MINIX使用圖2－23所示的調(diào)度方法，其中不同類型的進程有不同的優(yōu)先級。優(yōu)先級最低的進程（用戶進程）使用時間片調(diào)度法，而系統(tǒng)任務(wù)和服務(wù)器進程則允許一直運行到阻塞。請問優(yōu)先級最低的進程是否會發(fā)生饑餓，為什么？
33 MINIX適用于實時應(yīng)用嗎？例如數(shù)據(jù)日志記錄。若不適用，可對其作什么改動？
34 設(shè)你有一個提供信號量的操作系統(tǒng)，請實現(xiàn)一條消息傳遞系統(tǒng)，寫出發(fā)送和接收消息的過程。
35 一個主修人類學(xué)、輔修計算機科學(xué)的學(xué)生參加了一個課題，調(diào)查非洲狒狒是否能被教會理解死鎖。他找到一處很深的峽谷，在上邊固定了一根橫跨峽谷的繩索，這樣狒狒就可以攀住繩索越過峽谷。同一時刻可以有幾只狒狒通過，只要它們朝著相同的方向。但如果向東和向西的狒狒同時攀在繩索上則將發(fā)生死鎖（狒狒將被卡在中間），因為它們無法在吊在峽谷上時從另一只的背上翻過去。如果一只狒狒想越過峽谷，它必須看當(dāng)前是否有別的狒狒正在逆向通過。使用信號量寫一個避免死鎖的程序來解決該問題。
36 繼續(xù)前一問題，但現(xiàn)在要避免饑餓。當(dāng)一只想向東去的狒狒到了繩索跟前，但發(fā)現(xiàn)有別的狒狒正在向西越過峽谷時，它將一直等到繩索可用為止。但在至少有一只狒狒向東越過峽谷之前，不允許再有狒狒開始從東向西越過峽谷。
37 使用管程，而不是信號量來解決哲學(xué)家用餐問題。
38 在MINIX核心中增加一些代碼來跟蹤從進程（任務(wù)）i發(fā)送到進程（任務(wù)）j的消息個數(shù)，按下F4鍵時打印出該矩陣。
39 修改MINIX的調(diào)度程序以跟蹤每個用戶進程最近使用的CPU時間。當(dāng)沒有任務(wù)或服務(wù)器進程運行時，要求選擇使用CPU最少的用戶進程運行。
40 重新設(shè)計MINIX，使得每個進程的進程表中有一個優(yōu)先級域可用來對單個進程設(shè)置更高或更低的優(yōu)先級。
41 修改mpx386.s中的宏hwint_master 和hwint_slave，使得當(dāng)前由save函數(shù)執(zhí)行的操作改為由在線代碼執(zhí)行。這樣作使代碼增大了多少？你能測出性能提高了多少嗎？
