作業系統排程演算法

　　作業系統中的排程演算法使我們必須掌握的演算法。下面由小編為大家整理了的相關知識，希望對大家有幫助!

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

　　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***：選擇到當前時間為止被訪問次數最少的頁轉換。

　　五、磁碟排程