《操作系統(tǒng)原理》第二章 進(jìn)程管理

1、第二章 進(jìn)程管理,在多道程序批處理系統(tǒng)和分時系統(tǒng)中， 程序并不能獨立運行，操作系統(tǒng)引入 進(jìn)程作為資源分配和獨立運行的基本單位，并按照進(jìn)程的觀點進(jìn)行設(shè)計,現(xiàn)代操作系統(tǒng)的重要特征：程序的并發(fā)性和資源的共享性（這二者是相互聯(lián)系和相互依賴的。） 現(xiàn)代操作系統(tǒng)是圍繞進(jìn)程這個概念設(shè)計和構(gòu)造的。 操作系統(tǒng)必須交替執(zhí)行多個進(jìn)程，以提高處理器的利用率,本章主要內(nèi)容,進(jìn)程的引入和概念 進(jìn)程的描述：進(jìn)程狀態(tài)、PCB 進(jìn)程控制：創(chuàng)建、撤銷、阻塞、喚醒 處理機的調(diào)度 線程的引入,進(jìn)程的引入和概念,程序的順序執(zhí)行 程序： 指令或語句序列的集合，體現(xiàn)了某種算法 所有程序是順序的 程序的順序執(zhí)行：在任何時刻，機器只執(zhí)行一個操

2、作，只有在前一個操作執(zhí)行完后，才能執(zhí)行后繼操作。,程序的順序執(zhí)行,例如：一個有四條語句的程序段： S1: a:=x+2; S2: b:=y+4; S3: c:=a+b; S4: d:=c+b;,S1,S2,S3,S4,程序順序執(zhí)行的特征,順序性：處理機的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每一個操作必須在下一個操作之前結(jié)束。 資源獨占性（封閉性）：運行程序獨占全機資源。系統(tǒng)資源狀態(tài)由運行的這個程序決定和改變。執(zhí)行過程中不受外界因素影響。 結(jié)果無關(guān)性（可再現(xiàn)性）：程序運行結(jié)果與程序執(zhí)行速度無關(guān)，只要環(huán)境和初始條件相同，程序重復(fù)執(zhí)行總能得到相同結(jié)果。,程序順序執(zhí)行優(yōu)缺點,優(yōu)點：由于順序程度的資源獨

3、占性（封閉性）和結(jié)果無關(guān)性（可再現(xiàn)性），為程序員調(diào)試程序帶了很大方便 缺點：由于資源的獨占性，使得系統(tǒng)資源利用率非常低,程序并發(fā)執(zhí)行,并發(fā)處理技術(shù)引入：大大提高了計算機的利用率、運行速度和系統(tǒng)的處理能力。 程序的并發(fā)執(zhí)行：是指若干個程序（或程序段）同時在系統(tǒng)中運行，這些程序（或程序段）的執(zhí)行在時間上是重疊的，一個程序（或程序段）的執(zhí)行尚未結(jié)束，另一個程序（或程序段）的執(zhí)行已經(jīng)開始。,程序并發(fā)執(zhí)行,例如：一個有四條語句的程序段： S1: a:=x+2; S2: b:=y+4; S3: c:=a+b; S4: d:=c+b;,S1,S2,S3,S4,并發(fā)執(zhí)行,程序并發(fā)執(zhí)行的特征,1、失去了程序的封

4、閉性和可再現(xiàn)性 程序在并發(fā)執(zhí)行時，多個程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運行失去了封閉性；由于失去了封閉性，也將導(dǎo)致失去其可再現(xiàn)性。,程序并發(fā)執(zhí)行的特征,例如： 程序A L1: N:=N+1; Goto: L1,程序B L2: PRINT(N); N:=0; Goto: L2,設(shè)共享變量N初值為5，則會產(chǎn)生3種執(zhí)行結(jié)果 1）6，6，0 2）5，0，1 3）5，6，0,程序并發(fā)執(zhí)行的特征,2、并行執(zhí)行的程序間產(chǎn)生了相互制約關(guān)系 因共享資源或協(xié)調(diào)完成同一任務(wù)，使得并發(fā)程序之間發(fā)生了相互制約關(guān)系 間接制約關(guān)系 例：系統(tǒng)中并發(fā)執(zhí)行的程序段A和B在運行過程中都希望

5、使用打印機輸出計算結(jié)果， 若系統(tǒng)只有一臺打印機，分得打印機的程序段(假設(shè)A得到)可以繼續(xù)運行，而沒有得到打印機的程序段B就不得不暫停，等到有可用打印機時才能繼續(xù)執(zhí)行。我們稱這種制約關(guān)系為間接制約關(guān)系 產(chǎn)生間接制約關(guān)系的原因主要是競爭相同資源,程序并發(fā)執(zhí)行的特征,直接 制約關(guān)系 是各個并發(fā)執(zhí)行的程序段之間需要協(xié)調(diào)共同完成同一個任務(wù)引起的。 例如：ps -ef |grep httpd 這兩條命令就需要兩個程序通過管道實現(xiàn)兩者之間協(xié)作完成用戶希望的工作。 在并發(fā)環(huán)境下程序的執(zhí)行是間斷性的： 執(zhí)行-暫停-執(zhí)行,程序并發(fā)執(zhí)行的特征,3、程序與CPU執(zhí)行活動之間不再一一對應(yīng) 程序：是完成某一特定功能的指令

6、或語句序列，是靜態(tài)概念 CPU執(zhí)行的活動：是一個動態(tài)概念，它是程序的執(zhí)行過程。 程序在順序執(zhí)行（即單道運行）時，程序與CPU的活動是一一對應(yīng)的，而在程序并行執(zhí)行（即多道程序）時，這種關(guān)系不再存在。 例：在分時系統(tǒng)中，多個用戶都調(diào)用C編譯對自己的源程序進(jìn)行編譯，實際系統(tǒng)只保留一個編譯程序，為多個用戶進(jìn)行編譯,這里要求編譯程序必須是可再入程序（reentry code） 可再入程序具有這樣的性質(zhì)：它是純代碼，即在執(zhí)行過程中自身不改變?？杀欢鄠€進(jìn)程同時調(diào)用的程序，調(diào)用它的進(jìn)程應(yīng)該提供各自獨立的數(shù)據(jù)區(qū)。 由于并發(fā)程序的上述這些特點，使得系統(tǒng)中的活動以及各種活動之間的相互關(guān)系非常復(fù)雜。 “程序”這個靜態(tài)

7、的概念已不能如實地反映系統(tǒng)中的活動情況。 為此，現(xiàn)代操作系統(tǒng)引入了進(jìn)程的概念,進(jìn) 程,進(jìn)程這個概念是為了描述系統(tǒng)中各并發(fā)活動而引入的。 定義：Process 進(jìn)程是具有獨立功能的程序關(guān)于某個數(shù)據(jù)集合上的一次運行活動，是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨立單位 又稱任務(wù)（Task）,進(jìn)程的特征,動態(tài)性 并發(fā)性 獨立性 異步性 結(jié)構(gòu)特征,進(jìn)程的特征動態(tài)性,進(jìn)程對應(yīng)程序的執(zhí)行，是一個動態(tài)的過程。進(jìn)程是動態(tài)產(chǎn)生，動態(tài)消亡的。 進(jìn)程在其生命周期： 進(jìn)程由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤銷而消亡的過程。,進(jìn)程的特征并發(fā)性、獨立性、異步性,并發(fā)性：多個進(jìn)程同時在內(nèi)存中，且能在一段時間內(nèi)同時運行。 獨立性：進(jìn)程是一個能

8、獨立運行、獨立分配資源、獨立接受調(diào)度的基本單位。 例如：各進(jìn)程的地址空間相互獨立 異步性：每個進(jìn)程都以其相對獨立的、不可預(yù)知的速度向前推進(jìn),進(jìn)程的特征結(jié)構(gòu)特征,進(jìn)程結(jié)構(gòu)特征 進(jìn)程=PCB+程序段+數(shù)據(jù)段,PCB 進(jìn)程控制塊,程序段,數(shù)據(jù)段,動態(tài)特征的集中反映,描述要完成的功能,操作對象及工作區(qū),進(jìn)程和程序的關(guān)系,1）動態(tài)性和靜態(tài)性 進(jìn)程是一個動態(tài)概念，程序是一個靜態(tài)概念。程序可以作為一種軟件資源長期保存 進(jìn)程是把程序作為它的運行實體，沒有程序，也就沒有進(jìn)程。 可以把程序看做菜譜，而進(jìn)程則是按照菜譜進(jìn)行烹飪的過程 2）進(jìn)程控制塊 進(jìn)程由：程序+數(shù)據(jù)+PCB構(gòu)成,進(jìn)程和程序的關(guān)系,3）一對多的關(guān)系

9、 一個程序可對應(yīng)多個進(jìn)程，一個進(jìn)程為多個程序服務(wù) 4）并發(fā)性 多個進(jìn)程實體，能在一段時間內(nèi)同時執(zhí)行；而程序無法描述并發(fā)執(zhí)行 5）進(jìn)程具有創(chuàng)建其他進(jìn)程的功能，而程序沒有 6）操作系統(tǒng)中的每一個程序都是在一個進(jìn)程現(xiàn)場中運行的,進(jìn)程分類,系統(tǒng)進(jìn)程是操作系統(tǒng)管理系統(tǒng)資源并行活動的并發(fā)軟件；用戶進(jìn)程是可以獨立執(zhí)行的用戶程序段。 系統(tǒng)進(jìn)程之間的關(guān)系由操作系統(tǒng)負(fù)責(zé)；用戶進(jìn)程之間的關(guān)系由用戶負(fù)責(zé)。為便于用戶管理自己的任務(wù)，操作系統(tǒng)提供了一套簡便的任務(wù)調(diào)用命令作為協(xié)調(diào)手段。 系統(tǒng)進(jìn)程直接管理有關(guān)的軟、硬設(shè)備的活動；用戶進(jìn)程只能間接和系統(tǒng)資源發(fā)生關(guān)系 系統(tǒng)進(jìn)程優(yōu)先級高于用戶進(jìn)程。,進(jìn)程的描述,進(jìn)程控制塊 進(jìn)程狀態(tài)

10、 進(jìn)程的組織,進(jìn)程控制塊 (Process Control Block),操作系統(tǒng)在管理和控制進(jìn)程時必須知道什么？ 1、進(jìn)程的位置 2、進(jìn)程屬性 進(jìn)程控制塊：與每個進(jìn)程相關(guān)聯(lián)的操作系統(tǒng)用于控制進(jìn)程的所有屬性的集合。PCB是進(jìn)程存在系統(tǒng)中的唯一標(biāo)識。它包含了進(jìn)程的描述信息和管理控制信息，是進(jìn)程動態(tài)特性的集中表現(xiàn)。,PCB內(nèi)容,1、進(jìn)程標(biāo)識符：用于唯一地標(biāo)識一個進(jìn)程。 外部標(biāo)識符：由創(chuàng)建者提供，通常是由字母、數(shù)字所組成，往往是由用戶訪問進(jìn)程時使用，便于記憶。如計算進(jìn)程、打印進(jìn)程、發(fā)送進(jìn)程、接收進(jìn)程等。 內(nèi)部標(biāo)識符：OS為每一個進(jìn)程賦予了一個唯一的整數(shù)，作為內(nèi)部標(biāo)識。父進(jìn)程標(biāo)識符、子進(jìn)程標(biāo)識符、用戶

11、標(biāo)識符。,PCB內(nèi)容（2）,2、進(jìn)程的狀態(tài)：說明進(jìn)程目前所處的狀態(tài)，進(jìn)程可能的狀態(tài)在下一節(jié)描述。 3、CPU現(xiàn)場保護(hù)區(qū)：當(dāng)進(jìn)程由于某種原因不能繼續(xù)運行時，要將其CPU運行的現(xiàn)場信息保存起來，以便下次繼續(xù)運行。通常，CPU的現(xiàn)場信息包括：程序計數(shù)器(PC)、工作寄存器、程序狀態(tài)字等。 4、CPU的調(diào)度信息：包括進(jìn)程優(yōu)先級、進(jìn)程所在各種隊列的指針。 5、進(jìn)程要執(zhí)行的程序在主存和外存起始地址，及存取保護(hù)信息。,PCB內(nèi)容（3）,6、進(jìn)程使用的資源信息：包括分配給進(jìn)程的I/O設(shè)備、正在執(zhí)行的I/O請求信息、當(dāng)前進(jìn)程正打開的文件等。 7、記帳信息：包括CPU占用量，實際所用時間量，帳號等。 8、進(jìn)程之間

12、的家族關(guān)系：在進(jìn)程的樹型結(jié)構(gòu)系統(tǒng)（如UNIX系統(tǒng)）中，進(jìn)程之間存在著家族關(guān)系。創(chuàng)建進(jìn)程的進(jìn)程稱為父進(jìn)程，被創(chuàng)建進(jìn)程稱為子進(jìn)程。,進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換（1）,進(jìn)程的三種基本狀態(tài)：運行狀態(tài)、就緒狀態(tài)和阻塞狀態(tài) 進(jìn)程在生命消亡前處于且僅處于三種基本狀態(tài)之一 不同系統(tǒng)設(shè)置的進(jìn)程狀態(tài)數(shù)目不同,進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換（2）,運行狀態(tài)：進(jìn)程占有CPU，并在CPU上運行；在單處理機系統(tǒng)只有一個進(jìn)程處于執(zhí)行狀態(tài)。多處理機系統(tǒng)則有多個處于執(zhí)行狀態(tài) 就緒狀態(tài)：進(jìn)程已經(jīng)分配了除處理機以外的所有必要資源，只要再獲得處理機就能夠執(zhí)行的狀態(tài)。這樣的進(jìn)程可能有多個，通常排成一個隊列，稱就緒隊列。,進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換（3

13、）,阻塞狀態(tài)：正在執(zhí)行的進(jìn)程由于發(fā)生某事件而暫時無法繼續(xù)運行時，放棄處理機而進(jìn)入的狀態(tài)，又稱等待狀態(tài)、封鎖態(tài)、睡眠態(tài)。 處于阻塞態(tài)的進(jìn)程在邏輯上是不能運行的，即使CPU空閑，該進(jìn)程也不可運行 引起阻塞的事件：請求I/O，申請緩存等。,運行,就緒,阻塞,進(jìn)程調(diào)度程序把處理機分配給進(jìn)程,時間片 已用光,進(jìn)程因某事件(I/O， etc)變成堵塞狀態(tài),某事件被解除 (如I/O完成),就緒態(tài)-運行態(tài)：處于就緒態(tài)的某進(jìn)程被進(jìn)程調(diào)度程序的執(zhí)行選中時。 運行態(tài)-阻塞態(tài)：是由運行進(jìn)程自己主動改變的。 例：一個正在運行的進(jìn)程啟動了某一外圍設(shè)備后，等待該外圍設(shè)備傳輸完成時，使自己由運行態(tài)變?yōu)樽枞麘B(tài)。 阻塞態(tài)-就緒態(tài)

14、：是由外界事件引起的。 例：上面所述的外圍設(shè)備傳輸已經(jīng)完成時，請求中斷，由I/O中斷處理程序把因等待這一I/O完成而阻塞的進(jìn)程變?yōu)榫途w態(tài),由進(jìn)程狀態(tài)轉(zhuǎn)換圖可以看出：,運行態(tài)-就緒態(tài)：處于運行態(tài)的進(jìn)程被剝奪CPU時。例：采用時間片輪轉(zhuǎn)法調(diào)度時，當(dāng)前運行進(jìn)程用完分給它的時間片后，將由運行態(tài)變?yōu)榫途w態(tài)；或采用優(yōu)先級調(diào)度時，若有更高優(yōu)先級的進(jìn)程變?yōu)榫途w態(tài)，當(dāng)前進(jìn)程被迫放棄CPU，使自己由運行態(tài)變?yōu)榫途w態(tài)，之后轉(zhuǎn)進(jìn)程調(diào)度。 由于系統(tǒng)、進(jìn)程自身和外界的原因，可能使一個進(jìn)程多次反復(fù)地經(jīng)歷三個基本狀態(tài)的轉(zhuǎn)換，才能最終達(dá)到完成而撤消。,新狀態(tài)和終止?fàn)顟B(tài) 新狀態(tài)（創(chuàng)建態(tài)）：剛剛建立，還未送入就緒隊列的狀態(tài)。剛創(chuàng)建

15、，并為它分配資源。 終止?fàn)顟B(tài)：已正常結(jié)束或異常結(jié)束，但尚未撤消時。暫留在系統(tǒng)中，以便其它進(jìn)程去收集該進(jìn)程的有關(guān)信息。 創(chuàng)建態(tài)就緒態(tài)：OS準(zhǔn)備好再接納一個進(jìn)程時，把一個進(jìn)程從新建狀態(tài)轉(zhuǎn)換到就緒狀態(tài)。大多數(shù)系統(tǒng)基于現(xiàn)有的進(jìn)程數(shù)或分配給現(xiàn)有進(jìn)程的虛存數(shù)量設(shè)置一些限制，以確保不會因為活躍進(jìn)程的數(shù)量過多而導(dǎo)致系統(tǒng)的性能下降。,進(jìn)程的五種狀態(tài),創(chuàng)建態(tài),運行態(tài),阻塞,終止態(tài),進(jìn)程調(diào)度,被搶占,事件完成,等待事件,進(jìn)程完成,就緒態(tài),Fork(),接納,進(jìn)程控制塊的組織方式,PCB是系統(tǒng)對進(jìn)程進(jìn)行統(tǒng)一管理的依據(jù)。一個系統(tǒng)可有幾十個、幾百個PCB。為了便于系統(tǒng)查找，目前常用的組織方式如下： 1）線性表方式：將所有

16、進(jìn)程的PCB組成一個數(shù)組，系統(tǒng)通過數(shù)組下標(biāo)訪問每一個PCB。其組成方式如下： 優(yōu)點：簡單，節(jié)省存儲空間 缺點：查找一個指定的PCB較費時間，平均要花費半個PCB的時間，早期的UNIX系統(tǒng)就是采用這種形式的表,2、鏈接方式：把具有相同狀態(tài)的PCB，用其中的連接字，鏈接成一個隊列。 每一個隊列有一個專用隊列指針指出該隊列中第一個進(jìn)程PCB所在位置。 這樣就形成了就緒隊列、阻塞隊列。 處于就緒態(tài)的進(jìn)程可按照某種策略排成多個就緒隊列。 處于阻塞態(tài)的進(jìn)程又可以根據(jù)阻塞的原因不同組織成多個阻塞隊列。例如：等待磁盤I/O隊列，等待磁帶I/O隊列等。,PCB1,4,PCB2,3,PCB3,0,PCB4,PCB

17、5,PCB6,PCB7,PCB8,PCB9,PCB10,8,7,9,0,11,執(zhí)行指針,就緒隊列指針,阻塞隊列指針,空閑隊列指針,進(jìn)程控制,進(jìn)程控制,進(jìn)程控制：指系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間轉(zhuǎn)換。這些功能由OS的內(nèi)核來實現(xiàn)的。 原語：由若干條指令組成。這些指令，要么全做，要么全不做，不允許中斷。是不可分割的操作。具有原子操作的性質(zhì)。 用于進(jìn)程控制的原語有：創(chuàng)建原語、撤銷原語、阻塞原語、喚醒原語、掛起原語、解掛原語等等,創(chuàng)建原語,（UNIX系統(tǒng)用fork()系統(tǒng)調(diào)用實現(xiàn)進(jìn)程創(chuàng)建） 1、引起創(chuàng)建進(jìn)程的事件 用戶登錄：在分時系統(tǒng)中，用戶在終端鍵入登錄命令后，系

18、統(tǒng)將為該終端用戶建立一進(jìn)程，并把它插入就緒隊列。 作業(yè)調(diào)度：在批處理系統(tǒng)中，將作業(yè)裝入內(nèi)存時，為它分配必要的資源，系統(tǒng)并立即為它創(chuàng)建進(jìn)程，再插入就緒隊列。 提供服務(wù)：操作系統(tǒng)為用戶提供服務(wù)，如打印服務(wù)、計算服務(wù)等 應(yīng)用請求：完成復(fù)雜的計算等，需要自己創(chuàng)建子進(jìn)程 前三種都是由內(nèi)核完成的。第四種由用戶自己完成,進(jìn)程創(chuàng)建,一旦OS發(fā)現(xiàn)了要求創(chuàng)建新進(jìn)程的事件后，便調(diào)動進(jìn)程創(chuàng)建原語，步驟如下： 1、申請一個空白的PCB，分配唯一的數(shù)字標(biāo)識符。 2、為新進(jìn)程分配資源。為其程序和數(shù)據(jù)，以及用戶棧分配必要的內(nèi)存空間。 3、初始化進(jìn)程控制塊。把調(diào)用者提供的參數(shù)：進(jìn)程名、進(jìn)程優(yōu)先級、實體所在主存的起始地址、所需的

19、資源清單、記帳信息及進(jìn)程家族關(guān)系等填入PCB結(jié)構(gòu)中。 4、將新進(jìn)程插入到就緒隊列中,撤銷原語,撤銷：是指撤消進(jìn)程存在的標(biāo)志(PCB)。 1、引起進(jìn)程終止的事件 正常結(jié)束：進(jìn)程運行完，將產(chǎn)生一個中斷，通知OS進(jìn)程已運行完畢。 異常結(jié)束：進(jìn)程運行期間，出現(xiàn)某些錯誤或故障，而迫使進(jìn)程終止。故障中斷。如越界錯誤、非法指令、等待超時、運行超時、特權(quán)指令錯等 外界干預(yù)： a.操作員或系統(tǒng)干預(yù)。系統(tǒng)員kill進(jìn)程、死鎖 b.父進(jìn)程終止。操作系統(tǒng)將父進(jìn)程終止 c.父進(jìn)程請求。父進(jìn)程有權(quán)終止子進(jìn)程,進(jìn)程撤銷,2、 進(jìn)程的終止過程 根據(jù)被終止進(jìn)程的標(biāo)識符，從PCB集合中檢索出該進(jìn)程的PCB，從中讀出其狀態(tài)。 若正

20、處于執(zhí)行狀態(tài)，則終止，置調(diào)度標(biāo)志為真，待以后重調(diào)度。 若有子孫進(jìn)程，也須終止，以防成為不可控的。 將其全部資源或歸還其父進(jìn)程或歸還系統(tǒng)。 將其PCB從所在隊列中移出，等待其它程序來搜集信息。,進(jìn)程的阻塞與喚醒,1、引起進(jìn)程的阻塞的事件 處于運行狀態(tài)的進(jìn)程，在其執(zhí)行過程中期待某一事件發(fā)生，進(jìn)程自己執(zhí)行阻塞原語，使自己由運行態(tài)變?yōu)樽枞麘B(tài)： 等待鍵盤輸入； 等待磁盤的數(shù)據(jù)傳輸完成； 或等待其它進(jìn)程發(fā)送一個信息等等,2、阻塞過程 中斷CPU. 將其運行現(xiàn)場保存在其PCB中。 置狀態(tài)為阻塞態(tài)。 插入阻塞隊列。 轉(zhuǎn)進(jìn)程調(diào)度。,3、喚醒過程 被阻塞進(jìn)程所期待的事件出現(xiàn)了，則由有關(guān)進(jìn)程調(diào)用喚醒原語將其喚醒。

21、把被阻塞進(jìn)程從阻塞隊列中移出。 將其PCB的現(xiàn)行狀態(tài)改為就緒狀態(tài)。 插入就緒隊列中。,進(jìn)程的掛起和解掛（激活）,1、進(jìn)程的掛起 根據(jù)實際情況的需要，通常引入掛起原語，以便將正在執(zhí)行的或還未執(zhí)行的進(jìn)程掛起一段時間。 2、進(jìn)程的解掛（激活） 當(dāng)掛起進(jìn)程的原因可以被解除時，調(diào)用掛起原語，將被掛起進(jìn)程解掛，使它由靜態(tài)變?yōu)榛顒?處理機調(diào)度,處理機調(diào)度的級別,作業(yè)調(diào)度（Job Scheduler），處理機的高級調(diào)度 進(jìn)程調(diào)度（Process Scheduler），處理機的低級調(diào)度 處理機的交換調(diào)度,進(jìn)程調(diào)度,在多道程序系統(tǒng)中，用戶進(jìn)程數(shù)往往超過處理機數(shù)，另外，操作系統(tǒng)還要建立若干個系統(tǒng)進(jìn)程完成系統(tǒng)功能。

22、多進(jìn)程競爭處理機。將處理機動態(tài)地分配給系統(tǒng)中的各個就緒進(jìn)程，使之執(zhí)行。 由于上述理由，要求實現(xiàn)進(jìn)程調(diào)度。進(jìn)程調(diào)度程序完成分配處理機的任務(wù)。 何時分配CPU，則是調(diào)度時機問題。,進(jìn)程調(diào)度,進(jìn)程調(diào)度：就是系統(tǒng)按照某種算法動態(tài)、合理地把CPU分配給某一就緒進(jìn)程。 進(jìn)程調(diào)度程序：完成進(jìn)程調(diào)度工作的程序。 進(jìn)程調(diào)度的功能 1、記錄系統(tǒng)中各進(jìn)程的執(zhí)行狀況 管理系統(tǒng)中各進(jìn)程的進(jìn)程控制塊，將進(jìn)程的狀態(tài)變化及資源需求情況及時地記錄到進(jìn)程控制塊中。 進(jìn)程調(diào)度程序就是通過PCB變化來準(zhǔn)確地掌握系統(tǒng)中所有進(jìn)程的執(zhí)行情況和狀態(tài)特征的。當(dāng)需要時，從就緒隊列中選出一個進(jìn)程占有CPU。,進(jìn)程調(diào)度的功能（2）,2、根據(jù)進(jìn)程調(diào)度

23、算法分配CPU 按照系統(tǒng)規(guī)定的調(diào)度策略從就緒隊列中選擇一個進(jìn)程讓其占有CPU執(zhí)行，并記錄相關(guān)信息。 進(jìn)程調(diào)度依據(jù)的算法是與系統(tǒng)的設(shè)計目標(biāo)相一致。對于不同的系統(tǒng)，通常采用不同的調(diào)度策略。對于批處理系統(tǒng)常采用短作業(yè)的進(jìn)程優(yōu)先，以減少各作業(yè)的周轉(zhuǎn)時間。對于分時系統(tǒng)，更多地采用時間片輪轉(zhuǎn)。具體算法，下面再具體介紹。,進(jìn)程調(diào)度的功能（3）,3、從進(jìn)程收回處理機 正在運行的進(jìn)程，當(dāng)時間片用完、等待某種資源或者有更高優(yōu)先級的進(jìn)程需要處理機，必須交出處理機。,進(jìn)程調(diào)度方式和調(diào)度時機,根據(jù)執(zhí)行進(jìn)程的處理機是由進(jìn)程自己釋放，還是被強行剝奪，可以將進(jìn)程調(diào)度方式分為以下兩種： 非剝奪式(Non preemptive

24、mode) 不可搶占式 剝奪式(Preemptive mode) 搶占式,1、非剝奪方式 一旦把CPU分配給某一進(jìn)程后,便讓它一直運行下去，直到進(jìn)程完成或發(fā)生某事件而不能運行時，才將CPU分給其它進(jìn)程。 該方式通常用在批處理系統(tǒng)中。 主要優(yōu)點是簡單、系統(tǒng)開銷小。,2、剝奪方式 允許調(diào)度程序基于某種策略（優(yōu)先級策略、時間片策略等）剝奪現(xiàn)行進(jìn)程的CPU給其它進(jìn)程。 該方式通常用在分時系統(tǒng)和實時系統(tǒng)中，以便及時響應(yīng)各進(jìn)程的請求。,進(jìn)程調(diào)度的時機：是指什么情況下引起進(jìn)程調(diào)度程序工作。 現(xiàn)行進(jìn)程完成或錯誤終止； 現(xiàn)行進(jìn)程提出I/O請求，等待I/O完成時，轉(zhuǎn)進(jìn)程調(diào)度； 在分時系統(tǒng)，按照時間片輪轉(zhuǎn)，分給進(jìn)程

25、的時間片用完時； 優(yōu)先級調(diào)度時，有更高優(yōu)先級進(jìn)程變?yōu)榫途w時； 在進(jìn)程通訊中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語操作，如P操作、阻塞原語和喚醒原語時，都可能引起進(jìn)程調(diào)度。,進(jìn)程調(diào)度的時機,進(jìn)程調(diào)度算法,所采用的進(jìn)程調(diào)度算法是與整個系統(tǒng)的設(shè)計目標(biāo)相一致的。 在批處理系統(tǒng)中，系統(tǒng)的設(shè)計目標(biāo)是增加系統(tǒng)吞吐量和提高系統(tǒng)資源的利用率； 分時系統(tǒng)則保證每個分時用戶能容忍的響應(yīng)時間。 因此，進(jìn)程調(diào)度通常采用如下一些算法。,進(jìn)程調(diào)度算法,先來先服務(wù)(FCFS) 短作業(yè)優(yōu)先（SJF） 響應(yīng)比高者優(yōu)先（HRN） 輪轉(zhuǎn)調(diào)度 優(yōu)先級法： 優(yōu)先占有法：只要不是自身原因被堵塞，就一直運行 優(yōu)先剝奪法：CPU以剝奪的方式被更高優(yōu)先級

26、進(jìn)程占用 分級輪轉(zhuǎn)調(diào)度,進(jìn)程調(diào)度算法- 先來先服務(wù)（FCFS）,該方法按照進(jìn)程到達(dá)的先后順序排隊，每次調(diào)度隊首的進(jìn)程。 FCFS算法屬于非剝奪調(diào)度方式，實現(xiàn)簡單，看似公平。 但，對于那些后進(jìn)入隊列而運行時間較短的進(jìn)程，或I/O型的進(jìn)程而言，可能需要長時間等待。,先來先服務(wù)（FCFS）,短作業(yè)優(yōu)先（SJF）,該方法要求每個作業(yè)的進(jìn)程提供所需的運行時間，每次調(diào)度時總是選取運行時間最短的進(jìn)程運行 核心思想：保證響應(yīng)時間最快、平均周轉(zhuǎn)時間最短 優(yōu)點：保證了CPU的利用效率 缺點：無法通用，約束條件多，可能使得長進(jìn)程沒有機會運行。,響應(yīng)比高者優(yōu)先（HRN）,當(dāng)調(diào)度作業(yè)時，都要計算各個作業(yè)的響應(yīng)比，總是選

27、擇響應(yīng)比高的作業(yè)運行。 Rp=（作業(yè)等待時間+作業(yè)估計運行時間）/作業(yè)估計運行時間=1+作業(yè)等待時間/作業(yè)估計運行時間 在通常情況下，優(yōu)先運行短作業(yè)，當(dāng)長作業(yè)等待時間足夠長時，它也就變?yōu)榭蓛?yōu)先運行的作業(yè)了。,時間片輪轉(zhuǎn)調(diào)度法,在分時聯(lián)機系統(tǒng)中，n個進(jìn)程循環(huán)地獲得時間片而執(zhí)行。從系統(tǒng)中來看它們是交替執(zhí)行的，但就每個終端用戶而言，都感覺到自己獨占了一臺主機，不受其他用戶的影響。這是通過進(jìn)程并發(fā)執(zhí)行實現(xiàn)的。 如果用戶數(shù)太多，主機處理的進(jìn)程將會急劇增加，進(jìn)程排隊等待的時間也會很長，進(jìn)程的響應(yīng)時間也可能增長，用戶將明顯感覺到主機的速度變慢而不滿意。 另外，時間片的大小也會影響進(jìn)程的響應(yīng)時間。,基于時間片

28、輪轉(zhuǎn)調(diào)度,主機,終端1,終端2,終端n,一個基于時間片輪轉(zhuǎn)調(diào)度的聯(lián)機系統(tǒng),輪轉(zhuǎn)調(diào)度,最初的隊列形成可按照FCFS或者按照優(yōu)先級排隊 為每個進(jìn)程分配一個時間片，輪流運行,P1,P2,鏈頭,Pn,中斷現(xiàn)場保護(hù)區(qū),中斷現(xiàn)場保護(hù)區(qū),中斷現(xiàn)場保護(hù)區(qū),基于優(yōu)先級的調(diào)度算法,當(dāng)發(fā)生進(jìn)程調(diào)度時，將CPU分配給就緒隊列中優(yōu)先級最高的進(jìn)程。 靜態(tài)優(yōu)先級：在進(jìn)程創(chuàng)建時確定的，運行時保持不變。通常賦予系統(tǒng)進(jìn)程較高優(yōu)先級；申請資源量少的賦予較高優(yōu)先級。 優(yōu)點：簡單，系統(tǒng)調(diào)度性能差 動態(tài)優(yōu)先級：進(jìn)程的優(yōu)先級可隨著進(jìn)程的推進(jìn)而改變，以便獲得更好的調(diào)度性能。 通常根據(jù)進(jìn)程占用CPU時間的長短或等待CPU時間的長短動態(tài)調(diào)整。（

29、如：UNIX系統(tǒng)進(jìn)程優(yōu)先級是采用這種方法實現(xiàn)的。占用CPU時間長的優(yōu)先級低）,進(jìn)程的優(yōu)先級的確定條件- 靜態(tài)優(yōu)先級,進(jìn)程類型： 系統(tǒng)進(jìn)程/用戶進(jìn)程； 前臺進(jìn)程/后臺進(jìn)程； 聯(lián)機進(jìn)程/脫機進(jìn)程 運行時間：通常規(guī)定進(jìn)程優(yōu)先級與進(jìn)程所需運行時間成反比 作業(yè)的優(yōu)先級：根據(jù)作業(yè)的優(yōu)先級來決定其所屬進(jìn)程的優(yōu)先級,進(jìn)程的優(yōu)先級的確定條件-動態(tài)優(yōu)先級,進(jìn)程在運行過程中的優(yōu)先級會發(fā)生變化 I/O頻繁的作業(yè)/計算頻繁的作業(yè) 已經(jīng)使用了CPU較多的作業(yè)/剛提交的作業(yè),系統(tǒng)的響應(yīng)時間 就緒隊列中進(jìn)程的數(shù)目 進(jìn)程狀態(tài)轉(zhuǎn)換的時間開銷 計算機本身的處理能力,時間片長短的決定因素,分級輪轉(zhuǎn)法,分級輪轉(zhuǎn)法就是將先前的一個就緒隊

30、列，根據(jù)進(jìn)程的優(yōu)先級不同，劃分二個或二個以上的就緒隊列，并賦給每個隊列不同的優(yōu)先級。,分級輪轉(zhuǎn)法,輪轉(zhuǎn),鏈頭指針,FCFS,最高優(yōu)先級,最低優(yōu)先級,次高優(yōu)先級,調(diào)度時的進(jìn)程狀態(tài)變遷圖,運行,低優(yōu)先數(shù) 就緒,高優(yōu)先數(shù) 就緒,等待I/O而 阻塞,超過時間片,其次選擇,首先選擇,請求I/O,I/O完成,線程的概念（thread),1、進(jìn)程的弊端 引入進(jìn)程的目的：為了使多個程序并發(fā)執(zhí)行，以改善資源利用率及提高系統(tǒng)吞吐量。 進(jìn)程的兩個基本屬性：進(jìn)程是一個可擁有資源的獨立單位；進(jìn)程同時又是一個可以獨立調(diào)度和分派的基本單位。 進(jìn)程數(shù)目不宜過多，進(jìn)程切換的頻率也不宜過高。進(jìn)程是一個資源擁有者，因而在進(jìn)程的創(chuàng)建

31、、撤消和切換中，系統(tǒng)必須為了付出較大的時空開銷。因而限制了并發(fā)程度的進(jìn)一步提高。,線 程,2、線程的引入 為了減少程序并發(fā)執(zhí)行時系統(tǒng)付出的時空開銷，使操作系統(tǒng)更加有效。80年代引入了線程。 MS-DOS是一種支持單用戶進(jìn)程和單線程的OS；UNIX支持多用戶進(jìn)程，但只支持每個進(jìn)程一個線程；支持多線程的多進(jìn)程的包括Windows 2000、Solaris、Linux、OS/2等 將進(jìn)程的資源的擁有者和調(diào)度和分派的基本單位拆分開。即讓進(jìn)程只作為資源的擁有者（即可、資源的容器），而讓線程作為CPU調(diào)度和分派單位。,線 程（2）,每個進(jìn)程由若干代碼和數(shù)據(jù)塊組成，此外它還擁有文件、主存以及至少一個線程。 進(jìn)程被創(chuàng)建時，系統(tǒng)同時為進(jìn)程創(chuàng)建第一個線程。進(jìn)程中的其它線程是通過調(diào)用線程創(chuàng)建原語顯式創(chuàng)建；一線程可創(chuàng)建和撤消另一線程。 線程是進(jìn)程中的一個執(zhí)行單位。同一進(jìn)程中的各個線程分別有一組CPU指令、一組CPU寄存器和一個堆棧。它們共享進(jìn)程的主存和文