计算机操作系统 第三章：处理机调度与死锁（2）
目錄
3.3? 進 程 調 度
3.3.1? 進程調度的任務、機制和方式??
3.3.2? 輪轉調度算法
?3.3.3? 優先級調度算法
3.3.4? 多隊列調度算法
3.3.5? 多級反饋隊列(multileved feedback queue)調度算法?
3.3.6? 基于公平原則的調度算法??
3.4? 實 時 調 度
3.4.1? 實現實時調度的基本條件
3.4.2? 實時調度算法的分類???
?3.4.3? 最早截止時間優先EDF(Earliest Deadline First)算法?
?3.4.4? 最低松弛度優先LLF(Least Laxity First)算法
?3.4.5? 優先級倒置(priority inversion problem)??
3.3? 進 程 調 度
進程調度是OS中必不可少的一種調度。因此在三種類型的OS中，都無一例外地配置了進程調度。此外它也是對系統性能影響最大的一種處理機調度，相應的，有關進程調度的算法也較多。
3.3.1? 進程調度的任務、機制和方式??
1. 進程調度的任務
進程調度的任務主要有三：
(1) 保存處理機的現場信息。
(2) 按某種算法選取進程。
(3) 把處理器分配給進程。 ?
2. 進程調度機制
為了實現進程調度，在進程調度機制中，應具有如下三個基本部分，如圖3-1所示。
(1) 排隊器。
(2) 分派器。
(3) 上下文切換器。
?3. 進程調度方式
1) 非搶占方式(Nonpreemptive Mode)
在采用這種調度方式時，一旦把處理機分配給某進程后，就一直讓它運行下去，決不會因為時鐘中斷或任何其它原因去搶占當前正在運行進程的處理機，直至該進程完成，或發生某事件而被阻塞時，才把處理機分配給其它進程。
2) 搶占方式(Preemptive Mode)
這種調度方式允許調度程序根據某種原則，去暫停某個正在執行的進程，將已分配給該進程的處理機重新分配給另一進程。在現代OS中廣泛采用搶占方式，這是因為：對于批處理機系統，可以防止一個長進程長時間地占用處理機，以確保處理機能為所有進程提供更為公平的服務。在分時系統中，只有采用搶占方式才有可能實現人—機交互。在實時系統中，搶占方式能滿足實時任務的需求。但搶占方式比較復雜，所需付出的系統開銷也較大。
3.3.2? 輪轉調度算法
1. 輪轉法的基本原理
在輪轉(RR)法中，系統將所有的就緒進程按FCFS策略排成一個就緒隊列。系統可設置每隔一定時間(如30?ms)便產生一次中斷，去激活進程調度程序進行調度，把CPU分配給隊首進程，并令其執行一個時間片。當它運行完畢后，又把處理機分配給就緒隊列中新的隊首進程，也讓它執行一個時間片。這樣，就可以保證就緒隊列中的所有進程在確定的時間段內，都能獲得一個時間片的處理機時間。
2. 進程切換時機
在RR調度算法中，應在何時進行進程的切換，可分為兩種情況：① 若一個時間片尚未用完，正在運行的進程便已經完成，就立即激活調度程序，將它從就緒隊列中刪除，再調度就緒隊列中隊首的進程運行，并啟動一個新的時間片。② 在一個時間片用完時，計時器中斷處理程序被激活。如果進程尚未運行完畢，調度程序將把它送往就緒隊列的末尾。
3. 時間片大小的確定
在輪轉算法中，時間片的大小對系統性能有很大的
影響。
圖3-2示出了時間片大小對響應時間的影響，其中圖(a)是時間片略大于典型交互的時間，而圖(b)是時間片小于典型交互的時間。圖3-3示出了時間片分別為q?=?1和q?=?4時對平均周轉時間的影響。
?
?3.3.3? 優先級調度算法
1. 優先級調度算法的類型
優先級進程調度算法，是把處理機分配給就緒隊列中優先級最高的進程。這時，又可進一步把該算法分成如下兩種。
(1) 非搶占式優先級調度算法。
(2) 搶占式優先級調度算法。
2. 優先級的類型
1) 靜態優先級
靜態優先級是在創建進程時確定的，在進程的整個運行期間保持不變。優先級是利用某一范圍內的一個整數來表示的，例如0～255中的某一整數，又把該整數稱為優先數。確定進程優先級大小的依據有如下三個：
(1) 進程類型。
(2) 進程對資源的需求。
(3) 用戶要求。
2) 動態優先級
動態優先級是指在創建進程之初，先賦予其一個優先級，然后其值隨進程的推進或等待時間的增加而改變，以便獲得更好的調度性能。
3.3.4? 多隊列調度算法
如前所述的各種調度算法，尤其在應用于進程調度時，由于系統中僅設置一個進程的就緒隊列，即低級調度算法是固定的、單一的，無法滿足系統中不同用戶對進程調度策略的不同要求，在多處理機系統中，這種單一調度策略實現機制的缺點更顯突出，由此，多級隊列調度算法能夠在一定程度上彌補這一缺點
3.3.5? 多級反饋隊列(multileved feedback queue)調度算法?
1. 調度機制
多級反饋隊列調度算法的調度機制可描述如下：
(1) 設置多個就緒隊列。
圖3-4是多級反饋隊列算法的示意圖。
?(2) 每個隊列都采用FCFS算法。當新進程進入內存后，首先將它放入第一隊列的末尾，按FCFS原則等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可撤離系統。否則，即它在一個時間片結束時尚未完成，調度程序將其轉入第二隊列的末尾等待調度；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，……，依此類推。當進程最后被降到第n隊列后，在第n隊列中便采取按RR方式運行。
(3) 按隊列優先級調度。調度程序首先調度最高優先級隊列中的諸進程運行，僅當第一隊列空閑時才調度第二隊列中的進程運行；換言之，僅當第1～(i-1)所有隊列均空時，才會調度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務時又有新進程進入任一優先級較高的隊列，此時須立即把正在運行的進程放回到第i隊列的末尾，而把處理機分配給新到的高優先級進程。
2. 調度算法的性能
在多級反饋隊列調度算法中，如果規定第一個隊列的時間片略大于多數人機交互所需之處理時間時，便能較好地滿足各種類型用戶的需要。
(1) 終端型用戶。
(2) 短批處理作業用戶。
(3) 長批處理作業用戶。
3.3.6? 基于公平原則的調度算法??
1. 保證調度算法
保證調度算法是另外一種類型的調度算法，它向用戶所做出的保證并不是優先運行，而是明確的性能保證，該算法可以做到調度的公平性。一種比較容易實現的性能保證是處理機分配的公平性。如果在系統中有n個相同類型的進程同時運行，為公平起見，須保證每個進程都獲得相同的處理機時間1/n。
在實施公平調度算法時系統中必須具有這樣一些功能：
(1) 跟蹤計算每個進程自創建以來已經執行的處理時間。
(2) 計算每個進程應獲得的處理機時間，即自創建以來的時間除以n。
(3) 計算進程獲得處理機時間的比率，即進程實際執行的處理時間和應獲得的處理機時間之比。
(4) 比較各進程獲得處理機時間的比率。如進程A的比率最低，為0.5，而進程B的比率為0.8，進程C的比率為1.2等。
(5) 調度程序應選擇比率最小的進程將處理機分配給它，并讓該進程一直運行，直到超過最接近它的進程比率為止。
2. 公平分享調度算法
分配給每個進程相同的處理機時間，顯然，這對諸進程而言，是體現了一定程度的公平，但如果各個用戶所擁有的進程數不同，就會發生對用戶的不公平問題。
3.4? 實 時 調 度
在實時系統中，可能存在著兩類不同性質的實時任務，即HRT任務和SRT任務，它們都聯系著一個截止時間。為保證系統能正常工作，實時調度必須能滿足實時任務對截止時間的要求。為此，實現實時調度應具備一定的條件。
3.4.1? 實現實時調度的基本條件
1. 提供必要的信息
為了實現實時調度，系統應向調度程序提供有關任務的信息：
(1) 就緒時間，是指某任務成為就緒狀態的起始時間，在周期任務的情況下，它是事先預知的一串時間序列。
(2) 開始截止時間和完成截止時間，對于典型的實時應用，只須知道開始截止時間，或者完成截止時間。
(3) 處理時間，一個任務從開始執行，直至完成時所需的時間。
(4) 資源要求，任務執行時所需的一組資源。
(5) 優先級，如果某任務的開始截止時間錯過，勢必引起故障，則應為該任務賦予“絕對”優先級；如果其開始截止時間的錯過，對任務的繼續運行無重大影響，則可為其賦予“相對”優先級，供調度程序參考。
2. 系統處理能力強
在實時系統中，若處理機的處理能力不夠強，則有可能因處理機忙不過，而致使某些實時任務不能得到及時處理，從而導致發生難以預料的后果。假定系統中有m個周期性的硬實時任務HRT，它們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足下面的限制條件系統才是可調度的：
?提高系統處理能力的途徑有二：一是采用單處理機系統，但須增強其處理能力，以顯著地減少對每一個任務的處理時間；二是采用多處理機系統。假定系統中的處理機數為N，則應將上述的限制條件改為：
?3. 采用搶占式調度機制
在含有HRT任務的實時系統中，廣泛采用搶占機制。這樣便可滿足HRT任務對截止時間的要求。但這種調度機制比較復雜。
4. 具有快速切換機制
為保證硬實時任務能及時運行，在系統中還應具有快速切換機制，使之能進行任務的快速切換。該機制應具有如下兩方面的能力：
(1) 對中斷的快速響應能力。對緊迫的外部事件請求中斷能及時響應，要求系統具有快速硬件中斷機構，還應使禁止中斷的時間間隔盡量短，以免耽誤時機(其它緊迫任務)。
(2) 快速的任務分派能力。為了提高分派程序進行任務切換時的速度，應使系統中的每個運行功能單位適當的小，以減少任務切換的時間開銷。
3.4.2? 實時調度算法的分類???
??
可以按不同方式對實時調度算法加以分類：① 根據實時任務性質，可將實時調度的算法分為硬實時調度算法和軟實時調度算法；② 按調度方式，則可分為非搶占調度算法和搶占調度算法。
?1. 非搶占式調度算法
(1) 非搶占式輪轉調度算法。
(2) 非搶占式優先調度算法。
2. 搶占式調度算法
可根據搶占發生時間的不同而進一步分成以下兩種調度算法：
(1) 基于時鐘中斷的搶占式優先級調度算法。
(2) 立即搶占(Immediate Preemption)的優先級調度算法?！ ?br /> 圖3-5中的(a)、(b)、(c)、(d)分別示出了四種情況的調度時間。
?3.4.3? 最早截止時間優先EDF(Earliest Deadline First)算法?
1. 非搶占式調度方式用于非周期實時任務
圖3-6示出了將該算法用于非搶占調度方式之例。
?2. 搶占式調度方式用于周期實時任務
圖3-7示出了將該算法用于搶占調度方式之例。在該例中有兩個周期任務，任務A和任務B的周期時間分別為20 ms和50 ms，每個周期的處理時間分別為10?ms和25?ms。
?3.4.4? 最低松弛度優先LLF(Least Laxity First)算法
該算法在確定任務的優先級時，根據的是任務的緊急(或松弛)程度。任務緊急程度愈高，賦予該任務的優先級就愈高，以使之優先執行。
該算法主要用于可搶占調度方式中。假如在一個實時系統中有兩個周期性實時任務A和B，任務A要求每20?ms執行一次，執行時間為10?ms，任務B要求每50?ms執行一次，執行時間為25?ms。由此可知，任務A和B每次必須完成的時間分別為：A1、A2、A3、…和B1、B2、B3、…，見圖3-8。
?
?3.4.5? 優先級倒置(priority inversion problem)??
1. 優先級倒置的形成
當前OS廣泛采用優先級調度算法和搶占方式，然而在系統中存在著影響進程運行的資源而可能產生“優先級倒置”的現象，即高優先級進程(或線程)被低優先級進程(或線程)延遲或阻塞。我們通過一個例子來說明該問題。
假如P3最先執行，在執行了P(mutex)操作后，進入到臨界區CS-3。在時刻a，P2就緒，因為它比P3的優先級高，P2搶占了P3的處理機而運行，如圖3-10所示。
?2. 優先級倒置的解決方法
一種簡單的解決方法是規定：假如進程P3在進入臨界區后P3所占用的處理機就不允許被搶占。
??????? 一個比較實用的方法是建立在動態優先級繼承基礎上的。當高優先級進程P1要進入臨界區，去使用臨界資源R，如果已有一個低優先級進程P3正在使用該資源，此時一方面P1被阻塞，另一方面由P3繼承P1的優先級，并一直保持到P3退出臨界區。
圖3-11示出了采用動態優先級繼承方法后，P1、P2、P3三個進程的運行情況。
?
總結
以上是生活随笔為你收集整理的计算机操作系统 第三章：处理机调度与死锁（2）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 批量修改文件名.bat
- 下一篇： 【转换输出流小练习 】现有一字符串：”我