資源分配與調度.ppt

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