生習(xí)題：

1.1、列出并簡要地定義計(jì)算機(jī)的四個(gè)主要組成部分。

答：主存儲器，存儲數(shù)據(jù)和程序；算術(shù)邏輯單元，能處理二進(jìn)制數(shù)據(jù)；控制單元，

解讀存儲器中的指令并且使他們得到執(zhí)行；輸入/輸出設(shè)備，由控制單元管理。

1.2、定義處理器寄存器的兩種主要類別。

答：用戶可見寄存器：優(yōu)先使用這些寄存器，可以使機(jī)器語言或者匯編語言的程序

員減少對主存儲器的訪問次數(shù)。對高級語言而言，由優(yōu)化編譯器負(fù)責(zé)決定把哪

些變最應(yīng)該分配給主存儲器。一些高級語言，如C語言，允許程序言建議編

譯器把哪些變量保存在寄存器中。

控制和狀態(tài)寄存器：用以控制處理器的操作，且主要被具有特權(quán)的操作系統(tǒng)例

程使用，以控制程序的執(zhí)行。

1.3、一般而言，一條機(jī)器指令能指定的四種不同操作是什么？

答：這些動(dòng)作分為四類：處理器一寄存器：數(shù)據(jù)可以從處理器傳送到存儲器，或者

從存儲器傳送到處理器。處理器一1/0：通過處理器和I/O模塊間的數(shù)據(jù)傳送，

數(shù)據(jù)可以輸出到外部設(shè)備，或者從外部設(shè)備輸入數(shù)據(jù)。數(shù)據(jù)處理，處理器可以

執(zhí)行很多關(guān)于數(shù)據(jù)的算術(shù)操作或邏輯操作。控制：某些指令可以改變執(zhí)行順序。

1.4s什么是中斷？

答：中斷：其他模塊（I/O,存儲微）中斷處理器正常處理過程的機(jī)制。

1.5、多中斷的處理方式是什么？

答：處理多中斷芍兩種方法。第一種方法是當(dāng)正在處理一個(gè)中斷時(shí)，禁止再發(fā)生中

斷。第二種方法是定義中斷優(yōu)先級，允許高優(yōu)先級的中斷打斷低優(yōu)先級的中斷

處理器的運(yùn)行。

1.6、內(nèi)存層次的各個(gè)元素間的特征是什么？

答：存儲器的三個(gè)重要特性是：價(jià)格，容量和訪問時(shí)間。

1.7、什么是高速緩沖存儲器？

答：高速緩沖存儲器是比主存小而快的存儲器，用以協(xié)調(diào)主存跟處理器，作為最近

儲存地址的緩沖區(qū)。

1.8、列出并簡要地定義I/O操作的三種技術(shù)。

答：可編程I/O：當(dāng)處理器正在執(zhí)行程序并遇到與I/O相關(guān)的指令時(shí)，它給相應(yīng)的

I/O模塊發(fā)布命令（用以執(zhí)行這個(gè)指令）；在進(jìn)一步的動(dòng)作之前，處理器處于

繁忙的等待中，直到該操作已經(jīng)完成。中斷驅(qū)動(dòng)I/O：當(dāng)處理器正在執(zhí)行程序

并遇到與I/O相關(guān)的指令時(shí)，它給相應(yīng)的I/O模塊發(fā)布命令，并繼續(xù)執(zhí)行后續(xù)

指令，直到后者完成，它將被I/O模塊中斷。如果它對于進(jìn)程等待I/O的完成

來說是不必要的，可能是由于后續(xù)指令處于相同的進(jìn)程中。否則，此進(jìn)程在中

斷之前將被桂起，其他工作將被執(zhí)行。直接存儲訪問：DMA模塊控制主存與

I/O模塊間的數(shù)據(jù)交換。處理器向DMA模塊發(fā)送一個(gè)傳送數(shù)據(jù)塊的請求.（處

理器）只有當(dāng)整個(gè)數(shù)據(jù)塊傳送完畢后才會(huì)被中斷。

1.9、空間局部性和臨時(shí)局部性間的區(qū)別是什么？

答：空間局部性是指最近被訪問的元素的周圍的元素在不久的將來可能會(huì)被訪問。

臨時(shí)局部性（即時(shí)間局部性）是指最近被訪問的元素在不久的將來可能會(huì)被再

次訪問。

1.10.開發(fā)空間局部性和時(shí)間局部性的策略是什么？

答：空間局部性的開發(fā)是利用更大的緩沖塊并且在存儲器控制邏輯中加入預(yù)處理機(jī)

制。時(shí)間局部性的開發(fā)是利用在高速緩沖存儲器中保留最近使用的指令及數(shù)據(jù)，

并且定義緩沖存儲的優(yōu)先級。

2.1操作系統(tǒng)設(shè)計(jì)的三個(gè)目標(biāo)是什么？

方便：操作系統(tǒng)使計(jì)算機(jī)更易于使用。

有效：操作系統(tǒng)允許以更有效的方式使用計(jì)算機(jī)系統(tǒng)資源。

擴(kuò)展的能力：在構(gòu)造操作系統(tǒng)時(shí)，應(yīng)該允許在不妨礙服務(wù)的前提下有效地開

發(fā)、測試和引進(jìn)新的系統(tǒng)功能。

2.2什么是操作系統(tǒng)的內(nèi)核？

內(nèi)核是操作系統(tǒng)最常使用的部分，它存在于主存中并在特權(quán)模式下運(yùn)行,

響應(yīng)進(jìn)程調(diào)度和設(shè)備中斷。

2.3什么是多道程序設(shè)計(jì)？

多道程序設(shè)計(jì)是一種處理操作，它在兩個(gè)或多個(gè)程序間交錯(cuò)處理每個(gè)進(jìn)

程。

2.4什么是進(jìn)程？

進(jìn)程是一個(gè)正在執(zhí)行的程序，它被操作系統(tǒng)控制和選擇。

2.5操作系統(tǒng)是怎么使用進(jìn)程上下文的？

執(zhí)行上下文又稱為進(jìn)程狀態(tài)，是操作系統(tǒng)用來管理和控制所需的內(nèi)部數(shù)

據(jù)。這種內(nèi)部信息和進(jìn)程是分開的，因?yàn)椴僮飨到y(tǒng)信息不允許被進(jìn)程直接訪

問。上下文包括操年系統(tǒng)管理進(jìn)程以及處理器正確執(zhí)行進(jìn)程所需要的所有信

息，包括各種處理器寄存器的內(nèi)容，如程序計(jì)數(shù)器和數(shù)據(jù)寄存器。它還包括

操作系統(tǒng)使用的信息，如進(jìn)程優(yōu)先級以及進(jìn)程是否在等待特定I/O事件的完

成。

2.6列出并簡要介紹操作系統(tǒng)的五種典型存儲管理職責(zé)。

進(jìn)程隔離：操作系統(tǒng)必須保護(hù)獨(dú)立的進(jìn)程，防止互相干涉數(shù)據(jù)和存儲空

間。

自動(dòng)分配和管理：程序應(yīng)該根據(jù)需要在存儲層次間動(dòng)態(tài)的分配，分配對程序

員是透明的。因此，程序員無需關(guān)心與存儲限制有關(guān)的問題，操作系統(tǒng)有效

的實(shí)現(xiàn)分配問題，可以僅在需要時(shí)才給作業(yè)分配存儲空間。

P5I

2.7解釋實(shí)地址和虛地址的區(qū)別。

虛地址指的是存在于虛擬內(nèi)存中的地址，它有時(shí)候在磁盤中有時(shí)候在主

存中。實(shí)地址指的是主存中的地址。

2.8描述輪循調(diào)度技術(shù)。

輪循調(diào)度是一種調(diào)度算法，所有的進(jìn)程存放在一個(gè)環(huán)形隊(duì)列中并按固定

循序依次激活。因?yàn)榈却恍┦录ɡ纾旱却粋€(gè)子進(jìn)程或一個(gè)I/O操作）

的發(fā)生而不能被處理的進(jìn)程將控制權(quán)交給調(diào)度器。

2.9解釋單體內(nèi)核和微內(nèi)核的區(qū)別。

單體內(nèi)核是一個(gè)提供操作系統(tǒng)應(yīng)該提供的功能的大內(nèi)核，包括調(diào)度、文

件系統(tǒng)、網(wǎng)絡(luò)、設(shè)備驅(qū)動(dòng)程序、存儲管理等。內(nèi)核的所有功能成分都能夠訪

問它的內(nèi)部數(shù)據(jù)結(jié)構(gòu)和程序。典型情況下，這個(gè)大內(nèi)核是作為一個(gè)進(jìn)程實(shí)現(xiàn)

的，所有元素都共享相同的地址空間。微內(nèi)核是一個(gè)小的有特權(quán)的操作系統(tǒng)

內(nèi)核，只提供包括進(jìn)程調(diào)度、內(nèi)存管理、和迸程間通信等基本功能，要依靠

其他進(jìn)程擔(dān)當(dāng)起和操作系統(tǒng)內(nèi)核聯(lián)系作用。

2.1（）什么是多線程？

多線程技術(shù)是指把執(zhí)行一個(gè)應(yīng)用程序的進(jìn)程劃分成可以同時(shí)運(yùn)行的多個(gè)線

程。

3.1什么是指令跟蹤？

答：指令跟蹤是指為該進(jìn)程而執(zhí)行的指令序列。（P81）

3.2通常那些事件會(huì)導(dǎo)致創(chuàng)建一個(gè)進(jìn)程？

答：新的批處理作業(yè)；交互登錄；操作系統(tǒng)因?yàn)樘峁┮豁?xiàng)服務(wù)而創(chuàng)建；由現(xiàn)有的進(jìn)程

派生。（詳情請參考表3.1）

3.3對于圖3.6中的進(jìn)程模型，請簡單定義每個(gè)狀態(tài)。

答：運(yùn)行態(tài)：該進(jìn)程正在執(zhí)行。就緒態(tài)：進(jìn)程做好了準(zhǔn)備，只要有機(jī)會(huì)就

開始執(zhí)行。阻塞態(tài)：進(jìn)程在某些事件發(fā)生前不能執(zhí)行，如I/O操作完成。

新建態(tài)：剛剛創(chuàng)建的進(jìn)程，操作系統(tǒng)還沒有把它加入到可執(zhí)行進(jìn)程組中。

退出態(tài)：操作系統(tǒng)從可執(zhí)行進(jìn)程組中釋放出的進(jìn)程，或者是因?yàn)樗陨硗?/p>

止了，或者是因?yàn)槟撤N原因被取消。

3.4搶占一個(gè)進(jìn)程是什么意思？

答：處理器為了執(zhí)行另外的進(jìn)程而終止當(dāng)前正在執(zhí)行的進(jìn)程，這就叫進(jìn)程搶占。

3.5什么是交換,其目的是什么?

答：交換是指把主存中某個(gè)進(jìn)程的一部分或者全部內(nèi)容轉(zhuǎn)移到磁盤。當(dāng)主存中沒有處

于就緒態(tài)的進(jìn)程時(shí)，操作系統(tǒng)就把一個(gè)阻塞的進(jìn)程換出到磁盤中的掛起隊(duì)列，從而使

另一個(gè)進(jìn)程可以進(jìn)入主存執(zhí)行。

3.6為什么圖3.9（b）中有兩個(gè)阻塞態(tài)?

答：有兩個(gè)獨(dú)立的概念：進(jìn)程是否在等待一個(gè)事件（阻塞與否）以及進(jìn)程是否已經(jīng)被

換出主存（掛起與否）。為適應(yīng)這種2*2的組合，需要兩個(gè)阻塞態(tài)和兩個(gè)掛起態(tài)。

3.7列出掛起態(tài)進(jìn)程的4個(gè)特點(diǎn)。

答：1.進(jìn)程不能立即執(zhí)行。2.進(jìn)程可能是或不是正在等待一個(gè)事件。如果是，阻塞條

件不依賴于掛起條件，阻塞事件的發(fā)生不會(huì)使進(jìn)程立即被執(zhí)行。3.為了阻止進(jìn)程執(zhí)行,

可以通過代理把這個(gè)進(jìn)程置于掛起態(tài)，代理可以是進(jìn)程自己，也可以是父進(jìn)程或操作

系統(tǒng)。4.除非代理顯式地命令系統(tǒng)進(jìn)行狀態(tài)轉(zhuǎn)換，否則進(jìn)程無法從這個(gè)狀態(tài)中轉(zhuǎn)移。

3.8對于哪類實(shí)體,操作系統(tǒng)為了管理它而維護(hù)其信息表?

答：內(nèi)存、I/O、文件和進(jìn)程。（p92）

3.9列出進(jìn)程控制塊中的三類信息。

答：進(jìn)程標(biāo)識，處理器狀態(tài)信息，進(jìn)程控制信息。

3.10為什么需要兩種模式（用戶模式和內(nèi)核模式）?

答：用戶模式下可以執(zhí)行的指令和訪問的內(nèi)存區(qū)域都受到限制。這是為了防止操作系

統(tǒng)受到破壞或者修改。而在內(nèi)核模式下則沒有這些限制，從而使它能夠完成其功能。

3.11操作系統(tǒng)創(chuàng)建一個(gè)新進(jìn)程所執(zhí)行的步驟是什么?

阻塞的系統(tǒng)調(diào)用轉(zhuǎn)化為一個(gè)不產(chǎn)生阻塞的系統(tǒng)調(diào)用。

4.9簡單定義圖4.8中列出的各種結(jié)構(gòu)。

答：SIMD：一個(gè)機(jī)器指令控制許多處理部件步伐一致地同時(shí)執(zhí)行。每個(gè)處理部件都有一

個(gè)相關(guān)的數(shù)據(jù)存儲空間，因此，每條指令由不同的處理器在不同的數(shù)據(jù)集合上執(zhí)行。

MIMD：?組處理器同時(shí)在不同的數(shù)據(jù)集.上執(zhí)行不同的指令序列。主/從：操作系統(tǒng)內(nèi)核

總是在某個(gè)特定的處理器上運(yùn)行，其他處理器只用于執(zhí)行用戶程序，還可能執(zhí)行一些操

作系統(tǒng)實(shí)用程序。SMP:內(nèi)核可以在任何處理器上執(zhí)行，并且通常是每個(gè)處理器從可用

的進(jìn)程或線程池中進(jìn)行各自的調(diào)度工作。集群：每個(gè)處理器都有一個(gè)專用存儲器，而且

每個(gè)處理部件都是一個(gè)獨(dú)立的計(jì)算機(jī)。

4.10列出SMP操作系統(tǒng)的主要設(shè)計(jì)問題。

答：同時(shí)的并發(fā)進(jìn)程或線程，調(diào)度，同步，存儲器管理，可靠性和容錯(cuò)。(pl25)

4.11給出在典型的單體結(jié)構(gòu)操作系統(tǒng)中可以找到且可能是微內(nèi)核操作系統(tǒng)外部子系統(tǒng)中的

服務(wù)和功能。(P126)

答：設(shè)備驅(qū)動(dòng)程序，文件系統(tǒng)，虛存管理程序，窗口系統(tǒng)和安全服務(wù)。

4.12列出并簡單解釋微內(nèi)核設(shè)計(jì)相對于整體式設(shè)計(jì)的七個(gè)優(yōu)點(diǎn)。

答：一致接口:進(jìn)程不需要區(qū)分是內(nèi)核級服務(wù)還是用戶級服務(wù)，因?yàn)樗蟹?wù)都是通過

消息傳遞提供的?？蓴U(kuò)展性：允許增加新的服務(wù)以及在同一個(gè)功能區(qū)域中提供多個(gè)赧務(wù)。

靈活性：不僅可以在操作系統(tǒng)中增加新功能，還可以刪減現(xiàn)有的功能，以產(chǎn)生一個(gè)更小、

更有效的實(shí)現(xiàn)?？梢浦残裕核谢蛘咧辽俅蟛糠痔幚砥鲗Ｓ么a都在微內(nèi)核中。因此，

當(dāng)把系統(tǒng)移植到一個(gè)處理器上時(shí)只需要很少的變化，而且易于進(jìn)行邏輯上的歸類?？煽?/p>

性：小的微內(nèi)核可以被嚴(yán)格地測試，它使用少量的應(yīng)用程序編程接口(API),這就為內(nèi)

核外部的操作系統(tǒng)服務(wù)產(chǎn)生高質(zhì)量的代碼提供了機(jī)會(huì)。分布式系統(tǒng)支持：微內(nèi)核通信中

消息的方向性決定了它對分布式系統(tǒng)的支持。面向?qū)ο蟛僮飨到y(tǒng)環(huán)境：在微內(nèi)核設(shè)計(jì)和

操作系統(tǒng)模塊化擴(kuò)展的開發(fā)中都可以借助面向?qū)ο蠓椒ǖ脑怼?/p>

4.13解釋微內(nèi)核操作系統(tǒng)可能存在的性能缺點(diǎn)。

答：通過微內(nèi)核構(gòu)造和發(fā)送信息、接受應(yīng)答并解碼所花費(fèi)的時(shí)間比一次系統(tǒng)調(diào)用的時(shí)間

要多。(pl27)

4.14列出即使在最小的微內(nèi)核操作系統(tǒng)中也可以找到的三個(gè)功能。

答：低級存儲器管理，進(jìn)程間通信(IPC)以及I/O和中斷管理。

4.15在微內(nèi)核操作系統(tǒng)中,進(jìn)程或線程間通信的基本形式是什么?

答：消息。

5.1列出與并發(fā)相關(guān)的四種設(shè)計(jì)問題

答：進(jìn)程間的交互，共享資源之間的競爭，多個(gè)進(jìn)程的同步問題，對進(jìn)程的處理器時(shí)間分配

問題(pl44)

5.2列出并發(fā)的三種上下文

答：多個(gè)應(yīng)用程序，結(jié)構(gòu)化應(yīng)用程序，操作系統(tǒng)結(jié)構(gòu)

5.3執(zhí)行并發(fā)進(jìn)程的最基本要求是什么？

答：加強(qiáng)互斥的能力(pl44)

5.4列出進(jìn)程間的三種互相知道的程度，并簡單地給出各自的定義。(表5.2)

答：進(jìn)程間互相不知道對方：這是一些獨(dú)立的進(jìn)程，他們不會(huì)一起工作。進(jìn)程間間接知道對

方：這些進(jìn)程并不需要知道對方的進(jìn)程ID號，但他們夫享訪問某些對象，如?個(gè)I/O緩沖

區(qū)。進(jìn)程間直接知道對方：這些進(jìn)程可以通過進(jìn)程ID號互相通信，用于合作完成某些活動(dòng)。

5.5競爭進(jìn)程和合作進(jìn)程進(jìn)程間有什么區(qū)別。

答：競爭進(jìn)程需要同時(shí)訪問相同的資源，像磁盤，文件或打印機(jī)。合作進(jìn)程要么共享訪問一

個(gè)共有的資源，像一個(gè)內(nèi)存訪問區(qū)，要么就與其他進(jìn)程相互通信，在一些應(yīng)用程序或活動(dòng)上

進(jìn)行合作。

5.6列出與競爭進(jìn)程相關(guān)的三種控制問題，并簡單地給出各自的定義。

答：互斥：競爭進(jìn)程僅可以訪問一個(gè)臨界資源（一次僅有一個(gè)進(jìn)程可以訪問臨界資源;，并

發(fā)機(jī)制必須滿足一次只有一個(gè)進(jìn)程可以訪問臨界資源這個(gè)規(guī)則。死鎖：如果競爭進(jìn)程需要唯

一的訪問多于一個(gè)資源，并且當(dāng)一個(gè)進(jìn)程控制著一個(gè)進(jìn)程，且在等待另一個(gè)進(jìn)程，死鎖可能

發(fā)生。饑餓：一組進(jìn)程的一個(gè)可能會(huì)無限期地拒絕進(jìn)入到一個(gè)需要資源，因?yàn)槠渌蓡T組成

壟斷這個(gè)資源。

5.7列出對互斥的要求。

答：1.必須強(qiáng)制實(shí)施互斥：在具有關(guān)于相同資源或共享對象的臨界區(qū)的所有進(jìn)程中，一次只

允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)°2.一個(gè)在非臨界區(qū)停止的進(jìn)程必須不干涉其他進(jìn)程。3.絕不允許

出現(xiàn)一個(gè)需要訪問臨界區(qū)的進(jìn)程被無限延遲的情況，即不會(huì)餓死或饑餓。4.當(dāng)沒有進(jìn)程在臨

界區(qū)中時(shí)，任何需要進(jìn)入臨界區(qū)的進(jìn)程必須能夠立即進(jìn)入。5.對相關(guān)進(jìn)程的速度和處理器的

數(shù)目沒有任何要求和限制，6.一個(gè)進(jìn)程駐留在臨界區(qū)中的時(shí)間是有限的。

5.8在信號量上可以執(zhí)行什么操作。

答：1.一個(gè)信號量可以初始化成非負(fù)數(shù)。2.wait操作使信號量減1,如果值為負(fù)數(shù)，那么進(jìn)

程執(zhí)行wait就會(huì)受阻。3signal操作使信號量增加1,如果小于或等于0,則被wait操作阻

塞的進(jìn)程被解除阻塞。

5.9.二元信號量與一般信號量有什么區(qū)別。

答：二元信號量只能取?；?，而一般信號量可以取任何整數(shù)。

5.10強(qiáng)信號量與弱信號量有什么區(qū)別。

答：強(qiáng)信號量要求在信號量上等待的進(jìn)程按照先進(jìn)先出的規(guī)則從隊(duì)列中移出。弱信號量沒有

此規(guī)則。

5.11.什么是管程。

答：管程是由一個(gè)或多個(gè)過程，一個(gè)初始化序列和局部數(shù)據(jù)組成的軟件模塊。

5.12對于消息，有阻塞和無阻塞有什么區(qū)別？

答：p169

5.13.通常與讀者-寫者問題相關(guān)聯(lián)的有哪些條件？

答：1.任意多的讀進(jìn)程可以同時(shí)讀這個(gè)文件，2.一次只有一個(gè)寫進(jìn)程可以往文件中寫，3.如

果一個(gè)寫進(jìn)程正在往文件中寫時(shí)，則禁止任何讀進(jìn)程讀文件。

第六章習(xí)題翻譯

第一部分復(fù)習(xí)題

6.1給出可重用資源和可消費(fèi)資源的例子。

答：可重用資源：處理器，I/O通道，主存和輔存，設(shè)備以及諸如文件，數(shù)據(jù)

庫和信號量之類的數(shù)據(jù)結(jié)構(gòu)。

可消費(fèi)資源：中斷，信號，消息和I/O緩沖區(qū)中的信息。

6.2可能發(fā)生死鎖所必須的三個(gè)條件是什么？

答：互斥，占有且等待，非搶占。

6.3產(chǎn)生死鎖的第4人條件是什么？

答：循環(huán)等待。

6.4如何防止占有且等待的條件？

答：可以要求進(jìn)程一次性地請求所有需要的資源，并且阻塞這個(gè)資源直到所有請

求都同時(shí)滿足。

6.5給出防止無搶占條件的兩種方法。

答：第一種，如果占有某些資源的一個(gè)進(jìn)程進(jìn)行進(jìn)一步資源請求被拒絕，則該進(jìn)

程必須釋放它最初占用的資源，如果有必要，可再次請求這些資源和另外的資源。

第二種，如果一個(gè)進(jìn)程請求當(dāng)前被另一個(gè)進(jìn)程占有的一個(gè)資源，則操作系

統(tǒng)可以搶占另一個(gè)進(jìn)程，要求它釋放資源。

6.6如何防止循環(huán)等待條件？

答：可以通過定義資源類型的線性順序來預(yù)防。如果一個(gè)進(jìn)程已經(jīng)分配到了R類

型的資源，那么它接下來請求的資源只能是那些排在R類型之后的資源類型。

6.7死鎖避免，檢測和預(yù)防之間的區(qū)別是什么？

答：死鎖預(yù)防是通過間接地限制三種死鎖必要條作的至少一個(gè)或是直接地限制循

環(huán)等待的發(fā)生來避免死鎖的出現(xiàn)。死鎖避免允許可能出現(xiàn)的必要條件發(fā)生，但是

采取措施確保不會(huì)出現(xiàn)死鎖的情況。而死鎖檢測允許資源的自由分配，采取周期

性的措施來發(fā)現(xiàn)并處理可能存在的死鎖情況。

第二部分習(xí)題

6.1寫出圖6.1(a)中死鎖的四個(gè)條件。

解：互斥：同一時(shí)刻只有一輛車可以占有一個(gè)十字路口象限。占有旦等待；沒有

車可以倒退；在十字路口的每輛車都要等待直到它前面的象限是空的。非搶占:

沒有汽車被允許擠開其他車輛。循環(huán)等待：每輛汽車都在等待一個(gè)此時(shí)已經(jīng)被

其他車占領(lǐng)的十字路口象限。

6.2按照6.1節(jié)中對圖6.2中路徑的描述，給出對圖6.3中6種路徑的簡單

描述。

解：1.Q獲得B和A,然后釋放B和A.當(dāng)P重新開始執(zhí)行的時(shí)候，它將會(huì)

能夠獲得兩個(gè)資源。

2.Q獲得B和A,P執(zhí)行而且阻塞在對A的請求上.Q釋放B和A。當(dāng)P重

新開始執(zhí)行的時(shí)候，它將會(huì)能夠獲得兩個(gè)資源。

3.Q獲得B,然后P獲得和釋放A.Q獲得A然后釋放

B和A.當(dāng)P重新開始行的時(shí)候，它將會(huì)能夠獲得Bo

4.P獲得A然后Q獲得B.P釋放A.Q獲得A然后釋放

B.P獲得B然后釋放Bo

5.P獲得，然后釋放A.P獲得B.Q執(zhí)行而且阻塞在對B的請求上。P釋放

B。當(dāng)Q重新開始執(zhí)行的時(shí)候，，它將會(huì)能夠獲得兩個(gè)資源。

6.P獲得A而且釋放A然后獲得并且釋放B.當(dāng)Q重新開始實(shí)行，它將會(huì)能

夠獲得兩個(gè)資源。

6.3圖6.3反映的情況不會(huì)發(fā)生死鎖，請證明。

證明：如果Q獲得B和A(在P之前請求A),那么Q能使用這些兩類資源

然后釋放他們，允許A進(jìn)行。如果P在Q之前請求A獲得A,然后Q最多能執(zhí)

行到請求A然后被阻塞。然而，一旦P釋放A,Q能進(jìn)行。一旦Q釋放B,

A能進(jìn)行。

6.4考慮下面的一個(gè)系統(tǒng)，當(dāng)前不存在未滿足的請求。

可用

rlr2r3r4

100

2

當(dāng)前分配最大需求

仍然需求

a計(jì)算每個(gè)進(jìn)程仍然可能需要的資源，并填入標(biāo)為“仍然需要”的列中。

b系統(tǒng)當(dāng)前是處于安全狀態(tài)還是不安全狀態(tài)，為什么。

c系統(tǒng)當(dāng)前是否死鎖？為什么？

d哪個(gè)進(jìn)程（如果存在）是死鎖的或可能變成死鎖的？

e如果P3的請求（0,1,0,0）到達(dá)，是否可以立即安全地同意該請求？在什

么狀態(tài)（死鎖，安全，不安全）下可以立即同意系統(tǒng)剩下的全部請求？如果立即

同意全部請求，哪個(gè)進(jìn)程（如果有）是死鎖的或可能變成死鎖的？

解：a.0000

0750

6622

2002

rlrlr2

r2r3r4r3r4rlr2r3r4

01

001202

20002750

6

0034656

4

2354356

03320652

0320

b.系統(tǒng)當(dāng)前處于安全狀態(tài)，因?yàn)橹辽儆幸粋€(gè)進(jìn)程執(zhí)行序列，不會(huì)導(dǎo)致死鎖，

運(yùn)行順序是pl,p4,p5,p2,p3.

c.系統(tǒng)當(dāng)前并沒有死鎖，因?yàn)镻l進(jìn)程當(dāng)前分配與最大需求正好相等，F(xiàn)1進(jìn)

程可以運(yùn)行直至結(jié)束，接下來運(yùn)行其他進(jìn)程

d.P2,P3,P4,P5可能死鎖

e.不可以，當(dāng)進(jìn)程P1,P4,P5執(zhí)行完可用資源為（4,6,9,8）,P2,P3將死

鎖，所以不安全，完全不可以立即同意系統(tǒng)剩下的全部請求。

6.5請把6.4中的死鎖檢測算法應(yīng)用于下面的數(shù)據(jù)，并給出結(jié)果。

Available=(2100)

20010010

Request二1010Allocation=2001

21000120

解：1.W=(2100)

2.MarkP3;W=(2100)+(0120)=(2220)

3.MarkP2;W=(2220)+(2001)=(4221)

4.MarkPl;nodeadlockdetected沒有死鎖

6.6一個(gè)假脫機(jī)系統(tǒng)包含一個(gè)輸入進(jìn)程I,用戶進(jìn)程進(jìn)程P和一個(gè)輸出進(jìn)程0,

它們之間用兩個(gè)緩沖區(qū)連接。進(jìn)程以相等大小的塊為單位交換數(shù)據(jù)，這些塊利用

輸入緩沖區(qū)和輸出緩沖區(qū)之間的移動(dòng)邊界緩存在磁盤匕并取決于進(jìn)程的速度。

所使用的通信原語確保滿足下面的資源約束：V。Wmax

其中，max表示磁盤中的最大塊數(shù)，i表示磁盤中的輸入塊數(shù)目，。表示磁盤中的

輸出塊數(shù)目。

以下是關(guān)于進(jìn)程的知識：

1.只要環(huán)境提供數(shù)據(jù)，進(jìn)程I最終把它輸入到磁盤上（只要磁盤空間可用）。

2.只要磁盤可以得到輸入，進(jìn)程P最終消耗掉它，并在磁盤上為每個(gè)輸入塊輸

出有限量的數(shù)據(jù)（只要磁盤空間可用）。

3.只要磁盤可以得到輸出，進(jìn)程0最終消耗掉它。說明這個(gè)系統(tǒng)可能死鎖。

解：當(dāng)I的速度遠(yuǎn)大于P的速度，有可能使磁盤上都是輸入數(shù)據(jù)而此時(shí)P進(jìn)程要處

理輸入數(shù)據(jù)，即要將處理數(shù)據(jù)放入輸出數(shù)據(jù)區(qū)。于是P進(jìn)程等待磁盤空間輸出，1

進(jìn)程等待磁盤空間輸入，二者死鎖。

6.7給出在習(xí)題6.6中預(yù)防死鎖的附加資源約束，仍然通話輸入和輸出緩沖區(qū)

之間的邊界可以根據(jù)進(jìn)程的要求變化。

解：為輸出緩沖區(qū)保留一個(gè)最小數(shù)目（稱為res。）塊，但是當(dāng)磁盤空間足夠大時(shí)允

許輸出塊的數(shù)目超過這一個(gè)界限。資源限制現(xiàn)在變成

I+OWmax

IWmax-reso

當(dāng)0<reso<max

如果程序P正在等候遞送輸出給磁盤，程序0最后處理所有的早先輸出而且

產(chǎn)生至少reso頁，然后讓P繼續(xù)執(zhí)行。因此P不會(huì)因?yàn)?而延遲。

如果磁盤充滿I/O,I能被延遲；但是遲早，所有的早先的

輸入可以被P處理完，而且對應(yīng)的輸出將會(huì)被0處理，

因而可以讓I繼續(xù)執(zhí)行。

6.8在THE多道程序設(shè)計(jì)系統(tǒng)中，一個(gè)磁鼓（磁盤的先驅(qū)，用做輔存）被劃

分為輸入緩沖區(qū)，處理和輸出緩沖區(qū)，它們的邊界可以移動(dòng)，這取決于所涉及的

進(jìn)程速度。磁鼓的當(dāng)前狀態(tài)可以用以下參數(shù)描述：

max表示磁鼓中的最大頁數(shù)，i示磁鼓中的愉入頁數(shù)，p示磁鼓中的處理頁數(shù)，。

示磁鼓中的輸出頁數(shù)，res。出保留的最小頁數(shù)，resp理保留的最小頁數(shù)。

解：

I+O+PWmax-

I+OWmax-resp

I+PWmax-reso

IWmax-(reso+resp)

6.9在THE多道程序設(shè)計(jì)系統(tǒng)中，一頁可以進(jìn)行下列狀態(tài)轉(zhuǎn)換：

1.空—輸入緩沖區(qū)（輸入生產(chǎn)）

2.輸入緩沖區(qū)一處理區(qū)域（輸入消耗）

3.處理區(qū)域輸出緩沖區(qū)（輸出生產(chǎn)）

4.輸出緩沖區(qū)一空（輸出生產(chǎn)）

5.空一處理區(qū)域（輸出消耗）

6.處理區(qū)域一空（過程調(diào)用）

a根據(jù)I,。和P的量定義這些轉(zhuǎn)換的結(jié)果。

b如果維持習(xí)題6.6中關(guān)于輸入進(jìn)程，用戶進(jìn)程和輸出進(jìn)程的假設(shè)，它們中的任

何一個(gè)轉(zhuǎn)換是否會(huì)導(dǎo)致死鎖。

解：1.i-i+1

2.i-p+1

3.p-p-1；o-o?1

4.o-o-1

5.p-p+1

6.p-p-1

b.結(jié)合在對問題6.7的解決辦法被列出的資源限制，我們

能總結(jié)下列各項(xiàng)：

6.過程返回能立刻發(fā)生因?yàn)樗麄冎会尫?/p>

資源。

5.程序調(diào)用可能用盡磁盤片（p=max-reso）導(dǎo)致死鎖。

4.當(dāng)有輸出時(shí)輸出消耗能立刻發(fā)生。

3.輸出生產(chǎn)能暫時(shí)被延遲直到所有的早先輸出被消耗而且為下一步的輸出至少

可以產(chǎn)生reso頁。

2.只要有輸入，輸入消耗能立刻發(fā)生。

1.輸入生產(chǎn)被延遲直到所有先前輸入和對應(yīng)的輸出已經(jīng)被消耗。此時(shí)，當(dāng)i=

。二0,如果消費(fèi)進(jìn)程還沒有占用完磁盤空間（p<max-reso）,可以產(chǎn)生輸入。

結(jié)論：分配給消費(fèi)進(jìn)程的不受控制的存儲空間是

唯一可能引發(fā)死鎖的因素。

6.10考慮一個(gè)共有150個(gè)存儲器單元的系統(tǒng)，其單元如下分配三個(gè)進(jìn)程:

進(jìn)程最大占用

17045

26040

36015

使用銀行家算法，以確定同意下面的任何一個(gè)請求是否安全。如果安全，說明能

保證的終止序列；如果不安全，給出結(jié)果分配簡表。

a.第4個(gè)進(jìn)程到達(dá)，最多需要60個(gè)存儲單元，最初需要25個(gè)單元。

b第4個(gè)進(jìn)程到達(dá)，最多需要60個(gè)存儲單元，最初需要35個(gè)單元。

解：a.若同意第4個(gè)進(jìn)程請求，則儲存器單元共用去25+15+40+45=125個(gè)單元,

還有25個(gè)存儲單元，則可以安全執(zhí)行全部進(jìn)程。安全順序是1—2—3—4

b.若同意第4個(gè)進(jìn)程請求，則還有15個(gè)資源可以用，此時(shí)處于不安全狀態(tài)，

結(jié)果分配見表

進(jìn)程最大占有需要空閑

170452515

2604020

3601545

4603525

6.11評價(jià)獨(dú)家算法在實(shí)際應(yīng)用中是否有用。

解：不切實(shí)際的：不能總是預(yù)先知道最大要求，進(jìn)程數(shù)目和資源數(shù)目可能隨著時(shí)

間改變。大多數(shù)的操作系統(tǒng)忽視死鎖。

6.12有一個(gè)已經(jīng)實(shí)現(xiàn)了的管道算法，使得進(jìn)程P0產(chǎn)生的T類型的數(shù)據(jù)元素

經(jīng)進(jìn)程序列P1P2…PnT,并且按該順序在元素上操作。

a.定義一個(gè)一般的消息緩沖區(qū)，包含所有部分消耗的數(shù)據(jù)元素，并按下面的格式

為進(jìn)程Pi(OWiWn-1)寫一個(gè)算法。

Repeat

從前驅(qū)接收

消耗

給后續(xù)發(fā)送

Forever

假設(shè)P0收到PnT發(fā)送的空元素。該算法能夠使進(jìn)程直接在緩沖區(qū)中保存的消息

上操作，而無需復(fù)制。

b.說明關(guān)于普通的緩沖區(qū)進(jìn)程不會(huì)死鎖。

解：arbuffer:array0..max-1ofsharedT;

available:sharedarray0..n~lof0..max;

Initialization

varK:1..n-1;

regionavailabledo

begin

available(O):=max;

foreverykdoavailable(k):=0;

end

“Processi〃

varj:0..max-1;succ:0..n-1;

begin

j:=0;succ:=(i+1)modn;

repeat

regionavailabledo

awaitavailable(i)>0;

regionbuffer(j)doconsumeelement;

regionavailabledo

begin

available(i):=available(i)-1;

available(succ):=available(succ)+1;

end

j:=(j+1)nodmax;

forever

end

b.死鎖可以被解決通過

P0waitsforPn-lAND

PlwaitsforPOAND

Pn-1waitsforPn-2

因?yàn)?/p>

(available(0)=0)AND

(available(1)0)AND

(available(n-1)=0)

但是如果max>0,這個(gè)條件不成立，因?yàn)榕R界域滿足

claim{l)+claimk,2,+…

<available(J)+avai…+available(哈

=max

6.13a.3個(gè)進(jìn)程共享4個(gè)資源單元，一次只能保留或釋放一個(gè)單元。每個(gè)

進(jìn)程最大需要2個(gè)單元。說明不會(huì)死鎖。

b.N個(gè)進(jìn)程共享M個(gè)資源單元，一次只能保留或釋放一個(gè)單元。每個(gè)進(jìn)程最大需

要單元數(shù)不超過M,并且所有最大需求的總和小于M+N。說明不會(huì)發(fā)生死鎖。

解：a.說明由于每個(gè)進(jìn)程最多需要2個(gè)資源，最壞情況下，每個(gè)進(jìn)程需要獲得一

個(gè)，系統(tǒng)還剩1個(gè)，這一個(gè)資源，無論分給誰都能完成。完成進(jìn)程釋放資源后，

使剩余進(jìn)程也完成，故系統(tǒng)不會(huì)死鎖。

b.假定每個(gè)進(jìn)程最多申請X個(gè)資源，最壞情況下，每個(gè)進(jìn)程都得到XT個(gè)資

源都在申請最后一個(gè)資源，這時(shí)系統(tǒng)剩余資源數(shù)量為M-N(X—1),只要系統(tǒng)還有

一個(gè)剩余資源，就可以使其中的一個(gè)進(jìn)程獲得所需要的全部資源，該進(jìn)程運(yùn)行結(jié)

束以后釋放資源，就可以使其他進(jìn)程得到全部資源的滿足，因此，當(dāng)M-N(XT)》

1時(shí)系統(tǒng)不會(huì)發(fā)生死鎖，解這個(gè)不等式X《(M+N-1)，系統(tǒng)不會(huì)發(fā)生死鎖，因此,

當(dāng)所有進(jìn)程的需求總和小于M+N時(shí)，系統(tǒng)是不會(huì)發(fā)生死鎖的。

6.14考慮一個(gè)由四個(gè)進(jìn)程和一個(gè)單獨(dú)資源組成的系統(tǒng)，當(dāng)前的聲明和分

配矩陣是

3'1

21

C=9A=3

72

對于安全狀態(tài)，需要的最小資源數(shù)目是多少？

解：最小資源數(shù)是3個(gè)，總共有10個(gè)資源。P2獲得一個(gè)資源，完成后釋

放兩個(gè)資源，P1獲得三個(gè)資源，完成后釋放三個(gè)資源，接下來P4獲得五個(gè)資

源，釋放完資源后，F(xiàn)3獲得所需的6個(gè)資源后完成。

6.15考慮下列處理死鎖的方法：1銀行家算法，2死鎖檢測并殺死線程，

釋放所有資源，3事先保留所有資源，4如果線程需要等待，5資源排序，6重

新執(zhí)行檢測死鎖并退回線程的動(dòng)作。

評價(jià)解釋死鎖的不同方法使用的一個(gè)標(biāo)準(zhǔn)是，哪種方法允許最大的并發(fā)。換

言之，在沒有死鎖時(shí)，哪種方法允許最多數(shù)目的線程無需要等待繼續(xù)前進(jìn)？對下

面列出的6種處理死鎖的方法，給出從1到6的一個(gè)排序(1表示最大程序的并

發(fā))，并解釋你的排序。

另一個(gè)標(biāo)準(zhǔn)是效率；哪種方法需要最小的處理器開銷？假設(shè)死鎖很少發(fā)生，

給出各種方法從1到6的一個(gè)排序(1表示最有效)，并解釋這樣排序的原因。

如果死鎖發(fā)生很頻繁，你的順序需要改變嗎？

解：a從最多并發(fā)事件到最少，有一個(gè)大概的次序如下：

1.死鎖檢測并殺死線程，釋放所有資源

發(fā)現(xiàn)死鎖并退回線程的動(dòng)作，如果線程需要等候那么重新開始線程而且釋放所有

的資源，在死鎖發(fā)生之前，這些運(yùn)算法則都不會(huì)限制并發(fā)，因?yàn)樗麄冄鲑囘\(yùn)行時(shí)

間檢查而并非靜態(tài)的限制。他們的效果在死鎖被發(fā)現(xiàn)比較難以描述：他們?nèi)匀?/p>

允許許多并發(fā)(在一些情形，他們增加它)，但是很難有準(zhǔn)確的估計(jì)。第三個(gè)運(yùn)

算法則是最奇怪的，因?yàn)槿绱撕笤S多的它的并發(fā)將會(huì)是無用的重復(fù)；因?yàn)榫€程

競爭執(zhí)行時(shí)間，這一個(gè)運(yùn)算法則也影響運(yùn)行速度。因此在兩者的極端，它以這順

序被列出兩次。

2.銀行家的運(yùn)算法則

資源排序

這些運(yùn)算法則因?yàn)橄拗贫喾N的可允許的計(jì)算，而相對早先兩種法則會(huì)引起更多的

不必要的等候。銀行家的運(yùn)算法則避免不安全的配置和資源排序限制配置序列

以便線程在他們是否?定等候的時(shí)候有較少的選擇。

3.事先保留所有的資源

這一個(gè)運(yùn)算法則相比前兩個(gè)要允許更少的并發(fā)，但是比最壞的那一種有更少的

缺點(diǎn)。因?yàn)橐A(yù)先保留所有的資源,線程必須等候比較長的而且當(dāng)他們工作的時(shí)

候更有可能阻塞其他的線程，因此系統(tǒng)上來說具有更多的線性。

4.如果線程需要等待，則重新啟動(dòng)線程并且釋放所有的資源

如上所述，這一個(gè)運(yùn)算法則在區(qū)別最多和最少并發(fā)上有疑問,這具體要看并發(fā)的

定義。

b從最高效率到最低，有如下大概的一個(gè)順序：

1.預(yù)先保留所有的資源

資源排序

因?yàn)樗麄儧]有包括運(yùn)行時(shí)間經(jīng)常開支，所以這些運(yùn)算法則最有效率。

注意這是在相同的靜態(tài)限制下的結(jié)果。

2.銀行家的運(yùn)算法則

發(fā)現(xiàn)死鎖而且殺死線程,釋放它的資源

這些運(yùn)算法則在概略的配置上包括運(yùn)行時(shí)間檢查

；銀行家的運(yùn)算法則運(yùn)行搜尋查證復(fù)雜度在線程和配置的數(shù)字和死鎖檢測中是

O(nm),死鎖檢測的復(fù)雜度是0(n)。資源-從屬鏈被線程數(shù)目，資源數(shù)目和分配

數(shù)目限制。

3.發(fā)現(xiàn)死鎖并退回線程的動(dòng)作

這一個(gè)運(yùn)算法則運(yùn)行也需要運(yùn)行上述的相同的時(shí)間檢查。

在寫內(nèi)存上的復(fù)雜度為0(n)。

4.如果線程需要等待，則重新啟動(dòng)線程并釋放所有的資源

這一個(gè)運(yùn)算法則是非常無效率，有如下兩個(gè)理由。首先，因?yàn)榫€程有重新開始

的危險(xiǎn)，他們完成的可能性低。其次，他們與其他重新開始線程競爭有限的執(zhí)行

時(shí)間，因此整個(gè)系統(tǒng)運(yùn)行的速度很慢。

6.16評價(jià)下面給出的就餐問題的解決方案。一位饑餓的哲學(xué)家首先拿起他左

邊的叉子，如果他右邊的叉子也是可用的，則拿起右邊的叉子開始吃飯，否則他

放下左邊的義子，并重復(fù)這個(gè)循環(huán)。

解：如果哲學(xué)家們步調(diào)完全一致地拿起左邊叉子又放下的話，他們會(huì)重復(fù)這一過

程，導(dǎo)致饑餓情況的出現(xiàn)。

6.17假設(shè)有兩種類型的哲學(xué)家。一類總是先拿起左邊的叉子(左撇子)，另

一類總是先拿起右邊的叉子(右撇子)。左撇子的行為和圖6.12中定義的一

致。右撇子的行為如下：

begin

repeat

think;

wait(fork[(i+l)mod5]);

wait(fork[i]);

eat;

signal(fork[i]);

signal(fork[(i+l)mod5]);

forever;

end;

證明：a如果至少有一個(gè)左撇子或右撇子，則他們的任何就座安排都可以避免死

鎖。

b如果至少有一個(gè)左撇子或右撇子，則他們的任何就座安排都可以防止饑餓.

解：a假設(shè)存在死鎖情況，設(shè)有D個(gè)哲學(xué)家，他們每人都有一支叉子而且另一

支叉子被鄰居占有。不失一般性，設(shè)Pj是一個(gè)左撇子。Pj抓牢他的左邊叉子

而且沒有他的右邊叉子，他的右邊鄰居Pk沒有完成就餐因此也是一個(gè)左撇子。

因此依次推理下去所有這D個(gè)哲學(xué)家都是左撇子。這與既有左撇子又有右撇子的

條件矛盾，假設(shè)不成立，不存在死鎖。

b

假設(shè)左撇子Pj饑餓，也就是說，有一部分人在就餐而Pj從不吃。假如Pj沒

有叉子。這樣Pj的左邊鄰居Pi一定持續(xù)地占有叉子而始終不吃完。因此Pi

是右撇子，

抓住他的右邊叉子，但是從不得到他的左邊叉子來完成就餐,也就是說Pi

也饑餓9現(xiàn)在Pi左邊鄰居也一定是持續(xù)占有右邊叉子的右撇子。向左進(jìn)行這

樣的推理，得出所有哲學(xué)家都是饑餓的右撇子，這同Pj是個(gè)左撇子矛盾。因此Pj

一直擁有左邊子而且在等待他的右邊叉子,Pj的右邊鄰居Pk一直舉著他的左

邊叉子而且從不完成一餐,也就是，Pk是也饑餓的左撇子。如果Pk不是一直

拿著他的左邊又子，Pj就可以就餐；因此Pk拿著他的左邊義子。向右推理可

得所有哲學(xué)家都是饑餓的左撇子。這與條件矛盾，因此假設(shè)不成立，沒有人饑餓。

6.18圖1.17顯示了另外一個(gè)使用管程解決哲學(xué)家就餐問題的方法。和圖6.

14比較并闡述你的結(jié)論。

解：圖6.14是等待可用的叉子，圖6.17是等待鄰居吃完，在本質(zhì)上邏置是

一樣的，后者顯得更加緊湊。

monitordining_controller;

enunistates}thinking,hungry,eating}statcl5|;

condneedFork[5]/*conditionvariable*/

voidget_forks(intpid)/*pidisthephilosopheridnumber*/

(

start[pid|=hungry;/*announcethatIamhungry*/

if(s(aie[(pid+1)%S]==eaiing

||(state[(pid-l)%5]==eating

cwait(nccdForklpid]);/*waitifeitherneighboriseating*/

slaie[pid]=ealing;/"proceedifneitherneighboriseating*/

}

voidrelease_fork(intpid)

(

state[pid]=thinking;

/*givcright(highcr)ncighborachancetocat*/

if(sta(e[(pid+l)%5])==hungry)

&(state[(pid+2)%5])!=eating)

csignal(needFork[pid+l|);

/*giveleft(lower)neighborachancetoeat*/

elseif(state[(pid-1)%5J==hungry)

||(state[(pid-2)%5!=eating]

voidphilosopher[k=0to4]/*thefivephilosopherclients*/

{

while(true)

(

<think>;

get_fbrks(k);/"clientrequeststwoforksviamonitor*/

<eatspaghctti>;

release_forks(k);/*clientreleasesforksviathemonitor*/

)

)

6.19在表6.13中，Linux的一些原子操作不會(huì)涉及到對同一變量的兩次訪

問。Ltlatomic_read(atomic_t*v).簡單的讀操作在任何體系結(jié)構(gòu)中都是原子

的。為什么該操柞增加到了原字操作的指令表？

解：原子操作是在原子數(shù)據(jù)類型上操作，原子數(shù)據(jù)類型有他們自己的內(nèi)在的

格式。因此，不能用簡單的閱讀操作，但是特別的閱讀操作

對于原子數(shù)據(jù)類型來說是不可或缺的.

6.20考慮Linux系統(tǒng)中的如下代碼片斷：

readlock(&mrrwlock);

write_lock(&mr_rwlock);

mrjwlock是讀著寫者鎖。這段代碼的作用是什么？

解：因?yàn)閷懻哝i將會(huì)自旋，所以這段代碼會(huì)導(dǎo)致死鎖，等待所有的

讀者解鎖，包括喚醒這個(gè)線程。

6.21兩個(gè)變量a和b分別有初始值1和2,對于Linux系統(tǒng)有如下代碼：

線線程

程12

a=3；一

mb()；—

一C=b；

一rmb()；

d=a；

使用內(nèi)在屏障是為了避免什么錯(cuò)誤？

解：沒有使用內(nèi)存屏障，在一些處理器上可能c接到b的新值，而d接到b的舊

值。舉例來說，c可以等于4(我們期待的)，然而d可能等于1.(不是我們期

待的)。使用nib()確保a和b按合適的次序被寫，使用rmb()確保c和d按

合適的次序被讀。

第7章內(nèi)存管理

復(fù)習(xí)題：

7.1.內(nèi)存管理需要滿足哪些需求?

答：重定位、保護(hù)、共享、邏輯組織和物理組織。

7.2.為什么需要重定位進(jìn)程的能力?

答：通常情況下，并不能事先知道在某個(gè)程序執(zhí)行期間會(huì)有哪個(gè)程序駐留在主存中。

此外還希望通過提供一個(gè)巨大的就緒進(jìn)程池，能夠把活動(dòng)進(jìn)程換入和換出主存，以便

使處理器的利用率最大化。在這兩種情況下，進(jìn)程在主存中的確切位置是不可預(yù)知的。

7.3.為什么不可能在編譯時(shí)實(shí)施內(nèi)存保護(hù)?

答：由于程序在主存中的位置是不可預(yù)測的，因而在編譯時(shí)不可能檢查絕對地址來確

保保護(hù)。并且，大多數(shù)程序設(shè)計(jì)語言允許在運(yùn)行時(shí)進(jìn)行地址的動(dòng)態(tài)計(jì)算(例如，通過

計(jì)算數(shù)組下標(biāo)或數(shù)據(jù)結(jié)構(gòu)中的指針)。因此，必須在運(yùn)行時(shí)檢查進(jìn)程產(chǎn)生的所有存儲

器訪問，以便確保它們只訪問了分配給該進(jìn)程的存儲空間。

7.4.允許兩個(gè)或多個(gè)進(jìn)程訪問進(jìn)程的某一特定區(qū)域的原因是什么?

答：如果許多進(jìn)程正在執(zhí)行同一程序，則允許每個(gè)進(jìn)程訪問該程序的同一個(gè)副本要比

讓每個(gè)進(jìn)程有自己單獨(dú)的副本更有優(yōu)勢。同樣，合作完成同一任務(wù)的進(jìn)程可能需要共

享訪問同一個(gè)數(shù)據(jù)結(jié)構(gòu)。

7.5.在固定分區(qū)方案中,使用大小不等的分區(qū)有什么好處?

答：通過使用大小不等的固定分區(qū)：1.可以在提供很多分區(qū)的同時(shí)提供一到兩個(gè)非常

大的分區(qū)。大的分區(qū)允許將很大的進(jìn)程全部載入主存中。2.由「小的進(jìn)程可以被放入

小的分區(qū)中，從而減少了內(nèi)部碎片。

7.6.內(nèi)部碎片和外部碎片有什么區(qū)別?

答：內(nèi)部碎片是指由于被裝入的數(shù)據(jù)塊小于分區(qū)大小而導(dǎo)致的分區(qū)內(nèi)部所浪費(fèi)的空

間。外部碎片是與動(dòng)態(tài)分區(qū)相關(guān)的一種現(xiàn)象，它是指在所有分區(qū)外的存儲空間會(huì)變成

越來越多的碎片的。

7.7.邏輯地址、相對地址和物理地址間有什么區(qū)別?

答：邏輯地址是指與當(dāng)前數(shù)據(jù)在內(nèi)存中的物理分配地址無關(guān)的訪問地址，在執(zhí)行對內(nèi)

存的訪問之前必須把它轉(zhuǎn)化成物理地址。相對地址是邏輯地址的一個(gè)特例，是相對于

某些已知點(diǎn)（通常是程序的開始處）的存儲單元。物理地址或絕對地址是數(shù)據(jù)在主存

中的實(shí)際位置。

7.8.頁和幀之間有什么區(qū)別?

答：在分頁系統(tǒng)中，進(jìn)程和磁盤上存儲的數(shù)據(jù)被分成大小固定相等的小塊，叫做頁。

而主存被分成了同樣大小的小塊，叫做幀。一頁恰好可以被裝入一幀中。

79頁和段之間有什么區(qū)別?

答：分段是細(xì)分用戶程序的另一種可選方案。采用分段技術(shù)，程序和相關(guān)的數(shù)據(jù)被劃

分成一組段。盡管有一個(gè)最大段長度，但并不需要所有的程序的所有段的長度都相等。

習(xí)題：

7.1.2.3節(jié)中列出了內(nèi)存管理的5個(gè)目標(biāo)，7.1節(jié)中列出了5中需求。請說明它們是一致

的。

答：重定位-支持模塊化程序設(shè)計(jì)；

保護(hù)比保護(hù)和訪問控制以及進(jìn)程隔離；

共享七保護(hù)和訪問控制；

邏輯組織-支持模塊化程序設(shè)計(jì)；

物理組織心長期存儲及自動(dòng)分配和管理.

7.2.考慮使用大小相等分區(qū)的固定分區(qū)方案。分區(qū)大小為2el6字節(jié)，貯存的大小為2e24

字節(jié)。使用一個(gè)進(jìn)程表來包含每一個(gè)進(jìn)程對應(yīng)的分區(qū)。這個(gè)指針需要多少位？

答：分區(qū)的數(shù)量等于主存的字節(jié)數(shù)除以每個(gè)分區(qū)的字節(jié)數(shù)：224/216=28.需要8個(gè)

比特來確定一個(gè)分區(qū)大小為28中的某一個(gè)位置。

7.3.考慮動(dòng)態(tài)分區(qū)方案，說明平均內(nèi)存中空洞的數(shù)量是段數(shù)量的一半。

答：設(shè)n和h為斷數(shù)量和空洞數(shù)量的個(gè)數(shù).在主存中，每劃分一個(gè)斷產(chǎn)生一個(gè)空洞的概

率是0.5,因?yàn)閯h除一個(gè)斷和添加一個(gè)斷的概率是一樣的.假設(shè)s是內(nèi)存中斷的個(gè)數(shù)那

么空洞的平均個(gè)數(shù)一定等于s/2.而導(dǎo)致空洞的個(gè)數(shù)一定小余斷的數(shù)量的直接原因是

相鄰的兩個(gè)斷在刪除是一定會(huì)產(chǎn)生一個(gè)空洞.

7.4.在實(shí)現(xiàn)動(dòng)態(tài)分區(qū)中的各種放置算法（見7.2節(jié)），內(nèi)存中必須保留一個(gè)空閑塊列表。

分別討論最佳適配、首次適配、臨近適配三種方法的平均查找長度。

答:通過上題我們知道，假設(shè)S是駐留段的個(gè)數(shù)，那么空洞的平均個(gè)數(shù)是S/2。從平均

意義上講，平均查找長度是s/4。

7.5.動(dòng)態(tài)分區(qū)的另一種放置算法是最壞適配，在這種情況下，當(dāng)調(diào)入一個(gè)進(jìn)程時(shí)，使用最

大的空閑存儲塊。該方法與最佳適配、首次適配、鄰近適配相比，優(yōu)點(diǎn)和缺點(diǎn)各是什

么？它的平均查找長度是多少？

答：一種對最佳適配算法的評價(jià)即是為固定分配一個(gè)組塊后和剩余空間是如此小以至

于實(shí)際上已經(jīng)沒有什么用處。最壞適配算法最大化了在一次分配之后，剩余空間的大

小仍足夠滿足另一需求的機(jī)率，同時(shí)最小化了壓縮的概率。這種方法的缺點(diǎn)是最大存

儲塊最早被分配，因此大空間的要求可能無法滿足。

7.6.如果使用動(dòng)態(tài)分區(qū)方案，下圖所示為在某個(gè)給定的時(shí)間點(diǎn)的內(nèi)存配置：

陰影部分為已經(jīng)被分配的塊;空白部分為空閑塊。接下來的三個(gè)內(nèi)存需求分別為40MB,

20MB和10MB。分別使用如下幾種放置算法，指出給這三個(gè)需求分配的塊的起始地址。

a.首次適配

b.最佳適配

c.臨近適配（假設(shè)最近添加的塊位于內(nèi)存的開始）

d.最壞適配

答：

a.40M的塊放入第2個(gè)洞中，起始地址足80M.20M的塊放入第一個(gè)洞中.起始地址足

d.40M,20M,10M,的起始地址是80M,230M,360M.

7.7.使用伙伴系統(tǒng)分配一個(gè)1MB的存儲塊。

a.利用類似于圖7.6的圖來說明按下列順序請求和返回的結(jié)果：請求70；請求35；

請求80；返回A；請求60；返回B；返回D；返回C。

b.給出返回B之后的二叉樹表示。

答：

Request70A128256512

Request35AB64256512

Request80ABC128512

ReturnA128B64c128512

Request60128B1)d128512

ReturnB12864Dc128512

ReturnP256c128512

ReturnCW24

b.

12864DC128512

7.8.考慮一個(gè)伙伴系統(tǒng)，在當(dāng)前分配下的一個(gè)特定塊地址為011011110000.

a.如果塊大小為4,它的伙伴的二進(jìn)制地址為多少？

b.如果塊大小為16,它的伙伴的二進(jìn)制地址為多少？

答：

a.011011110100

b.011011100000

7.9.令buddyk(x)為大小為2卜、地址為x的塊的伙伴的地址，寫出buddyKx)的通用表達(dá)式。

答：

.V+2Aif.vmod2-1=0

buddy/)

,v-2*if.tmod=2"

7.10.Fabonacci序列定義如下：

Fo=O,Fi=l,F*Fn”+Fn,nMO

a.這個(gè)序列可以用于建立伙伴系統(tǒng)嗎？

b.該伙伴系統(tǒng)與本章介紹的二叉伙伴系統(tǒng)相比，有什么優(yōu)點(diǎn)?

答：

a.是。字區(qū)大小可以確定Fn=Fn-1+Fn-2.。

b.這種策略能夠比二叉伙伴系統(tǒng)提供更多不同大小的塊，因而具有減少內(nèi)部碎片的可

能性。但由于創(chuàng)建了許多沒用的小塊，會(huì)造成更多的外部碎片。

7.11.在程序執(zhí)行期間，每次取指令后處理器把指令寄存器的內(nèi)容（程序計(jì)數(shù)器）增加一個(gè)

字，但如果遇到會(huì)導(dǎo)致在程序中其他地址繼續(xù)執(zhí)行的轉(zhuǎn)跳或調(diào)用指令，處理器將修改

這個(gè)寄存器的內(nèi)容?，F(xiàn)在考慮圖7.8。關(guān)于指令地址有兩種選擇：

?在指令寄存器中保存相對地址，并把指令寄存器作為輸入進(jìn)行動(dòng)態(tài)地址轉(zhuǎn)換。當(dāng)

遇到一次成功的轉(zhuǎn)跳或調(diào)用時(shí)，由這個(gè)轉(zhuǎn)跳或調(diào)用產(chǎn)生的相對地址被裝入到指令

寄存器中。

?在指令寄存器中保存絕對地址。當(dāng)遇到一次成功的轉(zhuǎn)跳或調(diào)用時(shí)，采用動(dòng)態(tài)地址

轉(zhuǎn)換，其結(jié)果保存到指令寄存器中。

哪種方法更好？

答：使用絕對地址可以減少動(dòng)態(tài)地址轉(zhuǎn)換的次數(shù)。但是，我們希望程序能夠被重定位。

因此，在指令寄存器中保存相對地址似乎就更好一些。也可以選擇在進(jìn)程被換出主存

時(shí)將指令寄存器中的地址轉(zhuǎn)換為相對地址。

7.12.考慮一個(gè)簡單分頁系統(tǒng)，其物理存儲器大小為2弘字節(jié)，頁大小為潭字節(jié)，邏輯地址

空間為*個(gè)頁。

a.邏輯地址空間包含多少位？

b.一個(gè)幀中包含多少字節(jié)？

c.在物理地址中指定幀需要多少位？

d.在頁表中包含多少個(gè)頁表項(xiàng)？

e.在每個(gè)頁表項(xiàng)中包含多少位？（假設(shè)每個(gè)頁表項(xiàng)中包含一個(gè)有效/無效位）

答：

a.物理地址空間的比特?cái)?shù)是**2嗎2%

b.一個(gè)幀包含的字節(jié)跟一個(gè)頁是一樣的,2州比特.

c.主存中幀的數(shù)量是237210=222,所以每個(gè)幀的定位要22個(gè)比特

d.在物理地址空間:每個(gè)頁都有一個(gè)頁表項(xiàng),所以有2咐項(xiàng)

e.加上有效/無效位，每個(gè)頁表項(xiàng)包含23位。

7.13.分頁系統(tǒng)中的虛地址a相當(dāng)于一對（p,w）,其中p是頁號，w是頁中的字節(jié)號。令z

是一頁中的字節(jié)總數(shù)，請給出p和w關(guān)于z和a的函數(shù)。

答：關(guān)系是：a=pz+w,其中p=l_a/zj,a/z的整數(shù)部分。w=Rz（a）,a除

以z的余數(shù)

7.14.在一個(gè)簡單分段系統(tǒng)中，包含如下段表：

起始地址長度（字節(jié)）

660248

1752442

222198

996604

對如下的每一個(gè)邏輯地址，確定其對應(yīng)的物理地址或者說明段錯(cuò)誤是否會(huì)發(fā)生:

a.0,198

b.