第8章處理器管理

1、第8章處理器管理本章基本內(nèi)容與要求基本內(nèi)容作業(yè)的概念進(jìn)程的概念進(jìn)程狀態(tài)及進(jìn)程控制處理機(jī)調(diào)度進(jìn)程的同步和互斥死鎖問題要求掌握進(jìn)程的概念及作用掌握進(jìn)程的控制與調(diào)度方法掌握進(jìn)程的同步與互斥、P、V操作掌握死鎖的概念和死鎖的解決方法 8.1 作業(yè)的概念一、作業(yè)的定義作業(yè)是用戶在一次算題過(guò)程中或一個(gè)事務(wù)處理中要求計(jì)算機(jī)系統(tǒng)所做的工作的集合。二、作業(yè)的組成作業(yè)由程序、數(shù)據(jù)和作業(yè)說(shuō)明書組成 。三、作業(yè)的狀態(tài)1）提交狀態(tài)2）收容狀態(tài) 3）執(zhí)行狀態(tài) 4）完成狀態(tài)8.2 進(jìn)程的概念一、程序的順序執(zhí)行 二、程序并發(fā)執(zhí)行與資源共享 三、并發(fā)執(zhí)行的特征 四、進(jìn)程的引入和描述五、進(jìn)程的狀態(tài)及其變遷六、進(jìn)程的組成8.2 進(jìn)

2、程的概念一、程序的順序執(zhí)行程序：一個(gè)在時(shí)間上按嚴(yán)格次序，前后相繼的操作序列。體現(xiàn)的是程序員要求的順序步驟。順序執(zhí)行：一個(gè)具有獨(dú)立功能的程序獨(dú)占處理機(jī)直至得到最終結(jié)果的過(guò)程。1.例：S1： a=x+y S2： b=a-5 S3： c=b+12. 特點(diǎn)：順序性：上一條指令執(zhí)行結(jié)束是下一條指令開始的充要條件。封閉性：由于資源獨(dú)占，執(zhí)行結(jié)果取決于程序本身，由給定初始條件決定，不受外界影響?？稍佻F(xiàn)性：同一數(shù)據(jù)集上重復(fù)執(zhí)行同一程序，結(jié)果相同，與執(zhí)行速度無(wú)關(guān)。OIC S1S2S3二、程序并發(fā)執(zhí)行和資源共享1.并發(fā)執(zhí)行：邏輯上獨(dú)立的一組程序在執(zhí)行時(shí)間上相互重疊在多處理機(jī)的情況下，若干個(gè)程序在各自處理機(jī)上運(yùn)行，

3、其執(zhí)行的時(shí)間是重疊的；在單處理機(jī)的情況下，這些并發(fā)程序按給定的時(shí)間片交替地在處理機(jī)上執(zhí)行為了提高系統(tǒng)處理能力和資源利用率而采取的一種在某一時(shí)段同時(shí)操作的技術(shù)。并發(fā)：幾道程序分時(shí)地運(yùn)行在同一個(gè)處理機(jī)(CPU)上；并行：幾道程序同時(shí)在不同的處理機(jī)(CPU)上執(zhí)行。8.2 進(jìn)程的概念二、程序并發(fā)執(zhí)行和資源共享2.例：輸入程序、計(jì)算程序、打印程序之間，存在有IiCiPi的前趨關(guān)系，但不存在PiIi+1關(guān)系，這樣他們可以并發(fā)執(zhí)行。二、程序并發(fā)執(zhí)行和資源共享S1: a:=x+2S2: b:=y+4S3: z:=a+bS4: w:=z+9三、并發(fā)執(zhí)行的特征1. 資源的爭(zhēng)奪與共享多個(gè)并發(fā)程序申請(qǐng)同一資源資源動(dòng)

4、態(tài)分配，資源狀態(tài)由多道程序活動(dòng)共同決定程序運(yùn)行不再具有封閉性和可再現(xiàn)性2.并發(fā)執(zhí)行的程序之間的相互約束性共享計(jì)算機(jī)的資源而相互制約互相通信協(xié)作完成同一任務(wù),相互依賴相互制約活動(dòng)規(guī)律（間斷性）：執(zhí)行暫停執(zhí)行8.2 進(jìn)程的概念8.2 進(jìn)程的概念3. 特性間斷性：程序具有“執(zhí)行-暫停-執(zhí)行”規(guī)律；失去封閉性：系統(tǒng)資源的狀態(tài)由多個(gè)程序決定，因此，程序的執(zhí)行受其它程序的影響。不可再現(xiàn)性：執(zhí)行結(jié)果與并發(fā)程序的相對(duì)速度有關(guān)。結(jié)論：程序的概念已無(wú)法描述多道環(huán)境中程序動(dòng)態(tài)執(zhí)行過(guò)程中的并發(fā)活動(dòng)引入一個(gè)新的概念來(lái)描述，這就是進(jìn)程四、進(jìn)程的引入和描述1. 進(jìn)程：程序在并發(fā)環(huán)境中的執(zhí)行過(guò)程。是系統(tǒng)進(jìn)行資源分配和調(diào)度的一

5、個(gè)獨(dú)立基本單位和實(shí)體進(jìn)程是程序的一次執(zhí)行進(jìn)程是可以和別的計(jì)算并發(fā)執(zhí)行的計(jì)算進(jìn)程可以定義為一個(gè)數(shù)據(jù)結(jié)構(gòu)，能在其上進(jìn)行操作進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上允許過(guò)程，是系統(tǒng)資源分配和調(diào)度的一個(gè)獨(dú)立單位?？刹l(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集合上的執(zhí)行過(guò)程。8.2 進(jìn)程的概念四、進(jìn)程的引入和描述2.進(jìn)程與程序間的區(qū)別和聯(lián)系1）區(qū)別：程序：是一組有序的指令，是一種靜態(tài)的概念；(劇本)進(jìn)程：是一次運(yùn)行的活動(dòng)，是動(dòng)態(tài)的概念 (演出) 一個(gè)進(jìn)程可以執(zhí)行一個(gè)或多個(gè)程序反之一個(gè)程序也可能被多個(gè)進(jìn)程執(zhí)行程序可作為一種資源，以文件的形式長(zhǎng)期保存；而進(jìn)程只是一次執(zhí)行過(guò)程，具有生命

6、期2）聯(lián)系進(jìn)程不能脫離具體程序而虛設(shè)程序規(guī)定了相應(yīng)進(jìn)程所要完成的動(dòng)作四、進(jìn)程的引入和描述3. 進(jìn)程的基本特征1)動(dòng)態(tài)性程序的一次執(zhí)行過(guò)程，具有生命期由系統(tǒng)創(chuàng)建并獨(dú)立的執(zhí)行，執(zhí)行過(guò)程中可能被暫時(shí)掛起，條件滿足時(shí)又繼續(xù)執(zhí)行，直至完成而被撤銷。2)并發(fā)性不同進(jìn)程的動(dòng)作在時(shí)間上可以重疊;由于共享資源，進(jìn)程間相互約束。3)獨(dú)立性程序和數(shù)據(jù)集合的實(shí)體；系統(tǒng)分配資源,處理機(jī)調(diào)度運(yùn)行的基本單位；各進(jìn)程間相互獨(dú)立4)異步性各進(jìn)程按各自獨(dú)立的，不可預(yù)知的速度異步向前推進(jìn)。五、進(jìn)程的狀態(tài)及其變遷進(jìn)程的基本狀態(tài)運(yùn)行態(tài)：指進(jìn)程已獲得處理機(jī)，其程序正在執(zhí)行。進(jìn)程數(shù)CPU數(shù)就緒態(tài)：當(dāng)進(jìn)程已分配到除CPU以外的所有必要資源，

7、一旦獲得CPU，便可立即執(zhí)行。等待（封鎖）態(tài)：進(jìn)程因等待某個(gè)事件的發(fā)生而暫停執(zhí)行創(chuàng)建狀態(tài)：一個(gè)進(jìn)程剛建立，還未進(jìn)入就緒態(tài)。終止?fàn)顟B(tài)：一個(gè)進(jìn)程已經(jīng)正?；虍惓＝Y(jié)束，被移除就緒隊(duì)列但尚未撤銷。8.2 進(jìn)程的概念計(jì)算機(jī)軟件技術(shù)基礎(chǔ)進(jìn)程管理五、進(jìn)程的狀態(tài)及其變遷2. 進(jìn)程狀態(tài)轉(zhuǎn)換就緒執(zhí)行等待進(jìn)程調(diào)度時(shí)間片到等待事件發(fā)生事件發(fā)生獲得資源提交撤消完成六、進(jìn)程的組成組成： 程序、數(shù)據(jù)集合、PCB統(tǒng)稱為進(jìn)程映象。程序：描述進(jìn)程所要完成的功能；數(shù)據(jù)集合：程序運(yùn)行所需數(shù)據(jù)和工作區(qū)；PCB：描述進(jìn)程的外部特征以及與其它進(jìn)程的通信關(guān)系的數(shù)據(jù)結(jié)構(gòu)。系統(tǒng)定義的一種數(shù)據(jù)結(jié)構(gòu)，是進(jìn)程存在的唯一標(biāo)志。描述和記錄進(jìn)程執(zhí)行的情況和狀

8、態(tài)變化。便于系統(tǒng)控制和描述進(jìn)程的活動(dòng)過(guò)程。PCB程序數(shù)據(jù)集常駐內(nèi)存8.2 進(jìn)程的概念2. PCB的作用 OS是根據(jù)PCB來(lái)對(duì)并發(fā)進(jìn)程執(zhí)行的進(jìn)程實(shí)施控制和管理。 (1)保存進(jìn)程的ID、進(jìn)程狀態(tài)、優(yōu)先級(jí)。 (2)現(xiàn)場(chǎng)保存與恢復(fù) (3)OS根據(jù)PCB對(duì)進(jìn)程實(shí)施調(diào)度。新進(jìn)程：OS為該進(jìn)程創(chuàng)建一個(gè)PCB結(jié)束： OS回收該進(jìn)程的PCB。六、進(jìn)程的組成3. PCB的內(nèi)容包含的信息類型和數(shù)量隨操作系統(tǒng)而不同一般分為調(diào)度信息和現(xiàn)場(chǎng)信息兩個(gè)部分1）調(diào)度信息：描述進(jìn)程的當(dāng)前狀況； 進(jìn)程名、當(dāng)前狀態(tài)、優(yōu)先級(jí)、資源清單、 家族關(guān)系、隊(duì)列指針 等，供進(jìn)程調(diào)度時(shí)使用。2）現(xiàn)場(chǎng)信息：刻劃進(jìn)程運(yùn)行的情況進(jìn)程在運(yùn)行過(guò)程中會(huì)改變的

9、寄存器，如程序狀態(tài)字，指針，地址寄存器。一旦進(jìn)程的執(zhí)行過(guò)程被中斷，必須立即將中斷時(shí)的內(nèi)容記入現(xiàn)場(chǎng)信息。六、進(jìn)程的組成4. PCB的物理組織方式PCB表：所有PCB按一定的方式組織起來(lái)的結(jié)構(gòu)。1）順序表：由OS預(yù)先分配空間，在內(nèi)存中順序地存放每個(gè)PCB。優(yōu)點(diǎn)：簡(jiǎn)單易實(shí)現(xiàn)，不必進(jìn)行復(fù)雜的申請(qǐng)/釋放。缺點(diǎn)：限制了系統(tǒng)中同時(shí)存在的進(jìn)程數(shù)；降低了調(diào)度效率（掃描整個(gè)表）；內(nèi)存浪費(fèi)（用戶少）2）鏈接表：按不同狀態(tài)進(jìn)程的PCB形成不同單鏈表，各單鏈表內(nèi)按FIFO運(yùn)行；優(yōu)點(diǎn)：進(jìn)程數(shù)目可隨機(jī)應(yīng)變；缺點(diǎn)：算法復(fù)雜。六、進(jìn)程的組成8.3 進(jìn)程的同步和互斥一、相關(guān)概念二、信號(hào)量和P、V原語(yǔ)三、用P、V原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥

10、四、用P、V原語(yǔ)操作實(shí)現(xiàn)簡(jiǎn)單同步 五、P、V原語(yǔ)在進(jìn)程同步/互斥問題中的應(yīng)用 一、相關(guān)概念臨界資源：一次只允許一個(gè)進(jìn)程使用的資源。臨界區(qū)：在每個(gè)進(jìn)程中，訪問臨界資源的那段程序稱為臨界區(qū)。 直接制約與同步：一組在異步環(huán)境下的并發(fā)進(jìn)程，各自的執(zhí)行結(jié)果互為對(duì)方的執(zhí)行條件，從而限制各進(jìn)程的執(zhí)行速度的過(guò)程稱為并發(fā)進(jìn)程間的直接制約。進(jìn)程因直接制約而進(jìn)行互相合作、互相等待并按一定速度執(zhí)行的過(guò)程稱為進(jìn)程間的同步。間接制約與互斥：由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進(jìn)程交叉執(zhí)行的現(xiàn)象，稱并發(fā)進(jìn)程間的間接制約。并發(fā)進(jìn)程之間的間接制約關(guān)系稱為進(jìn)程的互斥。例 X=COUNTX=X+1 COUNT=XY=C

11、OUNTY=Y+1 COUNT=Y臨界區(qū)進(jìn) 程 A進(jìn) 程 B 若進(jìn)程A與B對(duì)公共變量COUNT進(jìn)行互斥操作，最終實(shí)現(xiàn)COUNT增加2。臨界區(qū)A: X=COUNT;B: Y=COUNT;A: X=X+1; COUNT=X;B: Y=Y+1; COUNT=Y; 若A與B按右面順序推進(jìn)，結(jié)果COUNT只實(shí)現(xiàn)增加1。二、信號(hào)量和P，V原語(yǔ) 1.信號(hào)量S：是一個(gè)整型變量S0時(shí)，表示該類臨界資源的可用個(gè)數(shù)。S0時(shí)，表示等待使用該類臨界資源的進(jìn)程個(gè)數(shù)。 信號(hào)量只能通過(guò)P操作和V操作來(lái)訪問。2. P原語(yǔ)(1)信號(hào)量減1；(2)若信號(hào)量減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行。(3)若信號(hào)量減1后小于0，則該進(jìn)程被

12、阻塞后進(jìn)入與該信號(hào)相對(duì)應(yīng)的等待隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度程序，調(diào)度另一個(gè)處于就緒狀態(tài)的進(jìn)程占用CPU。二、信號(hào)量和P，V原語(yǔ) 3. V原語(yǔ)(1)信號(hào)量加1；(2)若信號(hào)量相加結(jié)果大于零，說(shuō)明沒有其它進(jìn)程等待使用該資源，則當(dāng)前進(jìn)程繼續(xù)執(zhí)行。(3)信號(hào)量相加結(jié)果小于或等于零，說(shuō)明此時(shí)尚有其它進(jìn)程等待使用該資源，則從該信號(hào)的等待隊(duì)列中喚醒一個(gè)等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。三、用P，V原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥 P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)Y=COUNTY=Y+1COUNT=Y臨界區(qū)V(S)P(S)進(jìn)程BX=CO

13、UNTX=X+1COUNT=X臨界區(qū)V(S)P(S)進(jìn)程AS=1 進(jìn)程P1 L1:P(s) 獲取信息 進(jìn)程P2 產(chǎn)生信息L2:V(s) 同步條件S=0同步點(diǎn)四、用P，V原語(yǔ)操作實(shí)現(xiàn)簡(jiǎn)單同步 1.用P，V操作描述前趨關(guān)系五、P、V原語(yǔ)在進(jìn)程同步/互斥問題中的應(yīng)用int f2=0,f3=0,f4=0,f5=0,f6=0;void main() cobegin P1();P2();P3();P4();P5(); coend P1() . v(f2);v(f3); P2() p(f2); . v(f4);v(f5); P3() p(f3); . v(f6); P4() p(f4); . v(f6);

14、P5() p(f5); . v(f6); P6() p(f6); 123NP1P2P3PmC1C2C3Cn有 界 緩 沖 池生產(chǎn)者消費(fèi)者五、P、V原語(yǔ)在進(jìn)程同步/互斥問題中的應(yīng)用2.生產(chǎn)者消費(fèi)者問題 同步條件：當(dāng)有界緩沖區(qū)中至少有一個(gè)單元是滿的時(shí)，消費(fèi)者才能接收數(shù)據(jù)；當(dāng)有界緩沖區(qū)中至少有一個(gè)單元是空的時(shí)，生產(chǎn)者才能發(fā)送數(shù)據(jù) ?；コ鈼l件：有界緩沖區(qū)是臨界資源，必須互斥使用 。設(shè)置信號(hào)量：互斥信號(hào)量Mutex：初值為1。 同步信號(hào)量Full ：初值為0。 同步信號(hào)量Empty ：初值為n。 生產(chǎn)者進(jìn)程P1P(Empty )P(Mutex)緩沖區(qū) 產(chǎn)品V(Full)V(Mutex)消費(fèi)者進(jìn)程C1P(

15、Full)P(Mutex)取產(chǎn)品V(Empty )V(Mutex)8.4 處理器調(diào)度一、高級(jí)調(diào)度（作業(yè)調(diào)度、宏觀調(diào)度）二、中級(jí)調(diào)度（交互調(diào)度）三、低級(jí)調(diào)度（進(jìn)程調(diào)度、微觀調(diào)度）四、三級(jí)調(diào)度之間的關(guān)系一、高級(jí)調(diào)度 1、功能 按照一定的調(diào)度算法對(duì)外存上處于后備狀態(tài)的作業(yè)進(jìn)行選擇； 給選中的作業(yè)分配內(nèi)存、輸入輸出設(shè)備等必要的資源，并建立相應(yīng)的進(jìn)程； 作業(yè)運(yùn)行完畢時(shí)，回收該作業(yè)占用的資源，輸出必要的信息，撤銷該作業(yè)的JCB與相應(yīng)的進(jìn)程。 2、調(diào)度時(shí)機(jī) 設(shè)m為系統(tǒng)支持的在主機(jī)上運(yùn)行的最大作業(yè)數(shù)，n為在主機(jī)上運(yùn)行的當(dāng)前作業(yè)數(shù)。若n后臺(tái))選擇各隊(duì)列合適的調(diào)度算法各隊(duì)列間調(diào)度方式固定優(yōu)先級(jí)的搶占式調(diào)度各隊(duì)列間

16、按規(guī)定占用CPU時(shí)間比例調(diào)度4.性能分析:比前面任何算法都科學(xué)合理,但開銷大。8.5 常用調(diào)度算法六、多級(jí)反饋隊(duì)列調(diào)度算法思想：按照一定的原則，設(shè)置多個(gè)就緒隊(duì)列，每個(gè)隊(duì)列按FCFS原則排列，各隊(duì)列之間的進(jìn)程享有不同的優(yōu)先級(jí)和時(shí)間片,但同一隊(duì)列內(nèi)優(yōu)先級(jí)和時(shí)間片相同,一個(gè)進(jìn)程在它執(zhí)行結(jié)束之前，可能需要反復(fù)多次通過(guò)反饋循環(huán)執(zhí)行。特點(diǎn)：允許作業(yè)（進(jìn)程）在各隊(duì)列間移動(dòng)。8.5 常用調(diào)度算法六、多級(jí)反饋隊(duì)列調(diào)度算法3. 實(shí)現(xiàn)1）置多個(gè)就緒隊(duì)列,賦予不同的優(yōu)先級(jí)和時(shí)間片2）當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后,首先將它放入第一隊(duì)列末尾,按FCFS原則調(diào)度3）當(dāng)進(jìn)程在一個(gè)時(shí)間片結(jié)束時(shí)未完成,將其轉(zhuǎn)入下一個(gè)隊(duì)列末尾； 4）僅