操作系統(tǒng)2002--進(jìn)程管理.ppt

1、進(jìn)程管理,多道程序設(shè)計 進(jìn)程的概念 進(jìn)程的描述 進(jìn)程的控制 進(jìn)程的調(diào)度 線程的基本概念,一、多道程序設(shè)計,什么是多道程序設(shè)計？,讓多個計算問題同時裝入計算機系統(tǒng)的主 存儲器并發(fā)執(zhí)行，這種設(shè)計技術(shù)稱為“多道程序 設(shè)計”，這種計算機系統(tǒng)稱為“多道程序設(shè)計系 統(tǒng)”或“多道系統(tǒng)”,并發(fā)活動,“多道程序設(shè)計”導(dǎo)致多個相互獨立的程序同時在系統(tǒng)中運行，這些程序在系統(tǒng)中既交叉地運行，又要共享系統(tǒng)中的資源，這就會引起一系列的問題，包括：對資源的競爭、運行程序之間的通信、程序之間的合作與協(xié)同等符。 要解決這些問題，用程序的概念已經(jīng)不能描述程序在系統(tǒng)中運行的狀態(tài)，必須引人新的概念進(jìn)程。,為什么要采用多道程序設(shè)計？,

2、程序的順序執(zhí)行,一個程序由若干個程序段組成，而這些程序段的執(zhí)行必須是順序的，這種程序執(zhí)行的方式就稱為程序的順序執(zhí)行。 例如：,輸入一批數(shù)據(jù),處理數(shù)據(jù),打印處理結(jié)果,時間 輸入機 處理器 打印機,t1 t2 t3 t4 t5 t6,程序順序執(zhí)行的特點 1.順序性 處理機的操作，嚴(yán)格按照程序所規(guī)定的順序執(zhí)行。每個操作必須在下一個操作開始之前結(jié)束，即只有前一操作結(jié)束后，才能執(zhí)行后繼操作。 2.封閉性 程序一旦開始執(zhí)行，就獨占全機資源，其計算結(jié)果不受外界的影響。當(dāng)程序的初始條件給定之后，其后的狀態(tài)只能由程序本身確定，即只有本程序才能改變它。 3.可再現(xiàn)性 程序執(zhí)行的結(jié)果與初始條件有關(guān)，而與執(zhí)行時間無關(guān)

3、。只要程序的初始條件相同，它的執(zhí)行結(jié)果是相同的，即只要程序執(zhí)行時的環(huán)境和初始條件相同，當(dāng)程序多次重復(fù)執(zhí)行時，不論它是從頭到尾不停頓地執(zhí)行，還是“停停走走”地執(zhí)行。都將獲得相同的結(jié)果。,例： 在系統(tǒng)中有n個作業(yè)，每個作業(yè)都有三個處理步驟，輸入數(shù)據(jù)、處理、輸出，即Ii,Ci,Pi (i=1,2,3,.,n)。,程序并發(fā)執(zhí)行,這些作業(yè)在系統(tǒng)中執(zhí)行時是對時間的偏序，有些操作必須在其它操作之前執(zhí)行，這是有序的，但有些操作是可以同時執(zhí)行的。,例如: I1、C1、P1的執(zhí)行必須嚴(yán)格按照I1，C1，P1的順序，而P1與I2，C1與I2,I3與P1是可以同時執(zhí)行的。,若干個程序段同時在系統(tǒng)中運行，這些程序的執(zhí)行

4、在時間上是重迭的，一個程序段的執(zhí)行尚未結(jié)束，另一個程序段的執(zhí)行已經(jīng)開始，即使這種重迭是很小的，也稱這幾個程序段是并發(fā)執(zhí)行的。,采用多道程序設(shè)計應(yīng)注意的問題,可能延長程序執(zhí)行時間 并行工作道數(shù)與系統(tǒng)效率不成比例,程序的并發(fā)執(zhí)行與順序執(zhí)行的比較,一、失去了程序的封閉性 若一個程序的執(zhí)行可改變另一個程序的變量，則程序執(zhí)行的結(jié)果不僅依賴于程序的初始條件，還依賴于程序執(zhí)行時的相對速度，在這種情況下就失去了程序的封閉性。 二、程序與計算不再一一對應(yīng) 在程序順序執(zhí)行時，一個程序總是對應(yīng)一個具體的計算，但在程序的并發(fā)執(zhí)行時，可能有多用戶共享使用同一個程序，但處理（計算）的對象卻是不同的，例如，在多用戶環(huán)境下，

5、可能同時有多個用戶調(diào)用C語言的編譯程序，這就是典型的一個程序?qū)?yīng)多個用戶源程序的情況。 三、程序并發(fā)執(zhí)行的相互制約 在多道程序設(shè)計的環(huán)境下，程序是并發(fā)執(zhí)行的。即系統(tǒng)中有多道程序在“同時”執(zhí)行，這些程序之間要共享系統(tǒng)的資源，程序之間有合作（通信）的關(guān)系。合作與競爭產(chǎn)生一系列的矛盾，這些矛盾實際上是一種相互制約，有直接的，也有間接的。,程序并發(fā)執(zhí)行時的特征： 間斷性 程序在并發(fā)執(zhí)行時，由于它們共享資源或為完成同一項任務(wù)而租互合作，致使在井發(fā)程序之間形成了相互制約的關(guān)系。例如：如果I、C、P是三個相互合作的程序。當(dāng)計算程序C完成了上一批數(shù)據(jù)的計算后，如果輸入程序I尚未完成下一批數(shù)據(jù)的輸入，則計算程序

6、就無法進(jìn)一步進(jìn)行處理，致使計算程序暫停運行。一旦使計算程序暫停的因素消失后（如輸入程序已完成了下一批數(shù)據(jù)的輸入后），計算程序便可恢復(fù)執(zhí)行。這樣的相互制約將導(dǎo)致井發(fā)程序具有“執(zhí)行一暫停執(zhí)行一執(zhí)行”這種間斷性的活動規(guī)律。 失去封閉性 程序在并發(fā)執(zhí)行時，是多個程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運行失去了封閉性。這樣，某程序在執(zhí)行時，必然受到其他程序的影響。 不可再現(xiàn)性 程序再并發(fā)執(zhí)行時，由于失去的并發(fā)性，也將導(dǎo)致失去可再現(xiàn)性。,例如：下述兩個循環(huán)程序A和B，它們共享一個變量n。程序A每循環(huán)一次都要對n做如下n := n + 1 操作：程序B每循環(huán)一次打印n 的

7、值，再將n置0。具體的程序為：,程序A Begin Repeat n := N + 1; Until false End,程序B Begin Repeat print (n) ; n := 0 ; Until false End,假定某一時刻，n 的值為N。程序 A 的 n:= N + 1 和程序B的 print（n）和 n := 0 如果有下述關(guān)系： .之前，則打印的結(jié)果為N+1； .之后，則打印的結(jié)果為N； .中間，則打印的結(jié)果為N；,在多道進(jìn)程設(shè)計的系統(tǒng)中，對多道并行執(zhí)行的程序來說，一個程序的執(zhí)行還可能受到另一個程序的約束，所以，程序的執(zhí)行實際上是走走停停的。為了能正確地反映程序的活動規(guī)

8、律和狀態(tài)變化（程序的執(zhí)行情況），要引進(jìn)一個新的概念-進(jìn)程，以便從變化的角度動態(tài)地研究程序的執(zhí)行。,二、進(jìn)程的概念,進(jìn)程的概念是操作系統(tǒng)中最基本、最重要的概念。它是在多道程序系統(tǒng)出現(xiàn)后，為了刻劃系統(tǒng)內(nèi)部出現(xiàn)的情況，描述系統(tǒng)內(nèi)部各作業(yè)的活動規(guī)律而引進(jìn)的一個新的概念。,進(jìn)程（PROCESS）這個名詞最早是六十年代初期，在麻省理工學(xué)院的MULTICS系統(tǒng)和IBM公司CTSS/360操作系統(tǒng)中引入的。直至目前關(guān)于進(jìn)程的定義及其名稱均不統(tǒng)一。在少數(shù)系統(tǒng)中把進(jìn)程稱為任務(wù)（TASK）。,對進(jìn)程的定義有如下幾種： （1）進(jìn)程是程序的一次執(zhí)行； （2）進(jìn)程是程序在一個數(shù)據(jù)集合上的運行過程，是 系統(tǒng)進(jìn)行資源分配和調(diào)

9、度的一個獨立單位； （3）進(jìn)程可定義為一個數(shù)據(jù)結(jié)構(gòu)及其能在其上進(jìn)行 操作的一個程序； （4）進(jìn)程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行 時所發(fā)生的活動； （5）進(jìn)程是可以與別的計算并發(fā)執(zhí)行的計算。,進(jìn)程具有的五大特征： （1）動態(tài)性 進(jìn)程的實質(zhì)是程序的一次執(zhí)行過程。因此， 動態(tài)特性是進(jìn)程最重要的特征。 （2）并發(fā)性 沒有為之建立進(jìn)程的程序是不能并發(fā)執(zhí)行的 ，僅當(dāng)為之建立一個進(jìn)程后，才能參加并發(fā)執(zhí)行。 （3）獨立性 進(jìn)程不是隨便一個拿來的程序，它是一個能 獨立運行的程序的化身。它同其它的這樣的獨立單位 去競爭系統(tǒng)資源和處理機。 （4）異步性 由于進(jìn)程間共享資源和協(xié)同合作時帶來了相 互制約關(guān)系，造成

10、進(jìn)程執(zhí)行的間斷性。 （5）結(jié)構(gòu)特征 為了控制和管理進(jìn)程，系統(tǒng)為每個進(jìn)程設(shè) 立一個進(jìn)程控制塊一PCB。這樣，從結(jié)構(gòu)上看， 每個 進(jìn)程都是由相應(yīng)的代碼段、數(shù)據(jù)段和一個PCB三者組成。,進(jìn)程和程序之間一般認(rèn)為有如下區(qū)別：。 （1）進(jìn)程是程序的執(zhí)行。故進(jìn)程屬于動態(tài)概念。而 程序是一組指令的有序集合，是靜態(tài)的概念； （2）進(jìn)程既然是程序的執(zhí)行，或者說是“一次運行活 動”。因而它是有生命過程的，從投入運行到運 行完成。 （3）進(jìn)程是程序的執(zhí)行，因此進(jìn)程的組成應(yīng)包括程 序和數(shù)據(jù)。除此之外，進(jìn)程的組成中還包括記 錄進(jìn)程狀態(tài)信息的“進(jìn)程控制塊”； （4）一個程序可能對應(yīng)多個進(jìn)程。 （5）一個進(jìn)程可以包含多個程序

11、。,1、系統(tǒng)進(jìn)程 系統(tǒng)進(jìn)程起著資源管理和控制的作用。 或者：執(zhí)行操作系統(tǒng)核心代碼的進(jìn)程。 2、用戶進(jìn)程 執(zhí)行用戶程序的進(jìn)程。,在系統(tǒng)中同時有多個進(jìn)程存在，但歸納起來有兩大類：,系統(tǒng)進(jìn)程與用戶進(jìn)程的區(qū)別： 1、系統(tǒng)進(jìn)程被分配一個初始的資源集合，這些資源可以為它獨占，也能以最高優(yōu)先權(quán)的資格使用。用戶進(jìn)程通過系統(tǒng)服務(wù)請求的手段競爭使用系統(tǒng)資源； 2、用戶進(jìn)程不能直接做I/O操作，而系統(tǒng)進(jìn)程可以做顯示的、直接的I/O操作。 3、系統(tǒng)進(jìn)程在管態(tài)下活動，而用戶進(jìn)程則在用戶態(tài)（目態(tài)）下活動。 另一種分類：計算進(jìn)程，I/O進(jìn)程等 注意：在UNIX系統(tǒng)中沒有這樣對進(jìn)程進(jìn)行分類。,三、進(jìn)程的描述,進(jìn)程控制塊： 為

12、了標(biāo)識進(jìn)程，記錄各個進(jìn)程執(zhí)行時的情況，操作系統(tǒng)為每個進(jìn)程都設(shè)置一個“進(jìn)程控制快”。進(jìn)程控制塊的英文名稱的縮寫為PCB。,進(jìn)程控制快是進(jìn)程實體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)之一。PCB中記錄了操作系統(tǒng)所需要的、用來描述進(jìn)程狀態(tài)及控制進(jìn)程運行所必需的全部信息。進(jìn)程控制快的作用，是使一個在多道程序環(huán)境下不能獨立運行的程序（及其所含的數(shù)據(jù)），成為一個能獨立運行的基本單位，一個能與其他進(jìn)程并發(fā)執(zhí)行的進(jìn)程。,一般情況下，進(jìn)程控制塊應(yīng)包含四類信息,存放進(jìn)程的管理和控制信息的數(shù)據(jù)結(jié)構(gòu)稱為進(jìn)程控制塊。它是進(jìn)程管理和控制的最重要的數(shù)據(jù)結(jié)構(gòu)，在創(chuàng)建時，建立PCB，并伴隨進(jìn)程運行的全過程，直到進(jìn)程撤消而

13、撤消。PCB就象我們的戶口。,進(jìn)程控制塊 PCB (Process Control Block),1、進(jìn)程標(biāo)識符 name 每個進(jìn)程都必須有一個唯一的標(biāo)識符，可以是字符串，也可以是一個數(shù)字。UNIX系統(tǒng)中就是一個整型數(shù)。在進(jìn)程創(chuàng)建時由系統(tǒng)賦予。 2、進(jìn)程當(dāng)前狀態(tài) status 說明進(jìn)程當(dāng)前所處的狀態(tài)。 為了管理的方便，系統(tǒng)設(shè)計時會將相同的狀態(tài)的進(jìn)程組成一個隊列，如就緒進(jìn)程隊列，等待進(jìn)程則要根據(jù)等待的事件組成多個等待隊列，如等待打印機隊列、等待磁盤I/O完成隊列等等。 3、當(dāng)前隊列指針 next 登記與本進(jìn)程處于同一隊列的下一個進(jìn)程的PCB的地址。,4、總鏈指針 all-q-next 5、執(zhí)行程

14、序開始地址 start-addr 6、進(jìn)程優(yōu)先級 priority 進(jìn)程的優(yōu)先級反映進(jìn)程的緊迫程序，通常由用戶指定和系統(tǒng)設(shè)置。UNIX系統(tǒng)采用用戶設(shè)置和系統(tǒng)計算相結(jié)合的方式確定進(jìn)程的優(yōu)先級。 7、CPU現(xiàn)場保護(hù)區(qū) cpustatus 當(dāng)進(jìn)程因某種原因不能繼續(xù)占用CPU時（等待打印機），釋放CPU，這時就要將CPU的各種狀態(tài)信息保護(hù)起來，為將來再次得到處理機恢復(fù)CPU的各種狀態(tài)，繼續(xù)運行。例如，我們下課，這時我要記住這次講到什么地方，下次課接著講。 8、通信信息 communication information 是指某個進(jìn)程在運行的過程中要與其它進(jìn)程進(jìn)行通信，該區(qū)記錄有關(guān)進(jìn)程通信方面的信息。,

15、9、家族聯(lián)系 process family 有的系統(tǒng)允許一個進(jìn)程可創(chuàng)建自已的子進(jìn)程，子進(jìn)程還可以繼續(xù)創(chuàng)建子子進(jìn)程。一個進(jìn)程往往處在一個家族之中，就需要記錄進(jìn)程在家族中位置的信息。 10、占有資源清單 own-resource 進(jìn)程占用系統(tǒng)資源的情況，不同的系統(tǒng)的處理差別很大，UNIX系統(tǒng)中就沒有此項。,進(jìn)程隊列,進(jìn)程的狀態(tài) 進(jìn)程在它存在過程中，由于系統(tǒng)中各進(jìn)程并行運行及相互制約的結(jié)果。使得它們的狀態(tài)不斷發(fā)生變化。 系統(tǒng)中不同的事件均可引起進(jìn)程狀態(tài)的變化。通常一個進(jìn)程至少具有三種基本狀態(tài)： （1）運行狀態(tài)（又稱為執(zhí)行狀態(tài)）：當(dāng)一個進(jìn)程正在處理機上運行時，稱此進(jìn)程處于運行狀態(tài)； （2）就緒狀態(tài)：一

16、個進(jìn)程獲得了除處理機之外的一切所需資源，一旦得到處理機即可運行，則稱此進(jìn)程處于就緒狀態(tài)； （3）等待狀態(tài)（又稱阻塞狀態(tài)）：一個進(jìn)程正在等待某一事件（如等待某種資源成為可用，等待輸入輸出完成或等待其它進(jìn)程給它發(fā)來消息）發(fā)生而暫時停止運行。這時即使把處理機分配給該進(jìn)程它也無法運行，則稱此進(jìn)程處于等待狀態(tài)（或稱阻塞狀態(tài)）。,進(jìn)程在系統(tǒng)中，其狀態(tài)變化的情況，可大致分為： （1）運行態(tài) - 等待態(tài) （2）等待態(tài) - 就緒態(tài) （3）運行態(tài) - 就緒態(tài) （4）就緒態(tài) - 運行態(tài),進(jìn)程在執(zhí)行過程中狀態(tài)會不斷發(fā)生變化，每個進(jìn)程在執(zhí)行過程中的任一時刻總是處于上述三種基本狀態(tài)之一。進(jìn)程狀態(tài)的轉(zhuǎn)換關(guān)系如圖所示。,（1

17、）運行態(tài)一等待態(tài) 處于運行狀態(tài)的進(jìn)程，在其運行過程中需要等待某一事件發(fā)生后，才能繼續(xù)運行，于是該進(jìn)程由運行狀態(tài)變?yōu)榈却隣顟B(tài)。例如，一個進(jìn)程運行中啟動了外圍設(shè)備，它就變成等待外圍設(shè)備傳輸信息的狀態(tài)；進(jìn)程在運行中申請資源（主存空間及外圍設(shè)備等）得不到滿足時變成等待資源狀態(tài)；進(jìn)程在運行中出現(xiàn)了故障（程序出錯或主存儲器讀寫錯等）變成等待干預(yù)狀態(tài)。 （2）等待態(tài) - 就緒態(tài) 處于等待狀態(tài)的進(jìn)程，若其等待的事件已經(jīng)發(fā)生，于是進(jìn)程由等待狀態(tài)變?yōu)榫途w狀態(tài)。例如：外圍設(shè)備工作結(jié)束后使等待外圍設(shè)備傳輸信息的進(jìn)程結(jié)束等待；等待的資源能得到滿足時（另一進(jìn)程歸還了資源）則等待資源者就結(jié)束等待；故障排除后讓等待干預(yù)的進(jìn)程

18、結(jié)束等待。任何一個結(jié)束等待的進(jìn)程必須先變成就緒狀態(tài)，待分配到處理器后才能運行，等待狀態(tài)的進(jìn)程不能直接轉(zhuǎn)變?yōu)檫\行狀態(tài)。,（3）運行態(tài)一就緒態(tài) 系統(tǒng)在進(jìn)程用完了一個使用處理器的時間片后就會強迫該進(jìn)程暫時讓出處理器，當(dāng)有更高優(yōu)先權(quán)的進(jìn)程要運行時也迫使正在運行的進(jìn)程讓出處理器。不是由于自身或外界原因成為等待狀態(tài)的進(jìn)程讓出處理器時，它的狀態(tài)就變成就緒狀態(tài)。 （4）就緒態(tài)一運行態(tài) 對等待分配處理器的進(jìn)程，系統(tǒng)按某種選定的策略從處于就緒狀態(tài)的進(jìn)程中選擇一個進(jìn)程，讓它占用處理器，這個被選中的進(jìn)程的狀態(tài)就從就緒態(tài)變成運行態(tài)。正在執(zhí)行的進(jìn)程也稱為當(dāng)前進(jìn)程。 在一個實際的系統(tǒng)里，出于調(diào)度策略的考慮，往往把這三種基本

19、狀態(tài)進(jìn)一步細(xì)分成若干更多的狀態(tài)。例如，在UNIX操作系統(tǒng)中，進(jìn)程的狀態(tài)被分成六種。當(dāng)然，狀態(tài)被細(xì)分后，狀態(tài)轉(zhuǎn)換關(guān)系相應(yīng)地也要更復(fù)雜一些。,四、進(jìn)程的控制,進(jìn)程是有生命周期的，產(chǎn)生、運行、暫停、終止。對進(jìn)程的這些操作叫進(jìn)程控制。 進(jìn)程控制的職責(zé)是對系統(tǒng)中全部進(jìn)程實施有效的管理，它是處理機管理的部分（另一部分是進(jìn)程調(diào)度），當(dāng)系統(tǒng)允許多進(jìn)程并發(fā)執(zhí)行時，為了實現(xiàn)共享、協(xié)調(diào)并發(fā)進(jìn)程的關(guān)系，處理機管理必須提供對進(jìn)程實行有效的管理。,為了防止操作系統(tǒng)及關(guān)鍵數(shù)據(jù)受到用戶程序有意或無意的破壞，通常將處理機的執(zhí)行狀態(tài)分成系統(tǒng)態(tài)或用戶態(tài)兩種： 系統(tǒng)態(tài)：具有較高的特權(quán)，能執(zhí)行一切指令，訪問 所有的寄存器和內(nèi)存 用戶態(tài)

20、：只能執(zhí)行規(guī)定的命令，訪問指定的寄存器 和內(nèi)存。 通常，用戶程序運行在用戶態(tài)，因此它不能執(zhí)行操作系統(tǒng)指令和訪問操作系統(tǒng)區(qū)域，所以操作系統(tǒng)得到了保護(hù)。操作系統(tǒng)運行在系統(tǒng)態(tài)。,進(jìn)程控制包括： 進(jìn)程創(chuàng)建 進(jìn)程撤消 進(jìn)程阻塞 進(jìn)程喚醒 這些操作都要對應(yīng)地執(zhí)行一個特殊的程序段（操作系統(tǒng)核心程序），同時系統(tǒng)也通過系統(tǒng)調(diào)用給用戶提供進(jìn)程控制的功能。教材上叫原語（一種特殊的系統(tǒng)調(diào)用）。,在UNIX系統(tǒng)中進(jìn)程控制的系統(tǒng)調(diào)用有： fork() 創(chuàng)建子進(jìn)程 sleep() 進(jìn)程睡眠 exit() 進(jìn)程自已終止（自殺） wait() (父）等待子進(jìn)程終止 wakeup() 進(jìn)程喚醒,1、進(jìn)程的創(chuàng)建,進(jìn)程之間的關(guān)系可以

21、用進(jìn)程圖來描述。,子進(jìn)程可以繼承父進(jìn)程所擁有的資源。撤消父進(jìn)程時必須同時撤消其所有子進(jìn)程。,A,B,C,D,E,E,F,G,進(jìn)程創(chuàng)建系統(tǒng)調(diào)用： create(name,priority,start-addr) UNIX系統(tǒng)： fork(),引起進(jìn)程創(chuàng)建的事件,用戶登陸 作業(yè)調(diào)度 提供服務(wù) 應(yīng)用請求,進(jìn)程的創(chuàng)建過程,申請空白PCB 為新進(jìn)程分配資源 初始化進(jìn)程控制塊 將新進(jìn)程插入就緒隊列,2、進(jìn)程的終止,正常結(jié)束 異常結(jié)束,越界錯誤 保護(hù)錯 特權(quán)指令錯 非法指令錯 運行超時 等待超時 算術(shù)運算錯 I/O故障,外界干預(yù),操作員干預(yù)或操作系統(tǒng)干預(yù) 父進(jìn)程請求 父進(jìn)程終止,進(jìn)程完成其任務(wù)，希望終止時，

22、調(diào)用終止進(jìn)程的系統(tǒng)調(diào)用（進(jìn)程終止原語）終止進(jìn)程。相當(dāng)于一個人死亡后，家人要去派出所消戶口。 在一般操作系統(tǒng)中進(jìn)程終止的系統(tǒng)調(diào)用是：kill UNIX系統(tǒng)中是exit()。,進(jìn)程的終止過程,根據(jù)被終止進(jìn)程的標(biāo)識符，從PCB集合中檢索出 該進(jìn)程的PCB，讀出其狀態(tài)信息。 若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn) 程的執(zhí)行，并設(shè)置調(diào)度標(biāo)志為真。 若該進(jìn)程還有子孫進(jìn)程，應(yīng)將其所有子孫進(jìn)程予 以終止。 將該進(jìn)程所擁有的所有資源，或者歸還給父進(jìn)程， 或者歸還給系統(tǒng)。 將被終止進(jìn)程從所在隊列中移出。,3、進(jìn)程的阻塞與喚醒,引起進(jìn)程阻塞與喚醒的事件,請求系統(tǒng)服務(wù) 啟動某種操作 新數(shù)據(jù)尚未到達(dá) 無新工作可做,

23、進(jìn)程的阻塞過程 正在執(zhí)行的進(jìn)程，當(dāng)出現(xiàn)上述某個事件時，由于無法繼續(xù)執(zhí)行，于是進(jìn)程便通過調(diào)用阻塞原語把自己阻塞，可見，進(jìn)程的阻塞是進(jìn)程自身的一種主動行為。進(jìn)入阻塞過程后，由于進(jìn)程此時還處于執(zhí)行狀態(tài)，所以應(yīng)先立即停止執(zhí)行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為“阻塞”。并把它插入到阻塞隊列（如系統(tǒng)中設(shè)置了因不同事件而阻塞的多個阻塞隊列則應(yīng)將改進(jìn)程插入到具有相同事件的阻塞隊列）。最后轉(zhuǎn)調(diào)度程序進(jìn)行重新調(diào)度，將處理機分配給另一就緒進(jìn)程，并進(jìn)行切換。,進(jìn)程從運行狀態(tài)轉(zhuǎn)換成阻塞狀態(tài)是由進(jìn)程掛起原語實現(xiàn)的，因此，調(diào)用進(jìn)程掛起操作是在進(jìn)程處于運行狀態(tài)下執(zhí)行的。它的執(zhí)行將引起等待某事件的隊列的改變. 例如，進(jìn)程

24、是因等待打印機而進(jìn)入阻塞狀態(tài)，則該進(jìn)程將加入到等待打印機的隊列。進(jìn)程掛起系統(tǒng)調(diào)用的算法和隊列變化如下。,進(jìn)程掛起的內(nèi)部調(diào)用形式（UNIX系統(tǒng)）： sleep(chan,pri) 其中：chan 進(jìn)程掛起（睡眠）的原因； pri 進(jìn)程被喚醒后的優(yōu)先級 一般調(diào)用形式： susp(chan) 其中：chan 進(jìn)程等待的原因,進(jìn)程的喚醒過程 一個正在運行的進(jìn)程會因等待某事件（例如，等待打印機）的發(fā)生，由運行狀態(tài)轉(zhuǎn)換成阻塞狀態(tài)，當(dāng)它等待的事件發(fā)生后，這個進(jìn)程將由阻塞狀態(tài)轉(zhuǎn)換成就緒狀態(tài)。這種轉(zhuǎn)換由進(jìn)程喚醒操作完成。 當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)時，則由有關(guān)進(jìn)程調(diào)用喚醒原語，將等待改事件的進(jìn)程喚醒。喚醒原語

25、的執(zhí)行過程是：首先將被阻塞進(jìn)程從等待該事件的阻塞隊列中移出，將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒，然后再將該進(jìn)程插入到就緒隊列中。 調(diào)用進(jìn)程喚醒操作一般在中斷處理、進(jìn)程通信等過程中。例如，打印機完成中斷處理程序， 在完成了打印完成的操作后，就去檢查等待打印機的隊列，若不為空，則調(diào)用進(jìn)程喚醒操作，喚醒一個（或多個）等待打印機的進(jìn)程。,進(jìn)程喚醒原語的形式： wakeup(chan) 其中：chan 喚醒進(jìn)程阻塞的原因。 算法：wakeup 輸入：chan:等待的事件（阻塞原因） 輸出：無 找到chan的等待隊列的指針； for(該隊列不為空） 從隊列中移出一個進(jìn)程； 置進(jìn)程狀態(tài)為“就緒”，并加入到

26、就緒隊列； ,按此算法，是把等待在chan事件上的所有進(jìn)程喚醒，類似于UNIX系統(tǒng)的處理方式。也有的系統(tǒng)只喚醒一個等待chan事件的進(jìn)程，若這樣處理，等待隊列就要按某種優(yōu)先級排隊。 進(jìn)程喚醒操作會引起就緒隊列和等待chan事件的等待隊列發(fā)生變化。,五、進(jìn)程的調(diào)度,1、什么是進(jìn)程調(diào)度 進(jìn)程調(diào)度的職責(zé)就是根據(jù)一定的算法，從多個就緒進(jìn)程中選擇其一來占用CPU。,2、進(jìn)程調(diào)度的方式 非搶占式（非剝奪方式）：就是某進(jìn)程一旦占用了CPU，除非它自身的原因（如調(diào)用原語操作或等待某事件的發(fā)生）而自動放棄CPU，否則它將一直運行下去。 搶占式（剝奪方式）：某進(jìn)程占用CPU的執(zhí)行過程中，如果出現(xiàn)了一個優(yōu)先級更高的

27、就緒進(jìn)程，則系統(tǒng)將強行中斷正在執(zhí)行的進(jìn)程，而把CPU分配給具有更高優(yōu)先級的就緒進(jìn)程。這種方式反映了進(jìn)程的優(yōu)先級特征。,3、進(jìn)程調(diào)度算法,優(yōu)先數(shù)調(diào)度算法 該算法的基本思想是：系統(tǒng)為每個進(jìn)程設(shè)置一個優(yōu)先數(shù)（對應(yīng)一個優(yōu)先級），調(diào)度時從就緒隊列中選擇優(yōu)先級最高的進(jìn)程投入運行。 靜態(tài)優(yōu)先數(shù)：按進(jìn)程的重要程度為每個進(jìn)程分配一個 優(yōu)先級，該優(yōu)先級在進(jìn)程的整個運行過 程中不再改變。 動態(tài)優(yōu)先數(shù)：進(jìn)程的優(yōu)先數(shù)在其運行時可以改變,先來先服務(wù)調(diào)度算法 該算法按照進(jìn)程進(jìn)入就緒隊列的先后次序來選擇進(jìn)程，使之占用CPU,時間片輪轉(zhuǎn)調(diào)度算法 所有就緒狀態(tài)的進(jìn)程按建立的先后順序形成一個隊列，從隊列首部挑選一個進(jìn)程，并分配一個

28、時間片q，使其投入運行。當(dāng)時間片到而進(jìn)程的工作還未完成時，該進(jìn)程將會再次加入到就緒隊列的隊尾，等待下一輪的調(diào)度。這種方法也稱為簡單輪轉(zhuǎn)法。,對時間片的討論：假定，時間片為q，同時就緒的進(jìn)程數(shù)為N，系統(tǒng)的響應(yīng)時間為T，則它們之間有如下關(guān)系：,可見，如果系統(tǒng)要求的響應(yīng)速度高，即T要小，則 q 也會隨之減少?；蛘哒f，時間片越小，則響應(yīng)速度越高。但 q 的設(shè)定也有個下限，這個下限取決于系統(tǒng)進(jìn)行進(jìn)程切換時所需要的時間。假定進(jìn)程切換需要的時間為，一般來說，q 的值要遠(yuǎn)遠(yuǎn)大于，比如與q的比為1/10。,作為簡單輪轉(zhuǎn)法的延伸，還有一種類似的方法，稱為固定周期輪轉(zhuǎn)法。其基本思想是：在保證系統(tǒng)的響應(yīng)時間不變的前提

29、下，動態(tài)設(shè)定時間片q的大小。,T N q 3 30 0.1 3 6 0.5,注意，每一輪調(diào)度中所得的q值大小，只在這一輪有效。,分級調(diào)度算法 系統(tǒng)將就緒進(jìn)程按其優(yōu)先級高低的不同，設(shè)置兩級或多級隊列，進(jìn)程調(diào)度每次總是先從高優(yōu)先級就緒隊列中挑選進(jìn)程，只有其隊列為空時，才從較低優(yōu)先級就緒隊列中選取。每個隊列中（同一優(yōu)先級就緒進(jìn)程）可按先來先服務(wù)或輪轉(zhuǎn)法進(jìn)行調(diào)度。,帶反饋多級隊列輪轉(zhuǎn)法模型,考慮5個進(jìn)程P1，P2，P3，P4，P5。規(guī)定進(jìn)程的優(yōu)先數(shù)越小，優(yōu)先級越高。進(jìn)程的創(chuàng)建時刻，運行時間和優(yōu)先數(shù)在下面的表中：,試描述在采用各種不同調(diào)度算法時，各個進(jìn)程的運行情況，并計算采用每種調(diào)度算法時的進(jìn)程平均周轉(zhuǎn)時間。忽略進(jìn)程的調(diào)度和進(jìn)程切換時間。,先來先服務(wù)調(diào)度算法進(jìn)程的運行過程如下：,時間片輪轉(zhuǎn)調(diào)度算法（固定時間片為1ms）進(jìn)程的運行過程如下：,P1 P2 P3 P4 P5,非強占式優(yōu)先級調(diào)度算法進(jìn)程的運行過程如下：,P1 P2 P3 P4 P5,強占式優(yōu)先級調(diào)度算法進(jìn)程的運行過程如下：,P1 P2 P3 P4 P5,進(jìn)程的切換（進(jìn)程的調(diào)度時機）,通常，在下列情況下均會引起進(jìn)程調(diào)度程序工作： （1）一個進(jìn)程從運行狀態(tài)變成了等待狀態(tài)。 （2）一個