【正文】 如果在銀行家算法中，把 P0發(fā)出的請求向量改為Request0(0， 1， 0)，系統(tǒng)是否能將資源分配給它？ 第三章 處理機調度與。如圖 318所示。 第三章 處理機調度與死鎖 4． 銀行家算法之例 假定系統(tǒng)中有五個進程 {P0， P1， P2， P3， P4}和三類資源{A， B， C}，各種資源的數(shù)量分別為 7，在 T0時刻的資源分配情況如圖 316所示。 ② Finish，它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。 (2) 如果 Requesti[j]≤Available[j] ，便轉向步驟 (3)；否則，表示尚無足夠資源， Pi須等待。 這也是一個 n m的矩陣 ， 用以表示每一個進程尚需的各類資源數(shù) 。 第三章 處理機調度與死鎖 (3) 分配矩陣 Allocation。 如果Available[j]=K， 則表示系統(tǒng)中現(xiàn)有 Rj類資源 K個 。銀行家算法 ?銀行家擁有一筆周轉資金 ?客戶要求分期貸款 ， 如果客戶能夠得到各期貸款 ， 就一定能夠歸還貸款 ， 否則就一定不能歸還貸款 ?銀行家應謹慎的貸款 ， 防止出現(xiàn)壞帳 ?用銀行家算法避免死鎖 ?操作系統(tǒng) （ 銀行家 ） ?操作系統(tǒng)管理的資源 (周轉資金 ) ?進程 （ 要求貸款的客戶 ） 第三章 處理機調度與死鎖 ?銀行家 算法思想： 該算法需要檢查申請者對資源的最大需求量，如果系統(tǒng) 現(xiàn)存的各類資源 可以滿足申請者的請求，就滿足申請者的請求。因為此時也無法再找到一個安全序列，從給 P3分配了第3臺磁帶機開始，系統(tǒng)便又進入了不安全狀態(tài)。假定系統(tǒng)中有三個進程 P P2和 P3，共有 12臺磁帶機。 第三章 處理機調度與死鎖 所謂 安全狀態(tài) ， 是指系統(tǒng)能按某種進程順序 (P1， P2， …，Pn)(稱 〈 P1， P2， …， Pn〉 序列為安全序列 )， 來為每個進程 Pi分配其所需資源 ， 直至滿足每個進程對資源的最大需求 ， 使每個進程都可順利地完成 。 ?為方便用戶，系統(tǒng)對用戶在編程時所施加的限制條件應盡量少。事實上，在采用這種策略時，總有一個進程占據(jù)了較高序號的資源，此后它繼續(xù)申請的資源必然是空閑的，因而進程可以一直向前推進。 這種預防死鎖的方法實現(xiàn)起來 比較復雜且要付出很大的代價。 ?缺點 (1)資源被嚴重浪費 ，因為一個進程是一次性地獲得其整個運行過程所需的全部資源的，且獨占資源，其中可能有些資源很少使用，甚至在整個運行期間都未使用，這就嚴重地惡化了系統(tǒng)資源的利用率； (2)使進程延遲運行 ，僅當進程在獲得了其所需的全部資源后，才能開始運行，但可能因有些資源已長期被其它進程占用而致使等待該資源的進程遲遲不能運行。 第三章 處理機調度與死鎖 預防、避免死鎖的方法 預防死鎖 1．破壞 “ 互斥 ” 條件，很難， 但可采用相應的技術，如利用假脫機技術，即用可共享使用的設備模擬非共享的設備。這是與檢測死鎖相配套的一種措施。 第三章 處理機調度與死鎖 (3) 檢測死鎖 。 第三章 處理機調度與死鎖 (2) 避免死鎖 。這是一種較簡單和直觀的事先預防的方法。 這 4個條件是必要條件而不是充分條件 。 如果此時還有其它進程請求該資源 ， 則請求者只能等待 ， 直至占有該資源的進程用畢釋放 。 進程 P1產(chǎn)生消息 S1，又要求從 P3接收消息 S3；進程 P3產(chǎn)生消息 S3， 又要求從進程 P2接收其所產(chǎn)生的消息 S2；進程 P2產(chǎn)生消息 S2， 又需要接收進程 P1所產(chǎn)生的消息 S1。（這是事件通知的死鎖） 第三章 處理機調度與死鎖 產(chǎn)生死鎖的原因 ? 死鎖的起因 ?競爭非剝奪性資源 例：有兩個進程 P、 Q，系統(tǒng)僅有一臺磁帶機和打印機。（這是獲取資源的死鎖。 第三章 處理機調度與死鎖 ? 最易理解的死鎖：線程 A、 B死鎖！ ? 兩兄弟相依為命，靠打獵為生，家里面有兩把槍，金槍和銀槍。具體用銀行家算法實現(xiàn)資源分配。 在 t7?=?70 ms時 ， A4的松弛度已減至 0 ms(即 80??10??70)，而 B2的松弛度為 20 ms(即 100??10??70)， 故此時調度又應搶占B2的處理機而調度 A4執(zhí)行 。 在 t3?=?30 ms時 ， A2的松弛度已減為 0(即 40??10??30)，而 B1的松弛度為 15 ms(即 50??5??30)， 于是調度程序應搶占 B1的處理機而調度 A2運行 。由此可得知任務 A和 B每次必須完成的時間分別為： A A A … 和 B B B … ，見圖 311。又如，另一任務在 400 ms時必須完成，它本身需要運行 150 ms，則其松弛程度為 250 ms。在該例中利用最早截止時間優(yōu)先算法可以 滿足系統(tǒng) 的要求。圖中的第一行示出了兩個任務的到達時間、最后期限和執(zhí)行時間圖。由于任務 3的開始截止時間早于任務 2，故系統(tǒng)在任務 1后將調度任務 3執(zhí)行。 可根據(jù)搶占發(fā)生時間的不同而進一步分成以下兩種調度算法 。 (5) 優(yōu)先級。 第三章 處理機調度與死鎖 實 時 調 度 實現(xiàn)實時調度的基本條件 1． 提供必要的信息 (1) 就緒時間 。 ? 高優(yōu)先就緒隊列 —— 當進程從等待狀態(tài)變?yōu)榫途w狀態(tài)時則進入高優(yōu)先就緒隊列。 ??? 短批處理用戶：周轉時間較短，通常三個隊列即可完成。 ?各隊列時間片不同。例如，第二個隊列的時間片要比第一個隊列的時間 片長一倍 ， …… ，第 i+1個隊列的時間片要比第 i個隊列的時間片長一倍。圖中的 RR(Round Robin)表示輪轉調度算法。每次調度時，把 CPU分配給隊首進程，令其執(zhí)行一個時間片，時間片用完后，若進程未結束，則重新排入就緒隊列尾部。 (3) 對于長作業(yè) ， 作業(yè)的優(yōu)先級可以隨等待時間的增加而提高 ， 當其等待時間足夠長時 ， 其優(yōu)先級便可升到很高 ，從而也可獲得處理機 。 要求服務時間要求服務時間等待時間優(yōu)先權 ??第三章 處理機調度與死鎖 由于等待時間與服務時間之和就是系統(tǒng)對該作業(yè)的響應時間，故 響應比 RP =優(yōu)先權。 第三章 處理機調度與死鎖 2) 動態(tài)優(yōu)先權 動態(tài)優(yōu)先權是指在創(chuàng)建進程時所賦予的優(yōu)先權，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調度性能。 這種搶占式的優(yōu)先權調度算法能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴格的 實時 系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。 第三章 處理機調度與死鎖 ? 作為進程調度算法 1) 非搶占式優(yōu)先權算法 在這種方式下，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權最高的進程后，該進程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一優(yōu)先權最高的進程。 (3) 不一定能真正做到短作業(yè)優(yōu)先調度 。它們可以分別用于作業(yè)調度和進程調度。據(jù)此可知， FCFS調度算法 有利于 CPU繁忙型的作業(yè) ，而不利于 I/O繁忙型的作業(yè) (進程 ). 第三章 處理機調度與死鎖 在此，我們通過一個例子來說明采用 FCFS調度算法時的調度性能。該進程一直運行到完成或發(fā)生某事件而阻塞后才放棄處理機。 ??? 平衡系統(tǒng)和用戶要求。選擇適當?shù)恼{度方式和算法可以保持系統(tǒng)中各類資源都處于忙碌狀態(tài)。 對于同一批作業(yè) ， 若采用了較好的調度方式和算法 ， 則可顯著地提高系統(tǒng)的吞吐量 。 第三章 處理機調度與死鎖 2． 面向系統(tǒng)的準則 (1) 系統(tǒng)吞吐量高 。 截止時間 ：是指某任務必須開始執(zhí)行的最遲時間 ， 或必須完成的最遲時間 。 ?響應時間 ：從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應為止的時間，或者說，直到屏幕上顯示出結果為止的一段時間間隔。 ? 周轉時間 ：從作業(yè)被提交給系統(tǒng)開始 ， 到作業(yè)完成為止的這段時間間隔 。在調出操作的作用下，可使進程狀態(tài)由內存就緒轉為外存就緒，由內存阻塞轉為外存阻塞；在中級調度的作用下，又可使外存就緒轉為內存就緒。由于其運行頻率較低，故允許作業(yè)調度算法花費較多的時間。 ? 缺點：開銷較大 。 ??? 在分時系統(tǒng)中，分配給該進程的時間片已用完 第三章 處理機調度與死鎖 3． 進程調度方式 （ 兩種 ） 1) 非搶占方式 (Nonpreemptive Mode) ? 分派程序一旦把處理機分配給某進程后便讓它一直運行下去，直到進程完成或發(fā)生某事件而阻塞時，才把處理機分配給另一個進程。 耗時？怎么辦？ P86 第三章 處理機調度與死鎖 ? 進程調度時機 ??? 正在執(zhí)行的進程執(zhí)行完畢。從就緒隊列中取出選中進程，然后進行上下文切換，分配處理機。 (2) 按某種算法選取進程 。 1) 決定接納多少個作業(yè)：多道程序度的確定應根據(jù)系統(tǒng)的規(guī)模和運行速度等情況做適當?shù)?折衷 2) 決定接納哪些作業(yè)：作業(yè)調度算法 第三章 處理機調度與死鎖 低級調度 調度的對象是進程 (或內核級線程 )。 ④ 完成狀態(tài) ：作業(yè)完成其全部運行，釋放其所占用的全部資源，準備退出系統(tǒng)。 ?作業(yè)的狀態(tài) 作業(yè)從輸入到完成要經(jīng)歷 提交，收容，執(zhí)行，完成 四個階段。 ① 編譯 ② 連結裝配 ③ 運行 (3) 作業(yè)流 。 處理機調度的層次 第三章 處理機調度與死鎖 處理機調度的層次 高級調度（只針對批處理系統(tǒng)） 1． 作業(yè)和作業(yè)步 (1) 作業(yè) (Job)=程序 +數(shù)據(jù) +作業(yè)說明書 系統(tǒng)根據(jù)說明書來對程序的運行進行控制。然后再將新創(chuàng)建的進程插入就緒隊列，準備執(zhí)行。因此，有時也把作業(yè)調度稱為接納調度 (Admission Scheduling)。在批處理系統(tǒng)中，以作業(yè)為基本單位從外存調入內存的。 若干個作業(yè)進入系統(tǒng)后 ， 被依次存放在外存上 ， 形成輸入的作業(yè)流；在操作系統(tǒng)的控制下 ， 逐個作業(yè)進行處理 ， 形成處理作業(yè)流 。 第三章 處理機調度與死鎖 JCB主要信息 第三章 處理機調度與死鎖 作業(yè)的狀態(tài)及其轉換 ① 提交狀態(tài) ：一個作業(yè)被提交給機房后或用戶通過終端設備向計算機中輸入其作業(yè)時所處的狀況。 第三章 處理機調度與死鎖 提交 后備 運行 就緒 等待 完成 作業(yè)調度 作業(yè)調度 作業(yè)錄入 作業(yè)的狀態(tài)及轉換 第三章 處理機調度與死鎖 3．作業(yè)調度算法的選擇 用戶：周轉時間少最好 系統(tǒng)：作業(yè)的平均周轉時間盡可能少，有利于提高 CPU 的利用率和系統(tǒng)的吞吐量。 進程調度是最基本的一種調度 ， 在多道批處理 、 分時和實時三種類型的 OS中 ， 都必須配置這級調度 。 (3) 把處理器分配給進程。 (3) 上下文切換機制 。 ??? 運行中的進程提出 I/O 請求。 ? 優(yōu)點：實現(xiàn)簡單，開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。 ? 原則： （ 1） 優(yōu)先權 （ 2） 短作業(yè) （ 進程 ） 優(yōu)先 （ 3）時間片 ?選擇性剝奪調度 第三章 處理機調度與死鎖 在上述三種調度中，進程調度的運行頻率最高，在分時系統(tǒng)中通常是 10～ 100 ms便進行一次進程調度，因此把它稱為短程調度。中級調度的運行頻率基本上 介于 上述兩種調度之間，因此把它稱為中程調度。圖 33示出了具有三級調度的調度隊列模型。 ? 平均周轉時間 ?帶權周轉時間：作業(yè)的周轉時間 T與系統(tǒng)為它提供服務的時間 Ts之比 ， 即 W = T/Ts ??????? ??niiTnT11第三章 處理機調度與死鎖 ?平均帶權周轉時間： ??????? ??niiTTnW1 s1 一般，總是 T或 W小的作業(yè)被選中，因為這樣資源利用率較高，用戶也滿意。 ?包括三部分時間：從鍵盤輸入的請求信息傳送到處理機的時間，處理機對請求信息進行處理的時間，以及將所形成的響應信息回送到終端顯示器的時間。 (4) 優(yōu)先權準則。 這是用于評價 批處理系統(tǒng)性能 的另一個重要指標 ， 因而是選擇批處理作業(yè)調度的重要準則 。 第三章 處理機調度與死鎖 (2) 處理機利用率好。但對于微型機和某些實時系統(tǒng)而言，準則(2)(3)并不重要。 ? 大多數(shù)系統(tǒng)都根據(jù)用戶的需要而采用兼顧某些目標的簡單調度算法 調 度 算 法 第三章 處理機調度