計(jì)算機(jī)操作系統(tǒng)教程課件-進(jìn)程管理

第3章進(jìn)程管理3.1引言3.2進(jìn)程的引入和定義3.3進(jìn)程的狀態(tài)和進(jìn)程控制塊3.4進(jìn)程控制3.5線程的基本概念3.6進(jìn)程調(diào)度3.7進(jìn)程通信3.8死鎖問題本章學(xué)習(xí)目標(biāo)在多道程序環(huán)境下，程序不能獨(dú)立運(yùn)行。作為資源分配和獨(dú)立運(yùn)行的基本單位是進(jìn)程。操作系統(tǒng)所有的特征都是基于進(jìn)程而體現(xiàn)的。所以，本章的主要問題是：

進(jìn)程的概念進(jìn)程的實(shí)體、狀態(tài)及狀態(tài)的演變進(jìn)程的控制與調(diào)度進(jìn)程之間的關(guān)系協(xié)調(diào)進(jìn)程的通信死鎖問題及解決3.1引言處理機(jī)管理是操作系統(tǒng)的基本管理功能之一，它所關(guān)心的是處理機(jī)的分配問題。也就是說把CPU（中央處理機(jī)）的使用權(quán)分給某個(gè)程序，通常把這個(gè)正準(zhǔn)備進(jìn)入內(nèi)存的程序稱為作業(yè)，當(dāng)這個(gè)作業(yè)進(jìn)入內(nèi)存后我們把它稱為進(jìn)程。處理機(jī)管理分為作業(yè)管理和進(jìn)程管理兩個(gè)階段去實(shí)現(xiàn)處理機(jī)的分配，常常又把直接實(shí)行處理機(jī)時(shí)間分配的進(jìn)程調(diào)度工作作為處理機(jī)管理的主要內(nèi)容。進(jìn)程通常具有三種狀態(tài)：運(yùn)行狀態(tài)（正在使用CPU）、阻塞狀態(tài)（等待輸入/輸出）和就緒狀態(tài)（等待分配CPU）。3.2進(jìn)程的引入和定義3.2.1進(jìn)程的引入3.2.2進(jìn)程的定義3.2.1進(jìn)程的引入1．程序的順序執(zhí)行及其特性2．資源共享3．程序的并發(fā)執(zhí)行及其特性

1．程序的順序執(zhí)行及其特性

由于各類軟件的出現(xiàn)及日益復(fù)雜化，使得程序設(shè)計(jì)的概念和方法有了很大的發(fā)展，在單道程序工作環(huán)境中，我們把一個(gè)“程序”理解為“一個(gè)在時(shí)間上按嚴(yán)格次序前后相繼的操作序列”。

一切順序執(zhí)行的程序都具有下列特性：

（1）順序性。

（2）資源獨(dú)占。

（3）結(jié)果的無(wú)關(guān)性。

2．資源共享

操作系統(tǒng)提供了兩種實(shí)現(xiàn)資源共享的方法。

（1）由操作系統(tǒng)統(tǒng)一管理和分配。

（2）由進(jìn)程自行使用。

3．程序的并發(fā)執(zhí)行及其特性

無(wú)論是操作系統(tǒng)自身的程序還是用戶程序，通常總是存在一些相對(duì)獨(dú)立、但又能并發(fā)執(zhí)行的程序段。由于這些程序段可以被多個(gè)用戶作業(yè)調(diào)用，因此可在同一時(shí)間間隔內(nèi)發(fā)生。這樣一來，某個(gè)程序段可能對(duì)應(yīng)多個(gè)“計(jì)算”，于是程序與“計(jì)算”已不具有一一對(duì)應(yīng)關(guān)系了。這些“并發(fā)程序”就構(gòu)成了一個(gè)“并發(fā)環(huán)境”。圖3.2并行計(jì)算的先后次序程序的制約方式有如下兩種：（1）間接制約方式。這是由于競(jìng)爭(zhēng)相同資源而引起的，得到資源的程序段可以投入運(yùn)行，而得不到資源的程序段就是暫時(shí)等待，直至獲得可用資源時(shí)再繼續(xù)運(yùn)行。（2）直接制約方式。這通常是在那些邏輯上相關(guān)的程序段之間發(fā)生的。一般是由于各種程序段要求共享信息引起的。3.2.2進(jìn)程的定義

進(jìn)程與程序的區(qū)別和相互關(guān)系：（1）動(dòng)態(tài)性和靜態(tài)性。

（2）從結(jié)構(gòu)上看每個(gè)進(jìn)程的實(shí)體都是由程序段和相應(yīng)的數(shù)據(jù)段兩部分構(gòu)成的，這一特征與程序的含義相近。（3）一個(gè)進(jìn)程可以涉及到一個(gè)或幾個(gè)程序的執(zhí)行；反之一程序可以對(duì)應(yīng)多個(gè)進(jìn)程，即同一程序段可在不同數(shù)據(jù)集合上運(yùn)行，可構(gòu)成不同的進(jìn)程。（4）并發(fā)性。

（5）進(jìn)程具有創(chuàng)建其他進(jìn)程的功能。

（6）操作系統(tǒng)中的每一個(gè)程序都是在一個(gè)進(jìn)程現(xiàn)場(chǎng)中運(yùn)行的。

3.3進(jìn)程的狀態(tài)和進(jìn)程控制塊

3.3.1進(jìn)程的狀態(tài)及狀態(tài)變化圖

3.3.2進(jìn)程控制塊

3.3.1進(jìn)程的狀態(tài)及狀態(tài)變化圖

（1）運(yùn)行狀態(tài)：進(jìn)程正在處理機(jī)上運(yùn)行的狀態(tài)，該進(jìn)程已獲得必要的資源，也獲得了處理機(jī)，用戶程序正在處理機(jī)上運(yùn)行。（2）阻塞狀態(tài)：進(jìn)程等待某種事件完成（例如，等待輸入/輸出操作的完成）而暫時(shí)不能運(yùn)行的狀態(tài)，處于該狀態(tài)的進(jìn)程不能參加競(jìng)爭(zhēng)處理機(jī)，此時(shí)，即使分配給它處理機(jī)，它也不能運(yùn)行。（3）就緒狀態(tài)：該進(jìn)程運(yùn)行所需的一切條件都得到滿足，但因處理機(jī)資源個(gè)數(shù)少于進(jìn)程個(gè)數(shù)，所以該進(jìn)程不能運(yùn)行，而必須等待分配處理機(jī)資源，一旦獲得處理機(jī)就立即投入運(yùn)行。圖3.3典型的進(jìn)程狀態(tài)演變圖狀態(tài)變化：（1）就緒狀態(tài)變化到運(yùn)行狀態(tài)。（2）運(yùn)行狀態(tài)變化到就緒狀態(tài)。

（3）運(yùn)行狀態(tài)變化到阻塞狀態(tài)。

（4）阻塞狀態(tài)變化到就緒狀態(tài)。

3.3.2進(jìn)程控制塊

為了刻畫進(jìn)程的動(dòng)態(tài)變化，通常把進(jìn)程表示為由程序段、私有數(shù)據(jù)塊和進(jìn)程控制塊組成，如圖3.4（a）所示。程序部分描述進(jìn)程本身所要完成的功能，而“私有數(shù)據(jù)塊”是接受程序規(guī)定操作的一組存儲(chǔ)單元的內(nèi)容，是操作的對(duì)象。進(jìn)程控制塊是在進(jìn)程創(chuàng)建時(shí)產(chǎn)生的，當(dāng)進(jìn)程存在于系統(tǒng)時(shí)（運(yùn)行），進(jìn)程控制塊就標(biāo)識(shí)了這個(gè)進(jìn)程。如圖3.4（b）所示。

進(jìn)程控制塊是進(jìn)程存在的標(biāo)志，當(dāng)系統(tǒng)或父進(jìn)程創(chuàng)建一個(gè)進(jìn)程時(shí)，實(shí)際上就是為其建立一個(gè)進(jìn)程控制塊。

進(jìn)程控制塊既能標(biāo)識(shí)進(jìn)程的存在，又能刻畫出進(jìn)程的動(dòng)態(tài)特征，它是一個(gè)進(jìn)程僅有的被系統(tǒng)真正感知的部分。對(duì)操作系統(tǒng)而言，所有進(jìn)程控制塊將構(gòu)成并發(fā)執(zhí)行控制和維護(hù)系統(tǒng)工作的依據(jù)。進(jìn)程控制塊的作用：3.4進(jìn)程控制

3.4.1原語(yǔ)

3.4.2進(jìn)程控制原語(yǔ)

3.4.1原語(yǔ)

在操作系統(tǒng)中，某些被進(jìn)程調(diào)用的操作，例如隊(duì)列操作、對(duì)信號(hào)燈的操作、檢查啟動(dòng)外設(shè)操作等，一旦開始執(zhí)行就不能被中斷，否則就會(huì)出現(xiàn)操作錯(cuò)誤，造成系統(tǒng)混亂。原語(yǔ)就是為實(shí)現(xiàn)這些操作而設(shè)置的。圖3.5進(jìn)程家族示例3.4.2進(jìn)程控制原語(yǔ)1．創(chuàng)建原語(yǔ)2．撤消原語(yǔ)3．阻塞原語(yǔ)4．喚醒原語(yǔ)3.5線程的基本概念3.5.1線程的引入3.5.2線程與進(jìn)程的比較3.5.3用戶級(jí)線程和內(nèi)核支持線程3.5.1線程的引入（1）創(chuàng)建進(jìn)程。系統(tǒng)在創(chuàng)建進(jìn)程時(shí)，必須為之分配其所必需的、除處理機(jī)以外的所有資源。如內(nèi)存空間、I/O設(shè)備以及建立相應(yīng)的PCB結(jié)構(gòu)。（2）撤消進(jìn)程。系統(tǒng)在撤消進(jìn)程時(shí)，又必須先對(duì)這些資源進(jìn)行回收操作，然后再撤消PCB結(jié)構(gòu)。（3）進(jìn)程切換。在對(duì)進(jìn)程進(jìn)行切換時(shí)，由于要保留當(dāng)前進(jìn)程的CPU環(huán)境和設(shè)置新選中進(jìn)程的CPU環(huán)境，為此需花費(fèi)不少處理機(jī)時(shí)間。3.5.2線程與進(jìn)程的比較1．調(diào)度：在傳統(tǒng)的操作系統(tǒng)中，擁有資源的基本單位和獨(dú)立調(diào)度、分派的基本單位都是進(jìn)程。

2．并發(fā)性：在引入線程的操作系統(tǒng)中，不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且在一個(gè)進(jìn)程中的多個(gè)線程之間亦可并發(fā)執(zhí)行，因而使操作系統(tǒng)具有更好的并發(fā)性，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)吞吐量。

3．擁有資源：不論是傳統(tǒng)的操作系統(tǒng)，還是設(shè)有線程的操作系統(tǒng)，進(jìn)程都是擁有資源的一個(gè)獨(dú)立單位，它可以擁有自己的資源。

4．系統(tǒng)開銷：由于在創(chuàng)建或撤消進(jìn)程時(shí)，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、I/O設(shè)備等。因此，操作系統(tǒng)所付出的開銷將明顯地大于在創(chuàng)建或撤消線程時(shí)的開銷。

3.5.3用戶級(jí)線程和內(nèi)核支持線程比較兩種線程的優(yōu)缺點(diǎn)：1．線程的調(diào)度與切換速度：內(nèi)核支持線程的調(diào)度和切換與進(jìn)程的調(diào)度和切換十分相似。

2．系統(tǒng)功能調(diào)用：當(dāng)傳統(tǒng)的用戶進(jìn)程調(diào)用一個(gè)系統(tǒng)功能調(diào)用時(shí)，要由用戶態(tài)進(jìn)入核心態(tài)，用戶進(jìn)程將被阻塞。當(dāng)內(nèi)核完成系統(tǒng)調(diào)用而返回時(shí)，才將該進(jìn)程喚醒，繼續(xù)執(zhí)行。

3．線程執(zhí)行時(shí)間：對(duì)于只設(shè)置了用戶級(jí)線程的系統(tǒng)，調(diào)度是以進(jìn)程為單位進(jìn)行的。在采用輪轉(zhuǎn)調(diào)度算法時(shí)，各個(gè)進(jìn)程輪流執(zhí)行一個(gè)時(shí)間片，這對(duì)諸進(jìn)程而言似乎是公平的。

3.6進(jìn)程調(diào)度

3.6.1進(jìn)程調(diào)度的職能

3.6.2進(jìn)程調(diào)度算法

3.6.3調(diào)度用的進(jìn)程狀態(tài)切換圖

3.6.1進(jìn)程調(diào)度的職能

（1）記錄系統(tǒng)中所有進(jìn)程的有關(guān)情況。

（2）確定分配處理機(jī)的原則。

（3）分配處理機(jī)給進(jìn)程。

（4）從進(jìn)程收回處理機(jī)。

3.6.2進(jìn)程調(diào)度算法

1．先來先服務(wù)

2．輪轉(zhuǎn)調(diào)度

3．分級(jí)輪轉(zhuǎn)法4．優(yōu)先數(shù)法

1．先來先服務(wù)

這種調(diào)度算法按照進(jìn)程進(jìn)入就緒隊(duì)列的先后順序來調(diào)度進(jìn)程，到達(dá)得越早，其優(yōu)先數(shù)越高。獲得處理機(jī)的進(jìn)程，未遇到其他情況時(shí)，一直運(yùn)行下去，系統(tǒng)只需具備一個(gè)先進(jìn)先出的隊(duì)列，在管理優(yōu)先數(shù)的就緒隊(duì)列時(shí)，這種方法是一種最常見策略，并且在沒有其他信息時(shí)，也是一種最合理的策略。2．輪轉(zhuǎn)調(diào)度

先來先服務(wù)的一個(gè)重要變形，就是輪轉(zhuǎn)規(guī)則。輪轉(zhuǎn)調(diào)度算法是系統(tǒng)把所有就緒進(jìn)程按先后次序排隊(duì)，處理機(jī)總是優(yōu)先分配給就緒隊(duì)列中的第一個(gè)就緒進(jìn)程，并分配它一個(gè)固定的時(shí)間片（如100毫秒）。當(dāng)該運(yùn)行進(jìn)程用完規(guī)定的時(shí)間片時(shí)，被迫釋放處理機(jī)給下一個(gè)處于就緒隊(duì)列中的第一個(gè)進(jìn)程，分給這個(gè)進(jìn)程相同的時(shí)間片，每個(gè)運(yùn)行完時(shí)間片的進(jìn)程，當(dāng)未遇到任何阻塞時(shí)，就回到就緒隊(duì)列的尾部，并等待下次轉(zhuǎn)到它時(shí)再投入運(yùn)行。于是，只要是處于就緒隊(duì)列中的進(jìn)程，按此種算法遲早總可以分得處理機(jī)投入運(yùn)行。3．分級(jí)輪轉(zhuǎn)法所謂分級(jí)輪轉(zhuǎn)法就是將先前的一個(gè)就緒隊(duì)列。根據(jù)進(jìn)程的優(yōu)先數(shù)不同劃分兩個(gè)或兩個(gè)以上的就緒隊(duì)列，并賦給每個(gè)隊(duì)列不同的優(yōu)先數(shù)。以兩個(gè)就緒隊(duì)列為例，一個(gè)具有較高優(yōu)先數(shù)，另一個(gè)具有較低優(yōu)先數(shù)，前者稱為前臺(tái)隊(duì)列，后者稱為后臺(tái)隊(duì)列。4．優(yōu)先數(shù)法

根據(jù)已占有處理

機(jī)的進(jìn)程是否可被剝奪而分為優(yōu)先占有法和優(yōu)先剝奪法兩種。優(yōu)先占有法的原理是：一旦某個(gè)最高優(yōu)先數(shù)的就緒進(jìn)程分得處理機(jī)之后，只要不是其自身的原因被阻塞（如要求I/O操作）而不能繼續(xù)運(yùn)行時(shí)，就一直運(yùn)行下去，直至運(yùn)行結(jié)束。優(yōu)先剝奪法的原理是：當(dāng)一個(gè)正在運(yùn)行的進(jìn)程即使其時(shí)間片未用完，無(wú)論什么時(shí)候，只要就緒隊(duì)列中有一個(gè)比它的優(yōu)先數(shù)高的進(jìn)程，優(yōu)先數(shù)高的進(jìn)程就可以取代以前正在運(yùn)行的進(jìn)程，投入運(yùn)行。確定進(jìn)程的優(yōu)先數(shù)通常應(yīng)考慮如下幾個(gè)因素：

（1）進(jìn)程類型。

（2）運(yùn)行時(shí)間。

（3）作業(yè)的優(yōu)先數(shù)。

（4）動(dòng)態(tài)優(yōu)先數(shù)。

3.6.3調(diào)度用的進(jìn)程狀態(tài)切換圖

圖3.6調(diào)度用的進(jìn)程狀態(tài)切換圖3.7進(jìn)程通信

3.7.1臨界資源和臨界區(qū)

3.7.2進(jìn)程的通信方式之一

——

同步與互斥

3.7.3兩個(gè)經(jīng)典的同步/互斥問題

3.7.4結(jié)構(gòu)化的同步/互斥機(jī)制——管程

3.7.5進(jìn)程的通信方式之二——消息緩沖

3.7.1臨界資源和臨界區(qū)

在計(jì)算機(jī)中有許多資源只允許一個(gè)進(jìn)程使用，如果有多個(gè)進(jìn)程同時(shí)去使用這類資源就會(huì)產(chǎn)生嚴(yán)重的錯(cuò)誤。

幾個(gè)進(jìn)程若共享同一臨界資源，它們必須以互斥的方式使用這個(gè)臨界資源，即當(dāng)一個(gè)進(jìn)程正在使用臨界資源且尚未使用完畢時(shí)，則其他進(jìn)程必須推遲對(duì)該資源的進(jìn)一步操作，在當(dāng)前進(jìn)程的使用完成之前，不能從中插進(jìn)去使用這個(gè)臨界資源，否則將會(huì)造成信息混亂和操作出錯(cuò)。

系統(tǒng)中同時(shí)存在有許多進(jìn)程，它們共享各種資源，然而有些資源每次只能讓一個(gè)進(jìn)程所使用。

3.7.2進(jìn)程的通信方式之一

——

同步與互斥

同步：我們把進(jìn)程間的這種必須互相合作的協(xié)同工作關(guān)系，稱為進(jìn)程同步。互斥：兩個(gè)并行的進(jìn)程A、B，如果當(dāng)A進(jìn)行某個(gè)操作時(shí)，B不能做這一操作，進(jìn)程間的這種限制條件稱為進(jìn)程互斥，這是引起資源不可共享的原因。

lock和unlock大部分同步方案均采用某個(gè)物理實(shí)體（如鎖、信號(hào)燈等）實(shí)現(xiàn)通信，進(jìn)程通信原語(yǔ)中關(guān)鎖（lock）和開鎖（unlock）是最簡(jiǎn)單的原語(yǔ)。在這兩個(gè)原語(yǔ)中設(shè)置一個(gè)公共變量x代表某個(gè)臨界資源的狀態(tài)。如：x=0，表示資源可用，x=1，表示資源正在使用。關(guān)鎖原語(yǔ)1ock（x）：L：ifx＝1thengotoLelsex：=1；開鎖原語(yǔ)unlock（x）：x：=0；圖3.7開鎖和關(guān)鎖程序流程圖3.7.3兩個(gè)經(jīng)典的同步/互斥問題

1．生產(chǎn)者與消費(fèi)者問題

2．讀者與寫者問題

1．生產(chǎn)者與消費(fèi)者問題

Dijkstra把廣義同步問題抽象成一種“生產(chǎn)者與消費(fèi)者問題”（Producer-consumer-relationship）的抽象模型。事實(shí)上，計(jì)算機(jī)系統(tǒng)中的許多問題都可歸結(jié)為生產(chǎn)者與消費(fèi)者問題，生產(chǎn)者與消費(fèi)者可以通過一個(gè)環(huán)形緩沖池（見圖3.8）聯(lián)系起來，環(huán)形緩沖池由幾個(gè)大小相等的緩沖塊組成，每個(gè)緩沖塊容納一個(gè)產(chǎn)品。每個(gè)生產(chǎn)者可不斷地每次往緩沖池中送一個(gè)生產(chǎn)產(chǎn)品，而每個(gè)消費(fèi)者則可不斷地每次從緩沖池中取出一個(gè)產(chǎn)品。

圖3.8環(huán)形緩沖池下面給出基于環(huán)形緩沖區(qū)的生產(chǎn)者與消費(fèi)者關(guān)系的形式描述，設(shè)：（1）公用信號(hào)量mutex：初值為1，用于實(shí)現(xiàn)臨界區(qū)互斥。（2）生產(chǎn)者私用信號(hào)量empty：初值為n，指示空緩沖塊數(shù)目。（3）消費(fèi)者私用信號(hào)量full：初值為0，指示滿緩沖塊數(shù)目。（4）整型量i和j初值均為0，i指示首空緩沖塊序號(hào)，j指示首滿緩沖塊序號(hào)。模塊設(shè)計(jì)如下：

Varmutex，empty，full：semaphore;i,j:integer；buffer：array[0…n一1]ofitem；Procedureproducer;生產(chǎn)者進(jìn)程

begin

whiletruedobeginproduceaproduct;P(empty);

P(mutex);Buffer(i)：＝Product;i：＝(i+1)modn；V(mutex);V(full)endend;procedureconsumer;消費(fèi)者進(jìn)程

beginWhiletruedobeginP(full)；P(mutex)goods：＝buffer(j);j：＝(j+1)modn;V(mutex);V(empty);Consumeaproduct;end

end;beginseminitial;i:＝j(luò):＝0;cobeginproducer；consumer；coendend2．讀者與寫者問題

設(shè)某航空公司有2個(gè)售票處，它們通過遠(yuǎn)程終端訪問設(shè)在公司總部的航空訂票系統(tǒng)，并要查詢或修改系統(tǒng)中記錄所有班機(jī)當(dāng)前訂票數(shù)的數(shù)據(jù)庫(kù)B。設(shè)Bi為某班機(jī)的當(dāng)前訂票數(shù)，P1和P2分別代表2個(gè)售票處的售票進(jìn)程，R1和R2為進(jìn)程執(zhí)行時(shí)使用的工作寄存器。由于售票進(jìn)程并發(fā)執(zhí)行，且各自訪問數(shù)據(jù)庫(kù)B的時(shí)間是隨機(jī)的，故有可能出現(xiàn)下面的訪問序列（假定Bi的當(dāng)前值為x）：P1:R1:=Bi;R1:=R1+1P2:R2=Bi;R2:=R2+1;P1:Bi:=R1;P2:Bi:=R2

可見，Bi的新值是X+1，而不是X+2。這里的P1和P2均為寫者，顯然，對(duì)于寫者Bi為臨界資源，因此寫者應(yīng)該互斥。下面給出讀者進(jìn)程與寫者進(jìn)程的一般結(jié)構(gòu)。varmutex,wrt:semaphore;readcount:integer;beginseminit;readcount:=0cobeginprocedurereader;beginP(mutex);Readcount:=readcount+1;Ifreadcount=1thenP(wrt);V(mutex);Readingisperforming;P(mutex);readcount:=readcount-1ifreadcount=0thenV(wrt);V(mutex);End

Procedurewriter;BeginP(wrt);writingisperforming;V(wrt);EndCoendEnd;3.7.4結(jié)構(gòu)化的同步/互斥機(jī)制——管程

建立管程的基本理由是：由于對(duì)臨界區(qū)的執(zhí)行分散在各進(jìn)程中，這樣不便于系統(tǒng)對(duì)臨界資源的控制和管理，也很難發(fā)現(xiàn)和糾正分散在用戶程序中的對(duì)同步原語(yǔ)的錯(cuò)誤使用等問題。為此，應(yīng)把分散的各同類臨界區(qū)集中起來。并為每個(gè)可共享資源設(shè)立一個(gè)專門的管程來統(tǒng)一管理各進(jìn)程對(duì)該資源的訪問。這樣既便于系統(tǒng)管理共享資源，又能保證互斥訪問。管程主要由兩部分組成：（1）局部于該管程的共享數(shù)據(jù)，這些數(shù)據(jù)表示了相應(yīng)資源的狀態(tài)。（2）局部于該管程的若干過程，每個(gè)過程完成關(guān)于上述數(shù)據(jù)的某種規(guī)定操作。為了實(shí)現(xiàn)對(duì)臨界資源的互斥訪問，管程每次只允許一個(gè)進(jìn)程進(jìn)入其內(nèi)（即訪問管程內(nèi)的某個(gè)過程），這是由編譯系統(tǒng)保證的。

monitorringbuffer;varrbuffer：array[0．．n-1]ofitem；k,nextempty,nextfull:integer;empty,full:condition;procedureentryput(varproduct:item);beginifk=nwait(empty);rbuffer[nextempty]:product;k:=k+1；nextempty:=(nextempty+1)modn;signal(full);end;例：以環(huán)形緩沖池為例，給出環(huán)形緩沖池的管程結(jié)構(gòu)

procedureentryget(vargoods:item);beginifk=0wait(full);goods:=rbuffer[nextfull];k:=k-1;nextfull:=(nextfull+1)modn;signal(empty);end;begink:=0;nextempty:=0;nextfull:=0;end;在利用管程解決生產(chǎn)者、消費(fèi)者問題時(shí)，其中的生產(chǎn)者和消費(fèi)者可描述為：producer：beginrepeatproduceanitem；ringbuffer.put(item)；untilfalse；endconsumer：beginrepeatringbuffer.get(item)；consumetheitem；end3.7.5進(jìn)程的通信方式之二——消息緩沖

1．SEND(A)（發(fā)送消息）原語(yǔ)

2．READ（A）（讀取消息）原語(yǔ)

1．SEND(A)（發(fā)送消息）原語(yǔ)

發(fā)送消息原語(yǔ)被進(jìn)程用于把消息發(fā)送到存放消息的緩沖區(qū)。A是原語(yǔ)的參數(shù)，表示發(fā)送區(qū)的地址。其工作原理是：首先調(diào)用“尋找目標(biāo)進(jìn)程的PCB”的程序查找接收進(jìn)程的PCB，如果接收進(jìn)程存在，申請(qǐng)一個(gè)存放消息的緩沖區(qū)，消息緩沖區(qū)為空時(shí)，接收此消息的進(jìn)程因等待此消息的到來而處于阻塞狀態(tài)，則喚醒此進(jìn)程，并把消息的內(nèi)容、發(fā)送原語(yǔ)的進(jìn)程名和消息等，復(fù)制到預(yù)先申請(qǐng)的存放消息的緩沖區(qū)，且將存放消息的緩沖區(qū)連接到接收進(jìn)程的PCB上；如果接收進(jìn)程不存在，則由系統(tǒng)給出一個(gè)“啞”回答；最后控制返回到發(fā)送消息的進(jìn)程繼續(xù)執(zhí)行，或轉(zhuǎn)入進(jìn)程調(diào)度程序重新分配處理機(jī)。如果消息緩沖區(qū)已滿，則返回到非同步錯(cuò)誤處理程序入口進(jìn)行特殊處理。如圖3.9所示。圖3.9發(fā)送消息過程流圖2．READ（A）（讀取消息）原語(yǔ)

READ(A)原語(yǔ)用來讀取消息，接收進(jìn)程讀取消息之前，在自己的空間中確定一個(gè)接收區(qū)。當(dāng)接收進(jìn)程想要讀取消息時(shí)，使用READ(A)原語(yǔ)，A是接收進(jìn)程提供的接收區(qū)開始地址。如圖3.10所示。圖3.10讀取消息3.8死鎖問題

3.8.1死鎖產(chǎn)生的原因和必要條件

3.8.2預(yù)防死鎖

3.8.3發(fā)現(xiàn)死鎖

3.8.4解除死鎖

3.8.1死鎖產(chǎn)生的原因和必要條件

死鎖產(chǎn)生的原因：當(dāng)某個(gè)進(jìn)程提出申請(qǐng)資源后，使得有關(guān)進(jìn)程在無(wú)外力協(xié)助下，永遠(yuǎn)分配不到必需的資源而無(wú)法繼續(xù)運(yùn)行，這就產(chǎn)生了一種特殊的現(xiàn)象——死鎖。在許多實(shí)時(shí)應(yīng)用中，比如計(jì)算機(jī)控制運(yùn)輸和監(jiān)視系統(tǒng)方面，死鎖問題也極為重要。

死鎖產(chǎn)生例子1：我們先來看一個(gè)申請(qǐng)不同類型資源的死鎖例子，假定有兩個(gè)進(jìn)程Pl和P2都要修改文件F，修改時(shí)都需要一條暫時(shí)存放信息的磁帶，而只有一臺(tái)磁帶機(jī)T可用。又假定由于某種原因，在進(jìn)行修改之前，P2需要一暫存磁帶（例如為了修改，要重新組織輸入數(shù)據(jù)）。設(shè)F和T都是可重用資源，它們分別表示允許更新文件和允許使用磁帶機(jī)。于是Pl和P2?？捎腥缦滦问剑悍治觯簭纳厦娴纳暾?qǐng)-釋放過程可以看出，進(jìn)程Pl和P2有可能“同時(shí)”分別到達(dá)rl和r2處，例如，P2首先得到T，然后Pl得到F，接著Pl到達(dá)r1，最后P2到達(dá)r2，此時(shí)，若Pl繼續(xù)運(yùn)行，則占有F的進(jìn)程Pl將阻塞在T上，若P2繼續(xù)運(yùn)行，則占有T的進(jìn)程P2將阻塞在F上，如果P2不能前進(jìn)，則P1也不能繼續(xù)下去，反之亦然。我們說這兩個(gè)進(jìn)程處在死鎖狀態(tài)。圖3.11簡(jiǎn)單的死鎖例子死鎖產(chǎn)生例子2：現(xiàn)在我們?cè)賮砜匆粋€(gè)關(guān)于相同類型資源共享的死鎖例子，假設(shè)有一類可再使用資源R，例如主存或外存，它包含有m個(gè)頁(yè)面或扇區(qū)，由n個(gè)進(jìn)程P1，P2…，Pn（2≤m≤n）共享。假定每個(gè)進(jìn)程按右圖順序申請(qǐng)和釋放頁(yè)面（或扇區(qū)）：分析：這里每次申請(qǐng)和釋放只涉及R的一個(gè)分配單元（頁(yè)或扇區(qū)）。因此，當(dāng)把所有單元全部分配完畢時(shí)，便很容易發(fā)生死鎖；占有R的單元的所有進(jìn)程（前m個(gè)進(jìn)程）會(huì)永遠(yuǎn)阻塞在第二次申請(qǐng)上，而有些進(jìn)程（n~m個(gè)進(jìn)程）類似地會(huì)阻塞在它們的第一次申請(qǐng)上，在圖3.12中說明了n＝3，m＝2時(shí)這種系統(tǒng)的狀態(tài)，這類死鎖是相當(dāng)普遍的。

圖3.12同類資源共享時(shí)的死鎖現(xiàn)象產(chǎn)生死鎖有四個(gè)必要條件：

產(chǎn)生死鎖有四個(gè)必要條件：（1）互斥條件。

（2）不剝奪條件。（3）請(qǐng)求和保持條件。（4）環(huán)路等待條件。

3.8.2預(yù)防死鎖

1．破壞“請(qǐng)求與保持條件”

2．破壞環(huán)路條件

3．資源受控動(dòng)態(tài)分配

1．破壞“請(qǐng)求與保持條件”

這種方法的基本思想是：每個(gè)進(jìn)程在運(yùn)行之前，必須預(yù)先提出自己所要使用的全部資源，調(diào)度程序在該進(jìn)程所需要的資源末得到滿足之前，不讓它們投入運(yùn)行，并且當(dāng)資源一旦分配給某個(gè)進(jìn)程之后，那么在該進(jìn)程的整個(gè)運(yùn)行期間相應(yīng)資源一直被它占有，這就破壞了產(chǎn)生死鎖的請(qǐng)求與保持條件。2．破壞