第8章處理器管理

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

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

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

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

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

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

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

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

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

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

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

12、阻塞后進入與該信號相對應的等待隊列中，然后轉(zhuǎn)進程調(diào)度程序，調(diào)度另一個處于就緒狀態(tài)的進程占用CPU。二、信號量和P，V原語 3. V原語(1)信號量加1；(2)若信號量相加結果大于零，說明沒有其它進程等待使用該資源，則當前進程繼續(xù)執(zhí)行。(3)信號量相加結果小于或等于零，說明此時尚有其它進程等待使用該資源，則從該信號的等待隊列中喚醒一個等待進程，然后再返回原進程繼續(xù)執(zhí)行或轉(zhuǎn)進程調(diào)度。三、用P，V原語實現(xià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)進程BX=CO

13、UNTX=X+1COUNT=X臨界區(qū)V(S)P(S)進程AS=1 進程P1 L1:P(s) 獲取信息 進程P2 產(chǎn)生信息L2:V(s) 同步條件S=0同步點四、用P，V原語操作實現(xiàn)簡單同步 1.用P，V操作描述前趨關系五、P、V原語在進程同步/互斥問題中的應用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)者消費者五、P、V原語在進程同步/互斥問題中的應用2.生產(chǎn)者消費者問題 同步條件：當有界緩沖區(qū)中至少有一個單元是滿的時，消費者才能接收數(shù)據(jù)；當有界緩沖區(qū)中至少有一個單元是空的時，生產(chǎn)者才能發(fā)送數(shù)據(jù) 。互斥條件：有界緩沖區(qū)是臨界資源，必須互斥使用 。設置信號量：互斥信號量Mutex：初值為1。 同步信號量Full ：初值為0。 同步信號量Empty ：初值為n。 生產(chǎn)者進程P1P(Empty )P(Mutex)緩沖區(qū) 產(chǎn)品V(Full)V(Mutex)消費者進程C1P(

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

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