一、處理機排程的層次

概念

• 按什麼原則分配CPU：排程演演算法。
• 何時分配CPU：排程時機。
• 如何分配CPU：排程過程。
• 週轉時間：完成時間-進入時間。（注意：從進入系統到執行完成包括在後備佇列中等待排程、在就緒佇列中等待程序排程、執行以及等待I/O操作完成四部分時間，作業進入是指作業準備好被排程的狀態）。
• 平均週轉時間：週轉時間/執行時間。
• 資源利用率：CPU有效工作時間/（CPU有效工作時間+CPU空閒等待時間）。

處理機排程的層次

  1、高階排程（作業排程）：排程物件是作業，主要功能：根據某種演演算法，決定將外存上處於後備佇列中的哪幾個作業調入記憶體，為它們建立程序、分配必要的資源，並將其放在就緒佇列中。
  2、低階排程（程序排程）：排程物件是程序，主要功能：根據某種演演算法，決定就緒佇列中哪個程序應獲得處理機，並由分派程式將處理機分配給被選中的程序。（即分配哪個程序進入執行狀態）
  3、中級排程（記憶體排程）：其主要目的是提高記憶體利用率和系統吞吐量。當一個程序暫時不能執行時，它被調至外存等待，此時該程序為掛起狀態。當這個程序具備繼續執行條件又稍有空閒時，由中級排程來決定，把外存上的那些已經具備執行條件的就緒程序重新調入記憶體，並修改其狀態為就緒狀態，掛在就緒佇列上等待。

二、作業與作業排程

  作業：不僅包含通常的程式和資料，還應配有一份作業說明書，系統根據該說明書對程式的執行進行控制。在批次處理系統中，是以作業為基本單位從外存調入記憶體的。

2.1 先來先服務（FCFS）排程演演算法

  就緒佇列中最先進入佇列的程序，先為之分配處理機執行，直至其結束或阻塞，將處理機分配給其他程序。有利於長作業，CPU繁忙型作業。可用於作業排程，也可用於程序排程。

2.2 短作業優先（SJF）排程演演算法

  作業越短，優先順序越高（注意：若一個程序已進入，而其他程序未進入，儘管未進入的程序作業更短，但仍先執行已進入的作業）。可用於作業排程，也可用於程序排程。

2.3 優先順序排程演演算法（PSA）

  可用於作業排程，也可用於程序排程。作業排程：選擇-建立程序-放入就緒佇列。程序排程：選擇-分配處理機。

2.4 高響應比優先排程演演算法（HRRN）

  主要用於作業排程。每次計算所有符合被排程條件（已經進入）的作業的響應比（響應比=週轉時間/處理時間），響應比高的先處理，然後再繼續計算下一步中所有符合被排程條件的作業的響應比，直到所有作業被排程完畢。

2.5 時間片輪轉排程演演算法

  主要用於程序排程，時間片大小需選擇合適：太大退化為FCFS，太小切換頻繁，用於執行時間太少。其舉例具體實現過程如下：

2.6 多級佇列排程演演算法

  主要用於程序排程。將就緒佇列分成若干子佇列，每個程序屬於一個就緒佇列，每個就緒佇列採用一種排程演演算法。

2.7 多級反饋佇列排程演演算法

  排程機制：

• 設定多個就緒佇列，併為每一個就緒佇列賦予不同的優先順序，第一個佇列優先順序最高，依次降低。該演演算法為不同佇列中的程序所賦予的執行時間片的大小也各不相同，在優先順序越高的佇列中，時間片越小。
• 每個佇列都採用FCFS演演算法。新程序進入記憶體後，先將其放在第一個佇列末尾，按FCFS演演算法等待排程，輪到該程序執行時，若它能在時間片內完成，便可撤離系統，否則將其轉入第二個佇列的末尾，等待排程，若在第二個佇列中執行一個時間片後仍未完成，轉入第三個佇列，依次類推。當程序最後被降到第n佇列後，在第n佇列中便採取RR方式執行。
• 按佇列優先順序排程。僅當前面佇列都空閒時，當前佇列才能夠執行。

三、死鎖

3.1 死鎖

3.1.1 死鎖定義

  一組程序中，每個程序都無限等待被該組程序中另一程序所佔有的資源，因而永遠無法得到該資源，這種現象稱為程序死鎖，這一組程序就稱為死鎖程序。
  結論：

• 參與死鎖的程序最少是兩個。
• 參與死鎖的程序至少兩個已經佔有資源。
• 參與死鎖的所有程序都在等待資源。
• 參與死鎖的程序是當前系統中所有程序的子集。

3.1.2 產生死鎖的必要條件

• 互斥條件：涉及的資源是非共用的。
• 不可搶佔條件（不可剝奪條件）：不能強行剝奪程序擁有的資源。
• 請求和保持條件：程序在等待一新資源時繼續佔有已分配的資源。
• 迴圈等待條件：存在一種程序的迴圈鏈，鏈中每一個程序已獲得的資源同時被鏈中下一個程序請求。

3.1.3 處理死鎖的方法

• 預防死鎖：通過設定某些限制條件，去破壞死鎖四個必要條件中的一個或多個，來防止死鎖。
• 避免死鎖：在資源動態分配過程中，用某種方法去防止系統進入不安全狀態，從而避免死鎖的發生。
• 檢測死鎖
• 解除死鎖：與檢測死鎖配套。

3.2 預防死鎖

  互斥條件是非共用裝置所必須的，不能改變

• 破壞不可剝奪條件：一個已擁有資源的程序，若它再提出新資源要求而不能立即得到滿足時，必須釋放已經擁有的所有資源。以後需要時再申請。
• 破壞請求和保持條件：系統要求所有程序一次性地申請在整個執行過程中所需的全部資源。若系統有足夠資源則全部分配。
• 破壞迴圈等待條件：系統中的所有資源都有一個確定的唯一號碼，所有分配請求必須以序號上升的次序進行。

3.3 避免死鎖

  死鎖避免定義：在系統執行過程中，對程序發出的每一個系統能夠滿足的資源申請進行動態檢查，並根據檢查結果決定是否分配資源，若分配後系統可能發生死鎖，則不予分配，否則予以分配。
  安全狀態：如果系統能按某種順序（如P 4，P 1，·,Pn，稱為安全序列）為每個程序分配其所需的資源，直至所有程序都能執行完成。稱系統處於安全狀態。若不存在這樣一個安全序列稱系統處於不安全狀態。

銀行家演演算法

1、資料結構

• 可利用資源向量Available。含有m個元素的陣列，每一個元素代表一類可利用的資源數目。
• 最大需求矩陣MAX。n×m矩陣，定義系統中n個程序中的每一個程序對m類資源的最大需求。
• 分配矩陣Allocation。系統中每一類資源已分配給每一程序的資源數。
• 需求矩陣Need。每一個程序尚需要的各類資源數。
• Need[i,j]=Max[i,j]-Allocation[i,j]。

2、銀行家演演算法

• 若Request i[j]<=Need[i,j]，繼續檢查；否則認為出錯，請求大於需求。
• 若Request i[j]<=Available[i,j]，繼續檢查，否則，等待，資源不夠。
• 試探分配給程序Pi:Available[i,j]-=Request i[j];Allocation[i,j]+=Request i[j];Need[i,j]-=Request i[j]。
• 系統執行安全性演演算法，若系統新狀態是安全的，則分配完成，若系統新狀態是不安全的，則恢復原狀態，程序等待。

3、安全性演演算法

• 設定兩個向量：可利用資源work，work=Available；標記程序是夠結束Finish=false（還未釋放）
• 從程序集合中選擇滿足條件的程序：1、Finish[i]=false；2、Need[i,j]<=work[j]；若不存在，轉（4）。
• 執行Work[j]+=Allocation[i,j]；Finish[j]=true；go to step2。
• 若所有程序Finish[i]=true都滿足，表示系統處於安全狀態，否則，處於不安全狀態。

4、銀行家演演算法例子
  假定系統中有五個程序{P0,P1,P2,P3,P4}和三類資源{A,B,C}，各種資源的數量分別為10、5、7，在T0時刻的資源分配情況如圖所示。

  T0時刻的安全性：利用安全性演演算法對To時刻的資源分配情況進行分析（如圖所示）可知，在To時刻存在著一個安全序列{P1,P3,P4,P2,P0}，故系統是安全的。

  將剩下的資源執行銀行家演演算法，看是否處於安全狀態。

3.4 死鎖的檢測與解除

  死鎖檢測：允許死鎖發生，作業系統不斷監視系統進展情況，判斷死鎖是否發生。一旦死鎖發生則採取專門的措施，解除死鎖並以最小的代價恢復作業系統執行。
  死鎖解除：重要的是以最小的代價恢復系統的執行。方法如下：1、重新啟動；2、撤消程序；3、剝奪資源；4、程序回退。
  用有向圖描述程序的死鎖。 系統由若干類資源構成，一類資源稱為一個資源類；每個資源類中包含若干個同種資源，稱為資源範例。二元組G=（V，E），V：結點集，分為P，R兩部分，程序P={p1,p2,…,pn}，資源R={r1,r2,…,rm}，E：邊的集合，其元素為有序二元組請求資源(pi,rj)或分配資源(rj,pi)。表示法：方框表示資源，圓圈表示程序，方框中的黑圓點表示資源範例。例如：

  死鎖定理：如果資源分配圖中沒有環路，則系統中沒有死鎖，如果圖中存在環路則系統中可能存在死鎖。如果每個資源類中只包含一個資源範例，則環路是死鎖存在的充分必要條件。
  資源分配圖化簡：

• 找一個非孤立程序結點且只有分配邊，去掉分配邊，將其變為孤立結點
• 再把相應的資源分配給一個等待該資源的程序，即將某程序的申請邊變為分配邊
• 重複以上步驟，若所有程序成為孤立結點，稱該圖是可完全簡化的，否則稱該圖是不可完全簡化的。

死鎖狀態的充分條件是：當且僅當資源分配圖是不可完全簡化的。