南京郵電大學(xué)操作技巧系統(tǒng)課后習(xí)題集標(biāo)準(zhǔn)答案

《操作系統(tǒng)教程》南郵正式版

習(xí)題解答

第三章進(jìn)程管理與調(diào)度習(xí)題

1、什么是多道程序設(shè)計(jì)？多道程序設(shè)計(jì)利用了系統(tǒng)與外圍設(shè)備的并行工作能力，從而提高

工作效率，具體表現(xiàn)在哪些方面？

答：

讓多個(gè)計(jì)算問題同時(shí)裝入一個(gè)計(jì)算機(jī)系統(tǒng)的主存儲(chǔ)器并行執(zhí)行，這種設(shè)計(jì)技術(shù)稱“多道程序

設(shè)計(jì)”，這種計(jì)算機(jī)系統(tǒng)稱“多道程序設(shè)計(jì)系統(tǒng)”或簡(jiǎn)稱“多道系統(tǒng)”。在多道程序設(shè)計(jì)的系

統(tǒng)中，主存儲(chǔ)器中同時(shí)存放了多個(gè)作業(yè)的程序。為避免相互干擾，必須提供必要的手段使得

在主存儲(chǔ)器中的各道程序只能訪問自己的區(qū)域。

提高工作效率，具體表現(xiàn)在：

?提高了處理器的利用率；

?充分利用外圍設(shè)備資源：計(jì)算機(jī)系統(tǒng)配置多種外圍設(shè)備，采用多道程序設(shè)計(jì)并行工

作時(shí)，可以將使用不同設(shè)備的程序搭配在一起同時(shí)裝入主存儲(chǔ)器，使得系統(tǒng)中各外

圍設(shè)備經(jīng)常處于忙碌狀態(tài)，系統(tǒng)資源被充分利用；

?發(fā)揮了處理器與外圍設(shè)備以及外圍設(shè)備之間的并行工作能力；

從總體上說，采用多道程序設(shè)計(jì)技術(shù)后，可以有效地提高系統(tǒng)中資源的利用率，增加單位時(shí)

間內(nèi)的算題量，從而提高了吞吐率。

2、請(qǐng)描述進(jìn)程的定義和屬性。

答：

進(jìn)程是具有獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合上的一次運(yùn)行活動(dòng)，是系統(tǒng)進(jìn)行資源分配、調(diào)

度和保護(hù)的獨(dú)立單位。

進(jìn)程的屬性有：結(jié)構(gòu)性?共享性?動(dòng)態(tài)性?獨(dú)立性?制約性?并發(fā)性

3、請(qǐng)描述進(jìn)程與程序的區(qū)別及關(guān)系。

答：

程序是靜止的，進(jìn)程是動(dòng)態(tài)的。進(jìn)程包括程序和程序處理的對(duì)象(數(shù)據(jù)集)，進(jìn)程能得到程

序處理的結(jié)果。進(jìn)程和程序并非一一對(duì)應(yīng)的，一個(gè)程序運(yùn)行在不同的數(shù)據(jù)集上就構(gòu)成了不同

的進(jìn)程。通常把進(jìn)程分為“系統(tǒng)進(jìn)程”和“用戶進(jìn)程”兩大類，把完成操作系統(tǒng)功能的進(jìn)程稱為

系統(tǒng)進(jìn)程，而完成用戶功能的進(jìn)程則稱為用戶進(jìn)程。

4、進(jìn)程有哪三種基本狀態(tài)？三種進(jìn)程狀態(tài)如何變化？

答：

通常，根據(jù)進(jìn)程執(zhí)行過程中不同時(shí)刻的狀態(tài)，可歸納為三種基本狀態(tài)：

?等待態(tài)：等待某個(gè)事件的完成；

?就緒態(tài)：等待系統(tǒng)分配處理器以便運(yùn)行；

?運(yùn)行態(tài)：占有處理器正在運(yùn)行。

進(jìn)程在執(zhí)行中狀態(tài)會(huì)不斷地改變，每個(gè)進(jìn)程在任何時(shí)刻總是處于上述三種基本狀態(tài)的某一種

基本狀態(tài)，進(jìn)程狀態(tài)之間轉(zhuǎn)換關(guān)系：

運(yùn)行態(tài)一等待態(tài)往往是由于等待外設(shè)，等待主存等資源分配或等待人工干預(yù)而引起的。

等待態(tài)一就緒態(tài)則是等待的條件已滿足，只需分配到處理器后就能運(yùn)行。

運(yùn)行態(tài)T就緒態(tài)不是由于自身原因，而是由外界原因使運(yùn)行狀態(tài)的進(jìn)程讓出處理器，這時(shí)

候就變成就緒態(tài)。例如時(shí)間片用完，或有更高優(yōu)先級(jí)的進(jìn)程來搶占處理器等。

就緒態(tài)一運(yùn)行態(tài)系統(tǒng)按某種策略選中就緒隊(duì)列中的??個(gè)進(jìn)程占用處理器，此時(shí)就變成了運(yùn)

行態(tài)。

5、進(jìn)程控制塊是什么，有何作用？通常進(jìn)程控制塊包含哪些信息？

答：

進(jìn)程控制塊(ProcessConirolBlock,簡(jiǎn)稱PCB),是操作系統(tǒng)為進(jìn)程分配的用于標(biāo)志進(jìn)程，記

錄各進(jìn)程執(zhí)行情況的。進(jìn)程控制塊是進(jìn)程存在的標(biāo)志，它記錄了進(jìn)程從創(chuàng)建到消亡動(dòng)態(tài)變化

的狀況，進(jìn)程隊(duì)列實(shí)際也是進(jìn)程控制塊的鏈接。操作系統(tǒng)利用進(jìn)程控制塊對(duì)進(jìn)程進(jìn)行控制和

管理。

?標(biāo)志信息含唯一的進(jìn)程名

?說明信息有進(jìn)程狀態(tài)、等待原因、進(jìn)程程序存放位置和進(jìn)程數(shù)據(jù)存放位置

?現(xiàn)場(chǎng)信息包括通用、控制和程序狀態(tài)字寄存器的內(nèi)容

?管理信息存放程序優(yōu)先數(shù)和隊(duì)列指針

進(jìn)程控制塊的作用有:

?(1)記錄進(jìn)程的有關(guān)信息，以便操作系統(tǒng)的進(jìn)程調(diào)度程序?qū)M(jìn)程進(jìn)行調(diào)度。這些信息

包括標(biāo)志信息、說明信息、現(xiàn)場(chǎng)信息和管理信息等；

?(2)標(biāo)志進(jìn)程的存在，進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志

6、什么是可再入程序？

答：

(1)什么是可再入程序。一個(gè)能被多個(gè)用戶同時(shí)調(diào)用的程序稱做“可再入”的程序。

(2)可再入程序的性質(zhì)。

?可再入程序必須是純代碼，在執(zhí)行時(shí)自身不改變；

?一個(gè)可再入程序要求調(diào)用者提供工作區(qū)，以保證程序以同樣方式為各用戶服務(wù)。

編譯程序和操作系統(tǒng)程序通常都是“可再入”程序，能同時(shí)被不同用戶調(diào)用而構(gòu)成不同的

進(jìn)程。

7、闡述進(jìn)程調(diào)度的常用算法：先來先服務(wù)、優(yōu)先數(shù)法、輪轉(zhuǎn)法。

答：

?先來先服務(wù)調(diào)度算法該算法按進(jìn)程進(jìn)入就緒隊(duì)列的先后次序選擇可以占用處理器

的進(jìn)程。

?優(yōu)先數(shù)調(diào)度算法對(duì)每個(gè)進(jìn)程確定一個(gè)優(yōu)先數(shù)，該算法總是讓優(yōu)先數(shù)最高的進(jìn)程先使

用處理器。對(duì)具有相同優(yōu)先數(shù)的進(jìn)程，再采用先來先服務(wù)的次序分配處理器。系統(tǒng)

常以任務(wù)的緊迫性和系統(tǒng)效率等因素確定進(jìn)程的優(yōu)先數(shù)。進(jìn)程的優(yōu)先數(shù)可以固定的,

也可隨進(jìn)程執(zhí)行過程動(dòng)態(tài)變化。一個(gè)高優(yōu)先數(shù)的進(jìn)程占用處理器后，系統(tǒng)處理該進(jìn)

程時(shí)有兩種方法，一是“非搶占式”，另一種是“可搶占式”。前者是此進(jìn)程占用處理

器后一直運(yùn)行到結(jié)束，除非本身主動(dòng)讓出處理器，后者則是嚴(yán)格保證任何時(shí)刻總是

讓優(yōu)先數(shù)最高的進(jìn)程在處理器上運(yùn)行。

?時(shí)間片輪轉(zhuǎn)調(diào)度法把規(guī)定進(jìn)程一次使用處理器的最長(zhǎng)時(shí)間稱為“時(shí)間片”。時(shí)間片輪

轉(zhuǎn)調(diào)度算法讓就緒進(jìn)程按就緒的先后次序排成隊(duì)列，每次總選擇該隊(duì)列中第一個(gè)進(jìn)

程占用處理器，但規(guī)定只能使用一個(gè)時(shí)間片，如該進(jìn)程尚未完成，則排入隊(duì)尾，等

待下一個(gè)供它使用的時(shí)間片。各個(gè)進(jìn)程就這樣輪轉(zhuǎn)運(yùn)行。時(shí)間片輪轉(zhuǎn)算法經(jīng)常用于

分時(shí)操作系統(tǒng)中。

8、程序狀態(tài)字包含哪些主要內(nèi)容？

答：

(1)程序基本狀態(tài)

(2)中斷碼

(3)中斷屏蔽位

9、比較進(jìn)程調(diào)度與作業(yè)調(diào)度的不同點(diǎn)。

答：

1)作業(yè)調(diào)度是宏觀調(diào)度，它決定了哪一個(gè)作業(yè)能進(jìn)入主存。進(jìn)程調(diào)度是微觀調(diào)度，它決定

各作業(yè)中的哪一個(gè)進(jìn)程占有中央處理機(jī)。(或)作業(yè)調(diào)度是高級(jí)調(diào)度，它位于操作系統(tǒng)的作

業(yè)管理層次。進(jìn)程調(diào)度是低級(jí)調(diào)度，它位于操作系統(tǒng)分層結(jié)構(gòu)的最內(nèi)層。

(2)作業(yè)調(diào)度是選符合條件的收容態(tài)作業(yè)裝入內(nèi)存。進(jìn)程調(diào)度是從就緒態(tài)進(jìn)程中選一個(gè)占

用處理機(jī)。

10、C程序說明系統(tǒng)調(diào)用fork。的應(yīng)用。請(qǐng)?jiān)冖貮③④處填入有關(guān)父、子進(jìn)程的正確語句：

/*ExampletodemonstratethefunctionofSystemCallfork*/

main()

{

inti；

①

if(i)>0

(

printf("②”)；

)

else{

printf(“③”)；

)

printf(u@n)；

)

執(zhí)行本程序時(shí)，子進(jìn)程在標(biāo)準(zhǔn)輸出上打印以下結(jié)果：

Itischildprocess.

Exit.

父進(jìn)程在標(biāo)準(zhǔn)輸出上打印以下結(jié)果：

ItisParentprocess.

Exit.

11、單道批處理環(huán)境下有5個(gè)作業(yè)，各作業(yè)進(jìn)入系統(tǒng)的時(shí)間和估計(jì)運(yùn)行時(shí)間如下表所示:

作業(yè)進(jìn)入系統(tǒng)時(shí)間估計(jì)運(yùn)行時(shí)間/分鐘

18:0040

28:2030

38:3012

49:0018

59:105

(1)如果應(yīng)用先來先服務(wù)的作業(yè)調(diào)度算法，試將下面表格填寫完整。

作業(yè)進(jìn)入系統(tǒng)時(shí)間估計(jì)運(yùn)行時(shí)間/分鐘開始時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間/分鐘

18:0040

28:2030

38:3012

49:0018

59:105

作業(yè)平均周轉(zhuǎn)時(shí)間T=

(2)如果應(yīng)用最短作業(yè)優(yōu)先的作業(yè)調(diào)度算法，試將下面表格填寫完整。

作業(yè)進(jìn)入系統(tǒng)時(shí)間估計(jì)運(yùn)行時(shí)間/分鐘開始時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間/分鐘

18:0040

28:2030

38:3012

49:0018

59:105

作業(yè)平均周轉(zhuǎn)時(shí)間T=

答：

1.(1)

作業(yè)進(jìn)入系統(tǒng)時(shí)間估計(jì)運(yùn)行時(shí)間/分鐘開始時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間/分鐘

18:00408：008：4040

28:20308：409：1050

38:30129：109：2252

49:00189；229：4040

59:1059：409：4535

作業(yè)平均周轉(zhuǎn)時(shí)間T=43.4217

(2)

作業(yè)進(jìn)入系統(tǒng)時(shí)間估計(jì)運(yùn)行時(shí)間/分鐘開始時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間/分鐘

18:00408：008：4040

28:20308：529：2262

38:30128：408：5222

49:00189：279：4545

59:1059：229：2717

作業(yè)平均周轉(zhuǎn)時(shí)間T:37.2186

12、有一個(gè)具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的非搶式調(diào)度算法，進(jìn)

程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列中，作業(yè)優(yōu)先數(shù)即為

進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級(jí)越高。

作業(yè)名到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間優(yōu)先數(shù)

A10：0040分5

B10：2030分3

C10：3050分4

D10：5020分6

（1）列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。

（2）計(jì)算平均周轉(zhuǎn)時(shí)間。

答：

每個(gè)作業(yè)運(yùn)行將經(jīng)過兩個(gè)階段：作業(yè)調(diào)度（SJF算法）和進(jìn)程調(diào)度（優(yōu)先數(shù)搶占式）。另

外，批處理最多容納2道作業(yè)，更多的作業(yè)將在后備隊(duì)列等待。

時(shí)間（分鐘）10:0010:2010:3010:5012:Q012：2。

：ABACD

CPU!-------

進(jìn)程就緒隊(duì)列11AlD?D?

1c?

作業(yè)后備隊(duì)列

(1)10:00,作業(yè)A到達(dá)并投入運(yùn)行。

(2)10:20,作業(yè)B到達(dá)且優(yōu)先權(quán)高于作業(yè)A,故作業(yè)B投入運(yùn)行而作業(yè)A在就緒隊(duì)

列等待。

(3)10:30,作業(yè)C到達(dá)，因內(nèi)存中已有兩道作業(yè)，故作業(yè)C進(jìn)入作業(yè)后備隊(duì)列等待。

(4)10:50,作業(yè)B運(yùn)行結(jié)束，作業(yè)D到達(dá)，按SJF短作業(yè)優(yōu)先算法，作業(yè)D被裝入

內(nèi)存進(jìn)入就緒隊(duì)列。而白于作業(yè)A的優(yōu)先級(jí)高于作業(yè)D,故作業(yè)A投入運(yùn)行。

(5)11:10,作業(yè)A運(yùn)行結(jié)束，作業(yè)C被調(diào)入內(nèi)存，且作業(yè)C的優(yōu)先級(jí)高于作業(yè)D,

故作業(yè)C投入運(yùn)行。

(6)12:00,作業(yè)C運(yùn)行結(jié)束，作業(yè)D投入運(yùn)行。

(7)12:20,作業(yè)D運(yùn)行結(jié)束。

作業(yè)進(jìn)入內(nèi)存時(shí)間運(yùn)行結(jié)束時(shí)間

A10:0011:10

B10:2010:50

C11:1012:00

D10:5012:20

各作業(yè)周轉(zhuǎn)時(shí)間為：作業(yè)A70,作業(yè)B30,作業(yè)C90,作業(yè)D90。平均作業(yè)周

轉(zhuǎn)時(shí)間為70分鐘。

第四章并發(fā)進(jìn)程的同步與互斥

1、進(jìn)程間同步和互斥的含義是什么？

答：

同步：并發(fā)進(jìn)程之間存在的相互制約和相互依賴的關(guān)系。

互斥：若干進(jìn)程共享一資源時(shí)，任何時(shí)刻只允許一個(gè)進(jìn)程使用。

2、用文字描述銀行家算法的基本思想？

答：

銀行家算法的基本思想是：將系統(tǒng)中的所有資源比做銀行家的資金，每進(jìn)行

一次資源的分配，銀行家都要從當(dāng)前的資源分配情況出發(fā)，計(jì)算這種分配方案的

安全性，如果是安全的，則進(jìn)行分配，否則選擇其它可能的分配方案。這樣，每

次分配都計(jì)算安全性,從而可以避免死鎖的發(fā)生c

3、簡(jiǎn)述死鎖的防止與死鎖的避免的區(qū)別。

答：

死鎖的防止是系統(tǒng)預(yù)先確定一些資源分配策略，進(jìn)程按規(guī)定申請(qǐng)資源，系統(tǒng)按預(yù)先規(guī)定的策

略進(jìn)行分配，從而防止死鎖的發(fā)生。

而死鎖的避免是當(dāng)進(jìn)程提出資源申請(qǐng)時(shí)系統(tǒng)測(cè)試資源分配，僅當(dāng)能確保系統(tǒng)安全時(shí)才把資源

分配給進(jìn)程，使系統(tǒng)一直處于安全狀態(tài)之中，從而避免死鎖。

4、試說明資源的靜態(tài)分配策略能防止死鎖的原因。

答：

資源靜態(tài)分配策略要求每個(gè)進(jìn)程在開始執(zhí)行前申請(qǐng)所需的全部資源，僅在系統(tǒng)為之分配了所

需的全部資源后，該進(jìn)程才開始執(zhí)行。這樣，進(jìn)程在執(zhí)行過程中不再申請(qǐng)資源，從而破壞了

死鎖的四個(gè)必要條件之一”占有并等待條件“，從而防止死鎖的發(fā)生。

5、有三個(gè)進(jìn)程Pl,P2和P3并發(fā)工作。進(jìn)程P1需用資源S3和S1；進(jìn)程P2需用資源S1

和S2；進(jìn)程P3需用資源S2和S3?；卮穑?/p>

(1)若對(duì)資源分配不加限制，會(huì)發(fā)生什么情況?為什么？

(2)為保證進(jìn)程正確工作，應(yīng)采用怎樣的資源分配策略?為什么？

答：

.(1)可能會(huì)發(fā)生死鎖

例如：進(jìn)程Pl,P2和P3分別獲得資源S3,S1和S2后再繼續(xù)申請(qǐng)資源時(shí)都要等待(2

分)，這是循環(huán)等待。

(或進(jìn)程在等待新源時(shí)均不釋放已占資源)

(2)可有幾種答案：

A.采用靜態(tài)分配由于執(zhí)行前已獲得所需的全部資源，故不會(huì)出現(xiàn)占有資源又等待別的

資源的現(xiàn)象(或不會(huì)出現(xiàn)循環(huán)等待資源現(xiàn)象)。

或B.采用按序分配不會(huì)出現(xiàn)循環(huán)等待資源現(xiàn)象。

或C.采用銀行家算法因?yàn)樵诜峙鋾r(shí)，保證了系統(tǒng)處于安全狀態(tài)。

6、某車站售票廳，任何時(shí)刻最多可容納20名購票者進(jìn)入，當(dāng)售票廳中少于20名購票者時(shí)，

則廳外的購票者可立即進(jìn)入，否則需在外面等待。若把一個(gè)購票者看作一個(gè)進(jìn)程，請(qǐng)回答下

歹U問題：

(1)用PV操作管理這些并發(fā)進(jìn)程時(shí)，應(yīng)怎樣定義信號(hào)量，寫出信號(hào)量的初值以及信號(hào)量

各種取值的含義。

(2)根據(jù)所定義的信號(hào)量，把應(yīng)執(zhí)行的PV操作填入適當(dāng)，以保證進(jìn)程能夠正確地并發(fā)執(zhí)

行。

COBEGINPROCESSPI(I=1.2,……)

begin；

進(jìn)入售票廳；

購票；

退出；

end；

COEND

(3)若欲購票者最多為n個(gè)人，寫出信號(hào)量可能的變化范圍(最大值和最小值)。

答：

.(1)定義一信號(hào)量S,初始值為20。

意義：

SX)S的值表示可繼續(xù)進(jìn)入售票廳的人數(shù)

S=0表示售票廳中已有20名顧客(購票者)

S<0|S|的值為等待進(jìn)入售票廳的人數(shù)

(2)P(S)

進(jìn)入售票廳;

購票；

退出；

V（s）

（3）S的最大值為20

S的最小值為20-n

注：信號(hào)量的符號(hào)可不同（如寫成I），但使用時(shí)應(yīng)一致（即上述的s全應(yīng)改成I）。

7、假定系統(tǒng)有三個(gè)并發(fā)進(jìn)程read,move和print共享緩沖器Bl和B2。進(jìn)程read負(fù)責(zé)從輸

入設(shè)備上讀信息，每讀出一個(gè)記錄后把它存放到緩沖器B1中。進(jìn)程move從緩沖器B1中

取出一記錄，加工后存入緩沖器B2O進(jìn)程print將B2中的記錄取出打印輸出。緩沖器B1

和B2每次只能存放一個(gè)記錄。要求三個(gè)進(jìn)程協(xié)調(diào)完成任務(wù)，使打印出來的與讀入的記錄的

個(gè)數(shù)，次序完全一樣。

請(qǐng)用PV操作，寫出它們的并發(fā)程序。

答：

beginSR,SM1,SM2,SP:semaphore;

Bl,B2:record;

SR:=1;SMl:=0;SM2:=1;SP:=O

cobcgin

processread

X:record;

beginR:（接收來自輸入設(shè)備上一個(gè)記錄）

X尸接收的一個(gè)記錄；

P（SR）：

B1:=X;

V（SM1）;

gotoR;

end;

Processmove

Y:record;

begin

M:P(SM1);

Y:=B1;

V(SR)

加工Y

P(SM2)；

B2:=Y;

V(SP);

gotoM;

end;

Processprint

Z:record;

begin

P:P(SP);

Z:=B2;

V(SM2)

打印Z

gotoP;

end;

coend;

end;

8、某系統(tǒng)中有1。臺(tái)打印機(jī)，有三個(gè)進(jìn)程Pi，P2，P3分別需要8臺(tái)，7臺(tái)和4臺(tái)。若匕，

P2,P3已申請(qǐng)到4臺(tái)，2臺(tái)和2臺(tái)。試問：按銀行家算法能安全分配嗎？請(qǐng)說明分配過程。

答：

系統(tǒng)能為進(jìn)程P3分配二臺(tái)打印機(jī)。因?yàn)楸M管此時(shí)10臺(tái)打印機(jī)己分配給進(jìn)程P14臺(tái)，P22

臺(tái)和P34臺(tái)，全部分配完，但P3已分配到所需要的全部4臺(tái)打印機(jī)，它不會(huì)對(duì)打印機(jī)再提

出申請(qǐng)，所以它能順利運(yùn)行下去，能釋放占用的4臺(tái)打印機(jī)，使進(jìn)程Pl,P2均可能獲得乘

余的要求4臺(tái)和5臺(tái)，按銀行家算法是安全的。

9、有兩個(gè)用戶進(jìn)程A和B,在運(yùn)行過程中都要使用系統(tǒng)中的一臺(tái)打印機(jī)輸出計(jì)算結(jié)果。

(1)試說明A、B兩進(jìn)程之間存在什么樣的制約關(guān)系？

(2)為保證這兩個(gè)進(jìn)程能正確地打印出各自的結(jié)果，請(qǐng)用信號(hào)量和P、V操作寫出各自

的有關(guān)申請(qǐng)、使用打印機(jī)的代碼。要求給出信號(hào)量的含義和初值。

（1）A、B兩進(jìn)程之間存在互斥的制約關(guān)系。因?yàn)榇蛴C(jī)屬于臨界資源，必須一個(gè)進(jìn)程

使用完之后另一個(gè)進(jìn)程才能使用。

（2）mutex：用于互斥的信號(hào)量，初值為1。

進(jìn)程A進(jìn)程B

P(mutex)P（mutex）

申請(qǐng)打印機(jī)申請(qǐng)打印機(jī)

使用打印機(jī)使用打卬機(jī)

V(mutex)V(mutex)

試以生產(chǎn)者一消費(fèi)者問題說明進(jìn)程同步問題的實(shí)質(zhì)。

答：

一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者和一個(gè)產(chǎn)品之間關(guān)系是典型的進(jìn)程同步問題。設(shè)信號(hào)量S為倉庫

內(nèi)產(chǎn)品，P-V操作配對(duì)進(jìn)行缺一不可。生產(chǎn)者進(jìn)程將產(chǎn)品放人倉庫后通知消費(fèi)者可用；消

費(fèi)者進(jìn)程在得知倉庫有產(chǎn)品時(shí)取走，然后告訴生產(chǎn)者可繼續(xù)生產(chǎn)。

10、請(qǐng)描述產(chǎn)生死鎖的四個(gè)必要條件。

答：

互斥使用（資源獨(dú)占）一個(gè)資源每次只能給一個(gè)進(jìn)程使用

不可強(qiáng)占（不可剝奪）資源申請(qǐng)者不能強(qiáng)行的從資源占有者手中奪取資源，資源只能由占有

者自愿釋放

請(qǐng)求和保持（部分分配，占有申請(qǐng)）一一個(gè)進(jìn)程在申請(qǐng)新的資源的同時(shí)保持對(duì)原有資源的占

有（只有這樣才是動(dòng)態(tài)申請(qǐng)，動(dòng)態(tài)分配）

循環(huán)等待一存在一個(gè)進(jìn)程等待隊(duì)列（Pl,P2,...,Pn）,其中Pl等待P2占有的資源,P2等待

P3占有的資源，…，Pn等待P1占有的資源，形成一個(gè)進(jìn)程等待環(huán)路

11、兩個(gè)并發(fā)執(zhí)行的進(jìn)程A和B的程序如下：

進(jìn)程A

N=N+5;

Untilfalse;

進(jìn)程B

Repeat

打印N的值；

N=0；

Untilfalse;

其中N為整數(shù)，初值為4。若進(jìn)程A先執(zhí)行了三個(gè)循環(huán)后，進(jìn)程A和進(jìn)程B又并發(fā)執(zhí)

行了一個(gè)循環(huán)，寫出可能出現(xiàn)的打印值。正確的打印值應(yīng)該是多少？請(qǐng)用P、V操作進(jìn)行管

理，使進(jìn)程A和B并發(fā)執(zhí)行時(shí)不會(huì)出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤。

答：

因?yàn)镹初值為4,若進(jìn)程A先執(zhí)行了三個(gè)循環(huán)，此時(shí)N的值為19。當(dāng)進(jìn)程A和進(jìn)程B并

發(fā)執(zhí)行時(shí)可能會(huì)有如下兩種執(zhí)行次序，即進(jìn)程A先執(zhí)行一次循環(huán)，然后再進(jìn)程B執(zhí)行一次

循環(huán)，此時(shí)打印的是正確值24,執(zhí)行后N中的值為0。但若進(jìn)程B先執(zhí)行一次循環(huán)，然后

再進(jìn)程A執(zhí)行一次循環(huán)，則打印的值是19,執(zhí)行后N中的值是5。這是錯(cuò)誤的，即發(fā)生了

與時(shí)間有關(guān)的錯(cuò)誤。用P、V操作進(jìn)行管理，使進(jìn)程A和B并發(fā)時(shí)不會(huì)出現(xiàn)與時(shí)間有關(guān)的

錯(cuò)誤的程序如下：(S為互斥信號(hào)量，初值為1),

進(jìn)程A

Repeat

P(S);

N=N+5;

V(S);

Untilfalse;

進(jìn)程B

Repeat

P(S);

打印N的值；

N=0；

V(S);

Untilfalse;

12、四個(gè)進(jìn)程PO,P1,P2,P3和四個(gè)信箱MO,Ml,M2,M3進(jìn)程間借助相鄰的信箱傳遞消息：

每次從中取出一條消息，經(jīng)加工送入中。其中MO,Ml,M2,M3分別設(shè)有3,322個(gè)格子,

每個(gè)格子放一條消息，初始時(shí)，M0裝滿了三條消息，其余為空。寫出使用信號(hào)量實(shí)現(xiàn)進(jìn)程

(i=0,l,2,3)同步及互斥的流程。

答：

mutexO~mutex3:分別用于控制互斥訪問MO~M3,初值為1。

fullO-fu113:分別用于控制同步訪問M0~M3,其中full。初值為3,fulll-fu113初值為0,

表示信箱中消息條數(shù)。

emptyO~empty3:分別用于同步控制對(duì)MO~M3的訪問。EmplyO初值為0,empty2-empty3

初值為2,emplyl初值為3,分別用于表示信箱中空格子個(gè)數(shù)。

另用send(Mi,message)表示將消息送到(Mimod4)號(hào)信箱中：而用receive(Mi,message)

表示接收已存在于(Mimod4)中的消息。

則使用信號(hào)量實(shí)現(xiàn)進(jìn)程Pi(i=0,l,2,3)同步及互斥的流程如下：

mutexO,mutex1,mutex2,mutex3:semaphore;

fullO,ful11,ful12,ful13:semaphore;

emptyO,empty1,empty2,empty3:semaphore;

begin

mutexO:=1;mutex1:=1;mutex2:=1;mutex:=1;

fullO:=3;fulll:=0;fu112:=0;fu113:=0;

emptyO:=0;empty1:=3;empty2:=2;cmpty3:=2;

Parbegin

P0：begin

repeat

P(mutexO);

P(fullO);

Receive(MO,message);

V(emptyO);

Processingthemessageuntilfinished;

P(mutex1);

P(empty1);

Send(M1,message);

V(fulll);

V（mutex1）;

Untilfalse;

end;

Pl：｛可類似于PO實(shí)現(xiàn)之）；

P2：｛可類似于PO實(shí)現(xiàn)之）；

P3：｛可類似于P0實(shí)現(xiàn)之）;

Parend;

End;

13、設(shè)系統(tǒng)中僅有一類數(shù)量為M的獨(dú)占型資源，系統(tǒng)中N個(gè)進(jìn)程競(jìng)爭(zhēng)該類資源，其中各

進(jìn)程對(duì)該類資源的最大需求量為W。當(dāng)M、N、W分別取下列值時(shí)，試判斷哪些情況會(huì)發(fā)

生死鎖？為什么？

①M(fèi)=2,N=2,W=1②M=3,N=2,W=2③M=3,N=2,W=3

@M=5,N=3,W=2⑤M=6,N=3,W=3

答：

③可能會(huì)發(fā)生死鎖。只要一個(gè)進(jìn)程占用了少于3個(gè)獨(dú)占型資源而另一個(gè)進(jìn)程占用了其余的獨(dú)

占型資源，兩個(gè)進(jìn)程都會(huì)相互處于等待對(duì)方進(jìn)程釋放資源的狀態(tài)。

⑤也可能會(huì)發(fā)生死鎖。當(dāng)每個(gè)進(jìn)程都分配了兩個(gè)資源時(shí)，3個(gè)進(jìn)程都會(huì)彼此等待。

14、假定具有5個(gè)進(jìn)程的進(jìn)程集合P=｛P0,PI,P2,P3,P4），系統(tǒng)中有三類資源A,B和C。

其中A類資源有1。個(gè)，B類資源將5個(gè)，C類資源有7個(gè)。假定在某時(shí)刻有如下狀態(tài)：

AllocationMaxAvailable

ABCABCABC

P0010753332

P1200322

P2302902

P32I1222

P4002433

試給出Need,并說明當(dāng)前系統(tǒng)是否處于安全狀態(tài)，如果是，給出安全序列。如果不

是，說明理由。

答:

當(dāng)前系統(tǒng)處于安全狀態(tài)，安全序列如下求解:

work=Available=(3,3,2)

尋找Needj<=work=(3,3,2)(j=0,1,2,3,4)

j=1Nccdl=(1,2,3)<=(3,3,2)

work:=(3,3,2)+(2,0,0)=(5,3,2)

尋找Needj<=work=(5,3,2)(j=0,2,3,4)

j=3Need3=(0,1,1)<=(5,3,2)

work:=(5,3,2)+(2,1,1)=(7,4,3)

尋找Needj<=work=(7,4,3)(j=0,2,4)

j=4Need4=(4,3J)<=(7,4,3)

work:=(7,4,3)+(0,0,2)=(7,4,5)

尋找Needj<=work=(7.4,5)(j=0,2)

j=2Need2=(6,0,0)<=(7,4,5)

work:=(7,4,5)+(3,0,2)=(10,4,7)

尋找Needj<=work=(Id,4,7)(j=0)

j=0work:=(10,4,7)+(0J,0)=(10,5,7)

所以安全序列為VP1,P3,P4,P2,P0>o

15、有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上登記。該表中每個(gè)表項(xiàng)代表閱覽室中

的一個(gè)座位。讀者離開時(shí)要消掉其登記信息。閱覽室共有50個(gè)座位。登記表每次僅允許一

位讀者進(jìn)行登記或注銷。讀者登記時(shí)，發(fā)現(xiàn)登記表滿，他在閱覽室外等待，直至有空位再登

記進(jìn)入。試用類Pascal語言和P、V操作，描述讀者行為。

答：

Begin{initialvalueofSis50)

Parbegin

Begin{register}

P(S);

Registerandenterintothereadingroom;

End;

Begin{leaveoff}

Registeroffandleave;

V(S);

End;

End;

16、考慮一個(gè)共有150個(gè)存儲(chǔ)單元的系統(tǒng)，如下分配給三個(gè)進(jìn)程.Pl最大需求70,己占

有25；P2最大需求60,己占有40；P3最大需求60,己占有45。使月銀行家算法，以確定

下面的任何一個(gè)請(qǐng)求是否安全。（1）P4進(jìn)程到達(dá)，P4最大需求60,最初請(qǐng)求25個(gè)。（2）P4

進(jìn)程到達(dá)，P4最大需求60,最初請(qǐng)求35。如果安全，找出所有的安全序列；如果不安全，

給出結(jié)果分配情況。

答：

（1）由于系統(tǒng)目前還有150-25*40-45=40個(gè)單元，P4進(jìn)程到達(dá)，把25個(gè)單元分給它。這

時(shí)系統(tǒng)還余15個(gè)單元，可把15個(gè)單元分給P3,它執(zhí)行完后會(huì)釋放60個(gè)單元。于

是可供P1（還要45個(gè)單元），P2（還要20個(gè)單元），P4（還要35個(gè)單元）任何一個(gè)執(zhí)行。

安全序列為:

P1,P2,P3,P4,P3,Pl,P2,P4

P2,P3,P4,P3,Pl,P4,P2

P1,P2,P3,P4,P3,P2,P1,

PI,P2,P3,P4,P3,P2,P4,P1

PI,P2,P3,P4,P3,P4,Pl,P2

Fl,P2,P3,P4,P3,E4,P2,E1

（2）P4進(jìn)程到達(dá)，P4最大需求60,最初請(qǐng)求35。如果把35個(gè)單元分給P4,系統(tǒng)還余5

個(gè)單元，不再能滿足任何一個(gè)進(jìn)程的需求，系統(tǒng)進(jìn)入不安全狀態(tài)。

17、在一個(gè)盒子里，混裝了數(shù)量相等的黑白圍棋子。現(xiàn)在用自動(dòng)分揀系統(tǒng)把黑子、白子分

開，設(shè)分揀系統(tǒng)有二個(gè)進(jìn)程P1和P2,其中P1揀白子：P2揀黑子。規(guī)定每個(gè)進(jìn)程每次揀一

子；當(dāng)一個(gè)進(jìn)程在揀時(shí)，不允許另一個(gè)進(jìn)程去揀；當(dāng)一個(gè)進(jìn)程揀了一子時(shí)，必須讓另一個(gè)進(jìn)

程去揀。試寫出兩進(jìn)程P1和P2能并發(fā)正確執(zhí)行的程序。

答：

實(shí)質(zhì)上是兩個(gè)進(jìn)程的同步問題，設(shè)信號(hào)量S1和S2分別表示可揀白子和黑子，不失一般性,

若令先揀白子。

varSl,S2:semaphore;

Sl:=l;S2:=0;

cobegin

(

processPl

begin

repeat

P(S1);

揀白子

V(S2);

untilfalse;

end

processP2

begin

repeat

P(S2);

揀黑子

V(S1);

untilfalse;

end

}

coend.

18、系統(tǒng)有A、B、C、D共4種資源，在某時(shí)刻進(jìn)程PO、Pl、P2、P3和P4對(duì)資源的占

有和需求情況如表，試解答下列問題：

AllocationClaimAvailable

Process

ABCDABCDABCD

Po003200441622

P110002750

p21354361010

P303320984

P4001406610

(1)系統(tǒng)此時(shí)處于安全狀態(tài)嗎？為什么？

(2)若此時(shí)P2發(fā)出requesU。、2、2、2),系統(tǒng)能分配資源給它嗎？為什么？

答：

(1)系統(tǒng)處于安全狀態(tài)，存在安全序列：

PO,P3,P4,Pl,P2

PO,P3,PLP4,P2

PO,P3,Pl,P2,P4

(2)不能分配，否則系統(tǒng)會(huì)處于不安全狀態(tài)。

19、假設(shè)有32個(gè)存儲(chǔ)區(qū)域，其編號(hào)為0,1,…，31,用一個(gè)32位的標(biāo)志字，位號(hào)也是

0,1,...31