資源分配與調(diào)度.ppt

第五章 資源分配與調(diào)度,（一） 資源管理功能 （二） 資源分配的機(jī)構(gòu)和策略 （三） 死鎖概念,（一） 資源管理功能,一. 資源管理功能 1. 目的： 保證資源的高利用率； 在“合理”時(shí)間內(nèi)使所有顧客有獲得所需資源的機(jī)會(huì)； 對(duì)不可共享的資源實(shí)施互斥使用； 防止由資源分配不當(dāng)而引起的死鎖。,2. 資源管理的任務(wù)： 資源管理的描述數(shù)據(jù)結(jié)構(gòu) 確定資源的分配原則（調(diào)度原則） 執(zhí)行資源分配（實(shí)施） 存取控制和安全保護(hù),二. 資源的靜態(tài)分配和動(dòng)態(tài)分配,1. 資源的靜態(tài)分配 系統(tǒng)對(duì)作業(yè)一級(jí)采用資源靜態(tài)分配方法。 當(dāng)一個(gè)進(jìn)程（或程序）運(yùn)行前，將它要求的資源一次分配加該進(jìn)程，直到該進(jìn)程終止，釋放其占用的所有資源。 特點(diǎn)：效率太低 2. 資源的動(dòng)態(tài)分配 系統(tǒng)對(duì)進(jìn)程一級(jí)采用資源靜態(tài)分配方法。 系統(tǒng)在進(jìn)程運(yùn)行中，根據(jù)進(jìn)程提出的資源需求，進(jìn)行資源的動(dòng)態(tài)分配和回收。 特點(diǎn)：資源利用率提高，但有可能造成死鎖,（二） 資源分配的機(jī)構(gòu)和策略,一. 資源分配機(jī)構(gòu) 1. 資源描述器 （1） 什么是資源描述器 描述各類(lèi)資源的最小分配單位的數(shù)據(jù)結(jié)構(gòu)稱(chēng)為資源描述器rd（resource descriptor）。 如：主存的最小分配單位： 在分頁(yè)分配中主存頁(yè)面 磁盤(pán)的最小分配單位： 磁盤(pán)面中的一個(gè)扇區(qū),（2） 資源描述器的內(nèi)容,資源名 資源類(lèi)型 最小分配單位的大小 最小分配單位的地址 分配標(biāo)志 描述器鏈接信息 存取權(quán)限 密級(jí) 最后一次存取時(shí)間 記帳信息,2. 資源信息塊,（1） 什么是資源信息塊 描述某類(lèi)資源的請(qǐng)求者、可用資源情況和該類(lèi)資源分配程序等必要信息的數(shù)據(jù)結(jié)構(gòu)。 （2） 資源信息塊的內(nèi)容,（3） 中央處理機(jī)資源信息塊,二. 資源分配策略,1. 先請(qǐng)求先服務(wù)（FIFO策略） 排序原則：按請(qǐng)求的先后次序排序。 每個(gè)新產(chǎn)生的請(qǐng)求均排在隊(duì)尾，而當(dāng)資源可用時(shí)，資源分配程序從隊(duì)列中選取第一個(gè)請(qǐng)求，并滿(mǎn)足其需要。,適用范圍：系統(tǒng)中的一切資源。 優(yōu)點(diǎn)：簡(jiǎn)單、系統(tǒng)開(kāi)銷(xiāo)小。 缺點(diǎn)：有時(shí)顯得不合理，系統(tǒng)無(wú)法進(jìn)行干預(yù)。,2. 優(yōu)先調(diào)度,在優(yōu)先調(diào)度策略下，對(duì)于每一個(gè)進(jìn)程（或作業(yè)）要指定一個(gè)優(yōu)先級(jí)，優(yōu)先級(jí)反映了進(jìn)程要求處理的緊迫程度。 排序原則：按優(yōu)先級(jí)的高低排序。 每一個(gè)新產(chǎn)生的請(qǐng)求，按其優(yōu)先級(jí)的高低插到相應(yīng)的位置上。而當(dāng)資源可用時(shí)，選取隊(duì)列中第一個(gè)請(qǐng)求，并滿(mǎn)足其需要。 優(yōu)先級(jí)的確定：主要由系統(tǒng)來(lái)確定，并可動(dòng)態(tài)改變。 使用范圍：由于系統(tǒng)開(kāi)銷(xiāo)大，主要適用于系統(tǒng)中的緊缺資源。便于資源的動(dòng)態(tài)分配。,3、適應(yīng)調(diào)度 4、均衡調(diào)度 5、針對(duì)設(shè)備特性的調(diào)度 移臂調(diào)度 旋轉(zhuǎn)調(diào)度,（三） 死鎖,一. 什么是死鎖 1. 死鎖的例子 （1） 設(shè)備共享 進(jìn)程PA、PB，共享一臺(tái)打印機(jī)和一臺(tái)磁帶機(jī) 時(shí)刻t1：進(jìn)程PA占用打印機(jī) 進(jìn)程PB占用磁帶機(jī) 時(shí)刻t2：進(jìn)程PA又請(qǐng)求磁帶機(jī) 進(jìn)程PB又請(qǐng)求打印機(jī) 問(wèn)：以后會(huì)發(fā)生什么情況？,（2） 用信號(hào)燈的P、V操作描述死鎖,上例中，用信號(hào)燈的P、V操作表示資源的申請(qǐng)和釋放。 信號(hào)燈設(shè)置： S1：表示設(shè)備R1可用，初值為1 S2：表示設(shè)備R2可用，初值為1 討論兩種資源請(qǐng)求序列，哪種情況可能產(chǎn)生互相死等的局面。,在這兩個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)，當(dāng)P1進(jìn)程占有R1、P2進(jìn)程占用R2時(shí)，P1要求R2，由于P2已占R2有而得不到，P1進(jìn)程只有等待；P2申請(qǐng)R1，由于P1已占有R1，而得不到，P2進(jìn)程只有等待，從而出現(xiàn)了死鎖的情況。,2,例2：三個(gè)進(jìn)程共享使用一臺(tái)打印機(jī)的程序若有一個(gè)進(jìn)程少寫(xiě)了一個(gè)V操作。,2. 什么是死鎖,死鎖簡(jiǎn)單的定義： 死鎖就是兩個(gè)或兩個(gè)以上的進(jìn)程等候著一個(gè)永遠(yuǎn)不會(huì)發(fā)生的事件時(shí)所處的一種系統(tǒng)狀態(tài)。 教材上關(guān)于死鎖的定義： 兩個(gè)或兩個(gè)以上并發(fā)進(jìn)程，如果每個(gè)進(jìn)程持有某種資源，而又等待著別的進(jìn)程釋放它或它們現(xiàn)在保持著的資源，否則就不能向前推進(jìn)。此時(shí)，每個(gè)進(jìn)程都占用了一定的資源，但又都不能向前推進(jìn)。這種現(xiàn)象稱(chēng)為死鎖。,二. 死鎖的起因和條件,1. 引起死鎖的原因 系統(tǒng)資源不足； 進(jìn)程推進(jìn)順序非法。,2. 死鎖的圖解,3. 產(chǎn)生死鎖的四個(gè)必要條件：,1. 互斥條件 2. 不可剝奪條件 3. 部分分配 4.環(huán)路條件,三. 死鎖的預(yù)防和避免,基本點(diǎn)：破壞死鎖的某一個(gè)必要條件 1. 解決死鎖問(wèn)題的幾個(gè)策略 為了不發(fā)生死鎖，必須設(shè)法破壞產(chǎn)生死鎖的四個(gè)必要條件之一。,條件2（不可剝奪條件）：容易否定，可制定相應(yīng)的規(guī)則即可，例如，當(dāng)一個(gè)進(jìn)程（程序）申請(qǐng)某資源被拒絕，則必須釋放已占用的資源，如需要再與其它所需資源一起申請(qǐng)。對(duì)CPU還可進(jìn)行可剝奪分配。,條件1（互斥條件）：難以否定，但可采用相應(yīng)的技術(shù)，如利用假脫機(jī)技術(shù)，即用可共享使用的設(shè)備模擬非共享的設(shè)備；,條件4（環(huán)路條件）：實(shí)際上系統(tǒng)不采用部分分配，也就破壞了環(huán)路條件。,條件3（部分分配）：也是很容易否定的，只要分配策略上規(guī)定一個(gè)進(jìn)程（或程序）一次將所需資源一次申請(qǐng)到位。用完后釋放?？梢匀坑猛旰?，統(tǒng)一釋放，也可使用完后立即釋放，只要是一次申請(qǐng)到的，系統(tǒng)就不會(huì)出現(xiàn)死鎖。,2. 靜態(tài)預(yù)防死鎖的方法,在作業(yè)調(diào)度時(shí)為選中的作業(yè)分配它所需的所有資源，當(dāng)資源一旦分配給該作業(yè)，在其整個(gè)運(yùn)行期間這些資源為它獨(dú)占。 討論： （1） 這種方法破壞了死鎖的必要條件中的哪一條？ （2）這種方法的資源利用率高不高？為什么？,這種方法安全而簡(jiǎn)單的方法，但設(shè)備的使用效率太低。其缺點(diǎn)也是明顯的： 1. 一個(gè)用戶(hù)（進(jìn)程）在程序運(yùn)行之前艱難提出將要使用的全部設(shè)備； 2. 用戶(hù)作業(yè)必須等待，直到所有資源滿(mǎn)足時(shí)才能投入運(yùn)行。 3. 設(shè)備（資源）的浪費(fèi)太大，有些資源在進(jìn)程運(yùn)行過(guò)程中可能只有很少的時(shí)間才用到，有的甚至不會(huì)用到，例如，一個(gè)分枝語(yǔ)句。,3. 動(dòng)態(tài)避免死鎖的方法,為了提高設(shè)備的利用率，應(yīng)采用動(dòng)態(tài)的設(shè)備分配方法，但應(yīng)設(shè)法避免發(fā)生死鎖，若存在發(fā)生死鎖的可能性，則拒絕分配。 預(yù)防死鎖： 采用的分配策略本身就否定了產(chǎn)生死鎖的四個(gè)必要條件之一，這就保證了不會(huì)發(fā)生死鎖； 死鎖避免： 是在動(dòng)態(tài)分配資源的策略下采用某種算法來(lái)預(yù)防可能發(fā)生的死鎖，從而拒絕可能產(chǎn)生死鎖的某個(gè)資源的請(qǐng)求。,系統(tǒng)中所有資源都按某種規(guī)則統(tǒng)一編號(hào)（例如打印機(jī)為1、磁帶機(jī)為2、磁盤(pán)為3、等等），所有分配請(qǐng)求必須以上升的次序進(jìn)行。當(dāng)遵守上升次序的規(guī)則時(shí)，若資源可用，則預(yù)以分配；否則，請(qǐng)求者等待。 系統(tǒng)要求申請(qǐng)進(jìn)程： 1. 對(duì)它所必須使用的而且屬于同一類(lèi)的所有資源，必須一次申請(qǐng)完； 2. 在申請(qǐng)不同類(lèi)資源時(shí)，必須按各類(lèi)設(shè)備的編號(hào)依次申請(qǐng)。 討論：這種方法破壞了死鎖的必要條件中的哪一條？為什么？,（1）有序資源分配法,例如：進(jìn)程PA，使用資源的順序是R1，R2； 進(jìn)程PB，使用資源的順序是R2，R1； 若采用動(dòng)態(tài)分配有可能形成環(huán)路條件，造成死鎖。 采用有序資源分配法：R1的編號(hào)為1，R2的編號(hào)為2； PA：申請(qǐng)次序應(yīng)是：R1，R2 PB：申請(qǐng)次序應(yīng)是：R1，R2 這樣就破壞了環(huán)路條件，避免了死鎖的發(fā)生。,（2） 銀行算法,避免死鎖算法中最有代表性的算法是Dijkstra E.W 于1968年提出的銀行家算法： 該算法需要檢查申請(qǐng)者對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的各類(lèi)資源可以滿(mǎn)足申請(qǐng)者的請(qǐng)求，就滿(mǎn)足申請(qǐng)者的請(qǐng)求。 這樣申請(qǐng)者就可很快完成其計(jì)算，然后釋放它占用的資源，從而保證了系統(tǒng)中的所有進(jìn)程都能完成，所以可避免死鎖的發(fā)生。,例子：假定系統(tǒng)有10個(gè)資源（為了說(shuō)明問(wèn)題的簡(jiǎn)單，不管它是什么資源），目前分配的情況如上表： 此時(shí)，系統(tǒng)中只剩下2個(gè)資源，這時(shí)就要考察能滿(mǎn)足哪個(gè)進(jìn)程，不能滿(mǎn)足P和R的最大要求，能滿(mǎn)足Q，于是將剩下的2個(gè)資源分配給Q，Q就能完成，然后釋放所占用的6個(gè)資源。 可滿(mǎn)足P，也可滿(mǎn)足R，這