進程調度算法

基本調度算法：

1.???先來先服務FCFS：既可以作為作業調度算法也可以作為進程調度算法；按作業或者進程到達的先后順序依次調度；因此對于長作業比較有利。

算法優點：易于理解且實現簡單，只需要一個隊列(FIFO)，且相當公平?
算法缺點：比較有利于長進程，而不利于短進程，有利于CPU 繁忙的進程，而不利于I/O 繁忙的進程。

2.???短作業優先SPF：作業調度算法，算法從就緒隊列中選擇估計時間最短的作業進行處理，直到得出結果或者無法繼續執行；

算法優點：相比FCFS 算法，該算法可改善平均周轉時間和平均帶權周轉時間，縮短進程的等待時間，提高系統的吞吐量。?
算法缺點：對長進程非常不利，可能長時間得不到執行，且未能依據進程的緊迫程度來劃分執行的優先級，以及難以準確估計進程的執行時間，從而影響調度性能。

3.? 高優先權優先HRRF：既可以作為作業調度也可以作為進程調度算法；調度作業時，從就緒隊列中選擇優先級最高的作業進行處理；由于涉及到了優先級，因此可以分為搶占式和非搶占式；而且優先級的確定也可以分為靜態優先級（事先根據進程類型，進程對資源的需求，用戶要求等方面確定一個固定值）；動態優先級（隨進程的推進或者等待時間而增加或者減少）。

4.???最高響應比優先HRRN：FCFS可能造成短作業用戶不滿，SPF可能使得長作業用戶不滿，于是提出HRN，選擇響應比最高的作業運行。（考慮等待和處理時間因素）響應比=1+作業等待時間/作業處理時間。

算法優點：由于長作業也有機會投入運行，在同一時間內處理的作業數顯然要少于SJF法，從而采用HRRN方式時其吞吐量將小于采用SJF 法時的吞吐量。?
算法缺點：由于每次調度前要計算響應比，系統開銷也要相應增加。

?

5.??時間片輪轉（RR，Round-Robin）：按到達的先后對進程放入隊列中，然后給隊首進程分配CPU時間片，時間片用完之后計時器發出中斷，暫停當前進程并將其放到隊列尾部，循環。

算法優點：時間片輪轉調度算法的特點是簡單易行、平均響應時間短。?
算法缺點：不利于處理緊急作業。額外的上下文切換。在時間片輪轉算法中，時間片的大小對系統性能的影響很大，因此時間片的大小應選擇恰當?

怎樣確定時間片的大小：

時間片大小的確定?
1.系統對響應時間的要求 （響應快，則小）
2.就緒隊列中進程的數目?
3.系統的處理能力

?

6.???多級反饋隊列：目前公認較好的調度算法；設置多個就緒隊列并為每個隊列設置不同的優先級，第一個隊列優先級最高，其余依次遞減。優先級越高的隊列分配的時間片越短，進程到達之后按FCFS放入第一個隊列，如果調度執行后沒有完成，那么放到第二個隊列尾部等待調度（說明需要更長的CPU時間完成，也就是優先級越高執行時間應該越短，最應該放在第一隊列！如果初次沒有完成，則轉入下一級，等待分配等多的時間片），如果第二次調度仍然沒有完成，放入第三隊列尾部。只有當前一個隊列為空的時候才會去調度下一個隊列的進程。

　在多級反饋隊列調度算法中，如果規定第一個隊列的時間片略大于多數人機交互所需之處理時間時，便能夠較好的滿足各種類型用戶的需要。

---

進程調度算法

不同環境的調度算法目標不同，因此需要針對不同環境來討論調度算法。

1. 批處理系統

批處理系統沒有太多的用戶操作，在該系統中，調度算法目標是保證吞吐量和周轉時間（從提交到終止的時間）。

1.1 先來先服務 first-come first-serverd（FCFS）

按照請求的順序進行調度。

有利于長作業，但不利于短作業，因為短作業必須一直等待前面的長作業執行完畢才能執行，而長作業又需要執行很長時間，造成了短作業等待時間過長。

1.2 短作業優先 shortest job first（SJF）

按估計運行時間最短的順序進行調度。

長作業有可能會餓死，處于一直等待短作業執行完畢的狀態。因為如果一直有短作業到來，那么長作業永遠得不到調度。

1.3 最短剩余時間優先 shortest remaining time next（SRTN）

按估計剩余時間最短的順序進行調度。

2. 交互式系統

交互式系統有大量的用戶交互操作，在該系統中調度算法的目標是快速地進行響應。

2.1 時間片輪轉

將所有就緒進程按 FCFS 的原則排成一個隊列，每次調度時，把 CPU 時間分配給隊首進程，該進程可以執行一個時間片。當時間片用完時，由計時器發出時鐘中斷，調度程序便停止該進程的執行，并將它送往就緒隊列的末尾，同時繼續把 CPU 時間分配給隊首的進程。

時間片輪轉算法的效率和時間片的大小有很大關系：

• 因為進程切換都要保存進程的信息并且載入新進程的信息，如果時間片太小，會導致進程切換得太頻繁，在進程切換上就會花過多時間。
• 而如果時間片過長，那么實時性就不能得到保證。

?

2.2 優先級調度

為每個進程分配一個優先級，按優先級進行調度。

為了防止低優先級的進程永遠等不到調度，可以隨著時間的推移增加等待進程的優先級。

2.3 多級反饋隊列

一個進程需要執行 100 個時間片，如果采用時間片輪轉調度算法，那么需要交換 100 次。

多級隊列是為這種需要連續執行多個時間片的進程考慮，它設置了多個隊列，每個隊列時間片大小都不同，例如 1,2,4,8,..。進程在第一個隊列沒執行完，就會被移到下一個隊列。這種方式下，之前的進程只需要交換 7 次。

每個隊列優先權也不同，最上面的優先權最高。因此只有上一個隊列沒有進程在排隊，才能調度當前隊列上的進程。

可以將這種調度算法看成是時間片輪轉調度算法和優先級調度算法的結合。

?

3. 實時系統

實時系統要求一個請求在一個確定時間內得到響應。

分為硬實時和軟實時，前者必須滿足絕對的截止時間，后者可以容忍一定的超時。

總結

以上是生活随笔為你收集整理的操作系统：进程调度算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。