第二章 計(jì)算機(jī)操作系統(tǒng)進(jìn)程管理

學(xué)院:計(jì)算機(jī)與信息技術(shù)學(xué)院教師:劉賢梅第二章進(jìn)程管理3/23/20241內(nèi)容概述2.1進(jìn)程的基本概念2.2進(jìn)程控制2.3進(jìn)程同步2.4經(jīng)典進(jìn)程的同步問(wèn)題2.5進(jìn)程通信2.6線(xiàn)程進(jìn)程管理的主要功能是把處理機(jī)分配給進(jìn)程,并對(duì)處理器運(yùn)行進(jìn)行有效地控制和管理,以及協(xié)調(diào)各個(gè)進(jìn)程之間的相互關(guān)系。3/23/202422.1進(jìn)程的基本概念2.1.1程序的順序執(zhí)行及其特征2.1.2前趨圖2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進(jìn)程的特征與狀態(tài)2.1.5進(jìn)程控制塊3/23/20243圖2-1程序的順序執(zhí)行1.程序的順序執(zhí)行僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進(jìn)行計(jì)算時(shí)，總須先輸入用戶(hù)的程序和數(shù)據(jù)，然后進(jìn)行計(jì)算，最后才能打印計(jì)算結(jié)果。

S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;2.1.1程序的順序執(zhí)行及其特征3/23/202442.程序順序執(zhí)行時(shí)的特征(1)順序性:處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行,只有當(dāng)上一個(gè)操作完成后,下一個(gè)操作才能執(zhí)行。(2)封閉性:程序運(yùn)行在一個(gè)封閉的環(huán)境中,即程序運(yùn)行時(shí)獨(dú)占系統(tǒng)的全部資源,這些資源的狀態(tài)只能因程序的執(zhí)行而改變,不受任何外界因素的影響。(3)可再現(xiàn)性:由于程序順序執(zhí)行的封閉性,只要程序順序執(zhí)行的初始條件和環(huán)境相同,則不論何時(shí)執(zhí)行,也不論程序執(zhí)行期間是否存在停頓,程序所得的結(jié)果也相同。結(jié)論:正由于程序順序執(zhí)行的特點(diǎn),程序員可以檢測(cè)和重現(xiàn)程序的錯(cuò)誤,可以調(diào)試和校正程序。3/23/202452.1進(jìn)程的基本概念2.1.1程序的順序執(zhí)行及其特征2.1.2前趨圖2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進(jìn)程的特征與狀態(tài)2.1.5進(jìn)程控制塊3/23/202462.1.2前趨圖(PrecedenceGraph)

前趨圖是一個(gè)有向無(wú)循環(huán)圖，記為DAG。用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。圖中的每個(gè)結(jié)點(diǎn)可用于描述一個(gè)程序段或進(jìn)程，乃至一條語(yǔ)句；結(jié)點(diǎn)間的有向邊則用于表示兩個(gè)結(jié)點(diǎn)之間存在的偏序或前趨關(guān)系“→”。→={(Pi,Pj)|PimustcompletebeforePjmaystart},如果(Pi,Pj)∈→,可寫(xiě)成Pi→Pj：稱(chēng)Pi是Pj的直接前趨，而稱(chēng)Pj是Pi的直接后繼。把沒(méi)有前趨的結(jié)點(diǎn)稱(chēng)為初始結(jié)點(diǎn)(InitialNode)，把沒(méi)有后繼的結(jié)點(diǎn)稱(chēng)為終止結(jié)點(diǎn)(FinalNode)。3/23/20247每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間。圖2-2前趨圖×直接前趨直接后繼初始結(jié)點(diǎn)終止結(jié)點(diǎn)3/23/20248對(duì)于圖2-2(a)所示的前趨圖,存在下述前趨關(guān)系P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9或表示為:P={P1,P2,P3,P4,P5,P6,P7,P8,P9}→={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)}應(yīng)當(dāng)注意,前趨圖中必須不存在循環(huán),但在圖2-2(b)中卻有著下述的前趨關(guān)系:S2→S3,S3→S23/23/202492.1進(jìn)程的基本概念2.1.1程序的順序執(zhí)行及其特征2.1.2前趨圖2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進(jìn)程的特征與狀態(tài)2.1.5進(jìn)程控制塊3/23/2024102.1.3程序的并發(fā)執(zhí)行及其特征

1.程序的并發(fā)執(zhí)行

圖2-3并發(fā)執(zhí)行時(shí)的前趨圖并發(fā)輸入程序I計(jì)算程序C輸出程序P3/23/202411下述四條語(yǔ)句的程序段:S1:a:=x+2S2:b:=y+4S3:c:=a+bS4:d:=c+6圖2-4四條語(yǔ)句的前趨關(guān)系什么樣的程序可以并發(fā)執(zhí)行？3/23/2024122.程序并發(fā)執(zhí)行時(shí)的特征

(1)間斷性

相互制約導(dǎo)致并發(fā)程序具有“執(zhí)行-暫停-執(zhí)行”的間斷性活動(dòng)規(guī)律。(2)失去封閉性

系統(tǒng)中多道程序共享資源，資源的狀態(tài)由多個(gè)程序來(lái)改變，必然失去了程序的封閉性。(3)不可再現(xiàn)性 失去封閉性－>失去可再現(xiàn)性，外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可重復(fù)特征。3/23/202413例如,有兩個(gè)程序A和B,它們共享一個(gè)變量N(初始值為x)。

A: N:=N+1B: Print(N); N:=0;

程序A和B并發(fā)執(zhí)行，可出現(xiàn)以下三種情況:(1)N:=N+1在Print(N)和N:=0之前,此時(shí)得到的N值分別為x+1,x+1,0。

(2)N:=N+1在Print(N)和N:=0之后,此時(shí)得到的N值分別為x,0,1。

(3)N:=N+1在Print(N)和N:=0之間,此時(shí)得到的N值分別為x,x+1,0。

3/23/2024142.1進(jìn)程的基本概念2.1.1程序的順序執(zhí)行及其特征2.1.2前趨圖2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進(jìn)程的特征與狀態(tài)2.1.5進(jìn)程控制塊3/23/2024152.1.4進(jìn)程的特征與狀態(tài)1、進(jìn)程實(shí)體的構(gòu)成(1)程序(段)：進(jìn)程要進(jìn)行的操作。(2)數(shù)據(jù)段：包括操作的數(shù)據(jù)和程序自己的變量。(3)進(jìn)程控制塊PCB(ProcessControlBlock)：存放進(jìn)程標(biāo)識(shí)符、進(jìn)程運(yùn)行的當(dāng)前狀態(tài)、程序和數(shù)據(jù)的地址、程序運(yùn)行時(shí)的CPU環(huán)境等。3/23/2024162.1.4進(jìn)程的特征與狀態(tài)

2.進(jìn)程的特征

結(jié)構(gòu)特征：進(jìn)程的創(chuàng)建與撤消就是PCB的創(chuàng)建與撤消。動(dòng)態(tài)性：進(jìn)程是一個(gè)動(dòng)態(tài)的概念，實(shí)質(zhì)上是程序的一次執(zhí)行過(guò)程。進(jìn)程具有生命期：它因“創(chuàng)建”而產(chǎn)生，因“調(diào)度”而執(zhí)行，執(zhí)行時(shí)還走走停停，因“撤消”而滅亡。并發(fā)性：多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中,且能在一段時(shí)間內(nèi)同時(shí)運(yùn)行,共享系統(tǒng)資源;引入進(jìn)程實(shí)體的目的就是并發(fā)執(zhí)行。3/23/2024172.進(jìn)程的特征獨(dú)立性：進(jìn)程是一個(gè)能獨(dú)立運(yùn)行的基本單位，也是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位。異步性：各進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)。3.進(jìn)程的定義

進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程,是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。3/23/2024184.進(jìn)程與程序的區(qū)別進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合，它可以復(fù)制；進(jìn)程是程序在數(shù)據(jù)集上的一次執(zhí)行。進(jìn)程是暫時(shí)的,程序是永久的：進(jìn)程是一個(gè)狀態(tài)變化的過(guò)程，有它的撤銷(xiāo)，程序可長(zhǎng)久保存。進(jìn)程具有結(jié)構(gòu)特征：由程序段、數(shù)據(jù)段和進(jìn)程控制塊三者組成，而程序僅是指令的有序集合,是進(jìn)程的組成部分之一。進(jìn)程與程序的對(duì)應(yīng)關(guān)系：通過(guò)多次執(zhí)行，一個(gè)程序可對(duì)應(yīng)多個(gè)進(jìn)程。3/23/2024195.進(jìn)程的狀態(tài)(1)進(jìn)程的三種基本狀態(tài)就緒(Ready)狀態(tài)：進(jìn)程已獲得除處理機(jī)外的所需資源，等待分配處理機(jī)資源；只要分配CPU就可執(zhí)行。執(zhí)行(Running)狀態(tài)：處于就緒狀態(tài)的進(jìn)程一旦獲得了處理機(jī)，進(jìn)程狀態(tài)就處于執(zhí)行狀態(tài)。阻塞(Blocked)狀態(tài)(“等待”或“睡眠”)：由于進(jìn)程等待某種事件(如I/O操作或進(jìn)程同步)，在事件發(fā)生之前無(wú)法繼續(xù)執(zhí)行。該事件發(fā)生前即使把處理機(jī)分配給該進(jìn)程,也無(wú)法運(yùn)行。如:請(qǐng)求I/O操作，申請(qǐng)緩沖空間等。3/23/202420圖2-5進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換1.時(shí)間片用光2.有優(yōu)先級(jí)高的進(jìn)程到來(lái)3/23/202421引入掛起狀態(tài)的原因終端用戶(hù)的請(qǐng)求父進(jìn)程請(qǐng)求負(fù)荷調(diào)節(jié)的需要操作系統(tǒng)的需要

(2)進(jìn)程的掛起狀態(tài)圖2-6具有掛起狀態(tài)的進(jìn)程狀態(tài)圖3/23/202422(3)進(jìn)程的其它兩種狀態(tài)

創(chuàng)建狀態(tài)：當(dāng)一個(gè)新進(jìn)程剛剛建立,還未將其放入就緒隊(duì)列時(shí)的狀態(tài)，稱(chēng)為新?tīng)顟B(tài)。終止?fàn)顟B(tài)：當(dāng)一個(gè)進(jìn)程已經(jīng)正常結(jié)束或異常結(jié)束，操作系統(tǒng)已將其從系統(tǒng)隊(duì)列中移出，但尚未撤消，這時(shí)稱(chēng)為終止?fàn)顟B(tài)。3/23/202423圖2-7進(jìn)程的五種基本狀態(tài)及其轉(zhuǎn)換3/23/2024242.1進(jìn)程的基本概念2.1.1程序的順序執(zhí)行及其特征2.1.2前趨圖2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進(jìn)程的特征與狀態(tài)2.1.5進(jìn)程控制塊3/23/2024252.1.5進(jìn)程控制塊

1.進(jìn)程控制塊的作用進(jìn)程控制塊的作用是使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序(含數(shù)據(jù))，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；蛘哒f(shuō)，OS是根據(jù)PCB來(lái)對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。記錄了操作系統(tǒng)所需的,用于描述進(jìn)程情況及控制進(jìn)程運(yùn)行所需的全部信息。

PCB是進(jìn)程存在的唯一標(biāo)志。3/23/2024262.進(jìn)程控制塊中的信息

進(jìn)程標(biāo)識(shí)符內(nèi)部標(biāo)識(shí)符和外部標(biāo)識(shí)符。處理機(jī)狀態(tài)①通用寄存器②指令計(jì)數(shù)器PC③程序狀態(tài)字PSW④用戶(hù)棧指針進(jìn)程調(diào)度信息①進(jìn)程狀態(tài)②進(jìn)程優(yōu)先級(jí)③進(jìn)程調(diào)度所需的其它信息④事件進(jìn)程控制信息①程序和數(shù)據(jù)的地址②進(jìn)程同步和通信機(jī)制③資源清單④鏈接指針struct

pcb{

intid;//進(jìn)程序號(hào)

int

ra;//所需資源A的數(shù)量

int

rb;//所需資源B的數(shù)量

int

rc;//所需資源C的數(shù)量

int

ntime;//所需的時(shí)間片個(gè)數(shù)

int

rtime;//已經(jīng)運(yùn)行的時(shí)間片個(gè)數(shù)

charstate;//進(jìn)程狀態(tài)

struct

pcb*next;}3/23/202427圖2-9PCB鏈接隊(duì)列示意圖3.進(jìn)程控制塊的組織方式(1)鏈接方式

(2)索引方式3/23/202428圖2-10按索引方式組織PCB3.進(jìn)程控制塊的組織方式(1)鏈接方式(2)索引方式3/23/202429內(nèi)容概述2.1進(jìn)程的基本概念

2.2進(jìn)程控制

2.3進(jìn)程同步2.4經(jīng)典進(jìn)程的同步問(wèn)題2.5進(jìn)程通信2.6線(xiàn)程3/23/2024302.2進(jìn)程控制1.系統(tǒng)態(tài)和用戶(hù)態(tài)處理機(jī)的執(zhí)行狀態(tài)分系統(tǒng)態(tài)和用戶(hù)態(tài)兩種:(1)系統(tǒng)態(tài)(管態(tài)、核心態(tài))：有較高特權(quán)，能執(zhí)行一切指令，訪(fǎng)問(wèn)所有寄存器和存儲(chǔ)區(qū)。

(2)用戶(hù)態(tài)(目態(tài))：有較低特權(quán)，能執(zhí)行規(guī)定指令，訪(fǎng)問(wèn)指定寄存器和存儲(chǔ)區(qū)。 用戶(hù)程序運(yùn)行在用戶(hù)態(tài)，不能執(zhí)行OS指令及區(qū)域。

OS內(nèi)核運(yùn)行在系統(tǒng)態(tài)，進(jìn)程控制是由OS內(nèi)核實(shí)現(xiàn)的。3/23/2024312.2進(jìn)程控制2.進(jìn)程控制的功能

進(jìn)程控制是進(jìn)程管理中最基本的功能：創(chuàng)建新進(jìn)程終止已結(jié)束進(jìn)程終止由于某事件而無(wú)法運(yùn)行下去的進(jìn)程負(fù)責(zé)進(jìn)程的狀態(tài)轉(zhuǎn)換進(jìn)程控制一般由OS的內(nèi)核中的原語(yǔ)來(lái)實(shí)現(xiàn)的。3/23/2024322.2進(jìn)程控制3.原語(yǔ)由若干條指令構(gòu)成的“原子操作”過(guò)程，在執(zhí)行期間不可中斷，作為一個(gè)整體而不可分割。原子操作：一個(gè)操作中的所有動(dòng)作要么全做，要么全不做。原子操作在管態(tài)下執(zhí)行，常駐內(nèi)存。原語(yǔ)的作用是為了實(shí)現(xiàn)進(jìn)程的通信和控制。1.創(chuàng)建原語(yǔ)2.撤消原語(yǔ)3.阻塞原語(yǔ)4.喚醒原語(yǔ)5.掛起原語(yǔ)6.激活原語(yǔ)3/23/2024332.2進(jìn)程控制2.2.1進(jìn)程的創(chuàng)建2.2.2進(jìn)程的終止2.2.3進(jìn)程的阻塞與喚醒2.2.4進(jìn)程的掛起與激活3/23/2024342.2.1進(jìn)程的創(chuàng)建圖2-9進(jìn)程樹(shù)

1.進(jìn)程圖(ProcessGraph)進(jìn)程圖是用于描述一個(gè)進(jìn)程的家族關(guān)系的有向樹(shù)，樹(shù)中的結(jié)點(diǎn)表示進(jìn)程。子進(jìn)程可以繼承父進(jìn)程的資源。撤消父進(jìn)程時(shí)必須同時(shí)撤消子進(jìn)程3/23/2024352.引起創(chuàng)建進(jìn)程的事件

(1)用戶(hù)登錄

(2)作業(yè)調(diào)度

(3)提供服務(wù)

(4)應(yīng)用請(qǐng)求3.進(jìn)程的創(chuàng)建步驟(1)申請(qǐng)空白PCB(2)為新進(jìn)程分配資源(3)初始化進(jìn)程控制塊

(4)將新進(jìn)程插入就緒隊(duì)列3/23/2024362.2進(jìn)程控制2.2.1進(jìn)程的創(chuàng)建2.2.2進(jìn)程的終止2.2.3進(jìn)程的阻塞與喚醒2.2.4進(jìn)程的掛起與激活3/23/2024372.2.2進(jìn)程的終止1.引起進(jìn)程終止的事件

1)正常結(jié)束

2)異常結(jié)束

3)外界干預(yù)3/23/2024382.進(jìn)程的終止過(guò)程

(1)從PCB集合中檢索出該進(jìn)程的PCB,讀出該進(jìn)程的狀態(tài)。

(2)若被終止進(jìn)程正處于執(zhí)行狀態(tài),應(yīng)立即終止該進(jìn)程的執(zhí)行。

(3)若該進(jìn)程還有子孫進(jìn)程,應(yīng)將其所有子孫進(jìn)程予以終止。

(4)將被終止進(jìn)程所擁有的全部資源,歸還給其父進(jìn)程,或者歸還給系統(tǒng)。

(5)將被終止進(jìn)程(它的PCB)從所在隊(duì)列(或鏈表)中移出,等待其他程序來(lái)搜集信息。3/23/2024392.2進(jìn)程控制2.2.1進(jìn)程的創(chuàng)建2.2.2進(jìn)程的終止2.2.3進(jìn)程的阻塞與喚醒2.2.4進(jìn)程的掛起與激活3/23/2024402.2.3進(jìn)程的阻塞與喚醒1.引起進(jìn)程阻塞和喚醒的事件

(1)請(qǐng)求系統(tǒng)服務(wù)(2)啟動(dòng)某種操作(3)新數(shù)據(jù)尚未到達(dá)(4)無(wú)新工作可做3/23/202441

2.進(jìn)程阻塞過(guò)程進(jìn)程調(diào)用阻塞原語(yǔ)block()把自己阻塞，立即停止執(zhí)行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為阻塞，并將PCB插入阻塞隊(duì)列。將本進(jìn)程插入到具有相同事件的阻塞(等待)隊(duì)列。調(diào)度程序進(jìn)行重新調(diào)度,將處理機(jī)分配給另一就緒進(jìn)程，并進(jìn)行切換，亦即，保留被阻塞進(jìn)程的處理機(jī)狀態(tài)(在PCB中)，再按新進(jìn)程的PCB中的處理機(jī)狀態(tài)設(shè)置CPU的環(huán)境。3/23/202442

3.進(jìn)程喚醒過(guò)程調(diào)用喚醒原語(yǔ)wakeup()將等待該事件的進(jìn)程喚醒。喚醒原語(yǔ)執(zhí)行的過(guò)程是把被阻塞的進(jìn)程從等待該事件的阻塞隊(duì)列中移出將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒將該P(yáng)CB插入到就緒隊(duì)列中3/23/2024432.2進(jìn)程控制2.2.1進(jìn)程的創(chuàng)建2.2.2進(jìn)程的終止2.2.3進(jìn)程的阻塞與喚醒2.2.4進(jìn)程的掛起與激活3/23/2024442.2.4進(jìn)程的掛起與激活

1.進(jìn)程的掛起系統(tǒng)將利用掛起原語(yǔ)suspend()將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。suspend()原語(yǔ)的執(zhí)行過(guò)程首先檢查被掛起進(jìn)程的狀態(tài)，若處于活動(dòng)就緒狀態(tài)，便將其改為靜止就緒；對(duì)于活動(dòng)阻塞狀態(tài)的進(jìn)程，則將之改為靜止阻塞。把該進(jìn)程的PCB復(fù)制到某指定的內(nèi)存區(qū)域。若被掛起的進(jìn)程正在執(zhí)行,則轉(zhuǎn)向調(diào)度程序重新調(diào)度。3/23/202445

2.進(jìn)程的激活過(guò)程系統(tǒng)將利用激活原語(yǔ)active()將指定進(jìn)程激活。active()原語(yǔ)執(zhí)行過(guò)程將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)，若是靜止就緒，將之改為活動(dòng)就緒；若為靜止阻塞便將之改為活動(dòng)阻塞。假如采用的是搶占調(diào)度策略，則每當(dāng)有新進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，應(yīng)檢查是否要進(jìn)行重新調(diào)度，即由調(diào)度程序?qū)⒈患せ钸M(jìn)程與當(dāng)前進(jìn)程進(jìn)行優(yōu)先級(jí)的比較，如果被激活進(jìn)程的優(yōu)先級(jí)更低，就不必重新調(diào)度；否則，立即剝奪當(dāng)前進(jìn)程的運(yùn)行，把處理機(jī)分配給剛被激活的進(jìn)程。3/23/202446內(nèi)容概述2.1進(jìn)程的基本概念

2.2進(jìn)程控制2.3進(jìn)程同步

2.4經(jīng)典進(jìn)程的同步問(wèn)題2.5進(jìn)程通信2.6線(xiàn)程3/23/2024472.3進(jìn)程同步進(jìn)程同步的主要任務(wù)是對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，以使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。2.3.1進(jìn)程同步的基本概念2.3.2信號(hào)量機(jī)制2.3.3信號(hào)量的應(yīng)用2.3.4管程機(jī)制3/23/2024482.3.1進(jìn)程同步的基本概念1.兩種形式的制約關(guān)系(1)間接相互制約關(guān)系源于資源共享。如A、B共享打印機(jī)，若A申請(qǐng)打印時(shí)，打印機(jī)已分配給B，則A只能阻塞，等B釋放后再改為就緒，又稱(chēng)為“互斥”。(2)直接相互制約關(guān)系源于進(jìn)程之間的合作關(guān)系。如進(jìn)程A向B提供數(shù)據(jù)，當(dāng)輸入緩沖空時(shí)，B不能得到數(shù)據(jù)而阻塞；反之當(dāng)緩沖滿(mǎn)時(shí)，A無(wú)法寫(xiě)入而阻塞，又稱(chēng)為“同步”。3/23/2024492.臨界資源定義:在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪(fǎng)問(wèn)的資源。例如:打印機(jī)、磁帶機(jī)、卡片輸入機(jī)、變量、表格、數(shù)據(jù)、

指針、數(shù)組等。進(jìn)程之間采取互斥方式實(shí)現(xiàn)對(duì)這些資源的共享。例子：

生產(chǎn)者-消費(fèi)者(producer-consumer)問(wèn)題是一個(gè)著名的進(jìn)程同步問(wèn)題。有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，提供給消費(fèi)者進(jìn)程去消費(fèi)。不能向滿(mǎn)緩沖區(qū)投放產(chǎn)品，不能從空緩沖區(qū)中取產(chǎn)品。3/23/202450

一個(gè)數(shù)組緩沖池，有n個(gè)緩沖區(qū)。

buffer:array［0,1,…,n-1］ofitem

輸入指針inin∶=(in+1)modn。輸出指針outout∶=(out+1)modn。

counter：初始值為0。緩沖池中含有的產(chǎn)品數(shù)目。01n-1inout……3/23/202451producer:repeat{生產(chǎn)者進(jìn)程}

…produceaniteminnextp;//生產(chǎn)一個(gè)產(chǎn)品

…whilecounter=ndono-op;buffer［in］∶

=nextp;//將產(chǎn)品放入緩沖區(qū)內(nèi)

in∶=in+1modn;counter∶=counter+1;//緩沖池中產(chǎn)品數(shù)加一

untilfalse;consumer:repeat{消費(fèi)者進(jìn)程}

whilecounter=0dono-op;

nextc∶=buffer［out］;//從緩沖區(qū)中消費(fèi)產(chǎn)品

out∶=(out+1)modn;counter∶=counter-1;//緩沖池中產(chǎn)品數(shù)減一

consumertheiteminnextc;//消費(fèi)一個(gè)產(chǎn)品

untilfalse;3/23/202452

雖然上面的生產(chǎn)者程序和消費(fèi)者程序，在分別看時(shí)都是正確的，而且兩者在順序執(zhí)行時(shí)其結(jié)果也會(huì)是正確的，但若并發(fā)執(zhí)行時(shí)，就會(huì)出現(xiàn)差錯(cuò)，問(wèn)題就在于這兩個(gè)進(jìn)程共享變量counter。生產(chǎn)者對(duì)它做加1操作，消費(fèi)者對(duì)它做減1操作，這兩個(gè)操作在用機(jī)器語(yǔ)言實(shí)現(xiàn)時(shí)，常可用下面的形式描述：register1∶=counter;register2∶=counter;register1∶=register1+1;register2∶=register2-1;counter∶=register1;counter∶=register2;3/23/202453

假設(shè)：counter的當(dāng)前值是5。如果生產(chǎn)者進(jìn)程先執(zhí)行左列的三條機(jī)器語(yǔ)言語(yǔ)句，然后消費(fèi)者進(jìn)程再執(zhí)行右列的三條語(yǔ)句，則最后共享變量counter的值仍為5；反之，如果讓消費(fèi)者進(jìn)程先執(zhí)行右列的三條語(yǔ)句，然后再讓生產(chǎn)者進(jìn)程執(zhí)行左列的三條語(yǔ)句，counter值也還是5，但是，如果按下述順序執(zhí)行，counter值是4。由于并發(fā)執(zhí)行而失去封閉性。register1∶=counter;(register1=5)register1∶=register1+1;(register1=6)register2∶=counter;(register2=5)register2∶=register2-1;(register2=4)counter∶=register1;(counter=6)counter∶=register2;(counter=4)共享資源的訪(fǎng)問(wèn)互斥3/23/2024543.臨界區(qū)不論是硬件臨界資源還是軟件臨界資源，多個(gè)進(jìn)程必須互斥地對(duì)它進(jìn)行訪(fǎng)問(wèn)。在每個(gè)進(jìn)程中訪(fǎng)問(wèn)臨界資源的那段代碼稱(chēng)為臨界區(qū)。每個(gè)進(jìn)程進(jìn)入臨界區(qū)之前應(yīng)先對(duì)欲訪(fǎng)問(wèn)的臨界資源進(jìn)行檢查，看是否正在被訪(fǎng)問(wèn)。如果此刻該臨界資源未被訪(fǎng)問(wèn)，該進(jìn)程可進(jìn)入臨界區(qū),并設(shè)置它正在被訪(fǎng)問(wèn)的標(biāo)志，在臨界區(qū)之前執(zhí)行的這段代碼稱(chēng)為進(jìn)入?yún)^(qū)。在臨界區(qū)后面也要加上一段代碼，用于將臨界區(qū)被訪(fǎng)問(wèn)的資源恢復(fù)為未被訪(fǎng)問(wèn)的標(biāo)志，稱(chēng)為退出區(qū)。3/23/202455可把一個(gè)訪(fǎng)問(wèn)臨界資源的循環(huán)進(jìn)程描述如下:

repeat

criticalsection; {臨界區(qū)}

remaindersection; {剩余區(qū)}untilfalse;entrysectionexitsection{進(jìn)入?yún)^(qū)}{退出區(qū)}3/23/2024564.同步機(jī)制應(yīng)遵循的規(guī)則(1)空閑讓進(jìn)：當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí),應(yīng)允許一個(gè)進(jìn)程進(jìn)入臨界區(qū),以有效利用臨界資源。(2)忙則等待：當(dāng)有進(jìn)程進(jìn)入臨界區(qū)時(shí),其他進(jìn)程必須等待。(3)有限等待：對(duì)要求訪(fǎng)問(wèn)臨界資源的進(jìn)程,應(yīng)保證在有限時(shí)間內(nèi)進(jìn)入自己的臨界區(qū),防止“死等”。(4)讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入其臨界區(qū)時(shí),應(yīng)立即釋放處理機(jī),防止“忙等”,不能一直用語(yǔ)句判斷能不能進(jìn),占用處理機(jī)。3/23/2024572.3進(jìn)程同步2.3.1進(jìn)程同步的基本概念2.3.2信號(hào)量機(jī)制2.3.3信號(hào)量的應(yīng)用3/23/2024581965年,荷蘭學(xué)者Dijkstra提出的信號(hào)量(Semaphores)機(jī)制是一種有效的進(jìn)程同步工具,所以P、V分別是荷蘭語(yǔ)的test(proberen)和increment(verhogen)。信號(hào)量機(jī)制已從整型信號(hào)量發(fā)展為記錄型信號(hào)量、AND型信號(hào)量,又進(jìn)一步發(fā)展為信號(hào)量集。信號(hào)量就是OS提供的管理公有資源的有效手段。信號(hào)量代表可用資源實(shí)體的數(shù)量。2.3.2信號(hào)量機(jī)制3/23/2024591.整型信號(hào)量除初始化外，僅能通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作wait(S)和signal(S)來(lái)訪(fǎng)問(wèn)。也稱(chēng)為P、V操作。wait和signal操作可描述為:wait(S):whileS≤0dono-op; S:=S-1;signal(S):S:=S+1;wait(S)和signal(S)是原子操作，因此它們?cè)趫?zhí)行時(shí)是不可中斷的。另外，信號(hào)量只能通過(guò)原語(yǔ)操作來(lái)訪(fǎng)問(wèn)，不能被進(jìn)程調(diào)度所打斷。有“忙等”現(xiàn)象。3/23/202460可把一個(gè)訪(fǎng)問(wèn)臨界資源的循環(huán)進(jìn)程描述如下:

repeat

criticalsection; {臨界區(qū)}

remaindersection; {剩余區(qū)}untilfalse;entrysectionexitsectionP(S)或wait(S);V(S)或signal(S);{進(jìn)入?yún)^(qū)}{退出區(qū)}3/23/2024612.記錄型信號(hào)量記錄型信號(hào)量（也稱(chēng)資源信號(hào)量）機(jī)制，則是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制，它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)。在采取了“讓權(quán)等待”的策略后，又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪(fǎng)問(wèn)同一臨界資源的情況。為此，在信號(hào)量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個(gè)進(jìn)程鏈表L，用于鏈接上述的所有等待進(jìn)程。3/23/202462typesemaphore=record

value:integer;//資源數(shù)目

L:listofprocess;//進(jìn)程鏈表指針

endprocedurewait(S)

varS:semaphore;begin

S.value:=S.value-1;ifS.value＜0thenblock(S.L);endproceduresignal(S)

varS:semaphore;begin

S.value:=S.value+1;ifS.value≤0thenwakeup(S.L);end請(qǐng)求一個(gè)單位的該類(lèi)資源該類(lèi)資源數(shù)減少一個(gè)自我阻塞，放棄處理機(jī)釋放一個(gè)單位資源該類(lèi)資源增加一個(gè)喚醒進(jìn)程3/23/2024633.AND型信號(hào)量

在有些任務(wù)中,一個(gè)進(jìn)程先要獲得多個(gè)共享資源后才能執(zhí)行，若進(jìn)程A和B都要申請(qǐng)D和E兩種資源，設(shè)信號(hào)量Dmutex和Emutex的初值均為1在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)Dmutex和Emutex的操作，即processA: processB:

P(Dmutex); P(Emutex);

P(Emutex); P(Dmutex);若進(jìn)程A和B按下述次序交替執(zhí)行P操作:processA:P(Dmutex);于是Dmutex=0processB:P(Emutex);于是Emutex=0processA:P(Emutex);于是Emutex=-1A阻塞

processB:P(Dmutex);于是Dmutex=-1B阻塞

3/23/202464

AND同步機(jī)制的基本思想是:將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源,一次性全部地分配給進(jìn)程,待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程,其它所有可能為之分配的資源,也不分配給他。亦即,對(duì)若干個(gè)臨界資源的分配,采取原子操作方式:要么全部分配到進(jìn)程,要么一個(gè)也不分配。由死鎖理論可知,這樣就可避免上述死鎖情況的發(fā)生。為此,在P操作中,增加了一個(gè)“AND”條件,故稱(chēng)為AND同步,或稱(chēng)為同時(shí)P操作,

即SP(Simultaneouswait)定義如下:3/23/202465SP:Swait(S1,S2,…,Sn)ifSi≥1and…andSn≥1then{每個(gè)資源都可用}fori:=1tondoSi:=Si-1;{分配所有資源}

endfor

else{否則,將進(jìn)程放到等待資源Si的隊(duì)列中}

“阻塞”(去第1個(gè)Si<1的“等待Si”的阻塞隊(duì)列中排隊(duì),并置它的程序計(jì)數(shù)器于SP操作的起始點(diǎn))

endifSV:Ssignal(S1,S2,…,Sn)fori:=1tondoSi=Si+1;{釋放所有資源}

“喚醒”(所有“等待Si”的阻塞進(jìn)程,置為“就緒”狀態(tài),移到就緒隊(duì)列中)

endfor;3/23/2024664.信號(hào)量集:一次申請(qǐng)多個(gè)資源在記錄型信號(hào)量機(jī)制中,P(S)和V(S)操作僅能對(duì)信號(hào)量施以加1或減1操作,意味著每次只能獲得或釋放一個(gè)單位的臨界資源,效率較低。在有些情況下,當(dāng)資源數(shù)量低于某下限值時(shí)便不予分配。因而,在每次分配之前,都必須測(cè)試該資源的數(shù)量,看其是否大于下限值。在對(duì)AND型信號(hào)量機(jī)制擴(kuò)充的基礎(chǔ)上,形成一般化的“信號(hào)量集”機(jī)制。3/23/202467SP:Swait(S1,t1,d1,…,Sn,tn,dn)ifSi≥t1and…andSn≥tnthenfori:=1tondoSi:=Si-di;{一次分配d個(gè)資源}

endfor

else

“阻塞”(去第1個(gè)Si<ti的“等待Si”的阻塞隊(duì)列中排隊(duì))

endif

SV:Ssignal(S1,d1,…,Sn,dn)fori:=1tondoSi:=Si+di;{釋放所有資源}“喚醒”(所有“等待Si”的阻塞進(jìn)程,置為“就緒”狀態(tài),移到就緒隊(duì)列中)

endfor;3/23/202468一般“信號(hào)量集”的幾種特殊情況:(1)SP(S,d,d)。此時(shí)在信號(hào)量集中只有一個(gè)信號(hào)量S,但允許它每次申請(qǐng)d個(gè)資源,當(dāng)現(xiàn)有資源數(shù)少于d時(shí),不予分配。

(2)SP(S,1,1)。此時(shí)的信號(hào)量集已蛻化為一般的記錄型信號(hào)量(S＞1時(shí))或互斥信號(hào)量(S=1時(shí))。

(3)SP(S,1,0)。這是一種很特殊且很有用的信號(hào)量操作。當(dāng)S≥1時(shí),允許多個(gè)進(jìn)程進(jìn)入某特定區(qū);當(dāng)S變?yōu)?后,將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之,它相當(dāng)于一個(gè)可控開(kāi)關(guān)。3/23/202469wait(S):whileS≤0dono-op; S:=S-1;signal(S):S:=S+1;procedurewait(S)

varS:semaphore;begin

S.value:=S.value-1;ifS.value＜0thenblock(S.L);endproceduresignal(S)

varS:semaphore;begin

S.value:=S.value+1;ifS.value≤0thenwakeup(S.L);end記錄型信號(hào)量：整型信號(hào)量：3/23/2024702.3進(jìn)程同步2.3.1進(jìn)程同步的基本概念2.3.2信號(hào)量機(jī)制2.3.3信號(hào)量的應(yīng)用3/23/2024712.3.3信號(hào)量的應(yīng)用1.利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥Var

mutex:semaphore:=1;//信號(hào)量初始值為1

begin

parbegin

process1:begin repeat

P(mutex);//占用資源

criticalsection

V(mutex);

//釋放資源

remainderseetion

untilfalse; end

process2:begin repeat

P(mutex);

criticalsection

V(mutex);

remaindersection untilfalse; end

parend3/23/202472利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥利用整型信呈量機(jī)制實(shí)現(xiàn)進(jìn)程互斥時(shí)應(yīng)注意，P(mutex)和V(mutex)必須成對(duì)出現(xiàn)。缺少P(mutex)會(huì)導(dǎo)致系統(tǒng)混亂，不能保證對(duì)臨界資源的互斥訪(fǎng)問(wèn)。缺少V(mutex)將會(huì)使臨界資源永遠(yuǎn)不被釋放，從而使因等待該資源而阻塞的進(jìn)程不再被喚醒。3/23/2024732.利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系設(shè)有兩個(gè)并發(fā)進(jìn)程P1和P2。P1中有語(yǔ)句S1，P2中有語(yǔ)句S2，希望在執(zhí)行完S1后執(zhí)行S2。進(jìn)程P1和P2共享一個(gè)公用信號(hào)量a，并賦初值為0。進(jìn)程P1:S1;V(a);進(jìn)程P2:P(a);S2;由于a被初始化為0，若P2先執(zhí)行，必定阻塞，只有在進(jìn)程P1執(zhí)行完使S增為1后，P2才能執(zhí)行S2操作。a3/23/202474圖2-10前趨圖舉例3/23/202475

Var

a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;begin

parbegin

beginS1;V(a);V(b);end; beginP(a);S2;V(c);V(d);end; beginP(b);S3;V(e);end; beginP(c);S4;V(f);end; beginP(d);S5;V(g);end; beginP(f);P(g);P(e);S6;end;

parend

endabcdegf圖2-10前趨圖舉例3/23/202476內(nèi)容概述2.1進(jìn)程的基本概念

2.2進(jìn)程控制2.3進(jìn)程同步2.4經(jīng)典進(jìn)程的同步問(wèn)題

2.5進(jìn)程通信2.6線(xiàn)程3/23/2024772.4經(jīng)典進(jìn)程的同步問(wèn)題2.4.1生產(chǎn)者—消費(fèi)者問(wèn)題2.4.2哲學(xué)家進(jìn)餐問(wèn)題2.4.3讀者—寫(xiě)者問(wèn)題3/23/202478未考慮進(jìn)程的互斥與同步問(wèn)題，會(huì)造成數(shù)據(jù)Counter的不定性。生產(chǎn)者—消費(fèi)者問(wèn)題是相互合作的進(jìn)程關(guān)系的一種抽象。例如，在輸入時(shí)，輸入進(jìn)程是生產(chǎn)者，計(jì)算進(jìn)程是消費(fèi)者；而在輸出時(shí)，則計(jì)算進(jìn)程是生產(chǎn)者，而打印進(jìn)程是消費(fèi)者。

2.4.1生產(chǎn)者—消費(fèi)者問(wèn)題3/23/202479producer:repeat{生產(chǎn)者進(jìn)程}

…produceaniteminnextp;//生產(chǎn)一個(gè)產(chǎn)品

…whilecounter=ndono-op;buffer［in］∶

=nextp;//將產(chǎn)品放入緩沖區(qū)內(nèi)

in∶=in+1modn;counter∶=counter+1;//緩沖池中產(chǎn)品數(shù)加一

untilfalse;consumer:repeat{消費(fèi)者進(jìn)程}

whilecounter=0dono-op;

nextc∶=buffer［out］;//從緩沖區(qū)中消費(fèi)產(chǎn)品

out∶=(out+1)modn;counter∶=counter-1;//緩沖池中產(chǎn)品數(shù)減一

consumertheiteminnextc;//消費(fèi)一個(gè)產(chǎn)品

untilfalse;3/23/2024801.利用記錄型信號(hào)量解決生產(chǎn)者—消費(fèi)者問(wèn)題只要緩沖池未滿(mǎn)，生產(chǎn)者便可將消息送入緩沖池。只要緩沖池未空，消費(fèi)者便可從緩沖池中取走一個(gè)消息?；コ庠L(fǎng)問(wèn)緩沖池。設(shè)置三個(gè)信號(hào)量：empty：表示可供使用的緩沖區(qū)數(shù)，其初值為n。full：表示放有消息的緩沖區(qū)數(shù)，其初值為0。mutex：互斥信號(hào)量，初值為1,表示各進(jìn)程互斥進(jìn)入臨界區(qū)，保證任何時(shí)候只有一個(gè)進(jìn)程使用緩沖區(qū)。3/23/202481Var

mutex,empty,full:semaphore:=1,n,0;

buffer:array［0,…,n-1］ofitem;in,out:integer:=0,0;begin

parbeginproducer:{生產(chǎn)者進(jìn)程}beginrepeat…

生產(chǎn)一條消息=>nextp;…

P(empty);{empty減1}

P(mutex);

buffer(in):=nextp;in:=(in+1)modn;{移動(dòng)生產(chǎn)指針}

V(mutex);

V(full);{full增1}untilfalse;end

consumer:{消費(fèi)者進(jìn)程}beginrepeat

P(full);

P(mutex);

nextc:=buffer(out);out:=(out+1)modn;

V(mutex);

V(empty);

消費(fèi)nextc中的一條消息;

untilfalse;end

parend

end3/23/202482在生產(chǎn)者—消費(fèi)者問(wèn)題中要注意以下幾點(diǎn)：在每個(gè)程序中用于實(shí)現(xiàn)互斥的P(mutex)和V(mutex)必須成對(duì)地出現(xiàn)；對(duì)資源信號(hào)量empty和full的P和V操作，同樣需要成對(duì)地出現(xiàn)，但它們分別處于不同的程序中。例如,P(empty)在計(jì)算進(jìn)程中,而V(empty)則在打印進(jìn)程中,計(jì)算進(jìn)程若因執(zhí)行P(empty)而阻塞,則以后將由打印進(jìn)程將它喚醒；在每個(gè)程序中的多個(gè)P操作順序不能顛倒。應(yīng)先執(zhí)行對(duì)資源信號(hào)量的P操作，然后再執(zhí)行對(duì)互斥信號(hào)量的P操作，否則可能引起進(jìn)程死鎖。3/23/2024832.利用AND信號(hào)量解決生產(chǎn)者—消費(fèi)者問(wèn)題Var

mutex,empty,full:semaphore:=1,n,0;

buffer:array［0,…,n-1］ofitem;inout:integer:=0,0;begin

parbeginproducer:beginrepeat…

生產(chǎn)一條消息=>nextp;…

SP(empty,mutex);

buffer(in):=nextp;in:=(in+1)modn;

SV(mutex,full);untilfalse;endconsumer:beginrepeat

SP(full,mutex);

nextc:=buffer(out);out:=(out+1)modn;

SV(mutex,empty);

消費(fèi)nextc中的一條消息;

untilfalse;end

parendend3/23/2024842.4經(jīng)典進(jìn)程的同步問(wèn)題2.4.1生產(chǎn)者—消費(fèi)者問(wèn)題2.4.2哲學(xué)家進(jìn)餐問(wèn)題2.4.3讀者—寫(xiě)者問(wèn)題3/23/2024852.4.2哲學(xué)家進(jìn)餐問(wèn)題哲學(xué)家進(jìn)餐問(wèn)題(TheDinningPhilosophersProblem)是由Dijkstra提出并解決的典型進(jìn)程同步問(wèn)題。問(wèn)題描述:5個(gè)哲學(xué)家坐在桌子邊,桌上有5個(gè)碗和5支筷子。哲學(xué)家的生活方式交替地進(jìn)行思考和進(jìn)餐。哲學(xué)家饑餓時(shí)便拿起兩邊的筷子進(jìn)餐,但只有當(dāng)拿到兩支后才能進(jìn)餐。用餐畢,放下筷子。3/23/2024861.利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問(wèn)題

經(jīng)分析可知,放在桌子上的筷子是臨界資源,在一段時(shí)間內(nèi)只允許一位哲學(xué)家使用。為了實(shí)現(xiàn)對(duì)筷子的互斥使用,可以用一個(gè)信號(hào)量表示一只筷子,由這五個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組。其描述如下:3/23/202487Varchopstick:array［0,…,4］ofsemaphore:=(1,1,1,1,1);beginrepeat

P(chopstick［i］);

P(chopstick［(i+1)mod5］);

… eat;{進(jìn)餐}…

V(chopstick［i］);

V(chopstick［(i+1)mod5］);

… think;{思考}untilfalse;end問(wèn)題:

每個(gè)哲學(xué)家都拿起左邊的筷子等待右邊的筷子，結(jié)果誰(shuí)也得不到兩把筷子，形成了死鎖。10234104323/23/2024882.利用AND信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問(wèn)題在哲學(xué)家進(jìn)餐問(wèn)題中,要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源(筷子)后方能進(jìn)餐,這在本質(zhì)上就是前面所介紹的AND同步問(wèn)題,故用AND信號(hào)量機(jī)制