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

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

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

3、。只要程序的初始條件相同，它的執(zhí)行結(jié)果是相同的，即只要程序執(zhí)行時的環(huán)境和初始條件相同，當程序多次重復執(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í)行必須嚴格按照I1，C1，P1的順序，而P1與I2，C1與I2,I3與P1是可以同時執(zhí)行的。,若干個程序段同時在系統(tǒng)中運行，這些程序的執(zhí)行

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

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

6、就無法進一步進行處理，致使計算程序暫停運行。一旦使計算程序暫停的因素消失后（如輸入程序已完成了下一批數(shù)據(jù)的輸入后），計算程序便可恢復執(zhí)行。這樣的相互制約將導致井發(fā)程序具有“執(zhí)行一暫停執(zhí)行一執(zhí)行”這種間斷性的活動規(guī)律。 失去封閉性 程序在并發(fā)執(zhí)行時，是多個程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運行失去了封閉性。這樣，某程序在執(zhí)行時，必然受到其他程序的影響。 不可再現(xiàn)性 程序再并發(fā)執(zhí)行時，由于失去的并發(fā)性，也將導致失去可再現(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；,在多道進程設(shè)計的系統(tǒng)中，對多道并行執(zhí)行的程序來說，一個程序的執(zhí)行還可能受到另一個程序的約束，所以，程序的執(zhí)行實際上是走走停停的。為了能正確地反映程序的活動規(guī)

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

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

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

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

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

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

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

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

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

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

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

19、狀態(tài)進一步細分成若干更多的狀態(tài)。例如，在UNIX操作系統(tǒng)中，進程的狀態(tài)被分成六種。當然，狀態(tài)被細分后，狀態(tài)轉(zhuǎn)換關(guān)系相應地也要更復雜一些。,四、進程的控制,進程是有生命周期的，產(chǎn)生、運行、暫停、終止。對進程的這些操作叫進程控制。 進程控制的職責是對系統(tǒng)中全部進程實施有效的管理，它是處理機管理的部分（另一部分是進程調(diào)度），當系統(tǒng)允許多進程并發(fā)執(zhí)行時，為了實現(xiàn)共享、協(xié)調(diào)并發(fā)進程的關(guā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)得到了保護。操作系統(tǒng)運行在系統(tǒng)態(tài)。,進程控制包括： 進程創(chuàng)建 進程撤消 進程阻塞 進程喚醒 這些操作都要對應地執(zhí)行一個特殊的程序段（操作系統(tǒng)核心程序），同時系統(tǒng)也通過系統(tǒng)調(diào)用給用戶提供進程控制的功能。教材上叫原語（一種特殊的系統(tǒng)調(diào)用）。,在UNIX系統(tǒng)中進程控制的系統(tǒng)調(diào)用有： fork() 創(chuàng)建子進程 sleep() 進程睡眠 exit() 進程自已終止（自殺） wait() (父）等待子進程終止 wakeup() 進程喚醒,1、進程的創(chuàng)建,進程之間的關(guān)系可以

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

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

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

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

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

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

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

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

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