操作系統(tǒng)第五版1-12章課后題中文答案

生習題：

1.1、列出并簡要地定義計算機的四個主要組成部分。

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

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

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

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

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

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

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

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

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

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

答：這些動作分為四類：處理器一寄存器：數(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,存儲微）中斷處理器正常處理過程的機制。

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

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

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

處理器的運行。

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

答：存儲器的三個重要特性是：價格，容量和訪問時間。

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

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

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

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

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

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

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

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

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

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

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

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

理器）只有當整個數(shù)據(jù)塊傳送完畢后才會被中斷。

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

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

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

次訪問。

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

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

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

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

2.1操作系統(tǒng)設(shè)計的三個目標是什么？

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

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

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

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

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

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

響應進程調(diào)度和設(shè)備中斷。

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

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

程。

2.4什么是進程？

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

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

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

據(jù)。這種內(nèi)部信息和進程是分開的，因為操作系統(tǒng)信息不允許被進程直接訪

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

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

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

成。

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

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

間。

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

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

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

P5I

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

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

存中。實地址指的是主存中的地址。

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

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

循序依次激活。因為等待一些事件（例如：等待一個子進程或一個I/O操作）

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

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

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

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

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

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

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

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

2.1（）什么是多線程？

多線程技術(shù)是指把執(zhí)行一個應用程序的進程劃分成可以同時運行的多個線

程。

3.1什么是指令跟蹤？

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

3.2通常那些事件會導致創(chuàng)建一個進程？

答：新的批處理作業(yè)；交互登錄；操作系統(tǒng)因為提供一項服務而創(chuàng)建；由現(xiàn)有的進程

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

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

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

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

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

退出態(tài)：操作系統(tǒng)從可執(zhí)行進程組中釋放出的進程，或者是因為它自身停

止了，或者是因為某種原因被取消。

3.4搶占一個進程是什么意思？

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

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

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

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

另一個進程可以進入主存執(zhí)行。

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

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

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

3.7列出掛起態(tài)進程的4個特點。

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

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

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

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

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

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

3.9列出進程控制塊中的三類信息。

答：進程標識，處理器狀態(tài)信息，進程控制信息。

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

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

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

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

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

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

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

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

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

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

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

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

每個處理部件都是一個獨立的計算機。

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

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

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

服務和功能。(P126)

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

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

答：一致接口:進程不需要區(qū)分是內(nèi)核級服務還是用戶級服務，因為所有服務都是通過

消息傳遞提供的。可擴展性：允許增加新的服務以及在同一個功能區(qū)域中提供多個赧務。

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

更有效的實現(xiàn)。可移植性：所有或者至少大部分處理器專用代碼都在微內(nèi)核中。因此，

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

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

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

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

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

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

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

要多。(pl27)

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

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

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

答：消息。

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

答：進程間的交互，共享資源之間的競爭，多個進程的同步問題，對進程的處理器時間分配

問題(pl44)

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

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

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

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

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

答：進程間互相不知道對方：這是一些獨立的進程，他們不會一起工作。進程間間接知道對

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

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

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

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

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

進行合作。

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

答：互斥：競爭進程僅可以訪問一個臨界資源（一次僅有一個進程可以訪問臨界資源;，并

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

一的訪問多于一個資源，并且當一個進程控制著一個進程，且在等待另一個進程，死鎖可能

發(fā)生。饑餓：一組進程的一個可能會無限期地拒絕進入到一個需要資源，因為其他成員組成

壟斷這個資源。

5.7列出對互斥的要求。

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

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

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

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

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

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

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

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

塞的進程被解除阻塞。

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

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

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

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

此規(guī)則。

5.11.什么是管程。

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

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

答：p169

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

答：1.任意多的讀進程可以同時讀這個文件，2.一次只有一個寫進程可以往文件中寫，3.如

果一個寫進程正在往文件中寫時，則禁止任何讀進程讀文件。

第六章習題翻譯

第一部分復習題

6.1給出可重用資源和可消費資源的例子。

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

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

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

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

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

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

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

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

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

求都同時滿足。

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

答：第一種，如果占有某些資源的一個進程進行進一步資源請求被拒絕，則該進

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

第二種，如果一個進程請求當前被另一個進程占有的一個資源，則操作系

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

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

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

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

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

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

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

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

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

第二部分習題

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

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

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

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

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

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

描述。

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

能夠獲得兩個資源。

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

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

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

B和A.當P重新開始行的時候，它將會能夠獲得Bo

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

B.P獲得B然后釋放Bo

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

B。當Q重新開始執(zhí)行的時候，，它將會能夠獲得兩個資源。

6.P獲得A而且釋放A然后獲得并且釋放B.當Q重新開始實行，它將會能

夠獲得兩個資源。

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

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

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

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

A能進行。

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

可用

rlr2r3r4

100

2

當前分配最大需求

仍然需求

a計算每個進程仍然可能需要的資源，并填入標為“仍然需要”的列中。

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

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

d哪個進程（如果存在）是死鎖的或可能變成死鎖的？

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

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

同意全部請求，哪個進程（如果有）是死鎖的或可能變成死鎖的？

解：a.0000

0750

6622

2002

rlrlr2

r2r3r4r3r4rlr2r3r4

01

001202

20002750

6

0034656

4

2354356

03320652

0320

b.系統(tǒng)當前處于安全狀態(tài)，因為至少有一個進程執(zhí)行序列，不會導致死鎖，

運行順序是pl,p4,p5,p2,p3.

c.系統(tǒng)當前并沒有死鎖，因為Pl進程當前分配與最大需求正好相等，F(xiàn)1進

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

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

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

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

6.5請把6.4中的死鎖檢測算法應用于下面的數(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一個假脫機系統(tǒng)包含一個輸入進程I,用戶進程進程P和一個輸出進程0,

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

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

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

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

輸出塊數(shù)目。

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

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

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

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

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

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

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

進程等待磁盤空間輸入，二者死鎖。

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

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

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

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

I+OWmax

IWmax-reso

當0<reso<max

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

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

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

輸入可以被P處理完，而且對應的輸出將會被0處理，

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

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

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

進程速度。磁鼓的當前狀態(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è)計系統(tǒng)中，一頁可以進行下列狀態(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如果維持習題6.6中關(guān)于輸入進程，用戶進程和輸出進程的假設(shè)，它們中的任

何一個轉(zhuǎn)換是否會導致死鎖。

解：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é)下列各項：

6.過程返回能立刻發(fā)生因為他們只釋放

資源。

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

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

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

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

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

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

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

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

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

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

進程最大占用

17045

26040

36015

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

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

a.第4個進程到達，最多需要60個存儲單元，最初需要25個單元。

b第4個進程到達，最多需要60個存儲單元，最初需要35個單元。

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

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

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

結(jié)果分配見表

進程最大占有需要空閑

170452515

2604020

3601545

4603525

6.11評價獨家算法在實際應用中是否有用。

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

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

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

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

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

為進程Pi(OWiWn-1)寫一個算法。

Repeat

從前驅(qū)接收

消耗

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

Forever

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

上操作，而無需復制。

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

解：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

因為

(available(0)=0)AND

(available(1)0)AND

(available(n-1)=0)

但是如果max>0,這個條件不成立，因為臨界域滿足

claim{l)+claimk,2,+…

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

=max

6.13a.3個進程共享4個資源單元，一次只能保留或釋放一個單元。每個

進程最大需要2個單元。說明不會死鎖。

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

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

解：a.說明由于每個進程最多需要2個資源，最壞情況下，每個進程需要獲得一

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

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

b.假定每個進程最多申請X個資源，最壞情況下，每個進程都得到XT個資

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

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

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

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

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

6.14考慮一個由四個進程和一個單獨資源組成的系統(tǒng)，當前的聲明和分

配矩陣是

3'1

21

C=9A=3

72

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

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

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

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

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

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

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

評價解釋死鎖的不同方法使用的一個標準是，哪種方法允許最大的并發(fā)。換

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

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

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

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

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

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

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

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

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

的資源，在死鎖發(fā)生之前，這些運算法則都不會限制并發(fā)，因為他們仰賴運行時

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

允許許多并發(fā)(在一些情形，他們增加它)，但是很難有準確的估計。第三個運

算法則是最奇怪的，因為如此后許多的它的并發(fā)將會是無用的重復；因為線程

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

序被列出兩次。

2.銀行家的運算法則

資源排序

這些運算法則因為限制多種的可允許的計算，而相對早先兩種法則會引起更多的

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

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

3.事先保留所有的資源

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

缺點。因為要預先保留所有的資源,線程必須等候比較長的而且當他們工作的時

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

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

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

定義。

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

1.預先保留所有的資源

資源排序

因為他們沒有包括運行時間經(jīng)常開支，所以這些運算法則最有效率。

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

2.銀行家的運算法則

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

這些運算法則在概略的配置上包括運行時間檢查

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

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

數(shù)目限制。

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

這一個運算法則運行也需要運行上述的相同的時間檢查。

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

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

這一個運算法則是非常無效率，有如下兩個理由。首先，因為線程有重新開始

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

時間，因此整個系統(tǒng)運行的速度很慢。

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

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

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

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

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

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

一類總是先拿起右邊的叉子(右撇子)。左撇子的行為和圖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如果至少有一個左撇子或右撇子，則他們的任何就座安排都可以避免死

鎖。

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

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

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

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

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

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

b

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

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

是右撇子，

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

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

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

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

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

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

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

6.18圖1.17顯示了另外一個使用管程解決哲學家就餐問題的方法。和圖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的一些原子操作不會涉及到對同一變量的兩次訪

問。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是讀著寫者鎖。這段代碼的作用是什么？

解：因為寫者鎖將會自旋，所以這段代碼會導致死鎖，等待所有的

讀者解鎖，包括喚醒這個線程。

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

線線程

程12

a=3；一

mb()；—

一C=b；

一rmb()；

d=a；

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

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

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

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

合適的次序被讀。

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

復習題：

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

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

7.2.為什么需要重定位進程的能力?

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

此外還希望通過提供一個巨大的就緒進程池，能夠把活動進程換入和換出主存，以便

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

越來越多的碎片的。

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

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

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

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

中的實際位置。

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

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

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

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

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

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

習題：

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

的。

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

保護比保護和訪問控制以及進程隔離；

共享七保護和訪問控制；

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

物理組織心長期存儲及自動分配和管理.

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

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

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

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

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

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

率是0.5,因為刪除一個斷和添加一個斷的概率是一樣的.假設(shè)s是內(nèi)存中斷的個數(shù)那

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

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

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

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

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

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

7.5.動態(tài)分區(qū)的另一種放置算法是最壞適配，在這種情況下，當調(diào)入一個進程時，使用最

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

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

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

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

小仍足夠滿足另一需求的機率，同時最小化了壓縮的概率。這種方法的缺點是最大存

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

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

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

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

a.首次適配

b.最佳適配

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

d.最壞適配

答：

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

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

7.7.使用伙伴系統(tǒng)分配一個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.考慮一個伙伴系統(tǒng)，在當前分配下的一個特定塊地址為011011110000.

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

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

答：

a.011011110100

b.011011100000

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

答：

.V+2Aif.vmod2-1=0

buddy/)

,v-2*if.tmod=2"

7.10.Fabonacci序列定義如下：

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

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

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

答：

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

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

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

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

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

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

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

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

寄存器中。

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

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

哪種方法更好？

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

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

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

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

空間為*個頁。

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

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

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

d.在頁表中包含多少個頁表項？

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

答：

a.物理地址空間的比特數(shù)是**2嗎2%

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

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

d.在物理地址空間:每個頁都有一個頁表項,所以有2咐項

e.加上有效/無效位，每個頁表項包含23位。

7.13.分頁系統(tǒng)中的虛地址a相當于一對（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.在一個簡單分段系統(tǒng)中，包含如下段表：

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

660248

1752442

222198

996604

對如下的每一個邏輯地址，確定其對應的物理地址或者說明段錯誤是否會發(fā)生:

a.0,198

b.