高中信息技術(shù) 第3章進(jìn)程管理課件.ppt

1、第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)分給某

2、個(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ì)的概念

3、和方法有了很大的發(fā)展，在單道程序工作環(huán)境中，我們把一個(gè)“程序”理解為“一個(gè)在時(shí)間上按嚴(yán)格次序前后相繼的操作序列”。,下一頁,一切順序執(zhí)行的程序都具有下列特性： （1）順序性。 （2）資源獨(dú)占。 （3）結(jié)果的無關(guān)性。,下一頁,2資源共享,操作系統(tǒng)提供了兩種實(shí)現(xiàn)資源共享的方法。 （1）由操作系統(tǒng)統(tǒng)一管理和分配。 （2）由進(jìn)程自行使用。,下一頁,3程序的并發(fā)執(zhí)行及其特性,無論是操作系統(tǒng)自身的程序還是用戶程序，通?？偸谴嬖谝恍┫鄬Κ?dú)立、但又能并發(fā)執(zhí)行的程序段。由于這些程序段可以被多個(gè)用戶作業(yè)調(diào)用，因此可在同一時(shí)間間隔內(nèi)發(fā)生。這樣一來，某個(gè)程序段可能對應(yīng)多個(gè)“計(jì)算”，于是程序與“計(jì)算”已不具有一一對應(yīng)關(guān)

4、系了。這些“并發(fā)程序”就構(gòu)成了一個(gè)“并發(fā)環(huán)境”。,下一頁,圖3.2 并行計(jì)算的先后次序,下一頁,程序的制約方式有如下兩種 ： （1）間接制約方式。 這是由于競爭相同資源而引起的，得到資源的程序段可以投入運(yùn)行，而得不到資源的程序段就是暫時(shí)等待，直至獲得可用資源時(shí)再繼續(xù)運(yùn)行 。 （2）直接制約方式。 這通常是在那些邏輯上相關(guān)的程序段之間發(fā)生的。一般是由于各種程序段要求共享信息引起的 。,返回本節(jié)目錄,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)程可以涉及

5、到一個(gè)或幾個(gè)程序的執(zhí)行；反之一程序可以對應(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)場中運(yùn)行的。,返回本節(jié)目錄,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)程不能

6、參加競爭處理機(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)。,返回本節(jié)目錄,3.3.2 進(jìn)程控制塊,為了刻畫進(jìn)程的動(dòng)態(tài)變化，通常把進(jìn)程表示為由程序段、私有數(shù)據(jù)塊和進(jìn)程控制塊組成，如圖3.4（a）所示。程序部分描述進(jìn)程本身所要完成的功能，而“私有數(shù)據(jù)塊

7、”是接受程序規(guī)定操作的一組存儲(chǔ)單元的內(nèi)容，是操作的對象。進(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)真正感知的部分。對操作系統(tǒng)而言，所有進(jìn)程控制塊將構(gòu)成并發(fā)執(zhí)行控制和維護(hù)系統(tǒng)工作的依據(jù)。,進(jìn)程控制塊的作用：,返回本節(jié)目錄,3.4 進(jìn)程控制,3.4.1 原語 3.4.2 進(jìn)程控制原語,返回本章首頁,3.4.1 原語,在操作系統(tǒng)中，某些被進(jìn)程調(diào)

8、用的操作，例如隊(duì)列操作、對信號(hào)燈的操作、檢查啟動(dòng)外設(shè)操作等，一旦開始執(zhí)行就不能被中斷，否則就會(huì)出現(xiàn)操作錯(cuò)誤，造成系統(tǒng)混亂。原語就是為實(shí)現(xiàn)這些操作而設(shè)置的。,下一頁,圖3.5 進(jìn)程家族示例,返回本節(jié)目錄,3.4.2 進(jìn)程控制原語,1創(chuàng)建原語 2撤消原語 3阻塞原語 4喚醒原語,返回本節(jié)目錄,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)在撤

9、消進(jìn)程時(shí)，又必須先對這些資源進(jìn)行回收操作，然后再撤消PCB結(jié)構(gòu)。 （3）進(jìn)程切換。在對進(jìn)程進(jìn)行切換時(shí)，由于要保留當(dāng)前進(jìn)程的CPU環(huán)境和設(shè)置新選中進(jìn)程的CPU環(huán)境，為此需花費(fèi)不少處理機(jī)時(shí)間。,返回本節(jié)目錄,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ú)立單位，它可以擁有

10、自己的資源。 4系統(tǒng)開銷：由于在創(chuàng)建或撤消進(jìn)程時(shí)，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、I/O設(shè)備等。因此，操作系統(tǒng)所付出的開銷將明顯地大于在創(chuàng)建或撤消線程時(shí)的開銷。,返回本節(jié)目錄,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í)間 ：對于只設(shè)置了用戶級(jí)線程的系統(tǒng)，調(diào)度是以進(jìn)程為單位進(jìn)行的。在采用輪轉(zhuǎn)調(diào)度算法時(shí)，各個(gè)進(jìn)程輪流執(zhí)行一個(gè)時(shí)間片

11、，這對諸進(jìn)程而言似乎是公平的。,返回本節(jié)目錄,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ī)。,返回本節(jié)目錄,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)

12、先數(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í)輪

13、轉(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í)間片未用完，無論什么時(shí)候，只要就緒隊(duì)列中有一個(gè)比它的優(yōu)先數(shù)高的進(jìn)程，優(yōu)先數(shù)高的進(jìn)程就可以取

14、代以前正在運(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ù)。,返回本節(jié)目錄,3.6.3 調(diào)度用的進(jìn)程狀態(tài)切換圖,圖3.6 調(diào)度用的進(jìn)程狀態(tài)切換圖,返回本節(jié)目錄,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)重

15、的錯(cuò)誤。 幾個(gè)進(jìn)程若共享同一臨界資源，它們必須以互斥的方式使用這個(gè)臨界資源，即當(dāng)一個(gè)進(jìn)程正在使用臨界資源且尚未使用完畢時(shí)，則其他進(jìn)程必須推遲對該資源的進(jìn)一步操作，在當(dāng)前進(jìn)程的使用完成之前，不能從中插進(jìn)去使用這個(gè)臨界資源，否則將會(huì)造成信息混亂和操作出錯(cuò)。 系統(tǒng)中同時(shí)存在有許多進(jìn)程，它們共享各種資源，然而有些資源每次只能讓一個(gè)進(jìn)程所使用。,返回本節(jié)目錄,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)程互斥，這是引起資源不可共享的原因。,l

16、ock和unlock 大部分同步方案均采用某個(gè)物理實(shí)體（如鎖、信號(hào)燈等）實(shí)現(xiàn)通信，進(jìn)程通信原語中關(guān)鎖（lock）和開鎖（unlock）是最簡單的原語。在這兩個(gè)原語中設(shè)置一個(gè)公共變量x代表某個(gè)臨界資源的狀態(tài)。如：x=0，表示資源可用，x=1，表示資源正在使用。 關(guān)鎖原語1ock（x）： L：if x1 then goto L else x：=1； 開鎖原語unlock（x）： x：=0；,圖3.7 開鎖和關(guān)鎖程序流程圖,返回本節(jié)目錄,3.7.3 兩個(gè)經(jīng)典的同步/互斥問題,1生產(chǎn)者與消費(fèi)者問題 2讀者與寫者問題,1生產(chǎn)者與消費(fèi)者問題,Dijkstra把廣義同步問題抽象成一種“生產(chǎn)者與消費(fèi)者問題”（

17、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)量

18、full：初值為0，指示滿緩沖塊數(shù)目。 （4）整型量i和j初值均為0，i指示首空緩沖塊序號(hào)，j指示首滿緩沖塊序號(hào)。 模塊 設(shè)計(jì)如下：,下一頁,Var mutex，empty，full：semaphore; i,j:integer；buffer：array 0n一1 of item； Procedure producer; 生產(chǎn)者進(jìn)程 begin while true do begin produce a product; P(empty);,下一頁,P(mutex); Buffer (i)：Product; i：(i+1) mod n； V(mutex); V(full) end end; p

19、rocedure consumer; 消費(fèi)者進(jìn)程,下一頁,begin While true do begin P(full)； P(mutex) goods：buffer(j); j：(j+1) mod n; V(mutex); V(empty); Consume a product; end,下一頁,end; begin seminitial ; i:j:0; cobegin producer； consumer； coend end,下一頁,2讀者與寫者問題,設(shè)某航空公司有2個(gè)售票處，它們通過遠(yuǎn)程終端訪問設(shè)在公司總部的航空訂票系統(tǒng)，并要查詢或修改系統(tǒng)中記錄所有班機(jī)當(dāng)前訂票數(shù)的數(shù)據(jù)庫B。設(shè)B

20、i為某班機(jī)的當(dāng)前訂票數(shù)，P1和P2分別代表2個(gè)售票處的售票進(jìn)程，R1和R2為進(jìn)程執(zhí)行時(shí)使用的工作寄存器。由于售票進(jìn)程并發(fā)執(zhí)行，且各自訪問數(shù)據(jù)庫B的時(shí)間是隨機(jī)的，故有可能出現(xiàn)下面的訪問序列（假定Bi的當(dāng)前值為x）：,下一頁,P1:R1:=Bi; R1:=R1+1 P2:R2=Bi; R2:=R2+1; P1:Bi:=R1; P2:Bi:=R2,可見，Bi的新值是X+1，而不是X+2。這里的P1和P2均為寫者，顯然，對于寫者Bi為臨界資源，因此寫者應(yīng)該互斥。,下一頁,下面給出讀者進(jìn)程與寫者進(jìn)程的一般結(jié)構(gòu)。 var mutex, wrt: semaphore; readcount: integer;

21、 begin seminit ; readcount:=0 cobegin procedure reader; begin P(mutex); Readcount:=readcount+1; If readcount=1 then P (wrt); V(mutex); Reading is performing;,下一頁,P(mutex); readcount:=readcount-1 if readcount=0 then V(wrt); V (mutex); End Procedure writer; Begin P(wrt); writing is performing; V(wrt);

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

23、只允許一個(gè)進(jìn)程進(jìn)入其內(nèi)（即訪問管程內(nèi)的某個(gè)過程），這是由編譯系統(tǒng)保證的。,下一頁,monitor ringbuffer; var rbuffer：array0n-1 of item； k, nextempty, nextfull: integer; empty, full: condition; procedure entry put (var product:item); begin if k=n wait (empty); rbuffer nextempty: product; k:=k+1； nextempty:=(nextempty+1) mod n; signal (full); e

24、nd;,例：以環(huán)形緩沖池為例，給出環(huán)形緩沖池的管程結(jié)構(gòu),下一頁,procedure entry get (var goods:item); begin if k =0 wait (full); goods:=rbuffer nextfull; k:=k-1; nextfull:=(nextfull+1) mod n; signal (empty); end; begin k:=0; nextempty:=0;nextfull:=0; end;,下一頁,在利用管程解決生產(chǎn)者、消費(fèi)者問題時(shí)，其中的生產(chǎn)者和消費(fèi)者可描述為：,producer：begin repeat produce an item；

25、 ringbuffer. put(item)； until false； end consumer：begin repeat ringbuffer. get (item)； consume the item； end,返回本節(jié)目錄,3.7.5 進(jìn)程的通信方式之二消息緩沖,1SEND(A)（發(fā)送消息）原語 2READ（A）（讀取消息）原語,下一頁,1SEND(A)（發(fā)送消息）原語,發(fā)送消息原語被進(jìn)程用于把消息發(fā)送到存放消息的緩沖區(qū)。A是原語的參數(shù)，表示發(fā)送區(qū)的地址。其工作原理是：首先調(diào)用“尋找目標(biāo)進(jìn)程的PCB”的程序查找接收進(jìn)程的PCB，如果接收進(jìn)程存在，申請一個(gè)存放消息的緩沖區(qū)，消息緩沖區(qū)為空

26、時(shí)，接收此消息的進(jìn)程因等待此消息的到來而處于阻塞狀態(tài)，則喚醒此進(jìn)程，并把消息的內(nèi)容、發(fā)送原語的進(jìn)程名和消息等，復(fù)制到預(yù)先申請的存放消息的緩沖區(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ā)送消息過程流圖,下一頁,2READ（A）（讀取消息）原語,READ(A)原語用來讀取消息，接收進(jìn)程讀取消息之前，在自己的空間中確定一個(gè)接收區(qū)。當(dāng)接收進(jìn)程想要讀取消息時(shí)，使用READ(A)原

27、語，A是接收進(jìn)程提供的接收區(qū)開始地址。如圖3.10所示。,下一頁,圖3.10 讀取消息,返回本節(jié)目錄,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)程提出申請資源后，使得有關(guān)進(jìn)程在無外力協(xié)助下，永遠(yuǎn)分配不到必需的資源而無法繼續(xù)運(yùn)行，這就產(chǎn)生了一種特殊的現(xiàn)象死鎖。 在許多實(shí)時(shí)應(yīng)用中，比如計(jì)算機(jī)控制運(yùn)輸和監(jiān)視系統(tǒng)方面，死鎖問題也極為重要。,下一頁,死鎖產(chǎn)生例子1：,我們先來看一個(gè)申請不同類型資源的死鎖例子，假定有兩個(gè)進(jìn)程Pl和P2都要修改文件F

28、，修改時(shí)都需要一條暫時(shí)存放信息的磁帶，而只有一臺(tái)磁帶機(jī)T可用。又假定由于某種原因，在進(jìn)行修改之前，P2需要一暫存磁帶（例如為了修改，要重新組織輸入數(shù)據(jù)）。設(shè)F和T都是可重用資源，它們分別表示允許更新文件和允許使用磁帶機(jī)。于是Pl和P2?？捎腥缦滦问剑?下一頁,分析：從上面的申請-釋放過程可以看出，進(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)程處在死鎖狀

29、態(tài)。,下一頁,圖3.11 簡單的死鎖例子,下一頁,死鎖產(chǎn)生例子2：,現(xiàn)在我們再來看一個(gè)關(guān)于相同類型資源共享的死鎖例子，假設(shè)有一類可再使用資源R，例如主存或外存，它包含有m個(gè)頁面或扇區(qū)，由n個(gè)進(jìn)程P1，P2，Pn（2mn）共享。假定每個(gè)進(jìn)程按右圖順序申請和釋放頁面（或扇區(qū)）：,下一頁,分析：這里每次申請和釋放只涉及R的一個(gè)分配單元（頁或扇區(qū)）。因此，當(dāng)把所有單元全部分配完畢時(shí)，便很容易發(fā)生死鎖；占有R的單元的所有進(jìn)程（前m個(gè)進(jìn)程）會(huì)永遠(yuǎn)阻塞在第二次申請上，而有些進(jìn)程（nm個(gè)進(jìn)程）類似地會(huì)阻塞在它們的第一次申請上，在圖3.12中說明了n3，m2時(shí)這種系統(tǒng)的狀態(tài)，這類死鎖是相當(dāng)普遍的。,下一頁,圖3.12 同類資源共享時(shí)的死鎖現(xiàn)象,下一頁,產(chǎn)生死鎖有四個(gè)必要條件：,產(chǎn)生死鎖有四個(gè)必要條件： （1）互斥條件。 （2）不剝奪條件。 （3）請求和保持條件。 （4）環(huán)路等待條件。,返回本節(jié)目錄,3.8.2 預(yù)防死鎖,1破壞“請求與保持條件” 2破壞環(huán)路條件 3資源受控動(dòng)態(tài)分配,1破壞“請求與保持條件”,這種方法的基本思想是：每個(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)生