《操作系統(tǒng)原理》算法總結

一,、進程(作業(yè))調度算法

l         先來先服務調度算法（FCFS）：每次調度是從就緒隊列中,，選擇一個最先進入就緒隊列的進程，把處理器分配給該進程,，使之得到執(zhí)行,。該進程一旦占有了處理器，它就一直運行下去,，直到該進程完成或因發(fā)生事件而阻塞,，才退出處理器。特點：利于長進程,，而不利于短進程,。

l         短進程（作業(yè)）優(yōu)先調度算法(SPF)：它是從就緒隊列中選擇一個估計運行時間最短的進程，將處理器分配給該進程,，使之占有處理器并執(zhí)行,，直到該進程完成或因發(fā)生事件而阻塞，然后退出處理器,，再重新調度,。

l         時間片輪轉調度算法 ：系統(tǒng)將所有的就緒進程按進入就緒隊列的先后次序排列。每次調度時把CPU分配給隊首進程,，讓其執(zhí)行一個時間片,，當時間片用完，由計時器發(fā)出時鐘中斷,，調度程序則暫停該進程的執(zhí)行,，使其退出處理器，并將它送到就緒隊列的末尾,，等待下一輪調度執(zhí)行,。

l         優(yōu)先數(shù)調度算法 ：它是從就緒隊列中選擇一個優(yōu)先權最高的進程，讓其獲得處理器并執(zhí)行,。

l         響應比高者優(yōu)先調度算法：它是從就緒隊列中選擇一個響應比最高的進程,，讓其獲得處理器執(zhí)行，直到該進程完成或因等待事件而退出處理器為止,。特點：既照顧了短進程,，又考慮了進程到達的先后次序，也不會使長進程長期得不到服務,，因此是一個比較全面考慮的算法,，但每次進行調度時,，都需要對各個進程計算響應比。所以系統(tǒng)開銷很大,，比較復雜,。

l         多級隊列調度算法

基本概念：

   作業(yè)周轉時間（Ti）＝完成時間(Tei)－提交時間(Tsi)

   作業(yè)平均周轉時間(T)＝周轉時間/作業(yè)個數(shù)

   作業(yè)帶權周轉時間（Wi）＝周轉時間/運行時間

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

二、存儲器連續(xù)分配方式中分區(qū)分配算法

n         首次適應分配算法（FF）：對空閑分區(qū)表記錄的要求是按地址遞增的順序排列的,，每次分配時,，總是從第1條記錄開始順序查找空閑分區(qū)表，找到第一個能滿足作業(yè)長度要求的空閑區(qū),，分割這個空閑區(qū),，一部分分配給作業(yè)，另一部分仍為空閑區(qū),。

n         循環(huán)首次適應算法：每次分配均從上次分配的位置之后開始查找,。

n         最佳適應分配算法(BF)：是按作業(yè)要求從所有的空閑分區(qū)中挑選一個能滿足作業(yè)要求的最小空閑區(qū)，這樣可保證不去分割一個更大的區(qū)域,，使裝入大作業(yè)時比較容易得到滿足,。為實現(xiàn)這種算法，把空閑區(qū)按長度遞增次序登記在空閑區(qū)表中,，分配時,，順序查找。

三,、頁面置換算法

l         最佳置換算法（OPT) ：選擇以后永不使用或在最長時間內不再被訪問的內存頁面予以淘汰,。

l         先進先出置換算法（FIFO）：選擇最先進入內存的頁面予以淘汰。

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

l         最少使用算法（LFU）：選擇到當前時間為止被訪問次數(shù)最少的頁轉換。

四,、磁盤調度

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

n         最短尋道時間優(yōu)先（SSTF）：讓離當前磁道最近的請求訪問者啟動磁盤驅動器，即是讓查找時間最短的那個作業(yè)先執(zhí)行,，而不考慮請求訪問者到來的先后次序，這樣就克服了先來先服務調度算法中磁臂移動過大的問題

n         掃描算法（SCAN）或電梯調度算法：總是從磁臂當前位置開始,，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者,。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向,。在這種調度方法下磁臂的移動類似于電梯的調度,，所以它也稱為電梯調度算法。

n         循環(huán)掃描算法（CSCAN）：循環(huán)掃描調度算法是在掃描算法的基礎上改進的,。磁臂改為單項移動,，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時,，再回到最外,，訪問柱面號最小的作業(yè)請求。