【正文】 蘇州大學計算機科學與技術(shù)學院徐云龍第二章 進程管理1 進程的基本概念程序的順序執(zhí)行及其特征程序的順序執(zhí)行程序順序執(zhí)行時的特征2程序的順序執(zhí)行? 一個較大的程序通常都由若干個程序段組成? 程序在執(zhí)行時，必須按照某種先后次序逐個執(zhí)行，僅當前一操作執(zhí)行完后，才能執(zhí)行后繼操作。I1 C1 P1 I2 C2 P2程序順序執(zhí)行時的前趨圖S1： a:=x+yS2： b:=a5S3： c:=b+1前趨關(guān)系： Ii?Ci?Pi3程序順序執(zhí)行時的特征? 順序性– 處理機的操作嚴格按照程序所規(guī)定的順序執(zhí)行，即每一操作必須在上一個操作結(jié)束之后開始。? 封閉性– 程序是在封閉的環(huán)境下執(zhí)行的，即程序運行時 獨占 全機 資源– 資源的狀態(tài)（除初始狀態(tài)外）只有本程序才能改變它– 程序一旦開始執(zhí)行，其執(zhí)行結(jié)果不受外界因素影響? 可再現(xiàn)性– 只要程序執(zhí)行時的環(huán)境和初始條件相同，當程序多次重復(fù)執(zhí)行時，不論它是從頭到尾不停頓地執(zhí)行，還是 “停停走走 ”地執(zhí)行，都將獲得相同的結(jié)果 。4 進程的基本概念前趨圖 PrecedenceGraphv有向無循環(huán)圖 DAG(DirectedAcyclicGraph)，用于描述進程之間執(zhí)行的前后關(guān)系。v結(jié)點 ：語句 /程序段 /進程v有向邊 ：兩結(jié)點之間存在的偏序（ PartialOrder）或前趨關(guān)系（PrecedenceRelation） ”?”v?={(Pi,Pj)|PimustpletebeforePjmaystart}，如果 (Pi,Pj)∈ ?，可寫成 Pi?Pj， 稱 Pi是 Pj的 直接 前趨 ， Pj是 Pi的 直接后繼v初始結(jié)點 InitialNode：沒有前趨的結(jié)點v終止結(jié)點 FinalNode：沒有后繼的結(jié)點v Weight：結(jié)點所含的程序量或結(jié)點的執(zhí)行時間v上圖的前趨關(guān)系： Ii?Ci?Pi和 S1?S2?S35圖 21 具有 9個結(jié)點的前趨圖? 前趨關(guān)系：167。 P1?P2,P1?P3,P1?P4,P2?P5,P3?P5,P4?P6,P4?P7, P5?P8， P6?P8,P7?P9,P8?P9v 或表示為：167。 P={P1,P2,P3,P4,P5,P6,P7,P8,P9}167。 ?={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5), (P4,P6),(P4,P7),(P5,P8) (P6,P8),(P7,P9),(P8,P9) }P1P2P3P4P5P6P7不存在循環(huán)！P9P86圖 21 具有循環(huán)的圖? 前趨關(guān)系：167。 S2?S3, S3?S2S1S2S37 進程的基本概念程序并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行程序并發(fā)執(zhí)行時的前趨圖P1 P2 P3 P4I1 I2 I3 I4C1 C2 C3 C4前趨關(guān)系： Ii?Ci,Ii?Ii+1,Ci?Pi,Ci?Ci+1,Pi?Pi+1而 Ii+1和 Ci及 Pi1是重迭的，亦即在 Pi1和 Ci以及 Ii+1之間，可以并發(fā)執(zhí)行。 8前趨圖和程序執(zhí)行例：程序段如下：S1:a=x+2S2:b=y+4S3:c=a+bS4:d=c+6S1S2S3 S49程序并發(fā)執(zhí)行時的特征? 間斷性– 程序在并發(fā)執(zhí)行時，由于它們共享系統(tǒng)資源，以及為完成同一項任務(wù)而相互合作，致使在這些并發(fā)執(zhí)行的程序之間，形成相互制約的關(guān)系。– 執(zhí)行 —— 暫停 —— 執(zhí)行? 失去封閉性– 程序在并發(fā)執(zhí)行時，是多個程序共享系統(tǒng)中的各種資源（如下例中的變量 N），因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運行失去了封閉性。– 這樣，某程序在執(zhí)行時，必然會受到其他程序的影響。? 不可再現(xiàn)性– 程序經(jīng)過多次執(zhí)行后，雖然其執(zhí)行時的環(huán)境和初始條件都相同，但得到的結(jié)果卻各不相同10不可再現(xiàn)性的例子? 有兩個循環(huán)程序 A和 B，它們共享一個變量 N。程序 A每執(zhí)行一次時，都要做 N++操作；程序 B則每執(zhí)行一次時，都要執(zhí)行 printf(N)操作，然后 N=0，程序 A和 B以不同的速度運行。這樣，可能出現(xiàn)下述三種情況（假定某時刻變量 N的值為 n）。1) N++在 printf(N)和 N=0之前，此時得到的 N值分別為 n+1,n+1,02) N++在 printf(N)和 N=0之后，此時得到的 N值分別為 n, 0 , 13) N++在 printf(N)和 N=0之間，此時得到的 N值分別為 n,n+1,0– 結(jié)論：失去了可再現(xiàn)性11 進程的特征與狀態(tài)1.進程的特征和定義2.進程的三種基本狀態(tài)3.掛起狀態(tài)4.創(chuàng)建狀態(tài)和終止狀態(tài)121. 進程的特征和定義1）結(jié)構(gòu)特征（程序段、數(shù)據(jù)段、 PCB）– 程序不能并發(fā)執(zhí)行。– 為使程序（含數(shù)據(jù)）能獨立運行，應(yīng)為之配置一進程控制塊，即 PCB(ProcessControlBlock)；而由程序段、相關(guān)的數(shù)據(jù)段和 PCB三部分便構(gòu)成了進程實體。– 進程 =進程實體– 創(chuàng)建進程 =創(chuàng)建進程實體中的 PCB– 撤消進程 =撤消進程實體中的 PCB13 進程的特征與狀態(tài)2）動態(tài)性– 進程的實質(zhì)是進程實體的一次執(zhí)行過程，因此，動態(tài)性是進程的最基本的特征。– 進程由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤消而消亡，進程實體有一定的生命期，而程序則只是一組有序指令的集合，并存放在某種介質(zhì)上，其本身并不具有運動的含義，因而是靜態(tài)的。14 進程的特征與狀態(tài)3）并發(fā)性– 多個進程實體同存于內(nèi)存中，且能在一段時間內(nèi)同時運行。– 并發(fā)性是進程的重要特征，同時也成為 OS的重要特征。– 引入進程的目的也是為了使進程實體能和其他進程實體并發(fā)執(zhí)行，而程序是不能并發(fā)執(zhí)行的。15 進程的特征與狀態(tài)4）獨立性– 進程實體是一個能獨立運行的基本單位、獨立分配資源和獨立接受調(diào)度的基本單位。凡未建立 PCB的程序都不能作為一個獨立的單位參與運行。5）異步性– 進程各自獨立的、不可預(yù)知的速度向前推進，或說進程實體按異步方式運行。16進程的定義? 進程是進程實體的運行過程? 是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位172. 進程的狀態(tài)與轉(zhuǎn)換p 進程執(zhí)行時的間斷性，決定了進程可能具有多種狀態(tài)。? 運行狀態(tài)? 就緒狀態(tài)? 阻塞狀態(tài)? 創(chuàng)建狀態(tài)? 結(jié)束狀態(tài)18運行狀態(tài)（ Running）p 也叫執(zhí)行狀態(tài)。p 進程正在 CPU上運行。p 在單處理機環(huán)境下，每一時刻最多只有一個進程處于運行狀態(tài)。19就緒（ Ready）狀態(tài) p 進程獲得了除 CPU以外的一切所需資源p 就緒隊列：在一個系統(tǒng)中處于就緒狀態(tài)的進程可能有多個，通常將它們排成一個隊列，稱為就緒隊列。p 就緒隊列可以有多個l 為交互性作業(yè)所建立的進程，則排入 前臺就緒隊列 ；為批處理作業(yè)所建立的進程排入 后臺就緒隊列l(wèi) 前臺采用時間片輪轉(zhuǎn)調(diào)度算法，以便用戶能與自己的交互型作業(yè)交互；后臺采用優(yōu)先權(quán)高者優(yōu)先調(diào)度算法或短作業(yè)優(yōu)先調(diào)度算法。20阻塞（ Blocked）狀態(tài)? 又稱等待狀態(tài)、封鎖狀態(tài)。? 進程正在等待某一事件而暫停運行，如等待某資源為可用（不包括 CPU）或等待 I/O完成。即使CPU空閑，該進程也不能運行。? 致使進程阻塞的典型事件– 請求 I/O– 申請緩沖空間等? 阻塞隊列：將處于阻塞狀態(tài)的進程排成的隊列。? 根據(jù)阻塞原因，把處于阻塞狀態(tài)的進程排成多個隊列 。21注意區(qū)分就緒狀態(tài)和等待狀態(tài)? 就緒狀態(tài)是指進程僅缺少 CPU，只要獲得 CPU就立即執(zhí)行；等待狀態(tài)是指進程 需要其他資源 或 等待某一事件 。? 之所以把 CPU和其他資源分開來，是因為在分時系統(tǒng)的時間片輪轉(zhuǎn)機制中，每個進程分到的時間片是若干 ms，進程得到 CPU的時間很短且非常頻繁，進程在運行過程中實際上是頻繁地轉(zhuǎn)換到就緒狀態(tài)的；而其他資源（如外設(shè)）的使用和分配或者某一事件的發(fā)生（如 IO操作的完成）對應(yīng)的時間相對很長，進程轉(zhuǎn)換到等待狀態(tài)的次數(shù)也相對較少。22進程的三種基本狀態(tài)及其轉(zhuǎn)換進程調(diào)度就緒運行阻塞時 間片完I/O請求I/O完成23三種基本狀態(tài)之間的轉(zhuǎn)換? 就緒狀態(tài) ?運行狀態(tài)（進程調(diào)度）– 處于就緒狀態(tài)的進程，在調(diào)度程序為之分配了處理機之后，該進程便可執(zhí)行，相應(yīng)地，它就由就緒狀態(tài)轉(zhuǎn)變?yōu)閳?zhí)行狀態(tài)。? 運行狀態(tài) ?就緒狀態(tài)（時間片完）– 正在執(zhí)行的進程也稱為當前進程，如果因分配給它的時間片已完而暫停執(zhí)行時，該進程便由執(zhí)行狀態(tài)又回復(fù)到就緒狀態(tài)。此外，在可剝奪的 OS中，當有更高優(yōu)先級的進程就緒時，調(diào)度程序?qū)⒄龍?zhí)行的進程轉(zhuǎn)換為就緒狀態(tài)，讓更高優(yōu)先級的進程執(zhí)行。24三種基本狀態(tài)之間的轉(zhuǎn)換? 運行狀態(tài) ?阻塞狀態(tài)（ I/O請求）– 當進程 請求某一資源（如外設(shè)）的使用和分配 或 等待某一事件發(fā)生（如 IO操作的完成） 時，它就從運行狀態(tài)轉(zhuǎn)換為阻塞狀態(tài)。? 阻塞狀態(tài) ?就緒狀態(tài)（ I/O完成）– 當進程等待的事件到來時，如 IO操作結(jié)束或中斷結(jié)束時，中斷處理程序必須把相應(yīng)進程的狀態(tài)由阻塞狀態(tài)轉(zhuǎn)換為就緒狀態(tài)。25Ready Queue And Various I/O Device Queues就緒隊列和各種 I/O設(shè)備隊列26進程調(diào)度的隊列圖分派124327補充實例根據(jù)以下 某系統(tǒng)的進程狀態(tài)轉(zhuǎn)換圖。（ 1）說明引起各種狀態(tài)轉(zhuǎn)換的典型事件。（ 2）分析下述狀態(tài)轉(zhuǎn)換是否可立即引起其他的狀態(tài)轉(zhuǎn)換： 1,2,3,4。2就緒執(zhí)行阻塞1 3428（ 1） 引起狀態(tài)轉(zhuǎn)換的典型事件狀態(tài)轉(zhuǎn)換 引 起 狀態(tài) 轉(zhuǎn) 換的典型事件轉(zhuǎn)換 1 CPU調(diào)度轉(zhuǎn)換 2 執(zhí)行進程的時間片用完，或被其他優(yōu)先權(quán)更高的進程搶占 CPU轉(zhuǎn)換 3 等待某種事件（如 I/O的完成，或被他人占用的臨界資源變?yōu)榭捎脿?態(tài) ）轉(zhuǎn)換 4 進程所等待的事件發(fā)生（如 I/O完成，或所等待的臨界資源變?yōu)榭捎脿顟B(tài)）29（ 2）狀態(tài)轉(zhuǎn)換分析?狀態(tài)轉(zhuǎn)換 1不會立即引起其他狀態(tài)轉(zhuǎn)換。?狀態(tài)轉(zhuǎn)換 2必然立即引發(fā)狀態(tài)轉(zhuǎn)換 1：狀態(tài)轉(zhuǎn)換 2發(fā)生后，進程調(diào)度程序必然要選出一個新的就緒進程投入運行，該新進程可能是其他進程，也可能是剛從執(zhí)行狀態(tài)轉(zhuǎn)換成就緒狀態(tài)的那個進程。?狀態(tài)轉(zhuǎn)換 3可能立即引發(fā)狀態(tài)轉(zhuǎn)換 1：狀態(tài)轉(zhuǎn)換 3發(fā)生后，若就緒隊列非空，則進程調(diào)度程序?qū)⑦x出一個就緒進程投入執(zhí)行。?狀態(tài)轉(zhuǎn)換 4可能引發(fā)狀態(tài)轉(zhuǎn)換 1：狀態(tài)轉(zhuǎn)換 4發(fā)生后，若 CPU空閑，并且沒有其他進程競爭 CPU，則該進程將被立即調(diào)度。?另外，狀態(tài)轉(zhuǎn)換 4還可能同時引發(fā)狀態(tài)轉(zhuǎn)換 1和 2：若系統(tǒng)采用搶占調(diào)度方式，而新就緒的進程具備搶占 CPU的條件（如其優(yōu)先權(quán)很高），則它可立即得到 CPU轉(zhuǎn)換成執(zhí)行狀態(tài)，而原來正在執(zhí)行的進程則轉(zhuǎn)換成就緒狀態(tài)。303. 掛起狀態(tài)使正在執(zhí)行的進程暫停執(zhí)行；若此時用戶進程正處于就緒狀態(tài)而未執(zhí)行，則該進程暫不接受調(diào)度，以便用戶研究其執(zhí)行情況或?qū)Τ绦蜻M行修改。這種靜止狀態(tài)稱為掛起狀態(tài)。311）引入掛起狀態(tài)的原因（ 1）終端用戶的請求：– 當終端用戶在自己的程序運行期間發(fā)現(xiàn)有可疑問題時，希望暫時使自己的程序靜止下來，亦即，使正在執(zhí)行的進程暫停執(zhí)行。– 若此時用戶進程正處于就緒狀態(tài)而未執(zhí)行，則該進程暫不接受調(diào)度，以便用戶研究其執(zhí)行情況或?qū)Τ绦蜻M行修改。（ 2）父進程請求：父進程希望掛起自己的某個子進程，以便考查和修改該子進程，或者協(xié)調(diào)各子進程間的活動。32（ 3）負荷調(diào)節(jié)的需要：當實時系統(tǒng)中的工作負荷較重，已可能影響到對實時任務(wù)的控制時，可由系統(tǒng)把一些不重要的進程掛起，以便系統(tǒng)能正常運行。（ 4）操作系統(tǒng)的需要： OS有時希望掛起某些進程，以便檢查運行中的資源使用情況或進行記賬。331）引入掛起狀態(tài)的原因p在引入掛起狀態(tài)后，又將增加從掛起狀態(tài)（靜止狀態(tài)）到非掛起狀態(tài)（活動狀態(tài)）的轉(zhuǎn)換；或者相反。342）進程狀態(tài)的轉(zhuǎn)換（ 1）活動就緒 → 靜止就緒–活動就緒狀態(tài) Readya：當進程處于未被掛起的就緒狀態(tài)時。–靜止就緒狀態(tài) Readys：當用掛起原語 suspend將進程掛起后，該進程便轉(zhuǎn)換為靜止就緒狀態(tài)， 處于Readys狀態(tài)的進程不再被調(diào)度執(zhí)行 。352）進程狀態(tài)的轉(zhuǎn)換（ 2）活動阻塞 → 靜止阻塞–活動阻塞狀態(tài) Blockeda：進程處于未被掛起的阻塞狀態(tài)時。–靜止阻塞狀態(tài) Blockeds：當用Suspend原語將處于活動阻塞狀態(tài)的進程掛起后，進程便轉(zhuǎn)換為靜止阻塞狀態(tài)。處于該狀態(tài)的進程在其所期待的事件出現(xiàn)后，將從靜止阻塞變?yōu)殪o止就緒。 362）進程狀態(tài)的轉(zhuǎn)換（ 3） 靜止就緒 → 活動就緒–處于 Readys狀態(tài)的進程，若用激活原語 Active激活后，該進程將轉(zhuǎn)變?yōu)?Readya狀態(tài)。（ 4） 靜止阻塞 → 活動阻塞–處于 Blockeds狀態(tài)的進程，若用激活原語 Active激活后，進程將轉(zhuǎn)變?yōu)?Blockeda狀態(tài)。372）進程狀態(tài)的轉(zhuǎn)換活動阻塞靜止阻塞靜止就緒執(zhí)行活動就緒掛起請求I/O 激活掛起釋放激活釋放掛起調(diào) 度具有掛起狀態(tài)的進程狀態(tài)圖384. 創(chuàng)建狀態(tài)和終止狀態(tài)創(chuàng)建狀態(tài)終止狀態(tài)u 對一個進程來說，它處于創(chuàng)建狀態(tài)和終止狀態(tài)都只有一次。39創(chuàng)建（ New）狀態(tài)? 創(chuàng)建進程的步驟– 為新進程創(chuàng)建 PCB，并填寫必要的管理信息– 把該進程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊列? 當一個新進程被創(chuàng)建時，系統(tǒng)已為其分配了 PCB，填寫了進程標識等信息，但由于該進程所必需的資源或其他信息，如主存資源尚未分配等，即創(chuàng)建工作尚未完成，進程還不能被調(diào)度運行，其所處的狀態(tài)就是 創(chuàng)建狀態(tài) 。40創(chuàng)建（ New）狀態(tài)? 引入創(chuàng)建狀態(tài)的原因– 保證進程調(diào)度必須在創(chuàng)建工作完成后進行，以確保對 PCB操作的完整性。– 增加了管理的靈活性， OS可以根據(jù)