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

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

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

【解答】

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

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

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

算機(jī)之間起到接口的作用。

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

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

【分析】

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

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

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

運(yùn)行在用戶(hù)態(tài)下。

【解答】

錯(cuò)誤。

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

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

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

【解答】

選擇C。

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

年試題）

【分析】

多道運(yùn)行的特征是多道性，宏觀上并行，彳散觀上串行。多道性是指計(jì)算機(jī)主存中同

時(shí)存放幾道相互獨(dú)立的程序。宏觀上并行是指同時(shí)進(jìn)入系統(tǒng)的幾道程序都處于運(yùn)行過(guò)程

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

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

【解答】

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

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

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

【分析】

時(shí)間片越小，進(jìn)程切換所用的開(kāi)銷(xiāo)就相對(duì)越大。因此時(shí)間片不是越小越好，一般運(yùn)

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

【解答】

錯(cuò)誤。

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

【分析】

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

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

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

定了它的特性是：①具有實(shí)時(shí)時(shí)鐘管理功能；②能進(jìn)行過(guò)載愛(ài)護(hù)；③高牢靠性。

【解答】

及時(shí)性高牢靠性

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

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

【解答】

飛機(jī)訂票系統(tǒng)，圖書(shū)資料查詢(xún)系統(tǒng)

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

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

【解答】

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

【擴(kuò)展】

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

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

構(gòu)中所說(shuō)的處理機(jī)的組成混淆起來(lái)。選擇D。

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

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

【分析】

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

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

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

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

【解答】

存儲(chǔ)無(wú)關(guān)性，存儲(chǔ)愛(ài)護(hù)

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

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

轉(zhuǎn)時(shí)間。

【分析】

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

標(biāo)一般有：

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

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

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

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

【解答】選擇B,D,Eo

【擴(kuò)展】

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

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

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

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

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

【分析】

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

層把應(yīng)用程序和裸機(jī)隔離開(kāi)來(lái)，使得應(yīng)用程序看起來(lái)似乎運(yùn)行在一個(gè)虛擬機(jī)器上。題中

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

【解答】

錯(cuò)誤。

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

年試題）

【解答】

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

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

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

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

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

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

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

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

【解答】

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

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

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

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

【解答】

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

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

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

的存儲(chǔ)區(qū)，從而愛(ài)護(hù)了操作系統(tǒng)程序的正常運(yùn)行。

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

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

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

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

?推斷:用戶(hù)程序通常可以直接訪問(wèn)系統(tǒng)緩沖區(qū)中的數(shù)據(jù)。（）（大連理工大學(xué)2000

年試題）

【分析】

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

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

【解答】

錯(cuò)誤。

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

試題,10分）

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

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

【解答】

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

?簡(jiǎn)答：試說(shuō)明中斷在進(jìn)程限制中的推動(dòng)作用。（南開(kāi)大學(xué)2000年試題）（8分）

【解答】

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

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

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

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

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

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

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

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

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

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

【分析】

一次中斷過(guò)程分為中斷進(jìn)入（由硬件負(fù)責(zé)）和中斷處理過(guò)程（由軟件負(fù)責(zé)）。在中

斷進(jìn)入過(guò)程中，首先保存PC,PS值，然后從中斷向量地址中得到PC,PS值放入寄存

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

復(fù)原和退出中斷。簡(jiǎn)要地說(shuō)，一次中斷，兩次愛(ài)護(hù)現(xiàn)場(chǎng)。分步愛(ài)護(hù)現(xiàn)場(chǎng)的緣由是，進(jìn)入

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

硬件完成。

【解答】

答案是D。

【擴(kuò)展】

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

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

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

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

【分析】

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

只能通過(guò)中斷屏蔽。

【解答】

中斷屏蔽

3.3用戶(hù)界面與OS實(shí)例

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

試題）

左列：右列：

(1)Linux（1）面對(duì)對(duì)象

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

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

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

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

【分析】

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

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

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

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

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

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

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

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

正純粹的完全Microkernel化版本。

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

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

軟件。

OS/2的圖形用戶(hù)界面稱(chēng)為WorkplaceShell。它運(yùn)用面對(duì)對(duì)象的標(biāo)記和拖放界面（在

這一點(diǎn)上，WindowsNT也是）。用戶(hù)可以對(duì)工具和文件夾進(jìn)行個(gè)人化以簡(jiǎn)化對(duì)重要信息

的訪問(wèn)。

【解答】

連線見(jiàn)下圖：

充圖I：

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

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

（3）微內(nèi)核

（4）自由軟件

（5）C語(yǔ)言

3.4進(jìn)程的描述與限制

?什么是進(jìn)程限制塊？試從進(jìn)程管理，進(jìn)程通信，中斷處理，文件管理，存儲(chǔ)

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

【分析】

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

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

中各重量的含義。

熟記我們?cè)谇懊媪谐龅倪M(jìn)程限制原語(yǔ)的形式描述有助于加深對(duì)這個(gè)題的理解。

【解答】

進(jìn)程限制塊（PCB）是為描述進(jìn)程的運(yùn)動(dòng)變化過(guò)程而采納的一個(gè)與進(jìn)程相聯(lián)系的數(shù)

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

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

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

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

①進(jìn)程的標(biāo)識(shí)符name：每個(gè)進(jìn)程都必需有唯一的標(biāo)識(shí)符，可以用字符或編號(hào)表示。

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

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

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

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

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

當(dāng)前隊(duì)列指針調(diào)度下一個(gè)就緒進(jìn)程進(jìn)入運(yùn)行。

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

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

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

⑤程序開(kāi)始地址start_addi-：進(jìn)程開(kāi)始的地址。當(dāng)一個(gè)進(jìn)程被調(diào)度進(jìn)入運(yùn)行時(shí)，須

要從今處獲得進(jìn)程開(kāi)始地址。

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

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

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

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

⑦通信信息communicationinformation：是指每個(gè)進(jìn)程在運(yùn)行過(guò)程中與別的進(jìn)程進(jìn)

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

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

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

識(shí)符。

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

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

級(jí)。

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

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

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

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

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

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

【解答】

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

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

1995年試題）

①給出運(yùn)行進(jìn)程的個(gè)數(shù)。

②給出就緒進(jìn)程的個(gè)數(shù)。

③給出等待進(jìn)程的個(gè)數(shù)。

【分析】

單處理機(jī)在任一時(shí)刻只能處理一道程序，在不考慮狀態(tài)過(guò)渡的狀況下，任一進(jìn)程只

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

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

【解答】

①1。

②不肯定。

③不肯定。

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

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

【解答】

喚醒原語(yǔ)。

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

【解答】

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

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

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

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

3.5同步，互斥與通信

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

科學(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);/*進(jìn)入臨界區(qū)*/

INCRTICALSECTION

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

【解答】

一次僅允許一個(gè)進(jìn)程運(yùn)用的資源稱(chēng)為臨界資源，在進(jìn)程中對(duì)于臨界資源訪問(wèn)的程序

段稱(chēng)為臨界區(qū)。

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

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

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

這種算法是不平安的。因?yàn)?，在進(jìn)入臨界區(qū)的操作enter-crtsec()不是一個(gè)原子操作,

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

入臨界區(qū)。

?舉例說(shuō)明P,V操作為什么要求設(shè)計(jì)成原語(yǔ)(即對(duì)同一信號(hào)量上的操作必需互

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

【分析】

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

【解答】

P操作的流程如下所示。

PROCEDUREP(S)BEGIN

lockoutinterrupts;

S:=S-l;

IFS<0THEN

BEGIN

status(q):=blockeda;

insert(Q,q);

unlockinterrupts;

scheduler;

END;

ELSEunlockinterruptsEND;

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

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

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

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

作不符合P操作的語(yǔ)義。

同樣地，對(duì)于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è)信號(hào)量s的初值為-1,當(dāng)一個(gè)V操作執(zhí)行完"S:=S+1”后，S的值為0,該V操

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

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

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

操作將不再去喚醒被堵塞的進(jìn)程。這樣的V操作不符合V操作的語(yǔ)義。

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

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

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

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

不被喚醒。

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

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

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

【擴(kuò)展】

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

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

?一個(gè)系統(tǒng)有多個(gè)進(jìn)程(>5)共同存在并同時(shí)工作，但只有5臺(tái)磁帶機(jī)。每個(gè)進(jìn)

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

題)

申請(qǐng)：

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;

說(shuō)明：

shared表示該變量為多個(gè)進(jìn)程共享。

S為信號(hào)量，初值為lo

其他變量初值為：

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

tape_units=5

wait_tape=false

問(wèn)：

①上述程序的問(wèn)題在什么地方？

②改正它。

【分析】本題考查了臨界資源的屬性。臨界資源可以為多個(gè)進(jìn)程共享，訪問(wèn)，必需

是全部變量。

【解答】

程序的問(wèn)題有：

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

(2)wait_tape也應(yīng)互斥共享，但在題中并未實(shí)現(xiàn)這一點(diǎ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è)計(jì)題

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

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

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

【分析】

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

信號(hào)量。另外，環(huán)形緩沖池和環(huán)形隊(duì)列管理也是考點(diǎ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;

【擴(kuò)展】

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

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

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

同的程序中，正是這一點(diǎn)保證了互斥共享。

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

行對(duì)互斥信號(hào)量的操作，否則可能引起進(jìn)程死鎖。

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

進(jìn)程依次地從緩沖區(qū)讀出信息。回答下列問(wèn)題：(中國(guó)科學(xué)院軟件探討所1996年試題)

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

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

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);

消費(fèi)m;

out:=(out+1)MODN;

P(S1)；

forever

END;

【分析】

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

不能因此就說(shuō)這個(gè)算法不正確?？忌毤?xì)致分析試題中所給出的算法。

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

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

此外，對(duì)緩沖區(qū)的訪問(wèn)也沒(méi)有用互斥信號(hào)量進(jìn)行限制。

【解答】

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

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

需等待。

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

界區(qū)讀信息。當(dāng)存在多個(gè)讀進(jìn)程和多個(gè)寫(xiě)進(jìn)程時(shí)，還須要引入一個(gè)信號(hào)量SO以防止同

時(shí)讀或同時(shí)寫(xiě)。

改進(jìn)后的算法如下：

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);

消費(fèi)m;

forever

END;

【擴(kuò)展】

本題是一類(lèi)判別錯(cuò)誤和改錯(cuò)題。這類(lèi)題目一般是用來(lái)檢查考生對(duì)一些典型算法的駕

馭程度的。在本題中，是考查考生對(duì)生產(chǎn)者一消費(fèi)者問(wèn)題的駕馭。解答這類(lèi)問(wèn)題時(shí)，首

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

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

生則不能認(rèn)為其解答是錯(cuò)誤的。因?yàn)樵谙拗扑惴ㄖ?，V操作的依次不會(huì)影響算法的正確

性。

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

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

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

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

P取出后，則又可用來(lái)存放下一次讀入的字符。請(qǐng)用P,V操作為同步機(jī)制寫(xiě)出它們能

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

【分析】

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

沖區(qū)指針。與之對(duì)應(yīng)有3個(gè)信號(hào)量。

【解答】

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;

【擴(kuò)展】

本題在進(jìn)程同步之外，還考查了考生基本編程實(shí)力及環(huán)形隊(duì)列操作?？忌鷳?yīng)當(dāng)留意

這個(gè)信號(hào)。盡管P,V操作本身已有肯定難度，但仍舊存在結(jié)合其他知識(shí)點(diǎn)命題，以進(jìn)

一步增加難度的可能。

我們可以列舉一些知識(shí)點(diǎn)綜合的方向。比如說(shuō)，在讀者一寫(xiě)者問(wèn)題中，可以結(jié)合

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

問(wèn)題結(jié)合起來(lái)，等等。

?多個(gè)進(jìn)程共享一個(gè)文件，其中只讀文件的稱(chēng)之為讀者，其余只寫(xiě)文件的稱(chēng)為寫(xiě)者。

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

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

②用P,V操作寫(xiě)出其同步算法。

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

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

【分析】

本題要求寫(xiě)出的算法與前面的題目略有不同。這里的兩類(lèi)進(jìn)程(讀者和寫(xiě)者進(jìn)程)

的限制是不相同的。對(duì)于寫(xiě)者進(jìn)程，只能獨(dú)占文件，即當(dāng)有寫(xiě)者進(jìn)程時(shí)不能有其他進(jìn)程

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

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

畢后，才允許其他的寫(xiě)者進(jìn)程進(jìn)入。

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

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

者進(jìn)程進(jìn)入，因此須要該讀者進(jìn)程對(duì)限制寫(xiě)者進(jìn)程的信號(hào)量進(jìn)行P操作，以便與寫(xiě)者進(jìn)

程互斥運(yùn)行；當(dāng)rc值由非。值增加時(shí)，說(shuō)明不是第一個(gè)讀者進(jìn)程，此時(shí)限制寫(xiě)者進(jìn)程的

信號(hào)量已經(jīng)過(guò)P操作限制禁止寫(xiě)者進(jìn)程進(jìn)入，因此不須要再次對(duì)該信號(hào)量進(jìn)行P操作。

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

個(gè)讀者進(jìn)程退出，因此須要該讀者進(jìn)程對(duì)限制寫(xiě)者進(jìn)程的信號(hào)量進(jìn)行V操作，以便使寫(xiě)

者進(jìn)程能夠進(jìn)入。

【解答】

①進(jìn)程間的相互制約關(guān)系有三類(lèi)。一是讀者之間允許同時(shí)讀；二是讀者與寫(xiě)者之間

須互斥進(jìn)行；三是寫(xiě)者之間須互斥寫(xiě)。

②進(jì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;

③為了提高寫(xiě)者的優(yōu)先級(jí)，我們?cè)黾右粋€(gè)信號(hào)量W,用以在寫(xiě)進(jìn)程到達(dá)時(shí)封鎖后續(xù)

的讀者進(jìn)程。相應(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;

【擴(kuò)展】

對(duì)于可由一類(lèi)進(jìn)程多次訪問(wèn)，而不同類(lèi)的進(jìn)程必需互斥訪問(wèn)的資源的限制，是進(jìn)程

限制中常見(jiàn)的一類(lèi)問(wèn)題。本題是這類(lèi)問(wèn)題中的一個(gè)典型，它給出了對(duì)于這類(lèi)資源的限制

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

的訪問(wèn)。這時(shí)，資源計(jì)數(shù)變量rc是一個(gè)臨界資源，須要用信號(hào)量對(duì)其進(jìn)行訪問(wèn)限制。

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

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

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

【分析】

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

即臨界區(qū)允很多個(gè)實(shí)例訪問(wèn)。用一個(gè)信號(hào)量來(lái)互斥訪問(wèn)臨界區(qū)。由于不能允許某一方向

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

上的車(chē)通過(guò)。用另兩個(gè)信號(hào)量來(lái)實(shí)現(xiàn)這一點(diǎ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;

【擴(kuò)展】

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

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

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

在實(shí)際考試中最好把全部分析過(guò)程，補(bǔ)充的約束條件寫(xiě)出，一方面扶植解題，一方面扶

植老師閱卷。

3.7進(jìn)程通信

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

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

申詢(xún)一科總區(qū)

消且義消g區(qū)

從消鳥(niǎo)池上摘下一消總

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

消自淺樓恢區(qū)

將放消總區(qū)

【分析】

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

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

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

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

斥訪問(wèn)。

【解答】

框圖中所缺的步驟如下：

①P(S1)

②V(S1)

③P(S2)

@P(S1)

⑤V(S1)

其中，S1是用于限制互斥訪問(wèn)消息鏈的互斥信號(hào)量，其初值為1；S2是用于記錄消

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

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

年試題）

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

②請(qǐng)給出消息緩沖機(jī)制（有界緩沖）的基本原理。

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

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

原語(yǔ)。

【解答】

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

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

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

P,V操作效率較低。

通信對(duì)用戶(hù)不透亮。

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

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

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

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

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

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

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

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

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

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

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

typemessagebuffer=record

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

size;消息長(zhǎng)度

text;消息正文

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

end;

發(fā)送原語(yǔ)：

PROCEDUREsend（receive,a）

〃接收進(jìn)程標(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;

接收原語(yǔ)：

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進(jìn)程調(diào)度

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

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

2001年試題）

【解答】

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

3.9死鎖

?用信號(hào)量及p,v操作解生產(chǎn)者-消費(fèi)者問(wèn)題，并改動(dòng)操作使之產(chǎn)生死鎖。（南開(kāi)

大學(xué)1995年試題）

【分析】

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

生對(duì)生產(chǎn)者一消費(fèi)者問(wèn)題的理解和對(duì)死鎖問(wèn)題的理解。

【解答】

生產(chǎn)者-消費(fèi)者問(wè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)生死鎖，只需改動(dòng)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;

在這個(gè)流程里，由于生產(chǎn)者和消費(fèi)者在生產(chǎn)和消費(fèi)之前都要對(duì)信號(hào)量mutex進(jìn)行P

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

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

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

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

【擴(kuò)展】

產(chǎn)生死鎖是在用信號(hào)量進(jìn)行流程限制過(guò)程中常會(huì)遇到的一個(gè)問(wèn)題。何時(shí)會(huì)發(fā)生死

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

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

生死鎖等類(lèi)似的問(wèn)題。

?用信號(hào)量及P,V操作解生產(chǎn)者-消費(fèi)者問(wèn)題，并改動(dòng)操作使之產(chǎn)生死鎖。(南開(kāi)

大學(xué)1995年試題)

【分析】

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

生對(duì)生產(chǎn)者一消費(fèi)者問(wèn)題的理解和對(duì)死鎖問(wèn)題的理解。

【解答】

生產(chǎn)者-消費(fèi)者問(wè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)生死鎖，只需改動(dòng)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;

在這個(gè)流程里，由于生產(chǎn)者和消費(fèi)者在生產(chǎn)和消費(fèi)之前都要對(duì)信號(hào)量mutex進(jìn)行P

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

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

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

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

【擴(kuò)展】

產(chǎn)生死鎖是在用信號(hào)量進(jìn)行流程限制過(guò)程中常會(huì)遇到的一個(gè)問(wèn)題。何時(shí)會(huì)發(fā)生死

鎖。如何避開(kāi)死鎖，是在考研中常考的問(wèn)題。在本題中，要求用經(jīng)典的生產(chǎn)者-消費(fèi)者問(wèn)

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

生死鎖等類(lèi)似的問(wèn)題。

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

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

VARfork:ARRAY[0..4]OFsemaphore;

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

PARBEGIN

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

ThinkFORWhile;

P(fork[i]);

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

EatFORWHILE;

V(fork[i]);

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

UNTILfalse

BXREND

【分析】

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

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

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

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

量來(lái)限制對(duì)臨界資源的訪問(wèn)，避開(kāi)死鎖。

【解答】

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

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

一種改進(jìn)的算法如下：

VARfork:ARRAY[0..4]OFsemaphore;

VARmutex:semaphore;

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

mutex:=1;

PARBEGIN

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

ThinkFo