操作系統(tǒng)的原理與應(yīng)用-22548第2章進(jìn)程管理

1、操作系統(tǒng)原理Principles of Operating System 主講：孔憲君第2章 進(jìn)程管理 2.1 進(jìn)程與任務(wù)CPU管理主要研究進(jìn)程控制、進(jìn)程和線程管理、提供進(jìn)程同步機(jī)制和進(jìn)程通信機(jī)制，進(jìn)程調(diào)度和死鎖等 。我們可以把進(jìn)程理解為操作系統(tǒng)的工作單元，進(jìn)程是正在執(zhí)行的程序，進(jìn)程的執(zhí)行需要一定的資源。操作系統(tǒng)主要研究進(jìn)程與資源的關(guān)系。 2.1.1 前趨圖為了描述一個程序的各部分(程序段或語句)間的依賴關(guān)系 如圖所示的前趨圖中，P1為初始點(diǎn)，P7為終止點(diǎn)。前趨圖存在下面的前趨關(guān)系：P1P2，P1P3，P1P4，P2P5，P3P5，P3P6，P4P6，P5P7，P6P7。前趨圖中有兩種元素：節(jié)

2、點(diǎn)。用圓圈表示，其內(nèi)涵可以是一條語句、一個程序段或進(jìn)程。有向邊。用箭頭表示，表示兩個節(jié)點(diǎn)之間存在的偏序(Partial_Order)或前趨關(guān)系(Precedence_Relation)。PiPj表示在Pj開始前Pi必須完成，即Pi是Pj的直接前趨，Pj是Pi的直接后繼，前趨圖中不存在循環(huán)。 2.1.2 程序的順序執(zhí)行程序是指一個按嚴(yán)格次序執(zhí)行的操作序列，執(zhí)行的次序有順序、分支和循環(huán)；操作是數(shù)據(jù)處理的一種規(guī)則，一經(jīng)啟動就需要在有限時間內(nèi)完成。一個程序中包括三部分。I:輸入操作，C:計算操作，P:打印操作。這樣多個程序的順序執(zhí)行次序如圖所示。順序程序的特征如下:順序性：程序的執(zhí)行是按照程序結(jié)構(gòu)所指

3、定的次序進(jìn)行的。封閉性：程序在封閉的環(huán)境下執(zhí)行，即程序執(zhí)行時獨(dú)占全部系統(tǒng)資源。程序一旦開始執(zhí)行，其計算結(jié)果不受外界因素影響，計算機(jī)的狀態(tài)完全由該程序的控制邏輯所決定?？稍佻F(xiàn)性：只要程序執(zhí)行時的環(huán)境和初始條件相同，當(dāng)程序重復(fù)執(zhí)行時，不論它是從頭到尾不停頓地執(zhí)行，還是“停停走走”地執(zhí)行，都將獲得相同的結(jié)果。程序的結(jié)果與它的執(zhí)行速度無關(guān)，只要給定相同的輸入，一定會得到相同的結(jié)果。2.1.3 程序的并發(fā)執(zhí)行為提高系統(tǒng)資源的利用率和增強(qiáng)系統(tǒng)處理能力，在現(xiàn)代計算機(jī)中廣泛采用并行操作技術(shù)和并發(fā)程序設(shè)計技巧。 每個程序的輸入操作、計算操作和打印操作必須順序執(zhí)行。對一批程序進(jìn)行同時處理時，不同程序的各項(xiàng)操作可以

4、并發(fā)執(zhí)行。 如圖2-3所示，存在以下的前趨關(guān)系：IiCi，CiPi，IiIi+1，CiCi+1，PiPi+1。故Pi-1和Ci以及Ii+1之間可以并發(fā)執(zhí)行。 程序的并發(fā)執(zhí)行的特征： 間斷性：程序并發(fā)執(zhí)行時，CPU交替執(zhí)行多個程序，每個程序都是以“停停走走”的方式執(zhí)行，可能走到中途停下來，而且程序無法預(yù)知每次執(zhí)行和暫停的時間長度，失去原有的時序關(guān)系。失去封閉性：由于程序的并發(fā)執(zhí)行，打破了由一程序獨(dú)占系統(tǒng)資源的封閉性。多個程序共享一個計算機(jī)系統(tǒng)的多種資源，每個程序的執(zhí)行都會受其他程序的影響。失去可再現(xiàn)性。程序并發(fā)執(zhí)行時，由于失去了封閉性。由于程序每次執(zhí)行的環(huán)境不同，程序執(zhí)行的速度具有不可再現(xiàn)性。如

5、果不采取制約措施，在不同執(zhí)行環(huán)境下的程序的執(zhí)行結(jié)果也將失去可再現(xiàn)特征。10程序并發(fā)執(zhí)行失去可再現(xiàn)性典型的例子一個飛機(jī)訂票系統(tǒng)，兩個終端，同時執(zhí)行二個程序T1和T2。T1 : T2:. .read(x); read(x);if(x=1) -x; if(x=1) -x;write(x); write(x);. .程序執(zhí)行是為了對輸入信息進(jìn)行處理，并得到相應(yīng)的處理結(jié)果。為此，程序在并發(fā)執(zhí)行時，必須保證程序執(zhí)行結(jié)果可再現(xiàn)性。由于程序并發(fā)執(zhí)行產(chǎn)生了一系列新特征，為了準(zhǔn)確地描述程序的并發(fā)執(zhí)行，必須引入進(jìn)程的概念。2.1.4 進(jìn)程進(jìn)程是正在執(zhí)行的程序, 進(jìn)程是在并發(fā)環(huán)境下一個程序在一個數(shù)據(jù)集合上的一次執(zhí)行過

6、程。傳統(tǒng)進(jìn)程的兩個屬性： 進(jìn)程是操作系統(tǒng)進(jìn)行資源分配和CPU調(diào)度的基本單位?，F(xiàn)代操作系統(tǒng)引進(jìn)線程之后，進(jìn)程的兩個屬性發(fā)生分離，進(jìn)程僅是操作系統(tǒng)進(jìn)行資源分配基本單位，而線程是操作系統(tǒng)CPU調(diào)度的基本單位。引入進(jìn)程對操作系統(tǒng)的影響為了準(zhǔn)確地描述程序的并發(fā)執(zhí)行，必須引入進(jìn)程的概念。進(jìn)程是計算機(jī)系統(tǒng)資源的使用主體，進(jìn)程與CPU、存儲器和外設(shè)等資源的分配和回收相對應(yīng)。操作系統(tǒng)引入進(jìn)程，可以實(shí)現(xiàn)多個進(jìn)程的并發(fā)執(zhí)行，提高了系統(tǒng)資源的利用率，提高了系統(tǒng)的吞吐量。但由于每個進(jìn)程配備PCB，增加了內(nèi)存的空間開銷。進(jìn)程之間的切換、同步等需付出時間開銷，引入進(jìn)程會帶來額外的時空開銷，增加了操作系統(tǒng)的復(fù)雜性。進(jìn)程的特征

7、動態(tài)性并發(fā)性獨(dú)立性異步性結(jié)構(gòu)特征。進(jìn)程的程序段描述了進(jìn)程所要完成的功能。如果一個程序能夠被多個進(jìn)程同時共享執(zhí)行，那么，這個程序段就是純代碼(pure code)，即可重入代碼(reentry code)形式編寫的，它是指進(jìn)程執(zhí)行時不可修改的部分。數(shù)據(jù)段是指進(jìn)程執(zhí)行時用到的數(shù)據(jù)。用戶程序在此數(shù)據(jù)集合上進(jìn)行操作，得到相應(yīng)的結(jié)果。16進(jìn)程和程序的比較它們的主要區(qū)別如下：程序是有序代碼的集合，是一個靜態(tài)的概念。進(jìn)程是程序的一次執(zhí)行過程，是一個動態(tài)概念。進(jìn)程不可以在計算機(jī)之間遷移，而程序通常對應(yīng)著文件，可以復(fù)制。進(jìn)程是一個狀態(tài)變化的過程，是有生命期的。而程序是永久的，可以長久保存。進(jìn)程與程序的組成不同。

8、進(jìn)程由程序段、數(shù)據(jù)段和進(jìn)程控制塊組成，而程序僅是代碼的有序集合。進(jìn)程與程序是密切相關(guān)的。通過多次執(zhí)行，一個程序可對應(yīng)多個進(jìn)程。但進(jìn)程與它本身所執(zhí)行的程序只能是一對一的關(guān)系。進(jìn)程更能真實(shí)地描述并發(fā)，而程序不能。進(jìn)程可創(chuàng)建其他進(jìn)程，而程序并不能形成新的程序。172.2進(jìn)程控制塊與進(jìn)程的狀態(tài)2.2.1進(jìn)程控制塊進(jìn)程控制塊是由操作系統(tǒng)維護(hù)，用來記錄進(jìn)程相關(guān)信息的數(shù)據(jù)結(jié)構(gòu)。每個進(jìn)程在操作系統(tǒng)中都有對應(yīng)的進(jìn)程控制塊。操作系統(tǒng)依據(jù)進(jìn)程控制塊對進(jìn)程進(jìn)行控制和管理，進(jìn)程控制塊中的內(nèi)容會隨進(jìn)程的推進(jìn)而動態(tài)改變。 通常進(jìn)程控制塊PCB包括以下信息：進(jìn)程標(biāo)識符： CPU狀態(tài)保護(hù)區(qū) 進(jìn)程調(diào)度信息 進(jìn)程控制信息 2.2.

9、2進(jìn)程的基本狀態(tài)進(jìn)程在運(yùn)行過程中主要是在就緒、執(zhí)行和阻塞三種基本狀態(tài)間進(jìn)行轉(zhuǎn)換 創(chuàng)建(new)狀態(tài)。進(jìn)程正在創(chuàng)建過程中，但還未將它送入就緒隊(duì)列時的狀態(tài)。就緒狀態(tài)（Ready）。進(jìn)程已得到必要的資源，唯缺CPU，等待CPU調(diào)度，一旦獲得CPU便可立即執(zhí)行。將處于就緒狀態(tài)的那些進(jìn)程排成隊(duì)列就叫就緒狀態(tài)隊(duì)列。執(zhí)行狀態(tài)（Running）。進(jìn)程占用CPU資源并正在CPU上執(zhí)行，處于此狀態(tài)的進(jìn)程數(shù)目小于等于CPU的數(shù)目。在沒有其他進(jìn)程可以執(zhí)行時(如所有進(jìn)程都在阻塞狀態(tài))，通常會自動執(zhí)行系統(tǒng)的空閑進(jìn)程。在多機(jī)系統(tǒng)中，可以有多個進(jìn)程處于執(zhí)行狀態(tài)。而在單機(jī)系統(tǒng)中，僅有一個進(jìn)程處于執(zhí)行狀態(tài)。 等待狀態(tài)（Waiti

10、ng）。也稱為阻塞（Blocked)狀態(tài)，在執(zhí)行過程中，因等待某一事件而暫時無法執(zhí)行。將等待同一事件的阻塞進(jìn)程排一個隊(duì)列就叫該事件的等待隊(duì)列。退出（exit)狀態(tài)。當(dāng)一個進(jìn)程已經(jīng)正常結(jié)束或異常結(jié)束，系統(tǒng)回收資源。操作系統(tǒng)已將它從就緒隊(duì)列中移出，正在將它撤消。2.2.3進(jìn)程的狀態(tài)變遷機(jī)制 提交(Admit)：完成一個新進(jìn)程的創(chuàng)建過程，新進(jìn)程進(jìn)入就緒狀態(tài)。由于性能、內(nèi)存、進(jìn)程總數(shù)等原因，系統(tǒng)會限制并發(fā)進(jìn)程總數(shù)。調(diào)度(Dispatch)：按調(diào)度算法從就緒進(jìn)程隊(duì)列中選擇進(jìn)程，進(jìn)入執(zhí)行狀態(tài)。釋放(Release)：由于進(jìn)程完成或異常終止進(jìn)程運(yùn)行，進(jìn)入退出狀態(tài)。狀態(tài)變遷圖中只畫出了執(zhí)行狀態(tài)到退出狀態(tài)間的釋

11、放轉(zhuǎn)換。但實(shí)際上，還存在從就緒狀態(tài)或阻塞狀態(tài)到退出狀態(tài)的釋放轉(zhuǎn)換。執(zhí)行到退出的轉(zhuǎn)換可分為正常退出(exit)和異常退出(abort)。超時(Timeout)：由于用完時間片或高優(yōu)先級進(jìn)程就緒等原因?qū)е逻M(jìn)程暫停執(zhí)行。分配的時間片用完而發(fā)生時鐘中斷，或一個剛進(jìn)入就緒隊(duì)列的進(jìn)程，其優(yōu)先級高于處于執(zhí)行狀態(tài)的進(jìn)程的優(yōu)先級而搶占CPU，于是進(jìn)程從執(zhí)行狀態(tài)到就緒狀態(tài)的轉(zhuǎn)變。等待事件(Event Wait)：進(jìn)程要求的事件未出現(xiàn)而進(jìn)入阻塞?？赡艿脑虬ǎ荷暾埾到y(tǒng)服務(wù)或資源、通信、I/O操作等。事件發(fā)生(Event Occurs)：進(jìn)程等待的事件發(fā)生。例如，操作完成、申請成功等。進(jìn)程從等待狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)，

12、重新等待CPU調(diào)度。23操作系統(tǒng)中多個進(jìn)程的并發(fā)執(zhí)行是通過兩套循環(huán)完成。一是通過調(diào)度與超時二種狀態(tài)變遷原因的循環(huán)。二是通過調(diào)度、等待事件和事件發(fā)生三種狀態(tài)變遷原因的循環(huán)。 242.2.4具有掛起狀態(tài)的進(jìn)程 25掛起狀態(tài)的進(jìn)程模型中，產(chǎn)生了四種新意義的狀態(tài)：就緒狀態(tài)(Ready)：進(jìn)程在內(nèi)存，等待CPU調(diào)度。阻塞狀態(tài)(Blocked)：進(jìn)程在內(nèi)存，等待某事件的發(fā)生。阻塞掛起狀態(tài)(Blocked Suspend)：進(jìn)程在外存并等待某事件的發(fā)生。就緒掛起狀態(tài)(Ready Suspend)：進(jìn)程在外存。等待被激活。在掛起進(jìn)程模型中，操作系統(tǒng)用進(jìn)程狀態(tài)變遷機(jī)制來控制進(jìn)程的狀態(tài)變化，進(jìn)程狀態(tài)變遷機(jī)制一共有

13、提交和釋放、調(diào)度和超時、掛起和激活、事件發(fā)生和等待事件等八種，其中掛起和激活是新引入的，內(nèi)涵有變化的變遷機(jī)制為事件發(fā)生和提交。2.2.5進(jìn)程之間的上下文切換在多進(jìn)程并發(fā)執(zhí)行中，將CPU切換到另一個進(jìn)程需要保存原來進(jìn)程的關(guān)聯(lián)狀態(tài)并裝入新進(jìn)程的關(guān)聯(lián)狀態(tài)。這一任務(wù)稱為上下文切換當(dāng)發(fā)生上下文切換時，內(nèi)核會將舊進(jìn)程的關(guān)聯(lián)狀態(tài)保存在其PCB中，然后裝入經(jīng)調(diào)度要執(zhí)行的新進(jìn)程的已保存的關(guān)聯(lián)狀態(tài)。上下文切換時間是系統(tǒng)額外開銷，因?yàn)榍袚Q時系統(tǒng)并不能做什么有用的工作。操作系統(tǒng)越復(fù)雜，上下文切換所要做的工作就越多。上下文切換問題可能會成為操作系統(tǒng)性能的瓶頸，我們可以采用線程減少或避免上下文切換時間，降低操作系統(tǒng)開銷。

14、272.3進(jìn)程控制2.3.1進(jìn)程家族 進(jìn)程家族是一個樹形體系結(jié)構(gòu)，子進(jìn)程被父進(jìn)程創(chuàng)建，這是最普通的一種。還有一種進(jìn)程是在系統(tǒng)生成時即被建立，直至系統(tǒng)關(guān)閉，這種進(jìn)程一個系統(tǒng)中一般只有一或兩個，如UNIX系統(tǒng)中有0#進(jìn)程和1#進(jìn)程。 2.3.2進(jìn)程隊(duì)列鏈接方式索引方式2.3.3 進(jìn)程控制原語創(chuàng)建進(jìn)程的典型事件批處理系統(tǒng)中的作業(yè)調(diào)度。用戶登錄。用戶啟動應(yīng)用程序。由操作系統(tǒng)創(chuàng)建的系統(tǒng)服務(wù)。創(chuàng)建新的進(jìn)程。撤消原語撤消進(jìn)程的典型事件：正常結(jié)束：進(jìn)程完成了程序的執(zhí)行任務(wù)。異常結(jié)束：出錯或故障結(jié)束，有算術(shù)運(yùn)算出錯、I/O故障等。被干預(yù)結(jié)束：包括操作員或操作系統(tǒng)干預(yù)結(jié)束、被父進(jìn)程請求結(jié)束、父進(jìn)程本身要結(jié)束而其子

15、孫進(jìn)程跟隨結(jié)束。阻塞原語阻塞原語具體的操作過程是：查找到該被阻塞進(jìn)程的PCB，剝奪其CPU，將其狀態(tài)改為阻塞狀態(tài)，轉(zhuǎn)進(jìn)程調(diào)度。根據(jù)阻塞事件的類型將該阻塞進(jìn)程插入到相應(yīng)阻塞隊(duì)列中。阻塞原語的算法描述:void block(WQr)i=*EP;/*取得調(diào)用者進(jìn)程的PCB*/stop(i);/*剝奪CPU*/i.status=“blocked”/*將進(jìn)程i的狀態(tài)置為阻塞狀態(tài)*/i.state=WQr;/*填入所在隊(duì)列的首指針*/insert(WQr);/*插入相應(yīng)阻塞隊(duì)列*/scheduler;/*進(jìn)程調(diào)度*/喚醒原語因事件發(fā)生，進(jìn)程從阻塞狀態(tài)轉(zhuǎn)換到就緒狀態(tài)，用喚醒原語完成。喚醒原語對PCB進(jìn)行修改來實(shí)現(xiàn)其功能，在被喚醒的阻塞隊(duì)列中，找到隊(duì)首進(jìn)程。并將該進(jìn)程