考研-操作系統(tǒng)基礎(chǔ)知識歸納和總結(jié)

考研基礎(chǔ)知識總結(jié)

?什么是操作系統(tǒng)？它有什么基本特征？（哈工大2000年試題）

【解答】

操作系統(tǒng)：操作系統(tǒng)是計算機系統(tǒng)中的一個系統(tǒng)軟件。它是一些程序模塊的集合，

這些程序模塊管理和限制計算機中的硬件和軟件資源，合理地組織計算機工作流程，以

便有效地利用這些資源為用戶供應(yīng)一個功能強，運用便利的工作環(huán)境，從而在用戶及計

算機之間起到接口的作用。

操作系統(tǒng)的基本特征是并行性，共享性，不確定性。

?推斷：操作系統(tǒng)程序都是在核心態(tài)下才能運行。（大連理工大學(xué)2000年試題）

【分析】

操作系統(tǒng)是一組限制和管理計算機硬件和軟件資源，合理地對各類作業(yè)進行調(diào)度

以及便利用戶的程序的集合。操作系統(tǒng)供應(yīng)的服務(wù)，一部分必需在核心態(tài)下才能運行，

如進程調(diào)度，目錄服務(wù)等。還有一些功能，如DOS下的外部命令，則可以由用戶調(diào)用，

運行在用戶態(tài)下。

【解答】

錯誤。

?批處理系統(tǒng)的主要缺點是：（清華大學(xué)1996年試題）

A.CPU利用率低。B.不能并發(fā)執(zhí)行。

C.缺少交互性。D.以上都不是。

【解答】

選擇C。

?填空：多道運行的特征之一是宏觀上并行，它的含義是（（華中科技大學(xué)2000

年試題）

【分析】

多道運行的特征是多道性，宏觀上并行，彳散觀上串行。多道性是指計算機主存中同

時存放幾道相互獨立的程序。宏觀上并行是指同時進入系統(tǒng)的幾道程序都處于運行過程

中，即它們先后開始了各自的運行，但都未運行完畢。微觀上串行是指主存中的多道程

序輪番或分時地占有處理機交替執(zhí)行。

【解答】

并發(fā)程序都已經(jīng)開始執(zhí)行，但都未結(jié)束。

?推斷：在分時系統(tǒng)中，響應(yīng)時間X時間片X用戶數(shù)，因此為改善響應(yīng)時間，常用的

原則是使時間片越小越好。（東南大學(xué)1996年試題）

【分析】

時間片越小，進程切換所用的開銷就相對越大。因此時間片不是越小越好，一般運

用戶鍵入的常用命令能在一個時間片內(nèi)處理完畢即可。

【解答】

錯誤。

?實時系統(tǒng)應(yīng)具備的兩個基本特性是（）和（）。（北京理工大學(xué)2000年試題）

【分析】

實時系統(tǒng)是順應(yīng)實時限制和實時信息處理的須要而產(chǎn)生的。所謂"實時"是表示"及時

"，"即時"，而實時系統(tǒng)是指系統(tǒng)能及時（或即時）響應(yīng)外部事務(wù)的懇求，在規(guī)定的時間

內(nèi)完成對該事務(wù)的處理，并限制全部實時任務(wù)協(xié)調(diào)一樣地運行。實時系統(tǒng)的應(yīng)用領(lǐng)域確

定了它的特性是：①具有實時時鐘管理功能；②能進行過載愛護；③高牢靠性。

【解答】

及時性高牢靠性

?實時信息處理是實時應(yīng)用的一種，例如（）和（）都是實時信息處理的例子。

（華中科技大學(xué)2000年試題）

【解答】

飛機訂票系統(tǒng)，圖書資料查詢系統(tǒng)

?現(xiàn)代操作系統(tǒng)的基本功能是管理計算機系統(tǒng)的硬件，軟件資源，這些管理工作分

為A管理，B管理，C管理，D管理，E和通信事務(wù)管理。（東南大學(xué)2000年試題）

【解答】

A.處理機B.存儲器管理C.設(shè)備D.文件E.作業(yè)

【擴展】

選擇：操作系統(tǒng)的（）管理部分負責(zé)對進程調(diào)度。

A.主存儲器B.限制器C.運算器D.處理機這里要防止把處理機與系統(tǒng)結(jié)

構(gòu)中所說的處理機的組成混淆起來。選擇D。

?為了支持多道程序運行，存儲管理必須要實現(xiàn)的主要功能有（），（）和主存

擴充。（華中科技大學(xué)1997年試題）

【分析】

在多道程序運行環(huán)境下，程序員無法預(yù)知存儲管理模塊將把他們的程序安排到主存

的什么地方，而且程序員也盼望擺脫存儲地址，存儲空間大小等細微環(huán)節(jié)問題。因此存

儲管理模塊應(yīng)當(dāng)供應(yīng)地址重定位實力。另外，由于主存中可同時存放多道程序，為了防

止程序間相互干擾，存儲管理模塊必需供應(yīng)存儲愛護手段。

【解答】

存儲無關(guān)性，存儲愛護

?選擇：衡量整個計算機性能指標(biāo)的參數(shù)有：（北京理工大學(xué)1999年試題）

A.用戶接口。B.資源利用率。C.作業(yè)步的多少。D.吞吐量。E.周

轉(zhuǎn)時間。

【分析】

操作系統(tǒng)的性能與計算機系統(tǒng)工作的優(yōu)劣有著親密的聯(lián)系。評價操作系統(tǒng)的性能指

標(biāo)一般有：

系統(tǒng)的牢靠性；系統(tǒng)的吞吐率（量），是指系統(tǒng)在單位時間內(nèi)所處理的信息量，以每

小時或每天所處理的各類作業(yè)的數(shù)量來度量；系統(tǒng)響應(yīng)時間，是指用戶從提交作業(yè)到得

到計算結(jié)果這段時間，又稱周轉(zhuǎn)時間；系統(tǒng)資源利用率，指系統(tǒng)中各個部件，各種設(shè)備

的運用程度。它用在給定時間內(nèi)，某一設(shè)備實際運用時間所占的比例來度量；可移植性。

【解答】選擇B,D,Eo

【擴展】

推斷：資源的利用率高和系統(tǒng)的工作效率高是一回事O。（東南大學(xué)試題）

解答：系統(tǒng)的工作效率，也就是吞吐率。從上述分析可知，此題應(yīng)判錯誤。

3.2邏輯結(jié)構(gòu)

?推斷：數(shù)據(jù)庫管理程序須要調(diào)用操作系統(tǒng)程序，操作系統(tǒng)程序的實現(xiàn)也須要數(shù)據(jù)

庫系統(tǒng)的支持。O（大連理工大學(xué)2000年試題）

【分析】

從操作系統(tǒng)虛擬機的結(jié)構(gòu)來看，最核心層是裸機，緊挨著的一層是操作系統(tǒng)，這一

層把應(yīng)用程序和裸機隔離開來，使得應(yīng)用程序看起來似乎運行在一個虛擬機器上。題中

說法沒有正確反映應(yīng)用程序與操作系統(tǒng)的關(guān)系。

【解答】

錯誤。

?簡答：操作系統(tǒng)有哪幾種結(jié)構(gòu)設(shè)計方法？簡述其中之一的特點。（武漢大學(xué)2000

年試題）

【解答】

操作系統(tǒng)有無結(jié)構(gòu)，層次結(jié)構(gòu)和客戶/服務(wù)器模型等3種結(jié)構(gòu)設(shè)計方法。

現(xiàn)今大多數(shù)操作系統(tǒng)采納的是層次結(jié)構(gòu)。層次結(jié)構(gòu)是結(jié)構(gòu)設(shè)計方法的一種，運用這

種方法進行設(shè)計時，可以形成正確，結(jié)構(gòu)清晰的軟件系統(tǒng)，從而達到牢靠，可適應(yīng)，可

移植的設(shè)計目標(biāo)。在層次式結(jié)構(gòu)下，操作系統(tǒng)的各模塊應(yīng)處于什么位置，各模塊之間的

關(guān)系特別清晰。

?一個分層結(jié)構(gòu)操作系統(tǒng)由裸機，用戶，CPU調(diào)度和P,V操作，文件管理，作業(yè)

管理，內(nèi)存管理，設(shè)備管理，命令管理等部分組成。試按層次結(jié)構(gòu)的原則從內(nèi)到外將各

部分重新排列。（中國科學(xué)院計算技術(shù)探討所1997年試題）

【解答】

按層次結(jié)構(gòu)的原則從內(nèi)到外依次為：裸機，CPU調(diào)度和P,V操作，內(nèi)存管理，作

業(yè)管理，設(shè)備管理，文件管理，命令管理，用戶。

?在計算機系統(tǒng)中，為什么要區(qū)分管態(tài)與目態(tài)？操作系統(tǒng)為什么能為用戶程序供應(yīng)

各種服務(wù)？（西安電子科技大學(xué)1999年試題）

【解答】

操作系統(tǒng)是計算機系統(tǒng)中最重要的系統(tǒng)軟件，為了能正確地進行管理和限制，其本

身是不能被破壞的。因此，系統(tǒng)采納了區(qū)分處理機狀態(tài)的方法，為操作系統(tǒng)程序建立一

個愛護環(huán)境。這樣，用戶程序只能在管態(tài)下運行，只能執(zhí)行非特權(quán)指令，只能訪問自己

的存儲區(qū)，從而愛護了操作系統(tǒng)程序的正常運行。

操作系統(tǒng)虛擬機為用戶供應(yīng)了一個幫助解決問題的裝置。操作系統(tǒng)為用戶供應(yīng)兩種

類型的用戶界面,其一是命令接口，包括鍵盤命令，作業(yè)限制語言，圖形化用戶界面等;

其二是系統(tǒng)調(diào)用，又稱程序接口。通過這兩種界面，操作系統(tǒng)把它的全部操作命令的集

合呈現(xiàn)給用戶（或用戶程序），從而實現(xiàn)了為用戶服務(wù)。

?推斷:用戶程序通?？梢灾苯釉L問系統(tǒng)緩沖區(qū)中的數(shù)據(jù)。（）（大連理工大學(xué)2000

年試題）

【分析】

由前面敘述可知，用戶程序工作在目態(tài)下，只能直接訪問自己的存儲區(qū)，訪問系統(tǒng)

緩沖區(qū)必需通過操作系統(tǒng)的服務(wù)。

【解答】

錯誤。

?選擇：你認為下列哪幾種指令應(yīng)當(dāng)在核心狀態(tài)下執(zhí)行。（（上海交通大學(xué)1999年

試題,10分）

1.屏蔽全部中斷；2.讀時鐘周期；3.設(shè)置時鐘日期；4.改變存儲映像圖；5.存

取某地址單元的內(nèi)容；6.停機。

【解答】

1,2,4,6必需在核心狀態(tài)下執(zhí)行。

?簡答：試說明中斷在進程限制中的推動作用。（南開大學(xué)2000年試題）（8分）

【解答】

中斷是實現(xiàn)操作系統(tǒng)功能的基礎(chǔ)，是構(gòu)成多道程序運行環(huán)境的根本措施，是進程限

制中的推動力氣。例如，外設(shè)完成中斷或懇求運用外設(shè)的訪管中斷的出現(xiàn)，將導(dǎo)致I/O

管理進程投入運行；申請或釋放主存而發(fā)出的訪管中斷，將導(dǎo)致在主存中創(chuàng)建一個進程

而且開始運行；時鐘中斷或I/O完成中斷，可導(dǎo)致處理機調(diào)度工作的執(zhí)行；操作員從鍵

盤發(fā)出終止執(zhí)行的命令，可以終止當(dāng)前進程的運行。所以，中斷是進程運行的引導(dǎo)，是

它們被激活的驅(qū)動源。

?選擇：中斷發(fā)生時，由硬件愛護并更新程序指令計數(shù)器PC,而不是由軟件完成,

主要是為了（）（華中科技大學(xué)1998年試題）

A.提高處理速度。B.使中斷程序易于編制。C.節(jié)約內(nèi)存。D.能進入

中斷處理程序并能正確返回。

【分析】

一次中斷過程分為中斷進入（由硬件負責(zé)）和中斷處理過程（由軟件負責(zé)）。在中

斷進入過程中，首先保存PC,PS值，然后從中斷向量地址中得到PC,PS值放入寄存

器。軟件的中斷處理過程是，先保存現(xiàn)場信息和參數(shù)傳遞，再執(zhí)行中斷處理程序，最終

復(fù)原和退出中斷。簡要地說，一次中斷，兩次愛護現(xiàn)場。分步愛護現(xiàn)場的緣由是，進入

軟件的中斷處理后，PC,PS寄存器里被填上了新內(nèi)容，因此，PC,PS的愛護只能由

硬件完成。

【解答】

答案是D。

【擴展】

中斷響應(yīng)的實質(zhì)是什么？

從上述分析可知，中斷響應(yīng)的實質(zhì)是交換指令執(zhí)行地址和處理器狀態(tài)信息。

?填空：中斷優(yōu)先級是由硬件規(guī)定的，若要調(diào)整中斷的響應(yīng)次序，可通過。

（北京大學(xué)1997年試題）

【分析】

中斷優(yōu)先級是由硬件規(guī)定的,其次序是不能由軟件更改的。要調(diào)整中斷的響應(yīng)次序,

只能通過中斷屏蔽。

【解答】

中斷屏蔽

3.3用戶界面與OS實例

?在答卷上用連線把下面左右兩列詞連起來形成最恰當(dāng)?shù)?對。（東南大學(xué)2000年

試題）

左列：右列：

(1)Linux（1）面對對象

(2)UNIX（2）網(wǎng)絡(luò)操作系統(tǒng)

(3)WindowsNT（3）微內(nèi)核

(4)Mach3.0（4）自由軟件

(5)OS/2（5）C語言

【分析】

UNIX的核心代碼大部分是用C語言寫的。WindowsNT是當(dāng)然的網(wǎng)絡(luò)操作系統(tǒng)。

Linux是UNIX的一種，詳細講Linux是一套兼容于SystemV以及BSDUNIX的操作系

統(tǒng),也是遵循POSIX規(guī)范的一個操作系統(tǒng)。Linux于1991年4月由芬蘭人LinusBenedict

Torvalds在赫爾辛基大學(xué)獨立開發(fā)，并由此開創(chuàng)了自由軟件的先河。當(dāng)UNIX日漸龐大

困難而難以駕馭時，人們提出了Microkernel的概念，就是把Kernel去蕪存菁，僅留下

重要的部分，以此減低Kernel的困難度。Mach就是在Camegie-Mellon（卡耐基-梅隆

CMU）大學(xué)誕生的一個Microkernel（微核心）操作系統(tǒng)（1980年）。Mach最普遍的版

本是Mach2.5。它是很多商業(yè)UNIX如DECOSF/1,NextStep的基礎(chǔ)。Mach3.0才是真

正純粹的完全Microkernel化版本。

OS/2采納32位搶先多任務(wù)體系結(jié)構(gòu)，采納客戶機一服務(wù)器策略，在對等層環(huán)境既

是一個客戶機又是一個服務(wù)器。OS/2可以同時運行Windows3.1,DOS和OS/2的應(yīng)用

軟件。

OS/2的圖形用戶界面稱為WorkplaceShell。它運用面對對象的標(biāo)記和拖放界面（在

這一點上，WindowsNT也是）。用戶可以對工具和文件夾進行個人化以簡化對重要信息

的訪問。

【解答】

連線見下圖：

充圖I：

（1）面向?qū)ο?/p>

（2）掰絡(luò)操作系統(tǒng)

（3）微內(nèi)核

（4）自由軟件

（5）C語言

3.4進程的描述與限制

?什么是進程限制塊？試從進程管理，進程通信，中斷處理，文件管理，存儲

管理，設(shè)備管理的角度設(shè)計進程限制塊應(yīng)包含的項目。（北京大學(xué)1999年試題）

【分析】

北京大學(xué)1990年，1992年，1995年，1997年都以名詞說明的形式考查了PCB

這一知識點。1999年再次考查這一知識點，并提高了考試要求，即要求理解PCB結(jié)構(gòu)

中各重量的含義。

熟記我們在前面列出的進程限制原語的形式描述有助于加深對這個題的理解。

【解答】

進程限制塊（PCB）是為描述進程的運動變化過程而采納的一個與進程相聯(lián)系的數(shù)

據(jù)結(jié)構(gòu)，用于記錄系統(tǒng)管理進程所需的信息，描述進程的瞬間特征。它是進程的唯一實

體，操作系統(tǒng)通過PCB而感知進程的存在。

為了完成進程管理，進程通信，中斷處理，文件管理，存儲管理，設(shè)備管理等

各項任務(wù)，進程PCB結(jié)構(gòu)必需如下項目：

①進程的標(biāo)識符name：每個進程都必需有唯一的標(biāo)識符，可以用字符或編號表示。

在創(chuàng)建一個進程時，由創(chuàng)建者給出進程的標(biāo)識，唯一地標(biāo)識進程，與其他進程區(qū)分。

②進程當(dāng)前運行狀態(tài)status：說明本進程目前處于何種狀態(tài)（運行，就緒，等待）,

作為進程調(diào)度時安排處理機的主要依據(jù)。

③當(dāng)前隊列指針next：登記了處于同一狀態(tài)的下一個PCB的地址，以此將處于同

一狀態(tài)的全部進程鏈接起來。比如在一個就緒隊列中，當(dāng)前活動進程堵塞，則須要依據(jù)

當(dāng)前隊列指針調(diào)度下一個就緒進程進入運行。

④總鏈指針all_q_next：將全部的進程鏈接起來，進程PCB中的該項內(nèi)容總是指向

總鏈中的下一個PCB地址。這在有的場合是很便利的，比如當(dāng)創(chuàng)建一個進程時，須要推

斷創(chuàng)建者給出的標(biāo)識符名是否唯一，此時沿總鏈往下查找就比較便利。

⑤程序開始地址start_addi-：進程開始的地址。當(dāng)一個進程被調(diào)度進入運行時，須

要從今處獲得進程開始地址。

⑥CPU現(xiàn)場愛護區(qū)cpustatus：通常愛護的信息有工作寄存器，指令計數(shù)器以及程

序狀態(tài)字等，供進程調(diào)度時運用。當(dāng)一個進程由運行轉(zhuǎn)入其他狀態(tài)時，須要把這些信息

保存起來。當(dāng)一個進程投入運行時，又須要把這些內(nèi)容寫入相應(yīng)的寄存器。同時進行中

斷處理也須要保存CPU現(xiàn)場。

⑦通信信息communicationinformation：是指每個進程在運行過程中與別的進程進

行通信時所記錄的有關(guān)信息。

⑧家庭聯(lián)系processfamily：有的系統(tǒng)允許一個進程創(chuàng)建自己的子進程，這樣，會組

成一個進程家庭。在pcb中必需指明本進程與家庭的聯(lián)系，如它的子進程和父進程的標(biāo)

識符。

⑨占有資源清單own_resource,用于設(shè)備管理。

⑩進程優(yōu)先級priority,在中斷處理，進程調(diào)度過程中都須要比較進程之間的優(yōu)先

級。

上述項目是一般PCB結(jié)構(gòu)應(yīng)包含最基本內(nèi)容。不同的操作系統(tǒng)所運用的PCB結(jié)構(gòu)

是不同的。在UNIX系統(tǒng)中，為完成存儲管理，文件管理，還在PCB結(jié)構(gòu)中設(shè)有i結(jié)點

指針，主存地址，當(dāng)前中斷愛護區(qū)內(nèi)⑷等內(nèi)容。

?推斷:進程是基于多道程序技術(shù)而提出來的。其最基本的特性是并發(fā)性和動態(tài)性;

進程的執(zhí)行也即在各種基本狀態(tài)之間多次轉(zhuǎn)換的過程。但只有處于就緒，堵塞，執(zhí)行這

3種狀態(tài)的進程位于內(nèi)存。（中科院軟件所2000年試題）

【解答】

錯誤。①去掉并發(fā)性；②進程在新，死狀態(tài)上只經(jīng)過一次；③進程都在內(nèi)存中。

?一個單CPU的操作系統(tǒng)共有n個進程，不考慮進程狀態(tài)過渡的狀況：（北京大學(xué)

1995年試題）

①給出運行進程的個數(shù)。

②給出就緒進程的個數(shù)。

③給出等待進程的個數(shù)。

【分析】

單處理機在任一時刻只能處理一道程序，在不考慮狀態(tài)過渡的狀況下，任一進程只

有3種狀態(tài)，即運行，就緒和等待。但此時該系統(tǒng)其他條件未知（如資源安排狀況），

故無法確定就緒進程和等待進程的數(shù)目。

【解答】

①1。

②不肯定。

③不肯定。

?填空：為了實現(xiàn)進程由等待狀態(tài)轉(zhuǎn)換成就緒狀態(tài)的狀態(tài)變化，操作系統(tǒng)應(yīng)供應(yīng)

原語。(華中科技大學(xué)2001年試題)

【解答】

喚醒原語。

?什么是線程？試說明線程與進程的關(guān)系。(南京大學(xué)2000年試題)

【解答】

在引入線程的OS中，線程是進程中的一個實體，是被系統(tǒng)調(diào)度和分派的基本單位。

進程與線程既區(qū)分，又聯(lián)系。進程是任務(wù)調(diào)度的單位，也是系統(tǒng)資源的安排單位;

而線程是進程中的一條執(zhí)行路徑，當(dāng)系統(tǒng)支持多線程處理時，線程是任務(wù)調(diào)度的單位，

但不是系統(tǒng)資源的安排單位。每個進程至少有一個執(zhí)行線程。

3.5同步，互斥與通信

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

科學(xué)技術(shù)大學(xué)1998年試題)

#defineTRUE;#defineFALSE;

intflag[2];

flag[0]=flag[l]=FALSE;

entei^crtsec(i)inti;{

WHILE(flag[l-i]);

flag[i]=TRUE;}

leave-crtsec(i)inti;{

flag[i]=FALSE;}

processi:/*i=0ORi=1*/

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

INCRTICALSECTION

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

【解答】

一次僅允許一個進程運用的資源稱為臨界資源，在進程中對于臨界資源訪問的程序

段稱為臨界區(qū)。

從概念上講，系統(tǒng)中各進程在邏輯上是獨立的，它們可以按各自獨立的速度向前推

動。但由于它們共享某些臨界資源，而產(chǎn)生了臨界區(qū)問題。對于具有臨界區(qū)問題的共行

進程，它們之間必需互斥，以保證不會同時進入臨界區(qū)。

這種算法是不平安的。因為，在進入臨界區(qū)的操作enter-crtsec()不是一個原子操作,

假如兩個進程同時執(zhí)行完其循環(huán)(此前兩個flag均為False),則這兩個進程可以同時進

入臨界區(qū)。

?舉例說明P,V操作為什么要求設(shè)計成原語(即對同一信號量上的操作必需互

斥)。(北京大學(xué)1993年試題)

【分析】

這是一個概念題，要求考生對P,V操作有較深刻的理解。

【解答】

P操作的流程如下所示。

PROCEDUREP(S)BEGIN

lockoutinterrupts;

S:=S-l;

IFS<0THEN

BEGIN

status(q):=blockeda;

insert(Q,q);

unlockinterrupts;

scheduler;

END;

ELSEunlockinterruptsEND;

設(shè)信號量S的初值為1,當(dāng)一個P操作執(zhí)行完"S:=S-1"后，S的值為0,該P操作

不應(yīng)被堵塞。但若P操作不是一個原語，也就是說在一個P操作執(zhí)行的過程中可以有另

一個P操作同時在執(zhí)行，假如第2個P操作在第1個P操作執(zhí)行推斷語句“IFS<0”前也

執(zhí)行了"S:=S-1”操作，則這時的S值為-1。這時第一個P操作將會被堵塞。這樣的P操

作不符合P操作的語義。

同樣地，對于V操作，其流程為：

PROCEDUREV(S)BEGIN

lockoutinterrupts;

S:=S+1;

IFS<=0THEN

BEGIN

remove(Q,R);

status(R):=readya;

insert(RL,R);

length(RL):=length(RL)+1;

END;

unlockinterrupts;END;

設(shè)信號量s的初值為-1,當(dāng)一個V操作執(zhí)行完"S:=S+1”后，S的值為0,該V操

作應(yīng)當(dāng)喚醒一個被P操作堵塞的進程。但若V操作不是一個原語，也就是說在一個V

操作執(zhí)行的過程中可以有另一個V操作同時在執(zhí)行。假如第2個V操作在第1個V操

作執(zhí)行推斷語句"IFSN"前也執(zhí)行了"S:=S+1"操作，則這時的S值為1。這時第1個V

操作將不再去喚醒被堵塞的進程。這樣的V操作不符合V操作的語義。

同樣地，當(dāng)P操作的執(zhí)行過程中插入了V操作，也會出現(xiàn)不符合原語語義的狀況。

例如，在P操作執(zhí)行完"S:=S-1”后，S的值為-1,經(jīng)推斷，該進程應(yīng)當(dāng)被堵塞。但若在

進行推斷后堵塞進程前執(zhí)行完另外一個V操作，則該V操作并沒有可以喚醒的被堵塞的

進程。而當(dāng)V操作執(zhí)行完后接著執(zhí)行P操作時，該P操作仍將堵塞該進程，這一進程將

不被喚醒。

對于V操作的執(zhí)行過程中插入了P操作，也會出現(xiàn)不符合原語語義的狀況。例如，

在V操作執(zhí)行完"S:=S+1”后，S的值為1,該進程無需喚醒其他進程。但若在進行推

斷前執(zhí)行了一個P操作，則在后續(xù)操作中須要喚醒一個堵塞進程。

【擴展】

類似這一類有關(guān)概念的探討，首先須要明確概念的定義，然后再進行探討。在探討

的過程中，對可能發(fā)生的狀況應(yīng)分類探討。論述要清晰。

?一個系統(tǒng)有多個進程(>5)共同存在并同時工作，但只有5臺磁帶機。每個進

程最多可以申請一臺磁帶機工作。編制了下列程序來管理磁帶機：(北京大學(xué)1993年試

題)

申請：

PROCEDUREget_tape(VARx:integer);

VARi:integer;

tape_units:sharedinteger;

wait_tape:sharedboolean;

tape:sharedARRAY[0..4]OFinteger;

BEGIN

wait_tape:=true;

P(S)；

WHILE(wait_tape二true)DO

BEGIN

IFtape_units>0THEN

BEGIN

tape_units:=tape_units-l;

i:=0;

WHILE(i<=4)DO

BEGIN

IFtape[i]=0THEN

BEGIN

x:=i;

tape[i]:=1;

exit

END;

i：=i+1;

END;

wait_tape:二false;

END;

END;

V(S);

END;釋放：

PROCEDURErelease_tape(x:integer);

VARtape_units:sharedinteger;

tape:sharedARRAY[0..4]OFinteger;

BEGIN

P(S)；

tape_units:二tape_units+1;

tape[x]:=0;

V(S);

END;

說明：

shared表示該變量為多個進程共享。

S為信號量，初值為lo

其他變量初值為：

tape[i]=0(0<i<4)

tape_units=5

wait_tape=false

問：

①上述程序的問題在什么地方？

②改正它。

【分析】本題考查了臨界資源的屬性。臨界資源可以為多個進程共享，訪問，必需

是全部變量。

【解答】

程序的問題有：

(1)全部的共享變量應(yīng)是全局變量，而非局部變量。

(2)wait_tape也應(yīng)互斥共享，但在題中并未實現(xiàn)這一點。

改后的程序如下：

BEGIN

Vartape_units:sharedinteger;

tape:sharedARRAY[0..4]OFinteger;

wait_tape:sharedinteger;

S:integer;

PROCEDUREget_tape(varx:integer);

BEGIN

vari:integer;

P(S)；

wait_tape:=true;

WHILE(wait_tape二true)DO

BEGIN

IFtape_units>0THEN

BEGIN

tape_units:二tape_units-1;

i=0;

WHILE(i<=4)DO

BEGIN

x:=i;

tape[i]:=1;

exit

END;

i:=i+1;

END;

wait_tape:=folse;

END;

END;

V(S);

END;

PROCEDURErelease_tape(x:integer);

BEGIN

P(S)；

tape_units:=tape_units+1;

tape[x]:=0;

V(S);

End;

3.6算法設(shè)計題

?進程A和B利用公共緩沖池交換數(shù)據(jù)。設(shè)緩沖池有N個緩沖塊，進程A每次生

成一個數(shù)據(jù)塊存入一空緩沖區(qū)，進程B每次從緩沖池中取出一個滿的緩沖塊。試用信號

量及P,V操作實現(xiàn)進程A和B的同步。(中山大學(xué)1996年試題)

【分析】

本題是標(biāo)準(zhǔn)的生產(chǎn)者一消費者問題。與上題相比，運用了多緩沖區(qū)，須要增加一個

信號量。另外，環(huán)形緩沖池和環(huán)形隊列管理也是考點之一。

【解答】

Varmutex,empty,full:semaphore:1,n,0;

buffer:ARRAY[0..n-l]ofitem;

in,out:integer:=0,0;

BEGIN

COBEGIN:

A:BEGIN

LI:

produceadateblock;

P(empty);

P(mutex);

Buffer[in]:=nextp;

in:=(in+1)modn

V(mutex);

V(full);

GOTOLI;

END;

B:BEGIN

L2:

P(fuU);

P(mutex);

Nextpc:=Bufler[out];

out:二(out+1)modn

V(mutex);

V(empty);

consumetheiteminnextc

GOTOL2;

END;

GOTOL2;END;

【擴展】

此題應(yīng)留意以下幾點：

(1)在全部的程序中P(mutex)和V(mutex)應(yīng)成對出現(xiàn)。

⑵對資源信號量empty和foil的P,V操作也必需成對出現(xiàn)，但它們是處于不

同的程序中，正是這一點保證了互斥共享。

(3)在每個程序中的P操作依次不能顛倒，應(yīng)先執(zhí)行對資源信號量的操作，再執(zhí)

行對互斥信號量的操作，否則可能引起進程死鎖。

?設(shè)有一個具有N個信息元素的環(huán)形緩沖區(qū)，A進程依次地把信息寫入緩沖區(qū)，B

進程依次地從緩沖區(qū)讀出信息?；卮鹣铝袉栴}：(中國科學(xué)院軟件探討所1996年試題)

①敘述A,B兩進程的相互制約關(guān)系;②判別下列用RV操作表示的同步算法是

否正確？如不正確，試說明理由，并修改成正確算法。

VARbuffer:ARRAY0..N-1OFT;

in,out:O..N-1;VARSLS2:Semaphore;

SI:=0;S2:=N;in:=out:=0;

PROCEDUREA:

BEGIN

REPEAT

生產(chǎn)數(shù)據(jù)m;

P(S2);

Buffer(in):二m;

in:=(in+l)MODN;

V(S1);

forever

END;

PROCEDUREB:

BEGIN

REPEAT

V(S2);

m:=buffer(out);

消費m;

out:=(out+1)MODN;

P(S1)；

forever

END;

【分析】

本題是一個標(biāo)準(zhǔn)的生產(chǎn)者-消費者問題。題中所給的算法與標(biāo)準(zhǔn)算法不同，但考生

不能因此就說這個算法不正確?？忌毤氈路治鲈囶}中所給出的算法。

在本題中，進程B在運用緩沖區(qū)前(讀緩沖區(qū))無需進行任何P操作，即進程B

不會因任何緣由被堵塞。這與題目中的限制要求不相符。因此這個算法實現(xiàn)是錯誤的。

此外，對緩沖區(qū)的訪問也沒有用互斥信號量進行限制。

【解答】

①A和B兩進程的相互制約關(guān)系如下：

當(dāng)緩沖區(qū)滿時，A進程不可以寫，必需等待；當(dāng)緩沖區(qū)空時，B進程不可以讀，必

需等待。

②該算法有錯，它對讀進程進入臨界區(qū)未加限制。當(dāng)緩沖區(qū)為空時，也可以進入臨

界區(qū)讀信息。當(dāng)存在多個讀進程和多個寫進程時，還須要引入一個信號量SO以防止同

時讀或同時寫。

改進后的算法如下：

VARbuffer:ARRAY0..N-1OFT;

in,out:O..N-1;VARSO,SI,S2:Semaphore;

SO:=1;S1:=0;S2:=N;in:=out:=0;

PROCEDUREA:

BEGIN

REPEAT

生產(chǎn)數(shù)據(jù)m;

P(S2);

P(S0);

Buffer(in):=m;

in:=(in+1)MODN;

V(S0);

V(S1);

forever

END;

PROCEDUREB:

BEGIN

REPEAT

P(S1)；

P(so)；

m:=bufier(out);

out:=(out+1)MODN;

V(S0);

V(S2);

消費m;

forever

END;

【擴展】

本題是一類判別錯誤和改錯題。這類題目一般是用來檢查考生對一些典型算法的駕

馭程度的。在本題中，是考查考生對生產(chǎn)者一消費者問題的駕馭。解答這類問題時，首

先須要對標(biāo)準(zhǔn)算法嫻熟駕馭，其次，還需對算法的變化做到心中有數(shù)。不要把正確的變

化列為出錯點。例如本例中，假如題目中的算法給出的V操作依次與標(biāo)準(zhǔn)算法不同，考

生則不能認為其解答是錯誤的。因為在限制算法中，V操作的依次不會影響算法的正確

性。

?今有3個并發(fā)進程R,M和P,它們共享了一個可循環(huán)運用的緩沖區(qū)B,緩沖區(qū)

B共有N個單元。進程R負責(zé)從輸入設(shè)備讀信息，每讀一個字符后，把它存放在緩沖區(qū)

B的一個單元中；進程M負責(zé)處理讀入的字符，若發(fā)覺讀入的字符中有空格符，則把它

改成“，“；進程P負責(zé)把處理后的字符取出并打印輸出。當(dāng)緩沖區(qū)單元中的字符被進程

P取出后，則又可用來存放下一次讀入的字符。請用P,V操作為同步機制寫出它們能

正確并發(fā)執(zhí)行的程序。(南京大學(xué)1997年試題)

【分析】

此題是3個進程之間的同步問題。明顯R與M,R與P,P與M之間均應(yīng)有一緩

沖區(qū)指針。與之對應(yīng)有3個信號量。

【解答】

Varfull,changed,empty,mutex:integer;

VarfullP,changedP,emptyP:integer;

Varch:char;

VarcharrayARRAY[0..n]ofchar;

fullP:=0;

emptyP:=0;

changedP:=0;

fidl:=0;

empty:二n;

changed:=0;

mutex:=0;R:

BEGIN

getchar(ch);

P(Empty);

P(mutex);

charray[fullP]:=ch;

fullP:=(fullP+1)modn;

V(mutex);

V(changed);

END;

M:

BEGIN

P(changed);

P(mutex);

ch:=charray[changedP];

ifch=*'then

ch=','；

changedP:=(changedP+1)modn;

V(fuU);

V(changed);

END;

P:

BEGIN

P(fuU);

P(mutex);

ch:=charray[emptyP];

putchar(ch);

emptyP:二(emptyP+1)modn;

V(mutex);

V(empty);

END;

【擴展】

本題在進程同步之外，還考查了考生基本編程實力及環(huán)形隊列操作。考生應(yīng)當(dāng)留意

這個信號。盡管P,V操作本身已有肯定難度，但仍舊存在結(jié)合其他知識點命題，以進

一步增加難度的可能。

我們可以列舉一些知識點綜合的方向。比如說，在讀者一寫者問題中，可以結(jié)合

UNIX文件系統(tǒng)附帶考查文件打開，關(guān)閉等操作；可以把P,V操作和實際的資源管理

問題結(jié)合起來，等等。

?多個進程共享一個文件，其中只讀文件的稱之為讀者，其余只寫文件的稱為寫者。

讀者可以同時讀，但是寫者只能獨立地寫。(中科院軟件所1995年試題)

①說明進程間的相互制約關(guān)系，應(yīng)設(shè)哪些信號量？

②用P,V操作寫出其同步算法。

③修改上述的同步算法，使得它對寫者優(yōu)先，即一旦有寫者到達，后續(xù)的讀者都必

需等待，而無論是否有讀者在讀文件。

【分析】

本題要求寫出的算法與前面的題目略有不同。這里的兩類進程(讀者和寫者進程)

的限制是不相同的。對于寫者進程，只能獨占文件，即當(dāng)有寫者進程時不能有其他進程

運行；對于讀者進程，可以與其他的讀者進程共享文件，即當(dāng)有讀者進程的，只允許其

他的讀者進程運行，而不允許寫者進程運行。此外，當(dāng)全部正在運行的讀者進程運行完

畢后，才允許其他的寫者進程進入。

為了達到這一限制效果，我們引入了一個變量rc,用于記錄當(dāng)前正在運行的讀者進

程數(shù)。每個讀者進程進入系統(tǒng)后須對rc值加1。當(dāng)rc值由0變?yōu)?時，說明是第一個讀

者進程進入，因此須要該讀者進程對限制寫者進程的信號量進行P操作，以便與寫者進

程互斥運行；當(dāng)rc值由非。值增加時，說明不是第一個讀者進程，此時限制寫者進程的

信號量已經(jīng)過P操作限制禁止寫者進程進入，因此不須要再次對該信號量進行P操作。

當(dāng)讀者進程退出時，須對rc做減1操作。如發(fā)覺減1后rc值變?yōu)?,說明是最終一

個讀者進程退出，因此須要該讀者進程對限制寫者進程的信號量進行V操作，以便使寫

者進程能夠進入。

【解答】

①進程間的相互制約關(guān)系有三類。一是讀者之間允許同時讀；二是讀者與寫者之間

須互斥進行；三是寫者之間須互斥寫。

②進程間的限制算法如下所示。

BEGIN

integermutexl,mutex2,rc;

mutex1:=1;

mutex2:二1;

rc:=0;

COBEGIN

reader:BEGIN

P(mutexl);

rc:=rc+1;

IFrc=1THENP(mutex2);

V(mutexl);

Readingthefile;

P(mutexl);

rc:=rc-l;

IFrc=0THENV(mutex2);

V(mutexl);

END;

writer:BEGIN

P(mutex2);

Writeingthefile;

V(mutex2);

END;

COENDEND;

③為了提高寫者的優(yōu)先級，我們增加一個信號量W,用以在寫進程到達時封鎖后續(xù)

的讀者進程。相應(yīng)的限制算法如下：

BEGIN

integermutex1,mutex2,rc,w;

mutex1:=1;

mutex2:=1;

rc:=0;

w:二1;

COBEGIN

reader:BEGIN

P(w);

P(mutexl);

rc:=rc+1;

IFrc=1THENP(mutex2);

V(mutexl);

V(w);

ReadingtheFILE;

P(mutexl);

rc:=rc-l;

IFrc=0THENV(mutex2);

V(mutexl);

END;

writer:BEGIN

P(w);

P(mutex2);

WriteingtheFILE;

V(mutex2);

V(w);

END;

COENDEND;

【擴展】

對于可由一類進程多次訪問，而不同類的進程必需互斥訪問的資源的限制，是進程

限制中常見的一類問題。本題是這類問題中的一個典型，它給出了對于這類資源的限制

方法，即采納一個資源計數(shù)變量rc進行限制。把對于該資源的訪問限制變成對變量rc

的訪問。這時，資源計數(shù)變量rc是一個臨界資源，須要用信號量對其進行訪問限制。

?有橋如圖所示。（北京大學(xué)1992年試題）

車流如箭頭所示。橋上不允許兩車交會，但允許同方向多輛車依次通行（即橋上可

以有多個同方向的車）。用P,V操作實現(xiàn)交通管理以防止橋上堵塞。

【分析】

由于橋上不允許兩車會面，故橋應(yīng)被互斥訪問，而同一方向上允很多輛車依次通過,

即臨界區(qū)允很多個實例訪問。用一個信號量來互斥訪問臨界區(qū)。由于不能允許某一方向

的車完全“限制"橋，應(yīng)保證最多某一方向上連續(xù)通過肯定數(shù)量的車后，必需讓另一方向

上的車通過。用另兩個信號量來實現(xiàn)這一點。

【解答】

BEGIN

Varintegermutex，availn,avails;

availn=m;

avails=m;

mutex=0;

COBEGIN

South:BEGIN

LI:

P(avails);

P(mutex);

Crossthebridge;

V(mutex);

V(availn);

END;

North:BEGIN

LI:

P(availn);

P(mutex);

Crossthebridge;

V(mutex);

V(avails);

END;

COEND;

END;

【擴展】

在解此類題目時，首先應(yīng)分析清晰此題的臨界區(qū)是什么，題目對臨界區(qū)的共享的約

束條件是什么，再分析應(yīng)設(shè)幾個信號量，各信號量的作用是什么。當(dāng)全部問題都分析清

晰之后再做題。另外當(dāng)遇到實際問題時，依據(jù)實際狀況，留意分析是否應(yīng)補充約束條件。

在實際考試中最好把全部分析過程，補充的約束條件寫出，一方面扶植解題，一方面扶

植老師閱卷。

3.7進程通信

?圖所示的是高級通信原語SEND和RECEIVE不完整的框圖。請?zhí)畛溥m當(dāng)?shù)腜,V

操作，并說明所用信號量的意義和初值。(中國科學(xué)院軟件探討所1994年試題)

申詢一科總區(qū)

消且義消g區(qū)

從消鳥池上摘下一消總

消息區(qū)挖人落自於

消自淺樓恢區(qū)

將放消總區(qū)

【分析】

本題是一個生產(chǎn)者一消費者問題，與標(biāo)準(zhǔn)的生產(chǎn)者一消費者問題的不同之處在于本

題的消息緩沖區(qū)的個數(shù)是無限制的，因此，不須要生產(chǎn)者一消費者問題解答中的信號量

availo在框圖中所給出的信號量就是限制消息個數(shù)的信號量fiill。為了正確地限制程序流

程，我們還要加入對應(yīng)于生產(chǎn)者一消費者問題中的信號量mutex,以限制對消息鏈的互

斥訪問。

【解答】

框圖中所缺的步驟如下：

①P(S1)

②V(S1)

③P(S2)

@P(S1)

⑤V(S1)

其中，S1是用于限制互斥訪問消息鏈的互斥信號量，其初值為1；S2是用于記錄消

息個數(shù)的同步信號量，其初值為0。

?消息緩沖通信技術(shù)是一種高級通信機制，由Hansen首先提出。（北京大學(xué)1997

年試題）

①試敘述高級通信機制與低級通信機制P,V原語操作的主要區(qū)分。

②請給出消息緩沖機制（有界緩沖）的基本原理。

③消息緩沖通信機制（有界緩沖）中供應(yīng)發(fā)送原語Send（receiver,a）,調(diào)用參數(shù)

a表示發(fā)送消息的內(nèi)存區(qū)首地址,試設(shè)計相應(yīng)的數(shù)據(jù)結(jié)構(gòu),并用P,V原語操作實現(xiàn)Send

原語。

【解答】

①P,V操作是一種低級通信機制，它們作為同步工具用在進程同步和互斥上是特

別有效的，但是作為通信工具，則不夠志向。而高級通信機制是指用戶可直接利用操作

系統(tǒng)所供應(yīng)的一組通信命令，高效傳送大量數(shù)據(jù)的一種通信方式。二者的主要區(qū)分如下:

P,V操作效率較低。

通信對用戶不透亮。

②消息緩沖通信機制，首先由美國的Hansan提出，并在RC4000上實現(xiàn)。在這種

通信機制中，發(fā)送進程利用Send原語，將消息直接發(fā)送給接收進程。接收進程利用

Receive原語接受消息。該機制主要利用的數(shù)據(jù)結(jié)構(gòu)是消息緩沖區(qū)。

發(fā)送進程在利用發(fā)送原語發(fā)送消息前，在自己的內(nèi)存空間里設(shè)置一發(fā)送區(qū)，把待發(fā)

送的正文，發(fā)送進程標(biāo)記符，消息長度等信息填入，然后調(diào)用發(fā)送原語，把消息發(fā)送給

目標(biāo)進程。發(fā)送原語首先依據(jù)發(fā)送區(qū)中設(shè)置的長度來申請一個緩沖區(qū)i,接著把發(fā)送區(qū)中

的正文信息復(fù)制到緩沖區(qū)i中。為了能將i掛在接收進程的消息隊列上，應(yīng)先獲得接收進

程的內(nèi)部標(biāo)記符。由于該隊列屬于臨界資源，應(yīng)執(zhí)行同步操作。

接收進程調(diào)用接收原語receive。，從自己的消息緩沖隊列中，摘下第一個消息緩沖

區(qū)i,并將其中的消息正文拷貝到指定的消息接收區(qū)內(nèi)。

③消息緩沖區(qū)可描述為：

typemessagebuffer=record

sender;發(fā)送者進程標(biāo)記符

size;消息長度

text;消息正文

next;指向下一個消息緩沖區(qū)的指針

end;

發(fā)送原語：

PROCEDUREsend（receive,a）

〃接收進程標(biāo)記receive,發(fā)送區(qū)a

BEGIN

getbufi(a.size,i);

i.sender:=a.sender;

i.size:二a.size;

i.text:二a.text;

i.next:=0;

getid(PCB.set,receive.j);

P(j.mutex);

insert(j.mq,i);

V(j.mutex);

V(j.sm);

END;

接收原語：

PROCEDUREreceive(b)

〃發(fā)送區(qū)b

BEGIN

j:二internalname;

P(j.sm);

P(j.mutex);

remove(j.mq,i);

V(j.mutex);

b.sender:=i.sender;

b.size:二i.size;

b.text:=i.text;

END;

3.8進程調(diào)度

?設(shè)某系統(tǒng)進程的狀態(tài)除了最基本的三種狀態(tài)外，還增加了創(chuàng)建狀態(tài)，延遲狀態(tài)和

完成狀態(tài)。試畫出系統(tǒng)的進程狀態(tài)變遷圖，并標(biāo)明狀態(tài)變遷可能的緣由。（華中科技大學(xué)

2001年試題）

【解答】

進程狀態(tài)變遷圖及可能的緣由如圖所示:

3.9死鎖

?用信號量及p,v操作解生產(chǎn)者-消費者問題，并改動操作使之產(chǎn)生死鎖。（南開

大學(xué)1995年試題）

【分析】

本題是關(guān)于P,V操作及生產(chǎn)者一消費者問題的一個基本問題。在這里主要考查考

生對生產(chǎn)者一消費者問題的理解和對死鎖問題的理解。

【解答】

生產(chǎn)者-消費者問題的流程如下：

BEGINintegermutex,avail,full;

mutex:=1;

avail:=n;

fuU:=0;

COBEGIN

producer:BEGIN

LI:producenextproduct;

P(avail);

P(mutex);

addTObuffer;

V(foU);

V(mutex);

gotoLI;

END;

consumer:BEGIN

L2:P(fuU);

P(mutex);

takefrombuffer;

V(avail);

V(mutex);

consumeproduct;

gotoL2;

END;

COEND

END;

要使該操作產(chǎn)生死鎖，只需改動P操作的依次。能產(chǎn)生死鎖的操作流程如下:

BEGINintegermutex,avail,full;

mutex:=1;

avail:=n;

faU:=0;

COBEGIN

producer:BEGIN

LI:producenextproduct;

P(mutex);

P(avail);

addTObuffer;

V(fuU);

V(mutex);

gotoLI;

END;

consumer:BEGIN

L2:P(mutex);

P(fiiU);

takefrombuffer;

V(avail);

V(mutex);

consumeproduct;

gotoL2;

END;

COEND

END;

在這個流程里，由于生產(chǎn)者和消費者在生產(chǎn)和消費之前都要對信號量mutex進行P

操作，所以，會導(dǎo)致生產(chǎn)者進入臨界區(qū)后(對mutex進行P操作后)，因無緩沖區(qū)而被

堵塞；消費者由于無法進入臨界區(qū)，無法釋放緩沖區(qū)，從而導(dǎo)致死鎖。同樣地，當(dāng)消費

者進入臨界區(qū)后(對mutex進行P操作后)，由于無產(chǎn)品可供運用被堵塞；而生產(chǎn)者由

于無法進入臨界區(qū)，無法生產(chǎn)產(chǎn)品，從而導(dǎo)致死鎖。

【擴展】

產(chǎn)生死鎖是在用信號量進行流程限制過程中常會遇到的一個問題。何時會發(fā)生死

鎖。如何避開死鎖，是在考研中?？嫉膯栴}。在本題中，要求用經(jīng)典的生產(chǎn)者-消費者問

題構(gòu)造出死鎖現(xiàn)象，是一種常見的題型。此外，還會有要求分析給定流程限制是否會產(chǎn)

生死鎖等類似的問題。

?用信號量及P,V操作解生產(chǎn)者-消費者問題，并改動操作使之產(chǎn)生死鎖。(南開

大學(xué)1995年試題)

【分析】

本題是關(guān)于P,V操作及生產(chǎn)者一消費者問題的一個基本問題。在這里主要考查考

生對生產(chǎn)者一消費者問題的理解和對死鎖問題的理解。

【解答】

生產(chǎn)者-消費者問題的流程如下：

BEGINintegermutex,avail,full;

mutex:=1;

avail:二n;

fuU:=0;

COBEGIN

producer:BEGIN

LI:producenextproduct;

P(avail);

P(mutex);

addTObuffer;

V(fuU);

V(mutex);

gotoLI;

END;

consumer:BEGIN

L2:P(fon);

P(mutex);

takefrombuffer;

V(avail);

V(mutex);

consumeproduct;

gotoL2;

END;

COEND

END;

要使該操作產(chǎn)生死鎖，只需改動P操作的依次。能產(chǎn)生死鎖的操作流程如下:

BEGINintegermutex,avail,full;

mutex:=1;

avail:二n;

fuU:=0;

COBEGIN

producer:BEGIN

LI:producenextproduct;

P(mutex);

P(avail);

addTObuffer;

V(fuU);

V(mutex);

gotoLI;

END;

consumer:BEGIN

L2:P(mutex);

P(fuU);

takefrombuffer;

V(avail);

V(mutex);

consumeproduct;

gotoL2;

END;

COEND

END;

在這個流程里，由于生產(chǎn)者和消費者在生產(chǎn)和消費之前都要對信號量mutex進行P

操作，所以，會導(dǎo)致生產(chǎn)者進入臨界區(qū)后（對mutex進行P操作后），因無緩沖區(qū)而被

堵塞；消費者由于無法進入臨界區(qū)，無法釋放緩沖區(qū)，從而導(dǎo)致死鎖。同樣地，當(dāng)消費

者進入臨界區(qū)后（對mutex進行P操作后），由于無產(chǎn)品可供運用被堵塞；而生產(chǎn)者由

于無法進入臨界區(qū)，無法生產(chǎn)產(chǎn)品，從而導(dǎo)致死鎖。

【擴展】

產(chǎn)生死鎖是在用信號量進行流程限制過程中常會遇到的一個問題。何時會發(fā)生死

鎖。如何避開死鎖，是在考研中?？嫉膯栴}。在本題中，要求用經(jīng)典的生產(chǎn)者-消費者問

題構(gòu)造出死鎖現(xiàn)象，是一種常見的題型。此外，還會有要求分析給定流程限制是否會產(chǎn)

生死鎖等類似的問題。

?分析下面信號量解決哲學(xué)家進餐問題的同步算法是否滿意同步機制的準(zhǔn)則。若不

滿意，說明為什么，并給出滿意同步機制準(zhǔn)則的同步算法。(中科院軟件所1998年試題)

VARfork:ARRAY[0..4]OFsemaphore;

fork[0]:=fork[l]:=fork[2]:二fbrk[3]:=fork[4]:=1;

PARBEGIN

Pi:REPEAT/*第i個哲學(xué)家的生活過程*/

ThinkFORWhile;

P(fork[i]);

P(FOR[(i+l)MOD5]);

EatFORWHILE;

V(fork[i]);

V(fbrk[(i+1)MOD5]);

UNTILfalse

BXREND

【分析】

哲學(xué)家進餐問題是進程同步與互斥中的一個典型問題。本題要求分析算法是否滿意

同步機制的準(zhǔn)則，即每次至多有一個進程進入臨界區(qū)，進程應(yīng)在有限時間內(nèi)進入臨界區(qū),

進程在臨界區(qū)內(nèi)停留有限時間。本題所給出的算法會在特定狀況下產(chǎn)生死鎖，因此無法

滿意同步機制的準(zhǔn)則中的“有限等待‘準(zhǔn)則。為了解決這一問題，我們可以用額外的信號

量來限制對臨界資源的訪問，避開死鎖。

【解答】

上述同步算法不滿意同步機制的準(zhǔn)則中的“有限等待”準(zhǔn)則。當(dāng)每個哲學(xué)家都只拿到

一把叉子時，發(fā)生死鎖。

一種改進的算法如下：

VARfork:ARRAY[0..4]OFsemaphore;

VARmutex:semaphore;

fork[0]:=fork[l]:=fork[2]:=fork[3]:=fork[4]:=1;

mutex:=1;

PARBEGIN

Pi:REPEAT/*第i個哲學(xué)家的生活過程*/

ThinkFo