【正文】 第三章 處理機(jī)調(diào)度與死鎖 作業(yè) 2： 設(shè)有三個(gè)作業(yè) ， 它們到達(dá)系統(tǒng)的時(shí)間和計(jì) 算時(shí)間如下： J1： 8： 00到達(dá) 計(jì)算時(shí)間 2個(gè)小時(shí) J2： 8： 30到達(dá) 計(jì)算時(shí)間 1個(gè)小時(shí) J3： 9： 30到達(dá) 計(jì)算時(shí)間 系統(tǒng)按單道方式運(yùn)行 ， 采用響應(yīng)比高者優(yōu) 先調(diào)度 ， 在 9： 30開始調(diào)度時(shí) ， 試寫出作業(yè) 調(diào)度次序 。 為把系統(tǒng)從死鎖狀態(tài)中解脫出來 ， 所花費(fèi)的代價(jià)可表示為： R(S)min=min{Cui}+min{Cuj}+min{Cuk}+… 第三章 處理機(jī)調(diào)度與死鎖 圖 321 付出代價(jià)最小的死鎖解除方法 U1V12V13V1kW132W134W13kP2P3……P2P4… Pk…PkU2V21V22V2kW231W234W23k…P1P4… Pk…UkVk1Vk2VkkWk21Wk22Wk2k……Pk… …SP1(cu1) P1(cuk)P1(cud)第三章 處理機(jī)調(diào)度與死鎖 作業(yè) 1： 假定一個(gè)處理機(jī)上執(zhí)行的作業(yè)如下： 作業(yè) 提交時(shí)間 短暫時(shí)間段長度 優(yōu)先數(shù) 1 0 7 3 2 1 4 1 3 2 2 6 4 3 1 4 5 3 5 2 且規(guī)定優(yōu)先數(shù)大優(yōu)先級(jí)別高 。 ?第三章 處理機(jī)調(diào)度與死鎖 死鎖的解除 (1) 剝奪資源。 Li∪ L。 Work ∶ =Available。 第三章 處理機(jī)調(diào)度與死鎖 (4) 若不能把所有進(jìn)程都記入 L表中 ， 便表明系統(tǒng)狀態(tài) S的資源分配圖是不可完全簡(jiǎn)化的 。 (3) 從進(jìn)程集合中找到一個(gè) Requesti≤Work的進(jìn)程 ， 做如下處理： ① 將其資源分配圖簡(jiǎn)化 ， 釋放出資源 ， 增加工作向量Work∶ =Work+Allocationi。 第三章 處理機(jī)調(diào)度與死鎖 2. 死鎖定理 圖 320 資源分配圖的簡(jiǎn)化 ( a ) ( b )P1( c )P1P2P1P2P2第三章 處理機(jī)調(diào)度與死鎖 3. 死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量 Available， 它表示了 m類資源中每一類資源的可用數(shù)目 。 ??第三章 處理機(jī)調(diào)度與死鎖 圖 318 為 P0分配資源后的有關(guān)資源數(shù)據(jù) 第三章 處理機(jī)調(diào)度與死鎖 死鎖的檢測(cè)與解除 死鎖的檢測(cè) 1. 資源分配圖 (Resource Allocation Graph) 圖 319 每類資源有多個(gè)時(shí)的情況 P1P2r1r2第三章 處理機(jī)調(diào)度與死鎖 (2) 凡屬于 E中的一個(gè)邊 e∈ E， 都連接著 P中的一個(gè)結(jié)點(diǎn)和 R中的一個(gè)結(jié)點(diǎn) ， e={pi, rj}是資源請(qǐng)求邊 ， 由進(jìn)程 pi指向資源 rj， 它表示進(jìn)程 pi請(qǐng)求一個(gè)單位的 rj資源 。 ② Request0(0, 2, 0)≤Available(2, 3, 0)。 ② Request4(3, 3, 0) Available(2, 3, 0)， 讓 P4等待 。 ④ 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。 第三章 處理機(jī)調(diào)度與死鎖 4. 銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程 ｛ P0, P1, P2, P3, P4｝ 和三類資源 ｛ A, B, C｝ ， 各種資源的數(shù)量分別為 7， 在 T0時(shí)刻的資源分配情況如圖 315 所示 。 第三章 處理機(jī)調(diào)度與死鎖 ?設(shè) Work 和 Finish是長度分別為 m,n的向量 初試值 Work： =Available ， Finishi： = False（所有） ?從進(jìn)程集合中找到一個(gè)能滿足下列條件的進(jìn)程 a. Finishi= False b. Needi ? Work 如找到 go to 3 否則 go to 4 ?當(dāng)進(jìn)程 Pi 獲得資源后，順利執(zhí)行，直至完成，并釋放分 配給它的資源。 ?如果 Requesti ? Available 則 go to 3，否則表示無足夠資源， Pi等待。 如果 Need[i,j]=k， 表示進(jìn)程 i還需要 Rj類資源有 k個(gè)。如果 Allocation [i,j]=k，則表示進(jìn)程 i獲得 Rj類資源有 k個(gè) 。 ?Max： 一個(gè) m n矩陣，定義每個(gè)進(jìn)程的最大資源需求數(shù) 如果 Max[i,j]=k,表示進(jìn)程 i需要 Rj類資源有 k個(gè)。 如果系統(tǒng)無法找到這樣一個(gè)安全序列 ，則稱系統(tǒng)處于不安全狀態(tài) 。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài) ， 則將資源分配給進(jìn)程； 否則 ， 令進(jìn)程等待 。 每個(gè)進(jìn)程 釋放 按序號(hào)遞減次序進(jìn)行 申請(qǐng) 按序號(hào)遞增次序進(jìn)行 第三章 處理機(jī)調(diào)度與死鎖 優(yōu)點(diǎn)： ? 資源的申請(qǐng)與分配逐步進(jìn)行 ， 比預(yù)分配策略的資源利用率高； 缺點(diǎn)： ? 嚴(yán)格限制資源的順序性 ， 不允許增加資源請(qǐng)求 ? 在使用資源的順序與系統(tǒng)規(guī)定不一致時(shí) ， 資源利用率降低； ? 不能搶占 。 如 CPU，內(nèi)存。為其分配所有資源，讀卡機(jī)，磁盤文件，打印機(jī)，磁帶機(jī) 按第二種制約： 先申請(qǐng)讀卡機(jī)，磁盤文件 ?釋放兩者 ?申請(qǐng)磁盤文件，打印機(jī) ?釋放兩者 ?申請(qǐng)磁盤文件，磁帶機(jī) ?釋放兩者。 第三章 處理機(jī)調(diào)度與死鎖 例 1：如果有這樣進(jìn)程，它從讀卡機(jī)中拷貝磁盤 文件，排序磁盤文件，然后將結(jié)果打印在打印機(jī) 上，并將起拷貝到磁帶。 ? 故不能通過取消互斥來預(yù)防死鎖。 預(yù)防死鎖是一種較可取的方法，但資源的利用率較低。 (4) 解除死鎖。 (2) 避免死鎖。 例如 ， 當(dāng) P1運(yùn)行到 P1:Request(R2)時(shí) ， 將因 R2已被 P2占用而阻塞；當(dāng) P2運(yùn)行到 P2: Request(R1)時(shí) ， 也將因R1已被 P1占用而阻塞 ， 于是發(fā)生了進(jìn)程死鎖 。 此時(shí) P1保持了資源 R1, P2保持了資源 R2, 系統(tǒng)處于不安全狀態(tài) 。 (2) 進(jìn)程間推進(jìn)順序非法。 申請(qǐng)一頁 申請(qǐng)一頁 釋放一頁 釋放一頁 第三章 處理機(jī)調(diào)度與死鎖 死鎖的產(chǎn)生：各進(jìn)程的執(zhí)行次序輪轉(zhuǎn) R1 R2 R3 P1 P2 P3 P4 M=3， N=4 框：資源 圈：進(jìn)程 圈 ?框：分配邊 框 ?圈：請(qǐng)求邊 第三章 處理機(jī)調(diào)度與死鎖 例 3：不同類型資源 假定系統(tǒng)有 N種外部設(shè)備 R1， R2???RN，系統(tǒng)又有 N 個(gè)進(jìn)程 P1， P2 ???PN，它們以這種方式要求資源 。 不安全狀態(tài)：永遠(yuǎn)不具有成交的可能，則為不安全。 第三章 處理機(jī)調(diào)度與死鎖 死鎖的產(chǎn)生：當(dāng)各顧客借款總額之和大于銀行可借用資金總和，而每顧客都未達(dá)到他的預(yù)定最大借款額。 ? 每當(dāng)顧客提出借款請(qǐng)求，銀行可立即給予，或讓顧客等一段時(shí)間。 第三章 處理機(jī)調(diào)度與死鎖 例 1銀行借款 假定某行有一筆法郎可供一批顧客借用， 并假定： ? 每個(gè)顧客預(yù)知他的最大借款總額，且不超過銀行擁有可用資金總和。 該算法主要用于可搶占調(diào)度方式 第三章 處理機(jī)調(diào)度與死鎖 A和 B任務(wù)每次必須完成的時(shí)間 A