計(jì)算機(jī)操作系統(tǒng)(湯小丹第三版)第2章 進(jìn)程管理

1、第二章進(jìn)程管理，2.1進(jìn)程的基本概念2.2進(jìn)程控制2.3進(jìn)程同步2.4經(jīng)典進(jìn)程同步問(wèn)題2.5進(jìn)程通信2.6線程，*分配處理器，有效地控制管理其工作。 主要任務(wù)：在多個(gè)程序環(huán)境下，處理器管理可以歸結(jié)為流程管理，因此處理器管理主要研究流程的調(diào)度管理。 *過(guò)程控制：主要功能：*過(guò)程同步：*過(guò)程通信：*調(diào)度：第二章過(guò)程管理，2.1過(guò)程的基本概念，2.1.1程序的順序執(zhí)行及其特征，1，程序的順序執(zhí)行僅在執(zhí)行當(dāng)前操作(程序段)后圖2-1的程序的順序執(zhí)行、2、程序順序執(zhí)行時(shí)的特征、順序性(2)封閉性(3)再現(xiàn)性、S1: a:=x y； S2: b:=a-5； S3: c:=b 1； 2.1.2向前圖，向前圖

2、是有向無(wú)環(huán)圖，有向邊表示節(jié)點(diǎn)間的偏差和向前關(guān)系。 直接前進(jìn)直接后續(xù)的初始節(jié)點(diǎn)結(jié)束節(jié)點(diǎn)的重量或權(quán)重，可以同時(shí)執(zhí)行相互不依賴的節(jié)點(diǎn)，2.1.2前進(jìn)圖、IiCiPi S1S2S3、2.1.2前進(jìn)圖、P1P2、P1P3、P1P4、P2P5、P3P5、P4P6、P4 P2 P3、P4、P5、P6、P7、P8、P9=(P1、P2)、(P1、P3)、(P1、P4)、(P2、P5)、(P4、P6)、(P4、P7)、(P5、P8)、(P7、P9)、(P8、P9) 如果系統(tǒng)中存在循環(huán)，可能會(huì)發(fā)生死鎖。S2S3、S2S3、2.1.3程序同時(shí)執(zhí)行及其特征、1、程序同時(shí)執(zhí)行、圖2-3同時(shí)執(zhí)行時(shí)的向前圖，圖中存在向前關(guān)系

3、： IiCi、IiIi 1、CiPi、CiCi 1、PiPi 1中相互不依賴的部分同時(shí)程序段及其前驅(qū)圖： s 1: a=x2 s 2: b=y4s : c=ab 4: d=CB，圖2-4的四個(gè)語(yǔ)句的前進(jìn)關(guān)系，2，程序同時(shí)執(zhí)行時(shí)的特征，例如，a、b這兩個(gè)程序段同時(shí)、a:n:=n 1打印n，b :打印n n:=0，n的可能值：n 1、n 1、0 n、n 1、0 n、0、1、 2、程序同時(shí)執(zhí)行時(shí)的特征，1 )斷續(xù)性2 )閉合性3 )失去再現(xiàn)性，程序順序執(zhí)行時(shí)的特征：順序性(2)閉合性(3)再現(xiàn)性，3，程序同時(shí)執(zhí)行的條件，Bernstain條件：r (P1 ) w (p2 ) r (p2 ) w (P

4、1 )。 如果在p2的讀取集和寫入集之間或者在寫入集和寫入集之間沒(méi)有公共變量，兩個(gè)過(guò)程可以同時(shí)執(zhí)行。 1、流程的定義： (1)流程是程序的一次執(zhí)行。 (2)進(jìn)程是在處理器上順序執(zhí)行進(jìn)程及其數(shù)據(jù)時(shí)產(chǎn)生的活動(dòng)。 (3)過(guò)程是程序在一個(gè)數(shù)據(jù)集上運(yùn)行的過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單位。 流程是流程實(shí)體的執(zhí)行過(guò)程，是系統(tǒng)分配和調(diào)度資源的獨(dú)立單位。2.1.4過(guò)程的特征和狀態(tài)、2.1.4過(guò)程的特征和狀態(tài)、2、過(guò)程的特征和定義、1 )結(jié)構(gòu)特征2 )動(dòng)態(tài)性3 )獨(dú)立性4 )獨(dú)立性5 )異步性、*過(guò)程是可以并行執(zhí)行的程序在一個(gè)數(shù)據(jù)集合上的執(zhí)行過(guò)程。 *進(jìn)程是進(jìn)程實(shí)體的執(zhí)行進(jìn)程。*流程實(shí)體由段、數(shù)據(jù)段和流程

5、控制塊(PCB )組成。 注：進(jìn)程和程序的主要區(qū)別在于*程序是指令的集合，其本身沒(méi)有任何執(zhí)行的意義，是靜態(tài)概念的進(jìn)程是在處理器上執(zhí)行程序的過(guò)程，是動(dòng)態(tài)的概念。 *程序的存在是永久性的，流程有一個(gè)生命周期，由創(chuàng)建生成，按時(shí)間表執(zhí)行，資源不足，暫停，因撤消而消失。 *程序只是指令的順序集合，進(jìn)程由段、數(shù)據(jù)段和進(jìn)程控制塊組成。 *進(jìn)程和程序沒(méi)有一對(duì)一地對(duì)應(yīng)。 也就是說(shuō)，同一程序在多個(gè)不同的數(shù)據(jù)集上同時(shí)執(zhí)行，并且屬于不同的進(jìn)程。 也可以在一個(gè)過(guò)程中運(yùn)行多個(gè)程序。3、流程的三個(gè)基本狀態(tài)，圖2-5流程的三個(gè)基本狀態(tài)及其轉(zhuǎn)變，流程的五個(gè)基本狀態(tài)，*準(zhǔn)備完成狀態(tài)，*執(zhí)行狀態(tài)，*塊狀態(tài)，*新?tīng)顟B(tài)，*結(jié)束狀態(tài)，兩

6、個(gè)狀態(tài)的流程模型，五個(gè)狀態(tài)的流程模型，流程塊隊(duì)列，流程塊密鑰掛起狀態(tài)成為掛起狀態(tài)的原因最終用戶的請(qǐng)求(2)父進(jìn)程請(qǐng)求(3)需要調(diào)節(jié)負(fù)載(4)需要操作系統(tǒng)(5)需要更換，2 )進(jìn)程狀態(tài)的轉(zhuǎn)換，活動(dòng)準(zhǔn)備(2)活動(dòng)阻塞靜止阻塞(3)靜止阻塞靜止阻塞活動(dòng)阻塞，圖2-6中具有掛起狀態(tài)的過(guò)程狀態(tài)圖的掛起實(shí)際上是將對(duì)應(yīng)的狀態(tài)進(jìn)一步下降一級(jí)，2 )過(guò)程狀態(tài)的轉(zhuǎn)換，過(guò)程的掛起狀態(tài)，過(guò)程的掛起狀態(tài)，1，PCB的作用和特征，* PCB是操作系統(tǒng)中最重要的數(shù)據(jù)結(jié)構(gòu)并且是存在進(jìn)程的唯一標(biāo)志，* PCB的角色是，能夠獨(dú)立執(zhí)行在多個(gè)環(huán)境中不能獨(dú)立執(zhí)行的程序(包括數(shù)據(jù))的基本單元，并且能夠與其他進(jìn)程同時(shí)執(zhí)行的進(jìn)程可以由操作系

7、統(tǒng)中的多個(gè)模塊讀取或修改，* PCB是流程實(shí)體的一部分，與流程一樣具有一定的生命周期，與流程匹配。 2.1.5過(guò)程控制塊PCB、2、PCB的信息，1 )進(jìn)程標(biāo)識(shí)符內(nèi)部標(biāo)識(shí)符外部標(biāo)識(shí)符，2 )處理器狀態(tài)通用寄存器指令計(jì)數(shù)器程序狀態(tài)字PSW堆棧指針，3 )進(jìn)程調(diào)度信息進(jìn)程狀態(tài)進(jìn)程優(yōu)先級(jí)調(diào)度函數(shù)過(guò)程控制信息程序和數(shù)據(jù)的地址進(jìn)程同步和通信機(jī)構(gòu)資源列表鏈接指針2、PCB中的信息、3、PCB的組織方式、1 )鏈接方式、圖2-7 PCB鏈接矩陣圖、2 )索引方式、圖2-8索引方式來(lái)組織PCB，2 *流程控制由操作系統(tǒng)內(nèi)核實(shí)現(xiàn)，在系統(tǒng)狀態(tài)下運(yùn)行。 操作系統(tǒng)內(nèi)核是計(jì)算機(jī)硬件的第一個(gè)擴(kuò)展，由與硬件密切相關(guān)的模塊和

8、頻繁運(yùn)行的模塊組成。 內(nèi)核駐留內(nèi)存受到特別的保護(hù)。 *基元是由實(shí)現(xiàn)特定功能的特殊過(guò)程組成的指令組成的。 與常用過(guò)程的不同之處在于“原子操作”(Action Operation )。 2.2流程控制、操作系統(tǒng)內(nèi)核功能、*支持功能： *資源管理功能： *中斷管理、*時(shí)鐘管理、*原語(yǔ)操作、*流程管理、*內(nèi)存管理、*設(shè)備管理、*流程圖：用于描述流程族關(guān)系的有向圖，或反映父子關(guān)系1、流程圖、2.2流程控制、2.2.1流程的創(chuàng)建、2、引起創(chuàng)建流程的事件、用戶登錄(2)作業(yè)調(diào)度(3)服務(wù)提供(4)應(yīng)用程序請(qǐng)求、2.2流程控制應(yīng)用程序創(chuàng)建新進(jìn)程，3，創(chuàng)建進(jìn)程(Creation of Progress )，1

9、)申請(qǐng)空白PCB。 (2)向新進(jìn)程分配資源。 (3)對(duì)過(guò)程控制塊進(jìn)行初始化。 (4)如果新進(jìn)程插入到就緒隊(duì)列中，并且進(jìn)程就緒隊(duì)列能夠接受該新進(jìn)程，則將新進(jìn)程插入到就緒隊(duì)列中。 2.2.2進(jìn)程終止，1，引起進(jìn)程終止的事件1 )正常終止，3 )異常終止越境錯(cuò)誤保護(hù)非法命令錯(cuò)誤執(zhí)行超時(shí)等待算術(shù)運(yùn)算錯(cuò)誤I/O故障。 2 )外部介入運(yùn)營(yíng)商或系統(tǒng)介入父進(jìn)程請(qǐng)求終止該父進(jìn)程，2 )進(jìn)程終止過(guò)程(1)從該P(yáng)CB集合中檢索該過(guò)程的PCB，取得對(duì)應(yīng)的狀態(tài)(2)結(jié)束該過(guò)程的執(zhí)行，并改變調(diào)度標(biāo)志(3)。 將所有其資源返還給其父進(jìn)程或系統(tǒng)(5)從該進(jìn)程(即PCB )所屬的隊(duì)列(或鏈表)中刪除。 2.2.3進(jìn)程的閉塞與覺(jué)

10、醒，1、引起進(jìn)程的閉塞與覺(jué)醒的事件，對(duì)系統(tǒng)服務(wù)要求某種操作的新數(shù)據(jù)還沒(méi)有達(dá)到新的工作，2、進(jìn)程的閉塞進(jìn)程(1)通過(guò)調(diào)用閉塞原語(yǔ)block來(lái)使自己進(jìn)程塊是進(jìn)程本身的主動(dòng)行動(dòng)。(2)將PCB中的當(dāng)前狀態(tài)改變?yōu)殛P(guān)閉；(3)將PCB插入塊隊(duì)列；(4)將處理器分配給另一準(zhǔn)備完成進(jìn)程。 3、如果被阻止的進(jìn)程發(fā)生了期望的事件，那么該進(jìn)程喚醒進(jìn)程將調(diào)用原語(yǔ)wakeup，并等待該事件的進(jìn)程啟動(dòng)。 喚醒原文執(zhí)行的過(guò)程： (1)從塊隊(duì)列中刪除該過(guò)程(2)將PCB中的當(dāng)前狀態(tài)更改為就緒(3)將該過(guò)程的PCB插入準(zhǔn)備隊(duì)列。 發(fā)生引起2.2.4進(jìn)程掛起和激活、1、進(jìn)程掛起進(jìn)程掛起的事件時(shí)，系統(tǒng)使用掛起原語(yǔ)suspend來(lái)

11、掛起指定進(jìn)程或塊狀態(tài)的進(jìn)程。 中斷原語(yǔ)言的執(zhí)行過(guò)程：活動(dòng)準(zhǔn)備就緒的靜止準(zhǔn)備活動(dòng)將靜止塊的執(zhí)行狀態(tài)塊重新安排(靜止準(zhǔn)備就緒)，2，進(jìn)程的激活過(guò)程系統(tǒng)利用激活原語(yǔ)言active激活指定的進(jìn)程。 激活原語(yǔ)之前，將進(jìn)程從外部?jī)?nèi)存調(diào)用到內(nèi)存中，檢查該進(jìn)程的當(dāng)前狀態(tài)：靜止準(zhǔn)備活動(dòng)準(zhǔn)備阻止靜止塊活動(dòng)，2.3進(jìn)程同步，進(jìn)程同步：調(diào)整多個(gè)相關(guān)進(jìn)程的執(zhí)行順序。 這些過(guò)程是相互合作的，在某些重點(diǎn)上，需要互相等待和交換消息。 流程同步的主要任務(wù)：在并行執(zhí)行的各進(jìn)程之間有效地共享資源，使程序的執(zhí)行具有重復(fù)性。2.3.1進(jìn)程同步的基本概念、1、2種形式的制約關(guān)系(并行進(jìn)程間的關(guān)系)、*資源共享關(guān)系、*相互合作關(guān)系、(間接

12、相互制約)、(直接相互制約)、進(jìn)程間無(wú)關(guān)，進(jìn)程同步必須確保各進(jìn)程互斥的訪問(wèn)界限資源。 進(jìn)程之間有優(yōu)先級(jí)關(guān)系，進(jìn)程同步確保了各進(jìn)程執(zhí)行順序的協(xié)調(diào)，時(shí)間上沒(méi)有錯(cuò)誤。 2.3.1過(guò)程同步的基本概念、2、臨界資源、一段時(shí)間只能訪問(wèn)一個(gè)過(guò)程的資源臨界資源要求互斥的訪問(wèn)。 例如，生產(chǎn)者消費(fèi)者問(wèn)題，2.3.1進(jìn)程同步的基本概念，例如，生產(chǎn)者消費(fèi)者問(wèn)題，同步規(guī)則：消費(fèi)者進(jìn)程不允許在空緩沖區(qū)中發(fā)送消息，生產(chǎn)者進(jìn)程還允許在有消息但還沒(méi)有發(fā)送消息的緩沖區(qū)池中發(fā)送消息、producer、consumer、2.3.1進(jìn)程同步的基本概念，例如生產(chǎn)者消費(fèi)者問(wèn)題，解決方案：1 )輸入一個(gè)指針in，該指針表示數(shù)組buffer，

13、一個(gè)具有n個(gè)緩沖區(qū)的緩沖區(qū)池，輸出指針out表示可以投入以下消息的緩沖區(qū)2 )循環(huán)緩沖方式：投入信息時(shí)： in=(in1)取得mod n信息時(shí)： out=(out 1) mod n緩沖池空： in=out緩沖池滿： (in 1) mod n=out， 3 )導(dǎo)入整形變量counter表示當(dāng)前緩沖區(qū)中的信息數(shù)：信息投入時(shí)： counter=counter 1信息取得時(shí)： counter=counter - 1、生產(chǎn)者/消費(fèi)者問(wèn)題的有界循環(huán)緩沖區(qū)、producer : repeatpr while counter=n do no-op； nextp (:緩沖器)； in:=in 1 mod n；

14、counter:=counter 1； untiuntilffalse； consumer : repeatwhilecounter=0dono-op； nextc :=緩沖器輸出； out:=(out 1) mod n； 計(jì)數(shù)器=計(jì)數(shù)器- 1； 用戶the item in nextc； untiuntilffalse； Var n、integer； 類型項(xiàng)目=； var buffer :陣列0，1，n-1 of item； 輸入，輸出：1，n-1； counter :0，1，n； 生產(chǎn)者程序和消費(fèi)者程序都是正確的，而且順序執(zhí)行時(shí)的結(jié)果也是正確的。 但是，并行執(zhí)行會(huì)發(fā)生錯(cuò)誤，問(wèn)題是這兩個(gè)進(jìn)程共

15、享變量counter。在程序執(zhí)行時(shí)，register1:=counter； 注冊(cè)器2:=計(jì)數(shù)器； 注冊(cè)器1:=注冊(cè)器11； 注冊(cè)器2:=注冊(cè)器2-1； 計(jì)數(shù)器：=注冊(cè)器1； counter:=register2； 如果采用counter的當(dāng)前值為5、順序執(zhí)行方式，則如果采用假定最后的共享變量counter的值仍為5的同時(shí)執(zhí)行方式，則可能會(huì)發(fā)生下一個(gè)執(zhí)行順序和結(jié)果： counter值為4，register 1=counter； (注冊(cè)者1=5)注冊(cè)者1=注冊(cè)者1； (注冊(cè)器1=6)注冊(cè)器2=計(jì)數(shù)器； (注冊(cè)器2=5)注冊(cè)器2=注冊(cè)器2-1； (注冊(cè)器2=4)計(jì)數(shù)器=注冊(cè)器1； (計(jì)數(shù)器=6)計(jì)數(shù)器=注冊(cè)器2； (counter=4)，2.3.1程序同步的基本概念，事例：生產(chǎn)者消費(fèi)者問(wèn)題，問(wèn)題點(diǎn)：在相同次數(shù)的輸入輸出操作中，由于段的執(zhí)行順序不同，counter的值不同，偏離了正確的值，有錯(cuò)誤。 可以得出結(jié)論：變量counter是臨界資源，必須是排他的訪問(wèn)。 3、臨界區(qū)、*臨界區(qū)的定義，各過(guò)程中訪問(wèn)臨界資源的程序代碼稱為臨界區(qū)。重復(fù)進(jìn)