第二章 進(jìn)程與處理器管理

1、2.1 進(jìn)程的引入進(jìn)程的引入2.2 進(jìn)程狀態(tài)和管理進(jìn)程狀態(tài)和管理2.3 進(jìn)程同步與通信進(jìn)程同步與通信2.4 處理器調(diào)度處理器調(diào)度2.5 死鎖死鎖2.6 線程線程理解程序并發(fā)運(yùn)行引起的問題，掌握進(jìn)理解程序并發(fā)運(yùn)行引起的問題，掌握進(jìn)程的定義和特征，熟練掌握進(jìn)程的狀態(tài)程的定義和特征，熟練掌握進(jìn)程的狀態(tài)轉(zhuǎn)換及其管理方法。轉(zhuǎn)換及其管理方法。 理解進(jìn)程同步與互斥的含義，熟練掌握理解進(jìn)程同步與互斥的含義，熟練掌握P、V原語實(shí)現(xiàn)的同步與互斥控制，了解進(jìn)程原語實(shí)現(xiàn)的同步與互斥控制，了解進(jìn)程的高級通信機(jī)制。的高級通信機(jī)制。 理解處理器管理的目標(biāo)和任務(wù)，掌握處理解處理器管理的目標(biāo)和任務(wù)，掌握處理器調(diào)度的分類和基本原

2、則；熟練掌握理器調(diào)度的分類和基本原則；熟練掌握進(jìn)程調(diào)度的方法及效率分析。進(jìn)程調(diào)度的方法及效率分析。 理解死鎖的含義，掌握死鎖預(yù)防、死鎖理解死鎖的含義，掌握死鎖預(yù)防、死鎖避免和死鎖檢測與解除的方法。避免和死鎖檢測與解除的方法。 了解線程的概念和特征，理解線程、進(jìn)了解線程的概念和特征，理解線程、進(jìn)程與程序的區(qū)別。程與程序的區(qū)別。 2.1 進(jìn)程的引入2.1.1 程序并發(fā)運(yùn)行帶來的問題程序并發(fā)運(yùn)行帶來的問題I1C1P1I2C2P2圖2.1 單道程序設(shè)計(jì)環(huán)境的程序運(yùn)行特性 2.1.1 程序并發(fā)運(yùn)行帶來的問題（續(xù)）程序并發(fā)運(yùn)行帶來的問題（續(xù)）I1I2I3I4C1C2C3C4P1P2P3P4t圖2.2 多道

3、程序設(shè)計(jì)環(huán)境的程序運(yùn)行特性2.1.2 進(jìn)程的概念進(jìn)程的概念典型的進(jìn)程定義：典型的進(jìn)程定義：進(jìn)程是程序的一次執(zhí)行進(jìn)程是程序的一次執(zhí)行進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)發(fā)生的活動(dòng)進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，它是系進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位2.1.2 進(jìn)程的概念進(jìn)程的概念進(jìn)程（進(jìn)程（Process）是具有獨(dú)立功能的程序）是具有獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合上的一次運(yùn)行活動(dòng)。關(guān)于某個(gè)數(shù)據(jù)集合上的一次運(yùn)行活動(dòng)。與程序的區(qū)別與程序的區(qū)別進(jìn)程是動(dòng)態(tài)的

4、，程序是靜態(tài)的進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的進(jìn)程的存在是暫時(shí)的，程序是永久的進(jìn)程的存在是暫時(shí)的，程序是永久的進(jìn)程包括程序進(jìn)程包括程序進(jìn)程與程序不存在一一對應(yīng)關(guān)系進(jìn)程與程序不存在一一對應(yīng)關(guān)系進(jìn)程可以創(chuàng)建其他子進(jìn)程，而程序則不能進(jìn)程可以創(chuàng)建其他子進(jìn)程，而程序則不能2.1.2 進(jìn)程的基本特征進(jìn)程的基本特征動(dòng)態(tài)性動(dòng)態(tài)性并發(fā)性并發(fā)性獨(dú)立性獨(dú)立性交互性交互性制約性制約性結(jié)構(gòu)性結(jié)構(gòu)性 2.2 進(jìn)程狀態(tài)和管理2.2.1 進(jìn)程狀態(tài)及其轉(zhuǎn)換進(jìn)程狀態(tài)及其轉(zhuǎn)換運(yùn)行態(tài)運(yùn)行態(tài)就緒態(tài)就緒態(tài)阻塞態(tài)阻塞態(tài)等待某事件發(fā)生等待某事件發(fā)生所等待的事件發(fā)生所等待的事件發(fā)生進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換分配到分配到CP

5、U時(shí)間片到時(shí)間片到n問題：問題： 操作系統(tǒng)如何找到進(jìn)程？操作系統(tǒng)如何找到進(jìn)程？ 如何來刻畫一個(gè)進(jìn)程在各個(gè)不同時(shí)期所如何來刻畫一個(gè)進(jìn)程在各個(gè)不同時(shí)期所處的狀態(tài)？處的狀態(tài)？ 如何來描述一個(gè)進(jìn)程和其他進(jìn)程以及系如何來描述一個(gè)進(jìn)程和其他進(jìn)程以及系統(tǒng)資源的關(guān)系呢？統(tǒng)資源的關(guān)系呢？ 2.2.2 進(jìn)程的描述進(jìn)程的描述進(jìn)程控制塊進(jìn)程控制塊1. 進(jìn)程控制塊（進(jìn)程控制塊（PCB）的概念）的概念 所謂進(jìn)程控制塊（所謂進(jìn)程控制塊（PCB， Process Control Block ），就是描述進(jìn)程與其他），就是描述進(jìn)程與其他進(jìn)程、系統(tǒng)資源的關(guān)系以及進(jìn)程在各個(gè)進(jìn)程、系統(tǒng)資源的關(guān)系以及進(jìn)程在各個(gè)不同時(shí)期所處的狀態(tài)的不同

6、時(shí)期所處的狀態(tài)的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)。2.2.2 進(jìn)程的描述進(jìn)程的描述進(jìn)程控制塊進(jìn)程控制塊2. 進(jìn)程控制塊（進(jìn)程控制塊（PCB）的作用）的作用 操作系統(tǒng)是通過操作系統(tǒng)是通過PCB來對并發(fā)運(yùn)行的進(jìn)來對并發(fā)運(yùn)行的進(jìn)程進(jìn)行控制和管理的。具體表現(xiàn)如下：程進(jìn)行控制和管理的。具體表現(xiàn)如下： （1）創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程，就是創(chuàng)建，就是創(chuàng)建PCB，PCB是是系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志。系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志。（2）進(jìn)程與）進(jìn)程與PCB是是一一對應(yīng)一一對應(yīng)的，每一個(gè)的，每一個(gè)進(jìn)程都有自己的進(jìn)程控制塊。進(jìn)程都有自己的進(jìn)程控制塊。2.2.2 進(jìn)程的描述進(jìn)程的描述進(jìn)程控制塊進(jìn)程控制塊2. 進(jìn)程控制塊（進(jìn)程控制塊（PCB）

7、的作用）的作用 （3）PCB集中地反映了一個(gè)進(jìn)程的集中地反映了一個(gè)進(jìn)程的動(dòng)態(tài)動(dòng)態(tài)特征特征。（4）在進(jìn)程并發(fā)運(yùn)行時(shí)，由于資源共享，）在進(jìn)程并發(fā)運(yùn)行時(shí)，由于資源共享，帶來各進(jìn)程之間的相互制約。為了帶來各進(jìn)程之間的相互制約。為了反映反映這些這些制約關(guān)系制約關(guān)系和和資源共享關(guān)系資源共享關(guān)系，是根據(jù)，是根據(jù)PCB中的信息對進(jìn)程實(shí)施有效的管理和中的信息對進(jìn)程實(shí)施有效的管理和控制的?？刂频?。2.2.2 進(jìn)程的描述進(jìn)程的描述進(jìn)程控制塊進(jìn)程控制塊3. 進(jìn)程控制塊（進(jìn)程控制塊（PCB）的內(nèi)容）的內(nèi)容 進(jìn)程名（進(jìn)程名（ID） 進(jìn)程狀態(tài)進(jìn)程狀態(tài) 程序存放位置程序存放位置 數(shù)據(jù)存放位置數(shù)據(jù)存放位置 通用寄存器內(nèi)容通用寄

8、存器內(nèi)容 控制寄存器內(nèi)容控制寄存器內(nèi)容 斷點(diǎn)地址斷點(diǎn)地址 進(jìn)程優(yōu)先數(shù)進(jìn)程優(yōu)先數(shù) 隊(duì)列指針隊(duì)列指針標(biāo)志信息標(biāo)志信息說明信息說明信息現(xiàn)場信息現(xiàn)場信息管理信息管理信息圖圖2-5 PCB所包含的信息所包含的信息4. 進(jìn)程隊(duì)列進(jìn)程隊(duì)列操作系統(tǒng)要管理、控制好進(jìn)程，就必須操作系統(tǒng)要管理、控制好進(jìn)程，就必須首先組織好首先組織好PCB。 系統(tǒng)把所有系統(tǒng)把所有PCB組織在一起，并把它們組織在一起，并把它們放在主存的固定區(qū)域，就構(gòu)成了放在主存的固定區(qū)域，就構(gòu)成了PCB表。表。 PCB表的大小決定了系統(tǒng)中最多可同時(shí)表的大小決定了系統(tǒng)中最多可同時(shí)存在的存在的進(jìn)程個(gè)數(shù)進(jìn)程個(gè)數(shù)，稱為系統(tǒng)的，稱為系統(tǒng)的并發(fā)度并發(fā)度。 空空

9、PCB運(yùn)行態(tài)運(yùn)行態(tài)就緒態(tài)就緒態(tài)阻塞阻塞1阻塞阻塞2PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn.6751015PCB表示意圖表示意圖進(jìn)程隊(duì)列的組織方式進(jìn)程隊(duì)列的組織方式線性方式線性方式 鏈接方式鏈接方式 索引方式索引方式 PCB表線性方式 線性方式線性方式 組織形式簡單、易于實(shí)現(xiàn)組織形式簡單、易于實(shí)現(xiàn) ，此種方式的優(yōu)缺點(diǎn)？此種方式的優(yōu)缺點(diǎn)？PCB1 PCB2 PCB3 PCB4 PCBn-2 PCBn-1 PCBn圖圖2-7 PCB線性隊(duì)列結(jié)構(gòu)示意圖線性隊(duì)列結(jié)構(gòu)示意圖PCB表鏈接方式 鏈接方式鏈接方式 鏈接方式是常采用的方式，不鏈接方式是常采用的方式，不同狀態(tài)的進(jìn)程分別鏈接

10、組成自己的隊(duì)列同狀態(tài)的進(jìn)程分別鏈接組成自己的隊(duì)列PCB表鏈接方式 PCB2PCB3PCB7PCB6 -1PCB5PCB8 -1PCB4 -1PCB10PCB9PCB1 -1運(yùn)行隊(duì)列指針運(yùn)行隊(duì)列指針運(yùn)行隊(duì)列運(yùn)行隊(duì)列:就緒隊(duì)列頭指針就緒隊(duì)列頭指針就緒隊(duì)列就緒隊(duì)列:阻塞隊(duì)列阻塞隊(duì)列1頭指針頭指針阻塞隊(duì)列阻塞隊(duì)列1:阻塞隊(duì)列阻塞隊(duì)列2頭指針頭指針阻塞隊(duì)列阻塞隊(duì)列2:圖圖2-8 PCB鏈接隊(duì)列結(jié)構(gòu)示意圖鏈接隊(duì)列結(jié)構(gòu)示意圖PCB表索引方式 索引方式索引方式 索引方式是利用索引表記載相索引方式是利用索引表記載相應(yīng)狀態(tài)進(jìn)程的應(yīng)狀態(tài)進(jìn)程的PCB地址。地址。 各個(gè)索引表在主存中的起始地址存放在各個(gè)索引表在主存中的

11、起始地址存放在專用指針單元中。專用指針單元中。 PCB表索引方式 圖圖2-9 PCB索引隊(duì)列結(jié)構(gòu)示意圖索引隊(duì)列結(jié)構(gòu)示意圖運(yùn)行指針就緒表指針阻塞表指針阻塞索引表就緒索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB72.2.3 進(jìn)程的控制與管理進(jìn)程控制的功能進(jìn)程控制的功能 完成創(chuàng)建和撤消進(jìn)程，掛起和激活進(jìn)完成創(chuàng)建和撤消進(jìn)程，掛起和激活進(jìn)程等程等完成進(jìn)程狀態(tài)的轉(zhuǎn)換。完成進(jìn)程狀態(tài)的轉(zhuǎn)換。原語的引入問題：問題：操作系統(tǒng)如何保證進(jìn)程在執(zhí)行時(shí)操作系統(tǒng)如何保證進(jìn)程在執(zhí)行時(shí)的絕對正確呢？的絕對正確呢？ 關(guān)鍵進(jìn)程在執(zhí)行時(shí)要以一個(gè)整體出現(xiàn)，關(guān)鍵進(jìn)程在執(zhí)行時(shí)要以一個(gè)整體出現(xiàn)，不可分割。不可分割。原語原語(

12、primitive)：由若干條指令構(gòu)成的由若干條指令構(gòu)成的“原子操作原子操作(atomic operation)”過程，作過程，作為一個(gè)為一個(gè)整體整體而而不可分割不可分割-要么全都完成，要么全都完成，要么全都不做。要么全都不做。原語的引入 許多系統(tǒng)調(diào)用就是原語。許多系統(tǒng)調(diào)用就是原語。 注意：注意：系統(tǒng)調(diào)用并不都是原語。系統(tǒng)調(diào)用并不都是原語。 進(jìn)程進(jìn)程A調(diào)用調(diào)用read()，因無數(shù)據(jù)而阻塞，在，因無數(shù)據(jù)而阻塞，在read()里未返回。然后進(jìn)程里未返回。然后進(jìn)程B調(diào)用調(diào)用read()，此時(shí)此時(shí)read()被重入。系統(tǒng)調(diào)用不一定一次被重入。系統(tǒng)調(diào)用不一定一次執(zhí)行完并返回該進(jìn)程，有可能在特定的執(zhí)行完并

13、返回該進(jìn)程，有可能在特定的點(diǎn)暫停，而轉(zhuǎn)入到其他進(jìn)程。點(diǎn)暫停，而轉(zhuǎn)入到其他進(jìn)程。進(jìn)程控制的主要原語進(jìn)程控制的主要原語 進(jìn)程創(chuàng)建與撤消原語進(jìn)程創(chuàng)建與撤消原語 進(jìn)程阻塞與喚醒原語進(jìn)程阻塞與喚醒原語進(jìn)程掛起與激活原語進(jìn)程掛起與激活原語1. “創(chuàng)建進(jìn)程”原語 引起創(chuàng)建進(jìn)程的事件：引起創(chuàng)建進(jìn)程的事件：用戶登錄：用戶登錄： 為終端用戶建立一進(jìn)程為終端用戶建立一進(jìn)程作業(yè)調(diào)度：（不是進(jìn)程調(diào)度）作業(yè)調(diào)度：（不是進(jìn)程調(diào)度） 為被調(diào)度的作業(yè)建立進(jìn)程為被調(diào)度的作業(yè)建立進(jìn)程提供服務(wù)：提供服務(wù)： 如要打印時(shí)建立打印進(jìn)程如要打印時(shí)建立打印進(jìn)程應(yīng)用請求：應(yīng)用請求： 由應(yīng)用程序建立多個(gè)進(jìn)程由應(yīng)用程序建立多個(gè)進(jìn)程進(jìn)程控制的主要原語

14、進(jìn)程控制的主要原語進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建原語原語進(jìn)程樹進(jìn)程樹ABCDJFGHIEKLM 進(jìn)程樹是有向樹進(jìn)程樹是有向樹 父子關(guān)系表示創(chuàng)建父子關(guān)系表示創(chuàng)建與被創(chuàng)建的關(guān)系與被創(chuàng)建的關(guān)系 父子關(guān)系不表示執(zhí)父子關(guān)系不表示執(zhí)行的先后關(guān)系行的先后關(guān)系1. “創(chuàng)建進(jìn)程”原語 進(jìn)程的創(chuàng)建原語的進(jìn)程的創(chuàng)建原語的操作過程操作過程：（1）申請空白）申請空白PCB； （2）填寫）填寫PCB；（3）為新進(jìn)程分配資源；）為新進(jìn)程分配資源； （4）初始化進(jìn)程控制塊；）初始化進(jìn)程控制塊； （5）將新進(jìn)程插入就緒隊(duì)列。）將新進(jìn)程插入就緒隊(duì)列。入口入口申請空白申請空白PCB有有PCB?填寫填寫PCB的相關(guān)項(xiàng)的相關(guān)項(xiàng)為新進(jìn)程分配資源為新進(jìn)

15、程分配資源初始化進(jìn)程控制塊初始化進(jìn)程控制塊新進(jìn)程插入就緒隊(duì)列新進(jìn)程插入就緒隊(duì)列返回返回有有出錯(cuò)處理出錯(cuò)處理無無創(chuàng)建進(jìn)程原語流程圖創(chuàng)建進(jìn)程原語流程圖Procedure Create(n, S0, P0, M0, R0)Begin i :=GetInternalName(n); i.id := n; i.priority := P0; /* 初始化初始化PCB */ i.CPU_State := S0; i.Mainstore := M0; i.resources := R0; i.status := Ready; j := EP; i.parent := j; /* 插入家族隊(duì)列插入家族隊(duì)列 *

16、/ geny := ; geny := i; i.sdata := RQ; insert( RQ, i ); /* 插入就緒隊(duì)列插入就緒隊(duì)列 */End;查找查找PCB集合，返回集合，返回PCB的內(nèi)部標(biāo)識符的內(nèi)部標(biāo)識符 i 被創(chuàng)建進(jìn)程的外部標(biāo)識符被創(chuàng)建進(jìn)程的外部標(biāo)識符處理機(jī)的初始狀態(tài)處理機(jī)的初始狀態(tài)進(jìn)程優(yōu)先級進(jìn)程優(yōu)先級初始內(nèi)存數(shù)初始內(nèi)存數(shù)所需資源清單所需資源清單進(jìn)程狀態(tài)有關(guān)的指針進(jìn)程狀態(tài)有關(guān)的指針 “創(chuàng)建進(jìn)程”原語描述 2. “撤銷進(jìn)程”原語 當(dāng)一個(gè)進(jìn)程在完成其任務(wù)后應(yīng)予以撤銷，當(dāng)一個(gè)進(jìn)程在完成其任務(wù)后應(yīng)予以撤銷，以便及時(shí)釋放它所占用的資源（外部設(shè)以便及時(shí)釋放它所占用的資源

17、（外部設(shè)備、主存空間等）。備、主存空間等）。 導(dǎo)致進(jìn)程被撤消的原因?qū)е逻M(jìn)程被撤消的原因 一個(gè)進(jìn)程在完成任務(wù)而正常終止一個(gè)進(jìn)程在完成任務(wù)而正常終止 由于錯(cuò)誤導(dǎo)致非正常終止由于錯(cuò)誤導(dǎo)致非正常終止 祖先進(jìn)程要求撤消某個(gè)子進(jìn)程祖先進(jìn)程要求撤消某個(gè)子進(jìn)程2. “撤銷進(jìn)程”原語 進(jìn)程的撤銷原語的進(jìn)程的撤銷原語的操作過程操作過程：（1）查找要被撤消的）查找要被撤消的PCB；（2）如果該進(jìn)程存在，且有子進(jìn)程存在，）如果該進(jìn)程存在，且有子進(jìn)程存在，則需要先行撤消子進(jìn)程；則需要先行撤消子進(jìn)程；（3）如果進(jìn)程正在運(yùn)行，則立即停止其如果進(jìn)程正在運(yùn)行，則立即停止其運(yùn)行，并設(shè)置調(diào)度標(biāo)志為真運(yùn)行，并設(shè)置調(diào)度標(biāo)志為真 ；（4

18、）釋放該進(jìn)程所占全部資源；）釋放該進(jìn)程所占全部資源； （5）釋放該）釋放該P(yáng)CB結(jié)構(gòu)本身。結(jié)構(gòu)本身。入入 口口查進(jìn)程鏈表或進(jìn)程家族查進(jìn)程鏈表或進(jìn)程家族有此有此PCB嗎嗎?釋放該進(jìn)程所占有的資源釋放該進(jìn)程所占有的資源釋放該釋放該P(yáng)CB結(jié)構(gòu)本身結(jié)構(gòu)本身返返 回回有有出錯(cuò)處理出錯(cuò)處理無無該該P(yáng)CB有子進(jìn)程嗎有子進(jìn)程嗎?否否 撤消進(jìn)程原語流程圖撤消進(jìn)程原語流程圖有有是否正在運(yùn)行是否正在運(yùn)行無無設(shè)置調(diào)度標(biāo)志為真設(shè)置調(diào)度標(biāo)志為真是Procedure Destroy(n)Begin Sched := false; i :=GetInternalName(n); Kill(i); if Sched then

19、Scheduler else continue;End;Procedure Kill(i)Begin if i.status = “Running” then stop(i); Sched := True; remove(i.sdata, i); for all Sgeny do Kill(S); for all rMain store i.resources do Release(r); Release (PCB(i)End;（Kill是可遞歸的是可遞歸的）調(diào)用者提供的進(jìn)調(diào)用者提供的進(jìn)程的外部標(biāo)識程的外部標(biāo)識如果進(jìn)程正如果進(jìn)程正在運(yùn)行，則在運(yùn)行，則立即停止其立即停止其運(yùn)行，并設(shè)運(yùn)行

20、，并設(shè)置調(diào)度標(biāo)志置調(diào)度標(biāo)志為真為真 “撤銷進(jìn)程”原語描述 2.3 進(jìn)程同步與通信進(jìn)程同步與通信進(jìn)程同步是操作系統(tǒng)管理進(jìn)程同步是操作系統(tǒng)管理共享資源共享資源和避免并發(fā)和避免并發(fā)進(jìn)程產(chǎn)生與進(jìn)程產(chǎn)生與時(shí)間時(shí)間有關(guān)的錯(cuò)誤的一種手段有關(guān)的錯(cuò)誤的一種手段 。進(jìn)程同步的主要任務(wù)，是使并發(fā)執(zhí)行的諸進(jìn)程進(jìn)程同步的主要任務(wù)，是使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地共享資源和相互合作，從而使程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。序的執(zhí)行具有可再現(xiàn)性。進(jìn)程同步包括進(jìn)程的進(jìn)程同步包括進(jìn)程的互斥互斥和進(jìn)程的和進(jìn)程的同步同步兩個(gè)方兩個(gè)方面。面。 間接相互制約關(guān)系：互斥間接相互制約關(guān)系：互斥直接相互制約關(guān)系

21、：同步直接相互制約關(guān)系：同步2.3.1 進(jìn)程的互斥引例引例教室分配問題教室分配問題多道程序共用一臺打印機(jī)多道程序共用一臺打印機(jī) 飛機(jī)航班售票系統(tǒng)飛機(jī)航班售票系統(tǒng) 解決方法：解決方法：為了使并發(fā)進(jìn)程能正確地運(yùn)行，必須對獨(dú)占為了使并發(fā)進(jìn)程能正確地運(yùn)行，必須對獨(dú)占的共享資源的使用加以的共享資源的使用加以限制限制。 進(jìn)程間的關(guān)系進(jìn)程間的關(guān)系并發(fā)執(zhí)行舉例并發(fā)執(zhí)行舉例 例：例：飛機(jī)訂票系統(tǒng)，兩個(gè)終飛機(jī)訂票系統(tǒng)，兩個(gè)終端，運(yùn)行端，運(yùn)行T1、T2進(jìn)程進(jìn)程 T1 : T2: . . Read(x); Read(x); y1:=x; y2:=x; if y1=1 then if y2=1 then y1:=y1-

22、1; y2:=y2-1; x:=y1; x:=y2; write(x); write(x); . .設(shè)設(shè)x的當(dāng)前值為：的當(dāng)前值為：1001. 若執(zhí)行順序?yàn)椋喝魣?zhí)行順序?yàn)椋?先先T1; 后后T2; 則結(jié)果：則結(jié)果：x = 982. 若執(zhí)行順序?yàn)椋喝魣?zhí)行順序?yàn)椋篢1: Read(x); y1:=x; T2: Read(x); y2:=x;T1: if y1=1 then y1:=y1-1;T2: if y2=1 then y2:=y2-1;T1: write(x);T2: write(x); 則結(jié)果則結(jié)果 x = 99分析：產(chǎn)生錯(cuò)誤的原因是分析：產(chǎn)生錯(cuò)誤的原因是不不加控制地訪問共享變量加控制地訪問

23、共享變量x2.3.1 進(jìn)程的互斥進(jìn)程的互斥是指進(jìn)程的互斥是指并發(fā)進(jìn)程并發(fā)進(jìn)程在在競爭競爭共享共享資資源源時(shí)，任何時(shí)刻最多只允許時(shí)，任何時(shí)刻最多只允許一個(gè)進(jìn)程一個(gè)進(jìn)程去去使用，其他欲使用該資源的進(jìn)程必須使用，其他欲使用該資源的進(jìn)程必須等等待待，直至使用者，直至使用者釋放釋放了該資源后才能讓了該資源后才能讓另一個(gè)進(jìn)程去使用。另一個(gè)進(jìn)程去使用。進(jìn)程的互斥即進(jìn)程的互斥即并發(fā)進(jìn)程并發(fā)進(jìn)程對于對于共享資源共享資源的的使用，必須是使用，必須是排他的、互斥的排他的、互斥的。 互斥的特點(diǎn)（1）互斥進(jìn)程彼此在邏輯上是完全）互斥進(jìn)程彼此在邏輯上是完全無關(guān)無關(guān)的的，各自單獨(dú)運(yùn)行都是正確的，各自單獨(dú)運(yùn)行都是正確的 ；

24、（2）它們的運(yùn)行不具有時(shí)間次序的特征；）它們的運(yùn)行不具有時(shí)間次序的特征；（3）互斥是進(jìn)程之間的一種）互斥是進(jìn)程之間的一種“間接制約間接制約”關(guān)系。關(guān)系。2.3.1 進(jìn)程的互斥操作系統(tǒng)通過對獨(dú)占的共享資源實(shí)行互操作系統(tǒng)通過對獨(dú)占的共享資源實(shí)行互斥的使用，來解決并發(fā)進(jìn)程出現(xiàn)斥的使用，來解決并發(fā)進(jìn)程出現(xiàn)“系統(tǒng)系統(tǒng)資源的競爭資源的競爭”問題。問題。問題：問題：獨(dú)占的共享資源的互斥使用是如獨(dú)占的共享資源的互斥使用是如何實(shí)現(xiàn)的呢？何實(shí)現(xiàn)的呢？引入了引入了臨界資源臨界資源和和臨界區(qū)臨界區(qū)兩個(gè)概念兩個(gè)概念 臨界資源與臨界區(qū)臨界資源與臨界區(qū)（1）臨界資源臨界資源所謂臨界資源（所謂臨界資源（Critical Re

25、source）是指）是指一次僅允許一個(gè)進(jìn)程使用的資源。一次僅允許一個(gè)進(jìn)程使用的資源。計(jì)算機(jī)系統(tǒng)中的臨界資源很多，如物理計(jì)算機(jī)系統(tǒng)中的臨界資源很多，如物理設(shè)備的設(shè)備的輸入機(jī)、打印機(jī)、磁帶機(jī)輸入機(jī)、打印機(jī)、磁帶機(jī)等，稱等，稱為為硬臨界資源硬臨界資源，還有，還有公用變量、數(shù)據(jù)、公用變量、數(shù)據(jù)、表格、隊(duì)列表格、隊(duì)列等等軟臨界資源軟臨界資源。 臨界資源與臨界區(qū)臨界資源與臨界區(qū)（2）臨界區(qū)）臨界區(qū)所謂臨界區(qū)（所謂臨界區(qū)（Critical Section）是指在每）是指在每個(gè)進(jìn)程中個(gè)進(jìn)程中訪問臨界資源的那段程序訪問臨界資源的那段程序，簡，簡稱稱CS區(qū)。區(qū)。 臨界資源與臨界區(qū)臨界資源與臨界區(qū)Q進(jìn)程進(jìn)程AAB進(jìn)

26、程進(jìn)程BCD進(jìn)程進(jìn)程CEF圖圖2-12 并發(fā)進(jìn)程訪問臨界資源示意圖并發(fā)進(jìn)程訪問臨界資源示意圖（3）臨界區(qū)的管理準(zhǔn)則）臨界區(qū)的管理準(zhǔn)則 空閑讓進(jìn)：空閑讓進(jìn)：當(dāng)無進(jìn)程處于臨界區(qū)時(shí)，表明臨界資源處當(dāng)無進(jìn)程處于臨界區(qū)時(shí)，表明臨界資源處于于空閑狀態(tài)，空閑狀態(tài)，應(yīng)允許一個(gè)請求進(jìn)入臨界區(qū)的進(jìn)程立即應(yīng)允許一個(gè)請求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。忙則等待：忙則等待：當(dāng)有若干進(jìn)程同時(shí)要用到同一個(gè)臨界資源當(dāng)有若干進(jìn)程同時(shí)要用到同一個(gè)臨界資源時(shí)，每次時(shí)，每次至多允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)至多允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)；其余的進(jìn)程其余的進(jìn)程必須等待必須等待。有

27、限退出：有限退出：任何一個(gè)進(jìn)入臨界區(qū)運(yùn)行的進(jìn)程必須在任何一個(gè)進(jìn)入臨界區(qū)運(yùn)行的進(jìn)程必須在有有限的時(shí)間限的時(shí)間內(nèi)退出臨界區(qū)，即任何進(jìn)程都不能無限制的內(nèi)退出臨界區(qū)，即任何進(jìn)程都不能無限制的在自己的臨界區(qū)內(nèi)逗留。在自己的臨界區(qū)內(nèi)逗留。有限等待：有限等待：不能強(qiáng)迫一個(gè)進(jìn)程不能強(qiáng)迫一個(gè)進(jìn)程無限地等待無限地等待進(jìn)入它的臨進(jìn)入它的臨界區(qū)，即有進(jìn)程退出臨界區(qū)時(shí)應(yīng)該讓一個(gè)等待進(jìn)入臨界區(qū)，即有進(jìn)程退出臨界區(qū)時(shí)應(yīng)該讓一個(gè)等待進(jìn)入臨界區(qū)的進(jìn)程進(jìn)入它的臨界區(qū)運(yùn)行。界區(qū)的進(jìn)程進(jìn)入它的臨界區(qū)運(yùn)行。讓權(quán)等待：讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，釋放處理機(jī)，以免進(jìn)程陷入以

28、免進(jìn)程陷入“忙等忙等”。2.3.2 進(jìn)程的同步引例引例公交車的司機(jī)和乘務(wù)員協(xié)作問題公交車的司機(jī)和乘務(wù)員協(xié)作問題 司機(jī)司機(jī) P1 售票員售票員 P2 REPEAT REPEAT 啟動(dòng)啟動(dòng) 關(guān)門關(guān)門 正常運(yùn)行正常運(yùn)行 售票售票 到站停到站停 開門開門 UNTIL FALSE UNTIL FALSE 2.3.2 進(jìn)程的同步引例引例進(jìn)程進(jìn)程A把讀入的數(shù)據(jù)記錄存入緩沖器，進(jìn)把讀入的數(shù)據(jù)記錄存入緩沖器，進(jìn)程程B從緩沖器中取出數(shù)據(jù)記錄加工從緩沖器中取出數(shù)據(jù)記錄加工 數(shù)據(jù)記錄數(shù)據(jù)記錄緩沖器緩沖器BA讀讀存存取取加工加工圖圖2-13 進(jìn)程協(xié)作示意圖進(jìn)程協(xié)作示意圖 進(jìn)程的同步概念進(jìn)程的同步概念進(jìn)程的進(jìn)程的同步（同

29、步（Synchronization）是指并是指并發(fā)進(jìn)程之間存在的一種發(fā)進(jìn)程之間存在的一種制約關(guān)系制約關(guān)系，一個(gè)，一個(gè)進(jìn)程的運(yùn)行進(jìn)程的運(yùn)行依賴其他進(jìn)程依賴其他進(jìn)程的運(yùn)行情況，的運(yùn)行情況，即一個(gè)進(jìn)程在沒有收到其他進(jìn)程的消息即一個(gè)進(jìn)程在沒有收到其他進(jìn)程的消息時(shí)必須時(shí)必須等待等待，直至另一進(jìn)程送來消息后，直至另一進(jìn)程送來消息后才繼續(xù)運(yùn)行下去。才繼續(xù)運(yùn)行下去。 同步的特點(diǎn)同步的特點(diǎn)同步是進(jìn)程間共同完成一項(xiàng)任務(wù)時(shí)同步是進(jìn)程間共同完成一項(xiàng)任務(wù)時(shí)直接直接發(fā)生相互作用發(fā)生相互作用的關(guān)系，具有以下的關(guān)系，具有以下特點(diǎn)特點(diǎn)： （1）同步進(jìn)程間具有）同步進(jìn)程間具有合作合作關(guān)系，在邏輯關(guān)系，在邏輯上有某種聯(lián)系；上有某種

30、聯(lián)系； （2）在執(zhí)行時(shí)間上必須按一定的）在執(zhí)行時(shí)間上必須按一定的順序順序協(xié)協(xié)調(diào)進(jìn)行。調(diào)進(jìn)行。（3）同步是進(jìn)程之間的一種）同步是進(jìn)程之間的一種“直接制約直接制約”關(guān)系。關(guān)系。2.3.3 進(jìn)程同步機(jī)制并發(fā)進(jìn)程之間并發(fā)進(jìn)程之間互斥互斥與與同步同步的相互制約關(guān)的相互制約關(guān)系都是要在系都是要在時(shí)間順序時(shí)間順序上對并發(fā)進(jìn)程的操上對并發(fā)進(jìn)程的操作加以某種作加以某種限制限制。 互斥互斥不能同時(shí)進(jìn)入臨界區(qū)。不能同時(shí)進(jìn)入臨界區(qū)。 同步同步執(zhí)行時(shí)有先后順序。執(zhí)行時(shí)有先后順序。進(jìn)程之間的互斥是一種特殊的同步關(guān)系進(jìn)程之間的互斥是一種特殊的同步關(guān)系進(jìn)程同步機(jī)制可分為進(jìn)程同步機(jī)制可分為硬件機(jī)制硬件機(jī)制和和軟件機(jī)軟件機(jī)制制。

31、 1. 加鎖機(jī)制加鎖機(jī)制解決進(jìn)程互斥的最簡單的辦法是解決進(jìn)程互斥的最簡單的辦法是加鎖加鎖。對每個(gè)對每個(gè)臨界區(qū)臨界區(qū)設(shè)置一把設(shè)置一把“鎖鎖”，就可以，就可以解決并發(fā)進(jìn)程互斥進(jìn)入臨界區(qū)的問題。解決并發(fā)進(jìn)程互斥進(jìn)入臨界區(qū)的問題。 （1）加鎖機(jī)制原理）加鎖機(jī)制原理通過為每個(gè)臨界區(qū)或其他互斥資源設(shè)置通過為每個(gè)臨界區(qū)或其他互斥資源設(shè)置一個(gè)一個(gè)布爾變量布爾變量作為鎖，用來代表某個(gè)臨作為鎖，用來代表某個(gè)臨界資源的界資源的可用狀態(tài)可用狀態(tài)。例如，布爾變量例如，布爾變量W，其值為，其值為0時(shí)表示臨界時(shí)表示臨界資源未被使用，處于資源未被使用，處于可用狀態(tài)可用狀態(tài)（開鎖）（開鎖）；其值為其值為1時(shí)表示臨界資源正被使用

32、，處于時(shí)表示臨界資源正被使用，處于不可用狀態(tài)不可用狀態(tài)（加鎖）（加鎖）。 （1）加鎖機(jī)制原理）加鎖機(jī)制原理 加鎖原語加鎖原語Lock(w)定義如下：定義如下： 測試測試W是否為是否為0。 若若W為為0，則將，則將W設(shè)為設(shè)為1。 若若W為為1，則返回到。，則返回到。 整個(gè)操作是一條原語，即不可以中斷，整個(gè)操作是一條原語，即不可以中斷，中間也不允許其他進(jìn)程來改變中間也不允許其他進(jìn)程來改變W的狀態(tài)。的狀態(tài)。（2）加鎖）加鎖/開鎖偽代碼開鎖偽代碼 加鎖加鎖 Lock(w) 開鎖開鎖Unlock(w)Lock(w) Unlock(w)L:if w=1 then goto L w := 0;else w

33、:= 1; （3）加鎖機(jī)制存在的問題）加鎖機(jī)制存在的問題當(dāng)某個(gè)進(jìn)程進(jìn)入臨界區(qū)后，當(dāng)某個(gè)進(jìn)程進(jìn)入臨界區(qū)后，其他進(jìn)程其他進(jìn)程一一旦想進(jìn)入就要旦想進(jìn)入就要不斷測試鎖的狀態(tài)不斷測試鎖的狀態(tài)，直到，直到鎖的狀態(tài)為鎖的狀態(tài)為0，才可進(jìn)入臨界區(qū)。，才可進(jìn)入臨界區(qū)。這樣就會使得這樣就會使得CPU出現(xiàn)出現(xiàn)“忙等忙等”狀態(tài)，狀態(tài)，造成造成CPU的時(shí)間浪費(fèi)，使得系統(tǒng)效率降的時(shí)間浪費(fèi)，使得系統(tǒng)效率降低。低。 2. 信號量與信號量與P、V操作操作信號量信號量semaphore 信號量和信號量和P、V原原語語1968年，由荷蘭學(xué)者年，由荷蘭學(xué)者Dijkstra提出（所以提出（所以P、V分別是荷蘭語的分別是荷蘭語的“發(fā)信號

34、發(fā)信號”和和“等等待待”兩個(gè)詞的首字母），是一種卓有成兩個(gè)詞的首字母），是一種卓有成效的進(jìn)程同步機(jī)制。效的進(jìn)程同步機(jī)制。2. 信號量與信號量與P、V操作操作信號量：信號量：semaphore是一個(gè)數(shù)據(jù)結(jié)構(gòu)，是一個(gè)數(shù)據(jù)結(jié)構(gòu)，定義如下：定義如下： typedef struct int count; Pointer_PCB Queue; Semaphore;信號量說明：信號量說明： Semaphore s;2. 信號量與信號量與P、V操作操作指針指針數(shù)值數(shù)值(-3)PCB1PCB2PCB3信號量信號量進(jìn)程進(jìn)程PCB隊(duì)列隊(duì)列圖圖2-14 信號量的一般結(jié)構(gòu)信號量的一般結(jié)構(gòu)2. 信號量與信號量與P、V操作

35、操作在一個(gè)信號量在一個(gè)信號量S上，只能做規(guī)定的兩種操上，只能做規(guī)定的兩種操作：作：P操作，記為操作，記為P（S）和和V操作，記為操作，記為V（S），），也僅能由這兩個(gè)操作才能改變也僅能由這兩個(gè)操作才能改變S的值。的值。 1）信號量）信號量S上的上的P操作定義操作定義當(dāng)一個(gè)進(jìn)程調(diào)用當(dāng)一個(gè)進(jìn)程調(diào)用P（S）時(shí)，應(yīng)該順序做）時(shí)，應(yīng)該順序做下面兩個(gè)下面兩個(gè)不可分割不可分割的動(dòng)作：的動(dòng)作： S = S -1，即把當(dāng)前信號量，即把當(dāng)前信號量S的取值減的取值減1。 若若S =0，則調(diào)用進(jìn)程，則調(diào)用進(jìn)程繼續(xù)運(yùn)行繼續(xù)運(yùn)行； 若若S 0，則調(diào)用進(jìn)程繼續(xù)運(yùn)行；，則調(diào)用進(jìn)程繼續(xù)運(yùn)行； 若若S=0，則先從與該信號量有關(guān)的

36、隊(duì)列，則先從與該信號量有關(guān)的隊(duì)列Q上摘下一個(gè)等待進(jìn)程，讓它從阻塞狀態(tài)上摘下一個(gè)等待進(jìn)程，讓它從阻塞狀態(tài)變?yōu)樽優(yōu)榫途w狀態(tài)就緒狀態(tài)，到就緒隊(duì)列里排隊(duì)，然，到就緒隊(duì)列里排隊(duì)，然后調(diào)用進(jìn)程繼續(xù)運(yùn)行。后調(diào)用進(jìn)程繼續(xù)運(yùn)行。2）信號量）信號量S上的上的V操作含義操作含義做一次做一次V（S）操作意味著）操作意味著釋放釋放一個(gè)資源，一個(gè)資源，因此對信號量因此對信號量S做加做加1操作。操作。S加加1操作后，若操作后，若S的值大于的值大于0，說明沒有，說明沒有進(jìn)程在等待該資源；進(jìn)程在等待該資源；而而S值為負(fù)值時(shí)，它的絕對值表示的是等值為負(fù)值時(shí)，它的絕對值表示的是等待此資源的進(jìn)程數(shù)，待此資源的進(jìn)程數(shù)，2）信號量）信號

37、量S上的上的V操作含義操作含義所以，在所以，在V（S）操作后，）操作后，S的值小于等的值小于等于于0時(shí)，表示有進(jìn)程在等待該資源，執(zhí)行時(shí)，表示有進(jìn)程在等待該資源，執(zhí)行V（S）操作的進(jìn)程將從等待該資源的隊(duì)）操作的進(jìn)程將從等待該資源的隊(duì)列中列中喚醒喚醒一個(gè)等待進(jìn)程，然后自己繼續(xù)一個(gè)等待進(jìn)程，然后自己繼續(xù)執(zhí)行后面的操作。執(zhí)行后面的操作。 2. 信號量與信號量與P、V操作操作綜上所述，在解決互斥問題時(shí)，如果把綜上所述，在解決互斥問題時(shí)，如果把信號量信號量S的初始值的初始值，理解為是系統(tǒng)中某種，理解為是系統(tǒng)中某種資源的數(shù)目資源的數(shù)目，那么：，那么：在它的上面做在它的上面做P操作，即是操作，即是申請申請一個(gè)

38、資源；一個(gè)資源；在它的上面做在它的上面做V操作，即是操作，即是釋放釋放一個(gè)用完一個(gè)用完的資源。的資源。2. 信號量與信號量與P、V操作操作與信號量與信號量S有關(guān)的隊(duì)列，是有關(guān)的隊(duì)列，是資源等待資源等待隊(duì)列。隊(duì)列。信號量信號量S的值與相應(yīng)資源的使用情況有關(guān)。的值與相應(yīng)資源的使用情況有關(guān)。信號量信號量S的值僅由的值僅由P、V操作改變，操作改變，P、V操作都是原語操作，且操作都是原語操作，且P、V操作必須成操作必須成對出現(xiàn)。對出現(xiàn)。用信號量實(shí)現(xiàn)兩個(gè)進(jìn)程共享一臺打印機(jī)實(shí)現(xiàn)進(jìn)程的互斥示例 設(shè)信號量設(shè)信號量mutex表示打印機(jī)，其初值為表示打印機(jī)，其初值為1，表示打印機(jī)可用（也可理解為有一臺打印機(jī)）。表示

39、打印機(jī)可用（也可理解為有一臺打印機(jī)）。Pa（）（）、Pb（）（）表示表示A、B兩個(gè)進(jìn)程，兩個(gè)進(jìn)兩個(gè)進(jìn)程，兩個(gè)進(jìn)程及其臨界區(qū)代碼可按下述形式組成：程及其臨界區(qū)代碼可按下述形式組成：Pa（）（） Pb（）（） P（mutex）；）； P（mutex）；）；使用打印機(jī)；使用打印機(jī)； 使用打印機(jī)；使用打印機(jī)；V（mutex）；）； V（mutex）；）； 用信號量實(shí)現(xiàn)三個(gè)進(jìn)程分工協(xié)作完成讀入數(shù)據(jù)、加工處理和打印輸出的同步示例。 緩沖區(qū)緩沖區(qū)B1緩沖區(qū)緩沖區(qū)B2R進(jìn)程進(jìn)程C進(jìn)程進(jìn)程P進(jìn)程進(jìn)程圖圖2-15 同步使用緩沖區(qū)示意圖同步使用緩沖區(qū)示意圖一般來說，處理進(jìn)程的一般來說，處理進(jìn)程的同步同步需要需要兩個(gè)

40、兩個(gè)信信號量，一個(gè)用于號量，一個(gè)用于協(xié)調(diào)合作協(xié)調(diào)合作進(jìn)程的推進(jìn)速進(jìn)程的推進(jìn)速度，一個(gè)用于臨界區(qū)的度，一個(gè)用于臨界區(qū)的互斥互斥。 設(shè)四個(gè)信號量及初值為：設(shè)四個(gè)信號量及初值為： B1empty緩沖區(qū)緩沖區(qū)B1空空信號，初值為信號，初值為1； B1full 緩沖區(qū)緩沖區(qū)B1滿滿信號，初值為信號，初值為0； B2empty緩沖區(qū)緩沖區(qū)B2空空信號，初值為信號，初值為1； B2full 緩沖區(qū)緩沖區(qū)B2滿滿信號，初值為信號，初值為0；各進(jìn)程的執(zhí)行步驟如下： P(B1empty)輸入數(shù)據(jù)寫入緩輸入數(shù)據(jù)寫入緩沖區(qū)沖區(qū)B1 V(B1full) P(B1full)從從B1中取出數(shù)據(jù)中取出數(shù)據(jù) V(B1 empt

41、y) 加工數(shù)據(jù)加工數(shù)據(jù) P(B2 empty) 結(jié)果送入結(jié)果送入B2 V(B2full) P(B2full)從從B2中取出數(shù)據(jù)進(jìn)行中取出數(shù)據(jù)進(jìn)行打印打印 V(B2empty)R進(jìn)程進(jìn)程C進(jìn)程進(jìn)程P進(jìn)程進(jìn)程3. 幾個(gè)典型的互斥、同步問題幾個(gè)典型的互斥、同步問題生產(chǎn)者消費(fèi)者問題生產(chǎn)者消費(fèi)者問題哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題 理發(fā)師睡眠問題理發(fā)師睡眠問題 生產(chǎn)者消費(fèi)者問題生產(chǎn)者消費(fèi)者問題 問題描述問題描述：若干進(jìn)程通過有限的共享緩：若干進(jìn)程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，沖區(qū)交換數(shù)據(jù)。其中，生產(chǎn)者生產(chǎn)者進(jìn)程不進(jìn)程不斷寫入，而斷寫入，而消費(fèi)者消費(fèi)者進(jìn)程不斷讀出；共進(jìn)程不斷讀出；共享緩沖區(qū)共有享緩沖區(qū)

42、共有N個(gè)；任何時(shí)刻只能有一個(gè)個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)程可對共享緩沖區(qū)進(jìn)行操作。進(jìn)程可對共享緩沖區(qū)進(jìn)行操作。緩沖區(qū)不滿，生產(chǎn)者才能寫入；緩沖區(qū)緩沖區(qū)不滿，生產(chǎn)者才能寫入；緩沖區(qū)不空，消費(fèi)者才能讀出不空，消費(fèi)者才能讀出同步同步互斥互斥 設(shè)信號量：設(shè)信號量： full是是“滿滿”數(shù)目，初值為數(shù)目，初值為0， empty是是“空空”數(shù)目，初值為數(shù)目，初值為N。實(shí)際上，。實(shí)際上，full和和 empty是同一個(gè)含義：是同一個(gè)含義：full + empty = N mutex用于訪問緩沖區(qū)時(shí)的互斥，初值是用于訪問緩沖區(qū)時(shí)的互斥，初值是1 ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)

43、one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=5Full=0Mutex=1緩沖

44、區(qū)緩沖區(qū)等待隊(duì)列等待隊(duì)列ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=5Full=0Mutex=1緩沖區(qū)緩沖區(qū)Producer makes a new unit等待隊(duì)列等待隊(duì)列ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full

45、);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=4Full=0Mutex=1緩沖區(qū)緩沖區(qū)Producer applies a “empty”等待隊(duì)列等待隊(duì)列ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);

46、/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=4Full=0Mutex=0緩沖區(qū)緩沖區(qū)Producer applies critical section等待隊(duì)列等待隊(duì)列ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=4Full=0Mutex=0緩沖區(qū)緩沖區(qū)Producer puts unit i

47、nto buffer等待隊(duì)列等待隊(duì)列ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=4Full=0Mutex=1緩沖區(qū)緩沖區(qū)Producer goes out critical section等待隊(duì)列等待隊(duì)列ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;

48、V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=4Full=1Mutex=1緩沖區(qū)緩沖區(qū)Producer releases a “full”等待隊(duì)列等待隊(duì)列ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(m

49、utex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=0Full=5Mutex=1緩沖區(qū)緩沖區(qū)Repeat 4 times again等待隊(duì)列等待隊(duì)列ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=0Full=5Mutex=1緩沖區(qū)緩沖區(qū)Producer makes new

50、 unit again等待隊(duì)列等待隊(duì)列ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=-1Full=5Mutex=1緩沖區(qū)緩沖區(qū)Producer applies a “empty”等待隊(duì)列等待隊(duì)列P1ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mu

51、tex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=-1Full=4Mutex=1緩沖區(qū)緩沖區(qū)Consumer applies a “full”等待隊(duì)列等待隊(duì)列P1ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mut

52、ex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=-1Full=4Mutex=0緩沖區(qū)緩沖區(qū)Consumer applies critical section等待隊(duì)列等待隊(duì)列P1ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=-1Full=4Mutex=0緩沖區(qū)緩沖區(qū)Con

53、sumer gets a unit from buffer等待隊(duì)列等待隊(duì)列P1ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=-1Full=4Mutex=1緩沖區(qū)緩沖區(qū)Consumer goes out critical section等待隊(duì)列等待隊(duì)列P1ProducerP(empty);P(mutex);

54、/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=0Full=4Mutex=1緩沖區(qū)緩沖區(qū)Consumer releases a “empty”等待隊(duì)列等待隊(duì)列P1ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);

55、/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=0Full=4Mutex=0緩沖區(qū)緩沖區(qū)Producer applies critical section等待隊(duì)列等待隊(duì)列ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empt

56、y=0Full=4Mutex=0緩沖區(qū)緩沖區(qū)Producer puts unit into buffer等待隊(duì)列等待隊(duì)列ProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(full);/退出區(qū)退出區(qū)ConsumerP(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unit buffer;V(mutex);V(empty);/退出區(qū)退出區(qū)P1.PnC1.Cn變量：變量：Empty=0Full=4Mutex=0緩沖區(qū)緩沖區(qū)生產(chǎn)者與生產(chǎn)者互斥生產(chǎn)者與生產(chǎn)者互斥消費(fèi)者與消費(fèi)者互斥消費(fèi)者與消費(fèi)者互斥生產(chǎn)者與消費(fèi)者同步生產(chǎn)者與消

57、費(fèi)者同步操作的順序很重要，不當(dāng)會產(chǎn)生死鎖。操作的順序很重要，不當(dāng)會產(chǎn)生死鎖。如假定如假定Producer和和Consumer如下：如下：Consumer：Producer：P(empty);P(mutex); one unitbuf;V(mutex);V(full);P(full);P(mutex);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unitbuf;V(mutex);V(empty);/退出區(qū)退出區(qū)當(dāng)當(dāng)full=0, mutex = 1時(shí)，執(zhí)行順序：時(shí)，執(zhí)行順序： Consumer.P(mutex) ; Consumer.P(full); / C阻塞，等待阻塞，等待Producer 發(fā)出的發(fā)出的full

58、信號信號 Producer.P(empty) ; Producer.P(mutex) ; / P 阻塞，等待阻塞，等待Consumer發(fā)出的發(fā)出的mutex信號信號死鎖死鎖 ，還有其他的執(zhí)行序列可以產(chǎn)生死鎖嗎？，還有其他的執(zhí)行序列可以產(chǎn)生死鎖嗎？資源信號量在前，互斥信號量在后資源信號量在前，互斥信號量在后解決辦法：解決辦法：Consumer：Producer：P(mutex);P(empty); one unitbuf;V(mutex);V(full);P(mutex);P(full);/進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) one unitbuf;V(mutex);V(empty);/退出區(qū)退出區(qū)當(dāng)當(dāng)empty=0

59、, mutex = 1時(shí)，執(zhí)行順序：時(shí)，執(zhí)行順序：Producer.P(mutex) ; Producer.P(empty) ; / P 阻塞，等待阻塞，等待Consumer發(fā)出的發(fā)出的empty信號信號 Consumer.P(full) ; Consumer.P(mutex); / C阻塞，等待阻塞，等待Producer 發(fā)出的發(fā)出的mutex信號信號 形式化描述形式化描述Var mutex,empty,full:semaphore:=1,n,0; buffer:array0,n-1 of item; in,out:integer:=0,0; begin parbegin producer:

60、 begin repeat produce an item; P(empty); P(mutex); buffer(in):=item; in:=(in+1) mod n; V(mutex); V(full); until false; end consumer: begin repeat P(full); P(mutex); item:=buffer(out); out:=(out+1) mod n; V(mutex); V(empty); consume the item; until false; end parend end full是是“滿滿”數(shù)目，初值為數(shù)目，初值為0， empty