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

多級反饋隊列調度算法詳解

通常在使用多級隊列調度算法時,進程進入系統時被永久地分配到某個隊列。例如,如果前臺和后臺進程分別具有單獨隊列,那么進程并不從一個隊列移到另一個隊列,這是因為進程不會改變前臺或后臺的性質。這種設置的優點是調度開銷低,缺點是不夠靈活。

相反,多級反饋隊列調度算法允許進程在隊列之間遷移。這種想法是,根據不同 CPU 執行的特點來區分進程。如果進程使用過多的 CPU 時間,那么它會被移到更低的優先級隊列。這種方案將 I/O 密集型和交互進程放在更高優先級隊列上。 此外,在較低優先級隊列中等待過長的進程會被移到更高優先級隊列。這種形式的老化可阻止饑餓的發生。

多級反饋隊列
圖 1 多級反饋隊列

例如,一個多級反饋隊列的調度程序有三個隊列,從 0 到 2(圖 1)。調度程序首先執行隊列 0 內的所有進程。只有當隊列 0 為空時,它才能執行隊列 1 內的進程。類似地,只有隊列 0 和 1 都為空時,隊列 2 的進程才能執行。到達隊列 1 的進程會搶占隊列 2 的進程。同樣,到達隊列 0 的進程會搶占隊列 1 的進程。

每個進程在進入就緒隊列后,就被添加到隊列 0 內。隊列 0 內的每個進程都有 8ms 的時間片。如果一個進程不能在這一時間片內完成,那么它就被移到隊列 1 的尾部。如果隊列 0 為空,隊列 1 頭部的進程會得到一個 16ms 的時間片。如果它不能完成,那么將被搶占,并添加到隊列 2。只有當隊列 0 和 1 為空時,隊列 2 內的進程才可根據 FCFS 來運行。

這種調度算法將給那些 CPU 執行不超過 8ms 的進程最高優先級。這類進程可以很快得到 CPU,完成 CPU 執行,并且處理下個 I/O 執行。

所需超過 8ms 但不超過 24ms 的進程也會很快得以服務,但是它們的優先級要低一點。長進程會自動沉入隊列 2,隊列 0 和 1 不用的 CPU 周期按 FCFS 順序來服務。

通常,多級反饋隊列調度程序可由下列參數來定義:
  1. 隊列數量。
  2. 每個隊列的調度算法。
  3. 用以確定何時升級到更高優先級隊列的方法。
  4. 用以確定何時降級到更低優先級隊列的方法。
  5. 用以確定進程在需要服務時將會進入哪個隊列的方法。

多級反饋隊列調度程序的定義使其成為最通用的 CPU 調度算法。通過配置,它能適應所設計的特定系統。遺憾的是,由于需要一些方法來選擇參數以定義最佳的調度程序,所以它也是最復雜的算法。

所有教程

優秀文章

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

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

底部Logo