【正文】 。na, nm: 0 … +∞。在協(xié)議的第二部分，在M上阻塞的NM個(gè)進(jìn)程將使用類似于第一部分的串聯(lián)技術(shù)，依次進(jìn)入他們的臨界區(qū)，定義一個(gè)算法實(shí)現(xiàn)上面的描述。除了這三個(gè)信號量外，算法使用兩個(gè)非負(fù)整數(shù)變量，作為在算法特定區(qū)域的進(jìn)程的計(jì)數(shù)器。1979年， 了一個(gè)使用三個(gè)弱信號量的算法，反駁了這個(gè)推測。因此semWait中的最后一個(gè)semSignalB(mutex)變成無條件的，semSignal中的semSignalb(mutex)變成了有條件的。因?yàn)閟=2 mutex沒有鎖定，假如有另外兩個(gè)進(jìn)程同時(shí)成功的調(diào)用semSignal（s），他們接著就會(huì)調(diào)用semsignalb（delay），但是第二個(gè)semsignalb沒有被定義。提示：假設(shè)兩個(gè)進(jìn)程，每個(gè)都在s初始化為0時(shí)調(diào)用semwait（s）,當(dāng)?shù)谝粋€(gè)剛剛執(zhí)行了semsignalb（mutex）但還沒有執(zhí)行semwaitb（delay），第二個(gè)調(diào)用semwait（s）并到達(dá)同一點(diǎn)。 }最初。 if(s=0) semSignalB(delay)。 { semWaitB(mutex)。 semWaitB(delay)。 s。我們使用semWaitB操作和semSignalB操作以及兩個(gè)二元信號量delay和mutex。當(dāng)在程序中分別使用這兩種定義時(shí)，其效果有什么不同？也就是說，是否可以在不改變程序意義的前提下，用一個(gè)定義代替另一個(gè)？答：這兩個(gè)定義是等價(jià)的，當(dāng)信號量的值為負(fù)值時(shí)，它的值代表了有多少個(gè)進(jìn)程在等待；在此題中的定義中，雖然你沒有關(guān)于這方面的信息，但是這兩個(gè)版本的函數(shù)是一樣的。 } Else ++。 } } Void semSignal(s) { If (there is at liast one process blocked on semaphore) { Remove a process P from 。 } Else { Place this process in 。if j = i then lock := falseelse waiting := false。 critical section j := i + 1 mod n。while waiting[i] and key do key := testset(lock)。repeatwaiting[i] := true。答：以下的程序由[SILB98]提供：var j: 0..n1。,我們有Tk2 Tk3 Tw1 Tw2,因此有Tk2,Pi已經(jīng)讀了當(dāng)前number[k],因?yàn)門w2是當(dāng)j=k第二次while循環(huán)執(zhí)行發(fā)生的時(shí)刻,我們有(number[i], i ) ( number[k], k),因?yàn)樗鼤?huì)發(fā)現(xiàn)number[i]不等于0,并且( number[i], i ) ( number[k], k ).，對進(jìn)程在允許訪問臨界區(qū)之前必須等待多久沒有控制。Tk2:Pk完成number[k]的計(jì)算。C． 說明它實(shí)施了互斥。符號（a，b）（c，d）被定義成 （a，c）或（a=c且bd）A． 用文字描述這個(gè)算法。 /*remainder*/。amp。jn。 Number[i]=1+getmax(number[],n)； Choosing[i]=false。 Int number[n]。請舉出證明該方法不正確的一個(gè)反例。 Parbegin(P(0),P(1))。 Blocked[1]=false。 Turn =id。 void P(int id) { While (true) { While(turn!=id)。答：就一般情況來說是對的,有一種特殊情況,當(dāng)進(jìn)程執(zhí)行到程序的某一點(diǎn)處,在此處要等待直到條件滿足,而正好條件已滿足,此時(shí)忙等待會(huì)立即有結(jié)果,然而阻塞等待會(huì)消耗操作系統(tǒng)資源在換出與換入進(jìn)程上. boolean blocked[2]。write(tally)。 }}void main(){ tally =0。count =n。void total(){ int count。 const int n=50。DABEC。DEABC。ADBEC。ABDEC。 } }答：ABCDE。 E。 { D。．考慮一個(gè)并發(fā)程序，它有兩個(gè)進(jìn)程p和q，定義如下。協(xié)同程序squash不需要知道任何關(guān)于輸入的八十個(gè)字符的結(jié)構(gòu)，它簡單的查找成對出現(xiàn)的星號，然后將更改夠的字符串經(jīng)由只有一個(gè)字符大小的緩沖sp，傳遞給協(xié)同程序print。參考：[LEVI96]第5章 并發(fā)性：互斥和同步答：，將字符賦給一個(gè)只有一個(gè)字大小的緩沖區(qū)rs然后在賦給squash協(xié)同程。請問，如果有一個(gè)可運(yùn)行的、具有更高優(yōu)先級的線程，讓位函數(shù)是否還會(huì)導(dǎo)致讓位于具有相同優(yōu)先級或更高優(yōu)先級的線程？答：任何一個(gè)可能改變線程優(yōu)先級或者使更高優(yōu)先級的線程可運(yùn)行的調(diào)用都會(huì)引起調(diào)度，它會(huì)依次搶占低優(yōu)先級的活躍線程。最少的空閑設(shè)備數(shù)量為0，最多有2個(gè)。第四個(gè)只有的需要的時(shí)候才分配。在最好的情況下沒有磁帶設(shè)備空閑。答：a. 采用一個(gè)保守的策略，一次最多同時(shí)執(zhí)行20/4=5個(gè)作業(yè)。請問一次最多可以同時(shí)執(zhí)行幾個(gè)作業(yè)？采用這種策略，最多有幾個(gè)磁帶設(shè)備可能是空閑的？最少有幾個(gè)？b. 給出另外一種策略，要求其可以提高磁帶設(shè)備的利用率，并且同時(shí)可以避免系統(tǒng)死鎖。a. 假設(shè)操作系統(tǒng)中的調(diào)度器只有當(dāng)4個(gè)磁帶設(shè)備都可用時(shí)才開始一個(gè)作業(yè)。假設(shè)每個(gè)作業(yè)開始運(yùn)行時(shí)只需要3個(gè)磁帶設(shè)備，并且在很長時(shí)間內(nèi)都只需要這3個(gè)設(shè)備，而只是在最后很短的一段時(shí)間內(nèi)需要第4個(gè)設(shè)備以完成操作。. 一個(gè)多處理系統(tǒng)有8個(gè)處理器和20個(gè)附加磁帶設(shè)備。ASCB是在系統(tǒng)存儲(chǔ)器中保存的全局結(jié)構(gòu)，而TCB是保存在各自的地址空間中的局部結(jié)構(gòu)。ASCB中的信息包括分派優(yōu)先級、分配給該地址空間的實(shí)存和虛存、該地址空間中就緒的任務(wù)數(shù)以及是否每個(gè)都被換出。管理任務(wù)結(jié)構(gòu)有兩個(gè)主要的數(shù)據(jù)結(jié)構(gòu)。參考：[LEWI96]. OS/390主機(jī)操作系統(tǒng)圍繞著地址空間和任務(wù)的概念構(gòu)造。參考：[LEWI96]. 如果一個(gè)進(jìn)程退出時(shí)，該進(jìn)程的某些線程仍在運(yùn)行，請問他們會(huì)繼續(xù)運(yùn)行嗎？答：不會(huì)。在一個(gè)多線程程序中，可能一個(gè)內(nèi)核級線程會(huì)產(chǎn)生引發(fā)阻塞的系統(tǒng)調(diào)用，而其他內(nèi)核級線程可以繼續(xù)執(zhí)行。. 考慮這樣一個(gè)環(huán)境，用戶級線程和內(nèi)核級線程呈一對一的映射關(guān)系，并且允許進(jìn)程中的一個(gè)或多個(gè)線程產(chǎn)生會(huì)引發(fā)阻塞的系統(tǒng)調(diào)用，而其他線程可以繼續(xù)運(yùn)行。它為明確圖形輸出和鍵盤/鼠標(biāo)輸入應(yīng)該被關(guān)聯(lián)到什么位置提供了一個(gè)統(tǒng)一的機(jī)制，減輕了操作系統(tǒng)的工作負(fù)擔(dān)。為了進(jìn)一步地進(jìn)行構(gòu)造，進(jìn)程可以被劃分成線程。刪去會(huì)話，把用戶接口（鍵盤、顯示器、鼠標(biāo)）和進(jìn)程關(guān)聯(lián)起來。當(dāng)一個(gè)會(huì)話在后臺(tái)時(shí)，如果該會(huì)話的任何一個(gè)進(jìn)程的任何一個(gè)線程正在執(zhí)行并產(chǎn)生屏幕輸出，則這個(gè)輸出被送到邏輯視頻緩沖區(qū)；當(dāng)這個(gè)會(huì)話返回前臺(tái)時(shí)，屏幕被更新，為新的前臺(tái)會(huì)話反映出邏輯視頻緩沖區(qū)中的當(dāng)前內(nèi)容。在任何時(shí)刻，只有一個(gè)會(huì)話在前臺(tái)模式，其他的會(huì)話都在后臺(tái)模式，鍵盤和鼠標(biāo)的所有輸入都發(fā)送給前臺(tái)會(huì)話的一個(gè)進(jìn)程。會(huì)話代表了一個(gè)交互式的用戶應(yīng)用程序，如字處理程序或電子表格，這個(gè)概念使得PC用戶可以打開一個(gè)以上的應(yīng)用程序，在屏幕上顯示一個(gè)或更多個(gè)窗口。. 在OS/2中，其他操作系統(tǒng)中通用的進(jìn)程概念被分成了三個(gè)獨(dú)立類型的實(shí)體：會(huì)話、進(jìn)程和線程。. 在比較用戶級線程和內(nèi)核級線程時(shí)曾指出用戶級線程的一個(gè)缺點(diǎn)，即當(dāng)一個(gè)用戶級線程執(zhí)行系統(tǒng)調(diào)用時(shí)，不僅這個(gè)線程被阻塞，而且進(jìn)程中的所有線程都被阻塞。第4章 線程、對稱多處理和微內(nèi)核. 一個(gè)進(jìn)程中的多個(gè)線程有以下兩個(gè)優(yōu)點(diǎn)：（1）在一個(gè)已有進(jìn)程中創(chuàng)建一個(gè)新線程比創(chuàng)建一個(gè)新進(jìn)程所需的工作量少；（2）在同一個(gè)進(jìn)程中的線程間的通信比較簡單。請闡述原因。參考：[BRIN73]。這是就必須將進(jìn)程A的執(zhí)行狀態(tài)從與中斷相關(guān)的位置復(fù)制到與A相關(guān)的進(jìn)程描述中。答：這種技術(shù)是基于被中斷的進(jìn)程A在中斷響應(yīng)之后繼續(xù)執(zhí)行的假設(shè)的。. 在很多早期計(jì)算機(jī)中，中斷導(dǎo)致寄存器值被保存在與給定的中斷信息相關(guān)聯(lián)的固定單元?？梢允褂靡环N特殊的隊(duì)列，或者將進(jìn)程放入兩個(gè)獨(dú)立的隊(duì)列中。這樣就可能存在某一時(shí)刻，進(jìn)程即在等待從輸入進(jìn)程獲得數(shù)據(jù)，又在等待磁盤可用。如果當(dāng)前在另一個(gè)進(jìn)程中正有數(shù)據(jù)在等待被取走，進(jìn)程就可以繼續(xù)獲得數(shù)據(jù)并處理它。a. 是否能夠允許進(jìn)程同時(shí)等待一個(gè)或多個(gè)事件？請舉例說明。b. 有一種解決這一問題的方法叫做可信系統(tǒng)，我們將在16章中進(jìn)行討論。一個(gè)運(yùn)行在Dj中的進(jìn)程可以讀取Dj中的數(shù)據(jù)，然后把數(shù)據(jù)復(fù)制到Di中。因此，如果Dj中包含的信息比Di中的更具有特權(quán)或者要求的安全性更高，那么這種限制就是合理的。b. 請給出環(huán)狀結(jié)構(gòu)操作系統(tǒng)解決這個(gè)問題的一種方法。這意味著在Di中可訪問的每個(gè)段在Dj中都可以訪問。. 在前面習(xí)題中討論的VMS方案常常稱為環(huán)狀保護(hù)結(jié)構(gòu)。例如，程序在每一種執(zhí)行模式下都要有一個(gè)獨(dú)立的堆棧。a. 很多操作系統(tǒng)有兩種模式，內(nèi)核和用戶，那么提供四種模式有什么優(yōu)點(diǎn)和缺點(diǎn)？b. 你可以舉出一種有四種以上模式的情況嗎？答：a. 四種模式的優(yōu)點(diǎn)是對主存的訪問控制更加靈活，能夠?yàn)橹鞔嫣峁└玫谋Ｗo(hù)。在較少特權(quán)模式執(zhí)行的進(jìn)程通常需要調(diào)用在較多特權(quán)模式下執(zhí)行的過程，例如，一個(gè)用戶程序需要一個(gè)操作系統(tǒng)服務(wù)。l 管理模式：執(zhí)行其他操作系統(tǒng)服務(wù)，如響應(yīng)用戶命令。四種模式如下：l 內(nèi)核模式：執(zhí)行VMS操作系統(tǒng)的內(nèi)核，包括內(nèi)存管理、中斷處理和I/O操作。訪問模式確定：l 指令執(zhí)行特權(quán)：處理器將執(zhí)行什么指令。c. 可以由下面的進(jìn)程狀態(tài)轉(zhuǎn)換表得到狀態(tài)轉(zhuǎn)換圖。b. 在這些狀態(tài)下，允許進(jìn)程被換出只會(huì)使效率更低。當(dāng)影響某一等待進(jìn)程的事件發(fā)生時(shí)，把等待進(jìn)程分成不同的隊(duì)列就減少了定位這一等待進(jìn)程所需的工作量。c. 請畫出狀態(tài)轉(zhuǎn)換圖，并指出引發(fā)狀態(tài)裝換的原因。a. 請給出這么多種等待狀態(tài)的理由。答：對于一個(gè)就緒/掛起態(tài)的進(jìn)程，降低一定數(shù)量（如一或兩個(gè)）優(yōu)先級，從而保證只有當(dāng)一個(gè)就緒/掛起態(tài)的進(jìn)程比就緒態(tài)的進(jìn)程的最高優(yōu)先級還高出幾個(gè)優(yōu)先級時(shí)，它才會(huì)被選做下一個(gè)執(zhí)行。有兩種極端的策略：（1）總是分派一個(gè)處于就緒態(tài)的進(jìn)程，以減少交換；（2）總是把機(jī)會(huì)給具有最高優(yōu)先級的進(jìn)程，即使會(huì)導(dǎo)致在不需要交換時(shí)進(jìn)行交換。. （b）中的狀態(tài)轉(zhuǎn)換圖。答：。后一種區(qū)別是必需的，而且應(yīng)該在進(jìn)程狀態(tài)中以某種形式表現(xiàn)出來。這種對等待某一設(shè)備的兩種不同原因的區(qū)別，在操作系統(tǒng)組織其工作時(shí)是非常有用的。當(dāng)進(jìn)程重新變?yōu)閳?zhí)行態(tài)時(shí)要對新獲得的磁帶設(shè)備進(jìn)行寫操作。當(dāng)它做出請求時(shí)，磁帶設(shè)備可能并不可用，這種情況下，該進(jìn)程就處于阻塞態(tài)。答：[PINK89]中引用了以下例子來闡述其中阻塞和掛起的定義：假設(shè)一個(gè)進(jìn)程已經(jīng)執(zhí)行了一段時(shí)間，它需要一個(gè)額外的磁帶設(shè)備來寫出一個(gè)臨時(shí)文件。在許多操作系統(tǒng)中，這兩種狀態(tài)常常放在一起作為阻塞態(tài)，掛起態(tài)使用本章中給出的定義。. 在[PINK89] 中為進(jìn)程定義了以下狀態(tài)：執(zhí)行（運(yùn)行）態(tài)、活躍（就緒）態(tài)、阻塞態(tài)和掛起態(tài)。在多道程序環(huán)境中，多個(gè)進(jìn)程可能會(huì)競爭有限的資源。合作進(jìn)程之間必須具有一定的方式進(jìn)行通信。提供進(jìn)程的通信機(jī)制。對共享數(shù)據(jù)的并行訪問可能會(huì)導(dǎo)致數(shù)據(jù)沖突。提供進(jìn)程的同步機(jī)制。在進(jìn)程調(diào)度中，當(dāng)進(jìn)程在等待某些資源時(shí)，操作系統(tǒng)需要將它的狀態(tài)改變?yōu)榈却蚓途w狀態(tài)。當(dāng)進(jìn)程終止時(shí)，操作系統(tǒng)需要收回任何可以重新利用的資源。而并發(fā)執(zhí)行需要進(jìn)程的創(chuàng)建和刪除機(jī)制。答：用戶進(jìn)程和系統(tǒng)進(jìn)程創(chuàng)建及刪除。典型的平均時(shí)間應(yīng)該是兩分鐘以上，這個(gè)平均時(shí)間看起來很長，其實(shí)并不長。一段時(shí)間后，SRM求這些數(shù)據(jù)的平均值，以確定系統(tǒng)中一個(gè)頁面未曾被觸及的平均秒數(shù)。SRM每秒大約接受20次控制，并在互相之間以及每個(gè)頁面之間進(jìn)行檢查。實(shí)存被劃分為成千上萬個(gè)大小相等的塊，稱為幀。SRM依次提供報(bào)告，允許受過訓(xùn)練的操作員改進(jìn)配置和參數(shù)設(shè)置，以改善用戶服務(wù)。SRM是的OS/390在操作系統(tǒng)中具有特殊性，沒有任何其他的主機(jī)操作系統(tǒng)，當(dāng)然沒有任何其他類型的操作系統(tǒng)可以比得上SRM所實(shí)現(xiàn)的功能。通常情況下，系統(tǒng)調(diào)用最終轉(zhuǎn)換成在內(nèi)核模式下的系統(tǒng)程序。因此，最小的上下文轉(zhuǎn)換最高效。分時(shí)