第2章進(jìn)程管理

操作系統(tǒng)第二章進(jìn)程管理院(系):計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院研究室:軟件支持技術(shù)教師:印桂生、王紅濱2025/1/141內(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ī)制2.6進(jìn)程通信2.7線程進(jìn)程管理的主要功能是把處理機(jī)分配給進(jìn)程,并對(duì)處理器運(yùn)行進(jìn)行有效地控制和管理,以及協(xié)調(diào)各個(gè)進(jìn)程之間的相互關(guān)系。2025/1/1422.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)程控制塊2025/1/1432.1.2前趨圖(PrecedenceGraph)前趨圖是一個(gè)有向無(wú)循環(huán)圖,記為DAG(DirectedAcyclicGraph),用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。圖中的每個(gè)結(jié)點(diǎn)可用于描述一個(gè)程序段或進(jìn)程,乃至一條語(yǔ)句;結(jié)點(diǎn)間的有向邊則用于表示兩個(gè)結(jié)點(diǎn)之間存在的偏序(PartialOrder)或前趨關(guān)系(PrecedenceRelation)“→”。

→={(Pi,Pj)|PimustcompletebeforePjmaystart},如果(Pi,Pj)∈→,可寫成Pi→Pj,稱Pi是Pj的直接前趨,而稱Pj是Pi的直接后繼。在前趨圖中,把沒有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)(InitialNode),把沒有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)(FinalNode)。2025/1/144每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight),用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間。圖2-2前趨圖2025/1/145對(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→S22025/1/1462.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)程控制塊2025/1/147程序的執(zhí)行有兩種方式:順序執(zhí)行和并發(fā)執(zhí)行。順序執(zhí)行是單道批處理系統(tǒng)的執(zhí)行方式,也用于簡(jiǎn)單的單片機(jī)系統(tǒng);現(xiàn)在的操作系統(tǒng)多為并發(fā)執(zhí)行,具有許多新的特征。引入并發(fā)執(zhí)行的目的是為了提高資源利用率。2025/1/148圖2-1程序的順序執(zhí)行1.程序的順序執(zhí)行這是最自然、也是最初的設(shè)計(jì)。僅當(dāng)前一操作(程序段)執(zhí)行完后,才能執(zhí)行后繼操作。例如,在進(jìn)行計(jì)算時(shí),總須先輸入用戶的程序和數(shù)據(jù),然后進(jìn)行計(jì)算,最后才能打印計(jì)算結(jié)果。S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;2.1.1程序的順序執(zhí)行及其特征2025/1/1492.程序順序執(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)試和校正程序。2025/1/14102.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)程控制塊2025/1/14112.1.3程序的并發(fā)執(zhí)行及其特征1.程序的并發(fā)執(zhí)行圖2-3并發(fā)執(zhí)行時(shí)的前趨圖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í)行。對(duì)于具有下述四條語(yǔ)句的程序段:S1:a:=x+2S2:b:=y+4S3:c:=a+bS4:d:=c+6圖2-4四條語(yǔ)句的前趨關(guān)系2025/1/14132.程序并發(fā)執(zhí)行時(shí)的特征(1)間斷性 "走走停停",一個(gè)程序可能走到中途停下來(lái),失去原有的時(shí)序關(guān)系;(2)失去封閉性

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

程序A和B并發(fā)執(zhí)行,以不可預(yù)知的速度運(yùn)行,可出現(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。2025/1/1415補(bǔ)充:并發(fā)執(zhí)行失去封閉性的原因是共享資源的影響,去掉這種影響就行了。1966年,由Bernstein(波恩斯坦)給出并發(fā)執(zhí)行的條件。若兩個(gè)程序P1和P2滿足下述條件,便能并發(fā)執(zhí)行且有可再現(xiàn)性: (R(P1)

W(P2))(R(P2)

W(P1))(W(P1)

W(P2))={}解釋:運(yùn)算的讀集R(Pi)是指在運(yùn)算執(zhí)行期間參考的所有變量的集合;運(yùn)算的寫集W(Pi)是指在運(yùn)算執(zhí)行期間要改變的所有變量的集合。存在的問(wèn)題是這個(gè)條件不好檢查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)=ieikoi4可見:語(yǔ)句S1和S2可以并發(fā)執(zhí)行嗎？語(yǔ)句S1和S3可以并發(fā)執(zhí)行嗎？語(yǔ)句S2和S3可以并發(fā)執(zhí)行嗎？語(yǔ)句S3和S4可以并發(fā)執(zhí)行嗎？語(yǔ)句S2和S4可以并發(fā)執(zhí)行嗎？(R(S1)

W(S2))(R(S2)

W(S1))(W(S1)

W(S2))={}可以不可以,因?yàn)?R(S3)

W(S1)={a}{}不可以,因?yàn)?R(S3)

W(S2)={}不可以,因?yàn)?R(S4)

W(S3)={c}{}可以2025/1/14172.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)程控制塊2025/1/1418進(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)境等。2025/1/14192.1.4進(jìn)程的特征與狀態(tài)1.進(jìn)程的特征和定義動(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í)行;獨(dú)立性:進(jìn)程是一個(gè)能獨(dú)立運(yùn)行的基本單位,也是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位;異步性:各進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn);結(jié)構(gòu)特征:程序段、數(shù)據(jù)段和PCB;程序文件中通常也劃分了代碼段和數(shù)據(jù)段,進(jìn)程的創(chuàng)建與撤消就是PCB的創(chuàng)建與撤消。2025/1/1420較典型的進(jìn)程定義有:(1)進(jìn)程是程序的一次執(zhí)行。(2)進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。(3)進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過(guò)程,它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。在引入了進(jìn)程實(shí)體的概念后,我們可以把傳統(tǒng)OS中的進(jìn)程定義為:“進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程,是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位”。2025/1/1421進(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ò)程,有它的撤銷,程序可長(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)程;2025/1/14222.進(jìn)程的三種基本狀態(tài)(1)就緒(Ready)狀態(tài)進(jìn)程已獲得除處理機(jī)外的所需資源,等待分配處理機(jī)資源;只要分配CPU就可執(zhí)行。一個(gè)系統(tǒng)中多個(gè)處于就緒狀態(tài)的進(jìn)程排成就緒隊(duì)列。(2)執(zhí)行(Running)狀態(tài)處于就緒狀態(tài)的進(jìn)程一旦獲得了處理機(jī),就可以運(yùn)行,進(jìn)程狀態(tài)也就處于執(zhí)行狀態(tài)。處于此狀態(tài)的進(jìn)程的數(shù)目小于等于CPU的數(shù)目。(3)阻塞(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)緩沖空間等通常阻塞進(jìn)程也排成若干隊(duì)列。2025/1/1423圖2-5進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換1.時(shí)間片用光2.有優(yōu)先級(jí)高的進(jìn)程到來(lái)2025/1/1424進(jìn)程的其它兩種狀態(tài)新(創(chuàng)建)狀態(tài) 當(dāng)一個(gè)新進(jìn)程剛剛建立,還未將其放入就緒隊(duì)列時(shí)的狀態(tài),稱為新狀態(tài)。終止?fàn)顟B(tài) 當(dāng)一個(gè)進(jìn)程已經(jīng)正常結(jié)束或異常結(jié)束,操作系統(tǒng)已將其從系統(tǒng)隊(duì)列中移出,但尚未撤消,這時(shí)稱為終止?fàn)顟B(tài)。2025/1/1425圖2-5’進(jìn)程的五種基本狀態(tài)及其轉(zhuǎn)換進(jìn)程的五種基本狀態(tài)及其轉(zhuǎn)換2025/1/14261.引入掛起狀態(tài)的原因(1)終端用戶的請(qǐng)求 當(dāng)終端用戶在自己的程序運(yùn)行期間發(fā)現(xiàn)有可疑問(wèn)題時(shí),希望暫時(shí)將自己的程序靜止下來(lái)。(2)父進(jìn)程請(qǐng)求 父進(jìn)程需要考查和修改子進(jìn)程。(3)操作系統(tǒng)的需要 如檢查運(yùn)行中的資源使用情況。(4)對(duì)換的需要 緩和內(nèi)存緊張,將阻塞進(jìn)程換到外存上,有別于阻塞狀態(tài)。(5)負(fù)荷調(diào)節(jié)的需要 在實(shí)時(shí)系統(tǒng)中為了調(diào)整工作負(fù)荷可將不重要的進(jìn)程掛起。3.掛起狀態(tài)2025/1/1427圖2-6具有掛起狀態(tài)的進(jìn)程狀態(tài)圖2.進(jìn)程狀態(tài)的轉(zhuǎn)換2025/1/14282.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)程控制塊2025/1/14292.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)志。2025/1/14302.進(jìn)程控制塊中的信息1)進(jìn)程標(biāo)識(shí)符

進(jìn)程標(biāo)識(shí)符用于惟一地標(biāo)識(shí)一個(gè)進(jìn)程。一個(gè)進(jìn)程通常有兩種標(biāo)識(shí)符:(1)內(nèi)部標(biāo)識(shí)符。在所有的操作系統(tǒng)中,都為每一個(gè)進(jìn)程賦予一個(gè)惟一的數(shù)字標(biāo)識(shí)符,它通常是一個(gè)進(jìn)程的序號(hào)。設(shè)置內(nèi)部標(biāo)識(shí)符主要是為了方便系統(tǒng)使用。(2)外部標(biāo)識(shí)符。它由創(chuàng)建者提供,通常是由字母、數(shù)字組成,往往是由用戶(進(jìn)程)在訪問(wèn)該進(jìn)程時(shí)使用。為了描述進(jìn)程的家族關(guān)系,還應(yīng)設(shè)置父進(jìn)程標(biāo)識(shí)及子進(jìn)程標(biāo)識(shí)。此外,還可設(shè)置用戶標(biāo)識(shí),以指示擁有該進(jìn)程的用戶。2025/1/14312)處理機(jī)狀態(tài) 處理機(jī)狀態(tài)信息主要是由處理機(jī)的各種寄存器中的內(nèi)容組成的。①通用寄存器,又稱為用戶可視寄存器,它們是用戶程序可以訪問(wèn)的,用于暫存信息,在大多數(shù)處理機(jī)中,有8~32個(gè)通用寄存器,在RISC結(jié)構(gòu)的計(jì)算機(jī)中可超過(guò)100個(gè);②指令計(jì)數(shù)器PC,其中存放了要訪問(wèn)的下一條指令的地址;③程序狀態(tài)字PSW,其中含有狀態(tài)信息,如條件碼、執(zhí)行方式、中斷屏蔽標(biāo)志等;④用戶棧指針,指每個(gè)用戶進(jìn)程都有一個(gè)或若干個(gè)與之相關(guān)的系統(tǒng)棧,用于存放過(guò)程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向該棧的棧頂。2025/1/14323)進(jìn)程調(diào)度信息在PCB中還存放一些與進(jìn)程調(diào)度和進(jìn)程對(duì)換有關(guān)的信息,包括:①進(jìn)程狀態(tài),指明進(jìn)程的當(dāng)前狀態(tài),作為進(jìn)程調(diào)度和對(duì)換時(shí)的依據(jù);②進(jìn)程優(yōu)先級(jí),用于描述進(jìn)程使用處理機(jī)的優(yōu)先級(jí)別的一個(gè)整數(shù),優(yōu)先級(jí)高的進(jìn)程應(yīng)優(yōu)先獲得處理機(jī);③進(jìn)程調(diào)度所需的其它信息,它們與所采用的進(jìn)程調(diào)度算法有關(guān),比如,進(jìn)程已等待CPU的時(shí)間總和、進(jìn)程已執(zhí)行的時(shí)間總和等;④事件,是指進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件,即阻塞原因。2025/1/14334)進(jìn)程控制信息進(jìn)程控制信息包括:①程序和數(shù)據(jù)的地址,是指進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存地(首)址,以便再調(diào)度到該進(jìn)程執(zhí)行時(shí),能從PCB中找到其程序和數(shù)據(jù);②進(jìn)程同步和通信機(jī)制,指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)必需的機(jī)制,如消息隊(duì)列指針、信號(hào)量等,它們可能全部或部分地放在PCB中;③資源清單,是一張列出了除CPU以外的、進(jìn)程所需的全部資源及已經(jīng)分配到該進(jìn)程的資源的清單;④鏈接指針,它給出了本進(jìn)程(PCB)所在隊(duì)列中的下一個(gè)進(jìn)程的PCB的首地址。2025/1/1434圖2-7PCB鏈接隊(duì)列示意圖3.進(jìn)程控制塊的組織方式(1)鏈接方式把具有同一狀態(tài)的PCB用其中的鏈接字鏈接成一個(gè)隊(duì)列,可以形成就緒隊(duì)列、若干個(gè)阻塞隊(duì)列和空閑隊(duì)列(2)......2025/1/1435圖2-8按索引方式組織PCB3.進(jìn)程控制塊的組織方式(1)......(2)索引方式系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)建立幾張索引表,如就緒索引表、阻塞索引表等,并把各索引表在內(nèi)存的首地址記錄在專用單元中。索引表中記錄的是PCB在PCB表中的地地址。2025/1/1436內(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ī)制2.6進(jìn)程通信2.7線程2025/1/1437補(bǔ)充內(nèi)容處理機(jī)的執(zhí)行狀態(tài)分系統(tǒng)態(tài)和用戶態(tài)兩種:(1)系統(tǒng)態(tài)(管態(tài)、核心態(tài)):有較高特權(quán),能執(zhí)行一切指令,訪問(wèn)所有寄存器和存儲(chǔ)區(qū)。(2)用戶態(tài)(目態(tài)):有較低特權(quán),能執(zhí)行規(guī)定指令,訪問(wèn)指定寄存器和存儲(chǔ)區(qū)。 用戶程序運(yùn)行在用戶態(tài),不能執(zhí)行OS指令及區(qū)域。 OS內(nèi)核運(yùn)行在系統(tǒng)態(tài),進(jìn)程控制是由OS內(nèi)核實(shí)現(xiàn)的。2025/1/14382.2進(jìn)程控制進(jìn)程控制是進(jìn)程管理中最基本的功能,主要包括以下幾個(gè)方面創(chuàng)建新進(jìn)程終止已結(jié)束進(jìn)程終止由于某事件而無(wú)法運(yùn)行下去的進(jìn)程負(fù)責(zé)進(jìn)程的狀態(tài)轉(zhuǎn)換原語(yǔ)(primitive)由若干條指令構(gòu)成的“原子操作(atomicoperation)”過(guò)程,在執(zhí)行期間不可中斷,以保證其正確性。作為一個(gè)整體而不可分割。許多系統(tǒng)調(diào)用就是原語(yǔ)。系統(tǒng)調(diào)用并不都是原語(yǔ)。進(jìn)程A調(diào)用read(),因無(wú)數(shù)據(jù)而阻塞,在read()里未返回。然后進(jìn)程B調(diào)用read(),此時(shí)read()被重入。系統(tǒng)調(diào)用不一定一次執(zhí)行完并返回該進(jìn)程,有可能在特定的點(diǎn)暫停,而轉(zhuǎn)入到其他進(jìn)程。1.創(chuàng)建原語(yǔ)2.撤消原語(yǔ)3.阻塞原語(yǔ)4.喚醒原語(yǔ)5.掛起原語(yǔ)6.激活原語(yǔ)2025/1/14392.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)程的掛起與激活2025/1/14402.2.1進(jìn)程的創(chuàng)建圖2-9進(jìn)程樹1.進(jìn)程圖(ProcessGraph)進(jìn)程圖是用于描述一個(gè)進(jìn)程的家族關(guān)系的有向樹,樹中的結(jié)點(diǎn)表示進(jìn)程在進(jìn)程A創(chuàng)建了進(jìn)程B之后稱A是B的父進(jìn)程(ParentProcess),B是A的子進(jìn)程(ProgenyProcess)。創(chuàng)建父進(jìn)程的進(jìn)程稱為祖先進(jìn)程,把樹的根結(jié)點(diǎn)稱為進(jìn)程家族的祖先進(jìn)程(Ancestor)子進(jìn)程可以繼承(Inherit)父進(jìn)程的資源。撤消父進(jìn)程時(shí)必須同時(shí)撤消子進(jìn)程2025/1/14412.引起創(chuàng)建進(jìn)程的事件 在多道程序環(huán)境中,只有進(jìn)程才能在系統(tǒng)中運(yùn)行。因此,為使程序運(yùn)行,必須創(chuàng)建進(jìn)程,創(chuàng)建進(jìn)程事件包括:(1)用戶登錄 在分時(shí)系統(tǒng)中,用戶在終端登錄后,如是合法用戶,系統(tǒng)將為用戶創(chuàng)建一個(gè)進(jìn)程,并插入就緒隊(duì)列。(2)作業(yè)調(diào)度 在批處理系統(tǒng)中,當(dāng)作業(yè)調(diào)度程序調(diào)度到某作業(yè)時(shí),將該作業(yè)裝入內(nèi)存,為它分配資源并創(chuàng)建進(jìn)程。(3)提供服務(wù) 當(dāng)運(yùn)行中的用戶進(jìn)程提出某種請(qǐng)求后,系統(tǒng)將專門創(chuàng)建一個(gè)進(jìn)程來(lái)提供服務(wù),如打印。(4)應(yīng)用請(qǐng)求由應(yīng)用進(jìn)程為自己創(chuàng)建進(jìn)程,以便能并發(fā)執(zhí)行,如輸入、計(jì)算、輸出程序。2025/1/14423.進(jìn)程的創(chuàng)建步驟(CreationofProgress)(1)申請(qǐng)空白PCB為新進(jìn)程申請(qǐng)惟一的數(shù)字標(biāo)識(shí)符,并從PCB集合中索取一個(gè)空白PCB(2)為新進(jìn)程分配資源為新進(jìn)程的程序和數(shù)據(jù)分配內(nèi)存。對(duì)于批處理型作業(yè),可以在用戶提出創(chuàng)建進(jìn)程時(shí)要求提供所需內(nèi)存大小。對(duì)于交互型作業(yè)可以由系統(tǒng)來(lái)分配一定的空間(3)初始化進(jìn)程控制塊初始化標(biāo)識(shí)信息將系統(tǒng)標(biāo)識(shí)信息寫入新PCB初始化處理機(jī)狀態(tài)信息使程序計(jì)數(shù)器指向程序的入口地址,棧指針指向棧頂初始化處理機(jī)控制信息將進(jìn)程的狀態(tài)設(shè)為就緒狀態(tài)或靜止就緒狀態(tài)(4)將新進(jìn)程插入就緒隊(duì)列如果進(jìn)程就緒隊(duì)列能夠接納新進(jìn)程,便將新進(jìn)程插入就緒隊(duì)列2025/1/14432.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)程的掛起與激活2025/1/14442.2.2進(jìn)程的終止1.引起進(jìn)程終止(TerminationofProcess)的事件1)正常結(jié)束在任何計(jì)算機(jī)系統(tǒng)中,都應(yīng)有一個(gè)用于表示進(jìn)程已經(jīng)運(yùn)行完成的指示。例如,在批處理系統(tǒng)中,通常在程序的最后安排一條Halt指令或終止的系統(tǒng)調(diào)用。當(dāng)程序運(yùn)行到Halt指令時(shí),將產(chǎn)生一個(gè)中斷,去通知OS本進(jìn)程已經(jīng)完成。在分時(shí)系統(tǒng)中,用戶可利用Logsoff去表示進(jìn)程運(yùn)行完畢,此時(shí)同樣可產(chǎn)生一個(gè)中斷,去通知OS進(jìn)程已運(yùn)行完畢。2025/1/14452)異常結(jié)束在進(jìn)程運(yùn)行期間,由于出現(xiàn)某些錯(cuò)誤和故障而迫使進(jìn)程終止。這類異常事件很多,常見的有:①越界錯(cuò)誤。這是指程序所訪問(wèn)的存儲(chǔ)區(qū),已越出該進(jìn)程的區(qū)域;②保護(hù)錯(cuò)。進(jìn)程試圖去訪問(wèn)一個(gè)不允許訪問(wèn)的資源或文件,或者以不適當(dāng)?shù)姆绞竭M(jìn)行訪問(wèn),例如,進(jìn)程試圖去寫一個(gè)只讀文件;③非法指令。程序試圖去執(zhí)行一條不存在的指令。出現(xiàn)該錯(cuò)誤的原因,可能是程序錯(cuò)誤地轉(zhuǎn)移到數(shù)據(jù)區(qū),把數(shù)據(jù)當(dāng)成了指令;④特權(quán)指令錯(cuò)。用戶進(jìn)程試圖去執(zhí)行一條只允許OS執(zhí)行的指令;⑤運(yùn)行超時(shí)。進(jìn)程的執(zhí)行時(shí)間超過(guò)了指定的最大值;⑥等待超時(shí)。進(jìn)程等待某事件的時(shí)間,超過(guò)了規(guī)定的最大值;⑦算術(shù)運(yùn)算錯(cuò)。進(jìn)程試圖去執(zhí)行一個(gè)被禁止的運(yùn)算,例如,被0除;⑧I/O故障。這是指在I/O過(guò)程中發(fā)生了錯(cuò)誤等。2025/1/14463)外界干預(yù)外界干預(yù)并非指在本進(jìn)程運(yùn)行中出現(xiàn)了異常事件,而是指進(jìn)程應(yīng)外界的請(qǐng)求而終止運(yùn)行。這些干預(yù)有:①操作員或操作系統(tǒng)干預(yù)。由于某種原因,例如,發(fā)生了死鎖,由操作員或操作系統(tǒng)終止該進(jìn)程;②父進(jìn)程請(qǐng)求。由于父進(jìn)程具有終止自己的任何子孫進(jìn)程的權(quán)利,因而當(dāng)父進(jìn)程提出請(qǐng)求時(shí),系統(tǒng)將終止該進(jìn)程;③父進(jìn)程終止。當(dāng)父進(jìn)程終止時(shí),OS也將他的所有子孫進(jìn)程終止。2025/1/14472.進(jìn)程的終止過(guò)程(1)根據(jù)被終止進(jìn)程的標(biāo)識(shí)符,從PCB集合中檢索出該進(jìn)程的PCB,從中讀出該進(jìn)程的狀態(tài)。(2)若被終止進(jìn)程正處于執(zhí)行狀態(tài),應(yīng)立即終止該進(jìn)程的執(zhí)行,并置調(diào)度標(biāo)志為真,用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。(3)若該進(jìn)程還有子孫進(jìn)程,還應(yīng)將其所有子孫進(jìn)程予以終止,以防他們成為不可控的進(jìn)程。(4)將被終止進(jìn)程所擁有的全部資源,或者歸還給其父進(jìn)程,或者歸還給系統(tǒng)。(5)將被終止進(jìn)程(它的PCB)從所在隊(duì)列(或鏈表)中移出,等待其他程序來(lái)搜集信息。2025/1/14482.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)程的掛起與激活2025/1/14492.2.3進(jìn)程的阻塞與喚醒1.引起進(jìn)程阻塞和喚醒的事件 (1)請(qǐng)求系統(tǒng)服務(wù) 如請(qǐng)求打印機(jī)時(shí),若已被其他進(jìn)程占用,此時(shí)只能阻塞,等其他進(jìn)程釋放后再將請(qǐng)求進(jìn)程喚醒。(2)啟動(dòng)某種操作 當(dāng)進(jìn)程啟動(dòng)某種操作后,如果該進(jìn)程必須在該操作完成后才能繼續(xù)執(zhí)行,則必須先使進(jìn)程阻塞,以等待該操作完成。如啟動(dòng)I/O設(shè)備。(3)新數(shù)據(jù)尚未到達(dá) 對(duì)于相互合作的進(jìn)程,如果一個(gè)進(jìn)程需要另一合作進(jìn)程提供的數(shù)據(jù),則在數(shù)據(jù)到達(dá)之前只能阻塞。(4)無(wú)新工作可做 系統(tǒng)中的一些特殊功能進(jìn)程,在完成了任務(wù)之后,等待新任務(wù)到來(lái)。如系統(tǒng)中的發(fā)送進(jìn)程。2025/1/14502.進(jìn)程阻塞過(guò)程正在執(zhí)行的進(jìn)程,當(dāng)發(fā)現(xiàn)上述某事件時(shí),由于無(wú)法繼續(xù)執(zhí)行,于是進(jìn)程便通過(guò)調(diào)用阻塞原語(yǔ)block()把自己阻塞?？梢?進(jìn)程的阻塞是進(jìn)程自身的一種主動(dòng)行為進(jìn)入block過(guò)程后,由于此時(shí)該進(jìn)程還處于執(zhí)行狀態(tài),所以應(yīng)先立即停止執(zhí)行,把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為阻塞,并將PCB插入阻塞隊(duì)列如果系統(tǒng)中設(shè)置了因不同事件而阻塞的多個(gè)阻塞隊(duì)列,則應(yīng)將本進(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)境2025/1/14513.進(jìn)程喚醒過(guò)程當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)時(shí),如I/O完成或其所期待的數(shù)據(jù)已經(jīng)到達(dá),則由有關(guān)進(jìn)程(比如,用完并釋放了該I/O設(shè)備的進(jìn)程)調(diào)用喚醒原語(yǔ)wakeup(),將等待該事件的進(jìn)程喚醒喚醒原語(yǔ)執(zhí)行的過(guò)程是把被阻塞的進(jìn)程從等待該事件的阻塞隊(duì)列中移出將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒將該P(yáng)CB插入到就緒隊(duì)列中2025/1/14522.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)程的掛起與激活2025/1/14532.2.4進(jìn)程的掛起與激活1.進(jìn)程的掛起當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時(shí),比如,用戶進(jìn)程請(qǐng)求將自己掛起,或父進(jìn)程請(qǐng)求將自己的某個(gè)子進(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)程考查該進(jìn)程的運(yùn)行情況而把該進(jìn)程的PCB復(fù)制到某指定的內(nèi)存區(qū)域。若被掛起的進(jìn)程正在執(zhí)行,則轉(zhuǎn)向調(diào)度程序重新調(diào)度。2025/1/14542.進(jìn)程的激活過(guò)程當(dāng)發(fā)生激活進(jìn)程的事件時(shí),例如,父進(jìn)程或用戶進(jìn)程請(qǐng)求激活指定進(jìn)程,若該進(jìn)程駐留在外存而內(nèi)存中已有足夠的空間時(shí),則可將在外存上處于靜止就緒狀態(tài)的進(jìn)程換入內(nèi)存。這時(shí),系統(tǒng)將利用激活原語(yǔ)active()將指定進(jìn)程激活。active()原語(yǔ)執(zhí)行過(guò)程激活原語(yǔ)先將進(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)程。2025/1/1455內(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ī)制2.6進(jìn)程通信2.7線程2025/1/14562.3進(jìn)程同步2.3.1進(jìn)程同步的基本概念2.3.2信號(hào)量機(jī)制2.3.3信號(hào)量的應(yīng)用2025/1/1457一個(gè)循環(huán)進(jìn)程順序執(zhí)行的謄抄輸入:fwhile(f不為空)dobegininput;output;end由這個(gè)程序完成謄抄工作是不會(huì)出錯(cuò)的。2025/1/1458兩個(gè)進(jìn)程并發(fā)執(zhí)行完成謄抄設(shè)有一臺(tái)標(biāo)準(zhǔn)輸入設(shè)備(鍵盤),和一臺(tái)標(biāo)準(zhǔn)輸出設(shè)備(顯示器或打印機(jī)),輸入進(jìn)程負(fù)責(zé)從標(biāo)準(zhǔn)設(shè)備中讀取一個(gè)字符,送緩沖區(qū)中。輸出進(jìn)程從緩沖區(qū)中取數(shù)據(jù),送標(biāo)準(zhǔn)設(shè)備輸出。2025/1/1459兩個(gè)進(jìn)程并發(fā)執(zhí)行完成謄抄parbeginprocess輸入beginwhile(不為結(jié)束符)dobegininput;{從標(biāo)準(zhǔn)輸入設(shè)備讀入一個(gè)數(shù)據(jù)}send;{將讀入的數(shù)據(jù)送到buffer}endendprocess輸出beginwhile(buffer不為空)dobeginreceive;{從buffer中取數(shù)據(jù)}output;{送打印機(jī)輸出}endendparend2025/1/1460兩個(gè)進(jìn)程并發(fā)執(zhí)行完成謄抄這兩個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)可能出現(xiàn)如下情況:1.輸出進(jìn)程運(yùn)行的速度比輸入進(jìn)程快時(shí),有些輸出會(huì)重復(fù);如輸入送入了一個(gè)字符“A”,輸出取出打印“A”,當(dāng)輸入進(jìn)程還未送入新的數(shù)據(jù),輸出進(jìn)程已執(zhí)行,又取出“A”打印,這樣“A”的輸出就重復(fù)了,出錯(cuò)。2.輸入進(jìn)程執(zhí)行的速度比輸出進(jìn)程快時(shí),有些數(shù)據(jù)會(huì)丟失;如輸入進(jìn)程送入一個(gè)字符“B”,緊接著(當(dāng)輸出進(jìn)程還未取走字符“B”)又送入字符“N”,這時(shí)輸出進(jìn)程取走的是“N”,“B”就丟失了。2025/1/14612.3.1進(jìn)程同步的基本概念1.兩種形式的制約關(guān)系在多道程序環(huán)境下,當(dāng)程序并發(fā)執(zhí)行時(shí),由于資源共享和進(jìn)程合作,使同處于系統(tǒng)中的諸進(jìn)程之間存在兩種形式的制約關(guān)系。(1)間接相互制約關(guān)系同處于一個(gè)系統(tǒng)中的進(jìn)程必然共享某種資源,如CPU、I/O設(shè)備等,間接相互制約即源于資源共享。如A、B共享打印機(jī),若A申請(qǐng)打印時(shí),打印機(jī)已分配給B,則A只能阻塞,等B釋放后再改為就緒,又稱為“互斥”。(2)直接相互制約關(guān)系

這種制約源于進(jìn)程之間的合作關(guān)系。如進(jìn)程A向B提供數(shù)據(jù),當(dāng)輸入緩沖空時(shí),B不能得到數(shù)據(jù)而阻塞;反之當(dāng)緩沖滿時(shí),A無(wú)法寫入而阻塞,又稱為“同步”。2025/1/1462引例:宿舍電話的使用打印機(jī)的使用2.臨界資源(CriticalResouce)定義:在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問(wèn)的資源。例如:打印機(jī),磁帶機(jī),卡片輸入機(jī),變量,表格,數(shù)據(jù),指針、數(shù)組等。2025/1/1463例設(shè)有兩個(gè)進(jìn)程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個(gè)售票處。每個(gè)售票處通過(guò)終端訪問(wèn)系統(tǒng)中的公用數(shù)據(jù)區(qū),假定公共數(shù)據(jù)區(qū)中一些單元xk(k=1,2,…)分別存放×月×日×次航班的現(xiàn)存票數(shù)。設(shè)P1,P2,…,Pn表示各售票處的處理進(jìn)程,R1,R2,…,Rn表示各進(jìn)程執(zhí)行時(shí)所用的工作單元。進(jìn)程實(shí)現(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)由前例可見,不論是硬件臨界資源還是軟件臨界資源,多個(gè)進(jìn)程必須互斥地對(duì)它進(jìn)行訪問(wèn)在每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼稱為臨界區(qū)(criticalsection)每個(gè)進(jìn)程進(jìn)入臨界區(qū)之前應(yīng)先對(duì)欲訪問(wèn)的臨界資源進(jìn)行檢查,看是否正在被訪問(wèn)。如果此刻該臨界資源未被訪問(wèn),該進(jìn)程可進(jìn)入臨界區(qū),并設(shè)置它正在被訪問(wèn)的標(biāo)志,在臨界區(qū)之前執(zhí)行的這段代碼稱為進(jìn)入?yún)^(qū)(entrysection)在臨界區(qū)后面也要加上一段代碼,用于將臨界區(qū)被訪問(wèn)的資源恢復(fù)為未被訪問(wèn)的標(biāo)志,稱為退出區(qū)(exitsection)2025/1/1467可把一個(gè)訪問(wèn)臨界資源的循環(huán)進(jìn)程描述如下:

repeat

criticalsection; {臨界區(qū)}

remaindersection; {剩余區(qū)}untilfalse;entrysectionexitsection{進(jìn)入?yún)^(qū)}{退出區(qū)}2025/1/14684.同步機(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ì)要求訪問(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ī)。2025/1/14692.3進(jìn)程同步2.3.1進(jìn)程同步的基本概念2.3.2信號(hào)量機(jī)制2.3.3信號(hào)量的應(yīng)用2025/1/14701965年,荷蘭學(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)量機(jī)制已廣泛應(yīng)用于單處理機(jī)、多處理機(jī)以及計(jì)算機(jī)網(wǎng)絡(luò)中。信號(hào)量就是OS提供的管理公有資源的有效手段。信號(hào)量代表可用資源實(shí)體的數(shù)量。2.3.2信號(hào)量機(jī)制2025/1/14711.整型信號(hào)量最初由Dijkstra把整型信號(hào)量定義為一個(gè)整型量,除初始化外,僅能通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作wait(S)和signal(S)來(lái)訪問(wèn)。這兩個(gè)操作一直被分別稱為P、V操作。wait和signal操作可描述為:wait(S):whileS≤0dono-op; S:=S-1;signal(S):S:=S+1;wait(S)和signal(S)是原子操作,因此它們?cè)趫?zhí)行時(shí)是不可中斷的。另外,在wait操作中,對(duì)S的測(cè)試和做S:=S-1操作時(shí)都不可中斷,信號(hào)量只能通過(guò)原語(yǔ)操作來(lái)訪問(wèn),不能被進(jìn)程調(diào)度所打斷。有“忙等”現(xiàn)象。2025/1/1472可把一個(gè)訪問(wèn)臨界資源的循環(huán)進(jìn)程描述如下:

repeat

criticalsection; {臨界區(qū)}

remaindersection; {剩余區(qū)}untilfalse;entrysectionexitsectionP(S);V(S);{進(jìn)入?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):用信號(hào)量實(shí)現(xiàn)進(jìn)程間互斥的程序如下:2025/1/14742.記錄型信號(hào)量在整型信號(hào)量機(jī)制中的wait操作,只要是信號(hào)量S≤0,就會(huì)不斷地測(cè)試。因此,該機(jī)制并未遵循“讓權(quán)等待”的準(zhǔn)則,而是使進(jìn)程處于“忙等”的狀態(tài)。記錄型信號(hào)量機(jī)制,則是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。但在采取了“讓權(quán)等待”的策略后,又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問(wèn)同一臨界資源的情況。為此,在信號(hào)量機(jī)制中,除了需要一個(gè)用于代表資源數(shù)目的整型變量value外,還應(yīng)增加一個(gè)進(jìn)程鏈表L,用于鏈接上述的所有等待進(jìn)程。記錄型信號(hào)量是由于它采用了記錄型的數(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在記錄型信號(hào)量機(jī)制中,S.value的初值表示系統(tǒng)中某類資源的數(shù)目,因而又稱為資源信號(hào)量對(duì)它的每次P操作,意味著進(jìn)程請(qǐng)求一個(gè)單位的該類資源,因此描述為S.value:=S.value-1;當(dāng)S.value＜0時(shí),表示該類資源已分配完畢,因此進(jìn)程應(yīng)調(diào)用block原語(yǔ),進(jìn)行自我阻塞,放棄處理機(jī),并插入到信號(hào)量鏈表S.L中?？梢?該機(jī)制遵循了“讓權(quán)等待”準(zhǔn)則。此時(shí)S.value的絕對(duì)值表示在該信號(hào)量鏈表中已阻塞進(jìn)程的數(shù)目對(duì)信號(hào)量的每次V操作,表示執(zhí)行進(jìn)程釋放一個(gè)單位資源,故S.value:=S.value+1操作表示資源數(shù)目加1。若加1后仍是S.value≤0,則表示在該信號(hào)量鏈表中,仍有等待該資源的進(jìn)程被阻塞,故還應(yīng)調(diào)用wakeup原語(yǔ),將S.L鏈表中的第一個(gè)等待進(jìn)程喚醒。如果S.value的初值為1,表示只允許一個(gè)進(jìn)程訪問(wèn)臨界資源,此時(shí)的信號(hào)量轉(zhuǎn)化為互斥信號(hào)量。2025/1/14773.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阻塞

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

“阻塞”(去第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;2025/1/1482一般“信號(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è)可控開關(guān)。2025/1/14832.3進(jìn)程同步2.3.1進(jìn)程同步的基本概念2.3.2信號(hào)量機(jī)制2.3.3信號(hào)量的應(yīng)用2025/1/14842.3.3信號(hào)量的應(yīng)用1.利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥mutex作為互斥信號(hào)量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利用信號(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ì)臨界資源的互斥訪問(wèn)。缺少V(mutex)將會(huì)使臨界資源永遠(yuǎn)不被釋放,從而使因等待該資源而阻塞的進(jìn)程不再被喚醒。2025/1/14862.利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系設(shè)有兩個(gè)并發(fā)進(jìn)程P1和P2。P1中有語(yǔ)句S1,P2中有語(yǔ)句S2,希望在執(zhí)行完S1后執(zhí)行S2。為實(shí)現(xiàn)這種前趨關(guān)系,可讓進(jìn)程P1和P2共享一個(gè)公用信號(hào)量a,并賦初值為0,將V(a)操作放在語(yǔ)句S1后面;而在S2語(yǔ)句前插入P(a)操作。進(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操作。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進(jìn)程的基本概念

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

2.5管程機(jī)制2.6進(jìn)程通信2.7線程2025/1/14902.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讀者—寫者問(wèn)題2025/1/14912.4.1生產(chǎn)者—消費(fèi)者問(wèn)題一個(gè)生產(chǎn)者—一個(gè)消費(fèi)者問(wèn)題

前面我們已經(jīng)對(duì)生產(chǎn)者—消費(fèi)者問(wèn)題(Theproducer-consumerproblem)做了一些描述,但未考慮進(jìn)程的互斥與同步問(wèn)題,因而造成了數(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)者,因此,該問(wèn)題有很大的代表性及實(shí)用價(jià)值。2025/1/14921.利用記錄型信號(hào)量解決生產(chǎn)者—消費(fèi)者問(wèn)題假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖池中,具有1個(gè)緩沖區(qū);利用信號(hào)量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定就一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者,只要緩沖池未滿,生產(chǎn)者便可將消息送入緩沖池;只要緩沖池未空,消費(fèi)者便可從緩沖池中取走一個(gè)消息。對(duì)生產(chǎn)者—消費(fèi)者問(wèn)題可描述如下:設(shè)置兩個(gè)信號(hào)量:full:表示放有消息的緩沖區(qū)數(shù),其初值為0。empty:表示可供使用的緩沖區(qū)數(shù),其初值為1。2025/1/1493Varempty,full:semaphore:=1,0;buffer:item;beginparbeginproducer:{生產(chǎn)者進(jìn)程}beginrepeat…生產(chǎn)一條消息=>nextp;…P(empty);{empty減1}buffer:=nextp;V(full);{full增1}untilfalse;endconsumer:{消費(fèi)者進(jìn)程}beginrepeatP(full);nextc:=buffer;V(empty);

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

in,out:integer:=0,0;beginparbeginproducer:{生產(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;endconsumer:{消費(fèi)者進(jìn)程}beginrepeatP(full);

P(mutex);

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

V(mutex);

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

untilfalse;endparendend2025/1/1497在生產(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)程死鎖。2025/1/1498初始值:mutex:=1; 生產(chǎn)者:P(empty);full:=0; P(mutex);empty:=n; 消費(fèi)者:P(mutex); P(full);生產(chǎn)者:P(empty); 成功empty:=n-1而P(mutex); 不成功消費(fèi)者:P(mutex); 成功mutex:=0;P(full); 不成功full:=-1;死鎖！2025/1/14992.利用AND信號(hào)量解決生產(chǎn)者—消費(fèi)者問(wè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);

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

untilfalse;endparendend2025/1/141002.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讀者—寫者問(wèn)題2025/1/141012.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)餐用餐畢,放下筷子2025/1/141021.利用記錄型信號(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ù)組。其描述如下:2025/1/14103Varchopstick: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í)也得不到兩把筷子。形成了死鎖。01234104322025/1/14104可采取以下幾種解決方法:(1)至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子,最終能保證至少有一位哲學(xué)家能夠進(jìn)餐,并在用畢時(shí)能釋放出他用過(guò)的兩只筷子,從而使更多的哲學(xué)家能夠進(jìn)餐。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;{進(jìn)餐}… V(chopstick［i］); V(chopstick［(i+1)mod5］);

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

2.利用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ī)制可獲得最簡(jiǎn)潔的解法。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)典進(jìn)程的同步問(wèn)題2.4.1生產(chǎn)者—消費(fèi)者問(wèn)題2.4.2哲學(xué)家進(jìn)餐問(wèn)題2.4.3讀者—寫者問(wèn)題2025/1/141092.4.3讀者-寫者問(wèn)題一個(gè)數(shù)據(jù)文件或記錄可被多個(gè)進(jìn)程共享,把只要求讀該文件的進(jìn)程稱為“Reader進(jìn)程”,其他進(jìn)程稱為“Writer進(jìn)程”允許多個(gè)進(jìn)程同時(shí)讀一個(gè)共享對(duì)象,因?yàn)樽x不會(huì)使數(shù)據(jù)文件混亂不允許一個(gè)Writer進(jìn)程和其他Reader進(jìn)程或Writer進(jìn)程同時(shí)訪問(wèn)一個(gè)對(duì)象讀者—寫者問(wèn)題(Reader-WriterProblem)是指保證一個(gè)Writer進(jìn)程必須與其他進(jìn)程互斥地訪問(wèn)共享對(duì)象的同步問(wèn)題2025/1/141101.利用記錄型信號(hào)量解決讀者-寫者問(wèn)題設(shè)置兩個(gè)信號(hào)量:讀互斥信號(hào)量rmutex和寫互斥信號(hào)量wmutex。另外設(shè)立一個(gè)讀計(jì)數(shù)器readcount表示正在讀的進(jìn)程數(shù)目,它是一個(gè)整型變量,初值為0。wmutex:用于實(shí)現(xiàn)Reader與Writer進(jìn)程間在讀或?qū)憰r(shí)的互斥,初值為1。rmutex:用于讀者互斥地訪問(wèn)readcount,初值為1。2025/1/14111讀者-寫者問(wèn)題可描述如下:Varrmutex,wmutex:semaphore:=1,1;readcount:integer:=0;beginparbegin

Reader:beginrepeat

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

V(rmutex);…