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

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

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

4、疊。 每個程序的輸入操作、計算操作和打印操作必須順序執(zhí)行。對一批程序進行同時處理時，不同程序的各項操作可以并發(fā)執(zhí)行。,8,如圖2-3所示，存在以下的前趨關(guān)系：IiCi，CiPi，IiIi+1，CiCi+1，PiPi+1。故Pi-1和Ci以及Ii+1之間可以并發(fā)執(zhí)行。,9,程序的并發(fā)執(zhí)行的特征：,間斷性：程序并發(fā)執(zhí)行時，處理機交替執(zhí)行多個程序，每個程序都是以“停停走走”的方式執(zhí)行，可能走到中途停下來，而且程序無法預(yù)知每次執(zhí)行和暫停的時間長度，失去原有的時序關(guān)系。 失去封閉性：由于程序的并發(fā)執(zhí)行，打破了由一程序獨占系統(tǒng)資源的封閉性。多個程序共享一個計算機系統(tǒng)的多種資源，每個程序的執(zhí)行都會受其他程序

5、的影響。 失去可再現(xiàn)性。程序并發(fā)執(zhí)行時，由于失去了封閉性。由于程序每次執(zhí)行的環(huán)境不同，程序執(zhí)行的速度具有不可再現(xiàn)性。如果不采取制約措施，在不同執(zhí)行環(huán)境下的程序的執(zhí)行結(jié)果也將失去可再現(xiàn)特征。,10,程序執(zhí)行是為了對輸入信息進行處理，并得到相應(yīng)的處理結(jié)果。為此，程序在并發(fā)執(zhí)行時，必須保證程序執(zhí)行結(jié)果可再現(xiàn)性。由于程序并發(fā)執(zhí)行產(chǎn)生了一系列新特征，為了準確地描述并發(fā)程序的執(zhí)行，必須引入進程的概念。,11,2.1.4 進程,進程是指程序在并發(fā)環(huán)境下的一次運行過程。 可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的運行過程 傳統(tǒng)進程的兩個屬性： 進程是操作系統(tǒng)進行資源分配和處理機調(diào)度的基本單位。 現(xiàn)代操作系統(tǒng)引進線程之

6、后，進程的兩個屬性發(fā)生分離，進程僅是操作系統(tǒng)進行資源分配基本單位，而線程是操作系統(tǒng)處理機調(diào)度的基本單位。,12,引入進程對操作系統(tǒng)的影響,進程是計算機系統(tǒng)資源的使用主體，進程與處理機、存儲器和外設(shè)等資源的分配和回收相對應(yīng)。操作系統(tǒng)引入進程，可以實現(xiàn)多個進程的并發(fā)執(zhí)行，提高了系統(tǒng)資源的利用率，提高了系統(tǒng)的吞吐量。但由于每個進程配備PCB，增加了內(nèi)存的空間開銷。進程之間的切換、同步等需付出時間開銷，引入進程會帶來額外的時空開銷，增加了操作系統(tǒng)的復(fù)雜性。,13,進程的特征,動態(tài)性 并發(fā)性 獨立性 異步性 結(jié)構(gòu)特征。,14,進程的程序段描述了進程所要完成的功能。如果一個程序能夠被多個進程同時共享執(zhí)行，

7、那么，這個程序段就是純代碼(pure code)，即可重入代碼(reentry code)形式編寫的，它是指進程執(zhí)行時不可修改的部分。數(shù)據(jù)段是指進程執(zhí)行時用到的數(shù)據(jù)。用戶程序在此數(shù)據(jù)集合上進行操作，得到相應(yīng)的結(jié)果。進程控制塊包含進程的描述信息和控制信息，不同的操作系統(tǒng)其進程控制塊的內(nèi)容及信息量也不相同。,15,進程和程序的比較,程序是有序代碼的集合，是一個靜態(tài)的概念。進程是程序的一次執(zhí)行過程，是一個動態(tài)概念。進程不可以在計算機之間遷移，而程序通常對應(yīng)著文件，可以復(fù)制。 進程是一個狀態(tài)變化的過程，是有生命期的。而程序是永久的，可以長久保存。 進程與程序的組成不同。進程由程序段、數(shù)據(jù)段和進程控制塊

8、組成，而程序僅是代碼的有序集合。 進程與程序是密切相關(guān)的。通過多次執(zhí)行，一個程序可對應(yīng)多個進程。但進程與它本身所運行的程序只能是一對一的關(guān)系。 進程更能真實地描述并發(fā)，而程序不能。 進程可創(chuàng)建其他進程，而程序并不能形成新的程序。,16,2.1.5 任務(wù)與多任務(wù),對于有多個CPU的計算機，同時在每一個CPU上執(zhí)行進程稱為多重處理。多重處理是針對多機系統(tǒng)定義的，這一點請讀者注意理解。我們可以認為多重處理是多任務(wù)處理在多機系統(tǒng)中的一個特例，多重處理是多任務(wù)處理的子集。 多任務(wù)是指在同一時間間隔內(nèi)系統(tǒng)執(zhí)行多個進程,這里包含多重處理和多進程并發(fā)執(zhí)行。任務(wù)是一個具有開始時間和完成時間的操作,任務(wù)是系統(tǒng)的基

9、本工作單元，任務(wù)調(diào)度與進程調(diào)度的過程基本類似。在操作系統(tǒng)中，站在用戶的角度上，任務(wù)可以理解為邏輯上的進程。不同的操作系統(tǒng)進程與任務(wù)的含義不同，在Linux系統(tǒng)中，進程與任務(wù)的含義是相同的。,17,2.2 進程的狀態(tài)與進程控制塊 2.2.1進程的基本狀態(tài),18,進程在運行過程中主要是在就緒、執(zhí)行和阻塞三種基本狀態(tài)間進行轉(zhuǎn)換,創(chuàng)建(new)狀態(tài)。進程正在創(chuàng)建過程中，但還未將它送入就緒隊列時的狀態(tài)。 就緒狀態(tài)（Ready）。進程已得到必要的資源，唯缺處理機，等待處理機調(diào)度，一旦獲得處理機便可立即執(zhí)行。將處于就緒狀態(tài)的那些進程排成隊列就叫就緒狀態(tài)隊列。 執(zhí)行狀態(tài)（Running）。進程占用CPU資源并

10、正在CPU上執(zhí)行，處于此狀態(tài)的進程數(shù)目小于等于CPU的數(shù)目。在沒有其他進程可以執(zhí)行時(如所有進程都在阻塞狀態(tài))，通常會自動執(zhí)行系統(tǒng)的空閑進程。在多機系統(tǒng)中，可以有多個進程處于執(zhí)行狀態(tài)。而在單機系統(tǒng)中，僅有一個進程處于執(zhí)行狀態(tài)。,19,等待狀態(tài)（Waiting）。也稱為阻塞（Blocked)狀態(tài)，在執(zhí)行過程中，因等待某一事件而暫時無法執(zhí)行。將等待同一事件的阻塞進程排一個隊列就叫該事件的等待隊列。 退出（exit)狀態(tài)。當(dāng)一個進程已經(jīng)正常結(jié)束或異常結(jié)束，系統(tǒng)回收資源。操作系統(tǒng)已將它從就緒隊列中移出，正在將它撤消。,20,2.2.2進程的狀態(tài)變遷機制,提交(Admit)：完成一個新進程的創(chuàng)建過程，新

11、進程進入就緒狀態(tài)。由于性能、內(nèi)存、進程總數(shù)等原因，系統(tǒng)會限制并發(fā)進程總數(shù)。 調(diào)度(Dispatch)：按調(diào)度算法從就緒進程隊列中選擇進程，進入執(zhí)行狀態(tài)。 釋放(Release)：由于進程完成或異常終止進程運行，進入退出狀態(tài)。狀態(tài)變遷圖中只畫出了執(zhí)行狀態(tài)到退出狀態(tài)間的釋放轉(zhuǎn)換。但實際上，還存在從就緒狀態(tài)或阻塞狀態(tài)到退出狀態(tài)的釋放轉(zhuǎn)換。執(zhí)行到退出的轉(zhuǎn)換可分為正常退出(exit)和異常退出(abort)。,21,超時(Timeout)：由于用完時間片或高優(yōu)先級進程就緒等原因?qū)е逻M程暫停執(zhí)行。分配的時間片用完而發(fā)生時鐘中斷，或一個剛進入就緒隊列的進程，其優(yōu)先級高于處于執(zhí)行狀態(tài)的進程的優(yōu)先級而搶占處理機

12、，于是進程從執(zhí)行狀態(tài)到就緒狀態(tài)的轉(zhuǎn)變。 等待事件(Event Wait)：進程要求的事件未出現(xiàn)而進入阻塞。可能的原因包括：申請系統(tǒng)服務(wù)或資源、通信、I/O操作等。 事件發(fā)生(Event Occurs)：進程等待的事件發(fā)生。例如，操作完成、申請成功等。進程從等待狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)，重新等待處理機調(diào)度。 操作系統(tǒng)中多個進程的并發(fā)執(zhí)行是通過兩套循環(huán)完成。一是通過調(diào)度與超時二種狀態(tài)變遷原因的循環(huán)。二是通過調(diào)度、等待事件和事件發(fā)生三種狀態(tài)變遷原因的循環(huán)。,22,2.2.4進程控制塊,所謂進程控制塊（Process Control Block，PCB）是由操作系統(tǒng)維護，用來記錄進程相關(guān)信息的數(shù)據(jù)結(jié)構(gòu)。每個

13、進程在操作系統(tǒng)中都有對應(yīng)的進程控制塊。操作系統(tǒng)依據(jù)進程控制塊對進程進行控制和管理，進程控制塊中的內(nèi)容會隨進程的推進而動態(tài)改變。進程控制塊通常不能由應(yīng)用程序自身的代碼來直接訪問，而要通過系統(tǒng)調(diào)用進行訪問。,23,2.2.5進程之間的上下文切換,在多進程并發(fā)執(zhí)行中，將CPU切換到另一個進程需要保存原來進程的關(guān)聯(lián)狀態(tài)并裝入新進程的關(guān)聯(lián)狀態(tài)。這一任務(wù)稱為上下文切換當(dāng)發(fā)生上下文切換時，內(nèi)核會將舊進程的關(guān)聯(lián)狀態(tài)保存在其PCB中，然后裝入經(jīng)調(diào)度要執(zhí)行的新進程的已保存的關(guān)聯(lián)狀態(tài)。上下文切換時間是系統(tǒng)額外開銷，因為切換時系統(tǒng)并不能做什么有用的工作。 操作系統(tǒng)越復(fù)雜，上下文切換所要做的工作就越多。上下文切換問題可

14、能會成為操作系統(tǒng)性能的瓶頸，我們可以采用線程減少或避免上下文切換時間，降低操作系統(tǒng)開銷。,24,2.3 進程控制,鏈接方式,25,索引方式,26,2.3.3 進程控制原語,創(chuàng)建進程的典型事件 批處理系統(tǒng)中的作業(yè)調(diào)度。 用戶登錄。 用戶啟動應(yīng)用程序。 由操作系統(tǒng)創(chuàng)建的系統(tǒng)服務(wù)。 創(chuàng)建新的進程。,27,撤消原語,撤消進程的典型事件： 正常結(jié)束：進程完成了程序的執(zhí)行任務(wù)。 異常結(jié)束：出錯或故障結(jié)束，有算術(shù)運算出錯、I/O故障等。 被干預(yù)結(jié)束：包括操作員或操作系統(tǒng)干預(yù)結(jié)束、被父進程請求結(jié)束、父進程本身要結(jié)束而其子孫進程跟隨結(jié)束。,28,阻塞原語,阻塞原語具體的操作過程是：查找到該被阻塞進程的PCB，剝

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