第2章進程管理

操作系統(tǒng)第二章進程管理院(系):計算機科學(xué)與技術(shù)學(xué)院研究室:軟件支持技術(shù)教師:印桂生、王紅濱2025/1/141內(nèi)容概述2.1進程的基本概念2.2進程控制2.3進程同步2.4經(jīng)典進程的同步問題2.5管程機制2.6進程通信2.7線程進程管理的主要功能是把處理機分配給進程,并對處理器運行進行有效地控制和管理,以及協(xié)調(diào)各個進程之間的相互關(guān)系。2025/1/1422.1進程的基本概念2.1.1程序的順序執(zhí)行及其特征2.1.2前趨圖2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進程的特征與狀態(tài)2.1.5進程控制塊2025/1/1432.1.2前趨圖(PrecedenceGraph)前趨圖是一個有向無循環(huán)圖,記為DAG(DirectedAcyclicGraph),用于描述進程之間執(zhí)行的前后關(guān)系。圖中的每個結(jié)點可用于描述一個程序段或進程,乃至一條語句;結(jié)點間的有向邊則用于表示兩個結(jié)點之間存在的偏序(PartialOrder)或前趨關(guān)系(PrecedenceRelation)“→”。

→={(Pi,Pj)|PimustcompletebeforePjmaystart},如果(Pi,Pj)∈→,可寫成Pi→Pj,稱Pi是Pj的直接前趨,而稱Pj是Pi的直接后繼。在前趨圖中,把沒有前趨的結(jié)點稱為初始結(jié)點(InitialNode),把沒有后繼的結(jié)點稱為終止結(jié)點(FinalNode)。2025/1/144每個結(jié)點還具有一個重量(Weight),用于表示該結(jié)點所含有的程序量或結(jié)點的執(zhí)行時間。圖2-2前趨圖2025/1/145對于圖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→S22025/1/1462.1進程的基本概念2.1.1程序的順序執(zhí)行及其特征2.1.2前趨圖2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進程的特征與狀態(tài)2.1.5進程控制塊2025/1/147程序的執(zhí)行有兩種方式:順序執(zhí)行和并發(fā)執(zhí)行。順序執(zhí)行是單道批處理系統(tǒng)的執(zhí)行方式,也用于簡單的單片機系統(tǒng);現(xiàn)在的操作系統(tǒng)多為并發(fā)執(zhí)行,具有許多新的特征。引入并發(fā)執(zhí)行的目的是為了提高資源利用率。2025/1/148圖2-1程序的順序執(zhí)行1.程序的順序執(zhí)行這是最自然、也是最初的設(shè)計。僅當(dāng)前一操作(程序段)執(zhí)行完后,才能執(zhí)行后繼操作。例如,在進行計算時,總須先輸入用戶的程序和數(shù)據(jù),然后進行計算,最后才能打印計算結(jié)果。S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;2.1.1程序的順序執(zhí)行及其特征2025/1/1492.程序順序執(zhí)行時的特征(1)順序性:處理機的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行,只有當(dāng)上一個操作完成后,下一個操作才能執(zhí)行。(2)封閉性:程序運行在一個封閉的環(huán)境中,即程序運行時獨占系統(tǒng)的全部資源,這些資源的狀態(tài)只能因程序的執(zhí)行而改變,不受任何外界因素的影響。(3)可再現(xiàn)性:由于程序順序執(zhí)行的封閉性,只要程序順序執(zhí)行的初始條件和環(huán)境相同,則不論何時執(zhí)行,也不論程序執(zhí)行期間是否存在停頓,程序所得的結(jié)果也相同。結(jié)論:正由于程序順序執(zhí)行的特點,程序員可以檢測和重現(xiàn)程序的錯誤,可以調(diào)試和校正程序。2025/1/14102.1進程的基本概念2.1.1程序的順序執(zhí)行及其特征2.1.2前趨圖2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進程的特征與狀態(tài)2.1.5進程控制塊2025/1/14112.1.3程序的并發(fā)執(zhí)行及其特征1.程序的并發(fā)執(zhí)行圖2-3并發(fā)執(zhí)行時的前趨圖2025/1/1412在該例中存在下述前趨關(guān)系:Ii→Ci,Ii→Ii+1,Ci→Pi,Ci→Ci+1,Pi→Pi+1而Ii+1和Ci及Pi-1是重迭的,亦即在Pi-1和Ci以及Ii+1之間,可以并發(fā)執(zhí)行。對于具有下述四條語句的程序段:S1:a:=x+2S2:b:=y+4S3:c:=a+bS4:d:=c+6圖2-4四條語句的前趨關(guān)系2025/1/14132.程序并發(fā)執(zhí)行時的特征(1)間斷性 "走走停停",一個程序可能走到中途停下來,失去原有的時序關(guān)系;(2)失去封閉性

程序并發(fā)執(zhí)行時,系統(tǒng)中多道程序共享資源,資源的狀態(tài)不是唯一地取決于某一個程序,因此,必然失去了程序的封閉性,而程序的執(zhí)行結(jié)果因依賴于外部環(huán)境也失去了可再現(xiàn)性。(3)不可再現(xiàn)性 失去封閉性－>失去可再現(xiàn)性;外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化,失去原有的可重復(fù)特征。2025/1/1414例如,有兩個程序A和B,它們共享一個變量N(初始值為x)。A: N:=N+1B: Print(N); N:=0;

程序A和B并發(fā)執(zhí)行,以不可預(yù)知的速度運行,可出現(xiàn)以下三種情況:(1)N:=N+1在Print(N)和N:=0之前,此時得到的N值分別為x+1,x+1,0。(2)N:=N+1在Print(N)和N:=0之后,此時得到的N值分別為x,0,1。(3)N:=N+1在Print(N)和N:=0之間,此時得到的N值分別為x,x+1,0。2025/1/1415補充:并發(fā)執(zhí)行失去封閉性的原因是共享資源的影響,去掉這種影響就行了。1966年,由Bernstein(波恩斯坦)給出并發(fā)執(zhí)行的條件。若兩個程序P1和P2滿足下述條件,便能并發(fā)執(zhí)行且有可再現(xiàn)性: (R(P1)

W(P2))(R(P2)

W(P1))(W(P1)

W(P2))={}解釋:運算的讀集R(Pi)是指在運算執(zhí)行期間參考的所有變量的集合;運算的寫集W(Pi)是指在運算執(zhí)行期間要改變的所有變量的集合。存在的問題是這個條件不好檢查2025/1/1416例S1:a:=x+y R(S1)={x,y} W(S1)={a}S2:b:=z+1 R(S2)={z} W(S2)=S3:c:=a-b R(S3)={a,b} W(S3)={c}S4:d:=c+1 R(S4)={c} W(S4)=l8pub9c可見:語句S1和S2可以并發(fā)執(zhí)行嗎？語句S1和S3可以并發(fā)執(zhí)行嗎？語句S2和S3可以并發(fā)執(zhí)行嗎？語句S3和S4可以并發(fā)執(zhí)行嗎？語句S2和S4可以并發(fā)執(zhí)行嗎？(R(S1)

W(S2))(R(S2)

W(S1))(W(S1)

W(S2))={}可以不可以,因為:R(S3)

W(S1)={a}{}不可以,因為:R(S3)

W(S2)={}不可以,因為:R(S4)

W(S3)={c}{}可以2025/1/14172.1進程的基本概念2.1.1程序的順序執(zhí)行及其特征2.1.2前趨圖2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進程的特征與狀態(tài)2.1.5進程控制塊2025/1/1418進程實體由三部分構(gòu)成:(1)程序(段):進程要進行的操作。(2)數(shù)據(jù)段:包括操作的數(shù)據(jù)和程序自己的變量。(3)進程控制塊PCB(ProcessControlBlock):存放進程標(biāo)識符、進程運行的當(dāng)前狀態(tài)、程序和數(shù)據(jù)的地址、程序運行時的CPU環(huán)境等。2025/1/14192.1.4進程的特征與狀態(tài)1.進程的特征和定義動態(tài)性:進程是一個動態(tài)的概念,實質(zhì)上是程序的一次執(zhí)行過程。進程具有生命期:它因“創(chuàng)建”而產(chǎn)生,因“調(diào)度”而執(zhí)行,執(zhí)行時還走走停停,因“撤消”而滅亡。并發(fā)性:多個進程實體同存于內(nèi)存中,且能在一段時間內(nèi)同時運行,共享系統(tǒng)資源;引入進程實體的目的就是并發(fā)執(zhí)行;獨立性:進程是一個能獨立運行的基本單位,也是系統(tǒng)進行資源分配和調(diào)度的基本單位;異步性:各進程按各自獨立的、不可預(yù)知的速度向前推進;結(jié)構(gòu)特征:程序段、數(shù)據(jù)段和PCB;程序文件中通常也劃分了代碼段和數(shù)據(jù)段,進程的創(chuàng)建與撤消就是PCB的創(chuàng)建與撤消。2025/1/1420較典型的進程定義有:(1)進程是程序的一次執(zhí)行。(2)進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動。(3)進程是程序在一個數(shù)據(jù)集合上運行的過程,它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。在引入了進程實體的概念后,我們可以把傳統(tǒng)OS中的進程定義為:“進程是進程實體的運行過程,是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位”。2025/1/1421進程與程序的區(qū)別進程是動態(tài)的,程序是靜態(tài)的:程序是有序代碼的集合,它可以復(fù)制;進程是程序在數(shù)據(jù)集上的一次執(zhí)行。進程是暫時的,程序是永久的:進程是一個狀態(tài)變化的過程,有它的撤銷,程序可長久保存。進程具有結(jié)構(gòu)特征,由程序段、數(shù)據(jù)段和進程控制塊三者組成,而程序僅是指令的有序集合,是進程的組成部分之一。進程與程序的對應(yīng)關(guān)系:通過多次執(zhí)行,一個程序可對應(yīng)多個進程;2025/1/14222.進程的三種基本狀態(tài)(1)就緒(Ready)狀態(tài)進程已獲得除處理機外的所需資源,等待分配處理機資源;只要分配CPU就可執(zhí)行。一個系統(tǒng)中多個處于就緒狀態(tài)的進程排成就緒隊列。(2)執(zhí)行(Running)狀態(tài)處于就緒狀態(tài)的進程一旦獲得了處理機,就可以運行,進程狀態(tài)也就處于執(zhí)行狀態(tài)。處于此狀態(tài)的進程的數(shù)目小于等于CPU的數(shù)目。(3)阻塞(Blocked)狀態(tài)(“等待”或“睡眠”)由于進程等待某種事件(如I/O操作或進程同步),在事件發(fā)生之前無法繼續(xù)執(zhí)行。該事件發(fā)生前即使把處理機分配給該進程,也無法運行。如:請求I/O操作,申請緩沖空間等通常阻塞進程也排成若干隊列。2025/1/1423圖2-5進程的三種基本狀態(tài)及其轉(zhuǎn)換進程的三種基本狀態(tài)及其轉(zhuǎn)換1.時間片用光2.有優(yōu)先級高的進程到來2025/1/1424進程的其它兩種狀態(tài)新(創(chuàng)建)狀態(tài) 當(dāng)一個新進程剛剛建立,還未將其放入就緒隊列時的狀態(tài),稱為新狀態(tài)。終止?fàn)顟B(tài) 當(dāng)一個進程已經(jīng)正常結(jié)束或異常結(jié)束,操作系統(tǒng)已將其從系統(tǒng)隊列中移出,但尚未撤消,這時稱為終止?fàn)顟B(tài)。2025/1/1425圖2-5’進程的五種基本狀態(tài)及其轉(zhuǎn)換進程的五種基本狀態(tài)及其轉(zhuǎn)換2025/1/14261.引入掛起狀態(tài)的原因(1)終端用戶的請求 當(dāng)終端用戶在自己的程序運行期間發(fā)現(xiàn)有可疑問題時,希望暫時將自己的程序靜止下來。(2)父進程請求 父進程需要考查和修改子進程。(3)操作系統(tǒng)的需要 如檢查運行中的資源使用情況。(4)對換的需要 緩和內(nèi)存緊張,將阻塞進程換到外存上,有別于阻塞狀態(tài)。(5)負(fù)荷調(diào)節(jié)的需要 在實時系統(tǒng)中為了調(diào)整工作負(fù)荷可將不重要的進程掛起。3.掛起狀態(tài)2025/1/1427圖2-6具有掛起狀態(tài)的進程狀態(tài)圖2.進程狀態(tài)的轉(zhuǎn)換2025/1/14282.1進程的基本概念2.1.1程序的順序執(zhí)行及其特征2.1.2前趨圖2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進程的特征與狀態(tài)2.1.5進程控制塊2025/1/14292.1.5進程控制塊1.進程控制塊的作用進程控制塊的作用是使一個在多道程序環(huán)境下不能獨立運行的程序(含數(shù)據(jù)),成為一個能獨立運行的基本單位,一個能與其它進程并發(fā)執(zhí)行的進程?；蛘哒f,OS是根據(jù)PCB來對并發(fā)執(zhí)行的進程進行控制和管理的。記錄了操作系統(tǒng)所需的,用于描述進程情況及控制進程運行所需的全部信息。

PCB是進程存在的唯一標(biāo)志。2025/1/14302.進程控制塊中的信息1)進程標(biāo)識符

進程標(biāo)識符用于惟一地標(biāo)識一個進程。一個進程通常有兩種標(biāo)識符:(1)內(nèi)部標(biāo)識符。在所有的操作系統(tǒng)中,都為每一個進程賦予一個惟一的數(shù)字標(biāo)識符,它通常是一個進程的序號。設(shè)置內(nèi)部標(biāo)識符主要是為了方便系統(tǒng)使用。(2)外部標(biāo)識符。它由創(chuàng)建者提供,通常是由字母、數(shù)字組成,往往是由用戶(進程)在訪問該進程時使用。為了描述進程的家族關(guān)系,還應(yīng)設(shè)置父進程標(biāo)識及子進程標(biāo)識。此外,還可設(shè)置用戶標(biāo)識,以指示擁有該進程的用戶。2025/1/14312)處理機狀態(tài) 處理機狀態(tài)信息主要是由處理機的各種寄存器中的內(nèi)容組成的。①通用寄存器,又稱為用戶可視寄存器,它們是用戶程序可以訪問的,用于暫存信息,在大多數(shù)處理機中,有8~32個通用寄存器,在RISC結(jié)構(gòu)的計算機中可超過100個;②指令計數(shù)器PC,其中存放了要訪問的下一條指令的地址;③程序狀態(tài)字PSW,其中含有狀態(tài)信息,如條件碼、執(zhí)行方式、中斷屏蔽標(biāo)志等;④用戶棧指針,指每個用戶進程都有一個或若干個與之相關(guān)的系統(tǒng)棧,用于存放過程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向該棧的棧頂。2025/1/14323)進程調(diào)度信息在PCB中還存放一些與進程調(diào)度和進程對換有關(guān)的信息,包括:①進程狀態(tài),指明進程的當(dāng)前狀態(tài),作為進程調(diào)度和對換時的依據(jù);②進程優(yōu)先級,用于描述進程使用處理機的優(yōu)先級別的一個整數(shù),優(yōu)先級高的進程應(yīng)優(yōu)先獲得處理機;③進程調(diào)度所需的其它信息,它們與所采用的進程調(diào)度算法有關(guān),比如,進程已等待CPU的時間總和、進程已執(zhí)行的時間總和等;④事件,是指進程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件,即阻塞原因。2025/1/14334)進程控制信息進程控制信息包括:①程序和數(shù)據(jù)的地址,是指進程的程序和數(shù)據(jù)所在的內(nèi)存或外存地(首)址,以便再調(diào)度到該進程執(zhí)行時,能從PCB中找到其程序和數(shù)據(jù);②進程同步和通信機制,指實現(xiàn)進程同步和進程通信時必需的機制,如消息隊列指針、信號量等,它們可能全部或部分地放在PCB中;③資源清單,是一張列出了除CPU以外的、進程所需的全部資源及已經(jīng)分配到該進程的資源的清單;④鏈接指針,它給出了本進程(PCB)所在隊列中的下一個進程的PCB的首地址。2025/1/1434圖2-7PCB鏈接隊列示意圖3.進程控制塊的組織方式(1)鏈接方式把具有同一狀態(tài)的PCB用其中的鏈接字鏈接成一個隊列,可以形成就緒隊列、若干個阻塞隊列和空閑隊列(2)......2025/1/1435圖2-8按索引方式組織PCB3.進程控制塊的組織方式(1)......(2)索引方式系統(tǒng)根據(jù)所有進程的狀態(tài)建立幾張索引表,如就緒索引表、阻塞索引表等,并把各索引表在內(nèi)存的首地址記錄在專用單元中。索引表中記錄的是PCB在PCB表中的地地址。2025/1/1436內(nèi)容概述2.1進程的基本概念

2.2進程控制

2.3進程同步2.4經(jīng)典進程的同步問題2.5管程機制2.6進程通信2.7線程2025/1/1437補充內(nèi)容處理機的執(zhí)行狀態(tài)分系統(tǒng)態(tài)和用戶態(tài)兩種:(1)系統(tǒng)態(tài)(管態(tài)、核心態(tài)):有較高特權(quán),能執(zhí)行一切指令,訪問所有寄存器和存儲區(qū)。(2)用戶態(tài)(目態(tài)):有較低特權(quán),能執(zhí)行規(guī)定指令,訪問指定寄存器和存儲區(qū)。 用戶程序運行在用戶態(tài),不能執(zhí)行OS指令及區(qū)域。 OS內(nèi)核運行在系統(tǒng)態(tài),進程控制是由OS內(nèi)核實現(xiàn)的。2025/1/14382.2進程控制進程控制是進程管理中最基本的功能,主要包括以下幾個方面創(chuàng)建新進程終止已結(jié)束進程終止由于某事件而無法運行下去的進程負(fù)責(zé)進程的狀態(tài)轉(zhuǎn)換原語(primitive)由若干條指令構(gòu)成的“原子操作(atomicoperation)”過程,在執(zhí)行期間不可中斷,以保證其正確性。作為一個整體而不可分割。許多系統(tǒng)調(diào)用就是原語。系統(tǒng)調(diào)用并不都是原語。進程A調(diào)用read(),因無數(shù)據(jù)而阻塞,在read()里未返回。然后進程B調(diào)用read(),此時read()被重入。系統(tǒng)調(diào)用不一定一次執(zhí)行完并返回該進程,有可能在特定的點暫停,而轉(zhuǎn)入到其他進程。1.創(chuàng)建原語2.撤消原語3.阻塞原語4.喚醒原語5.掛起原語6.激活原語2025/1/14392.2進程控制2.2.1進程的創(chuàng)建2.2.2進程的終止2.2.3進程的阻塞與喚醒2.2.4進程的掛起與激活2025/1/14402.2.1進程的創(chuàng)建圖2-9進程樹1.進程圖(ProcessGraph)進程圖是用于描述一個進程的家族關(guān)系的有向樹,樹中的結(jié)點表示進程在進程A創(chuàng)建了進程B之后稱A是B的父進程(ParentProcess),B是A的子進程(ProgenyProcess)。創(chuàng)建父進程的進程稱為祖先進程,把樹的根結(jié)點稱為進程家族的祖先進程(Ancestor)子進程可以繼承(Inherit)父進程的資源。撤消父進程時必須同時撤消子進程2025/1/14412.引起創(chuàng)建進程的事件 在多道程序環(huán)境中,只有進程才能在系統(tǒng)中運行。因此,為使程序運行,必須創(chuàng)建進程,創(chuàng)建進程事件包括:(1)用戶登錄 在分時系統(tǒng)中,用戶在終端登錄后,如是合法用戶,系統(tǒng)將為用戶創(chuàng)建一個進程,并插入就緒隊列。(2)作業(yè)調(diào)度 在批處理系統(tǒng)中,當(dāng)作業(yè)調(diào)度程序調(diào)度到某作業(yè)時,將該作業(yè)裝入內(nèi)存,為它分配資源并創(chuàng)建進程。(3)提供服務(wù) 當(dāng)運行中的用戶進程提出某種請求后,系統(tǒng)將專門創(chuàng)建一個進程來提供服務(wù),如打印。(4)應(yīng)用請求由應(yīng)用進程為自己創(chuàng)建進程,以便能并發(fā)執(zhí)行,如輸入、計算、輸出程序。2025/1/14423.進程的創(chuàng)建步驟(CreationofProgress)(1)申請空白PCB為新進程申請惟一的數(shù)字標(biāo)識符,并從PCB集合中索取一個空白PCB(2)為新進程分配資源為新進程的程序和數(shù)據(jù)分配內(nèi)存。對于批處理型作業(yè),可以在用戶提出創(chuàng)建進程時要求提供所需內(nèi)存大小。對于交互型作業(yè)可以由系統(tǒng)來分配一定的空間(3)初始化進程控制塊初始化標(biāo)識信息將系統(tǒng)標(biāo)識信息寫入新PCB初始化處理機狀態(tài)信息使程序計數(shù)器指向程序的入口地址,棧指針指向棧頂初始化處理機控制信息將進程的狀態(tài)設(shè)為就緒狀態(tài)或靜止就緒狀態(tài)(4)將新進程插入就緒隊列如果進程就緒隊列能夠接納新進程,便將新進程插入就緒隊列2025/1/14432.2進程控制2.2.1進程的創(chuàng)建2.2.2進程的終止2.2.3進程的阻塞與喚醒2.2.4進程的掛起與激活2025/1/14442.2.2進程的終止1.引起進程終止(TerminationofProcess)的事件1)正常結(jié)束在任何計算機系統(tǒng)中,都應(yīng)有一個用于表示進程已經(jīng)運行完成的指示。例如,在批處理系統(tǒng)中,通常在程序的最后安排一條Halt指令或終止的系統(tǒng)調(diào)用。當(dāng)程序運行到Halt指令時,將產(chǎn)生一個中斷,去通知OS本進程已經(jīng)完成。在分時系統(tǒng)中,用戶可利用Logsoff去表示進程運行完畢,此時同樣可產(chǎn)生一個中斷,去通知OS進程已運行完畢。2025/1/14452)異常結(jié)束在進程運行期間,由于出現(xiàn)某些錯誤和故障而迫使進程終止。這類異常事件很多,常見的有:①越界錯誤。這是指程序所訪問的存儲區(qū),已越出該進程的區(qū)域;②保護錯。進程試圖去訪問一個不允許訪問的資源或文件,或者以不適當(dāng)?shù)姆绞竭M行訪問,例如,進程試圖去寫一個只讀文件;③非法指令。程序試圖去執(zhí)行一條不存在的指令。出現(xiàn)該錯誤的原因,可能是程序錯誤地轉(zhuǎn)移到數(shù)據(jù)區(qū),把數(shù)據(jù)當(dāng)成了指令;④特權(quán)指令錯。用戶進程試圖去執(zhí)行一條只允許OS執(zhí)行的指令;⑤運行超時。進程的執(zhí)行時間超過了指定的最大值;⑥等待超時。進程等待某事件的時間,超過了規(guī)定的最大值;⑦算術(shù)運算錯。進程試圖去執(zhí)行一個被禁止的運算,例如,被0除;⑧I/O故障。這是指在I/O過程中發(fā)生了錯誤等。2025/1/14463)外界干預(yù)外界干預(yù)并非指在本進程運行中出現(xiàn)了異常事件,而是指進程應(yīng)外界的請求而終止運行。這些干預(yù)有:①操作員或操作系統(tǒng)干預(yù)。由于某種原因,例如,發(fā)生了死鎖,由操作員或操作系統(tǒng)終止該進程;②父進程請求。由于父進程具有終止自己的任何子孫進程的權(quán)利,因而當(dāng)父進程提出請求時,系統(tǒng)將終止該進程;③父進程終止。當(dāng)父進程終止時,OS也將他的所有子孫進程終止。2025/1/14472.進程的終止過程(1)根據(jù)被終止進程的標(biāo)識符,從PCB集合中檢索出該進程的PCB,從中讀出該進程的狀態(tài)。(2)若被終止進程正處于執(zhí)行狀態(tài),應(yīng)立即終止該進程的執(zhí)行,并置調(diào)度標(biāo)志為真,用于指示該進程被終止后應(yīng)重新進行調(diào)度。(3)若該進程還有子孫進程,還應(yīng)將其所有子孫進程予以終止,以防他們成為不可控的進程。(4)將被終止進程所擁有的全部資源,或者歸還給其父進程,或者歸還給系統(tǒng)。(5)將被終止進程(它的PCB)從所在隊列(或鏈表)中移出,等待其他程序來搜集信息。2025/1/14482.2進程控制2.2.1進程的創(chuàng)建2.2.2進程的終止2.2.3進程的阻塞與喚醒2.2.4進程的掛起與激活2025/1/14492.2.3進程的阻塞與喚醒1.引起進程阻塞和喚醒的事件 (1)請求系統(tǒng)服務(wù) 如請求打印機時,若已被其他進程占用,此時只能阻塞,等其他進程釋放后再將請求進程喚醒。(2)啟動某種操作 當(dāng)進程啟動某種操作后,如果該進程必須在該操作完成后才能繼續(xù)執(zhí)行,則必須先使進程阻塞,以等待該操作完成。如啟動I/O設(shè)備。(3)新數(shù)據(jù)尚未到達 對于相互合作的進程,如果一個進程需要另一合作進程提供的數(shù)據(jù),則在數(shù)據(jù)到達之前只能阻塞。(4)無新工作可做 系統(tǒng)中的一些特殊功能進程,在完成了任務(wù)之后,等待新任務(wù)到來。如系統(tǒng)中的發(fā)送進程。2025/1/14502.進程阻塞過程正在執(zhí)行的進程,當(dāng)發(fā)現(xiàn)上述某事件時,由于無法繼續(xù)執(zhí)行,于是進程便通過調(diào)用阻塞原語block()把自己阻塞?？梢?進程的阻塞是進程自身的一種主動行為進入block過程后,由于此時該進程還處于執(zhí)行狀態(tài),所以應(yīng)先立即停止執(zhí)行,把進程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為阻塞,并將PCB插入阻塞隊列如果系統(tǒng)中設(shè)置了因不同事件而阻塞的多個阻塞隊列,則應(yīng)將本進程插入到具有相同事件的阻塞(等待)隊列調(diào)度程序進行重新調(diào)度,將處理機分配給另一就緒進程,并進行切換,亦即,保留被阻塞進程的處理機狀態(tài)(在PCB中),再按新進程的PCB中的處理機狀態(tài)設(shè)置CPU的環(huán)境2025/1/14513.進程喚醒過程當(dāng)被阻塞進程所期待的事件出現(xiàn)時,如I/O完成或其所期待的數(shù)據(jù)已經(jīng)到達,則由有關(guān)進程(比如,用完并釋放了該I/O設(shè)備的進程)調(diào)用喚醒原語wakeup(),將等待該事件的進程喚醒喚醒原語執(zhí)行的過程是把被阻塞的進程從等待該事件的阻塞隊列中移出將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒將該PCB插入到就緒隊列中2025/1/14522.2進程控制2.2.1進程的創(chuàng)建2.2.2進程的終止2.2.3進程的阻塞與喚醒2.2.4進程的掛起與激活2025/1/14532.2.4進程的掛起與激活1.進程的掛起當(dāng)出現(xiàn)了引起進程掛起的事件時,比如,用戶進程請求將自己掛起,或父進程請求將自己的某個子進程掛起,系統(tǒng)將利用掛起原語suspend()將指定進程或處于阻塞狀態(tài)的進程掛起。suspend()原語的執(zhí)行過程首先檢查被掛起進程的狀態(tài),若處于活動就緒狀態(tài),便將其改為靜止就緒;對于活動阻塞狀態(tài)的進程,則將之改為靜止阻塞。為了方便用戶或父進程考查該進程的運行情況而把該進程的PCB復(fù)制到某指定的內(nèi)存區(qū)域。若被掛起的進程正在執(zhí)行,則轉(zhuǎn)向調(diào)度程序重新調(diào)度。2025/1/14542.進程的激活過程當(dāng)發(fā)生激活進程的事件時,例如,父進程或用戶進程請求激活指定進程,若該進程駐留在外存而內(nèi)存中已有足夠的空間時,則可將在外存上處于靜止就緒狀態(tài)的進程換入內(nèi)存。這時,系統(tǒng)將利用激活原語active()將指定進程激活。active()原語執(zhí)行過程激活原語先將進程從外存調(diào)入內(nèi)存,檢查該進程的現(xiàn)行狀態(tài),若是靜止就緒,便將之改為活動就緒;若為靜止阻塞便將之改為活動阻塞。假如采用的是搶占調(diào)度策略,則每當(dāng)有新進程進入就緒隊列時,應(yīng)檢查是否要進行重新調(diào)度,即由調(diào)度程序?qū)⒈患せ钸M程與當(dāng)前進程進行優(yōu)先級的比較,如果被激活進程的優(yōu)先級更低,就不必重新調(diào)度;否則,立即剝奪當(dāng)前進程的運行,把處理機分配給剛被激活的進程。2025/1/1455內(nèi)容概述2.1進程的基本概念

2.2進程控制2.3進程同步

2.4經(jīng)典進程的同步問題2.5管程機制2.6進程通信2.7線程2025/1/14562.3進程同步2.3.1進程同步的基本概念2.3.2信號量機制2.3.3信號量的應(yīng)用2025/1/1457一個循環(huán)進程順序執(zhí)行的謄抄輸入:fwhile(f不為空)dobegininput;output;end由這個程序完成謄抄工作是不會出錯的。2025/1/1458兩個進程并發(fā)執(zhí)行完成謄抄設(shè)有一臺標(biāo)準(zhǔn)輸入設(shè)備(鍵盤),和一臺標(biāo)準(zhǔn)輸出設(shè)備(顯示器或打印機),輸入進程負(fù)責(zé)從標(biāo)準(zhǔn)設(shè)備中讀取一個字符,送緩沖區(qū)中。輸出進程從緩沖區(qū)中取數(shù)據(jù),送標(biāo)準(zhǔn)設(shè)備輸出。2025/1/1459兩個進程并發(fā)執(zhí)行完成謄抄parbeginprocess輸入beginwhile(不為結(jié)束符)dobegininput;{從標(biāo)準(zhǔn)輸入設(shè)備讀入一個數(shù)據(jù)}send;{將讀入的數(shù)據(jù)送到buffer}endendprocess輸出beginwhile(buffer不為空)dobeginreceive;{從buffer中取數(shù)據(jù)}output;{送打印機輸出}endendparend2025/1/1460兩個進程并發(fā)執(zhí)行完成謄抄這兩個進程并發(fā)執(zhí)行時可能出現(xiàn)如下情況:1.輸出進程運行的速度比輸入進程快時,有些輸出會重復(fù);如輸入送入了一個字符“A”,輸出取出打印“A”,當(dāng)輸入進程還未送入新的數(shù)據(jù),輸出進程已執(zhí)行,又取出“A”打印,這樣“A”的輸出就重復(fù)了,出錯。2.輸入進程執(zhí)行的速度比輸出進程快時,有些數(shù)據(jù)會丟失;如輸入進程送入一個字符“B”,緊接著(當(dāng)輸出進程還未取走字符“B”)又送入字符“N”,這時輸出進程取走的是“N”,“B”就丟失了。2025/1/14612.3.1進程同步的基本概念1.兩種形式的制約關(guān)系在多道程序環(huán)境下,當(dāng)程序并發(fā)執(zhí)行時,由于資源共享和進程合作,使同處于系統(tǒng)中的諸進程之間存在兩種形式的制約關(guān)系。(1)間接相互制約關(guān)系同處于一個系統(tǒng)中的進程必然共享某種資源,如CPU、I/O設(shè)備等,間接相互制約即源于資源共享。如A、B共享打印機,若A申請打印時,打印機已分配給B,則A只能阻塞,等B釋放后再改為就緒,又稱為“互斥”。(2)直接相互制約關(guān)系

這種制約源于進程之間的合作關(guān)系。如進程A向B提供數(shù)據(jù),當(dāng)輸入緩沖空時,B不能得到數(shù)據(jù)而阻塞;反之當(dāng)緩沖滿時,A無法寫入而阻塞,又稱為“同步”。2025/1/1462引例:宿舍電話的使用打印機的使用2.臨界資源(CriticalResouce)定義:在一段時間內(nèi)只允許一個進程訪問的資源。例如:打印機,磁帶機,卡片輸入機,變量,表格,數(shù)據(jù),指針、數(shù)組等。2025/1/1463例設(shè)有兩個進程P1、P2共享變量count

P1()beginR1:=count;{R1為寄存器}R1:=R1+1;count:=R1;endP2()beginR2:=count;{R2為寄存器}R2:=R2-1;count:=R2;end設(shè)初始值:count為x情況1:P1先執(zhí)行,P2后執(zhí)行。結(jié)果正常。情況2:交叉。P1:R1:=count;{R1=x}P2:R2:=count;{R2=x}P1:R1:=R1+1;{R1=x+1} count:=R1;{count=x+1}P2:R2:=R2-1;{R2=x-1} count:=R2;{count=x-1}結(jié)果:count等于x-1count:=count+1;count:=count-1;2025/1/1464例設(shè)一民航航班售票系統(tǒng)有n個售票處。每個售票處通過終端訪問系統(tǒng)中的公用數(shù)據(jù)區(qū),假定公共數(shù)據(jù)區(qū)中一些單元xk(k=1,2,…)分別存放×月×日×次航班的現(xiàn)存票數(shù)。設(shè)P1,P2,…,Pn表示各售票處的處理進程,R1,R2,…,Rn表示各進程執(zhí)行時所用的工作單元。進程實現(xiàn)的程序如下:2025/1/1465ProcessPi(d)(i=1,2,…,n)begin按旅客訂票要求找到xk;Ri:=xk;ifRi≥dthenbeginRi:=Ri-d;xk:=Ri;輸出d張票;endelsebegin輸出“票已售完或沒有d張票”;endend;2025/1/14663.臨界區(qū)(criticalsection)由前例可見,不論是硬件臨界資源還是軟件臨界資源,多個進程必須互斥地對它進行訪問在每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)(criticalsection)每個進程進入臨界區(qū)之前應(yīng)先對欲訪問的臨界資源進行檢查,看是否正在被訪問。如果此刻該臨界資源未被訪問,該進程可進入臨界區(qū),并設(shè)置它正在被訪問的標(biāo)志,在臨界區(qū)之前執(zhí)行的這段代碼稱為進入?yún)^(qū)(entrysection)在臨界區(qū)后面也要加上一段代碼,用于將臨界區(qū)被訪問的資源恢復(fù)為未被訪問的標(biāo)志,稱為退出區(qū)(exitsection)2025/1/1467可把一個訪問臨界資源的循環(huán)進程描述如下:

repeat

criticalsection; {臨界區(qū)}

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

repeat

criticalsection; {臨界區(qū)}

remaindersection; {剩余區(qū)}untilfalse;entrysectionexitsectionP(S);V(S);{進入?yún)^(qū)}{退出區(qū)}2025/1/1473ProcessPi(d)(i=1,2,…,n)varS:Semaphore:=1;begin按旅客訂票要求找到xk;

P(S);

Ri:=xk;ifRi≥dthenbeginRi:=Ri-d;xk:=Ri;

V(S);輸出d張票;endelsebegin

V(S);

輸出“票已售完或沒有d張票”;endend;民航航班售票系統(tǒng):用信號量實現(xiàn)進程間互斥的程序如下:2025/1/14742.記錄型信號量在整型信號量機制中的wait操作,只要是信號量S≤0,就會不斷地測試。因此,該機制并未遵循“讓權(quán)等待”的準(zhǔn)則,而是使進程處于“忙等”的狀態(tài)。記錄型信號量機制,則是一種不存在“忙等”現(xiàn)象的進程同步機制。但在采取了“讓權(quán)等待”的策略后,又會出現(xiàn)多個進程等待訪問同一臨界資源的情況。為此,在信號量機制中,除了需要一個用于代表資源數(shù)目的整型變量value外,還應(yīng)增加一個進程鏈表L,用于鏈接上述的所有等待進程。記錄型信號量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的。2025/1/1475typesemaphore=recordvalue:integer;L:listofprocess;end相應(yīng)地,wait(S)和signal(S)操作可描述為:

procedurewait(S)varS:semaphore;beginS.value:=S.value-1;ifS.value＜0thenblock(S.L);endproceduresignal(S)varS:semaphore;beginS.value:=S.value+1;ifS.value≤0thenwakeup(S.L);end2025/1/1476在記錄型信號量機制中,S.value的初值表示系統(tǒng)中某類資源的數(shù)目,因而又稱為資源信號量對它的每次P操作,意味著進程請求一個單位的該類資源,因此描述為S.value:=S.value-1;當(dāng)S.value＜0時,表示該類資源已分配完畢,因此進程應(yīng)調(diào)用block原語,進行自我阻塞,放棄處理機,并插入到信號量鏈表S.L中?？梢?該機制遵循了“讓權(quán)等待”準(zhǔn)則。此時S.value的絕對值表示在該信號量鏈表中已阻塞進程的數(shù)目對信號量的每次V操作,表示執(zhí)行進程釋放一個單位資源,故S.value:=S.value+1操作表示資源數(shù)目加1。若加1后仍是S.value≤0,則表示在該信號量鏈表中,仍有等待該資源的進程被阻塞,故還應(yīng)調(diào)用wakeup原語,將S.L鏈表中的第一個等待進程喚醒。如果S.value的初值為1,表示只允許一個進程訪問臨界資源,此時的信號量轉(zhuǎn)化為互斥信號量。2025/1/14773.AND型信號量

在有些任務(wù)中,一個進程先要獲得多個共享資源后才能執(zhí)行,若進程A和B都要申請D和E兩種資源,設(shè)信號量Dmutex和Emutex的初值均為1在兩個進程中都要包含兩個對Dmutex和Emutex的操作,即processA: processB:P(Dmutex); P(Emutex);P(Emutex); P(Dmutex);若進程A和B按下述次序交替執(zhí)行P操作:processA:P(Dmutex);于是Dmutex=0processB:P(Emutex);于是Emutex=0processA:P(Emutex);于是Emutex=-1A阻塞

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

死鎖！2025/1/1478AND同步機制的基本思想是:將進程在整個運行過程中需要的所有資源,一次性全部地分配給進程,待進程使用完后再一起釋放。只要尚有一個資源未能分配給進程,其它所有可能為之分配的資源,也不分配給他。亦即,對若干個臨界資源的分配,采取原子操作方式:要么全部分配到進程,要么一個也不分配。由死鎖理論可知,這樣就可避免上述死鎖情況的發(fā)生。為此,在P操作中,增加了一個“AND”條件,故稱為AND同步,或稱為同時P操作,即SP(Simultaneouswait)定義如下:2025/1/1479SP:Swait(S1,S2,…,Sn)ifS1≥1and…andSn≥1then{每個資源都可用}fori:=1tondoSi:=Si-1;{分配所有資源}endforelse{否則,將進程放到等待資源Si的隊列中}

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

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

“喚醒”(所有“等待Si”的阻塞進程,置為“就緒”狀態(tài),移到就緒隊列中)endfor;2025/1/14804.信號量集:一次申請多個資源在記錄型信號量機制中,P(S)和V(S)操作僅能對信號量施以加1或減1操作,意味著每次只能獲得或釋放一個單位的臨界資源,效率較低。在有些情況下,當(dāng)資源數(shù)量低于某下限值時便不予分配。因而,在每次分配之前,都必須測試該資源的數(shù)量,看其是否大于下限值。在對AND型信號量機制擴充的基礎(chǔ)上,形成一般化的“信號量集”機制。2025/1/1481SP:Swait(S1,t1,d1,…,Sn,tn,dn)ifS1≥t1and…andSn≥tnthenfori:=1tondoSi:=Si-di;{一次分配d個資源}endforelse

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

endif

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

endfor;2025/1/1482一般“信號量集”的幾種特殊情況:(1)SP(S,d,d)。此時在信號量集中只有一個信號量S,但允許它每次申請d個資源,當(dāng)現(xiàn)有資源數(shù)少于d時,不予分配。(2)SP(S,1,1)。此時的信號量集已蛻化為一般的記錄型信號量(S＞1時)或互斥信號量(S=1時)。(3)SP(S,1,0)。這是一種很特殊且很有用的信號量操作。當(dāng)S≥1時,允許多個進程進入某特定區(qū);當(dāng)S變?yōu)?后,將阻止任何進程進入特定區(qū)。換言之,它相當(dāng)于一個可控開關(guān)。2025/1/14832.3進程同步2.3.1進程同步的基本概念2.3.2信號量機制2.3.3信號量的應(yīng)用2025/1/14842.3.3信號量的應(yīng)用1.利用信號量實現(xiàn)進程互斥mutex作為互斥信號量Varmutex:semaphore:=1;beginparbeginprocess1:begin repeat

P(mutex);

criticalsection

V(mutex);

remainderseetion untilfalse; endprocess2:begin repeat

P(mutex);

criticalsection

V(mutex);

remaindersection untilfalse; endparendend2025/1/1485利用信號量實現(xiàn)進程互斥利用整型信呈量機制實現(xiàn)進程互斥時應(yīng)注意,P(mutex)和V(mutex)必須成對出現(xiàn)。缺少P(mutex)會導(dǎo)致系統(tǒng)混亂,不能保證對臨界資源的互斥訪問。缺少V(mutex)將會使臨界資源永遠(yuǎn)不被釋放,從而使因等待該資源而阻塞的進程不再被喚醒。2025/1/14862.利用信號量實現(xiàn)前趨關(guān)系設(shè)有兩個并發(fā)進程P1和P2。P1中有語句S1,P2中有語句S2,希望在執(zhí)行完S1后執(zhí)行S2。為實現(xiàn)這種前趨關(guān)系,可讓進程P1和P2共享一個公用信號量a,并賦初值為0,將V(a)操作放在語句S1后面;而在S2語句前插入P(a)操作。進程P1:S1;V(a);進程P2:P(a);S2;由于a被初始化為0,若P2先執(zhí)行,必定阻塞,只有在進程P1執(zhí)行完使S增為1后,P2才能執(zhí)行S2操作。a2025/1/1487圖2-10前趨圖舉例2025/1/1488Vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;beginparbegin 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;parendendabcdegf2025/1/1489內(nèi)容概述2.1進程的基本概念

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

2.5管程機制2.6進程通信2.7線程2025/1/14902.4經(jīng)典進程的同步問題2.4.1生產(chǎn)者—消費者問題2.4.2哲學(xué)家進餐問題2.4.3讀者—寫者問題2025/1/14912.4.1生產(chǎn)者—消費者問題一個生產(chǎn)者—一個消費者問題

前面我們已經(jīng)對生產(chǎn)者—消費者問題(Theproducer-consumerproblem)做了一些描述,但未考慮進程的互斥與同步問題,因而造成了數(shù)據(jù)Counter的不定性。由于生產(chǎn)者—消費者問題是相互合作的進程關(guān)系的一種抽象,例如,在輸入時,輸入進程是生產(chǎn)者,計算進程是消費者;而在輸出時,則計算進程是生產(chǎn)者,而打印進程是消費者,因此,該問題有很大的代表性及實用價值。2025/1/14921.利用記錄型信號量解決生產(chǎn)者—消費者問題假定在生產(chǎn)者和消費者之間的公用緩沖池中,具有1個緩沖區(qū);利用信號量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定就一個生產(chǎn)者和一個消費者,只要緩沖池未滿,生產(chǎn)者便可將消息送入緩沖池;只要緩沖池未空,消費者便可從緩沖池中取走一個消息。對生產(chǎn)者—消費者問題可描述如下:設(shè)置兩個信號量:full:表示放有消息的緩沖區(qū)數(shù),其初值為0。empty:表示可供使用的緩沖區(qū)數(shù),其初值為1。2025/1/1493Varempty,full:semaphore:=1,0;buffer:item;beginparbeginproducer:{生產(chǎn)者進程}beginrepeat…生產(chǎn)一條消息=>nextp;…P(empty);{empty減1}buffer:=nextp;V(full);{full增1}untilfalse;endconsumer:{消費者進程}beginrepeatP(full);nextc:=buffer;V(empty);

消費nextc中的一條消息;untilfalse;endparendend2025/1/1494多個生產(chǎn)者—多個消費者問題前面我們已經(jīng)對生產(chǎn)者—消費者問題(Theproducer-consumerproblem)做了一些描述,但未考慮進程的互斥與同步問題,因而造成了數(shù)據(jù)Counter的不定性。由于生產(chǎn)者—消費者問題是相互合作的進程關(guān)系的一種抽象,例如,在輸入時,輸入進程是生產(chǎn)者,計算進程是消費者;而在輸出時,則計算進程是生產(chǎn)者,而打印進程是消費者,因此,該問題有很大的代表性及實用價值。2025/1/14951.利用記錄型信號量解決生產(chǎn)者—消費者問題假定在生產(chǎn)者和消費者之間的公用緩沖池中,具有n個緩沖區(qū),這時可利用互斥信號量mutex實現(xiàn)諸進程對緩沖池的互斥使用;利用信號量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費者相互等效,只要緩沖池未滿,生產(chǎn)者便可將消息送入緩沖池;只要緩沖池未空,消費者便可從緩沖池中取走一個消息。對生產(chǎn)者—消費者問題可描述如下:設(shè)置三個信號量:full:表示放有消息的緩沖區(qū)數(shù),其初值為0。empty:表示可供使用的緩沖區(qū)數(shù),其初值為n。mutex:互斥信號量,初值為1,表示各進程互斥進入臨界區(qū),保證任何時候只有一個進程使用緩沖區(qū)。2025/1/1496Varmutex,empty,full:semaphore:=1,n,0;buffer:array［0,…,n-1］ofitem;

in,out:integer:=0,0;beginparbeginproducer:{生產(chǎn)者進程}beginrepeat…生產(chǎn)一條消息=>nextp;…P(empty);{empty減1}

P(mutex);

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

V(mutex);V(full);{full增1}untilfalse;endconsumer:{消費者進程}beginrepeatP(full);

P(mutex);

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

V(mutex);

V(empty);消費nextc中的一條消息;

untilfalse;endparendend2025/1/1497在生產(chǎn)者—消費者問題中要注意以下幾點在每個程序中用于實現(xiàn)互斥的P(mutex)和V(mutex)必須成對地出現(xiàn);對資源信號量empty和full的P和V操作,同樣需要成對地出現(xiàn),但它們分別處于不同的程序中。例如,P(empty)在計算進程中,而V(empty)則在打印進程中,計算進程若因執(zhí)行P(empty)而阻塞,則以后將由打印進程將它喚醒;在每個程序中的多個P操作順序不能顛倒。應(yīng)先執(zhí)行對資源信號量的P操作,然后再執(zhí)行對互斥信號量的P操作,否則可能引起進程死鎖。2025/1/1498初始值:mutex:=1; 生產(chǎn)者:P(empty);full:=0; P(mutex);empty:=n; 消費者:P(mutex); P(full);生產(chǎn)者:P(empty); 成功empty:=n-1而P(mutex); 不成功消費者:P(mutex); 成功mutex:=0;P(full); 不成功full:=-1;死鎖！2025/1/14992.利用AND信號量解決生產(chǎn)者—消費者問題Varmutex,empty,full:semaphore:=1,n,0;buffer:array［0,…,n-1］ofitem;inout:integer:=0,0;beginparbeginproducer:beginrepeat…生產(chǎn)一條消息=>nextp;…

SP(empty,mutex);buffer(in):=nextp;in:=(in+1)modn;SV(mutex,full);untilfalse;endconsumer:beginrepeatSP(full,mutex);nextc:=buffer(out);out:=(out+1)modn;SV(mutex,empty);

消費nextc中的一條消息;

untilfalse;endparendend2025/1/141002.4經(jīng)典進程的同步問題2.4.1生產(chǎn)者—消費者問題2.4.2哲學(xué)家進餐問題2.4.3讀者—寫者問題2025/1/141012.4.2哲學(xué)家進餐問題哲學(xué)家進餐問題(TheDinningPhilosophersProblem)是由Dijkstra提出并解決的典型進程同步問題問題描述5個哲學(xué)家坐在桌子邊,桌上有5個碗和5支筷子哲學(xué)家的生活方式交替地進行思考和進餐哲學(xué)家饑餓時便拿起兩邊的筷子進餐,但只有當(dāng)拿到兩支后才能進餐用餐畢,放下筷子2025/1/141021.利用記錄型信號量解決哲學(xué)家進餐問題經(jīng)分析可知,放在桌子上的筷子是臨界資源,在一段時間內(nèi)只允許一位哲學(xué)家使用。為了實現(xiàn)對筷子的互斥使用,可以用一個信號量表示一只筷子,由這五個信號量構(gòu)成信號量數(shù)組。其描述如下:2025/1/14103Varchopstick:array［0,…,4］ofsemaphore:=(1,1,1,1,1);beginrepeat

P(chopstick［i］);

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

… eat;{進餐}…

V(chopstick［i］);

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

… think;{思考}untilfalse;end問題:

每個哲學(xué)家都拿起左邊的筷子等待右邊的筷子,結(jié)果誰也得不到兩把筷子。形成了死鎖。01234104322025/1/14104可采取以下幾種解決方法:(1)至多只允許有四位哲學(xué)家同時去拿左邊的筷子,最終能保證至少有一位哲學(xué)家能夠進餐,并在用畢時能釋放出他用過的兩只筷子,從而使更多的哲學(xué)家能夠進餐。2025/1/14105Varchopstick:array［0,…,4］ofsemaphore:=(1,1,1,1,1);count:semaphore:=4;beginrepeat

P(count); P(chopstick［i］); P(chopstick［(i+1)mod5］); … eat;{進餐}… V(chopstick［i］); V(chopstick［(i+1)mod5］);

V(count); … think;{思考}untilfalse;end2025/1/14106可采取以下幾種解決方法:(1)………(2)僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時,才允許他拿起筷子進餐。(3)規(guī)定奇數(shù)號哲學(xué)家先拿他左邊的筷子,然后再去拿右邊的筷子;而偶數(shù)號哲學(xué)家則相反。按此規(guī)定,將是1、2號哲學(xué)家競爭1號筷子;3、4號哲學(xué)家競爭3號筷子。即五位哲學(xué)家都先競爭奇數(shù)號筷子,獲得后,再去競爭偶數(shù)號筷子,最后總會有一位哲學(xué)家能獲得兩只筷子而進餐。2025/1/14107

2.利用AND信號量機制解決哲學(xué)家進餐問題在哲學(xué)家進餐問題中,要求每個哲學(xué)家先獲得兩個臨界資源(筷子)后方能進餐,這在本質(zhì)上就是前面所介紹的AND同步問題,故用AND信號量機制可獲得最簡潔的解法。Varchopstickarray［0,…,4］ofsemaphore:=(1,1,1,1,1);processirepeatSP(chopstick［(i+1)mod5］,chopstick［i］);eat;SV(chopstick［(i+1)mod5］,chopstick［i］);think;untilfalse;2025/1/141082.4經(jīng)典進程的同步問題2.4.1生產(chǎn)者—消費者問題2.4.2哲學(xué)家進餐問題2.4.3讀者—寫者問題2025/1/141092.4.3讀者-寫者問題一個數(shù)據(jù)文件或記錄可被多個進程共享,把只要求讀該文件的進程稱為“Reader進程”,其他進程稱為“Writer進程”允許多個進程同時讀一個共享對象,因為讀不會使數(shù)據(jù)文件混亂不允許一個Writer進程和其他Reader進程或Writer進程同時訪問一個對象讀者—寫者問題(Reader-WriterProblem)是指保證一個Writer進程必須與其他進程互斥地訪問共享對象的同步問題2025/1/141101.利用記錄型信號量解決讀者-寫者問題設(shè)置兩個信號量:讀互斥信號量rmutex和寫互斥信號量wmutex。另外設(shè)立一個讀計數(shù)器readcount表示正在讀的進程數(shù)目,它是一個整型變量,初值為0。wmutex:用于實現(xiàn)Reader與Writer進程間在讀或?qū)憰r的互斥,初值為1。rmutex:用于讀者互斥地訪問readcount,初值為1。2025/1/14111讀者-寫者問題可描述如下:Varrmutex,wmutex:semaphore:=1,1;readcount:integer:=0;beginparbegin

Reader:beginrepeat

P(rmutex);ifreadcount=0thenP(wmutex);readcount:=readcount+1;

V(rmutex);…