OS排程算法常用摘要

一、常見的批處理作業排程

1.先來先服務排程算法（FCFS）:就是依照各個作業進入系統的自然次序來排程作業。這樣的排程算法的長處是實作簡單，公平。

其缺點是沒有考慮到系統中各種資源的綜合使用情況，往往使短作業的使用者不惬意，由于短作業等待處理的時間可能比實際執行時間長得多。

2.短作業優先排程算法(SPF): 就是優先排程并處理短作業。所謂短是指作業的執行時間短。

而在作業未投入執行時。并不能知道它實際的執行時間的長短。是以須要使用者在送出作業時同一時候送出作業執行時間的預計值。

3.最高響應比優先算法(HRN)：FCFS可能造成短作業使用者不滿，SPF可能使得長作業使用者不滿。于是提出HRN，選擇響應比最高的作業執行。響應比=1+作業等待時間/作業處理時間。

4. 基于優先數排程算法(HPF)：每個作業規定一個表示該作業優先級别的整數，當須要将新的作業由輸入井調入記憶體處理時，優先選擇優先數最高的作業。

5.均衡排程算法，即多級隊列排程算法

基本概念：

   作業周轉時間（Ti）＝完畢時間(Tei)－送出時間(Tsi)

   作業平均周轉時間(T)＝周轉時間/作業個數

   作業帶權周轉時間（Wi）＝周轉時間/執行時間

   響應比＝（等待時間＋執行時間）/執行時間

二、程序排程算法

1.先進先出算法(FIFO)：依照程序進入就緒隊列的先後次序來選擇。

即每當進入程序排程，總是把就緒隊列的隊首程序投入執行。

2. 時間片輪轉算法(RR)：分時系統的一種排程算法。

輪轉的基本思想是。将CPU的處理時間劃分成一個個的時間片，就緒隊列中的程序輪流執行一個時間片。

當時間片結束時，就強迫程序讓出CPU，該程序進入就緒隊列，等待下一次排程。同一時候。程序排程又去選擇就緒隊列中的一個程序。配置設定給它一個時間片，以投入執行。

3. 最高優先級算法(HPF)：程序排程每次将處理機配置設定給具有最高優先級的就緒程序。最高優先級算法可與不同的CPU方式結合形成可搶占式最高優先級算法和不可搶占式最高優先級算法。

4. 多級隊列回報法：幾種排程算法的結合形式多級隊列方式。

三、空暇分區配置設定算法

1. 首先适應算法：當接到記憶體申請時。查找分區說明表，找到第一個滿足申請長度的空暇區，将其切割并配置設定。此算法簡單，能夠高速做出配置設定決定。

2. 最佳适應算法：當接到記憶體申請時，查找分區說明表，找到第一個能滿足申請長度的最小空暇區，将其進行切割并配置設定。此算法最節約空間，由于它盡量不切割到大的空暇區。其缺點是可能會形成非常多非常小的空暇分區，稱為“碎片”。

3. 最壞适應算法：當接到記憶體申請時，查找分區說明表。找到能滿足申請要求的最大的空暇區。該算法的長處是避免形成碎片，而缺點是切割了大的空暇區後，在遇到較大的程式申請記憶體時，無法滿足的可能性較大。

四、虛拟頁式存儲管理中的頁面置換算法

1.理想頁面置換算法(OPT)：這是一種理想的算法。在實際中不可能實作。該算法的思想是：發生缺頁時，選擇以後永不使用或在最長時間内不再被訪問的記憶體頁面予以淘汰。

2.先進先出頁面置換算法(FIFO)：選擇最先進入記憶體的頁面予以淘汰。

3. 近期最久未使用算法（LRU）：選擇在近期一段時間内最久沒有使用過的頁，把它淘汰。

4.最少使用算法（LFU）：選擇到目前時間為止被訪問次數最少的頁轉換。

五、磁盤排程

1.先來先服務（FCFS）：是按請求訪問者的先後次序啟動磁盤驅動器。而不考慮它們要訪問的實體位置

2.最短尋道時間優先（SSTF）：讓離目前磁道近期的請求訪問者啟動磁盤驅動器，即是讓查找時間最短的那個作業先運作，而不考慮請求訪問者到來的先後次序。這樣就克服了先來先服務排程算法中磁臂移動過大的問題

3.掃描算法（SCAN）或電梯排程算法：總是從磁臂目前位置開始。沿磁臂的移動方向去選擇離目前磁臂近期的那個柱面的訪問者。

假設沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這樣的排程方法下磁臂的移動類似于電梯的排程。是以它也稱為電梯排程算法。

4.循環掃描算法（CSCAN）：循環掃描排程算法是在掃描算法的基礎上改進的。磁臂改為單項移動，由外向裡。目前位置開始沿磁臂的移動方向去選擇離目前磁臂近期的哪個柱面的訪問者。假設沿磁臂的方當用于通路沒有請求，然後再傳回到最外，的氣缸工作存取請求的最小數目。