3.1進程的引入3.2進程的描述3.3進程控制3.4進程控制的實現(xiàn)舉例習題3.1.1程序的順序執(zhí)行

1．程序順序執(zhí)行

一個程序通常由若干個程序段組成，它們必須按照某種先后次序來執(zhí)行，僅當前一操作執(zhí)行完后，才能執(zhí)行后續(xù)操作，這類執(zhí)行過程就是程序的順序執(zhí)行。例如，在處理一個作業(yè)時，總是先輸入用戶的程序和數(shù)據(jù)，然后進行計算，最后將所得的結(jié)果打印出來。若用結(jié)點代表各個程序段的操作，其中I代表輸入操作，C代表計算操作，P代表打印操作，則上述程序段的執(zhí)行過程如圖3-1所示。對一個作業(yè)的輸入、計算和打印三個操作，必須順序執(zhí)行。3.1進?程?的?引?入圖3-1程序的順序執(zhí)行

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

1)順序性

當順序程序在處理機上執(zhí)行時，處理機的操作是嚴格按照程序所規(guī)定的順序執(zhí)行的，即只有前一操作結(jié)束后，才能執(zhí)行后續(xù)操作。

2)封閉性

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

3)可再現(xiàn)性

只要程序執(zhí)行時的環(huán)境和初始條件相同，當程序多次重復執(zhí)行時，不論它是從頭到尾不停頓地執(zhí)行，還是“停停走走”地執(zhí)行，都將獲得相同的結(jié)果。3.1.2程序的并發(fā)執(zhí)行

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

如圖3-1所示的輸入操作、計算操作和打印操作是一個作業(yè)的三個處理過程，邏輯上要求順序執(zhí)行。但實際上，實現(xiàn)上述三個步驟的輸入機、中央處理機和打印機這三個物理部件是可以同時操作的。由于作業(yè)本身的特點，這三個作業(yè)步驟只能順序執(zhí)行。當有一批作業(yè)進行處理時，情況就不同了。輸入了作業(yè)1的程序和數(shù)據(jù)后，在對該作業(yè)進行計算的同時，可輸入作業(yè)2的程序和數(shù)據(jù)，即作業(yè)1的計算操作和作業(yè)2的輸入操作同時進行。如圖3-2所示，說明了系統(tǒng)對一批作業(yè)進行處理時，各程序段執(zhí)行的先后順序。圖3-2程序的并發(fā)執(zhí)行從圖3-2中可以看出，有的程序執(zhí)行是有先后順序的，如：I1先于I2和C1，C1先于P1和C2等。有的程序段可以并發(fā)執(zhí)行，如：I2和C1，C2和P1。所以，對于并發(fā)執(zhí)行的程序來說，它有時處于執(zhí)行狀態(tài)，但由于并發(fā)程序之間的相互制約關(guān)系，有時因需要的某種資源得不到滿足，處于暫停狀態(tài)。因此，并發(fā)程序執(zhí)行時就是像這樣停停走走向前推進的。為了能正確反映程序執(zhí)行時的活動規(guī)律和狀態(tài)變化，要引入一個新的概念——進程，以便從變化的角度動態(tài)地描述程序的執(zhí)行。

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

1)間斷性

程序在并發(fā)執(zhí)行時，由于它們共享資源或為完成同一項任務而相互合作，致使在并發(fā)程序之間形成了相互制約的關(guān)系。例如，圖3-2所示的I、C和P是三個相互合作的程序，當計算程序完成Ci-1的計算后，如果輸入程序I但計算程序尚未完成Ii的處理，則計算程序就無法進行Ci的處理，致使計算程序暫停運行。又如，打印程序完成了Pi的打印后，若計算程序尚未完成對Ci-1的計算，則打印程序就無法對Ci-1的處理結(jié)果進行打印。一旦使某程序暫停的因素消失，計算程序便可恢復執(zhí)行對Ci進行處理。簡言之，相互制約將導致并發(fā)程序具有“執(zhí)行－暫停執(zhí)行－執(zhí)行”這種間斷性的活動規(guī)律。

2)失去封閉性

程序在并發(fā)執(zhí)行時，是多個程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運行已失去了封閉性。這樣，某程序在執(zhí)行時，必然會受到其他程序的影響。例如，當處理機資源被其他程序占有時，某程序必須等待。

3)不可再現(xiàn)性

程序在并發(fā)執(zhí)行時，由于失去了封閉性，也將導致失去其可再現(xiàn)性。現(xiàn)以兩個并發(fā)的循環(huán)程序共用一個公共變量N來說明這個問題。設程序A每執(zhí)行一次都要做N=N+1操作，程序B每隔一定時間打印出N值，并將它重新置為0，變量N的初值為N0。這兩個程序如圖3-3所示。圖3-3兩個程序并發(fā)執(zhí)行實例由于程序A和程序B的執(zhí)行都以各自獨立的速度向前推進，故程序A與程序B之間對變量N的操作會有如下三種可能：

(1)程序A的N=N+1操作，在程序B的PRINT(N)和N=0操作之前，如圖3-4所示。

這種情況下打印機打印出來的N值為“N0+1”。

(2)程序A的N=N+1操作，在程序B的PRINT(N)和N?=?0操作之間，如圖3-5所示。

這種情況下打印機打印出來的N值為“N0”。

(3)程序A的N=N+1操作，在程序B的PRINT(N)和N=0操作之后，如圖3-6所示。圖3-4第一種執(zhí)行情況圖3-6第三種執(zhí)行情況這種情況下打印機打印出來的N值為“N0”。

之所以出現(xiàn)上述錯誤，是因為它們公用了一個公共變量N，而又沒有采取恰當?shù)拇胧?。這個例子說明并發(fā)程序的執(zhí)行結(jié)果與執(zhí)行速度有關(guān)，也就是說，并發(fā)程序已喪失了順序程序所具有的封閉性和可再現(xiàn)性的特征。3.2.1進程的定義

進程的概念是在20世紀60年代初期，首先由美國麻省理工學院的MULTICS和IBM公司的CTSS/360系統(tǒng)引入的，其后又有許多人從不同的角度給進程下過各種定義。其中較能反映進程實質(zhì)的定義有：

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

(2)進程可定義為一個數(shù)據(jù)結(jié)構(gòu)及能在其上進行操作的一個程序。

3.2進?程?的?描?述

(3)進程是一個程序與其數(shù)據(jù)一起通過處理機的執(zhí)行所發(fā)生的活動。

(4)進程是程序在一個數(shù)據(jù)集合上的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。

據(jù)此，可以把進程定義為：可并發(fā)執(zhí)行的程序在處理機上的執(zhí)行過程。

顯然，進程和程序是兩個截然不同的概念。程序是指令的有序集合，本身沒有任何運行的含義。而進程是程序在處理機上的一次執(zhí)行過程，是一個動態(tài)的概念，進程是有生命期的，能夠動態(tài)地產(chǎn)生和消亡。其動態(tài)性還表現(xiàn)為：“進程由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，因得不到資源而暫停，由撤銷而消亡”。程序和進程是既有區(qū)別又有聯(lián)系的兩個概念，它們的區(qū)別如下：

(1)程序是一個靜態(tài)的概念，而進程是一個動態(tài)的概念。

(2)程序的存在是永久的，而進程是有生命期的。

(3)進程是一個能獨立運行的基本單位，是系統(tǒng)資源分配和調(diào)度的基本單位。

(4)進程與程序之間不是一一對應的，即同一程序同時運行于若干不同的數(shù)據(jù)集合上，屬于若干個不同的進程。3.2.2進程的基本狀態(tài)

前面已經(jīng)介紹過，進程并不是一口氣運行到底的，它與并發(fā)執(zhí)行的其他進程的執(zhí)行是相互制約的。進程有時處于運行狀態(tài)，有時又由于某種原因而暫停，等到使它暫停的原因消失后，它又準備運行了，所以進程在運行中不斷地改變其運行狀態(tài)。一個進程在活動期間至少具備以下三種狀態(tài)：就緒狀態(tài)：當進程已經(jīng)獲得除處理機以外的所有資源后，一旦獲得CPU，就可以立即運行，這時的進程狀態(tài)稱為就緒狀態(tài)。在一個系統(tǒng)中，可以有多個進程同時處于就緒狀態(tài)，通常把這些進程排成一個或多個隊列，稱為就緒隊列。

運行狀態(tài)：進程已獲得處理機，它的程序正在執(zhí)行，這時的進程狀態(tài)稱為運行狀態(tài)。在單處理機系統(tǒng)中，只能有一個進程處于運行狀態(tài)。只有在多處理機系統(tǒng)，才存在運行隊列。等待狀態(tài)：進程因發(fā)生某事件(如請求I/O等)而暫時停止運行，即使給它CPU也無法運行，這時的進程狀態(tài)稱為等待狀態(tài)，也稱為阻塞狀態(tài)。把處于等待狀態(tài)的進程排成一個隊列，稱為等待隊列。有時也按阻塞的原因不同排成多個隊列。

進程并非固定地處于某個狀態(tài)，它將隨著程序的執(zhí)行和外界條件的變化而發(fā)生變化，可以用進程狀態(tài)變遷圖(如圖3-7所示)來說明系統(tǒng)中進程的狀態(tài)和這些狀態(tài)之間變遷的原因。在圖3-7中，以結(jié)點表示進程的狀態(tài)，以箭頭表示狀態(tài)的變化。圖3-7進程狀態(tài)變遷圖從圖3-7中可以看出，處于就緒狀態(tài)的進程，當進程調(diào)度程序為它分配了處理機后，該進程由就緒狀態(tài)變?yōu)檫\行狀態(tài)；正在運行的進程因發(fā)生某事件而無法執(zhí)行，則進程將由運行狀態(tài)變?yōu)樽枞麪顟B(tài)；處于阻塞狀態(tài)的進程，若其等待的事件已經(jīng)發(fā)生，則由阻塞狀態(tài)變?yōu)榫途w狀態(tài)；正在執(zhí)行的進程，如因時間片用完而被暫停執(zhí)行，該進程由執(zhí)行狀態(tài)轉(zhuǎn)為就緒狀態(tài)。3.2.3進程的描述

當程序并發(fā)執(zhí)行時，由于并發(fā)程序之間的相互制約關(guān)系，造成程序在執(zhí)行過程中受阻而暫停，如果系統(tǒng)無法保留該程序的現(xiàn)場，也就意味著無法恢復該程序的現(xiàn)場以繼續(xù)執(zhí)行。為了使程序在多道程序設計環(huán)境下能并發(fā)執(zhí)行，并能對并發(fā)執(zhí)行的程序加以控制和描述，專門配置了稱為“進程控制塊”的數(shù)據(jù)結(jié)構(gòu)。

1.進程控制塊

為了描述和控制進程的運行，系統(tǒng)為每個進程定義了一個數(shù)據(jù)結(jié)構(gòu)——進程控制塊(PCB，ProcessControlBlock)。所謂系統(tǒng)創(chuàng)建一個進程，就是由系統(tǒng)為某個程序設置一個PCB，用于對該進程進行控制和管理。進程執(zhí)行完成時，由系統(tǒng)收回其PCB，該進程便消亡了。

對于不同的操作系統(tǒng)來說，進程PCB所包含的內(nèi)容會有些不同，但通常會包括表3-1所示的內(nèi)容。表3-1進程PCB結(jié)構(gòu)對PCB所包含的內(nèi)容具體說明如下：

(1)進程標識符(NAME)：每個進程都必須有唯一的標識符，以區(qū)別于系統(tǒng)內(nèi)的其他進程。在進程創(chuàng)建時，由創(chuàng)建者給出進程的標識符。

(2)進程當前狀態(tài)(STATUS)：說明本進程目前處于何種狀態(tài)，即運行、就緒或等待，以作為進程調(diào)度程序分配處理機的依據(jù)。

(3)進程隊列指針(NEXT)：用于記錄處于同一狀態(tài)下的下一個PCB的地址，以此可以將同一狀態(tài)的所有進程鏈接起來。

(4)總鏈指針(ALL-Q-NEXT)：當系統(tǒng)中存在大量進程時，所有的進程根據(jù)自己的狀態(tài)分別處于相應的隊列中，這便于對進程實施調(diào)度控制。當進行某些管理功能，如執(zhí)行創(chuàng)建新進程時，就感到系統(tǒng)具有所有進程的總鏈將是十分方便的。因為進程的標識符必須是唯一的，為了避免重名，必須先檢查系統(tǒng)中已有的進程名，如果在各個不同狀態(tài)的隊列中進行查詢是非常麻煩的，所以，通過提供一個總鏈指針來方便查詢。PCB中的該項內(nèi)容是存放總鏈隊列中下一個PCB的地址。

(5)程序開始地址(START-ADDR)：該進程的程序從此地址開始執(zhí)行。

(6)進程優(yōu)先級(PRIORITY)：反映進程要求CPU的緊迫程度，優(yōu)先級高的進程可以優(yōu)先獲得CPU。

(7)CPU現(xiàn)場保護(CPUSTATUS)：當進程因某種原因釋放處理機時，CPU現(xiàn)場信息被保存在PCB的該區(qū)域中，以便在進程重新獲得處理機后繼續(xù)執(zhí)行。

(8)通信信息(COMMUNICATION-INFORMATION)：記錄該進程在執(zhí)行過程中與別的進程所發(fā)生的信息交換情況。

(9)進程家族(PROCESS-FAMILY)：有的系統(tǒng)允許進程創(chuàng)建子進程，從而形成一個進程家族樹。在PCB中必須指明進程與家族的關(guān)系。

(10)占有資源清單(OWN-RESOURCE)：列出進程所需資源及當前已分配資源清單。

2.進程的組成

從結(jié)構(gòu)上講，每個進程都是由程序、數(shù)據(jù)和一個進程控制塊PCB組成的，如圖3-8所示。進程的程序部分描述了進程所要完成的功能。數(shù)據(jù)集合是程序在執(zhí)行時所需要的數(shù)據(jù)和工作區(qū)。這兩部分是進程存在的基礎(chǔ)。PCB是進程存在的標識。圖3-8進程的組成3.2.4進程PCB的組織方式

在一個系統(tǒng)中，通常存在許多PCB。為能對它們實現(xiàn)有效的管理，應采用適當?shù)姆绞綄⑺鼈兘M織起來。目前常用的組織方式有鏈接方式和索引方式兩種。

1．鏈接方式

把具有相同狀態(tài)的PCB用其中的鏈接字鏈接成一個隊列，這樣，可形成就緒隊列、若干個阻塞隊列和空白隊列等。對其中的就緒隊列常按進程優(yōu)先權(quán)的大小排列，把優(yōu)先權(quán)高的進程的PCB排在隊列前面。此外，也可根據(jù)阻塞原因的不同，把處于阻塞狀態(tài)的進程的PCB排成等待I/O操作完成隊列、等待分配內(nèi)存隊列。圖3-9所示是一種鏈接隊列的組織

方式。圖3-9PCB鏈接隊列示意圖

2．索引方式

系統(tǒng)根據(jù)所有進程的狀態(tài)，建立幾張索引表。例如，就緒索引表、阻塞索引表等。并把各索引表在內(nèi)存的首地址記錄于內(nèi)存中的一些專用單元中。在每個索引表的表目中，記錄具有相應狀態(tài)的某個PCB在PCB表中的地址。按索引方式組織PCB，如圖3-10所示。圖3-10按索引方式組織PCB3.3.1進程創(chuàng)建

進程創(chuàng)建是由創(chuàng)建原語實現(xiàn)的。當需要進程時，就可以建立一個新進程。被創(chuàng)建的進程稱為子進程，創(chuàng)建者稱為父進程。

創(chuàng)建原語的主要功能是為被創(chuàng)建進程形成一個PCB，并填入相應的初始值，同時將PCB插入就緒隊列，返回一個進程的標識號(PID)。該原語的實現(xiàn)過程如圖3-11所示。3.3進程控制圖3-11進程創(chuàng)建算法流程圖3.3.2進程撤銷

進程撤銷是由撤銷原語實現(xiàn)的。一個進程在完成其任務后，應予以撤銷，以便及時釋放所占有的各類資源。

撤銷原語的主要功能是收回被撤銷進程占用的所有資源，并撤銷它的PCB，從總鏈隊列中摘除它，然后轉(zhuǎn)進程調(diào)度程序。該原語實現(xiàn)過程如圖3-12所示。圖3-12

進程撤銷算法流程圖3.3.3進程的阻塞與喚醒

阻塞原語的作用是將進程由執(zhí)行狀態(tài)轉(zhuǎn)為阻塞狀態(tài)，而喚醒原語的作用是將進程由阻塞狀態(tài)轉(zhuǎn)為就緒狀態(tài)。

當一個進程所期待的某一事件尚未出現(xiàn)時，該進程調(diào)用阻塞原語將自己阻塞起來。阻塞原語在阻塞一個進程時，由于該進程正處于執(zhí)行狀態(tài)，應先中斷處理機和保存該進程的CPU現(xiàn)場，然后將該進程插入到等待該事件的等待隊列中，再從就緒隊列中選擇一個新的進程投入運行。該原語實現(xiàn)過程如圖3-13所示。進程由運行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)是由于進程必須等待某一事件的發(fā)生，因此處于等待狀態(tài)的進程是絕對不可能叫醒自己的。當該進程期待的事件出現(xiàn)時，由發(fā)現(xiàn)者進程調(diào)用喚醒原語將阻塞的進程喚醒，使其進入就緒狀態(tài)。發(fā)現(xiàn)者進程和被喚醒進程是合作的并發(fā)進程。喚醒原語的功能是：當進程等待的事件發(fā)生時，喚醒該進程。該原語實現(xiàn)過程如圖3-14所示。圖3-13進程阻塞算法流程圖圖3-14進程喚醒算法流程圖

1．進程創(chuàng)建

Linux系統(tǒng)中，除初始化進程外，其他進程都是通過fork()系統(tǒng)調(diào)用建立的。使用fork()的進程為父進程，通過fork()創(chuàng)建的新進程為子進程。使用fork()系統(tǒng)調(diào)用后，對父進程返回子進程的進程號