第2章進(jìn)程概念和基本狀態(tài)

復(fù)習(xí)：操作系統(tǒng)的基本特征：

操作系統(tǒng)的主要功能：

OS結(jié)構(gòu)設(shè)計(jì)：

并發(fā)、共享、虛擬、異步CPU、存儲(chǔ)管理、設(shè)備管理、文件管理、用戶(hù)接口模塊、層次、C/S、面向?qū)ο笪?nèi)核、單體內(nèi)核第二章進(jìn)程的描述與控制

2.1前趨圖和程序執(zhí)行2.2進(jìn)程的描述2.3進(jìn)程控制2.4進(jìn)程同步2.5經(jīng)典進(jìn)程的同步問(wèn)題2.6進(jìn)程通信2.7線程(Threads)的基本概念2.8線程的實(shí)現(xiàn)2.1.1前趨圖

所謂前趨圖(PrecedenceGraph)，是指一個(gè)有向無(wú)循環(huán)圖，可記為DAG(DirectedAcyclicGraph)，它用于描述進(jìn)程之間執(zhí)行的先后順序。

圖中的每個(gè)結(jié)點(diǎn)可用來(lái)表示一個(gè)進(jìn)程或程序段，乃至一條語(yǔ)句，結(jié)點(diǎn)間的有向邊則表示兩個(gè)結(jié)點(diǎn)之間存在的偏序(PartialOrder)或前趨關(guān)系(PrecedenceRelation)。2.1前趨圖和程序執(zhí)行進(jìn)程(或程序)之間的前趨關(guān)系可用“→”來(lái)表示，如果進(jìn)程Pi和Pj存在著前趨關(guān)系，可表示為(Pi，Pj)∈→，也可寫(xiě)成Pi→Pj，表示在Pj開(kāi)始執(zhí)行之前Pi

必須完成。此時(shí)稱(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)。此外，每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或程序的執(zhí)行時(shí)間。

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)}前趨圖中是不允許有循環(huán)的，否則必然會(huì)產(chǎn)生不可能實(shí)現(xiàn)的前趨關(guān)系。

它一方面要求在S3開(kāi)始執(zhí)行之前，S2必須完成，另一方面又要求在S2開(kāi)始執(zhí)行之前，S3必須完成。顯然，這種關(guān)系是不可能實(shí)現(xiàn)的。

S2→S3，S3→S22.1.2程序順序執(zhí)行

1.程序的順序執(zhí)行

通常，一個(gè)應(yīng)用程序由若干個(gè)程序段組成，每一個(gè)程序段完成特定的功能，它們?cè)趫?zhí)行時(shí)，都需要按照某種先后次序順序執(zhí)行，僅當(dāng)前一程序段執(zhí)行完后，才運(yùn)行后一程序段。

例如，在進(jìn)行計(jì)算時(shí)，應(yīng)先運(yùn)行輸入程序，用于輸入用戶(hù)的程序和數(shù)據(jù)；然后運(yùn)行計(jì)算程序，對(duì)所輸入的數(shù)據(jù)進(jìn)行計(jì)算；最后才是運(yùn)行打印程序，打印計(jì)算結(jié)果。即使是一個(gè)程序段，也可能存在著執(zhí)行順序問(wèn)題，下面示出了一個(gè)包含了三條語(yǔ)句的程序段：

S1:a:=x+y；

S2:b:=a-5；

S3:c:=b+1；

其中，語(yǔ)句S2必須在語(yǔ)句S1后(即a被賦值)才能執(zhí)行，語(yǔ)句S3也只能在b被賦值后才能執(zhí)行，因此，三條語(yǔ)句存在著這樣的前趨關(guān)系：S1→S2→S3

2.程序順序執(zhí)行時(shí)的特征

在程序順序執(zhí)行時(shí)，具有這樣三個(gè)特征：

①順序性：指處理機(jī)嚴(yán)格地按照程序所規(guī)定的順序執(zhí)行，即每一操作必須在下一個(gè)操作開(kāi)始之前結(jié)束；

②封閉性：指程序在封閉的環(huán)境下運(yùn)行，即程序運(yùn)行時(shí)獨(dú)占全機(jī)資源，資源的狀態(tài)(除初始狀態(tài)外)只有本程序才能改變它，程序一旦開(kāi)始執(zhí)行，其執(zhí)行結(jié)果不受外界因素影響；

③可再現(xiàn)性：指只要程序執(zhí)行時(shí)的環(huán)境和初始條件相同，當(dāng)程序重復(fù)執(zhí)行時(shí)，不論它是從頭到尾不停頓地執(zhí)行，還是“停停走走”地執(zhí)行，都可獲得相同的結(jié)果。程序順序執(zhí)行時(shí)的這種特性，為程序員檢測(cè)和校正程序的錯(cuò)誤帶來(lái)了很大的方便。2.1.3程序并發(fā)執(zhí)行

1.程序的并發(fā)執(zhí)行：在輸入程序、計(jì)算程序和打印程序三者之間，存在著Ii→Ci→Pi這樣的前趨關(guān)系，以至對(duì)一個(gè)作業(yè)的輸入、計(jì)算和打印三個(gè)程序段必須順序執(zhí)行。對(duì)于具有下述四條語(yǔ)句的程序段：

S1:a:=x+2

S2:b:=y+4

S3:c:=a+b

S4:d:=c+b

可以看出：S3必須在a和b被賦值后方能執(zhí)行；S4必須在S3之后執(zhí)行；但S1和S2則可以并發(fā)執(zhí)行，因?yàn)樗鼈儽舜嘶ゲ灰蕾?lài)。

2.程序并發(fā)執(zhí)行時(shí)的特征

并發(fā)執(zhí)行的程序它們共享系統(tǒng)資源，以及它們?yōu)橥瓿赏豁?xiàng)任務(wù)而相互合作，致使在這些并發(fā)執(zhí)行的程序之間必將形成相互制約的關(guān)系，由此會(huì)給程序并發(fā)執(zhí)行帶來(lái)新的特征。

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

(2)失去封閉性。共享資源，這些資源的狀態(tài)也由這些程序來(lái)改變，致使其中任何一個(gè)程序在運(yùn)行時(shí)，其環(huán)境必然受其他程序的影響。

(3)不可再現(xiàn)性。失去封閉性－>失去可再現(xiàn)性；在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可重復(fù)特征。

程序A：

N=N+1;程序B：

print(N);N=0;假定某時(shí)刻：N=n;N=N+1;print(N);N=0;print(N);N=0;N=N+1;print(N);N=N+1;N=0;N=n+1n+1n=0nN=0N=1nN=n+1N=014舉例：計(jì)算交通流量觀察者beginrepeatwaitacargothroughN=N+1；untilend執(zhí)行序列(1)(2)(3)程序N=N+1；PrintN；N=0；PrintN；N=0；N=N+1；PrintN；N=N+1；N=0；最終結(jié)果NN=0N=N+1N=0打印結(jié)果N=n+1N=nN=n報(bào)告者beginrepeatdelayatimePrintN；

N=0；untilend初始N=n時(shí)，對(duì)于不同執(zhí)行序列，結(jié)果各不相同

2.2進(jìn)?程?的?描?述?

2.2.1進(jìn)程的定義和特征

1.進(jìn)程的定義

必須為每個(gè)進(jìn)程配置一個(gè)專(zhuān)門(mén)的數(shù)據(jù)結(jié)構(gòu)，稱(chēng)為進(jìn)程控制塊（PCB）。

利用PCB來(lái)描述進(jìn)程的基本情況和活動(dòng)過(guò)程，來(lái)控制和管理進(jìn)程。

由程序段、相關(guān)的數(shù)據(jù)段、PCB三部分構(gòu)成了進(jìn)程實(shí)體（進(jìn)程映像），將進(jìn)程實(shí)體簡(jiǎn)稱(chēng)進(jìn)程。

所謂創(chuàng)建進(jìn)程，實(shí)質(zhì)上就是創(chuàng)建進(jìn)程的PCB；

撤銷(xiāo)進(jìn)程，實(shí)質(zhì)上就是撤銷(xiāo)進(jìn)程的PCB其中較典型的定義有：

(1)進(jìn)程是程序的一次執(zhí)行。

(2)進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。

(3)進(jìn)程是具有獨(dú)立功能的程序在一個(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ú)立單位”。18進(jìn)程通常由三部分組成：程序、數(shù)據(jù)和進(jìn)程控制塊PCB

。創(chuàng)建進(jìn)程，實(shí)質(zhì)上就是創(chuàng)建進(jìn)程的PCB；撤銷(xiāo)進(jìn)程，實(shí)質(zhì)上就是撤銷(xiāo)進(jìn)程的PCB

程序

數(shù)據(jù)PCB（a）PCB

程

序

數(shù)據(jù)（b）PCB1共享程序

數(shù)據(jù)PCB2

數(shù)據(jù)（c）

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

進(jìn)程和程序是兩個(gè)截然不同的概念，除了進(jìn)程具有程序所沒(méi)有的PCB結(jié)構(gòu)外，還具有下面一些特征：

(1)動(dòng)態(tài)性。

(2)并發(fā)性。

(3)獨(dú)立性。

(4)異步性。20進(jìn)程與程序的區(qū)別：1)進(jìn)程是一次運(yùn)行的過(guò)程，屬于一種動(dòng)態(tài)的概念；而程序是指令的集合，是一個(gè)靜態(tài)的概念。5)

一個(gè)程序也可以對(duì)應(yīng)多個(gè)進(jìn)程。當(dāng)同一程序同時(shí)運(yùn)行于若干個(gè)不同的數(shù)據(jù)集合上時(shí)，它將屬于若干個(gè)不同的進(jìn)程。3)進(jìn)程是有生命期的；而程序是永久的。2)進(jìn)程可以并發(fā)執(zhí)行；而程序不能。4)進(jìn)程是系統(tǒng)資源分配的基本單位，而程序則不行。

編譯程序user1.cuser2.c2.2.2進(jìn)程的基本狀態(tài)及轉(zhuǎn)換

1.進(jìn)程的三種基本狀態(tài)

進(jìn)程在其生命周期內(nèi)可能具有多種狀態(tài)。每一個(gè)進(jìn)程至少應(yīng)處于三種基本狀態(tài)之一。

就緒狀態(tài)、執(zhí)行狀態(tài)、阻塞狀態(tài)

就緒狀態(tài)(Ready)：進(jìn)程已獲得除處理機(jī)外的所需資源，等待分配處理機(jī)資源；只要分配CPU就可執(zhí)行。

2.2.2進(jìn)程的基本狀態(tài)及轉(zhuǎn)換

1.進(jìn)程的三種基本狀態(tài)

執(zhí)行狀態(tài)(Running)：占用處理機(jī)資源；處于此狀態(tài)的進(jìn)程的數(shù)目小于等于CPU的數(shù)目。在沒(méi)有其他進(jìn)程可以執(zhí)行時(shí)（如所有進(jìn)程都在阻塞狀態(tài)），通常會(huì)自動(dòng)執(zhí)行系統(tǒng)的idle進(jìn)程（相當(dāng)于空操作）。

阻塞狀態(tài)(Blocked)：由于進(jìn)程等待某種條件（如I/O操作或進(jìn)程同步），在條件滿足之前無(wú)法繼續(xù)執(zhí)行。該事件發(fā)生前即使把處理機(jī)分配給該進(jìn)程，也無(wú)法運(yùn)行。如：等待I/O操作的完成。2.進(jìn)程狀態(tài)及轉(zhuǎn)換就緒執(zhí)行等待阻塞進(jìn)程調(diào)度1.時(shí)間片到2.高優(yōu)先級(jí)等待某事件而睡眠因等待事件發(fā)生而喚醒創(chuàng)建終止結(jié)束

3.創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)

1)創(chuàng)建狀態(tài)

進(jìn)程是由創(chuàng)建而產(chǎn)生。

創(chuàng)建一個(gè)進(jìn)程一般要通過(guò)多個(gè)步驟：

首先由進(jìn)程申請(qǐng)一個(gè)空白PCB，并向PCB中填寫(xiě)用于控制和管理進(jìn)程的信息；

然后為該進(jìn)程分配運(yùn)行時(shí)所必須的資源；

最后，把該進(jìn)程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊(duì)列之中。

3.創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)

1)創(chuàng)建狀態(tài)

如果進(jìn)程所需的資源尚不能得到滿足，比如系統(tǒng)尚無(wú)足夠的內(nèi)存使進(jìn)程無(wú)法裝入其中，此時(shí)創(chuàng)建工作尚未完成，進(jìn)程不能被調(diào)度運(yùn)行，于是把此時(shí)進(jìn)程所處的狀態(tài)稱(chēng)為創(chuàng)建狀態(tài)。進(jìn)程創(chuàng)建過(guò)程創(chuàng)建進(jìn)程請(qǐng)求調(diào)用創(chuàng)建進(jìn)程原語(yǔ)Creat()申請(qǐng)PCB、分配進(jìn)程ID為進(jìn)程分配資源初始化PCB將進(jìn)程放進(jìn)Ready隊(duì)列產(chǎn)生新進(jìn)程事件：用戶(hù)登錄：當(dāng)合法用戶(hù)登錄時(shí)作業(yè)調(diào)度：批處理系統(tǒng)，把一個(gè)作業(yè)調(diào)度執(zhí)行時(shí)。提供服務(wù)：當(dāng)系統(tǒng)收到服務(wù)請(qǐng)求時(shí)。應(yīng)用請(qǐng)求：當(dāng)應(yīng)用本身需要并發(fā)進(jìn)程時(shí)。為新進(jìn)程分配一個(gè)唯一的進(jìn)程ID,并申請(qǐng)一個(gè)空白的PCB。為進(jìn)程的程序代碼、數(shù)據(jù)用戶(hù)棧分配內(nèi)存空間。（1）將系統(tǒng)分配的進(jìn)程ID、父進(jìn)程ID寫(xiě)入PCB。（2）將程序計(jì)數(shù)器指向程序的入口地址、棧指針指向棧頂。（3）設(shè)置進(jìn)程狀態(tài)、優(yōu)先級(jí)等。

2)終止?fàn)顟B(tài)

進(jìn)程的終止也要通過(guò)兩個(gè)步驟：

首先，是等待操作系統(tǒng)進(jìn)行善后處理，

最后將其PCB清零，并將PCB空間返還系統(tǒng)。

當(dāng)一個(gè)進(jìn)程到達(dá)了自然結(jié)束點(diǎn)，或是出現(xiàn)了無(wú)法克服的錯(cuò)誤，或是被操作系統(tǒng)所