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

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