習(xí)題

第一章操作系統(tǒng)引論

【〈第?題＞】（中國科學(xué)院計算技術(shù)研究所1997年試題）

一個分層結(jié)構(gòu)操作系統(tǒng)由裸機、用戶、CPU調(diào)度和PV操作、文件管理、作業(yè)管理、內(nèi)存管理、設(shè)備管理、命令管理等

部分組成。試按層次結(jié)構(gòu)的原則從內(nèi)到外將各部分重新排列。

提示:

本題的考核要點是計算機系統(tǒng)的層次結(jié)構(gòu)。由丁?設(shè)計的原則不同，其層次結(jié)構(gòu)也有些區(qū)別。常見的劃分是:

?裸機層；

?CPU調(diào)度和P、V操作原語層；

?內(nèi)存管理、作業(yè)管理、設(shè)備管理、文件管理層；

?命令管理層（見下圖所示）。

【＜第：題＞］（南京大學(xué)1999年試題）

簡述卜.列各類操作系統(tǒng)的主要特征。

（1）批處理操作系統(tǒng)

（2）分時操作系統(tǒng)

（3）實時操作系統(tǒng)

（4）分布式操作系統(tǒng)

提示：

①批處理操作系統(tǒng)，具有以卜特點：

?自主性，無須人工干預(yù)。程序運行過程中不能與用戶會話。

?對于單道批處理系統(tǒng)來說，還具有程序運行的“順序性”。

②分時操作系統(tǒng)，具有的主要特點為：

?多路性。讓多個用戶同時工作，且各用戶獨立工作，互不干擾。

?交互性。用戶可通過終端與系統(tǒng)進行人一機會話.用戶的一項請求能在較短的時間內(nèi)獲得響應(yīng)。

③實時操作系統(tǒng)，具有的主要特點是：

?及時性。對時間的要求非常苛刻。

?過載保護.

④分布式操作系統(tǒng)，具有以下特點：

?分布性。OS的處理和控制功能是分布式的。

?并行性。它可將任務(wù)分布到多個處理單元上并行運行。

?透明性。它將對象的物理位置、并發(fā)控制、故障處理等實現(xiàn)細節(jié)隱藏在系統(tǒng)內(nèi)部，對用戶都是透明的.

?共享性。

?健壯性。任何站點上的故障都不能給系統(tǒng)造成太大的影響。

第二章進程的描述與控制（1）

[題]（西安電r?科技大學(xué)2001年試題）

在個分布式操作系統(tǒng)中，進程可能出現(xiàn)如下圖所示的變化，請把產(chǎn)生每?種變化的具體原因填在表格的相應(yīng)框中。

變化

<2)

⑶

<4)

(5)

提示：

本題考核的要點是引起進程狀態(tài)變化的條件。系統(tǒng)中的進程狀態(tài)共有4個，相關(guān)的內(nèi)容有：

?運行狀態(tài)。一個進程處于運行狀態(tài)，就表明該進程正在使用CPU進行運算。

?就緒隊列.處于就緒隊列的進程皆為就緒狀態(tài).若一個進程是就緒狀態(tài)，則該進程具有了運行條件（比如資

源已充足，也不等待I/O）,惟獨因CPU太少而得不到運行。

?數(shù)據(jù)資源狀態(tài).處于該狀態(tài)的進程必然因資源得不到滿足而等待.這類進程尚不具備運行條件.

?等I/O傳輸狀態(tài)。這也是一種進程等待狀態(tài)。處于該狀態(tài)的進程必然正在等待數(shù)據(jù)I/O操作的完成。這類進

程也不具備運行條件.

【第:題】（中國科學(xué)技術(shù)大學(xué)1998年試題）

（程序閱讀）何謂臨界區(qū)？下面給出的實現(xiàn)兩個進程互斥的算法是安全的嗎？為什么？

#defineTRUE;

#defineFALSE;

intflag[2];

flag[0]=flag[1]=FALSE;

enter-crtsec(i)

inti;

(

WHILE(flag[l-i]);

flag[i]=TRUE;

}

leave-crtsec(i)

inti;

(

flag[i]=FLASE;

)

processI:/*i=0OR1=1*/

enter-crtsec(i);/*進入臨界區(qū)*/

INCRTICALSECTION

Leave-crtsec(i);/*離開臨界區(qū)*/

提示：

本題的考核要點是臨界資源訪問。

①臨界資源指的是?次僅允許?個進程使用的資源。在進程中用于訪問臨界資源的程序段稱為臨界區(qū)（CRTICAL

SECTION）。

由于系統(tǒng)中的各進程在邏輯上是獨立的，因此它們各自以獨立的速度向前推進。然而它們又都需要系統(tǒng)中的資源，當(dāng)這

些資源為臨界資源時，就產(chǎn)生了互斥訪問的問題。臨界區(qū)的概念由此產(chǎn)生。

②本題給出的算法是不安全的。因為，在進入臨界區(qū)前執(zhí)行的過程enter-crtsec。和退出臨界區(qū)后執(zhí)行的過程Leave-crtsec

O都不是原子操作。因而不能避免兩個或更多進程進入臨界區(qū)。

【第二題】（清華大學(xué)1998年試題）

（判斷題）判斷對與錯：

①進程由進程控制塊和數(shù)據(jù)集以及對該數(shù)據(jù)集進行操作的程序組成。

②進程上下文是進程執(zhí)行活動全過程的靜態(tài)描述。

③并發(fā)是并行的不同描述，其原理相同。

提示：

本題考核的是進程的結(jié)構(gòu)、進程上下文，及進程的特征。涉及的內(nèi)容有：

①進程的結(jié)構(gòu)由PCB、數(shù)據(jù)集和程序代碼組成。

②進程上下文是進程執(zhí)行活動全過程的描述，主要包括系統(tǒng)中與執(zhí)行該進程有關(guān)的各種寄存器的值，比如數(shù)據(jù)寄存器、

地址寄存器和程序狀態(tài)字（PSW）,還有程序段經(jīng)編譯后形成的機器指令集、數(shù)據(jù)集及各種堆棧值和PCB結(jié)構(gòu)等。

③程序的并發(fā)執(zhí)行是指，一組在邏輯上互相獨立的程序或程序段在執(zhí)行時間上相互重疊.即一個程序段尚未結(jié)束，另

一個程序段的執(zhí)行已經(jīng)開始。應(yīng)當(dāng)注意，并發(fā)性和并行性是決然不同的。程序的并行執(zhí)行是指一組程序同時按獨立的、異

步的速度執(zhí)行；而并發(fā)性是指程序執(zhí)行時間上的重置，不等于程序同時運行。

【第四題】（南京大學(xué)1997年試題）

（論述題）操作系統(tǒng)中為什么要引入進程的概念？為了實現(xiàn)并發(fā)進程間的合作和協(xié)調(diào)工作，以及保證系統(tǒng)的安全，操作

系統(tǒng)在進程管理方面應(yīng)做哪些工作？

提示:

本題考核進程的?般概念。涉及的內(nèi)容有:

①讓程序并發(fā)方式執(zhí)行，能夠充分利用系統(tǒng)資源，提高系統(tǒng)的處理能力。但由于系統(tǒng)資源是有限的，諸多并發(fā)執(zhí)行的

程序在共享資源的同時，必將引起資源的競爭。此時如果不制定特定的規(guī)則和方法，必將使這種共享和競爭呈現(xiàn)無序狀態(tài)。

程序的執(zhí)行結(jié)果也將不可避免地失去封閉性和可再現(xiàn)性，從而得不出正確的、預(yù)期的結(jié)果。

正因為如此，多道程序設(shè)計中需要引入一個能描述程序執(zhí)行過程，且能用來共享資源的基本單位一那就是“進程”。因

此，進程可以被定義為“可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合的執(zhí)行過程”。

②操作系統(tǒng)對進程管理方面應(yīng)做如下工作：

?進程控制，包括進程創(chuàng)建與撤消，進程在運行過程中的狀態(tài)轉(zhuǎn)換，以及實現(xiàn)對進程控制塊的維護等操作。

?進程調(diào)度.操作系統(tǒng)必須按一定算法在就緒進程中選擇一個進程，把處理機分配給它，使它順利地投入運行。

為此，進程調(diào)度應(yīng)具有CPU現(xiàn)場信息的保護和恢復(fù)功能。

?進程同步。對于一組合作的進程，它們的推進速度應(yīng)當(dāng)受到某種約束，以便協(xié)調(diào)一致地向前推進。因此系統(tǒng)

必須設(shè)立同步控制機制，對所有進程的運行進行協(xié)調(diào)。協(xié)調(diào)方式包括進程互斥方式和進程同步方式.

?進程通信.在多道程序環(huán)境下，進程之間往往要互相發(fā)送一些信息.操作系統(tǒng)應(yīng)提供有關(guān)的通信調(diào)用和通信

規(guī)范，保證實現(xiàn)這些進程之間的信息交換.進程之間的通信種類是很多的，控制機制也有很多。

【第五題】（西安電子科技大學(xué)2001年試題）

（判斷題）有關(guān)進程的描述中，是正確的。

（A）進程執(zhí)行的相對速度不能由進程自己來控制

（B）P、V操作都是原語操作

（C）利用信號量的P、V操作可以交換大量信息

（D）同步是指并發(fā)進程之間存在的一種制約關(guān)系

提示：

該題的考核要點是進程。進程是多道程序設(shè)計中引入的一個新概念，是為了解決資源競爭，實現(xiàn)資源共享而提出的。涉

及的內(nèi)容有：

①進程的運行具有異步性——其推進速度是不可預(yù)測的。因此進程執(zhí)行的相對?速度不能由進程自己來控制。

②原語是一種運行時間較少的小程序，它的運行不可分割。P、V操作都是這樣一類操作。

③P、V操作只能花較少的時間運行。若讓它們交換大量信息，必然在關(guān)中斷的狀態(tài)下運行時間太長，使許多中斷得不

到響應(yīng)，最后造成不可預(yù)料的后果。

④同步是多個并發(fā)進程協(xié)調(diào)一致運行的一種制約關(guān)系。

【第六題】（南京大學(xué)2（X）0年試題）

（論述題）什么是線程？試說明線程與進程的關(guān)系。

提示:

本題的考核要點是線程的基本概念。在引入線程的操作系統(tǒng)中，線程是進程的實體。線程調(diào)度是處理機調(diào)度中最接近硬

件的部分。

①線程是為了減少程序并發(fā)執(zhí)行時付出的開銷而引入的。線程的特點是：

?結(jié)構(gòu)性。線程有自己的線程控制塊（TCB）、程序代碼及數(shù)據(jù)集合，它所擁有的資源主要是CPU現(xiàn)場信息

及堆棧信息等.除此之外基本上不擁有自己的資源.

?能動性。一個線程可以創(chuàng)建或者撇消另一個線程。

?并發(fā)性.同一進程的多個線程可以并發(fā)執(zhí)行.

?動態(tài)性。線程有生命周期，在其生命周期中，線程在就緒、運行、阻塞等狀態(tài)之間變換。

卜圖是線程控制塊的一個例子。

線程標(biāo)識

狀態(tài)

優(yōu)先數(shù)

現(xiàn)場存儲

②進程與線程的聯(lián)系與區(qū)別。

?進程是任務(wù)調(diào)度的單位，也是系統(tǒng)資源的分配單位；而線程可以看作是進程中的一條執(zhí)行路徑.

?當(dāng)系統(tǒng)支持多線程處理時，線程是任務(wù)調(diào)度的基本單位，但不是資源的分配單位，而進程恰好相反。

?每個進程至少有一個執(zhí)行線程.

?當(dāng)系統(tǒng)支持多線程處理時，線程的切換頻繁，但切換的系統(tǒng)開銷較小，因此被稱為“輕量級的進程”。而進

程的切換不頻繁，切換時的開銷較大.

［第七題］（中國科學(xué)院計算技術(shù)研究所1999年試題）

填空：

（1）進程控制塊的初始化工作包括O、（）、和（）°

（2）在操作系統(tǒng)中引入線程概念的主要目的是（）o

提示：

本題的考核要點是進程與線程的基本概念。涉及的內(nèi)容有：

①在進程控制塊中包含了進程的所有控制信息。這些信息可大體分為3類：

?標(biāo)識符號信息。

?處理機狀態(tài)信息。

?處理機控制信息。

第一小題就是針對這3類信息的初始化的。

②在操作系統(tǒng)中引入線程，主要是為了減少程序并發(fā)執(zhí)行時所需付出的時空開銷，縮短系統(tǒng)切換時間。同時也從提高

程序執(zhí)行的并發(fā)度方面考慮。

【第八題】（南京大學(xué)1997年試題）

（論述題）操作系統(tǒng)中為什么要引入進程的概念？為了實現(xiàn)并發(fā)進程間的合作和協(xié)調(diào)工作，以及保證系統(tǒng)的安全，操作

系統(tǒng)在進程管理方面應(yīng)做哪些工作？

提示：

本題考核進程的一般概念。涉及的內(nèi)容有：

①讓程序并發(fā)方式執(zhí)行，能夠充分利用系統(tǒng)資源，提高系統(tǒng)的處理能力。但由于系統(tǒng)資源是有限的，諸多并發(fā)執(zhí)行的

程序在共享資源的同時，必將引起資源的競爭。此時如果不制定特定的規(guī)則和方法，必將使這種共享和競爭呈現(xiàn)無序狀態(tài)。

程序的執(zhí)行結(jié)果也將不可避免地失去封閉性和可再現(xiàn)性，從而得不出正確的、預(yù)期的結(jié)果。

正因為如此，多道程序設(shè)計中需要引入一個能描述程序執(zhí)行過程，且能用來共享資源的基本單位一那就是“進程”。

因此，進程可以被定義為“可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合的執(zhí)行過程”。

②操作系統(tǒng)對進程管理方面應(yīng)做如下工作：

?進程控制，包括進程創(chuàng)建與撤消，進程在運行過程中的狀態(tài)轉(zhuǎn)換，以及實現(xiàn)對進程控制塊的維護等操作。

?進程調(diào)度.操作系統(tǒng)必須按一定算法在就緒進程中選擇一個進程，把處理機分配給它，使它順利地投入運行。

為此，進程調(diào)度應(yīng)具有CPU現(xiàn)場信息的保護和恢復(fù)功能。

?進程同步。對于一組合作的進程，它們的推進速度應(yīng)當(dāng)受到某種約束，以便協(xié)調(diào)一致地向前推進。因此系統(tǒng)

必須設(shè)立同步控制機制，對所有進程的運行進行協(xié)調(diào)。協(xié)調(diào)方式包括進程互斥方式和進程同步方式.

?進程通信.在多道程序環(huán)境下，進程之間往往要互相發(fā)送一些信息.操作系統(tǒng)應(yīng)提供有關(guān)的通信調(diào)用和通信

規(guī)范，保證實現(xiàn)這些進程之間的信息交換.進程之間的通信種類是很多的，控制機制也有很多。

【笫九期】（哈工大2000年試題）

（問答題）試比較進程和程序的區(qū)別。

提示：

本題注重的是進程概念。進程和程序是既相互聯(lián)系又相互區(qū)別的。

（1）相互聯(lián)系

程序是構(gòu)成進程的組成部分之一，一個進程的運行目標(biāo)是執(zhí)行它所對應(yīng)的程序，如果沒有程序，進程就失去了其實際的

存在。從靜態(tài)的角度看，進程是由程序、數(shù)據(jù)和進程控制塊（PCB）三部分組成的。

（2）相互區(qū)別

?程序是一個靜態(tài)概念。一個程序是一個靜態(tài)文本，是指令的有序集合,程序可以作為一種軟件資料長期保存，

只能起到文本的作用。進程是一個動態(tài)概念。它是程序在處理機上的一次執(zhí)行過程。進程是有一定生命周期的,

它能夠動態(tài)地產(chǎn)生和消亡.

?進程與程序在結(jié)構(gòu)上不同.進程由進程控制決（PCB）、程序段、數(shù)據(jù)段三部分組成。程序是進程運行的依據(jù)。

?進程是一個能獨立運行的單位，能與其■他進程并行運行。程序是算法的一種描述形式。

?進程是競爭計算機系統(tǒng)有限資源的基本單位，也是進行處理機調(diào)度的基本單位.同一程序運行于若干不同的數(shù)

據(jù)集合上，它將屬于若干個不同的進程。或者說，若干不同的進程可以包含相同的程序。

本

節(jié)

第二章進程同步與通信（2）導(dǎo)

讀

【第一題】（青島大學(xué)2002年試題）

青島嶗山有一處景點稱作上清宮，游客在宮內(nèi)游玩之后可以在宮門口免費搭乘轎車游覽嶗山的風(fēng)景區(qū)，游覽完畢再返回

宮門口（如下圖所示）。

已知風(fēng)景區(qū)內(nèi)的轎車總量為M輛，游客總數(shù)為N,約定：

(1)每輛轎車限乘一位游客：

(2)如果有空閑的轎車，應(yīng)當(dāng)允許想游覽的游客乘坐：

(3)無空閑轎車時，游客只能排隊等待；

(4)若沒在.想游覽的游客，空閑的轎車也要等待。

試利用P、V操作實現(xiàn)N個游客進程與M輛轎車進程的同步操作過程。

提示：本題中游客乘坐轎車游覽風(fēng)景區(qū)是免費的，因此程序設(shè)計中不需要考慮付費環(huán)節(jié)。

分析：

本題考核的要點是進程同步問題。我們定義了3個信號量cajavail,cajtaken和take_off,實現(xiàn)游客進程與轎車進程的

同步操作。

Begin

Semaphore：car_avail.car_taken,take_off：

car_avail:=0;car_taken:=0;take_off:=0;

cobegin

processpassenger()

begin

逛上清宮；

P(car_avail);

Take_in_car();//游客上車

V(car_taken);

P(finished);

Take_off_car();//游客下車

V(that_off);

end

processcar()

begin

repeat

V(car_avail);

P(car_taken);

Take_a_visit();//游覽嶗山風(fēng)景區(qū)：

V(finished);

P(that_off);

Untilfalse;

end.

【第.題】(西安電子科技大學(xué)2000年試題)

有一個理發(fā)師，一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子。如果沒有顧客，則理發(fā)師便在理發(fā)椅子上睡覺：當(dāng)一個

顧客到來時，喚醒理發(fā)師進行理發(fā)。如果理發(fā)師正在理發(fā)時又有新顧客到來，有空椅子可坐，他就坐卜來等，如果沒有空

椅子，就立即離開。為理發(fā)師和顧客各編一段程序描述他們的行為，要求不能帶有競爭條件。

分析：

這是一個比較復(fù)雜的進程同步問題。需要設(shè)計兩個進程：

?顧客進程Customer()

?理發(fā)師進程Barber()

特定義兩個信號量customers和barbers實現(xiàn)進程的同步，并定義信號量S實現(xiàn)進程的互斥。程序代碼如卜.:

Begin

//定義信號量并初始化

intCHAIRS:〃為等候的顧客準(zhǔn)備的椅『數(shù)

semaphore：customers=0;

semaphore：barbers=0;

semaphore：cut=0;

semaphore：finish=0;

semaphore：mutex=l;〃用于互斥的信號量

intwaiting=0;

Cobegin

//定義并發(fā)進程

ProcessCustomer()

(

P(mutex);

if(waiting>CHAIRS)

then

V(mutex)〃沒有空椅子，離開

else

(

waiting=waiting+1;

V(mutex);

V(customers);//喚醒理發(fā)師

SIT_ON_chair();〃坐在椅子上等候

P(barbers);//等待理發(fā)召喚

Stand_up();//從椅子上起身

P(mutex);

waiiting=waiting-l;

V(mutex);

SIT_ON_cut_chair();//坐在理發(fā)椅上

V(cut);//告訴理發(fā)師可以開始理發(fā)

P(finish);//等待理發(fā)完成

}

voidbarber()

(

while(T)

(

P(customers);//等待顧客到來

Clear_cut_chair();//整理一下理發(fā)椅子

V(barbers);//召喚一個顧客

P(cut);〃等待顧客就座

CUT_hair();//理發(fā)

V(finish);//告訴顧客已結(jié)束

Coend

//并發(fā)進程的定義結(jié)束

End.

討論：

①代碼中帶陰影的部分可以從顧客進程移到理發(fā)師進程中處理.

②該算法中沒有涉及顧客理發(fā)后的付款過程.

【第二題】(中國科學(xué)技術(shù)大學(xué)1998年試題)

(程序閱讀)何謂臨界區(qū)？下面給出的實現(xiàn)兩個進程互斥的算法是安全的嗎？為什么？

IdefineTRUE;

fdefineFALSE;

intflag[2];

flag[0]=flag[1]-FALSE;

enter-crtsec(i)

inti;

(

WHILE(flag[l-i]);

flagfi]=TRUE;

)

leave-crtsec(i)

inti;

(

flag[i]=FLASE;

}

processI:/*i=0OR1=1*/

enter-crtsec(i);/*進入臨界區(qū)*/

INCRTICALSECTION

Leave-crtsec(i);/*離開臨界區(qū)*/

提示：

本題的考核要點是臨界資源訪問。

①臨界資源指的是一次僅允許一個進程使用的資源。在進程中用于訪問臨界資源的程序段稱為臨界區(qū)(CRTICAL

SECTION)。

由于系統(tǒng)中的各進程在邏輯上是獨立的，因此它們各自以獨立的速度向前推進。然而它們又都需要系統(tǒng)中的資源，當(dāng)這

些資源為臨界資源肘，就產(chǎn)生了互斥訪問的問題。臨界區(qū)的概念由此產(chǎn)生。

②本題給出的算法是不安全的。因為，在進入臨界區(qū)前執(zhí)行的過程cnixcrtscc。和退出臨界區(qū)后執(zhí)行的過程Lcave?lscc

O都不是原子操作。因而不能避免兩個或更多進程進入臨界區(qū)。

【笫四題】(南京大學(xué)2000年試題)

為了讓用戶進程互斥地進入臨界區(qū)，可以把整個臨界區(qū)實現(xiàn)成不可中斷的過程，即讓用戶具有屏蔽所有中斷的能力。每

當(dāng)用戶程序進入臨界區(qū)的時候，屏蔽所有中|所。當(dāng)出了臨界區(qū)的時候，再開放所有中斷。你認為這種方法有什么缺點。

提示:

本題考核的要點是臨界資源的使用。為了達到互斥使用臨界資源的目的，將訪問臨界資源的程序放在中斷被屏蔽的狀態(tài)

下運行。這樣做雖然可以達到互斥訪問的目的，但并不可取。因為，一般情況下，進程對臨界資源的訪問時間都比較長，

比如訪問內(nèi)存中的一個緩沖區(qū)環(huán)，就需要判斷環(huán)內(nèi)是否已滿或為空，然后對當(dāng)前緩沖區(qū)進行訪問，最后再移動環(huán)上的指針。

如果讓中斷扉蔽時間拖的太長，有可能錯過對某的特別緊迫的中斷信號的響應(yīng)，以致喪失了最佳處理時機。

【第“題】(中國科學(xué)院計算技術(shù)研究所1996年試題)

Dijkstra提出的銀行家算法的主要思想是什么？它能夠用來解決實際中的死鎖問題嗎？為什么？

提示：

本題的考核要點是銀行家(Banker)算法。涉及的內(nèi)容有：

①銀行家算法是一?種解決死鎖問題的方法。該算法模擬了銀行在經(jīng)營中的貸款策略。當(dāng)用戶提出資源請求時，先計算

該次分配后是否會導(dǎo)致系統(tǒng)不安全，即是否存在一種順序，使得所有的進程都能執(zhí)行結(jié)束。若安全則將資源分配給用戶，

否則拒絕分配。

②從理論上說，該算法有是很有意義的，但在實際實施4」卻有一定難度。因為算法所假設(shè)的一些條件太多，諸如，讓

用戶提交作業(yè)需求資源的最大數(shù)目并不容易，算法本身涉及的數(shù)據(jù)結(jié)構(gòu)太復(fù)雜等。

③銀行家算法比較耗時，而每當(dāng)一?個用戶提出資源請求時，都需要調(diào)用銀行家算法測算一遍，無形中使系統(tǒng)的開銷加

大，降低了處理機的利用率。

注意：銀行家算法用于資源分配之前，檢測系統(tǒng)是否安全.該算法能夠解決實際中的死鎖問題，

但系統(tǒng)開銷較大。

【笫六虺】(西安理工大學(xué)2000年試題)

(程序設(shè)計題)設(shè)有6個進程Pl、P2、P3、P4、P5、P6,它們有如圖所示的并發(fā)關(guān)系。試用P、V操作實現(xiàn)這些進程

間的同步。

提示：

本題考核的是用P、V操作實現(xiàn)進程間同步的問題。卜.面設(shè)計了4個信號量分別用于進程之間的同步，它們的初始值為

0o當(dāng)進程Pl尚未得到運行的話，其他進程只能被阻塞等待。算法可描述如下：

BEGIN

Semaphore：si,s2,s3.s4;

si:=s2:=s3:=s4:=0

COBEGIN

ProcessPl:

Begin

doallwork;

V(sl);

V(sl);

End

ProcessP2:

Begin

P(sl)

doallwork;

V(s2);

End

ProcessP3:

Begin

P(sl);

doallwork;

V(s3);

End

ProcessP4:

Begin

P(s2);

doallwork;

V(s4);

End

ProcessP5:

Begin

P(s3);

doallwork;

V(s4);

End

ProcessP6:

Begin

P(s4);

P(s4);

doallwork;

End

COEND

END

【第七題】(清華大學(xué)1995年試題)

(問答題)使用P、V原語和加鎖法都可以實現(xiàn)并發(fā)進程間的互斥，問：

(1)P、V原語和加鎖法實現(xiàn)互斥時有何導(dǎo)同？

(2)使用加鎖法實現(xiàn)互斥時，有可能在進程使用臨界區(qū)時造成不公平現(xiàn)象，即某個進程一直占用臨界區(qū)，其他進程永

遠無法使用。找出一個不公平現(xiàn)象的例子，并分析產(chǎn)生不公平現(xiàn)象的原因。

提示：

本題的考核要點是P、V原語和加鎖法的原理。

①P、V操作與加鎖法都是實現(xiàn)進程互斥的方法。它們都是根據(jù)?個變量的值來判斷當(dāng)前是否可以進入臨界區(qū)。它們的

不同點如下：

?p、V操作是用原語來實現(xiàn)的，即P、V操作在屏蔽中斷的環(huán)境中執(zhí)行。而加鎖法不具備這個特點.

?加鎖法對系統(tǒng)的運行性能有較大影響.比如，對鎖定位的循環(huán)測試將損耗大量的CPU時間.

?用P、V操作實現(xiàn)進程互斥時，未進入臨界區(qū)的進程只能被阻塞等待，而加鎖法則相反.

②以下進程會產(chǎn)生不公平的現(xiàn)象。

ProcessPl()

begin

LI:lock(key[s])；

''訪問臨界資源〃：

unlock(key(s])；

GotoLI：

End.

ProcessP2()

Begin

L2:lock(key[s])：

''訪問臨界資源”；

unlock(key[s])；

GotoL2；

End.

假設(shè)進程Pl首先進入臨界區(qū)。那么在進程P1執(zhí)行unlock(key⑶)過程之前，key[s]的值為0,進程P2沒有進入臨界

區(qū)的機會。然而，當(dāng)進程P1執(zhí)行完unlock(key[s])過程后kcy[s]的值變?yōu)?,緊接著是一條轉(zhuǎn)向語句，又將再次進入臨界

區(qū)。

這樣一來，只有當(dāng)進程P1執(zhí)行完unlock(key[s])過程之后的一瞬間內(nèi)發(fā)生了進程調(diào)度，進程P2才可能獲得處理機。

因此說，進程P2獲得執(zhí)行的機會是相當(dāng)小的。故進程P2將處于氏期“饑餓”狀態(tài)。

【第八題】(北京大學(xué)1997年試題)

某高校計算機系開設(shè)有網(wǎng)絡(luò)課并安排了上機實習(xí)，假設(shè)機房共有2m臺機器，有2n名學(xué)生選該課，規(guī)定:

①每兩個學(xué)生組成一組，各占一臺機器，協(xié)同完成上機實習(xí)；

②只有一組的兩個學(xué)生到齊，并且此時機房有空閑機器時，該組學(xué)生才能進入機房：

③上機實習(xí)由一名教師檢查，檢查完畢，一組學(xué)生同時離開機房。

試用P、V操作模擬上機實習(xí)過程。

提示：

本題中考核的主要內(nèi)容是進程互斥與同步問題。為了保證系統(tǒng)的控制流程，專門設(shè)?個Monitor進程，用于控制學(xué)生進

入機房及計算機的分配使用。從題目本身來看，雖然沒有明確指出這一進程，但實際上這一進程應(yīng)當(dāng)是存在的。

上機實習(xí)過程可描述如卜：

BEGIN

Semaphore：student,computer,enter,finish,check;

studen:=0;

computer:=2m;

enter:=0;

finish:=0:

chech:=0;

COBEGIN

ProcessProcedureStudent()

begin

V(student)://表示有學(xué)生到達

P(computer)://等待獲取一臺計兌機

P(enter);//等待進入許可

DOitwithpartner();

V(finish);//實習(xí)完成

P(check);//等待老師檢查

V(computer)://釋放計算機資源

end

ProcessProcedureTeacher()

begin

LI:P(finished);//等待學(xué)生實習(xí)完成

P(finished);//等待另一學(xué)生實習(xí)完成

checkthework();

V(check);//表示檢查完成

V(check);//表示檢查完成

gotoLI;

end

ProcessProcedureMonitor()

begin

L2:P(student);//等待學(xué)生到達

P(student);//等待另一學(xué)生到達

V(enter);//允許學(xué)生進入

V(enter);//允許學(xué)生進入

end

Coend

END

【第九題】(西北工業(yè)大學(xué)2000年試題)

(設(shè)計題)從讀卡機上讀進N張卡片，然后復(fù)制一份，要求復(fù)制出來的卡片與讀進來的卡片完全一致。這一工作由三個

進程get,copy和put以及兩個緩沖區(qū)buffer1和buffer2完成。進程get的功能是把一張卡片上的信息從讀卡機上讀進

buffer1；進程copy的功能是把buffer1中的信息復(fù)制到buffcr2；進程put的功能是取出buffer!中的信息并從行式打印機上

打印輸出。

試用P、V操作完成這三個進程間的盡可能并發(fā)正確運行的關(guān)系(用程序或框圖表示)，并指明信號量的作用及初值。

提示：

設(shè)計6個信號量SI,S2,SnLSn2,Sml,Sm2。其中：

?SI和S2為互斥信號量，初值為1,分別用于對bufferl和buffer2的互斥訪問；

?Snl和Sn2為同步信號量，初值為1,分別表示bufferl和buffer2為空閑，可以存放一張卡片的信息；

?SmI和Sm2為同步信號量，初值為0,分別表示buffed和buffer2中的信息還沒有被取用(或已被取用

了),

用P、V操作完成這三個并發(fā)進程間能正確運行的程序如卜.：

BEGIN

semaphore:SI,S2,Snl,Sn2,Sml>Sm2;

S1=S2=1;//bufferl■和buffer2的互斥信號量

Snl=Sn2=l;//同步信號量

Sml=Sm2=0;

Cobegin

Processproduceget()

Begin

LI:從讀卡機讀進一張卡片信息：

P(Snl);

P(S1);

將信息放入bufferl;

V(Sml);

V(S1);

GotoLI

End

Processproducecopy()

Begin

L2:P(Sml);

P(S1);

從bufferl復(fù)制信息：

V(Snl);

V(S1);

P(Sn2);

P(S2);

將夏制的信息放入buffer2;

V(Sm2);

V(S2);

GotoL2

End

Processproduceput()

Begin

L3:P(Sm2);

P(S2);

從buffer2取信息；

V(Sn2);

V(S2);

把信息從打印機輸出：

GotoL3

End

Coend;

END

【第卜題】（南京大學(xué)1997年試題）

（程序設(shè)計題）假定有一個信箱可存放N封信。當(dāng)信箱不滿時，發(fā)信者可把信件送入信箱：當(dāng)信箱中有信時，收信者可

以從信箱中取信。用指針r、k分別表示可存信和取信的位置，請用管程（Monitor）來管理這個信箱，使發(fā)信者和收信者

能正確工作。

提示：

本題的考核要點是管程的概念。卜.面的程序中，讓變量Buffer[O..N-l]來存放信件，讓I?是讀信件的指針，k是寫信件的

指針。此外，還應(yīng)定義管程的兩個條件變量full和empty%程序描述如下：

MonitorMailboxManager

full,emptyl:Condition;

k,r,count:Integer;

Buffer:Array（0..N-l]ofMessage;

PROCEDURERead。

BEGIN

IF(count=N)THENP(full);

Buffer[r]:=message;

r:=(r+l)modN;

count:=count+l;

IF(count=1)THENV(empty);

END;

PROCEDUREWrite()

BEGIN

IF(count=0)THENP(empty);

message:=Buffer[k];

k:=(k+1)modN;

count:=count-l;

IF(count=N-l)THENV(full);

END;

//卜.面是初始化部分

begin

k=-l;

r=0;

count:=0;

END;

第三章調(diào)度與死鎖

【第題】（西安電子科技大學(xué)2001試題）

有；個進程Pl、P2和P3并發(fā)工作。進程P1需要資源S3和S1；進程P2需用資源S1和S2；進程P3需用資源S2和

S3,回答：

（I）若對資源分配不加限制，會發(fā)生什么情況？為什么？

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

提示：

①若對資源分配不加限制，可能會發(fā)生死鎖，因為這樣的分配叮能導(dǎo)致“環(huán)路等待”條件。例如：進程Pl、P2和P3

分別獲得資源S3、S1和S2,后再繼續(xù)申請資源時都要等待。進程和資源會形成如下環(huán)路：

②為保證進程正確地工作，應(yīng)采用的資源分配可有兒種答案。下面列舉3種：

?采用糙態(tài)分配

由于執(zhí)行前已獲得所需的全部資源，故不會出現(xiàn)占有資源又等待的資源的現(xiàn)象（或不會出現(xiàn)循環(huán)等待資源現(xiàn)象）。

?采用按序分配

按序分配不會出現(xiàn)“環(huán)路等待”現(xiàn)象。

?采用銀行家算法

在每次分配時，通過銀河家算法的測算，可保證系統(tǒng)處于安全狀態(tài)。

【第二題】（南京大學(xué)2002試題）

有三個作業(yè)A（到達時間8:50,執(zhí)行時間1.5小時）、B（到達時間9:00,執(zhí)行時間0.4小時）、C（到達時間9:30,執(zhí)

行時間I小時）。當(dāng)作業(yè)全部到達后，批處理單道系統(tǒng)按照響應(yīng)比高者優(yōu)先算法進行調(diào)度，則作業(yè)被選中的次序是（）。

A.(ABC)B.(BAC)

C.(BCA)D.(CBA)

E.(CAB)F.(ACB)

提示:

本題考?核進程調(diào)度問題。作業(yè)運行情況見下表:

進程到達時間運行長度開始時間結(jié)束時間

A8:501.59:5411:24

B9:000.49:309:54

C9:30111:2412:24

當(dāng)作業(yè)全部到達后，也就是9:30,系統(tǒng)開始調(diào)度。此刻各作業(yè)的等待時間是，A為40分鐘（0.67小時）、B為0.5小時、

C為0小時。其響應(yīng)比分別為：

A：1+0.67/1.5=1.4

B：1+0.5/0.4=2.25

C：I+0/1=1

系統(tǒng)首先選B運行24分鐘,至9:54運行結(jié)束。各作業(yè)的等待時間是,A為1.07小時,C為0.4小時。其響應(yīng)比分別修改

為：

A：1+1.07/1.5=1.7

C：1+0.4/1=1.4

系統(tǒng)再選A運行，至11:24運行結(jié)束。最后選擇C運行至12:24結(jié)束。因此，本題的正確答案應(yīng)當(dāng)是（B）。

注意：在做此類題目時，需要制作作業(yè)運行情況表，詳細列出提交時間、運行長度、

運行開始時間和運行結(jié)束時間。

【第題】（西安電子科技大學(xué)2001試題）

有5個待運行作業(yè)JI、J2、J3、J4和J5,各自預(yù)計運行時間分別是9、6、3、5和7。假定這些作業(yè)同時到達，并且在

一臺處理機上按單道方式執(zhí)行。

討論采用哪種調(diào)度算法和哪種運行次序?qū)⑹蛊骄苻D(zhuǎn)時間最短，平均周轉(zhuǎn)時間為多少？

提示：

本題的考核要點是作業(yè)調(diào)度算法的性能評價。涉及到作業(yè)平均周轉(zhuǎn)時間的計算問題。我們知道，常用的作業(yè)調(diào)度算法有

4種：先來先服務(wù)、最高優(yōu)先級調(diào)度、最短作業(yè)優(yōu)先和最高響應(yīng)比優(yōu)先。而前兩種在本題中已被排除，所以只需討論后兩

種即可。

①按照最短作業(yè)優(yōu)先（SJF）算法，作業(yè)的運行順序為J3,J4,J2,J5,JL平均周轉(zhuǎn)時間T為：

T=[3+（3+5）+（3+5+6）+（3+5+6+7）+（3+5+6+7+9）]/5=15.2

②按照最高響應(yīng)比優(yōu)先（HRF）算法，由于5個作業(yè)是同時提交的，因此第一時間的調(diào)度必然是最短的作業(yè)J3。當(dāng)J3

執(zhí)行完畢后，剩余4個作業(yè)的響應(yīng)比R（R=l+作業(yè)的等候時間/作業(yè)的執(zhí)行時間）計算的結(jié)果為：

Rl=1.33

R2=1.5

R4=1.6

R5=1.428

正是由于5個作業(yè)都是同時提交的，所以只需計算這次就可以確定它們的執(zhí)行次序：J4,J2,J5,J1。與J3合在?起，

得到的作業(yè)執(zhí)行次序為：

J3.J4,J2,J5,J1

顯然，兩種調(diào)度算法的調(diào)度次序皆相同。這是因為它們的提交時間相同所致。因此。它們的平均周轉(zhuǎn)時間T為15.2。

【第.題】（西安交大2002試題）

有5個任務(wù)A,B,C,D,E,它們幾乎同時到達，預(yù)計它們的運行時間為10,6,2,4,8min.其優(yōu)先級分別為3,5,

2,1和4,這里5為最高優(yōu)先級。對于下列每一種調(diào)度算法，計算其平均進程周轉(zhuǎn)時間（進程切換開俏可不考慮）。

（1）先來先服務(wù)（按A,B,C,D,E）算法。

（2）優(yōu)先級調(diào)度算法。

（3）時間片輪轉(zhuǎn)算法。

提示：

①采用先來先服務(wù)（FCFS）調(diào)度算法時，5個任務(wù)在系統(tǒng)中的執(zhí)行順序、完成時間及周轉(zhuǎn)時間如卜表所示:

執(zhí)行次序運行時間優(yōu)先數(shù)等待時間周轉(zhuǎn)時間

A103010

B651016

16

C22

18

D411822

E842230

根據(jù)表中的計算結(jié)果，5個進程的平均周轉(zhuǎn)時間T為：

T=（10+16+18+22+30）/5=19.2min

②采用最高優(yōu)先級調(diào)度（HPF）算法時，5個任務(wù)在系統(tǒng)中的執(zhí)行順序、完成時間及周轉(zhuǎn)時間如下表所示:

執(zhí)行次序運行時間優(yōu)先數(shù)等待時間周轉(zhuǎn)時間

B6506

E84614

A1031424

C222426

D112627

它們的平均周轉(zhuǎn)時間為：

T=（6+14+24+26+27）/5=19.4min

③如果系統(tǒng)采用時間片輪轉(zhuǎn)（RR）算法，令時間片為2分鐘，5個任務(wù)輪流執(zhí)行的情況為：

第1輪：（A,B,C,D,E）

第2輪：（A,B,D,E）

第3輪：（A,B,E）

第4輪：（A,E）

第5輪：（A）

顯然，5個進程的周轉(zhuǎn)時間為：Tl=30min、T2=22min、T3=6min、T4=16min.T5=28min0它們的平均周轉(zhuǎn)時間T為:

T=（30+22+6+16+28）/5=20.4min

【第一題】（南京大學(xué)2000年試題）

（問答題）現(xiàn)有兩道作業(yè)同時執(zhí)行，?道以計算為主，另?道以輸入輸出為主，你將怎樣賦予作業(yè)進程占有處理器的優(yōu)

先級？為什么？

提示：

本題考核要點是，如何提高系統(tǒng)效率的問題。我們知道，以計算為主的進程運行期間，將主要集中在CPU的計算上，

較少使用外部設(shè)備。而以輸入輸出為主的進程則主要集中在外部設(shè)備的I/OI.,較少使用CPU。因此讓兩個進程并發(fā)運行

是可以提高系統(tǒng)效率的。不過它們的優(yōu)先級應(yīng)當(dāng)設(shè)定合理，比如：

①如果計算進程的優(yōu)先級高于或者等于輸入輸出進程的優(yōu)先級，系統(tǒng)效率也不會提高。因為計算進程?旦占用了CPU

便忙于計算,使輸入輸出進程得不到運行機會，同樣會使設(shè)備空閑，不能提高系統(tǒng)效率。

②如果輸入輸出進程的優(yōu)先級高于計算進程的優(yōu)先級，系統(tǒng)效率就能夠得到提高。因為輸入輸出操作是種速度極慢

的操作。若該項操作的優(yōu)先級高，那么，當(dāng)它完成一項輸入輸出操作后，便能立即獲得CPU,為卜一次輸入輸出作準(zhǔn)備匚

作，并啟動外部設(shè)備。當(dāng)設(shè)備被啟動起來后，它便主動讓出CPU,由系統(tǒng)將CPU交給計算進程使用。從而獲得較好的運

行效率。

注意：優(yōu)先級的設(shè)定方式有兩種，一種是根據(jù)用戶要求設(shè)定，另一種由系統(tǒng)管理員設(shè)

定。后一種設(shè)