《操作系統(tǒng)》第3章處理機(jī)調(diào)度與死鎖

第三章處理機(jī)調(diào)度與死鎖重點(diǎn)掌握進(jìn)程調(diào)度算法，各適用于何種情況理解常用的幾種實(shí)時(shí)調(diào)度算法理解產(chǎn)生死鎖的原因掌握銀行家算法避免死鎖難點(diǎn)多道程序設(shè)計(jì)中的各種調(diào)度算法響應(yīng)比高者優(yōu)先調(diào)度算法的計(jì)算過程銀行家算法第三章處理機(jī)調(diào)度與死鎖知識(shí)點(diǎn)處理機(jī)調(diào)度及調(diào)度算法多處理機(jī)環(huán)境下的進(jìn)程（線程）調(diào)度方式產(chǎn)生死鎖的原因和必要條件預(yù)防死鎖的方法，死鎖的檢測(cè)與解除銀行家算法第三章處理機(jī)調(diào)度與死鎖處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源在多道程序環(huán)境下，進(jìn)程數(shù)目通常多于處理機(jī)的數(shù)目系統(tǒng)必須按一定方法動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程處理機(jī)利用率和系統(tǒng)性能（吞吐量、響應(yīng)時(shí)間）在很大程度上取決于處理機(jī)調(diào)度WHAT：按什么原則分配CPU—進(jìn)程調(diào)度算法WHEN：何時(shí)分配CPU—進(jìn)程調(diào)度的時(shí)機(jī)

HOW：如何分配CPU—CPU調(diào)度過程（進(jìn)程的上下文切換）第三章處理機(jī)調(diào)度與死鎖3.1處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)3.2作業(yè)與作業(yè)調(diào)度3.3進(jìn)程調(diào)度3.4實(shí)時(shí)調(diào)度3.5死鎖描述3.6預(yù)防死鎖3.7避免死鎖3.8死鎖的檢測(cè)與解除3.1.1處理機(jī)調(diào)度的層次高級(jí)調(diào)度(HighScheduling)

作業(yè)調(diào)度或長(zhǎng)程調(diào)度（Long-TermScheduling）按一定的原則對(duì)外存上處于后備狀態(tài)的作業(yè)進(jìn)行選擇，給選中的作業(yè)分配內(nèi)存、輸入/輸出設(shè)備等必要的資源，并建立相應(yīng)的進(jìn)程，放入就緒隊(duì)列，以使該作業(yè)的進(jìn)程獲得競(jìng)爭(zhēng)處理機(jī)的權(quán)利。也稱為接納調(diào)度（AdmissionScheduling）時(shí)間尺度：通常是分鐘、小時(shí)或天。3.1.1處理機(jī)調(diào)度的層次低級(jí)調(diào)度

進(jìn)程調(diào)度或短程調(diào)度（Short-TermScheduling）按照某種策略和方法選取一個(gè)處于就緒狀態(tài)的進(jìn)程，將處理機(jī)分配給它。常見調(diào)度方式非搶占式；搶占式。時(shí)間尺度：通常是毫秒級(jí)的。由于低級(jí)調(diào)度算法的頻繁使用，要求在實(shí)現(xiàn)時(shí)做到高效。3.1.1處理機(jī)調(diào)度的層次中級(jí)調(diào)度(Intermediate-LevelScheduling)

中程調(diào)度(Medium-TermScheduling)引入目的提高內(nèi)存利用率和系統(tǒng)吞吐量。使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待。交換過程按照給定的原則和策略，將處于外存對(duì)換區(qū)中的重又具備運(yùn)行條件的就緒進(jìn)程調(diào)入內(nèi)存，或?qū)⑻幱趦?nèi)存就緒狀態(tài)或內(nèi)存阻塞狀態(tài)的進(jìn)程交換到外存對(duì)換區(qū)。3.1.1處理機(jī)調(diào)度的層次進(jìn)程調(diào)度的運(yùn)行頻率最高，在分時(shí)系統(tǒng)中通常是10～100ms便進(jìn)行一次進(jìn)程調(diào)度，因此把它稱為短程調(diào)度。為避免進(jìn)程調(diào)度占用太多的CPU時(shí)間，進(jìn)程調(diào)度算法不宜太復(fù)雜。作業(yè)調(diào)度往往是發(fā)生在一個(gè)(批)作業(yè)運(yùn)行完畢，退出系統(tǒng)，而需要重新調(diào)入一個(gè)(批)作業(yè)進(jìn)入內(nèi)存時(shí)，故作業(yè)調(diào)度的周期較長(zhǎng)，大約幾分鐘一次，因此把它稱為長(zhǎng)程調(diào)度。由于其運(yùn)行頻率較低，故允許作業(yè)調(diào)度算法花費(fèi)較多的時(shí)間。中級(jí)調(diào)度的運(yùn)行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為中程調(diào)度。3.1.2處理機(jī)調(diào)度算法的目標(biāo)處理調(diào)度算法的共同目標(biāo)資源的利用率公平性平衡性策略強(qiáng)制執(zhí)行3.1.2處理機(jī)調(diào)度算法的目標(biāo)基本術(shù)語到達(dá)時(shí)間作業(yè)進(jìn)入后備作業(yè)隊(duì)列或新創(chuàng)建進(jìn)程進(jìn)入就緒隊(duì)列的時(shí)刻；服務(wù)時(shí)間作業(yè)（進(jìn)程）占用處理機(jī)的時(shí)間開始時(shí)間作業(yè)被創(chuàng)建進(jìn)入就緒隊(duì)列或進(jìn)程首次占有處理機(jī)的時(shí)刻完成時(shí)間用戶獲得作業(yè)執(zhí)行結(jié)果的時(shí)刻。3.1.2處理機(jī)調(diào)度算法的目標(biāo)批處理系統(tǒng)的目標(biāo)平均周轉(zhuǎn)時(shí)間短周轉(zhuǎn)時(shí)間，指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔(稱為作業(yè)周轉(zhuǎn)時(shí)間)。它包括四部分時(shí)間：作業(yè)在外存后備隊(duì)列上等待(作業(yè))調(diào)度的時(shí)間；進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間進(jìn)程在CPU上執(zhí)行的時(shí)間；進(jìn)程等待I/O操作完成的時(shí)間。注意：此三項(xiàng)在一個(gè)作業(yè)的處理過程中可能會(huì)發(fā)生多次。周轉(zhuǎn)時(shí)間=完成時(shí)間-到達(dá)時(shí)間3.1.2處理機(jī)調(diào)度算法的目標(biāo)批處理系統(tǒng)的目標(biāo)平均周轉(zhuǎn)時(shí)間短平均周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間：進(jìn)程（或作業(yè)）的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間TS之比，即W=T/TS

。平均帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間3.1.2處理機(jī)調(diào)度算法的目標(biāo)批處理系統(tǒng)的目標(biāo)系統(tǒng)吞吐量高吞吐量指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)作業(yè)調(diào)度的方式和算法對(duì)吞吐量的大小有較大影響處理機(jī)利用率高各類資源的平衡利用使內(nèi)存、外存和I/O設(shè)備的利用率高3.1.2處理機(jī)調(diào)度算法的目標(biāo)分時(shí)系統(tǒng)的目標(biāo)響應(yīng)時(shí)間快響應(yīng)時(shí)間，從用戶通過鍵盤提交一個(gè)請(qǐng)求開始，直至系統(tǒng)中首次產(chǎn)生響應(yīng)為止的時(shí)間交互式系統(tǒng)用周轉(zhuǎn)時(shí)間衡量不是最佳均衡性系統(tǒng)響應(yīng)時(shí)間的快慢與用戶所請(qǐng)求服務(wù)的復(fù)雜性相適應(yīng)。3.1.2處理機(jī)調(diào)度算法的目標(biāo)實(shí)時(shí)系統(tǒng)的目標(biāo)截止時(shí)間保證截止時(shí)間，某任務(wù)必須開始執(zhí)行的最遲時(shí)間或必須完成的最遲時(shí)間截止時(shí)間是實(shí)時(shí)系統(tǒng)中的重要指標(biāo)可預(yù)測(cè)性數(shù)據(jù)的到達(dá)或?qū)⒁幚砣蝿?wù)的要求是可預(yù)測(cè)的。3.1.2處理機(jī)調(diào)度算法的目標(biāo)問題的本質(zhì)周轉(zhuǎn)時(shí)間短響應(yīng)時(shí)間快截止時(shí)間保證批處理系統(tǒng)分時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)等待時(shí)間短優(yōu)先級(jí)3.1.2處理機(jī)調(diào)度算法的目標(biāo)目標(biāo)實(shí)現(xiàn)等待時(shí)間短等待時(shí)間，在就緒隊(duì)列中等待所花的時(shí)間調(diào)度算法并不影響進(jìn)程運(yùn)行和執(zhí)行I/O的時(shí)間量；只影響進(jìn)程在就緒隊(duì)列中等待所花費(fèi)的時(shí)間優(yōu)先級(jí)準(zhǔn)則在批處理、實(shí)時(shí)和分時(shí)系統(tǒng)中都可以選擇優(yōu)先級(jí)準(zhǔn)則，以便讓緊急任務(wù)先處理有時(shí)還選擇搶占式調(diào)度方式3.2作業(yè)與作業(yè)調(diào)度3.2.1批處理系統(tǒng)中的作業(yè)3.2.2作業(yè)調(diào)度的主要任務(wù)3.2.3先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法3.2.4優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比調(diào)度算法3.2.1批處理系統(tǒng)中的作業(yè)作業(yè)和作業(yè)步作業(yè)(Job)。用戶在一次解題或一個(gè)事務(wù)處理過程中要求計(jì)算機(jī)系統(tǒng)所做工作的集合，包括用戶程序、所需的數(shù)據(jù)及命令等。作業(yè)步(JobStep)。通常，在作業(yè)運(yùn)行期間，每個(gè)作業(yè)都必須經(jīng)過若干個(gè)相對(duì)獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果。例，一個(gè)典型的作業(yè)可分成三個(gè)作業(yè)步：①“編譯”作業(yè)步；②“鏈接裝配”作業(yè)步；③“運(yùn)行”作業(yè)步。3.2.1批處理系統(tǒng)中的作業(yè)作業(yè)控制塊（JobcontrolBlock,JCB）作業(yè)在系統(tǒng)中存在的標(biāo)志；包括作業(yè)標(biāo)識(shí)、用戶名稱、用戶賬號(hào)、作業(yè)類型（CPU繁忙型、I/O繁忙型、批量型、終端型）、作業(yè)狀態(tài)、調(diào)度信息（優(yōu)先級(jí)、作業(yè)運(yùn)行時(shí)間）、資源需求（預(yù)計(jì)運(yùn)行時(shí)間、要求內(nèi)存大?。①Y源使用情況。3.2.1批處理系統(tǒng)中的作業(yè)作業(yè)運(yùn)行的三個(gè)階段和三種狀態(tài)一個(gè)作業(yè)進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，一般需要經(jīng)歷收容、運(yùn)行、完成三個(gè)階段，與之相對(duì)應(yīng)的是作業(yè)的三種狀態(tài)后備狀態(tài)運(yùn)行狀態(tài)完成狀態(tài)3.2.1批處理系統(tǒng)中的作業(yè)作業(yè)狀態(tài)間轉(zhuǎn)換運(yùn)行狀態(tài)后備狀態(tài)完成狀態(tài)就緒阻塞執(zhí)行I/O完成I/O請(qǐng)求時(shí)間片完作業(yè)注冊(cè)作業(yè)調(diào)度進(jìn)程調(diào)度終止作業(yè)3.2.2作業(yè)調(diào)度的主要任務(wù)作業(yè)調(diào)度的主要功能根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。接納多少個(gè)作業(yè)即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行，取決于多道程序度（DegreeofMultiprogramming）作業(yè)太多服務(wù)質(zhì)量下降作業(yè)太少資源利用率低3.2.2作業(yè)調(diào)度的主要任務(wù)接納哪些作業(yè)取決于作業(yè)調(diào)度算法先來先服務(wù)短作業(yè)優(yōu)先作業(yè)優(yōu)先級(jí)調(diào)度響應(yīng)比調(diào)度多道程序度：即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。周轉(zhuǎn)時(shí)間：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔。吞吐量：是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。3.2.3先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)(FCFS)/先進(jìn)先出(FIFO)調(diào)度算法按照作業(yè)/進(jìn)程進(jìn)入系統(tǒng)的先后次序進(jìn)行調(diào)度，先進(jìn)入系統(tǒng)者先調(diào)度；即啟動(dòng)等待時(shí)間最長(zhǎng)的作業(yè)/進(jìn)程最簡(jiǎn)單的調(diào)度算法，既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度3.2.3先來先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均04A13B25C32D44E044476先來先服務(wù)（先進(jìn)先出）：712101214111418141225.53.592.8AAAABBBCCCCCDDEEEE05101518t3.2.3先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)（先進(jìn)先出）優(yōu)缺點(diǎn)比較有利于長(zhǎng)作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）有利于CPU繁忙型作業(yè)（進(jìn)程），而不利于I/O繁忙型作業(yè)（進(jìn)程）用于批處理系統(tǒng)，不適于分時(shí)系統(tǒng)3.2.3先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)（先進(jìn)先出）等待時(shí)間：J1=0;J2=0;J3=100；J4=100平均等待時(shí)間：(0+0+100+100)/4=50平均周轉(zhuǎn)時(shí)間：(1+100+101+200)/4=100.5平均帶權(quán)周轉(zhuǎn)時(shí)間：(1+1+101+2)/4=26.25作業(yè)到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間J101J21100J311J4210001110110110210220211100110110120023.2.3先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)（先進(jìn)先出）等待時(shí)間：J1=0;J2=1;J3=0；J4=100平均等待時(shí)間：(0+1+0+100)/4=25.25平均周轉(zhuǎn)時(shí)間：(1+1+101+200）/4=75.75平均帶權(quán)周轉(zhuǎn)時(shí)間：（1+1+1.01+2）/4=1.2525作業(yè)到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間J101J311J21100J421000112210210220211111011.0120023.2.3先來先服務(wù)和短作業(yè)優(yōu)先算法短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F按運(yùn)行時(shí)間長(zhǎng)短進(jìn)行調(diào)度，即先啟動(dòng)要求運(yùn)行時(shí)間最短的作業(yè)（進(jìn)程）短作業(yè)優(yōu)先(SJF)的調(diào)度算法：從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，調(diào)入內(nèi)存運(yùn)行；短進(jìn)程優(yōu)先(SPF)調(diào)度算法：從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度。3.2.3先來先服務(wù)和短作業(yè)優(yōu)先算法作業(yè)名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均04A13B25C32D44E0441短作業(yè)/短進(jìn)程優(yōu)先（SJF/SPF）：4631.56982.6791392.251318163.282.1AAAABBBCCCCCDDEEEE05101518t3.2.3先來先服務(wù)和短作業(yè)優(yōu)先算法SJ(P)F調(diào)度算法的缺點(diǎn)對(duì)長(zhǎng)作業(yè)不利。嚴(yán)重的是，由于調(diào)度程序總是優(yōu)先調(diào)度短作業(yè)(進(jìn)程)，將導(dǎo)致長(zhǎng)作業(yè)(進(jìn)程)長(zhǎng)期不被調(diào)度——饑餓不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理；不一定能真正做到短作業(yè)優(yōu)先調(diào)度。由于作業(yè)(進(jìn)程)的長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間。優(yōu)先級(jí)調(diào)度算法對(duì)于先來先服務(wù)算法，作業(yè)的等待時(shí)間就是作業(yè)的優(yōu)先級(jí)，等待時(shí)間越長(zhǎng)，優(yōu)先級(jí)越高。對(duì)于短作業(yè)優(yōu)先算法，作業(yè)的長(zhǎng)短就是作業(yè)的優(yōu)先級(jí)，作業(yè)所需時(shí)間越短，其優(yōu)先級(jí)越高。在優(yōu)先級(jí)算法，根據(jù)作業(yè)的緊迫程度，由外部給予作業(yè)不同的優(yōu)先級(jí)，然后根據(jù)優(yōu)先級(jí)調(diào)度3.2.4優(yōu)先級(jí)和高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法（HRRN）FCFS和SJF的結(jié)合，克服了兩種算法的缺點(diǎn)調(diào)度策略：響應(yīng)比最高的作業(yè)優(yōu)先啟動(dòng)因等待時(shí)間+服務(wù)時(shí)間=該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先級(jí)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為3.2.4優(yōu)先級(jí)和高優(yōu)先比優(yōu)先調(diào)度算法優(yōu)先級(jí)=等待時(shí)間+要求服務(wù)時(shí)間要求服務(wù)時(shí)間Rp=等待時(shí)間+要求服務(wù)時(shí)間要求服務(wù)時(shí)間

響應(yīng)時(shí)間要求服務(wù)時(shí)間=3.2.4優(yōu)先級(jí)和高優(yōu)先比優(yōu)先調(diào)度算法對(duì)HRRN的小結(jié)等待時(shí)間相同的作業(yè)，則要求服務(wù)的時(shí)間愈短，其優(yōu)先級(jí)愈高，要求服務(wù)的時(shí)間相同的作業(yè)，則等待時(shí)間愈長(zhǎng)，其優(yōu)先級(jí)愈高，長(zhǎng)作業(yè)，優(yōu)先級(jí)隨等待時(shí)間的增加而提高，其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先級(jí)便可升到很高，從而也可獲得處理機(jī)，是一種折衷，既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，又不會(huì)使長(zhǎng)作業(yè)長(zhǎng)期得不到服務(wù)。缺點(diǎn)：要進(jìn)行響應(yīng)比計(jì)算，增加了系統(tǒng)開銷——對(duì)短作業(yè)有利——先來先服務(wù)——對(duì)長(zhǎng)作業(yè)有利優(yōu)先級(jí)=

等待時(shí)間+要求服務(wù)時(shí)間要求服務(wù)時(shí)間

響應(yīng)時(shí)間要求服務(wù)時(shí)間=優(yōu)先級(jí)=

等待時(shí)間+服務(wù)時(shí)間服務(wù)時(shí)間當(dāng)前時(shí)間-到達(dá)時(shí)間+服務(wù)時(shí)間服務(wù)時(shí)間=作業(yè)名到達(dá)時(shí)間服務(wù)時(shí)間響應(yīng)比開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均04A13B25C32D44E04411418143.54762914122.479638.42.38高響應(yīng)比優(yōu)先，非搶占式21.41.51231.752.42.253.53.2.4優(yōu)先級(jí)和高優(yōu)先比優(yōu)先調(diào)度算法作業(yè)到達(dá)時(shí)間要求服務(wù)時(shí)間開始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間J18.02.0J28.60.6J38.80.2J49.00.5平均①②③④⑤⑥8.08.69.09.69.210.111.39.63.31.651.01.670.42.01.12.2/9.2/8.81.451.88/10.1⑦高響應(yīng)比優(yōu)先，搶占式3.2.4優(yōu)先級(jí)和高優(yōu)先比優(yōu)先調(diào)度算法3.3進(jìn)程調(diào)度3.3.1進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式3.3.2輪轉(zhuǎn)調(diào)度算法3.3.3優(yōu)先級(jí)調(diào)度算法3.3.4多隊(duì)列調(diào)度算法3.3.5多級(jí)反饋隊(duì)列調(diào)度算法3.3.6基于公平原則的調(diào)度算法3.3.1進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式進(jìn)程調(diào)度的任務(wù)保存處理機(jī)的現(xiàn)場(chǎng)信息。將正在運(yùn)行進(jìn)程的上下文保存到PCB及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)中。按某種算法選取進(jìn)程。控制、協(xié)調(diào)進(jìn)程對(duì)CPU的競(jìng)爭(zhēng)，即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程。把處理器分配給進(jìn)程。把CPU的使用權(quán)交給被選中的進(jìn)程，并裝入選中進(jìn)程的上下文。3.3.1進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式進(jìn)程調(diào)度機(jī)制

根據(jù)預(yù)定的算法，將系統(tǒng)中所有的就緒進(jìn)程排成一個(gè)或多個(gè)隊(duì)列，以便調(diào)度程序能最快地找到它。分派程序把由進(jìn)程調(diào)度程序所選定的進(jìn)程，從就緒隊(duì)列中取出該進(jìn)程，然后進(jìn)行上下文切換，將處理機(jī)分配給它。①OS保存當(dāng)前進(jìn)程的上下文，裝入分派程序的上下文；②將移出分派程序，把新選進(jìn)程的CPU現(xiàn)場(chǎng)信息裝入到處理機(jī)的各個(gè)相應(yīng)寄存器中。3.3.1進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式進(jìn)程調(diào)度方式非搶占方式(Non-preemptiveMode)搶占方式(PreemptiveMode)3.3.1進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式進(jìn)程調(diào)度方式——非搶占方式進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，新就緒的進(jìn)程進(jìn)入就緒隊(duì)列，該進(jìn)程仍繼續(xù)執(zhí)行，直到其完成或發(fā)生某種事件而進(jìn)入完成或阻塞狀態(tài)時(shí)，才轉(zhuǎn)讓處理機(jī)。引起進(jìn)程調(diào)度的因素正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如wait、Block、Wakeup原語優(yōu)點(diǎn)：算法簡(jiǎn)單，系統(tǒng)開銷小缺點(diǎn)：緊急任務(wù)不能及時(shí)響應(yīng)；短進(jìn)程到達(dá)要等待長(zhǎng)進(jìn)程運(yùn)行結(jié)束進(jìn)程調(diào)度方式——搶占方式進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，則立即暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分配給這個(gè)更為重要或緊迫的進(jìn)程搶占式調(diào)度原則優(yōu)先級(jí)原則允許高優(yōu)先級(jí)的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)短作業(yè)(進(jìn)程)優(yōu)先原則允許執(zhí)行時(shí)間短的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)時(shí)間片原則時(shí)間片用完后停止執(zhí)行，重新進(jìn)行調(diào)度，適用于分時(shí)系統(tǒng)優(yōu)點(diǎn)：適于時(shí)間要求嚴(yán)格的實(shí)時(shí)系統(tǒng)缺點(diǎn)：調(diào)度算法復(fù)雜，系統(tǒng)開銷大3.3.1進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式3.3.2輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)法的基本原理系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便停止該進(jìn)程的執(zhí)行，并將其放就緒隊(duì)列尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首時(shí)間片的大小從幾ms到幾百ms缺點(diǎn)：緊迫任務(wù)響應(yīng)慢。UNIX中采用：時(shí)間片+優(yōu)先級(jí)3.3.2輪轉(zhuǎn)調(diào)度算法進(jìn)程切換時(shí)間任務(wù)在給定時(shí)間片內(nèi)已完成，則將它標(biāo)記為終止?fàn)顟B(tài)，立即激活調(diào)度程序進(jìn)行調(diào)度；任務(wù)在時(shí)間片內(nèi)未完成，計(jì)時(shí)器中斷處理程序被激活，則將進(jìn)程進(jìn)入就緒隊(duì)列末尾，啟動(dòng)調(diào)度程序調(diào)度；3.3.2輪轉(zhuǎn)調(diào)度算法時(shí)間片大小的確定時(shí)間片選擇問題固定時(shí)間片可變時(shí)間片與時(shí)間片大小有關(guān)的因素系統(tǒng)響應(yīng)時(shí)間就緒進(jìn)程個(gè)數(shù)CPU能力

基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均ABCDEABCDEABCEACEC05101518t04A03B05C02D04E01234912151718153.75124183.694.5174.2514.24.02若到達(dá)時(shí)間為0、1、2、3、4，又如何？基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均ABACBDAECBDAECECEC05101518t04A13B25C32D44E01357111012171812393163.284133.2511.63.293.3.3優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法的類型非搶占式特點(diǎn)：系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成，或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)才將處理機(jī)重新分配給另一優(yōu)先級(jí)最高的進(jìn)程主要用于批處理系統(tǒng)中，也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中3.3.3優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法的類型搶占式把處理機(jī)分配給優(yōu)先級(jí)最高的進(jìn)程，在執(zhí)行期間，只要出現(xiàn)另一個(gè)優(yōu)先級(jí)更高的進(jìn)程，則進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程的執(zhí)行，并將處理機(jī)分配給新到的優(yōu)先級(jí)最高的進(jìn)程只要系統(tǒng)中出現(xiàn)一個(gè)新的就緒進(jìn)程，就進(jìn)行優(yōu)先級(jí)比較能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中3.3.3優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)的類型靜態(tài)優(yōu)先級(jí)靜態(tài)優(yōu)先級(jí)在創(chuàng)建進(jìn)程時(shí)確定，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般地，優(yōu)先級(jí)是利用某一范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，07或0255，又把該整數(shù)稱為優(yōu)先數(shù)確定進(jìn)程靜態(tài)優(yōu)先級(jí)的依據(jù)進(jìn)程類型:系統(tǒng)進(jìn)程，用戶進(jìn)程進(jìn)程對(duì)資源的需求用戶要求問題：用戶將優(yōu)先級(jí)設(shè)的較高，對(duì)其他進(jìn)程不利?。《踢M(jìn)程優(yōu)先對(duì)長(zhǎng)進(jìn)程不利?。?.3.3優(yōu)先級(jí)調(diào)度算法動(dòng)態(tài)優(yōu)先級(jí)隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變。例，在就緒隊(duì)列中的進(jìn)程，優(yōu)先級(jí)隨等待時(shí)間的增長(zhǎng)，以某一速率提高；相同優(yōu)先級(jí)初值的進(jìn)程，則最先進(jìn)入就緒隊(duì)列的進(jìn)程，優(yōu)先獲得處理機(jī)，即FCFS算法各不相同的優(yōu)先級(jí)初值的就緒進(jìn)程，則優(yōu)先級(jí)初值低的進(jìn)程，在等待了足夠的時(shí)間后，其優(yōu)先級(jí)便可能升為最高，從而可以獲得處理機(jī)當(dāng)采用搶占式優(yōu)先級(jí)調(diào)度算法時(shí)，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先級(jí)以某一速率下降，則可防止一個(gè)長(zhǎng)作業(yè)長(zhǎng)期地壟斷處理機(jī)。進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P107P215P323P432P544平均等待時(shí)間：(14+5+0+2+7)/5=5.6平均周轉(zhuǎn)時(shí)間：(21+10+3+4+11）/5=9.8平均帶權(quán)周轉(zhuǎn)時(shí)間：(3+2+1+2+2.75）/5=2.15①⑤②④③⑥⑦012557/7111115/15212131023142112.753.3.3優(yōu)先級(jí)調(diào)度算法——實(shí)例搶占式短進(jìn)程優(yōu)先SPF調(diào)度3.3.3優(yōu)先級(jí)調(diào)度算法——實(shí)例進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間靜態(tài)優(yōu)先級(jí)開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均靜態(tài)優(yōu)先級(jí)，非搶占式（1為最高優(yōu)先級(jí)）04A413B225C332D544E104414841811103.331116142.81618157.59.42.93考慮一下?lián)屨际?，情況如何？進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間靜態(tài)優(yōu)先級(jí)開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均高優(yōu)先級(jí)優(yōu)先調(diào)度算法04A413B225C332D544E101616448411431813112.21618157.59.83.14靜態(tài)優(yōu)先級(jí)，搶占式（1為高優(yōu)先級(jí)）ABBBEEEECCCCCAAADD05101518tBAACDEACD3.3.4多隊(duì)列調(diào)度算法單一就緒隊(duì)列→多個(gè)就緒隊(duì)列例，將就緒進(jìn)程分別進(jìn)入前臺(tái)和后臺(tái)就緒隊(duì)列前臺(tái)就緒隊(duì)列是交互性作業(yè)的進(jìn)程，通常采用時(shí)間片輪轉(zhuǎn)。后臺(tái)的就緒隊(duì)列是批處理作業(yè)的進(jìn)程，通常采用優(yōu)先級(jí)或短作業(yè)優(yōu)先算法。調(diào)度方式有兩種：優(yōu)先調(diào)度前臺(tái)，若前臺(tái)無可運(yùn)行進(jìn)程，才調(diào)度后臺(tái)。分配占用CPU的時(shí)間比例，如：前臺(tái)80%，后臺(tái)20%3.3.5多級(jí)反饋(multilevedfeedback)隊(duì)列調(diào)度算法調(diào)度機(jī)制

設(shè)置多個(gè)就緒隊(duì)列，各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先級(jí)逐個(gè)降低各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先級(jí)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。例，第二個(gè)隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍，……，第i+1個(gè)隊(duì)列的時(shí)間片要比第i個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍就緒隊(duì)列13.3.5多級(jí)反饋隊(duì)列調(diào)度算法就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)列nS1S2S3至CPU至CPU至CPU至CPU(時(shí)間片：S1＜S2＜S3)調(diào)度方式高低優(yōu)先級(jí)時(shí)間片小大Sn按FIFO原則排隊(duì)等待調(diào)度尚未完成轉(zhuǎn)入第二隊(duì)列的末尾，按FIFO原則等待調(diào)度采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行因等待而放棄CPU后，進(jìn)入阻塞隊(duì)列，一旦等待的事件發(fā)生，則回到原來的就緒隊(duì)列3.3.5多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法注意僅當(dāng)?shù)?~(i-1)隊(duì)列均空時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行第i隊(duì)列中某進(jìn)程正在運(yùn)行時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先級(jí)較高的隊(duì)列(第1~(i-1)中的任何一個(gè)隊(duì)列)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾第i隊(duì)列中某進(jìn)程正在運(yùn)行時(shí)，該進(jìn)程因等待事件發(fā)生而進(jìn)入阻塞隊(duì)列，等待事件發(fā)生后，調(diào)度程序把進(jìn)程放回到第i隊(duì)列的末尾3.3.5多級(jí)反饋隊(duì)列調(diào)度算法調(diào)度算法的性能終端型作業(yè)用戶提交的作業(yè)多屬于交互型作業(yè)，通常較小，系統(tǒng)只要能使這些作業(yè)在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成即可短批處理作業(yè)用戶若在第1隊(duì)列中執(zhí)行一個(gè)時(shí)間片即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時(shí)間如在第一個(gè)隊(duì)列中不能完成，只需在第2、3隊(duì)列中各執(zhí)行一個(gè)時(shí)間片長(zhǎng)批處理作業(yè)用戶長(zhǎng)作業(yè)將依次在第1，2，3…，n隊(duì)列中執(zhí)行，最終按輪轉(zhuǎn)方式運(yùn)行3.3.6基于公平原則的調(diào)度算法保證調(diào)度算法向用戶做出明確的性能保證易實(shí)現(xiàn)的算法：處理機(jī)分配的公平性當(dāng)工作時(shí)已有n個(gè)用戶登錄在系統(tǒng)，則將獲得CPU處理能力的1/n。類似的，在一個(gè)有n個(gè)進(jìn)程運(yùn)行的用戶系統(tǒng)中，每個(gè)進(jìn)程將獲得CPU處理能力的1/n。實(shí)現(xiàn)方法OS應(yīng)記錄及計(jì)算,各個(gè)進(jìn)程在一定時(shí)間段內(nèi),已經(jīng)使用的CPU時(shí)間和應(yīng)該得到的CPU時(shí)間,二者之比小者優(yōu)先級(jí)高3.3.6基于公平原則的調(diào)度算法公平分享調(diào)度算法每個(gè)用戶分配到CPU時(shí)間的一部分，而調(diào)度程序以一種強(qiáng)制的方式選擇進(jìn)程。這樣，如果兩個(gè)用戶都得到獲得50%CPU時(shí)間的保證，那么無論一個(gè)用戶有多少進(jìn)程存在，每個(gè)用戶都會(huì)得到應(yīng)有的CPU份額。例，用戶1有4個(gè)進(jìn)程A、B、C和D，而用戶2只有1個(gè)進(jìn)程E。如果采用輪轉(zhuǎn)調(diào)度，一個(gè)滿足所有限制條件的可能序列是：AEBECEDEAEBECEDE…3.3.6線程調(diào)度OS只調(diào)度核心級(jí)線程；用戶級(jí)線程必須映射到內(nèi)核線程才能運(yùn)行；本地調(diào)度（進(jìn)程競(jìng)爭(zhēng)范圍，PCS）線程庫決定如何將哪個(gè)線程調(diào)度到有效的LWP上。M::M，M::O全局調(diào)度（系統(tǒng)競(jìng)爭(zhēng)范圍，SCS）內(nèi)核決定調(diào)度那一個(gè)線程到CPU上運(yùn)行。O::O僅采用SCSPCS根據(jù)優(yōu)先級(jí)完成，由程序員設(shè)置。線程調(diào)度API#include<pthread.h>#include<stdio.h>#defineNUM_THREADS5intmain(intargc,char*argv[]){ inti,scope; pthread_ttid[NUM_THREADS]; pthread_attr_tattr; /*getthedefaultattributes*/ pthread_attr_init(&attr); /*settheschedulingalgorithmtoPROCESSorSYSTEM*/ pthread_attr_setscope(&attr,PTHREAD_SCOPE_SYSTEM); /*settheschedulingpolicy-FIFO,RT,orOTHER*/ pthread_attr_setschedpolicy(&attr,SCHED_OTHER);線程調(diào)度API /*createthethreads*/ for(i=0;i<NUM_THREADS;i++) pthread_create(&tid[i],&attr,runner,NULL); /*nowjoinoneachthread*/ for(i=0;i<NUMTHREADS;i++) pthread_join(tid[i],NULL);}/*Eachthreadwillbegincontrolinthisfunction*/void*runner(void*param){ printf("Iamathread\n"); pthread_exit(0);}3.4實(shí)時(shí)調(diào)度3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件3.4.2實(shí)時(shí)調(diào)度算法的分類3.4.3最早截止時(shí)間優(yōu)先算法3.4.4最低松弛度優(yōu)先算法3.4.5優(yōu)先級(jí)倒置3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件提供必要的信息就緒時(shí)間。開始截止時(shí)間和完成截止時(shí)間。處理時(shí)間。資源要求。優(yōu)先級(jí)。3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件系統(tǒng)處理能力強(qiáng)假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件，系統(tǒng)才是可調(diào)度的：

3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件系統(tǒng)處理能力強(qiáng)提高系統(tǒng)的處理能力的途徑采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減少對(duì)每一個(gè)任務(wù)的處理時(shí)間；采用多處理機(jī)系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為N，則應(yīng)將上述的限制條件改為：

3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件采用搶占式調(diào)度機(jī)制在含有硬實(shí)時(shí)任務(wù)的實(shí)時(shí)系統(tǒng)中，廣泛采用搶占機(jī)制。存在的問題：調(diào)度機(jī)制比較復(fù)雜。解決策略：對(duì)于一些小型實(shí)時(shí)系統(tǒng)，如果能預(yù)知任務(wù)的開始截止時(shí)間，則對(duì)實(shí)時(shí)任務(wù)的調(diào)度可采用非搶占調(diào)度機(jī)制。關(guān)鍵：應(yīng)使所有的實(shí)時(shí)任務(wù)都比較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時(shí)地將自己阻塞起來3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件具有快速切換機(jī)制對(duì)外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請(qǐng)求中斷時(shí)系統(tǒng)能及時(shí)響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)(其它緊迫任務(wù))?？焖俚娜蝿?wù)分派能力。在完成任務(wù)調(diào)度后，應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時(shí)的速度，應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)匦?，以減少任務(wù)切換的時(shí)間開銷。3.4.2實(shí)時(shí)調(diào)度算法的分類非搶占式調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法工業(yè)生產(chǎn)的群控系統(tǒng)，由一臺(tái)計(jì)算機(jī)控制若干個(gè)相同的(或類似的)對(duì)象，為每一個(gè)被控對(duì)象建立一個(gè)實(shí)時(shí)任務(wù)，并將它們排成一個(gè)輪轉(zhuǎn)隊(duì)列。調(diào)度程序每次選擇隊(duì)列中的第一個(gè)任務(wù)投入運(yùn)行。當(dāng)該任務(wù)完成后，便把它掛在輪轉(zhuǎn)隊(duì)列的末尾，等待下次調(diào)度運(yùn)行，而調(diào)度程序再選擇下一個(gè)(隊(duì)首)任務(wù)運(yùn)行?？色@得數(shù)秒至數(shù)十秒的響應(yīng)時(shí)間，可用于要求不太嚴(yán)格的實(shí)時(shí)控制系統(tǒng)中。3.4.2實(shí)時(shí)調(diào)度算法的分類非搶占式調(diào)度算法非搶占式優(yōu)先調(diào)度算法要求較為嚴(yán)格(響應(yīng)時(shí)間為數(shù)百毫秒)的任務(wù)，采用非搶占式優(yōu)先調(diào)度算法為這些任務(wù)賦予較高的優(yōu)先級(jí)。當(dāng)這些實(shí)時(shí)任務(wù)到達(dá)時(shí)，把它們安排在就緒隊(duì)列的隊(duì)首，等待當(dāng)前任務(wù)自我終止或運(yùn)行完成后才能被調(diào)度執(zhí)行。做了精心的處理后，有可能獲得僅為數(shù)秒至數(shù)百毫秒級(jí)的響應(yīng)時(shí)間，因而可用于有一定要求的實(shí)時(shí)控制系統(tǒng)中。3.4.2實(shí)時(shí)調(diào)度算法的分類搶占式調(diào)度算法基于時(shí)鐘中斷的搶占式優(yōu)先級(jí)調(diào)度算法在某實(shí)時(shí)任務(wù)到達(dá)后，如果該任務(wù)的優(yōu)先級(jí)高于當(dāng)前任務(wù)的優(yōu)先級(jí)，這時(shí)并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時(shí)鐘中斷到來時(shí)，調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給新到的高優(yōu)先級(jí)任務(wù)。能獲得較好的響應(yīng)效果，其調(diào)度延遲可降為幾十毫秒至幾毫秒。因此，此算法可用于大多數(shù)的實(shí)時(shí)系統(tǒng)中。3.4.2實(shí)時(shí)調(diào)度算法的分類搶占式調(diào)度算法立即搶占(ImmediatePreemption)的優(yōu)先級(jí)調(diào)度算法要求操作系統(tǒng)具有快速響應(yīng)外部事件中斷的能力。一旦出現(xiàn)外部中斷，只要當(dāng)前任務(wù)未處于臨界區(qū)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機(jī)分配給請(qǐng)求中斷的緊迫任務(wù)。能獲得非?？斓捻憫?yīng)，可把調(diào)度延遲降低到幾毫秒至100微秒，甚至更低。3.4.3最早截止時(shí)間優(yōu)先EDF(EarliestDeadlineFirst)算法實(shí)現(xiàn)方法優(yōu)先級(jí)確定：根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間愈早，其優(yōu)先級(jí)愈高。實(shí)時(shí)任務(wù)就緒隊(duì)列：按各任務(wù)截止時(shí)間的早晚排序；具有最早截止時(shí)間的任務(wù)排在隊(duì)列的最前面。調(diào)度順序：總是選擇就緒隊(duì)列中的第一個(gè)任務(wù)，為之分配處理機(jī)，使之投入運(yùn)行。適用范圍：既可用于搶占式調(diào)度，也可用于非搶占式調(diào)度方式中。3.4.3最早截止時(shí)間優(yōu)先EDF算法非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)例

任務(wù)到達(dá)時(shí)間開始截止時(shí)間完成時(shí)間

A013B2101C242D364任務(wù)名到達(dá)時(shí)間服務(wù)時(shí)間開始截止時(shí)間開始時(shí)間完成時(shí)間截止與完成差是否能保證03A121B1022C434D603C>A是91035D>C是59B>D是AA0359tBCD3.4.3最早截止時(shí)間優(yōu)先EDF算法ADBBCCDDDB3.4.3最早截止時(shí)間優(yōu)先EDF算法搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)例，兩個(gè)周期性任務(wù)，任務(wù)A的周期時(shí)間為20ms，每個(gè)周期的處理時(shí)間為10ms；任務(wù)B的周期時(shí)間為50ms，每個(gè)周期的處理時(shí)間為25ms。3.4.3最早截止時(shí)間優(yōu)先EDF算法B1的截止時(shí)間到，未完成A1的截止時(shí)間到，未完成3.4.3最早截止時(shí)間優(yōu)先EDF算法搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)采用最早截止時(shí)間優(yōu)先算法的時(shí)間圖。3.4.4最低松弛度優(yōu)先LLF(LeastLaxityFirst)算法實(shí)現(xiàn)方法松弛度=截止時(shí)間-任務(wù)執(zhí)行時(shí)間-當(dāng)前時(shí)間優(yōu)先級(jí)的確定任務(wù)緊急(或松弛)的程度，緊急程度愈高，任務(wù)的優(yōu)先級(jí)就愈高。實(shí)時(shí)任務(wù)就緒隊(duì)列按松弛度排序，松弛度最低的任務(wù)排在隊(duì)列最前面，調(diào)度程序總是選擇隊(duì)列中的隊(duì)首任務(wù)執(zhí)行。主要適用范圍：可搶占調(diào)度也就是任務(wù)的，機(jī)動(dòng)時(shí)間隨著時(shí)間的推移：

就緒隊(duì)列中任務(wù)的松弛度減少

執(zhí)行任務(wù)的松弛度不變調(diào)度時(shí)機(jī)：松弛度為0，或新任務(wù)就緒，或當(dāng)前任務(wù)完成3.4.4最低松弛度優(yōu)先LLF算法例有兩個(gè)周期性實(shí)時(shí)任務(wù)A和B，任務(wù)A要求每45ms執(zhí)行一次，執(zhí)行時(shí)間為15ms；任務(wù)B只要求每60ms執(zhí)行一次，執(zhí)行時(shí)間為40ms。由此可得知任務(wù)A和B每次必須完成的時(shí)間分別為：A1、A2、A3、…和B1、B2、B3、…。3.4.4最低松弛度優(yōu)先LLF算法t1=0時(shí)，A1的松弛度=45-15=30msB1的松弛度=60-40=20ms注意：A1的松弛度<B1的運(yùn)行時(shí)間t2=30時(shí)，A1的松弛度=45-15-30=0msB1的松弛度=60-10-30=20mst1B1t2A1t3=45時(shí)，A2的松弛度=90-15-45=30msB1的松弛度=60-10-45=5mst3B1t4A2t5B2t6A3t7B3t8A4t9B4與t1時(shí)類似注意：B1的松弛度>A1的運(yùn)行時(shí)間被占用3.4.5優(yōu)先級(jí)倒置（priorityinversionproblem）優(yōu)先級(jí)倒置的形成申請(qǐng)使用被搶先等待（阻塞）3.4.5優(yōu)先級(jí)倒置優(yōu)先級(jí)倒置的形成例，有優(yōu)先級(jí)為A、B和C三個(gè)任務(wù)P1，P2和P3，優(yōu)先級(jí)A>B>C，任務(wù)P1和P3使用信號(hào)量S共享資源。3.4.5優(yōu)先級(jí)倒置優(yōu)先級(jí)倒置的解決方法優(yōu)先級(jí)天花板(priorityceiling)當(dāng)任務(wù)申請(qǐng)某資源時(shí)，把該任務(wù)的優(yōu)先級(jí)提升到可訪問這個(gè)資源的所有任務(wù)中的最高優(yōu)先級(jí)。優(yōu)點(diǎn)：簡(jiǎn)單易行，不必進(jìn)行復(fù)雜的判斷。優(yōu)先級(jí)繼承(priorityinheritance)當(dāng)任務(wù)P1申請(qǐng)共享資源S時(shí)，如果S正在被任務(wù)P3使用，通過比較任務(wù)P3與P1的優(yōu)先級(jí)，如發(fā)現(xiàn)任務(wù)P3的優(yōu)先級(jí)小于P1的優(yōu)先級(jí)，則將任務(wù)P3的優(yōu)先級(jí)提升到P1的優(yōu)先級(jí)，任務(wù)P3釋放資源S后，再恢復(fù)任務(wù)P3的原優(yōu)先級(jí)。3.4.5優(yōu)先級(jí)倒置優(yōu)先級(jí)倒置的解決方法例：優(yōu)先級(jí)繼承3.4.6操作系統(tǒng)實(shí)例Solaris調(diào)度WindowsXP調(diào)度Linux調(diào)度Java線程調(diào)度Solaris調(diào)度采用基于優(yōu)先級(jí)的線程調(diào)度。根據(jù)優(yōu)先級(jí)分為四類調(diào)度，分別為：實(shí)時(shí)系統(tǒng)分時(shí)交互每個(gè)類型有不同的優(yōu)先級(jí)和調(diào)度算法。默認(rèn)調(diào)度類型是分時(shí)，采用多級(jí)反饋隊(duì)列動(dòng)態(tài)地調(diào)整優(yōu)先級(jí)和賦予不同長(zhǎng)度的時(shí)間片。3.4.6操作系統(tǒng)實(shí)例Solaris調(diào)度3.4.6操作系統(tǒng)實(shí)例（cont.）Solaris調(diào)度優(yōu)先級(jí)和時(shí)間片之間有反比關(guān)系（默認(rèn)）優(yōu)先級(jí)越高，時(shí)間片越小優(yōu)先級(jí)越低，時(shí)間片越大交互進(jìn)程通常具有更高的優(yōu)先級(jí)。CPU型進(jìn)程有更低的優(yōu)先級(jí)。交互和時(shí)間共享線程的分配表WindowsXP調(diào)度基于優(yōu)先級(jí)的、搶占調(diào)度算法來調(diào)度線程。調(diào)度程序處理調(diào)度一個(gè)被選定運(yùn)行線程一直運(yùn)行到被更高優(yōu)先級(jí)的線程搶占終止時(shí)間片已到調(diào)用了阻塞系統(tǒng)調(diào)用3.4.6操作系統(tǒng)實(shí)例（cont.）WindowsXP調(diào)度調(diào)度程序使用32級(jí)優(yōu)先級(jí)方案確定線程執(zhí)行順序。優(yōu)先級(jí)分為兩大類型：可變類型1~15級(jí)線程；實(shí)時(shí)類型16~31級(jí)線程0級(jí)線程用于內(nèi)存管理。如果沒有就緒線程，調(diào)度空閑線程。WindowsXP內(nèi)核和Win32API的優(yōu)先級(jí)數(shù)值之間有一個(gè)關(guān)系。3.4.6操作系統(tǒng)實(shí)例（cont.）WindowsXP調(diào)度Win32API定義了一個(gè)進(jìn)程可能屬于的一些優(yōu)先級(jí)類型。包括：REALTIME_PRIORITY_CLASSHIGH_PRIORITY_CLASSABOVE_NORMAL_PRIORITY_CLASSNORMAL_PRIORITY_CLASSBELOW_NORMAL_PRIORITY_CLASSIDLE_PRIORITY_CLASS3.4.6操作系統(tǒng)實(shí)例（cont.）WindowsXP調(diào)度每個(gè)給定優(yōu)先級(jí)類型的線程擁有相對(duì)優(yōu)先級(jí)。相對(duì)優(yōu)先級(jí)的值包括：TIME_CRITICALHIGHESTABOVE_NORMALNORMALBELOW_NORMALLOWESTIDLE3.4.6操作系統(tǒng)實(shí)例（cont.）WindowsXP調(diào)度線程的優(yōu)先級(jí)=線程類型+相對(duì)優(yōu)先級(jí)。基礎(chǔ)優(yōu)先級(jí)=每個(gè)類型中NORMAL相對(duì)優(yōu)先級(jí)3.4.6操作系統(tǒng)實(shí)例（cont.）WindowsXP調(diào)度對(duì)于不同優(yōu)先級(jí)類型的線程：時(shí)間片耗盡時(shí)，優(yōu)先級(jí)降低，不低于基礎(chǔ)優(yōu)先級(jí)。當(dāng)從Wait操作返回時(shí)，調(diào)度程序提高它的優(yōu)先級(jí)：鍵盤I/O完成時(shí)，大幅度提高；磁盤I/O完成時(shí)，中等程度提高。對(duì)于交互性程序前臺(tái)進(jìn)程后臺(tái)進(jìn)程3.4.6操作系統(tǒng)實(shí)例（cont.）WindowsXP調(diào)度與線程調(diào)度有關(guān)的API函數(shù)及功能說明Suspend/ResumeThread掛起/激活一個(gè)正在/暫停運(yùn)行的線程Get/SetPriorityClass讀/設(shè)置一個(gè)線程的基本優(yōu)先級(jí)類型Get/SetThreadPrority讀/設(shè)置一個(gè)線程的基本優(yōu)先級(jí)Get/SetProcessPriorityBoost讀/設(shè)置當(dāng)前進(jìn)程優(yōu)先級(jí)提升控制Get/SetThreadPriorityBoost讀/設(shè)置暫時(shí)線程優(yōu)先級(jí)狀態(tài)：在可調(diào)范圍內(nèi)Get/SetProcessAffinityMask讀/設(shè)置進(jìn)程的默認(rèn)處理器集合SetThreadAffinityMask設(shè)置線程的默認(rèn)處理器集合SetThreadIdealProcessor設(shè)置線程的首選處理器，但不限制線程在該處理器SwitchToThread當(dāng)前線程放棄一個(gè)或多個(gè)時(shí)間配額的運(yùn)行Sleep使當(dāng)前線程等待一個(gè)指定的時(shí)間段SleepEx使當(dāng)前線程進(jìn)入等待狀態(tài)3.4.6操作系統(tǒng)實(shí)例（cont.）Linux調(diào)度采用基于優(yōu)先級(jí)的、搶占調(diào)度算法。兩個(gè)獨(dú)立的優(yōu)先級(jí)范圍Real-time范圍：0~99級(jí)Nice范圍：100~140級(jí)每個(gè)處理器都有自己的運(yùn)行隊(duì)列：活動(dòng)隊(duì)列到期隊(duì)列當(dāng)所有任務(wù)耗盡時(shí)間片時(shí)，兩個(gè)隊(duì)列交換3.4.6操作系統(tǒng)實(shí)例（cont.）Linux調(diào)度實(shí)時(shí)任務(wù)分配靜態(tài)優(yōu)先級(jí)。其它的采用動(dòng)態(tài)優(yōu)先級(jí)：nice±5任務(wù)的交互性決定增加/減少5。任務(wù)的交互性決定于它在等待I/O時(shí)沉睡了多長(zhǎng)時(shí)間。睡眠時(shí)間長(zhǎng)=>更多交互=>-5重新計(jì)算時(shí)機(jī)：任務(wù)耗盡了時(shí)間片，被移至到期隊(duì)列中。3.4.6操作系統(tǒng)實(shí)例（cont.）優(yōu)先級(jí)和時(shí)間片長(zhǎng)度的關(guān)系根據(jù)優(yōu)先級(jí)編號(hào)的任務(wù)列表Java線程調(diào)度JVM采用基于優(yōu)先級(jí)的、搶占式線程調(diào)度。如果多個(gè)線程具有同樣的優(yōu)先級(jí)采用FIFO隊(duì)列。JVM調(diào)度一個(gè)線程運(yùn)行，當(dāng)當(dāng)前運(yùn)行線程退出runnable狀態(tài)；高優(yōu)先級(jí)線程到達(dá)runnable狀態(tài)。注意：JVM并不通知線程的時(shí)間片是否耗盡。3.4.6操作系統(tǒng)實(shí)例（cont.）Java線程調(diào)度由于JVM不能保證時(shí)間片，可以采用yield()方法。

while(true){ //performCPU-intensivetask ... Thread.yield(); }yield()控制另一個(gè)相同優(yōu)先級(jí)的進(jìn)程。3.4.6操作系統(tǒng)實(shí)例（cont.）Thread優(yōu)先級(jí)Java線程調(diào)度優(yōu)先級(jí)

注釋Thread.MIN_PRIORITY線程最小優(yōu)先級(jí)Thread.MAX_PRIORITY線程最大優(yōu)先級(jí)Thread.NORM_PRIORITY線程默認(rèn)優(yōu)先級(jí)Priorities可以通過setPriority()方法設(shè)置setPriority(Thread.NORM_PRIORITY+2);3.5死鎖描述3.5.1資源問題3.5.2計(jì)算機(jī)中的死鎖3.5.3死鎖的定義、必要條件和處理方法3.5.1

資源問題死鎖例子設(shè)系統(tǒng)有一臺(tái)打印機(jī)(R1)一臺(tái)掃描儀(R2)，兩進(jìn)程共享這兩臺(tái)設(shè)備。用信號(hào)量S1表示R1是否可用，用信號(hào)量S2表示R2是否可用，S1、S2初值為1。3.5.1

資源問題可重用性資源和消耗性資源可重用性資源，可重復(fù)使用多次的資源。性質(zhì)每類資源的每個(gè)實(shí)例只能分配給一個(gè)進(jìn)程使用，不能共享；資源使用模式：申請(qǐng)→分配→使用→釋放；每個(gè)資源的實(shí)例數(shù)目有限，進(jìn)程不能創(chuàng)建，也不能刪除。3.5.1

資源問題可重用性資源和消耗性資源可消耗性資源，又稱為臨時(shí)性資源，只可使用一次；由一個(gè)進(jìn)程產(chǎn)生，被另一進(jìn)程使用后就再也無用的資源。性質(zhì)每類資源的每個(gè)實(shí)例可以不斷變化；進(jìn)程在運(yùn)行期間可以不斷地創(chuàng)造資源的實(shí)例；進(jìn)程在運(yùn)行期間可以不斷地消耗資源的實(shí)例。3.5.1

資源問題可搶占（剝奪）資源和不可搶占（剝奪）資源可搶占（剝奪）資源：進(jìn)程在獲得這類資源后，該資源可以再被其他進(jìn)程或系統(tǒng)剝奪，如處理機(jī)、內(nèi)存等不可搶占（剝奪）資源：當(dāng)系統(tǒng)把這類資源分配給某個(gè)進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自行釋放，如磁帶機(jī)、打印機(jī)等3.5.2計(jì)算機(jī)系統(tǒng)中的死鎖競(jìng)爭(zhēng)不可搶占性資源

由于數(shù)量有限而不能滿足進(jìn)程運(yùn)行的需要，進(jìn)程在運(yùn)行過程中因爭(zhēng)奪這些資源而限入僵局競(jìng)爭(zhēng)可消耗性資源共同點(diǎn)：形成環(huán)路??！R1R2P1P2分配分配請(qǐng)求請(qǐng)求I/O設(shè)備共享S2P1S3P3S1P2P1產(chǎn)生P2產(chǎn)生P3產(chǎn)生要求接收要求接收要求接收進(jìn)程之間通信3.5.2計(jì)算機(jī)系統(tǒng)中的死鎖進(jìn)程推進(jìn)順序不當(dāng)引起死鎖P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④D不安全區(qū)3.5.3

死鎖的定義、必要條件和處理方法死鎖的定義多個(gè)進(jìn)程因競(jìng)爭(zhēng)共享資源而造成的一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。即：一組進(jìn)程中，每個(gè)進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，此現(xiàn)象稱為進(jìn)程死鎖，該組進(jìn)程就稱為死鎖進(jìn)程。3.5.3

死鎖的定義、必要條件和處理方法關(guān)于死鎖的一些結(jié)論參與死鎖的進(jìn)程最少是兩個(gè)參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源參與死鎖的所有進(jìn)程都在等待資源參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。3.5.3

死鎖的定義、必要條件和處理方法產(chǎn)生死鎖的必要條件互斥

進(jìn)程對(duì)所分配到的資源進(jìn)行排它性的使用請(qǐng)求和保持

進(jìn)程已經(jīng)至少保持了一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源又已被其他進(jìn)程占有不可搶占

進(jìn)程已獲得的資源在未使用完之前不能被剝奪循環(huán)等待在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程--資源循環(huán)等待的環(huán)形鏈3.5.3

死鎖的定義、必要條件和處理方法處理死鎖的方法預(yù)防死鎖通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件，來防止發(fā)生死鎖。避免死鎖不采用各種限制措施去破壞產(chǎn)生死鎖的必要條件，防止系統(tǒng)進(jìn)入不安全狀態(tài)，只需在事先加以較弱的限制條件。檢測(cè)與解除死鎖允許系統(tǒng)在運(yùn)行過程中發(fā)生死鎖。一旦檢測(cè)到死鎖，常用的實(shí)施方法是撤消或掛起一些進(jìn)程，以便回收一些資源，再將這些資源分配給已處于阻塞狀態(tài)的進(jìn)程，使之轉(zhuǎn)為就緒狀態(tài)，以繼續(xù)運(yùn)行。3.6預(yù)防死鎖3.6.1破壞“請(qǐng)求和保持”條件3.6.2破壞“不可搶占”條件3.6.3破壞“循環(huán)等待”條件3.6.1破壞“請(qǐng)求和保持”條件非請(qǐng)求所有進(jìn)程在開始運(yùn)行之前必須一次性的申請(qǐng)整個(gè)運(yùn)行過程所需的全部資源優(yōu)點(diǎn)：簡(jiǎn)單、易于實(shí)現(xiàn)、安全缺點(diǎn)：資源浪費(fèi)嚴(yán)重進(jìn)程延遲運(yùn)行3.6.1破壞“請(qǐng)求和保持”條件非保持申請(qǐng)其他資源之前，必須釋放其現(xiàn)在已分配的所有資源。優(yōu)點(diǎn)：資源利用率高；減少進(jìn)程發(fā)生饑餓的可能性。缺點(diǎn)：需要資源協(xié)調(diào)工作時(shí)，可能無法實(shí)現(xiàn)。3.6.2破壞“不可搶占”條件可搶占進(jìn)程逐個(gè)地申請(qǐng)所需資源當(dāng)一個(gè)已經(jīng)保持了某些資源的進(jìn)程申請(qǐng)新資源而不能得到滿足時(shí)，必須放棄所有已保持的資源缺點(diǎn)實(shí)現(xiàn)復(fù)雜、代價(jià)高昂延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間，還增加了系統(tǒng)開銷，降低了系統(tǒng)的吞吐量3.6.3破壞“循環(huán)等待”條件順序等待系統(tǒng)將所有資源按類型分配序號(hào)并排隊(duì)；所有進(jìn)程申請(qǐng)資源必須按序號(hào)遞增的順序。優(yōu)點(diǎn)資源利用率和系統(tǒng)吞吐量較高。序號(hào)資源1輸入機(jī)2打印機(jī)3磁帶機(jī)進(jìn)程需求資源P1打印機(jī)磁帶機(jī)P2磁帶機(jī)打印機(jī)例子3.6.3破壞“循環(huán)等待”條件3.6.3破壞“循環(huán)等待”條件存在問題資源所分配的序號(hào)，必須相對(duì)穩(wěn)定，這就限制了新設(shè)備類型的增加。進(jìn)程使用各資源的順序，與系統(tǒng)規(guī)定的順序不同，造成對(duì)資源的浪費(fèi)。按規(guī)定次序申請(qǐng)資源的方法，必然會(huì)限制了用戶簡(jiǎn)單、自主地編程。3.7避免死鎖3.7.1系統(tǒng)安全狀態(tài)3.7.2利用銀行家算法避免死鎖3.7.3利用資源分配圖法避免死鎖3.7避免死鎖提前獲取“進(jìn)程申請(qǐng)資源的附加信息”最簡(jiǎn)單且有效的模型要求每個(gè)進(jìn)程事先聲明它所需要的每種資源的最大數(shù)量。動(dòng)態(tài)檢查資源分配狀態(tài)，以保證不存在循環(huán)等待的條件。資源分配狀態(tài)通過可用資源數(shù)量、已分配資源數(shù)量，及進(jìn)程最大申請(qǐng)數(shù)量來定義。3.7.1系統(tǒng)安全狀態(tài)安全狀態(tài)安全序列：進(jìn)程序列<P1,P2,…,Pn>，如果對(duì)于每個(gè)Pi，Pi申請(qǐng)的資源小于當(dāng)前可用資源加上所有進(jìn)程Pj（其中j<i）所占有的資源。安全狀態(tài)：存在安全序列的系統(tǒng)狀態(tài)；不安全狀態(tài)：不存在安全序列的系統(tǒng)狀態(tài)；結(jié)論如果系統(tǒng)是安全的，則不會(huì)死鎖；如果系統(tǒng)不安全，可能會(huì)發(fā)生死鎖；3.7.1系統(tǒng)安全狀態(tài)避免死鎖的實(shí)質(zhì)允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，但在進(jìn)行資源分配時(shí)，如果不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則分配資源給進(jìn)程，否則，令進(jìn)程等待。關(guān)鍵：確保系統(tǒng)不會(huì)進(jìn)入不安全狀態(tài)。3.7.1系統(tǒng)安全狀態(tài)安全狀態(tài)之例假定系統(tǒng)中有三個(gè)進(jìn)程P1、P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，如下表所示：29P324P23510P1可用已分配最大需求進(jìn)程415100109312存在安全序列：P2-P1-P3，系統(tǒng)處于安全狀態(tài)。3.7.1系統(tǒng)安全狀態(tài)由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果不按照安全序列分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在T0時(shí)刻以后，P3又請(qǐng)求1臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。進(jìn)程最大需求已分配可用P11053P242P39232404不安全狀態(tài)

3.7.2利用銀行家算法避免死鎖銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(1)可利用資源向量Available。一個(gè)有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。3.7.2利用銀行家算法避免死鎖銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(2)最大需求矩陣Max。n×m的矩陣，系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max[i][j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。(3)分配矩陣Allocation。n×m的矩陣，每一類資源已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i][j]=K，表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。(4)需求矩陣Need。n×m的矩陣，每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need[i][j]=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，才能完成其任務(wù)。Need[i][j]=Max[i][j]–Allocation[i][j]3.7.2利用銀行家算法避免死鎖銀行家算法設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requesti[j]=K，進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出請(qǐng)求后，按下述步驟進(jìn)行檢查：(1)若Requesti[j]≤Need[i][j]，便轉(zhuǎn)向步驟(2)；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。(2)若Requesti[j]≤Available[j]，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。3.7.2利用銀行家算法避免死鎖銀行家算法(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

Available[j]=Available[j]-Requesti[j];Allocation[i][j]=Allocation[i][j]+Requesti[j];Need[i][j]=Need[i][j]-Requesti[j];(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。3.7.2利用銀行家算法避免死鎖安全性算法(1)設(shè)置兩個(gè)向量：①Work:可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work=Available;②Finish:是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。初值Finish[i]=false;當(dāng)有足夠資源分配給進(jìn)程時(shí)，令Finish[i]=true。3.7.2利用銀行家算法避免死鎖安全性算法(2)從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：①Finish[i]=false;②Need[i][j]≤Work[j]；若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。(3)當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：

Work[j]=Work[i]+Allocation[i][j];Finish[i]=true;

轉(zhuǎn)step2;(4)如果所有進(jìn)程的Finish[i]=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。3.7.2利用銀行家算法避免死鎖假定系統(tǒng)中有五個(gè)進(jìn)程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如下表。CB01001B32223C32025B04P439P223307P022P323P1AAAAvailableNeedAllocationMaxCB21200C110233102446701A3.7.2利用銀行家算法避免死鎖(1)T0時(shí)刻的安全性：truetruetruetruetrueFinish77532C54443B02210C10010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork+AllocationAllocationNeedWork存在安全序列：P1-P3-P4-P2-P0，系統(tǒng)在T0時(shí)刻處于安全狀態(tài)。P4P2P0P3P1NeedCB110233102446701AP4P2P0P3P1NeedCB110233102446701A3.7.2利用銀行家算法避免死鎖(2)P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available1(3,3,2)MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P44330024313.7.2利用銀行家算法避免死鎖③系統(tǒng)先假定可為P1分配資源，并修改Available,Allocation1和Need1向量。Request1(1，0，2)2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMax3220000323.7.2利用銀行家算法避免死鎖④再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。truetruetruetruetrueFinish75532C55443B20212C01010B03110C04312B55320C54433B10367P27047P45302P17077P07205P3AAAAWork+AllocationAllocationNeedWork存在安全序列：P1-P3-P4-P0-P2，系統(tǒng)處于安全狀態(tài)，可以滿足P1資源分配請(qǐng)求。3.7.2利用銀行家算法避免死鎖(3)P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)≤Available(2,3,0)，讓P4等待。MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P44330024313.7.2利用銀行家算法避免死鎖(4)P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量Request0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P44330024313.7.2利用銀行家算法避免死鎖③系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)。Request0(0，2，0)MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431723210030不安全狀態(tài)3.7.2利用銀行家算法避免死鎖(5)P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量改為Request0(0,1,0)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request0(0,1,0