第二章她理機(jī)碉念1

第三章處理初調(diào)度

2.1進(jìn)程出

習(xí)題：

2.2進(jìn)程搭1：題集P52：一、1,2,3,

21,22；4,5,6,P74：1,2,3,4,7,8；

2.3進(jìn)程非補(bǔ)充作業(yè)：

(1)假定一個處理器正在執(zhí)行兩道作業(yè)，一道，

2.4中斷投計算為主，另一道以輸入輸出為主，你將怎村

賦予它們占有處理器的優(yōu)先級？為什么？

(2)假定一個處理器正在執(zhí)行三道作業(yè)，一道以

計算為主，第二道以輸入輸出為主，第三道為

計算與輸入輸出均勻。應(yīng)該如何賦予它們占有

處理器的優(yōu)先級使得系統(tǒng)效率較高？

第二章處理機(jī)碉沒

2.1進(jìn)程的基本概念

2.1.1程序的順序執(zhí)行及其特征

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

僅當(dāng)前一操作（程序段）執(zhí)行完后，才能執(zhí)行后繼操作。

例如，在進(jìn)行計算時，總須先輸入用戶的程序和數(shù)據(jù)，然后

進(jìn)行計算，最后才能打印計算結(jié)果。

Sfa:=x+y;

S2：b:=a-5;

S3:c:=b+l;

第二章處理機(jī)碉念3

SSs

P2123

(a)程序的順序執(zhí)行(6)三條語句的順序執(zhí)行

圖2-1程序的順序執(zhí)行

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

⑴順序性:

(2)封閉性:

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

幸”史嬴I/—4

2.1.2前趨圖

前趨圖(PrecedenceGraph)是一個有向無循環(huán)圖，記為

DAG(DirectedAcyclicGraph),用于描述進(jìn)程之間執(zhí)行的前后關(guān)

系。圖中的每個結(jié)點(diǎn)可用于描述一個程序段或進(jìn)程，乃至一條語

句；結(jié)點(diǎn)間的有向邊則用于表示兩個結(jié)點(diǎn)之間存在的偏序

(PartialOrder)或前趨關(guān)系(PrecedenceRelation)''一〃。

如果

—>={(Pi9PjJ)|PjmustcompletebeforeP：maystart),(Pi，

耳)￡一,可寫成巴一耳，稱Pj是4的直接前趨，而稱Pj是B的直接

后繼。在前趨圖中，把沒有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)Qnitial

Node),把沒有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)(FinalNode)。

例如，圖2?1中存在這樣的前趨關(guān)系L-G-Pj和Si—S2一§3

第二章處理機(jī)碉念5

每個結(jié)點(diǎn)還具有一個重量(Weight),用于表示該結(jié)點(diǎn)

所含有的程序量或結(jié)點(diǎn)的執(zhí)行時間。

(。)具有九個結(jié)點(diǎn)的前趨圖⑸具有循環(huán)的前趨圖

圖2-2前趨圖

Mb上章”機(jī)倜盛［6

對于圖2?25）所示的前趨圖，存在下述前趨關(guān)系:

PlfP1-P3,P1-P”P2-P5,P3m6,Pf，

P5一「8,「6一「8,P7一P9,Pg一「9

或表不為:

P={PpP"P3,P4,「5,P?P7,P8,PJ

>={(Pl,P2),(P19P3),(Pi,PJ&P5),(P3,P5),(P4,P6)，(P”P7)，

(P5,P8)5(P6,P8)9(P79P9),(P89P9)}

應(yīng)當(dāng)注意，前趨圖中必須不存在循環(huán)，但在圖2.2@）中卻有著

下述的前趨關(guān)系:

S2Ts3,S3Ts2

第二章處理機(jī)倜念7

2.1.3程序的并發(fā)執(zhí)行及其特征

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

三事上章處理機(jī)調(diào)次—V—8

在該例中存在下述前趨關(guān)系：

ILG，1一5+1,Cj-Pi,Cj-Ci+i，Pj-Pj+i

而1+1和Ci及1是重迭的，亦即在Pi/和Ci以及Ii+1之間，可以并

發(fā)執(zhí)行。對于具有下述四條語句的程序段：

Si：a：=x+2

s2：b:=y+4

S3:c:=a+b

S4:d:=c+b

圖2-4四條語句的前趨關(guān)系

當(dāng)U第e辛處理機(jī)癡盛；一七10

27i澤笄娶薪行時的特征一

1）間斷性

2）失去封閉性

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

例如，有兩個循環(huán)程序A和B,它們共享一個變量N。程

序A每執(zhí)行一次時，都要做N：=N+1操作；程序B每執(zhí)行一次

時，都要執(zhí)行Print（N）操作，然后再將N置成“0〃。程序A和

B以不同的速度運(yùn)行。

(1)N：=N+1在Print(N)和N：=0之前,此時得到的N值分

另U為n+1,n+1,0o

(2)N：=N+1在Print(N)和N：=0之后,此時得到的N值分

別為n,0,1。

(3)N：=N+1在Print(N)和N：=0之間,此時得到的N值分

別為n,n+1,0o

工1^^第三章處理枇碉4YH

2.1.4進(jìn)程的直寫狀態(tài)

進(jìn)程的定義：

進(jìn)程是程序在一個數(shù)據(jù)集合上的一次運(yùn)行過程。

進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單位。

它由一組機(jī)器指令數(shù)據(jù)堆棧等組成的動態(tài)實(shí)體。

進(jìn)程和并發(fā)是現(xiàn)代操作系統(tǒng)最重要的基本概念。

也是操作系統(tǒng)運(yùn)行的基礎(chǔ)。

二L眩/A心理嬴I.―—―一12

進(jìn)程的特征：一一-

1、動態(tài)特征?進(jìn)程具有生命期:

2、并發(fā)特征由創(chuàng)建而產(chǎn)生

3、獨(dú)立特征由調(diào)度而運(yùn)行

由得不到資源而阻塞

4、結(jié)構(gòu)特征

由撤銷而消亡

5、異步特征

進(jìn)程最具特性的特征。

臺

'若h攸二專辦理機(jī)碉波.二二13

進(jìn)程的特征：-一-

1、動態(tài)特征引入并發(fā)程序，使其含義發(fā)生變化，從

而程序本身已不適應(yīng)并發(fā)環(huán)境。

2、并發(fā)特征

進(jìn)程的并發(fā)特性是其第二基本特征，而

3、獨(dú)立特征對沒有為之建立進(jìn)程的程序，已無并發(fā)

可言。

4、結(jié)構(gòu)特征

5、異步特征

臺

健工淹心理機(jī)碉波.二:14

進(jìn)程的特征：一一-

1、動態(tài)特征進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的一

個基本單位。

2、并發(fā)特征

3、獨(dú)立特征<

4、結(jié)構(gòu)特征

5、異步特征

臺

_珠二菱心理機(jī)倜主———;15

進(jìn)程的特征：—一一一

結(jié)構(gòu)特征也稱靜態(tài)特征。

為描述進(jìn)程的變化運(yùn)動過程，W:統(tǒng)為

每一個進(jìn)程配置一個進(jìn)程控制鄉(xiāng)tPCBo

靜態(tài)地看或從結(jié)構(gòu)上看，進(jìn)程成E由程

序段，數(shù)據(jù)集合以及PCB三部分組成。

［一般把進(jìn)程的1PCB

組成結(jié)構(gòu)稱為程序段」數(shù)據(jù)集合

進(jìn)程映象。如

圖3.4：圖3.4：進(jìn)程映象

像二者心理機(jī)碉念16

進(jìn)程的特征：-

1、動態(tài)特征各進(jìn)程按其各自獨(dú)立的，不可預(yù)知的速

度向前推進(jìn)，當(dāng)然對系統(tǒng)來說，需提供

2、并發(fā)特征某些設(shè)施來協(xié)調(diào)它們。

3、獨(dú)立特征

4、結(jié)構(gòu)特征

5、異步特征

建三幸處理機(jī)碉/'f二

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

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

1）就緒（Ready）狀態(tài)

2）執(zhí)行狀態(tài)（也叫運(yùn)行狀態(tài)）

3）阻塞狀態(tài)

18

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

1.就緒狀態(tài)2.運(yùn)行狀態(tài)3.阻塞狀態(tài)

(Ready)(Running)(Blocked)

進(jìn)程已得到必要的資源，

唯缺CPU而使其處于等待

CPU狀態(tài),一旦獲得CPU

便可立即執(zhí)行。真可謂

萬事俱備只欠東風(fēng)——

只欠CPU。

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

1.就緒狀態(tài)2.運(yùn)行狀態(tài)3.阻塞狀態(tài)

(Ready)(Running)(Blocked)

進(jìn)程獲得所需的資源并獲

得CPU,能夠真正在CPU上

運(yùn)行他的程序段。

多機(jī)系統(tǒng)中，可以有多個

進(jìn)程處于運(yùn)行狀態(tài)；

單機(jī)系統(tǒng)中，在任何時候

獲得資源，事件到來都僅有一個進(jìn)程處于運(yùn)行

圖3-5：進(jìn)程的基本狀態(tài)轉(zhuǎn)換狀態(tài)，而且要盡量保證總

有一個進(jìn)程處于運(yùn)行狀態(tài)。

20

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

1.就緒狀態(tài)2.運(yùn)行狀態(tài)3.阻塞狀態(tài)

(Ready)(Running)(Blocked)

時運(yùn)行阻塞狀態(tài)也稱為等待

請求資源等待

鐘(wait)態(tài)。

某一事件的

進(jìn)

到來在運(yùn)行過程中，因等待

某一事件而暫時無法運(yùn)

就緒阻塞行，或者說進(jìn)程運(yùn)行受

到了阻塞，此時即使它

獲得資源，事件到來分得CPU也無法繼續(xù)進(jìn)

圖3-5：進(jìn)程的基本狀態(tài)轉(zhuǎn)換行，因而只能處于暫停

狀態(tài)。

11

維士普“卜歡加楣春21

有些操作系統(tǒng)，將進(jìn)程狀態(tài)分為五種：就緒狀態(tài)、運(yùn)行狀態(tài)、

阻塞狀態(tài)

4.新狀態(tài)5.終止?fàn)顟B(tài)

這是一個進(jìn)程剛剛

建立，但還未將它

送入就緒隊列時的

狀態(tài)。

站已普。披七、4國備22

有些操作系統(tǒng)，修進(jìn)程狀態(tài)分為五種：就緒狀態(tài)、運(yùn)行狀態(tài)、

阻塞狀態(tài)

4.新狀態(tài)5.終止?fàn)顟B(tài)

當(dāng)一個進(jìn)程已經(jīng)正

常結(jié)束或異常結(jié)束,

操作系統(tǒng)已將它從

就緒隊列中移出，

但尚未將它撤消時

的狀態(tài)。

--出■在ALQG。__23

為了便于研究進(jìn)程的執(zhí)行情況或?qū)M(jìn)程進(jìn)行修改，希望能夠

人為地使正在執(zhí)行的進(jìn)程或未執(zhí)行的進(jìn)程處于靜止?fàn)顟B(tài)，所

以增加了掛起狀態(tài)。

正在執(zhí)行的進(jìn)程掛起后便停止執(zhí)行，也不參與調(diào)度,

即不再執(zhí)行。

掛起具

圖

運(yùn)行有

掛

起

3.進(jìn)6

狀

程

態(tài)

、r米的

激活的

活動

靜止、活動各

進(jìn)

就財就緒阻塞

種

獲得資源或等程

i1掛起

狀

待的事件到來狀

態(tài)

態(tài)

獲得資源或等待的事件到來靜止圖

阻塞

為了便于研究進(jìn)程的執(zhí)行情況或?qū)M(jìn)程進(jìn)行修改，希望能夠人

為地使正在執(zhí)行的進(jìn)程或未執(zhí)行的進(jìn)程處于靜止?fàn)顟B(tài)，所以增

加了掛起狀態(tài)。

靜止就緒活動就緒靜止阻塞活動阻塞

正在執(zhí)行的進(jìn)程和就緒進(jìn)程被掛起后處于靜止?fàn)顟B(tài)。

具

圖

有

掛

起3.6

進(jìn)

狀

程

態(tài)

的

的

各

進(jìn)

種

程

狀

狀

態(tài)

態(tài)

圖

>5

為了便于研究進(jìn)程的執(zhí)行情況或?qū)M(jìn)程進(jìn)行修改，希望能夠人

為地使正在執(zhí)行的進(jìn)程或未執(zhí)行的進(jìn)程處于靜止?fàn)顟B(tài)，所以增

加了掛起狀態(tài)。

靜止就緒活動就緒靜止阻塞活動阻塞

未被掛起的就緒狀態(tài)處于活動就緒狀態(tài)。

掛起具

圖

運(yùn)行有

掛

起3.6

進(jìn)

狀

程

態(tài)

的

激活的

靜止活動各

進(jìn)

就一逆紛獲得資源或等、阻塞

種

掛起程

狀

待的事件到來狀

態(tài)

態(tài)

獲得資源或等待的事件到來靜止圖

阻塞

為了便于研究進(jìn)程的執(zhí)行情況或?qū)M(jìn)程進(jìn)行修改，希望能夠人

為地使正在執(zhí)行的進(jìn)程或未執(zhí)行的進(jìn)程處于靜止?fàn)顟B(tài)，所以增

加了掛起狀態(tài)。

靜止就緒活動就緒靜止阻塞活動阻塞

被掛起的阻塞進(jìn)程處于靜止阻塞狀態(tài)。

掛起具

圖

運(yùn)行有

掛

起3.6

進(jìn)

狀

程

態(tài)

的

激活的

靜止〉

舌動活動各

X進(jìn)

就緒＞一述鄲,獲得資源或等、阻塞

種

掛起程

狀

待的事件到來狀

態(tài)

態(tài)

獲得資源或等待的事件到來靜止圖

阻塞

>7

為了便于研究進(jìn)程的執(zhí)行情況或?qū)M(jìn)程進(jìn)行修改，希望能夠人

為地使正在執(zhí)行的進(jìn)程或未執(zhí)行的進(jìn)程處于靜止?fàn)顟B(tài)，所以增

加了掛起狀態(tài)。

靜止就緒活動就緒靜止阻塞活動阻塞

未被掛起的阻塞進(jìn)程處于活動阻塞狀態(tài)。

具

圖

有

掛

起3.6

進(jìn)

狀

程

態(tài)

的

的

各

進(jìn)

種

程

狀

狀

態(tài)

態(tài)

圖

?夫結(jié)，嵬板上；陽玄_________________________________________28

當(dāng)一個作業(yè)進(jìn)入系統(tǒng)運(yùn)行時，操作系統(tǒng)為之建立一個與之對

應(yīng)的進(jìn)程，并修其進(jìn)程控制塊放入就緒隊列之尾。

進(jìn)程狀態(tài)隨著自身的推進(jìn)和外界條件的變化而變化。

就緒->運(yùn)行運(yùn)行->就緒運(yùn)行->阻塞阻塞->就緒

隨著進(jìn)程調(diào)度程序按

進(jìn)程調(diào)度算法的一次

次調(diào)度，該進(jìn)程終于

在某一時刻獲得CPU而

處于運(yùn)行狀態(tài)。

答案：不會！肯定

不會立即引起其它

的狀態(tài)轉(zhuǎn)換。I

?安結(jié)，徐披上；陽玄_________________________________________29

當(dāng)一個作業(yè)進(jìn)入系統(tǒng)運(yùn)行時，操作系統(tǒng)為之建立一個與之對

應(yīng)的進(jìn)程，并修其進(jìn)程控制塊放入就緒隊列之尾。

進(jìn)程狀態(tài)隨著自身的推進(jìn)和外界條件的變化而變化。

就緒->運(yùn)行運(yùn)行->就緒運(yùn)行->阻塞阻塞->就緒

運(yùn)行進(jìn)程分配的時間片

用完而發(fā)生時鐘中斷；

進(jìn)入就緒隊列的進(jìn)程，

其優(yōu)先級高于運(yùn)行進(jìn)程

的優(yōu)先級而搶上CPU一

答案：會！必然會立

即引起就緒到運(yùn)行的

狀態(tài)轉(zhuǎn)換。

?夫結(jié)，嵬板上；陽玄__________________________________________30

當(dāng)一個作業(yè)進(jìn)入系統(tǒng)運(yùn)行時，操作系統(tǒng)為之建立一個與之對

應(yīng)的進(jìn)程，并修其進(jìn)程控制塊放入就緒隊列之尾。

進(jìn)程狀態(tài)隨著自身的推進(jìn)和外界條件的變化而變化。

就緒->運(yùn)行運(yùn)行->就緒運(yùn)行->阻塞阻塞->就緒

一個正處于運(yùn)行狀態(tài)

的進(jìn)程，若因?yàn)榈却?/p>

輸入輸出或者請求主

存儲器、輔助存儲器

等資源而被阻塞。

答案：可能會！

當(dāng)就緒隊列非空

時，會立即引起|

就緒到運(yùn)行的狀|LZJ

31

當(dāng)一個作業(yè)進(jìn)入系統(tǒng)運(yùn)行時，操作系統(tǒng)為之建立一個與之對

應(yīng)的進(jìn)程，并修其進(jìn)程控制塊放入就緒隊列之尾。

進(jìn)程狀態(tài)隨著自身的推進(jìn)和外界條件的變化而變化。

就緒-A運(yùn)行運(yùn)行->就緒運(yùn)行->阻塞阻塞->就緒

一個阻塞狀態(tài)的進(jìn)程所

等待的事件已經(jīng)到來，

也即輸入輸出完成或請

求的資源得到滿足。

答案：可能會!

當(dāng)高優(yōu)先級進(jìn)程

會立即引起就緒

到運(yùn)行的狀態(tài)轉(zhuǎn)

于女■一與

a卜4斤，眼》

2.1.5進(jìn)程控制塊

進(jìn)程控制塊（PCB）是為了便于管理和控制進(jìn)程的運(yùn)行，為

每一個進(jìn)程設(shè)置的數(shù)據(jù)結(jié)構(gòu)。

進(jìn)程控制塊隨著進(jìn)程的創(chuàng)建而創(chuàng)建。

即創(chuàng)建一個進(jìn)程，就是創(chuàng)建一個PCB。

進(jìn)程控制塊隨著進(jìn)程的撤銷而撤銷。

即撤銷一個進(jìn)程，就是撤銷進(jìn)程的PCB。

PCB是進(jìn)程存在的唯一標(biāo)志。

第二章她理機(jī)碉念33

進(jìn)程控制塊的作用

進(jìn)程控制塊的作用是使一個在多道程序環(huán)境下

不能獨(dú)立運(yùn)行的程序（含數(shù)據(jù)），成為一個能獨(dú)立運(yùn)行的

基本單位，一個能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程。或者說,

OS是根據(jù)PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。

第二章她理機(jī)碉念34

1、標(biāo)識符為區(qū)分和標(biāo)識進(jìn)程,5、資源清單

在創(chuàng)建進(jìn)程時，由

系統(tǒng)給出的唯一與

之對應(yīng)的整型數(shù)，

2、現(xiàn)行狀態(tài)6、進(jìn)程優(yōu)先數(shù)

稱之為內(nèi)部標(biāo)識符。

創(chuàng)建者提供的標(biāo)識

符稱之為外部標(biāo)識

3、CPU狀態(tài)保護(hù)

符。7、隊列指針

區(qū)

4、進(jìn)程的位置

、家族聯(lián)系

和大小8

第二章她理機(jī)碉念35

1、標(biāo)識符5、資源清單

也稱為處理機(jī)狀

態(tài)。進(jìn)程目前的

2、現(xiàn)行狀態(tài)6、進(jìn)程優(yōu)先數(shù)

狀態(tài)，是進(jìn)程調(diào)

度、資源分配和

進(jìn)程控制的主要

3、CPU狀態(tài)保護(hù)

依據(jù)。7、隊列指針

區(qū)

4、進(jìn)程的位置

、家族聯(lián)系

和大小8

■

第二章她理機(jī)碉念36

1、標(biāo)識符5、資源清單

2、現(xiàn)行狀態(tài)6、進(jìn)程優(yōu)先數(shù)

進(jìn)程被阻塞時，

CPU現(xiàn)場信息被保

3、CPU狀態(tài)保護(hù)存在此，以便重獲

7、隊列指針

區(qū)CPU時進(jìn)程能繼續(xù)

進(jìn)行。

4、進(jìn)程的位置

8、家族聯(lián)系

和大小

第二章她理機(jī)碉念37

1、標(biāo)識符5、資源清單

2、現(xiàn)行狀態(tài)6、進(jìn)程優(yōu)先數(shù)

3、CPU狀態(tài)保護(hù)

7、隊列指針

區(qū)進(jìn)程運(yùn)行的程序段、

數(shù)據(jù)段，以及工作

區(qū)的位置和大小。

4、進(jìn)程的位置

、家族聯(lián)系

和大小8

第二章她理機(jī)碉念38

1、標(biāo)識符所需、所得資源情5、資源清單

況在此一■并反映。

2、現(xiàn)行狀態(tài)6、進(jìn)程優(yōu)先數(shù)

3、CPU狀態(tài)保護(hù)

7、隊列指針

區(qū)

4、進(jìn)程的位置

、家族聯(lián)系

和大小8

第二章她理機(jī)碉念39

1、標(biāo)識符5、資源清單

2、現(xiàn)行狀態(tài)進(jìn)程優(yōu)先數(shù)是進(jìn)程6、進(jìn)程優(yōu)先數(shù)

調(diào)度的重要依據(jù)。

3、CPU狀態(tài)保護(hù)

7、隊列指針

區(qū)

4、進(jìn)程的位置

、家族聯(lián)系

和大小8

第二章她理機(jī)碉念40

1、標(biāo)識符5、資源清單

2、現(xiàn)行狀態(tài)6、進(jìn)程優(yōu)先數(shù)

與處于相同狀態(tài)的

3、CPU狀態(tài)保護(hù)其它進(jìn)程PCB相連,

7、隊列指針

區(qū)或指向所在隊列隊

首。

4、進(jìn)程的位置

8、家族聯(lián)系

和大小

第二章她理機(jī)碉念41

1、標(biāo)識符5、資源清單

2、現(xiàn)行狀態(tài)6、進(jìn)程優(yōu)先數(shù)

3、CPU狀態(tài)保護(hù)

7、隊列指針

區(qū)

與此進(jìn)程有關(guān)的家

族成員由此指針連

4、進(jìn)程的位置

接。、家族聯(lián)系

和大小8

車二士章亞理空倜「二42

進(jìn)程控制塊在內(nèi)存的系統(tǒng)數(shù)據(jù)區(qū)中集中存放，稱為PCB區(qū)。

對于PCB區(qū)按其不同狀態(tài)，不同操作系統(tǒng)有不同的組織方式,

從而形成不同的管理效果。

如圖2.7將PCB組織成不同隊

列結(jié)構(gòu)。

如圖2.8用索引表鏈接，稱

為索引結(jié)構(gòu)或表格結(jié)構(gòu)。

合

宅第二章處理機(jī)成盒■一43

(b)阻塞隊列不分開

圖2.7PCB的隊列結(jié)構(gòu)

44

圖2.8：PCB的索引結(jié)果

第二章處理機(jī)碉t45

2.2進(jìn)程控制ULJ

2.2.1進(jìn)程樹和進(jìn)程隊列

2.2.2進(jìn)程控制原語

繳工量處理加抽塞e一-46

2.2.1進(jìn)程樹和進(jìn)程隊列

第二章處理機(jī)碉念47

(1)資源分配嚴(yán)格

樹形進(jìn)程機(jī)構(gòu)

的特點(diǎn)(2)進(jìn)程控制靈活

(3)進(jìn)程層次清晰

進(jìn)程樹的構(gòu)建方法:

最普通的一種進(jìn)程創(chuàng)建方式是在系統(tǒng)中被父進(jìn)程創(chuàng)建

還有一種是在系統(tǒng)生成時即被建立，直至系統(tǒng)關(guān)閉，這種進(jìn)

程一個系統(tǒng)中一般只有一、兩個，如UNIX系統(tǒng)中有0#進(jìn)程

和1#進(jìn)程。

0#進(jìn)程專門用于進(jìn)程對換和調(diào)度。

1#進(jìn)程專門用于創(chuàng)建shel1用戶進(jìn)程和管理shel1界面?！?/p>

1#進(jìn)程成為所有進(jìn)程的父進(jìn)程或祖先進(jìn)程。

第二章處理機(jī)碉凌一^48

為了實(shí)現(xiàn)對進(jìn)程的有效管理和控制，應(yīng)該對進(jìn)程按一定的方

式將其組織起來。

對于進(jìn)程的管理和控制主要是通過對PCB的組織來實(shí)現(xiàn)的。

PCB組織方式有隊列法，列表法，索引法等。

1處理機(jī)碉念49

1.隊列法

一個邏輯資源是：可以引起一個一

就緒進(jìn)程PCB組成一個隊

進(jìn)程進(jìn)入邏輯上阻塞狀態(tài)的任何

在單機(jī)系統(tǒng)中，運(yùn)行進(jìn)機(jī)事物，一般稱為資源。)

它獨(dú)立列為一隊列。

阻塞隊列一般較多，不同底遮，不同原因均可構(gòu)成不同的

阻塞隊列。

一般來說、一類資源組成一個進(jìn)程PCB阻塞隊列2

進(jìn)程隊列的組織方式有多種。一種典型的方式是為隊列設(shè)置

一個隊首結(jié)構(gòu)，它可以包括如下內(nèi)容：

隊列名：q1.插入程序入口Insert[q]

2.移出程序入口Remove[q]或Remove[q,i]

3.首元素指針First[q]

4.末元素指針Last[q]

Eh第二章處理枇碉,：一50

插入是插入到隊尾，移出一般是移出隊首元素，若非隊首元

素則將被移進(jìn)程標(biāo)識符i作為參數(shù)調(diào)用，即Removedi］。

隊列的組織方法可以按優(yōu)先級從高到低排列，也可按先進(jìn)先

出(FIFO)的順序排列。

進(jìn)程控制中，RL隊列按優(yōu)先級和FIF0相結(jié)合的方式

組織隊列。

其它隊列如資源等待隊列等，完全按FIFO排列。

如圖3.22（a、b、c）o

PCBPCBPCBPCB

---?~>—>

q—>P⑵P⑸P⑴P(n)

**?

Insert[q]*?*?**

*??—??

Remove[q]

datadatadatadata

First[q]addraddraddraddr

Last[q]

FIFO

(a)一般隊列組織

圖3.22：就緒隊列的組織

第二章她理機(jī)碉念52

PCBPCBPCBPCB

q:RL

TFP5WP2

Insert[q]

FlP3P5P8

Remove[q]

F1:P3addraddraddraddr:B1

1

B1:P2

PCBPCB|PCB

F2:F2

2P6P4P7

B2:B2F3P6P4

F3:P6add

3addadd

B3:P7.

PCB

F4:F4?

4fPl

B4:B43

一F5

F5:P1

5addr

B5:P1

(b)按隊列法組織PCB

First

Last圖3.22：就緒隊列的組織

PCB區(qū)

RLPCB14

PCB2

First1PCB35

Last15PCB4_8

PCB5_7

PCB6

PCB7_10

qiPCB8_12

PCB9

First3

PCB10_0

Last10PCB11_0

PCB1215

PCB13

q2PCB142n

PCB15—0

First16

PCB1614

Last11

PCB17

54

進(jìn)程控制塊

進(jìn)程標(biāo)示符，Id:外部標(biāo)識符，i：內(nèi)部標(biāo)

識符。

PCB

"ld[i]IStatus

Status[i]

進(jìn)程狀態(tài)，包括

Sdata[i]Running,Readya,

Readys,Blockeda,Blockeds等。

Priority[i]]

Sdata

圖3.23進(jìn)隊列指針，指向RL或某一資源等待隊列。

程控制塊

Addr

隊列中，進(jìn)程PCB間的鏈接指針，又可分

為向前向后兩種指針，如RL中。

Priority__________________

進(jìn)程的優(yōu)先數(shù)。

第二章處理機(jī)碉.——一~----------55

7^—-----口，就緒索引表

2?索引法空閑索引表以及阻塞

索引表等。

索引法將所有PCB區(qū)的PCB連續(xù)存放，根據(jù)所有進(jìn)

程狀態(tài)設(shè)置N個索引表。

每張索引表記有在此狀態(tài)里的所有PCB的地址，并

且此索引表按一定算法排列。

在系統(tǒng)數(shù)據(jù)區(qū)設(shè)有專用單元，專用單元中記有各

索引表的地址，以便查找。如圖3.24所示。

56

57

-2.2.2進(jìn)程控制原語

進(jìn)程控制

主要任務(wù)是創(chuàng)建和撤消進(jìn)程以及實(shí)現(xiàn)進(jìn)程的狀態(tài)轉(zhuǎn)換。

由操作系統(tǒng)的內(nèi)核完成的。

內(nèi)核

內(nèi)核基于硬件J它是硬件的第一次延伸。

有了內(nèi)核，系統(tǒng)對進(jìn)程的控制及管理就方便多了。

具體到每一個系統(tǒng)，內(nèi)核所包含的內(nèi)容都不一樣。

UNIX系統(tǒng)的整個基本功能都在操作系統(tǒng)的內(nèi)核里，所以

它包含的內(nèi)容就多一些。

Linux中內(nèi)核叫Kernel。

第二鎏處理機(jī)倜波.58

內(nèi)核可提供的功能因操作系統(tǒng)的不同而不同。

通常的功能有三方面：

(1)有限的中斷處理

計算機(jī)系統(tǒng)中的很多活動都離不開中斷處理這個最基本最

主要的功能。_________________________________________

操作系統(tǒng)的許多功能的實(shí)現(xiàn)也都依賴于它。______________

它是操作系統(tǒng)內(nèi)核的基本功能。

(2)進(jìn)程管理|L進(jìn)程的建立和撤消。

2.進(jìn)程調(diào)度。________________

3.實(shí)現(xiàn)進(jìn)程狀態(tài)的轉(zhuǎn)換。

4.控制和協(xié)調(diào)進(jìn)程的并發(fā)執(zhí)行。

第二章她理機(jī)碉念59

—如磁盤讀寫操作、時鐘管

(3)完成資源管理中的基本操作理操作和設(shè)春驅(qū)動等。

主要是資源管理中與硬件關(guān)系森嘉病訪!

內(nèi)核執(zhí)行上述操作時，大多數(shù)是通過原語來實(shí)現(xiàn)的。

原語是機(jī)器指令的延伸，是由若干條機(jī)器指令

進(jìn)程控制的幾，構(gòu)成的，用以完成特定功能的一段程序。為保

1.創(chuàng)建原語證操作的正確性，原語在執(zhí)行期間是不可分割

的(不可被打斷的)。實(shí)際上原語是操作系統(tǒng)

創(chuàng)建原語的彳提供的專用的程序段，只是它像機(jī)器指令那樣

_____________不分,在赧申I斯.日且右痔它」々坊臺B

進(jìn)程存在的標(biāo)志又在于PCB,所以創(chuàng)建進(jìn)程實(shí)際

上是建立PCB。

冬二章處理機(jī)碉液

Create(N,SO,KO,MO,RO)

創(chuàng)建原語的主要功能：I

尋找一空閑PCB

(1)尋找一個空閑PCBJ

(2)填寫PCB初值由N得內(nèi)部標(biāo)識符i,Id⑴=n

1

包括：填寫優(yōu)先數(shù)KO,CPU狀態(tài)，內(nèi)存

進(jìn)程的外部標(biāo)識符NM0,資源的初值RO

初始CPU狀態(tài)SO

進(jìn)程狀態(tài)jReadys”

標(biāo)識符

進(jìn)程優(yōu)先數(shù)

K0隊列指針=RL

初始內(nèi)存M0

所需資源清單R0等父進(jìn)程為*,子進(jìn)程為w

(3)插PCB于相應(yīng)隊歹U中。I

插入RL及家族隊列

流程圖如圖3.25。I

圖3.25:創(chuàng)建原語

61

專第"處理機(jī)倜隹

-——一——-^^一V「———^9^''---V

2.撤消原語

撤消進(jìn)程的原因有三種:

(1)正常結(jié)束

進(jìn)程完成了程序的執(zhí)行任務(wù)O

(2)出錯或故障結(jié)束，屬異常結(jié)束

有算術(shù)運(yùn)算出錯、違例出錯、I/O故障等。

(3)被干預(yù)結(jié)束

包括操作員或操作系統(tǒng)干預(yù)結(jié)束、被父進(jìn)程請

求結(jié)束、父進(jìn)程本身要結(jié)束而其子孫進(jìn)程不得

不結(jié)束。

■

撤消原語的作用是撤銷一個進(jìn)程。廠

首先是在找到被撤消進(jìn)程的PCB后，將該進(jìn)程所獲資源“上

交”，若是作業(yè)管理進(jìn)程則上交給系統(tǒng)，若是作業(yè)管理進(jìn)

程的子孫進(jìn)程則修資源“上交”給父進(jìn)程即可。

進(jìn)程存在的唯一標(biāo)志是PCB,所以撤消進(jìn)程最終是

撤消PCB,嚼PCB釋放回收給PCB區(qū)。

撤消原語的一種方法是采用遞歸調(diào)用。

在撤消子進(jìn)程中遞歸調(diào)用撤消進(jìn)程的kill,主進(jìn)

程則是在kill返回后根據(jù)有無運(yùn)行進(jìn)程標(biāo)志一若

有則引起進(jìn)程調(diào)度，若無則直接返回。

流^呈圖：圖圖

3.263.27■

鰭，巖叱理機(jī)碉盛一^^^5^164

3.阻塞原語T

進(jìn)程在運(yùn)行過程中，遇到要等待某一事件的到來，就需要

進(jìn)入阻塞隊列去等待，從而讓出CPU讓其他進(jìn)程去運(yùn)行。

這種從運(yùn)行到阻塞狀態(tài)的轉(zhuǎn)換可以用阻塞原語來實(shí)現(xiàn)。

阻塞原語的主要工作：算法描述:

查找到被阻塞進(jìn)程的PCBBlock(n,wl)

剝奪其CPU運(yùn)行權(quán)｛查找并得到PCB(n);

剝奪CPU;

改變狀態(tài)為阻塞狀態(tài)將進(jìn)程n的狀態(tài)置為阻塞狀態(tài);

將被阻塞進(jìn)程插入到相應(yīng)將PCB(n)從就緒隊列隊首移出

阻塞隊列中去插入相應(yīng)阻塞隊列wl;

「因?yàn)槊恳粋€阻塞原因都會進(jìn)程調(diào)度；

設(shè)置一個阻塞隊列。

第二金處理機(jī)碉/65

4.喚醒原語一"""~

完成進(jìn)程狀態(tài)從阻塞到就緒狀態(tài)的轉(zhuǎn)換。

喚醒原語仍對PCB進(jìn)行修改來實(shí)現(xiàn)其功能。

在被喚醒的阻塞隊列中，找到算法描述:

隊首進(jìn)程；

Wakeup(n,wl)

將該進(jìn)程從阻塞隊列移出；

(

將該進(jìn)程插入到就緒隊列中。查找并得到PCB(n);

從阻塞隊列wl中移出n;

將該進(jìn)程狀態(tài)改為就緒狀態(tài)。