《操作系統原理》算法總結

一、進(jìn)程(作業(yè))調度算法

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

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

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

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

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

l         多級隊列調度算法

基本概念：

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

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

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

   響應比＝（等待時(shí)間＋運行時(shí)間）/運行時(shí)間

二、存儲器連續分配方式中分區分配算法

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

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

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

三、頁(yè)面置換算法

l         最佳置換算法（OPT) ：選擇以后永不使用或在最長(cháng)時(shí)間內不再被訪(fǎng)問(wèn)的內存頁(yè)面予以淘汰。

l         先進(jìn)先出置換算法（FIFO）：選擇最先進(jìn)入內存的頁(yè)面予以淘汰。

l         最近最久未使用算法（LRU）：選擇在最近一段時(shí)間內最久沒(méi)有使用過(guò)的頁(yè)，把它淘汰。

l         最少使用算法（LFU）：選擇到當前時(shí)間為止被訪(fǎng)問(wèn)次數最少的頁(yè)轉換。

四、磁盤(pán)調度

n         先來(lái)先服務(wù)（FCFS）：是按請求訪(fǎng)問(wèn)者的先后次序啟動(dòng)磁盤(pán)驅動(dòng)器，而不考慮它們要訪(fǎng)問(wèn)的物理位置

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

n         掃描算法（SCAN）或電梯調度算法：總是從磁臂當前位置開(kāi)始，沿磁臂的移動(dòng)方向去選擇離當前磁臂最近的那個(gè)柱面的訪(fǎng)問(wèn)者。如果沿磁臂的方向無(wú)請求訪(fǎng)問(wèn)時(shí)，就改變磁臂的移動(dòng)方向。在這種調度方法下磁臂的移動(dòng)類(lèi)似于電梯的調度，所以它也稱(chēng)為電梯調度算法。

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