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

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

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

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

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

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

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

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

必須完成。此時稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。

在前趨圖中，把沒有前趨的結(jié)點稱為初始結(jié)點(InitialNode)，把沒有后繼的結(jié)點稱為終止結(jié)點(FinalNode)。此外，每個結(jié)點還具有一個重量(Weight)，用于表示該結(jié)點所含有的程序量或程序的執(zhí)行時間。

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)的，否則必然會產(chǎn)生不可能實現(xiàn)的前趨關(guān)系。

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

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

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

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

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

S1:a:=x+y；

S2:b:=a-5；

S3:c:=b+1；

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

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

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

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

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

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

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

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í)行，因為它們彼此互不依賴。

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

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

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

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

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

程序A：

N=N+1;程序B：

print(N);N=0;假定某時刻：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舉例：計算交通流量觀察者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報告者beginrepeatdelayatimePrintN；

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

2.2進?程?的?描?述?

2.2.1進程的定義和特征

1.進程的定義

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

利用PCB來描述進程的基本情況和活動過程，來控制和管理進程。

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

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

撤銷進程，實質(zhì)上就是撤銷進程的PCB其中較典型的定義有：

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

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

(3)進程是具有獨立功能的程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。在引入了進程實體的概念后，我們可以把傳統(tǒng)OS中的進程定義為：“進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位”。18進程通常由三部分組成：程序、數(shù)據(jù)和進程控制塊PCB

。創(chuàng)建進程，實質(zhì)上就是創(chuàng)建進程的PCB；撤銷進程，實質(zhì)上就是撤銷進程的PCB

程序

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

程

序

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

數(shù)據(jù)PCB2

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

2.進程的特征

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

(1)動態(tài)性。

(2)并發(fā)性。

(3)獨立性。

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

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

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

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

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

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

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

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

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

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

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

3.創(chuàng)建狀態(tài)和終止狀態(tài)

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

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

創(chuàng)建一個進程一般要通過多個步驟：

首先由進程申請一個空白PCB，并向PCB中填寫用于控制和管理進程的信息；

然后為該進程分配運行時所必須的資源；

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

3.創(chuàng)建狀態(tài)和終止狀態(tài)

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

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

2)終止狀態(tài)

進程的終止也要通過兩個步驟：

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

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

當一個進程到達了自然結(jié)束點，或是出現(xiàn)了無法克服的錯誤，或是被操作系統(tǒng)所