C語言中文網
首頁 > 編程筆記 > 操作系統筆記 閱讀:863

優先級調度算法及其優缺點

SJF 算法是通用優先級調度算法的一個特例。每個進程都有一個優先級與其關聯,而具有最高優先級的進程會分配到 CPU。具有相同優先級的進程按 FCFS 順序調度。SJF 算法是一個簡單的優先級算法,其優先級(p)為下次(預測的)CPU 執行的倒數。CPU 執行越長,則優先級越小;反之亦然。

注意,我們按照高優先級和低優先級討論調度。優先級通常為固定區間的數字,如 0~7 或 0~4095。不過,對于 0 表示最高還是最低的優先級沒有定論。有的系統用低數字表示低優先級,其他用低數字表示高優先級。這種差異可以導致混淆。本節用低數字表示高優先級。

舉個例子,假設有如下一組進程,它們在時間 0 按順序 P1,P2,…,P5 到達,其 CPU 執行時間以 ms 計:

進程 執行時間 優先級
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2

采用優先級調度,會按如下 Gantt 圖來調度這些進程:


 
平均等待時間為 8.2ms。

優先級的定義可以分為內部的或外部的:
優先調度可以是搶占的或非搶占的。當一個進程到達就緒隊列時,比較它的優先級與當前運行進程的優先級。如果新到達進程的優先級高于當前運行進程的優先級,那么搶占優先級調度算法就會搶占 CPU。非搶占優先級調度算法只是將新的進程加到就緒隊列的頭部。

優先級調度算法的一個主要問題是無窮阻塞饑餓就緒運行但是等待 CPU 的進程可以認為是阻塞的。優先級調度算法可讓某個低優先級進程無窮等待 CPU。對于一個超載的計算機系統,穩定的更高優先級的進程流可以阻止低優先級的進程獲得 CPU。一般來說,有兩種情況會發生。要么進程最終會運行(在系統最后為輕負荷時),要么系統最終崩潰并失去所有未完成的低優先級進程。(據說,在 1973 年關閉 MIT 的 IBM 7094 時,發現有一個低優先級進程早在 1967 年就已提交,但是一直未能運行。)

低優先級進程的無窮等待問題的解決方案之一是老化老化逐漸增加在系統中等待很長時間的進程的優先級。例如,如果優先級為從 127(低)到 0(高),那么可以每 15 分鐘遞減等待進程的優先級的值。最終初始優先級值為 127 的進程會成為系統內最高的優先級,進而能夠執行。事實上,不會超過 32 小時,優先級為 127 的進程會老化為優先級為 0 的進程。

所有教程

優秀文章

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo