操作系統(tǒng)精髓與設(shè)計(jì)原理第五版中文答案全

1、 2.1 情況（a）和情況（b）具有相同的答案。 假設(shè)處理器的操作不能重疊，但i/o操作可以。 1job：時(shí)間周期=nt 處理器利用率=50%； 2jobs：時(shí)間周期=nt 處理器利用率=100%； 4jobs：時(shí)間周期=（2n-1)nt 處理器利用率=100% 2.2 i/o限制程序只用相對(duì)較少的處理時(shí)間，因此，受到短期調(diào)度算法的偏愛。然而，如果一個(gè)處理器限制程序在一段很長的時(shí)間內(nèi)被處理器時(shí)間拒絕，那同樣的這個(gè)短期調(diào)度算法則會(huì)允許處理機(jī)去處理過去一段時(shí)間一直沒有使用處理機(jī)的程序，所以，并不是永遠(yuǎn)不受理處理器限制程序所需的處理器時(shí)間。 2.3 關(guān)于分時(shí)系統(tǒng)，我們所關(guān)注的是周轉(zhuǎn)時(shí)間。 首選的是時(shí)

2、間片，因?yàn)樗谝粋€(gè)很短的時(shí)間給 所有的程序一個(gè)訪問權(quán)限去使用處理器。在批 處理系統(tǒng)，我們所關(guān)注的是吞吐量和更少量的上 下文轉(zhuǎn)換，對(duì)于進(jìn)程來說獲得了更多的處理時(shí) 間。因此，最小化上下文轉(zhuǎn)換的處理是有優(yōu)勢 的。 2.4 應(yīng)用程序運(yùn)用系統(tǒng)調(diào)用去調(diào)用操作系統(tǒng)所 提供的功能。關(guān)鍵的是，系統(tǒng)調(diào)用導(dǎo)致轉(zhuǎn)換到 進(jìn)入內(nèi)核模式的系統(tǒng)程序。 操作系統(tǒng)第三章習(xí)題解答 3.1 系統(tǒng)和用戶進(jìn)程的創(chuàng)建和刪除：在系統(tǒng)中進(jìn)程對(duì)于信息共享，加速計(jì)算，模塊性 和便利性都能并發(fā)執(zhí)行。并發(fā)的執(zhí)行需要進(jìn)程的創(chuàng)建和刪除機(jī)制。進(jìn)程所需要的資源在進(jìn)程被創(chuàng)建時(shí)獲得或者在其運(yùn)行的時(shí)候分配。當(dāng)進(jìn)程結(jié)束時(shí)，操作系統(tǒng)需要收回任何可重用資源。 進(jìn)程的掛起

3、和恢復(fù)：在進(jìn)程調(diào)度中，當(dāng)進(jìn)程在等待某些資源時(shí)，操作系統(tǒng)需要把進(jìn)程狀態(tài)改變成等待或者就緒狀態(tài)。當(dāng)進(jìn)程所要求的資源可用時(shí)，操作系統(tǒng)需要把它的狀態(tài)變?yōu)檫\(yùn)行狀態(tài)恢復(fù)它的執(zhí)行。 進(jìn)程同步機(jī)制：協(xié)調(diào)進(jìn)程分享數(shù)據(jù)。 并發(fā)訪問使用共享數(shù)據(jù)可能導(dǎo)致數(shù)據(jù)不一致性，操作系統(tǒng)不得不為其提供一種進(jìn)程同步機(jī)制用來確保協(xié)作進(jìn)程有序的實(shí)行，從而保證數(shù)據(jù)的一致性。 進(jìn)程通信機(jī)制 ：在操作系統(tǒng)下執(zhí)行的進(jìn)程要么是獨(dú)立的進(jìn)程要么是協(xié)作的進(jìn)程。 協(xié)作進(jìn)程必須使用某些方法來實(shí)現(xiàn)進(jìn)程間的通信。 死鎖處理機(jī)制：在一個(gè)多道程序設(shè)計(jì)環(huán)境里，一些進(jìn)程可能因?yàn)橛邢迶?shù)量的資源而產(chǎn)生競爭。 如果一個(gè)死鎖發(fā)生，全部等待的進(jìn)程都不會(huì)從等待狀態(tài)改變成運(yùn)行狀態(tài)

4、，那么資源被浪費(fèi)，工作不會(huì)被完成。 3.4 對(duì)處于就緒/掛起狀態(tài)的所有進(jìn)程通過一 個(gè)固定的優(yōu)先級(jí)層次來劃分，如分成一到兩 個(gè)優(yōu)先級(jí)，只有當(dāng)就緒/掛起狀態(tài)的進(jìn)程優(yōu)先 級(jí)高于所有就緒狀態(tài)進(jìn)程的優(yōu)先級(jí)時(shí)，才把 處理機(jī)分配給它。3.6 a）采用4種模式的優(yōu)點(diǎn)在于：系統(tǒng)能夠提高對(duì)存儲(chǔ)器的訪問使用的靈活性，同時(shí)對(duì)內(nèi)存儲(chǔ)器的運(yùn)行起到很好的保護(hù)作用。缺點(diǎn)：復(fù)雜度和處理開銷。例如，處理器運(yùn)行在不同的訪問模式需要分離可訪問的堆棧。b）原則上，模式越多，靈活性適應(yīng)性越大，但系統(tǒng)越復(fù)雜，舉出一 種有4種以上模式的情況較難。 3.7 a） 當(dāng)j<i時(shí)，一個(gè)在di中運(yùn)行的進(jìn)程被阻止訪問dj中的對(duì)象。因此，如果dj中

5、包含的信息比di優(yōu)先權(quán)更高或者比di更安全，這個(gè)限制是適當(dāng)?shù)?。然而，這個(gè)安全政策可以用下面的方法更簡單的獲得。一個(gè)在dj中運(yùn)行的進(jìn)程可以從dj中讀取數(shù)據(jù)，并且可以把數(shù)據(jù)復(fù)制到di中，隨后，在di中運(yùn)行的進(jìn)程便可讀取這些信息。 b）一個(gè)近似的解決這個(gè)問題的方法就是大家都知道的可信系統(tǒng)。在以后的章節(jié)會(huì)詳細(xì)解釋。 3.8 a）一個(gè)應(yīng)用程序可能正處理從另一個(gè)進(jìn)程收到的數(shù)據(jù)并且把結(jié)果儲(chǔ)存在磁盤上。如果有等待取自其它進(jìn)程的數(shù)據(jù)，應(yīng)用程序可能進(jìn)入下一個(gè)進(jìn)程取出數(shù)據(jù)并且處理它。 如果一個(gè)先前的磁盤寫操作已經(jīng)完成并且有處理的數(shù)據(jù)寫出，應(yīng)用程序會(huì)將其寫入下一個(gè)磁盤。需要考慮的一點(diǎn)就是，進(jìn)程等待輸入進(jìn)程的額外數(shù)據(jù)和

6、磁盤的可用性。 b）有幾種處理的方式。 或者一種特定類型的隊(duì)列來處理，或者進(jìn)程可能被放進(jìn)兩個(gè)單獨(dú)的隊(duì)列。 無論哪種情況，操作系統(tǒng)必須處理細(xì)節(jié)，提醒進(jìn)程注意雙方事件一個(gè)接一個(gè)的發(fā)生。 3.9 這技術(shù)基于一個(gè)假設(shè)中斷進(jìn)程a響應(yīng)中斷后將會(huì)繼續(xù)進(jìn)行。 但是， 通常， 一個(gè)中斷將引起基本監(jiān)督程序搶占進(jìn)程a有利于另一個(gè)進(jìn)程b。有必要在描敘進(jìn)程a相關(guān)進(jìn)程中斷的位置復(fù)制進(jìn)程a的執(zhí)行狀態(tài)，機(jī)器最好第一時(shí)間把它們儲(chǔ)存在那里，以方便后續(xù)操作的進(jìn)行。 3.10 因?yàn)榇嬖谶M(jìn)程不能被搶占的情況 (例如正在內(nèi)核模式里執(zhí)行的進(jìn)程)，因此操作系統(tǒng)不能快速回復(fù)實(shí)時(shí)需求。 操作系統(tǒng)第四章習(xí)題解答 4.1 是的。因?yàn)楦嗟臓顟B(tài)信息必

7、須保留下來用于一個(gè)程序到另一個(gè)程序的轉(zhuǎn)換。 4.2 因?yàn)?，關(guān)于用戶級(jí)線程，一個(gè)進(jìn)程的線程結(jié)構(gòu)對(duì)于操作系統(tǒng)來講是不可視的，它僅僅是基于進(jìn)程調(diào)度的一個(gè)基本單位。 進(jìn)程和線程的區(qū)別在于： 簡而言之,一個(gè)程序至少有一個(gè)進(jìn)程,一個(gè)進(jìn)程至少有一個(gè)線程. 線程的劃分尺度小于進(jìn)程，使得多線程程序的并發(fā)性高。 另外，進(jìn)程在執(zhí)行過程中擁有獨(dú)立的內(nèi)存單元，而多個(gè)線程共享內(nèi)存，從而極大地提高了程序的運(yùn)行效率。 線程在執(zhí)行過程中與進(jìn)程還是有區(qū)別的。 每個(gè)獨(dú)立的線程有一個(gè)程序運(yùn)行的入口、順序執(zhí)行序列和程序的出口。但是線程不能夠獨(dú)立執(zhí)行，必須依存在應(yīng)用程序中，由應(yīng)用程序提供多個(gè)線程執(zhí)行控制。 從邏輯角度來看，多線程的意義在

8、于一個(gè)應(yīng)用程序中，有多個(gè)執(zhí)行部分可以同時(shí)執(zhí)行。但操作系統(tǒng)并沒有將多個(gè)線程看做多個(gè)獨(dú)立的應(yīng)用，來實(shí)現(xiàn)進(jìn)程的調(diào)度和管理以及資源分配。這就是進(jìn)程和線程的重要區(qū)別。 （續(xù)） 進(jìn)程是具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合上的一次運(yùn)行活動(dòng),進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位. 線程是進(jìn)程的一個(gè)實(shí)體,是cpu調(diào)度和分派的基本單位,它是比進(jìn)程更小的能獨(dú)立運(yùn)行的基本單位.線程自己基本上不擁有系統(tǒng)資源,只擁有一點(diǎn)在運(yùn)行中必不可少的資源(如程序計(jì)數(shù)器,一組寄存器和棧),但是它可與同屬一個(gè)進(jìn)程的其他的線程共享進(jìn)程所擁有的全部資源. 一個(gè)線程可以創(chuàng)建和撤銷另一個(gè)線程;同一個(gè)進(jìn)程中的多個(gè)線程之間可以并發(fā)執(zhí)行. 4

9、.4 這里的這個(gè)問題是機(jī)器花費(fèi)了它工作中大量時(shí)間去等待i/o的完成。在一個(gè)多線程程序中，一個(gè)內(nèi)核級(jí)線程使系統(tǒng)調(diào)用阻塞，而其它內(nèi)核級(jí)線程可以繼續(xù)運(yùn)行，而對(duì)于一個(gè)單獨(dú)的處理器，一個(gè)進(jìn)程只有使所有調(diào)用阻塞，才能使其它線程繼續(xù)。 4.5 不會(huì)。當(dāng)一個(gè)進(jìn)程退出，它將帶走關(guān)于它 的所有東西，內(nèi)核級(jí)線程、進(jìn)程結(jié)構(gòu)、存儲(chǔ)空 間，也包括線程。 4.6 盡可能多的關(guān)于地址空間的信息能夠和其它地址空間進(jìn)行交換，從而保存到主存儲(chǔ)器中。 4.7 a）如果采取保守策略，那么最多有20/4=5個(gè)作業(yè)同時(shí)執(zhí)行。因?yàn)榉峙浣o各自進(jìn)程的設(shè)備中有一個(gè)設(shè)備在大多數(shù)時(shí)間里都是空閑的，在同一時(shí)間，最多有5個(gè)設(shè)備空閑，最好的情況，沒有設(shè)備空

10、閑，全部都在工作狀態(tài)。 b）為了提高設(shè)備的利用率，最初每個(gè)作業(yè)分配3個(gè)磁帶設(shè)備，第4個(gè)則要按需求分配。根據(jù)這個(gè)策略，至多有20/3=6個(gè)作業(yè)能被同時(shí)激活，最小空閑設(shè)備數(shù)是0，最大空閑設(shè)備數(shù)是2。 4.8 每一個(gè)調(diào)用都可能改變一個(gè)線程的優(yōu)先級(jí)或者一個(gè)可運(yùn)行的、具有更高優(yōu)先級(jí)的線程也可以調(diào)用調(diào)度程序，而且它依次搶占低優(yōu)先級(jí)的活躍線程。因此，可運(yùn)行的、高優(yōu)先級(jí)線程不具備題目所述。 5.2 5.3 a.(1).上限是100。因?yàn)樽疃嘀挥?00次加1操作。這種情況發(fā)生在兩個(gè)進(jìn)程順序執(zhí)行時(shí)。(2).下限是2，發(fā)生的情形可以描述如下： 說明：tally+實(shí)際上分三步執(zhí)行，先執(zhí)行aßtally，再執(zhí)

11、行inc a，最后執(zhí)行tallyßa。此處a為寄存器，其值將在進(jìn)程切換時(shí)保護(hù)起來。 5.6 a.用文字描述這個(gè)算法： 分步： 對(duì)于第i個(gè)進(jìn)程： 為了得到服務(wù)首先要取得順序號(hào)：即對(duì)numberi進(jìn)行寫操作，此時(shí)應(yīng)屏蔽所有其它進(jìn)程對(duì)number數(shù)組的讀操作。當(dāng)對(duì)numberi的寫操作完成時(shí)才允許其它進(jìn)程對(duì)其的讀操作。 查看是否有其他進(jìn)程正在操作，若有則做空操作；與其它進(jìn)程的順序號(hào)比較，若小于則可得到服務(wù)，否則等待。 進(jìn)入臨界區(qū) 服務(wù)完畢將numberi置0。 總述： 當(dāng)一個(gè)進(jìn)程希望進(jìn)入其臨界區(qū)，它將得到一張票，票的號(hào)碼將是所有等待進(jìn)入臨界區(qū)或已在臨界區(qū)的進(jìn)程所得到票的號(hào)碼中最大者加1。擁

12、有最小票號(hào)的進(jìn)程將率先進(jìn)入臨界區(qū)。如果有多個(gè)進(jìn)程得到的票具有相同的號(hào)碼，則進(jìn)程號(hào)更小的進(jìn)程將更占優(yōu)勢。當(dāng)一個(gè)進(jìn)程離開其臨界區(qū)，它將重置其中票號(hào)為0。 b.解釋此算法如何避免死鎖 死鎖時(shí)的情形：每個(gè)人都拿到了順序號(hào)，但都拿不到面包。 在本算法中即使順序號(hào)相同，但數(shù)組下標(biāo)是不同的。所以進(jìn)程總可推進(jìn)不會(huì)發(fā)生死鎖。 c.解釋此算法如何加強(qiáng)互斥； (1)對(duì)臨界資源面包是按照順序號(hào)互斥的使用 (2)對(duì)number數(shù)組的操作通過寫操作前置true保證其它進(jìn)程此時(shí)不能對(duì)其讀，從而保證讀寫互斥。 5.9 錯(cuò)誤情形：假設(shè)有2個(gè)進(jìn)程都調(diào)用wait且s的初值為0。在第一個(gè)進(jìn)程執(zhí)行完signalb(mutex)且尚未執(zhí)

13、行waitb(delay)時(shí)，第二個(gè)進(jìn)程開始調(diào)用wait，也停在同一點(diǎn)（即signalb(mutex)和waitb(delay)之間）。這時(shí)，s的值為-2，而mutex是打開的。假如有另外2個(gè)進(jìn)程在這時(shí)相繼調(diào)用了signal，那么他們每個(gè)都會(huì)做signalb(delay)操作，但程序中后一個(gè)signalb將沒有意義。 解決： void wait(semaphore s) waitb(mutex); s-; if(s<0) signalb(mutex); waitb(delay); signalb(mutex);void signal(semaphore s) waitb(mutex);

14、s+; if(s<=0) signalb(delay); else signalb(mutex);5.11改正后的程序： var car_available:semaphore(:=n) passenger_wait:semaphore(:=0) passenger i: wandering for a random time; signal(passenger_wait); wait(car_available); car j: wait(passenger_wait); take passenger wandering signal(car_available) parbegin p

15、assenger1;passenger2;passengerm; car1;car2;carn; parend5.14 考慮圖5.17。如果按照以下的順序改變程序中的相應(yīng)處程序的意思會(huì)改變嗎? a. wait(e); wait(s) b. signal(s);signal(n) c. wait(n);wait(s) d. signal(s);signal(e) a.互換wait(e)和wait(s): 結(jié)果： 對(duì)于生產(chǎn)者進(jìn)程來說，若wait(s)成功，則說明可以使用緩沖池。若wait(e)不成功說明沒有空緩沖區(qū)可用，此時(shí)生產(chǎn)者進(jìn)程等待。 對(duì)于消費(fèi)者進(jìn)程來說，若wait(n)成功，則說明緩沖池不

16、空。若wait(s) 成功說明可以使用緩沖池，但此時(shí)由于生產(chǎn)者進(jìn)程已將緩沖池占有，此時(shí)消費(fèi)者進(jìn)程等待。結(jié)果發(fā)生死鎖。 b.意思不變 c.同a d.意思不變5.16 這一問題給出了相應(yīng)三種進(jìn)程的信號(hào)量的使用。圣誕老人（santa claus）在北極他的店里睡覺僅能被(1)、(2)喚醒。 (1)所有九個(gè)馴鹿都結(jié)束它們的假期從南太平洋回來 (2)僅當(dāng)制造玩具的小孩子有困難時(shí)將其喊醒為了讓圣誕老人多睡會(huì)兒覺，僅當(dāng)三個(gè)小孩子有問題時(shí)將其喚醒。當(dāng)三個(gè)小孩子有問題在解決時(shí)，其他小孩子想訪問圣誕老人時(shí)必須等其他人回來。 如果圣誕老人醒來發(fā)現(xiàn)有三個(gè)小孩子在他的店門外等候，同時(shí)最后一條馴鹿已經(jīng)從熱帶回來，圣誕老人

17、已經(jīng)決定讓這些小精靈等到圣誕節(jié)之后，因?yàn)樗难┣烈呀?jīng)準(zhǔn)備好了，這一點(diǎn)比較重要(假定馴鹿不想離開熱帶，因此他們會(huì)停留到最后一刻)。最后一只馴鹿到達(dá)時(shí)圣誕老人必須出發(fā)，以前到達(dá)的馴鹿在拉雪橇前在一個(gè)溫暖的小屋里等待。使用信號(hào)量解決這一問題。 分析： 三類進(jìn)程：santa claus, reindeer, kids santa claus: sleep in north pole waken by reindeer(9頭) kids(3個(gè)) reindeer:vacation in tropics return north pole christmas activity kids: making t

18、oys having difficulties ,need help semaphore:wakesanta=0;喚醒圣誕老人的信號(hào)量 returnreindeer=1; 返回的馴鹿的計(jì)數(shù)器互斥信號(hào)量 needhelp=1;需要幫助的elves的計(jì)數(shù)器互斥信號(hào)量 int :reindeercount=0, kidscount=0; santa claus: while (true) wait(wakesanta);/等待被喚醒 if(reindeercount=9) christmas activity; send_reindeer(); wait(returnreindeer);/獲得尋路返

19、/回互斥信號(hào)量 reindeercount=0; signal(returnreindeer);/釋放馴鹿/返回互斥信號(hào)量 if(elvescount>=3) help_kids(); wait(needhelp);/等待需要幫助信號(hào)量 kidscount=0; signal(needhelp);/釋放需要幫助信號(hào)/量 reindeer i while truevacation on tropics; return to north pole; wait(returnreindeer);/獲得馴鹿返回互斥信號(hào)量 reindeercount+; if(reindeercount=9) si

20、gnal(wakesanta)/釋放喚醒圣誕老人信號(hào)量 else wait_in_hut(); signal(returnreindeer)/釋放馴鹿返回互斥信號(hào)量 kids i:making toys; wait(needhelp);/獲得需要幫助信號(hào)量 kidscount+; if elvescount=3 signal(wakesanta);/釋放喚醒圣誕/老人信號(hào)量 else signal(needhelp);/釋放需要幫助互/斥信號(hào)量 6.1互斥：在每一時(shí)刻，只能有一輛車占用十字路口的一個(gè)象限；占有且等待：沒有車倒退；每輛車一直在等待，直到它前面的十字路口的象限可以使用；非搶占：沒有

21、車輛能夠強(qiáng)迫另一輛車給自己讓路；循環(huán)等待：每輛車一直等待另外的車輛占用的十字路口的象限。6.21.q獲得b，然后獲得a，然后釋放b和a；當(dāng)p恢復(fù)執(zhí)行的時(shí)候，它可以獲得全部資源。2.q獲得b，然后獲得a；p執(zhí)行并阻塞在對(duì)a的請(qǐng)求上；q釋放b和a，當(dāng)p恢復(fù)執(zhí)行時(shí)，它可以獲得全部資源。3.q獲得b，p獲得并釋放a，然后q獲得a并釋放b和a，當(dāng)p恢復(fù)執(zhí)行時(shí)，它可以獲得b。4.p獲得a，q獲得b，p釋放a，q獲得a并釋放b，p獲得b并且釋放b。5.p獲得并釋放a，p獲得b；q執(zhí)行并阻塞在對(duì)b的請(qǐng)求上；p釋放b，當(dāng)q恢復(fù)執(zhí)行時(shí)，它可以獲得全部資源。6.p獲得a并且釋放a，p獲得b并且釋放b，當(dāng)q恢復(fù)執(zhí)行時(shí)

22、，他可以獲得全部資源。6.3.如果q在p請(qǐng)求a之前獲得b和a，那么q能夠使用并稍后釋放這兩個(gè)資源，允許p繼續(xù)執(zhí)行。 如果p在q請(qǐng)求a之前獲得a，那么q至多執(zhí)行到請(qǐng)求a之前，然后被阻塞。盡管這樣，一旦p釋放a，q就能夠繼續(xù)執(zhí)行。一旦q釋放b，p也能繼續(xù)執(zhí)行。6.5 (1) w=2 1 0 0 (2) 進(jìn)程p3的請(qǐng)求等于w，標(biāo)記p3，w2 1 0 00 1 2 02 2 2 0 (3)進(jìn)程p2的請(qǐng)求小于w，標(biāo)記p2，w2 2 2 02 0 0 14 2 2 1 (4)進(jìn)程p1的請(qǐng)求小于w，標(biāo)記p1，w 4 2 2 1 0 0 1 04 2 3 1 (5)所有的進(jìn)程都標(biāo)記了，所以系統(tǒng)不存在死鎖6.1

23、0 a.第四個(gè)進(jìn)程到達(dá)，最大需求是60，初始要求是25 b.第四個(gè)進(jìn)程到達(dá)，最大需求是60，初始需求是356.13a.三個(gè)進(jìn)程共享四個(gè)資源單元最壞情況是，3個(gè)進(jìn)程各只得到1個(gè)資源單元。這時(shí)系統(tǒng)尚存有1個(gè)資源單元，因而將不會(huì)死鎖。b.定義：claimi=進(jìn)程i總共需要的資源數(shù)目； allocationi=進(jìn)程i已經(jīng)分配的資源數(shù)目； deficiti=進(jìn)程i仍然需要的資源數(shù)目。根據(jù)題意，我們有下式成立： 在一個(gè)死鎖的情況下，所有的資源都是被占有的，所以有下式成立： 并且，此時(shí)，每個(gè)進(jìn)程都在等待資源。從以上兩個(gè)式子我們可以得出：也就是說至少有一個(gè)進(jìn)程j，它已經(jīng)獲得了所有所需要的資源（deficitj

24、=0），將完成其工作并釋放所有的資源，剩下的進(jìn)程將依次完成工作，因此死鎖不會(huì)發(fā)生。6.14安全狀態(tài)，需要的最小資源數(shù)目是3。依次用p1-p4來表示四個(gè)進(jìn)程。從矩陣可以看出，四個(gè)進(jìn)程還需要的資源數(shù)目為（2，1，6，5），當(dāng)有一個(gè)可用資源時(shí)，p2可以執(zhí)行完成，并釋放占用資源，可用資源數(shù)目為2，允許p1執(zhí)行完成，可用資源數(shù)目為3，此時(shí)，p3需要6個(gè)資源，p4需要5個(gè)資源，既最小情況還需要2個(gè)額外資源，p4執(zhí)行完成，釋放資源后，p3再執(zhí)行完成。6.17 如果至少有一個(gè)左撇子或右撇子，則當(dāng)所有哲學(xué)家都準(zhǔn)備拿起第一根筷子時(shí)，必定會(huì)有兩個(gè)哲學(xué)家競爭一根筷子而其中一個(gè)得不到處于等待，這樣必定有一個(gè)哲學(xué)家可以獲

25、得兩根筷子，而不至于發(fā)生死鎖。 同樣也不會(huì)發(fā)生饑餓7.1重定位 支持模塊化程序設(shè)計(jì)保護(hù) 進(jìn)程隔離；保護(hù)和訪問控制共享 保護(hù)和訪問控制邏輯組織 支持模塊化程序設(shè)計(jì) 物理組織 長期存儲(chǔ)；自動(dòng)分配和管理7.2分區(qū)數(shù)目等于主存的字節(jié)數(shù)除以每個(gè)分區(qū)的字節(jié)數(shù)：每8位二進(jìn)制數(shù)表示 個(gè)分區(qū)中的一個(gè)分區(qū)。 7.3定義s和h分別為內(nèi)存中段的數(shù)量和空洞的數(shù)量。假定在動(dòng)態(tài)分區(qū)的內(nèi)存中，存儲(chǔ)段的創(chuàng)建和釋放以相同的概率發(fā)生，那么對(duì)于任一分區(qū)，它后面緊挨著的那個(gè)部分是一個(gè)分區(qū)或者是一個(gè)空洞的概率各為0.5。所以，對(duì)于有s個(gè)段的內(nèi)存中，空洞的平均數(shù)量為s/2，既空洞的數(shù)量是段數(shù)量的一半。7.5最佳適配算法在每次分割之后切割下

26、來的剩余部分總是最小的，這樣會(huì)在存儲(chǔ)器中留下很多難以利用的小空閑區(qū)。最壞適配算法當(dāng)有進(jìn)程調(diào)入的時(shí)候每次都分配最大的空閑存儲(chǔ)塊，這樣塊中剩余的空閑空間就足夠大從而可以滿足另外的請(qǐng)求。缺點(diǎn)是第一次分配的時(shí)候就把最大的空閑區(qū)分配了，當(dāng)有大的空間分配請(qǐng)求時(shí)極易分配失敗。7.6a.第一個(gè)塊分配到第二個(gè)空閑塊，起始地址為80m,第二個(gè)塊分配到第一個(gè)空閑塊，起始地址為20m，第三個(gè)塊分配到第二個(gè)空閑塊起始地址為120m。b.第一個(gè)塊分配到第四個(gè)空閑塊，起始地址為230m，第二個(gè)塊分配到第一個(gè)空閑塊，起始地址為20m，第三個(gè)塊分配到第三個(gè)空閑塊，起始地址為160m。c.從上一次放置的位置開始掃描（注意只往后看

27、），所以三個(gè)塊的起始地址分別為80m，120m和160m。d.每次都找最大的空閑塊。三個(gè)塊的起始地址為80m，230m和360m。7.7a.b.7.8a.011011110100b.0110111000007.9 其中，mod表示求余運(yùn)算。7.10a. 我們完全可以采用斐波那契（fibonacci）數(shù)列作為塊的劃分準(zhǔn)則，從而建立起與普遍采用的對(duì)分伙伴系統(tǒng)（binary buddy system）不同的伙伴系統(tǒng)。b. 與對(duì)分伙伴系統(tǒng)相比，按照斐波那契數(shù)列建立起來的伙伴系統(tǒng)能夠提供更多不同的塊容量；也就是說，整個(gè)內(nèi)存空間劃分得更細(xì)致了，塊的容量更具有多樣性。因此，在為進(jìn)程分配存儲(chǔ)空間時(shí)，可以找到最

28、佳適配的存儲(chǔ)塊，因而可以使內(nèi)部碎片的尺寸得以減小，這是這種伙伴系統(tǒng)具有的顯著優(yōu)點(diǎn)。7.12a.邏輯地址空間為： 邏輯地址空間包含的位數(shù)為26位。b.一個(gè)幀的大小和頁的大小相同都是 。c.存儲(chǔ)器地址空間/幀大小= ，所以指定幀需要22位。d.邏輯地址空間有 個(gè)頁，所以含有 個(gè)頁表項(xiàng)。e.加上一個(gè)有效/無效位，制定一個(gè)幀的位數(shù)為22，所以總共為23位。 7.14a.從段表可以看出，段表中的四個(gè)字段依次為段0，1，2，3。 物理地址=660+198=858b.物理地址=222+156=378c.由于段內(nèi)偏移（530）>段的長度（442），所以發(fā)生段錯(cuò)誤。d.物理地址=996+444=1440e

29、.物理地址=660+222=8828.1 a 步驟： 從虛地址求取頁號(hào)和頁內(nèi)偏移（利用公式：虛地址=頁號(hào)*頁長+頁內(nèi)偏移） 利用頁表由頁號(hào)求取對(duì)應(yīng)的塊號(hào) 求物理地址（利用公式：物理地址=塊號(hào)*塊長+塊內(nèi)偏移，注意到塊長=頁長，塊內(nèi)偏移=頁內(nèi)偏移） b. (i) 1052 = 1024 + 28 虛擬頁號(hào)為1，得到幀號(hào)為7。 物理地址=7*1024+28=7196 (ii) 2221 = 2 * 1024 + 173 虛擬頁號(hào)為2，頁錯(cuò)誤。 (iii) 5499 = 5 *1024 + 379虛擬頁號(hào)為5，得到幀號(hào)為0。 物理地址=0*1024+379=3798.2a.存儲(chǔ)器地址空間/頁大小=

30、，所以在虛擬存儲(chǔ)器中指定頁需要22位。 每一頁包含 個(gè)頁表項(xiàng)。每個(gè)頁表占據(jù)了8位，因此22位需要用到三級(jí)頁表。b.兩級(jí)的頁表包含 個(gè)頁表項(xiàng)，一級(jí)頁表包含 個(gè)頁表項(xiàng)(8+8+6=22)。c.我們這里有三級(jí)，三級(jí)所占位數(shù)為6，8，8，則頁的個(gè)數(shù)為： 若三級(jí)所占位數(shù)為：8，6，8，則頁的個(gè)數(shù)為： 若三級(jí)所占位數(shù)為：8，8，6，則頁的個(gè)數(shù)為：8.4 a. 3號(hào)頁幀的內(nèi)容將被置換，因?yàn)樗钤绫患虞d。 b. 1號(hào)頁幀的內(nèi)容將被置換，因?yàn)樗纳洗卧L問時(shí)間離當(dāng)前最久。 c. 0號(hào)頁幀的內(nèi)容將被置換，因?yàn)槠渲衦位和m位的值為（0, 1）。 d. 3號(hào)頁幀的內(nèi)容將被置換，因?yàn)橛蓪淼脑L問序列可知，頁面3的訪問順序

31、最靠后。8.6 a. 命中率=16/33 b. 命中率=16/33c. 對(duì)于這個(gè)特定的訪問序列，采用上述兩種替換策略得到的命中率相等。一般來說，采用lru替換策略的命中率會(huì)高于采用fifo替換策略的情況，而對(duì)于這個(gè)特定的訪問序列來說，一個(gè)頁面被載入之后，很少發(fā)生在接下來的5次連續(xù)訪問中再次被訪問的情形，因此缺頁發(fā)生的時(shí)刻與lru的情況相當(dāng)接近，從而使得對(duì)應(yīng)的命中率接近于lru。8.8存儲(chǔ)器地址從4000開始: 4000(r1) oneestablish index register for i 4001(r1) nestablish n in r2 4002compare r1, r2test

32、 i > n 4003branch greater 4009 4004(r3) b(r1)access bi using index register r1 4005(r3) (r3) + c(r1)add ci using index register r1 4006a(r1) (r3)store sum in ai using index register r1 4007(r1) (r1) + oneincrement i 4008branch 4002 6000-6999storage for a 7000-7999storage for b 8000-8999storage fo

33、r c 9000storage for one 9001storage for n8.10 假設(shè)需要i級(jí)，則可以表示的地址空間大小 = 要求表示64位地址空間，則要求10i+12>=64，所以i至少取6 8.11 a. 400ns b. 15%*420+85%*220=250 8.12 a. 缺頁下限=n b. 缺頁上限=p 8.17 a. 每段的最大尺寸=8*2k=16k b. 該任務(wù)的邏輯地址空間最大=4*16k=64k c. 邏輯地址格式是：2位表示段號(hào)，3位表示頁號(hào)，其他11位表示頁內(nèi)偏移。最后的11位轉(zhuǎn)換為十六進(jìn)制為2bc 8.18 a. 邏輯地址格式是：前5位表示頁號(hào)，后11

34、位表示頁內(nèi)偏移。 b. 頁表長度：25=32個(gè)條目；頁表寬度：20-11=9位。 c. 頁表寬度由9位變?yōu)?位。9.1 每個(gè)方塊表示一個(gè)執(zhí)行單元，方塊中的數(shù)字表示當(dāng)前執(zhí)行的進(jìn)程。fcfsaaabbbbbccdddddeeeeerr, q = 1ababcabcbdbdedededeerr, q = 4aaabbbbccbddddeeeedespnaaaccbbbbbdddddeeeeesrtaaaccbbbbbdddddeeeeehrrnaaabbbbbccdddddeeeeefeedback, q = 1abacbcabbdbdedededeefeedback, q = 2iabaacbbc

35、bbddeddeedeefcfsaaabbbbbccdddddeeeeerr, q = 1ababcabcbdbdedededeerr, q = 4aaabbbbccbddddeeeedespnaaaccbbbbbdddddeeeeesrtaaaccbbbbbdddddeeeeehrrnaaabbbbbccdddddeeeeefeedback, q = 1abacbcabbdbdedededeefeedback, q = 2iabaacbbcbbddeddeedee9.7 首先，調(diào)度器計(jì)算在時(shí)間t+r1+r2+r3時(shí)刻的響應(yīng)比，此時(shí)，三個(gè)作業(yè)都已經(jīng)完成。這個(gè)時(shí)候第三個(gè)作業(yè)具有最小的響應(yīng)比（圖中

36、可以看出），所以，調(diào)度器決定最后執(zhí)行第三個(gè)作業(yè)；繼續(xù)查看在時(shí)間t+r1+r2時(shí)，第一和第二個(gè)作業(yè)都已完成，此時(shí)，第一個(gè)任務(wù)的響應(yīng)比要小些，所以，在時(shí)間t的時(shí)候第二個(gè)作業(yè)被選擇執(zhí)行,既執(zhí)行順序?yàn)閞2,r1,r3。這個(gè)算法在每完成一個(gè)作業(yè)之后重新查看作業(yè)的響應(yīng)比，跟高響應(yīng)比優(yōu)先算法是有區(qū)別的，如果是后者那么在時(shí)間t的時(shí)候就會(huì)選擇第一個(gè)作業(yè)。9.14 在多級(jí)反饋隊(duì)列調(diào)度器的調(diào)度下，i/o-bound的進(jìn)程比cpu-bound的進(jìn)程更有利，也就是說，調(diào)度器更傾向于選擇i/o-bound的進(jìn)程進(jìn)行分派。原因在于i/o-bound的進(jìn)程會(huì)比較長時(shí)間地阻塞；在阻塞過程中，cpu-bound的進(jìn)程得到多次分派執(zhí)行，因而會(huì)很快進(jìn)入低優(yōu)先級(jí)的反饋隊(duì)列中。這樣，i/o-boun