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

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

3、占性（封閉性）和結(jié)果無(wú)關(guān)性（可再現(xiàn)性），為程序員調(diào)試程序帶了很大方便 缺點(diǎn)：由于資源的獨(dú)占性，使得系統(tǒng)資源利用率非常低,程序并發(fā)執(zhí)行,并發(fā)處理技術(shù)引入：大大提高了計(jì)算機(jī)的利用率、運(yùn)行速度和系統(tǒng)的處理能力。 程序的并發(fā)執(zhí)行：是指若干個(gè)程序（或程序段）同時(shí)在系統(tǒng)中運(yùn)行，這些程序（或程序段）的執(zhí)行在時(shí)間上是重疊的，一個(gè)程序（或程序段）的執(zhí)行尚未結(jié)束，另一個(gè)程序（或程序段）的執(zhí)行已經(jīng)開始。,程序并發(fā)執(zhí)行,例如：一個(gè)有四條語(yǔ)句的程序段： 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í)行時(shí)，多個(gè)程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個(gè)程序來(lái)改變，致使程序的運(yùn)行失去了封閉性；由于失去了封閉性，也將導(dǎo)致失去其可再現(xiàn)性。,程序并發(fā)執(zhí)行的特征,例如： 程序A L1: N:=N+1; Goto: L1,程序B L2: PRINT(N); N:=0; Goto: L2,設(shè)共享變量N初值為5，則會(huì)產(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在運(yùn)行過(guò)程中都希望

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

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

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

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

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

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

11、標(biāo)識(shí)符。,PCB內(nèi)容（2）,2、進(jìn)程的狀態(tài)：說(shuō)明進(jìn)程目前所處的狀態(tài)，進(jìn)程可能的狀態(tài)在下一節(jié)描述。 3、CPU現(xiàn)場(chǎng)保護(hù)區(qū)：當(dāng)進(jìn)程由于某種原因不能繼續(xù)運(yùn)行時(shí)，要將其CPU運(yùn)行的現(xiàn)場(chǎng)信息保存起來(lái)，以便下次繼續(xù)運(yùn)行。通常，CPU的現(xiàn)場(chǎng)信息包括：程序計(jì)數(shù)器(PC)、工作寄存器、程序狀態(tài)字等。 4、CPU的調(diào)度信息：包括進(jìn)程優(yōu)先級(jí)、進(jìn)程所在各種隊(duì)列的指針。 5、進(jìn)程要執(zhí)行的程序在主存和外存起始地址，及存取保護(hù)信息。,PCB內(nèi)容（3）,6、進(jìn)程使用的資源信息：包括分配給進(jìn)程的I/O設(shè)備、正在執(zhí)行的I/O請(qǐng)求信息、當(dāng)前進(jìn)程正打開的文件等。 7、記帳信息：包括CPU占用量，實(shí)際所用時(shí)間量，帳號(hào)等。 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)：運(yùn)行狀態(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）,運(yùn)行狀態(tài)：進(jìn)程占有CPU，并在CPU上運(yùn)行；在單處理機(jī)系統(tǒng)只有一個(gè)進(jìn)程處于執(zhí)行狀態(tài)。多處理機(jī)系統(tǒng)則有多個(gè)處于執(zhí)行狀態(tài) 就緒狀態(tài)：進(jìn)程已經(jīng)分配了除處理機(jī)以外的所有必要資源，只要再獲得處理機(jī)就能夠執(zhí)行的狀態(tài)。這樣的進(jìn)程可能有多個(gè)，通常排成一個(gè)隊(duì)列，稱就緒隊(duì)列。,進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換（3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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