《作業系統原理》演算法總結

● 先來先服務排程演算法（fcfs）：每次排程是從就緒佇列中，選擇乙個最先進入就緒佇列的程序，把處理器分配給該程序，使之得到執行。該程序一旦占有了處理器，它就一直執行下去，直到該程序完成或因發生事件而阻塞，才退出處理器。

特點：利於長程序，而不利於短程序。

● 短程序（作業）優先排程演算法(spf)：它是從就緒佇列中選擇乙個估計執行時間最短的程序，將處理器分配給該程序，使之占有處理器並執行，直到該程序完成或因發生事件而阻塞，然後退出處理器，再重新排程。

● 時間片輪轉排程演算法：系統將所有的就緒程序按進入就緒佇列的先後次序排列。每次排程時把cpu分配給隊首程序，讓其執行乙個時間片，當時間片用完，由計時器發出時鐘中斷，排程程式則暫停該程序的執行，使其退出處理器，並將它送到就緒佇列的末尾，等待下一輪排程執行。

● 優先數排程演算法：它是從就緒佇列中選擇乙個優先權最高的程序，讓其獲得處理器並執行。

● 響應比高者優先排程演算法：它是從就緒佇列中選擇乙個響應比最高的程序，讓其獲得處理器執行，直到該程序完成或因等待事件而退出處理器為止。特點：

既照顧了短程序，又考慮了程序到達的先後次序，也不會使長程序長期得不到服務，因此是乙個比較全面考慮的演算法，但每次進行排程時，都需要對各個程序計算響應比。所以系統開銷很大，比較複雜。

● 多級佇列排程演算法

作業周轉時間（ti）＝完成時間(tei)－提交時間(tsi)

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

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

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

● pv操作

三、死鎖中的銀行家演算法

銀行家演算法的處理步驟為：

（1）列出某一時刻資源分配表，格式如表2-4所示。

（2）拿可用資源量與每乙個程序所需資源量進行比較，可用資源量不少於所需資源量時，把資源分配給該程序。新的可用資源量為原有可用資源量加上該程序已分配資源量。

（3）重複（2），直到所有程序都執行完，即可判斷能否獲得乙個安全資源分配序列。

首次適應分配演算法（ff）：對空閒分割槽表記錄的要求是按位址遞增的順序排列的，每次分配時，總是從第1條記錄開始順序查詢空閒分割槽表，找到第乙個能滿足作業長度要求的空閒區，分割這個空閒區，一部分分配給作業，另一部分仍為空閒區。

迴圈首次適應演算法：每次分配均從上次分配的位置之後開始查詢。

最佳適應分配演算法(bf)：是按作業要求從所有的空閒分割槽中挑選乙個能滿足作業要求的最小空閒區，這樣可保證不去分割乙個更大的區域，使裝入大作業時比較容易得到滿足。為實現這種演算法，把空閒區按容量遞增次序登記在空閒區表中，分配時，順序查詢。

最壞適應演算法：為實現這種演算法，把空閒區按容量遞減次序登記在空閒區表中。

● 最佳置換演算法（opt) ：選擇以後永不使用或在最長時間內不再被訪問的記憶體頁面予以淘汰。

● 先進先出置換演算法（fifo）：選擇最先進入記憶體的頁面予以淘汰。

● 最近最久未使用演算法（lru）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。

● 最少使用演算法（lfu）：選擇到當前時間為止被訪問次數最少的頁轉換。

先來先服務（fcfs）：是按請求訪問者的先後次序啟動磁碟驅動器，而不考慮它們要訪問的物理位置

最短尋道時間優先（sstf）：讓離當前磁軌最近的請求訪問者啟動磁碟驅動器，即是讓查詢時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務排程演算法中磁臂移動過大的問題

掃瞄演算法（scan）或電梯排程演算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。

在這種排程方法下磁臂的移動類似於電梯的排程，所以它也稱為電梯排程演算法。

迴圈掃瞄演算法（cscan）：迴圈掃瞄排程演算法是在掃瞄演算法的基礎上改進的。磁臂改為單項移動，由外向裡。

當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。