操作系統(tǒng)調(diào)度算法

　　操作系統(tǒng)中的調(diào)度算法使我們必須掌握的算法。下面由學習啦小編為大家整理了操作系統(tǒng)調(diào)度算法的相關(guān)知識，希望對大家有幫助!

　　操作系統(tǒng)調(diào)度算法一、常見的批處理作業(yè)調(diào)度算法

　　1.先來先服務調(diào)度算法(FCFS):就是按照各個作業(yè)進入系統(tǒng)的自然次序來調(diào)度作業(yè)。這種調(diào)度算法的優(yōu)點是實現(xiàn)簡單，公平。其缺點是沒有考慮到系統(tǒng)中各種資源的綜合使用情況，往往使短作業(yè)的用戶不滿意，因為短作業(yè)等待處理的時間可能比實際運行時間長得多。

　　2.短作業(yè)優(yōu)先調(diào)度算法(SPF): 就是優(yōu)先調(diào)度并處理短作業(yè)，所謂短是指作業(yè)的運行時間短。而在作業(yè)未投入運行時，并不能知道它實際的運行時間的長短，因此需要用戶在提交作業(yè)時同時提交作業(yè)運行時間的估計值。

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

　　4. 基于優(yōu)先數(shù)調(diào)度算法(HPF)：每一個作業(yè)規(guī)定一個表示該作業(yè)優(yōu)先級別的整數(shù)，當需要將新的作業(yè)由輸入井調(diào)入內(nèi)存處理時，優(yōu)先選擇優(yōu)先數(shù)最高的作業(yè)。

　　5.均衡調(diào)度算法，即多級隊列調(diào)度算法

　　基本概念：

　　作業(yè)周轉(zhuǎn)時間(Ti)=完成時間(Tei)-提交時間(Tsi)

　　作業(yè)平均周轉(zhuǎn)時間(T)=周轉(zhuǎn)時間/作業(yè)個數(shù)

　　作業(yè)帶權(quán)周轉(zhuǎn)時間(Wi)=周轉(zhuǎn)時間/運行時間

　　響應比=(等待時間+運行時間)/運行時間

　　操作系統(tǒng)調(diào)度算法二、進程調(diào)度算法

　　1.先進先出算法(FIFO)：按照進程進入就緒隊列的先后次序來選擇。即每當進入進程調(diào)度，總是把就緒隊列的隊首進程投入運行。

　　2. 時間片輪轉(zhuǎn)算法(RR)：分時系統(tǒng)的一種調(diào)度算法。 輪轉(zhuǎn)的基本思想是，將CPU的處理時間劃分成一個個的時間片，就緒隊列中的進程輪流運行一個時間片。當時間片結(jié)束時，就強迫進程讓出CPU，該進程進入就 緒隊列，等待下一次調(diào)度，同時，進程調(diào)度又去選擇就緒隊列中的一個進程，分配給它一個時間片，以投入運行。

　　3. 最高優(yōu)先級算法(HPF)：進程調(diào)度每次將處理機分配給具有最高優(yōu)先級的就緒進程。最高優(yōu)先級算法可與不同的CPU方式結(jié)合形成可搶占式最高優(yōu)先級算法和不可搶占式最高優(yōu)先級算法。

　　4. 多級隊列反饋法：幾種調(diào)度算法的結(jié)合形式多級隊列方式。

　　操作系統(tǒng)調(diào)度算法三、空閑分區(qū)分配算法

　　1. 首先適應算法：當接到內(nèi)存申請時，查找分區(qū)說明表，找到第一個滿足申請長度的空閑區(qū)，將其分割并分配。此算法簡單，可以快速做出分配決定。

　　2. 最佳適應算法：當接到內(nèi)存申請時，查找分區(qū)說明表，找到第一個能滿足申請長度的最小空閑區(qū)，將其進行分割并分配。此算法最節(jié)約空間，因為它盡量不分割到大的空閑區(qū)，其缺點是可能會形成很多很小的空閑分區(qū)，稱為“碎片”。

　　3. 最壞適應算法：當接到內(nèi)存申請時，查找分區(qū)說明表，找到能滿足申請要求的最大的空閑區(qū)。該算法的優(yōu)點是避免形成碎片，而缺點是分割了大的空閑區(qū)后，在遇到較大的程序申請內(nèi)存時，無法滿足的可能性較大。

　　操作系統(tǒng)調(diào)度算法四、虛擬頁式存儲管理中的頁面置換算法

　　1.理想頁面置換算法(OPT)：這是一種理想的算法，在實際中不可能實現(xiàn)。該算法的思想是：發(fā)生缺頁時，選擇以后永不使用或在最長時間內(nèi)不再被訪問的內(nèi)存頁面予以淘汰。

　　2.先進先出頁面置換算法(FIFO)：選擇最先進入內(nèi)存的頁面予以淘汰。

　　3. 最近最久未使用算法(LRU)：選擇在最近一段時間內(nèi)最久沒有使用過的頁，把它淘汰。

　　4.最少使用算法(LFU)：選擇到當前時間為止被訪問次數(shù)最少的頁轉(zhuǎn)換。

　　操作系統(tǒng)調(diào)度算法五、磁盤調(diào)度

　　1.先來先服務(FCFS)：是按請求訪問者的先后次序啟動磁盤驅(qū)動器，而不考慮它們要訪問的物理位置

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

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

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