2014工程軟件3.3處理器管理

1、3.3 處理器管理為什么要對(duì)處理器（CPU）進(jìn)行管理？解決用戶提交的作業(yè)何時(shí)調(diào)入內(nèi)存，在調(diào)入內(nèi)存的各個(gè)作業(yè)間如何分配處理器的問(wèn)題，以達(dá)到多道程序能協(xié)調(diào)一致運(yùn)行，并且使系統(tǒng)資源又能得到最大程度的利用處理器管理包括哪些內(nèi)容？作業(yè)管理宏觀選取某些作業(yè)進(jìn)入內(nèi)存，為其分配必要的資源，建立相應(yīng)的進(jìn)程，當(dāng)作業(yè)完成后做善后工作進(jìn)程管理微觀按照某種調(diào)度原則，實(shí)現(xiàn)處理器在各進(jìn)程間切換一個(gè)正在執(zhí)行的程序計(jì)算機(jī)中正在運(yùn)行的程序的一個(gè)實(shí)例可以分配給處理器并由處理器執(zhí)行的一個(gè)實(shí)體 3.3 處理器管理相關(guān)概念特權(quán)指令只能由操作系統(tǒng)使用的指令非特權(quán)指令供一般用戶使用的指令管態(tài)又稱主態(tài)、執(zhí)行狀態(tài)，此時(shí)處理器執(zhí)行特權(quán)指令目態(tài)又稱

2、算態(tài)、題目狀態(tài)，此時(shí)處理器處于用戶執(zhí)行狀態(tài)3.3.1 作業(yè)調(diào)度作業(yè)狀態(tài)轉(zhuǎn)換作業(yè)控制塊提交收容完成執(zhí)行設(shè)備管理作業(yè)管理作業(yè)名現(xiàn)在狀態(tài)優(yōu)先數(shù)時(shí)間估計(jì)位置長(zhǎng)度外設(shè)申請(qǐng)。指向下一個(gè)JCB指針先來(lái)先服務(wù)基于優(yōu)先級(jí)的調(diào)度算法分時(shí)和優(yōu)先級(jí)結(jié)合的作業(yè)調(diào)度釋放資源3.3.1 作業(yè)調(diào)度功能按照某種調(diào)度算法，從作業(yè)隊(duì)列中選取作業(yè)進(jìn)入內(nèi)存調(diào)用存儲(chǔ)管理和設(shè)備管理程序，為被選中的作業(yè)分配內(nèi)存和外設(shè)為選中的作業(yè)建立相應(yīng)的進(jìn)程作業(yè)運(yùn)行完畢時(shí)回收該作業(yè)占用的資源，輸出必要的信息，撤銷該作業(yè)的JCB與相應(yīng)的進(jìn)程作業(yè)調(diào)度算法先來(lái)先服務(wù)算法基于優(yōu)先級(jí)的調(diào)度算法分時(shí)和優(yōu)先級(jí)相結(jié)合的作業(yè)調(diào)度3.3.2 進(jìn)程調(diào)度進(jìn)程調(diào)度算法時(shí)間到3.3.

3、2 進(jìn)程調(diào)度進(jìn)程控制塊（PCB）3.3.2 進(jìn)程調(diào)度進(jìn)程間CPU的切換（上下文切換）3.3.2 進(jìn)程調(diào)度進(jìn)程控制（1）創(chuàng)建進(jìn)程（2）撤銷進(jìn)程（3）進(jìn)程的阻塞與喚醒（1）創(chuàng)建進(jìn)程一個(gè)進(jìn)程可以創(chuàng)建若干個(gè)新進(jìn)程，新創(chuàng)建的進(jìn)程又可以創(chuàng)建子進(jìn)程ABDECF父進(jìn)程祖先進(jìn)程子進(jìn)程（1）創(chuàng)建進(jìn)程進(jìn)程創(chuàng)建過(guò)程進(jìn)程創(chuàng)建原語(yǔ)create()原語(yǔ)（primitive）：由若干條機(jī)器指令構(gòu)成，用以完成某一特定功能的程序段原語(yǔ)在執(zhí)行過(guò)程中是不允許被中斷的申請(qǐng)一個(gè)空閑的PCB為新進(jìn)程分配資源對(duì)PCB初始化將PCB插入就緒隊(duì)列返回一個(gè)進(jìn)程標(biāo)識(shí)號(hào)（2）撤銷進(jìn)程撤銷進(jìn)程釋放其占有的各類資源導(dǎo)致進(jìn)程撤消的事件進(jìn)程正常結(jié)束進(jìn)程異常結(jié)

4、束外界干預(yù)在運(yùn)行？NYNY在PCB集中找PCB并讀狀態(tài)歸還占有資源從所在隊(duì)列(索引表)撤消PCB中止運(yùn)行重置調(diào)度標(biāo)志終止所有子孫進(jìn)程有子孫進(jìn)程？（3）進(jìn)程的阻塞與喚醒進(jìn)程的阻塞當(dāng)一個(gè)進(jìn)程期待的事件尚未出現(xiàn)時(shí)，該進(jìn)程調(diào)用阻塞原語(yǔ)block() 將自己阻塞起來(lái)停止執(zhí)行修改PCB中的狀態(tài)（執(zhí)行-阻塞）插入到相應(yīng)的阻塞隊(duì)列調(diào)度一就緒進(jìn)程，切換CPU（保留阻塞進(jìn)程的CPU狀態(tài)）（3）進(jìn)程的阻塞與喚醒進(jìn)程的喚醒對(duì)于處于阻塞狀態(tài)的進(jìn)程，當(dāng)該進(jìn)程期待的事件出現(xiàn)時(shí)，由其它相關(guān)進(jìn)程調(diào)用喚醒原語(yǔ)wakeup() 將阻塞的進(jìn)程喚醒，使其進(jìn)入就緒狀態(tài)將阻塞進(jìn)程移出阻塞隊(duì)列插入到就緒隊(duì)列調(diào)度一就緒進(jìn)程，切換CPU（保留阻

5、塞進(jìn)程的CPU狀態(tài)）修改PCB中的狀態(tài)（阻塞-就緒）3.3.2 進(jìn)程調(diào)度進(jìn)程調(diào)度算法優(yōu)先數(shù)法把處理器分給最高優(yōu)先級(jí)的進(jìn)程適用于多道批處理系統(tǒng)輪轉(zhuǎn)調(diào)度法按照規(guī)定的時(shí)間片將處理器輪流分配給就緒隊(duì)列中的進(jìn)程可滿足分時(shí)系統(tǒng)中對(duì)響應(yīng)時(shí)間的要求對(duì)短進(jìn)程有利分級(jí)調(diào)度法分為多個(gè)優(yōu)先級(jí)，在同優(yōu)先級(jí)隊(duì)列中按照輪轉(zhuǎn)調(diào)度只有高優(yōu)先級(jí)執(zhí)行完成后等待IO操作，才執(zhí)行低優(yōu)先級(jí)的進(jìn)程3.3.3 進(jìn)程同步與互斥系統(tǒng)中各進(jìn)程之間在邏輯上存在著兩種制約關(guān)系進(jìn)程同步：為完成同一個(gè)任務(wù)的各進(jìn)程間因需要協(xié)調(diào)工作而相互等待、相互交換信息所產(chǎn)生的制約關(guān)系 進(jìn)程互斥 ：進(jìn)程共享獨(dú)占型資源時(shí)，必須互斥執(zhí)行同 步互 斥進(jìn)程-進(jìn)程進(jìn)程-資源-進(jìn)程時(shí)

6、間次序上受到某種限制競(jìng)爭(zhēng)到某一物理資源時(shí)不允許進(jìn)程工作相互清楚對(duì)方的存在及作用，交換信息不一定清楚其進(jìn)程情況例：生產(chǎn)與消費(fèi)之間，發(fā)送與接收之間，作者與讀者之間例：交通十字路口3.3.3 進(jìn)程同步與互斥臨界資源一次只允許一個(gè)進(jìn)程使用的資源稱為臨界資源，如打印機(jī)、繪圖機(jī)，變量、數(shù)據(jù)等，各進(jìn)程間采取互斥方式實(shí)現(xiàn)對(duì)這種臨界資源的共享，從而實(shí)現(xiàn)并行程序的封閉性例：有兩個(gè)進(jìn)程A和B，它們共享一個(gè)變量x，且兩個(gè)進(jìn)程按以下方式對(duì)變量X進(jìn)行訪問(wèn)和修改A: R1=X; R1=R1+1; X=R1;B: R2=X; R2=R2+1; X=R2;結(jié)果：X增加了2A: R1=X;B: R2=X;A: R1=R1+1;

7、X=R1;B: R2=R2+1; X=R2;結(jié)果：X增加了1變量X必需按臨界資源處理R1和R2為處理器中的兩個(gè)寄存器3.3.3 進(jìn)程同步與互斥臨界區(qū)每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼稱為臨界區(qū)進(jìn)入?yún)^(qū)增加在臨界區(qū)前面的一段代碼，用于檢查欲訪問(wèn)的臨界資源此刻是否被訪問(wèn)退出區(qū)增加在臨界區(qū)后面的一段代碼，用于將臨界資源的訪問(wèn)標(biāo)志恢復(fù)為未被訪問(wèn)標(biāo)志進(jìn)入?yún)^(qū)退出區(qū)臨界區(qū)3.3.3 進(jìn)程同步與互斥對(duì)進(jìn)入臨界區(qū)的進(jìn)程有什么條件限制呢？一次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)任何時(shí)候，處于臨界區(qū)的進(jìn)程不得多于一個(gè)進(jìn)入臨界區(qū)的進(jìn)程要在有限的時(shí)間內(nèi)退出如果不能進(jìn)入臨界區(qū)，則應(yīng)讓出處理器資源解決臨界區(qū)問(wèn)題有什么方法？P-V操作3.3

8、.3 進(jìn)程同步與互斥P-V操作用同步原語(yǔ)對(duì)某信號(hào)量進(jìn)行操作以實(shí)現(xiàn)同步與互斥 P操作： ss-1; if(s0) then status(q) blocked; insert(Q,q); return;V操作： ss+1; if(s0) then Remove(Q,r) status(r) ready; insert(RL,r); return;3.3.3 進(jìn)程同步與互斥例1：A: R1=X; R1=R1+1; X=R1;B: R2=X; R2=R2+1; X=R2;A: P(s); R1=X; R1=R1+1; X=R1; V(s);B: P(s); R2=X; R2=R2+1; X=R2;

9、V(s);s的初始值設(shè)為1P-V操作實(shí)現(xiàn)進(jìn)程間互斥假設(shè)只有A和B兩個(gè)進(jìn)程3.3.3 進(jìn)程同步與互斥A: R1=X;B: R2=X;A: R1=R1+1; X=R1;B: R2=R2+1; X=R2;P(s)，s=s-1=0; A正常進(jìn)行P(s)，s=s-1=-1; B被阻塞，保留當(dāng)前狀態(tài)A正常進(jìn)行 V(s) s=s+1=0;將B從阻塞狀態(tài)置成就緒狀態(tài)A繼續(xù)執(zhí)行B從恢復(fù)狀態(tài)執(zhí)行B執(zhí)行V(s) s=s+1=1;3.3.3 進(jìn)程同步與互斥P-V操作實(shí)現(xiàn)進(jìn)程間同步生產(chǎn)者和消費(fèi)者問(wèn)題生產(chǎn)者生產(chǎn)物品存入n個(gè)位置的公共緩沖區(qū)供消費(fèi)者使用生產(chǎn)者不能將物品放入已滿的緩沖區(qū)中消費(fèi)者不能從空緩沖區(qū)中取物品生產(chǎn)者：L

10、: 生產(chǎn)物品 P(s1) 將物品放入緩沖區(qū) V(s2) Goto L消費(fèi)者：C: P(s2) 從緩沖區(qū)中取物品 V(s1) 消費(fèi)物品 Goto C初始值設(shè)置：s1=ns2=0思考：一個(gè)生產(chǎn)者多個(gè)消費(fèi)者如何操作進(jìn)程：生產(chǎn)者和消費(fèi)者物品：交互信息s1表明緩沖區(qū)有多少個(gè)空間s2表明緩沖區(qū)有多少個(gè)物品3.3.3 進(jìn)程同步與互斥哲學(xué)家就餐問(wèn)題有五個(gè)哲學(xué)家，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。他們共用一張圓桌，分別坐在五張椅子上。在圓桌上有五個(gè)碗和五支筷子，平時(shí)一個(gè)哲學(xué)家進(jìn)行思考，饑餓時(shí)便試圖取用其左、右最靠近他的筷子，只有在他拿到兩支筷子時(shí)才能進(jìn)餐。進(jìn)餐完畢，放下筷子又繼續(xù)思考進(jìn)程：5個(gè)哲學(xué)家物品：5

11、支筷子3.3.3 進(jìn)程同步與互斥用P-V操作解決哲學(xué)家就餐問(wèn)題semaphore stick5=1,1,1,1,1; /*分別表示5支筷子*/philosopher(int i) while(true) 思考; P(sticki); P(stick(i+1)%5); 進(jìn)餐； V(sticki); V(stick(i+1)%5); 哲學(xué)家進(jìn)餐問(wèn)題可看作是并發(fā)進(jìn)程并發(fā)執(zhí)行時(shí)，處理共享資源的一個(gè)有代表性的問(wèn)題若五位哲學(xué)家同時(shí)饑餓而各自拿起了左邊的筷子，這使五個(gè)信號(hào)量stick均為0，當(dāng)他們?cè)噲D去拿起右邊的筷子時(shí)，都將因無(wú)筷子而無(wú)限期地等待下去，即可能會(huì)引起死鎖，（多幾雙筷子？不能只拿一支筷子？）5個(gè)

12、進(jìn)程同時(shí)執(zhí)行，phiosopher(0)phiosopher(4) 3.3.3 進(jìn)程同步與互斥“讀寫”問(wèn)題：一個(gè)數(shù)據(jù)文件可被多個(gè)進(jìn)程共享。其中，reader進(jìn)程要求讀，writer 進(jìn)程要求寫允許多個(gè)reader進(jìn)程同時(shí)讀共享數(shù)據(jù)但絕不允許一個(gè)writer進(jìn)程與其它的reader進(jìn)程或writer進(jìn)程同時(shí)訪問(wèn)，即writer進(jìn)程必須與其它進(jìn)程互斥訪問(wèn)共享文件3.3.3 進(jìn)程同步與互斥“讀寫”問(wèn)題解決辦法設(shè)置一個(gè)共享變量Readcount：記錄當(dāng)前正在讀數(shù)據(jù)文件的讀進(jìn)程數(shù)目，初值為0讀互斥信號(hào)量s1 ：表示讀進(jìn)程互斥地訪問(wèn)共享變量readcount，初值為1寫互斥信號(hào)量s2：表示寫進(jìn)程與其它進(jìn)程

13、（讀、寫）互斥地訪問(wèn)數(shù)據(jù)文件，初值為13.3.3 進(jìn)程同步與互斥reader( while(true) P(s1); if(readcount= =0) P(s2); readcount+; V(s1); 讀數(shù)據(jù)集； P(s1); readcount-; if(readcount= =0) V(s2); V(s1) writer( ) while(true) P(s2); 寫數(shù)據(jù)集； V(s2); P-V操作使用要點(diǎn)根據(jù)不同的要求，P操作和V操作分別放在進(jìn)入?yún)^(qū)或退出區(qū)根據(jù)不同的要求，需設(shè)置多個(gè)信號(hào)量，并對(duì)每個(gè)信號(hào)量設(shè)置相應(yīng)的初始值對(duì)某個(gè)信號(hào)量進(jìn)行的P-V操作必須是成對(duì)出現(xiàn)的3.3.4 進(jìn)程間通

14、信進(jìn)程通信是指進(jìn)程之間的信息交換P-V操作，傳遞少量信息，效率低，稱為低級(jí)通信高級(jí)通信，進(jìn)程間交換的信息量大且效率高共享存儲(chǔ)器：進(jìn)程間通過(guò)對(duì)共享存儲(chǔ)區(qū)讀寫來(lái)交換數(shù)據(jù)消息傳遞：進(jìn)程間以消息為單位，通過(guò)通信原語(yǔ)實(shí)現(xiàn)通信直接通信：發(fā)送進(jìn)程直接把消息發(fā)送給接收進(jìn)程間接通信：發(fā)送方把消息 發(fā)送到某個(gè)中間實(shí)體（如信箱），接收進(jìn)程從中取得消息管道通信發(fā)送進(jìn)程以字符流形式將大量數(shù)據(jù)送入管道，接收進(jìn)程從管道讀取數(shù)據(jù)（只限于進(jìn)程及其子孫進(jìn)程之間）管道：用于連接讀進(jìn)程和寫進(jìn)程以實(shí)現(xiàn)它們之間通信的共享文件3.3.4 進(jìn)程間通信：直接通信方式3.3.4 進(jìn)程間通信：信箱通信發(fā)送進(jìn)程把消息發(fā)送到某個(gè)中間實(shí)體（信箱），接收

15、進(jìn)程從中取得消息Send(A,Msg)Receive(A,Msg)3.3.5 死鎖死鎖：一組相互競(jìng)爭(zhēng)系統(tǒng)資源或進(jìn)行通信的進(jìn)程間的“永久”阻塞3.3.5 死鎖3.3.5 死鎖3.3.5 死鎖死鎖產(chǎn)生的必要條件：互斥占有且等待不可搶占循環(huán)等待進(jìn)程循環(huán)鏈3.3.5 死鎖解決死鎖的方法死鎖預(yù)防：破壞死鎖產(chǎn)生的必要條件之一破壞互斥：較難實(shí)現(xiàn)，設(shè)備屬性就是非共享的破壞占有且等待：一次性請(qǐng)求所有需要的資源破壞資源不可搶占：當(dāng)進(jìn)程資源請(qǐng)求被拒絕時(shí)，必須釋放已獲得的資源破壞循環(huán)等待：定義資源類型的線性順序死鎖避免：不限制必要條件的存在，當(dāng)死鎖有可能出現(xiàn)時(shí)，根據(jù)進(jìn)程資源請(qǐng)求的情況避免死鎖的發(fā)生如果一個(gè)進(jìn)程的請(qǐng)求導(dǎo)

16、致死鎖，不啟動(dòng)此進(jìn)程如果一個(gè)進(jìn)程的資源請(qǐng)求導(dǎo)致死鎖，則不允許此分配死鎖檢測(cè)和恢復(fù)：允許死鎖的前三個(gè)必要條件，檢測(cè)是否存在進(jìn)程的循環(huán)鏈3.3.5 死鎖：死鎖避免算法銀行家算法銀行家擁有一筆周轉(zhuǎn)資金客戶一開(kāi)始必須說(shuō)明其最大需求客戶要求分期貸款，如果客戶能夠得到各期貸款，就一定能夠歸還貸款，否則就一定不能歸還貸款只要客戶所要求的最大資金量不超過(guò)總周轉(zhuǎn)資金，銀行家總會(huì)在有限時(shí)間內(nèi)滿足其需求。銀行家應(yīng)謹(jǐn)慎的貸款，防止出現(xiàn)壞帳用銀行家算法避免死鎖操作系統(tǒng)=銀行家操作系統(tǒng)管理的資源=周轉(zhuǎn)資金進(jìn)程=要求貸款的客戶3.3.5 死鎖：死鎖避免算法Res=0P:2(4)Q:4(0)R:2(6)Res=4P:2(4)

17、R:2(6)Res=6R:2(6)Res=2P:2(4)Q:2(2)R:2(6)Res=1P:2(4)Q:2(2)R:3(5)Res=0P:3(3)Q:2(2)R:3(5)不死鎖死鎖3.3.6 線程（Thread）為什么要引入線程？線程是操作系統(tǒng)領(lǐng)域出現(xiàn)的一個(gè)非常重要的技術(shù)，其引入是為了進(jìn)一步提高程序并發(fā)執(zhí)行的程度，從而進(jìn)一步提高資源的利用率和系統(tǒng)的吞吐量如何引入？進(jìn)程包含的兩個(gè)特點(diǎn)資源所有權(quán)調(diào)度/執(zhí)行這兩個(gè)特點(diǎn)是相互獨(dú)立的，操作系統(tǒng)可以獨(dú)立地處理，調(diào)度/執(zhí)行的單位通常稱作線程，而擁有資源所有權(quán)的單位通常稱作進(jìn)程進(jìn)程和線程的區(qū)別進(jìn)程線程引入目的能并發(fā)執(zhí)行,提高資源的利用率和系統(tǒng)吞吐量提高并發(fā)執(zhí)

18、行的程度，進(jìn)一步提高資源的利用率和系統(tǒng)吞吐量并發(fā)性較低較高基本屬性（調(diào)度）資源擁有的基本單位進(jìn)程獨(dú)立調(diào)度/分派的基本單位進(jìn)程資源擁有的基本單位進(jìn)程獨(dú)立調(diào)度/分派的基本單位線程基本狀態(tài)就緒; 執(zhí)行;等待就緒;執(zhí)行;等待系統(tǒng)操作創(chuàng)建,撤消,切換創(chuàng)建,撤消,切換系統(tǒng)開(kāi)銷創(chuàng)建/撤消/切換時(shí)開(kāi)銷較大創(chuàng)建/撤消/切換時(shí)開(kāi)銷較小存在標(biāo)志進(jìn)程控制塊PCB進(jìn)程控制塊PCB，線程控制塊TCB關(guān)系單進(jìn)程單線程;單進(jìn)程多線程;多進(jìn)程，每個(gè)進(jìn)程一個(gè)線程;多進(jìn)程，每個(gè)進(jìn)程多個(gè)線程線程和進(jìn)程的關(guān)系3.3.6 線程的優(yōu)點(diǎn)在一個(gè)已有進(jìn)程中創(chuàng)建一個(gè)新線程比創(chuàng)建一個(gè)全新的進(jìn)程所需的時(shí)間要少（UNIX中快10倍）終止一個(gè)線程比終止一個(gè)進(jìn)程花費(fèi)的時(shí)間少同一進(jìn)程內(nèi)線程間切換比進(jìn)程間切換花費(fèi)時(shí)間少線程提高了不同