常用進程調度演算法

1. 五種進程調度演算法的總結;

1、時間片輪轉調度 演算法 （RR）：給每個進程固定的執行時間，根據進程到達的先後順序讓進程在單位時間片內執行，執行完成後便調度下一個進程執行，時間片輪轉調度不考慮進程等待時間和執行時間，屬於搶占式調度。優點是兼顧長短作業；缺點是平均等待時間較長，上下文切換較費時。適用於分時系統。
2、先來先服務調度演算法（FCFS）：根據進程到達的先後順序執行進程，不考慮等待時間和執行時間，會產生飢餓現象。屬於非搶占式調度，優點是公平，實現簡單；缺點是不利於短作業。
3、優先順序調度演算法（HPF）：在進程等待隊列中選擇優先順序最高的來執行。
4、多級反饋隊列調度演算法：將時間片輪轉與優先順序調度相結合，把進程按優先順序分成不同的隊列，先按優先順序調度，優先順序相同的，按時間片輪轉。優點是兼顧長短作業，有較好的響應時間，可行性強，適用於各種作業環境。
5、高響應比優先調度演算法：根據「響應比=（進程執行時間+進程等待時間）/ 進程執行時間」這個公式得到的響應比來進行調度。高響應比優先演算法在等待時間相同的情況下，作業執行的時間越短，響應比越高，滿足段任務優先，同時響應比會隨著等待時間增加而變大，優先順序會提高，能夠避免飢餓現象。優點是兼顧長短作業，缺點是計算響應比開銷大，適用於批處理系統。

2. 進程調度演算法

為了實現進程調度，在進程調度機制中，應具有如下三個基本部分：

「搶占」不是一種任意性行世碼為，必須遵守一定的原則。主要原則有：

基於時間片的輪轉（round robin，RR）調度演算法。該演算法採取了非常公平的處理機分配方式，卜冊即讓就緒隊列上的每一個矜持每次僅運行一個時間片。如果就緒隊列上有n個進程，則每個進程每次大約都可獲得1/n的處理機時間。

為了滿足系統中所有進程的緊迫性是不同的，在進程調度演算法中引入優先順序，而形成優先順序調度演算法。

該演算法將系統中的進程就緒隊列從一個拆分為若干個，將不同類型或性質的進程固定分配在不同的就緒隊列，不同的就緒隊列採用不同的調度演算法，一個就緒隊列中搜弊哪的進程可以設置不同的優先順序，不同的就緒隊列本身也可以設置不同的優先順序。

3. 進程調度的方式有哪兩種試列舉至少4種進程調度演算法。

進程調度的方式有非剝奪方式和剝奪方式。
非剝奪方式：
分派程序一旦把處理機分配給某進程後便讓它一直運行下去，直到進程完成或發生某事件而阻塞時，才把處理機分配給另一個進程。
剝奪方式：
當一個進程正在運行時，系統可以基於某種原則，剝奪已分配給它的處理機，將之分配給其它進程。剝奪原則有：優先權原則、短進程優先原則、時間片原則。
進程調度演算法：
1、先進先出演算法（FIFO）：
演算法總是把處理機分配給最先進入就緒隊列的進程，一個進程一旦分得處理機，便一直執行下去，直到該進程完成或阻塞時，才釋放處理機。
舉例：有三個進程P1、P2和P3先後進入就緒隊列，它們的執行期分別是21、6和3個單位時間，對於P1、P2、P3的周轉時間為21、27、30，平均周轉時間為26。可見，FIFO演算法服務質量不佳，容易引起作業用戶不滿，常作為一種輔助調度演算法。
2、最短CPU運行期優先調度演算法(SCBF--Shortest CPU Burst First)：
該演算法從就緒隊列中選出下一個「CPU執行期最短」的進程，為之分配處理機。
舉例：在就緒隊列中有四個進程P1、P2、P3和P4，它們的下一個執行進程調度期分別是16、12、4和3個單位時間，P1、P2、P3和P4的周轉時間分別為35、19、7、3，平均周轉時間為16。該演算法雖可獲得較好的調度性能，但難以准確地知道下一個CPU執行期，而只能根據每一個進程的執行歷史來預測。
3、時間片輪轉法：
前幾種演算法主要用於批處理系統中，不能作為分時系統中的主調度演算法，在分時系統中，都採用時間片輪轉法。簡單輪轉法：系統將所有就緒進程按FIFO規則排隊，按一定的時間間隔把處理機分配給隊列中的進程。這樣，就緒隊列中所有進程均可獲得一個時間片的處理機而運行。
4、多級反饋隊列：
多級隊列方法：將系統中所有進程分成若干類，每類為一級。多級反饋隊列方式是在系統中設置多個就緒隊列，並賦予各隊列以不同的優先權。

4. 進程常用的調度方式有哪三種

進程調度有以下兩種基本方式：
非剝奪方式
分派程序一旦把處理機分配給某進程後便讓它一直運行下去，直到進程完成或發生某事件而阻塞時，才把處理機分配給另一個進程。
剝奪方式
當一個進程正在運行時，系統可以基於某種原則，剝奪已分配給它的處理機，將之分配給其它進程。剝奪原則有：優先權原則、短進程、優先原則、時間片原則。
例如，有三個進程P1、P2、P3先後到達，它們分別需要20、4和2個單位時間運行完畢。
假如它們就按P1、P2、P3的順序執行，且不可剝奪，則三進程各自的周轉時間分別為20、24、
26個單位時間，平均周轉時間是23.33個時間單位。
假如用時間片原則的剝奪調度方式，可得到：
可見：P1、P2、P3的周轉時間分別為26、10、6個單位時間，平均周轉時間為14個單位時間。
衡量進程調度性能的指標有：周轉時間、響應時間、CPU-I/O執行期。

5. 進程調度演算法

演算法原理： 就是誰先來誰就先執行

演算法優點 ：易於理解且實現簡單，只需要一個隊列，公平
演算法缺點 ：有利於長進程，不利於短進程，有利於CPU 繁忙的進程，不利於I/O 繁忙的進程

演算法原理： 對預計執行時間短的進程優先執行。
演算法優點 ：相比FCFS 演算法，該演算法可改善平均周轉時間和平均帶權周轉時間，縮短進程的等待時間，提高系統的吞吐量。
演算法缺點： 對長進程不利，可能長時間得不到執行產生飢餓，不能判斷執行的優先順序。

演算法原理： 同時考慮每個作業的等待時間長短和估計需要的執行時間長短，從中選出響應比最高的作業投入執行。響應比R定義： R =(W+T)/T = 1+W/T
T為該作業估計需要的執行時間，W為作業在後備狀態隊列中的等待時間。執行之前系統計算每個作業的響應比，選擇其中R最大者執行。這種演算法是介於前面兩種之間的一種折中演算法。
演算法優點： 長作業也有機會投入運行，避免了飢餓。
演算法缺點： 每次調度前要計算響應比，增加系統開銷。

演算法原理： 設置一個時間片，每個進程輪流使用時間片，若一個時間片內進程還沒結束，也會被其他的進程搶占時間片而退出執行，進入等待隊列。
演算法優點： 簡單易行、平均響應時間短。
演算法缺點： 不利於處理緊急作業。時間片的大小的設置對系統性能的影響很大，因此時間片的大小應選擇恰當

演算法原理： 根據優先順序的來判斷執行哪個進程。可以分為靜態優先順序和動態優先順序，即優先順序可以根據情況改變。比如如果一個進程等了很久，我們就可以把他的優先順序適當的提高。

演算法優點 ：可以優先處理緊急事件，適用於實時操作系統。

演算法缺點 ：可能導致那些優先順序低的進程飢餓。

UNIX操作系統採取的便是這種調度演算法。
演算法原理 ：

實現先說明執行隊列優先順序Q1>Q2>Q3.......>Qn，分配的時間片Qn>Qn-1>...Q1.

進程在進入待調度的隊列等待時，首先進入優先順序最高的隊列Q1等待。若在Q1隊列裡面還沒執行完，則下放到Q2裡面，等Q1裡面的進程都執行完了之後再執行Q2。以此類推。
若在低優先順序的隊列中的進程在運行時，又有新到達的作業，那麼在運行完這個時間片後，CPU馬上分配給新到達的作業（搶占式）。
在多級反饋隊列調度演算法中，規定第一個隊列的時間片略大於多數人機交互所需之處理時間時，能夠較好的滿足各種類型用戶的需要。

6. 什麼是進程調度常用的進程調度演算法有哪些

無論是在批處理系統還是分時系統中，用戶進程數一般都多於處理機數、這將導致它們互相爭奪處理機。另外，系統進程也同樣需要使用處理機。這就要求進程調度程序按一定的策略，動態地把處理機分配給處於就緒隊列中的某一個進程，以使之執行。就是調度。
有先來先服務調度演算法、優先數調度演算法、時間片輪轉演算法、分級調度演算法 、最短作業時間優先（搶占式和非搶占式）、最高響應比調度演算法，樂透調度等。

7. 第三章 進程調度的幾種方式

進程調度概念：操作系統必須為多個，嗎進程可能有競爭的請求分配計算機資源。對處理器而言，可分配的資源是在處理器上的執行時間，分配途徑是調度。調度功能必須設計成可以滿足多個目標，包括公平、任何進程都不會餓死、有效地使用處理器時間和低開銷。此外，調度功能可能需要為某些進程的啟動或結束考慮不同的優先順序和實時最後期限。

這些年以來，調度已經成為深入研究的焦點，並且已經實現了許多不同的演算法。如今，調度研究的重點是開發多處理系統，特別是用於多線程的。

下面簡介幾種調度演算法。

一、先來先服務和短作業(進程)優先調度演算法

1．先來先服務調度演算法

先來先服務(FCFS)調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度，也可用於進程調度。當在作業調度中採用該演算法時，每次調度都是從後備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然後放入就緒隊列。在進程調度中採用FCFS演算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞後才放棄處理機。

2．短作業(進程)優先調度演算法

短作業(進程)優先調度演算法SJ(P)F，是指對短作業或短進程優先調度的演算法。它們可以分別用於作業調度和進程調度。短作業優先(SJF)的調度演算法是從後備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。而短進程優先(SPF)調度演算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執行並一直執行到完成，或發生某事件而被阻塞放棄處理機時再重新調度。

二、高優先權優先調度演算法

1．優先權調度演算法的類型

為了照顧緊迫型作業，使之在進入系統後便獲得優先處理，引入了最高優先權優先(FPF)調度演算法。此演算法常被用於批處理系統中，作為作業調度演算法，也作為多種操作系統中的進程調度演算法，還可用於實時系統中。當把該演算法用於作業調度時，系統將從後備隊列中選擇若干個優先權最高的作業裝入內存。當用於進程調度時，該演算法是把處理機分配給就緒隊列中優先權最高的進程，這時，又可進一步把該演算法分成如下兩種。

1) 非搶占式優先權演算法

在這種方式下，系統一旦把處理機分配給就緒隊列中優先權最高的進程後，該進程便一直執行下去，直至完成；或因發生某事件使該進程放棄處理機時，系統方可再將處理機重新分配給另一優先權最高的進程。這種調度演算法主要用於批處理系統中；也可用於某些對實時性要求不嚴的實時系統中。

2) 搶占式優先權調度演算法

在這種方式下，系統同樣是把處理機分配給優先權最高的進程，使之執行。但在其執行期間，只要又出現了另一個其優先權更高的進程，進程調度程序就立即停止當前進程(原優先權最高的進程)的執行，重新將處理機分配給新到的優先權最高的進程。因此，在採用這種調度演算法時，是每當系統中出現一個新的就緒進程i 時，就將其優先權Pi與正在執行的進程j 的優先權Pj進行比較。如果Pi≤Pj，原進程Pj便繼續執行；但如果是Pi>Pj，則立即停止Pj的執行，做進程切換，使i 進程投入執行。顯然，這種搶占式的優先權調度演算法能更好地滿足緊迫作業的要求，故而常用於要求比較嚴格的實時系統中，以及對性能要求較高的批處理和分時系統中。

2．高響應比優先調度演算法

在批處理系統中，短作業優先演算法是一種比較好的演算法，其主要的不足之處是長作業的運行得不到保證。如果我們能為每個作業引入前面所述的動態優先權，並使作業的優先順序隨著等待時間的增加而以速率a 提高，則長作業在等待一定的時間後，必然有機會分配到處理機。該優先權的變化規律可描述為：

由於等待時間與服務時間之和就是系統對該作業的響應時間，故該優先權又相當於響應比RP。據此，又可表示為：

由上式可以看出：

(1) 如果作業的等待時間相同，則要求服務的時間愈短，其優先權愈高，因而該演算法有利於短作業。

(2) 當要求服務的時間相同時，作業的優先權決定於其等待時間，等待時間愈長，其優先權愈高，因而它實現的是先來先服務。

(3) 對於長作業，作業的優先順序可以隨等待時間的增加而提高，當其等待時間足夠長時，其優先順序便可升到很高，從而也可獲得處理機。簡言之，該演算法既照顧了短作業，又考慮了作業到達的先後次序，不會使長作業長期得不到服務。因此，該演算法實現了一種較好的折衷。當然，在利用該演算法時，每要進行調度之前，都須先做響應比的計算，這會增加系統開銷。

三、基於時間片的輪轉調度演算法

1．時間片輪轉法

1) 基本原理

在早期的時間片輪轉法中，系統將所有的就緒進程按先來先服務的原則排成一個隊列，每次調度時，把CPU 分配給隊首進程，並令其執行一個時間片。時間片的大小從幾ms 到幾百ms。當執行的時間片用完時，由一個計時器發出時鍾中斷請求，調度程序便據此信號來停止該進程的執行，並將它送往就緒隊列的末尾；然後，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證就緒隊列中的所有進程在一給定的時間內均能獲得一時間片的處理機執行時間。換言之，系統能在給定的時間內響應所有用戶的請求。

2．多級反饋隊列調度演算法

前面介紹的各種用作進程調度的演算法都有一定的局限性。如短進程優先的調度演算法，僅照顧了短進程而忽略了長進程，而且如果並未指明進程的長度，則短進程優先和基於進程長度的搶占式調度演算法都將無法使用。而多級反饋隊列調度演算法則不必事先知道各種進程所需的執行時間，而且還可以滿足各種類型進程的需要，因而它是目前被公認的一種較好的進程調度演算法。在採用多級反饋隊列調度演算法的系統中，調度演算法的實施過程如下所述。

(1) 應設置多個就緒隊列，並為各個隊列賦予不同的優先順序。第一個隊列的優先順序最高，第二個隊列次之，其餘各隊列的優先權逐個降低。該演算法賦予各個隊列中進程執行時間片的大小也各不相同，在優先權愈高的隊列中，為每個進程所規定的執行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。

(2) 當一個新進程進入內存後，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可准備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣地按FCFS原則等待調度執行；如果它在第二隊列中運行一個時間片後仍未完成，再依次將它放入第三隊列，……，如此下去，當一個長作業(進程)從第一隊列依次降到第n隊列後，在第n 隊列便採取按時間片輪轉的方式運行。

(3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1～(i-1)隊列均空時，才會調度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務時，又有新進程進入優先權較高的隊列(第1～(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優先權進程。

8. 幾種進程調度演算法分析

前兩天做操作系統作業的時候學習了一下幾種進程調度演算法，在思考和討論後，有了一些自己的想法，現在就寫出來，跟大家討論下。 ，或者說只有有限的CPU資源，當系統中有多個進程處於就緒狀態，要競爭CPU資源時，操作系統就要負責完成如何分配資源的任務。在操作系統中，由調度程序來完成這一選擇分配的工作，調度程序所使用的演算法即是調度演算法。調度演算法需要考慮的指標主要有盡量保證CPU資源分配的公平性；按照一定策略強制執行演算法調度；平衡整個計算機系統，盡量保持各個部分都處於忙碌狀態。而根據系統各自不同的特點和要求，調度演算法又有一些側重點和目標不同，因此，演算法按照系統差異主要分為三大類： 批處理系統中的調度演算法， 代表調度演算法有：先來先服務、最短作業優先、最短剩餘時間優先。 互動式系統中的調度演算法， 代表調度演算法有：輪轉調度、優先順序調度、多級隊列、最短進程優先、保證調度、彩票調度、公平分享調度。 實時系統中的調度演算法 ，代表調度演算法有：速率單調調度、最早最終時限優先調度。 下面就上述提到的調度演算法中挑出幾個進行重點分析：保證調度保證調度是指利用演算法向用戶做出明確的性能保證，然後盡力按照此保證實現CPU的資源分配。利用這種演算法，就是定一個進程佔用CPU的時間的標准，然後按照這個標准去比較實際佔用CPU的時間，調度進程每次使離此標准最遠的進程得到資源，不斷滿足離所保證的標准最遠的進程，從而平衡資源分配滿足這個標準的要求。 保證調度演算法的優點是：能很好的保證進程公平的CPU份額，當系統的特點是：進程的優先順序沒有太大懸殊，所制定的保證標准差異不大，各個進程對CPU的要求較為接近時，比如說系統要求n個進程中的每個進程都只佔用1/n的CPU資源，利用保證調度可以很容易的實現穩定的CPU分配要求。但缺點是，這種情況太過理想，當系統的各個進程對CPU要求的緊急程度不同，所制定的保證較為復雜的時候，這個演算法實現起來比較困難。 彩票調度彩票調度這種演算法的大意是指向進程提供各種系統資源如CPU資源的彩票，當系統需要做出調度決策時，隨機抽出一張彩票，由此彩票的擁有者獲得資源。在彩票調度系統中，如果有一個新的進程出現並得到一些彩票，那麼在下一次的抽獎中，該進程會有同它持有彩票數量成正比例的機會贏得獎勵。進程持有的彩票數量越多，則被抽中的可能性就越大。調度程序可以通過控制進程的彩票持有數量來進行調度。 彩票調度有很多優點：首先，它很靈活，系統增加分給某個進程的彩票數量，就會大大增加它佔用資源的可能性，可以說，彩票調度的反應是迅速的，而快速響應需求正是互動式系統的一個重要要求。其次，彩票調度演算法中，進程可以交換彩票，這個特點可以更好的保證系統的平衡性，使其各個部分都盡可能的處於忙碌狀態。而且利用彩票調度還可以解決許多別的演算法很難解決的問題，例如可以根據特定的需要大致成比例的劃分CPU的使用。 速率單調調度 速率單調調度演算法是一種可適用於可搶占的周期性進程的經典靜態實時調度演算法。當實時系統中的進程滿足：每個周期性進程必須在其周期內完成，且進程之間沒有相互依賴的關系，每個進程在一次突發中需要相同的CPU時間量，非周期的進程都沒有最終時限四個條件時，並且為了建模方便，我們假設進程搶占即刻發生沒有系統開銷，可以考慮利用速率單調演算法。 速率單調調度演算法是將進程的速率（按照進程周期所算出的每秒響應的次數）賦為優先順序，則保證了優先順序與進程速率成線性關系，這即是我們所說的速率單調。調度程序每次運行優先順序最高的，只要優先順序較高的程序需要運行，則立即搶占優先順序低的進程，而優先順序較低的進程必須等所有優先順序高於它的進程結束後才能運行。 速率單調調度演算法可以保證系統中最關鍵的任務總是得到調度，但是缺點是其作為一種靜態演算法，靈活性不夠好，當進程數變多，系統調度變得復雜時，可能不能較好的保證進程在周期內運行。 最早最終時限優先調度 最早最終時限優先調度演算法是一個動態演算法，不要求進程是周期性的，只要一個進程需要CPU時間，它就宣布它的到來時間和最終時限。調度程序維持一個可運行的進程列表，按最終時限排序，每次調度一個最終時限最早的進程得到CPU 。當新進程就緒時，系統檢查其最終時限是否在當前運行的進程結束之前，如果是，則搶占當前進程。 由於是動態演算法，最早最終優先調度的優點就是靈活，當進程數不超過負載時，資源分配更優，但也同樣由於它的動態屬性，進程的優先順序都是在不斷變化中的，所以也沒有哪個進程是一定可以保證滿足調度的，當進程數超過負載時，資源分配合理度會急速下降，所以不太穩定。

9. 進程調度的演算法

演算法總是把處理機分配給最先進入就緒隊列的進程，一個進程一旦分得處理機，便一直執行下去，直到該進程完成或阻塞時，才釋放處理機。
例如，有三個進程P1、P2和P3先後進入就緒隊列，它們的執行期分別是21、6和3個單位時間，
執行情況如下圖：
對於P1、P2、P3的周轉時間為21、27、30，平均周轉時間為26。
可見，FIFO演算法服務質量不佳，容易引起作業用戶不滿，常作為一種輔助調度演算法。 最短CPU運行期優先調度演算法(SCBF--Shortest CPU Burst First)
該演算法從就緒隊列中選出下一個「CPU執行期最短」的進程，為之分配處理機。
例如，在就緒隊列中有四個進程P1、P2、P3和P4，它們的下一個執行期分別是16、12、4和3個單位時間，執行情況如下圖：
P1、P2、P3和P4的周轉時間分別為35、19、7、3，平均周轉時間為16。
該演算法雖可獲得較好的調度性能，但難以准確地知道下一個CPU執行期，而只能根據每一個進程的執行歷史來預測。 前幾種演算法主要用於批處理系統中，不能作為分時系統中的主調度演算法，在分時系統中，都採用時間片輪轉法。
簡單輪轉法：系統將所有就緒進程按FIFO規則排隊，按一定的時間間隔把處理機分配給隊列中的進程。這樣，就緒隊列中所有進程均可獲得一個時間片的處理機而運行。
多級隊列方法：將系統中所有進程分成若干類，每類為一級。 多級反饋隊列方式是在系統中設置多個就緒隊列，並賦予各隊列以不同的優先權。

10. 進程/作業/頁面調度演算法

進程已獲得除CPU之外的所有必須資源,只等待操作系統利用CPU調度演算法將CPU分配給該進程以便執行。

進程等待某一特定事件的出現。如[I/O操作,在該過程中,進程依舊位於內存內,且佔有CPU資源。

（1）靜態優先數法：
一開始創建的時候就確定他的優先數，並在運行時保持不變。確定優先數時可以讓外設的進程優先，或者操作時間長的優先....

（2）動態優先數法：
克服無法修改優先數的問題。CPU佔用時間過長優先數下降，進程等待時間過長，優先數提高。

時間片太短切換開銷太大不劃算，太長又變成了FCFS。

引入多個就緒隊列，在時間片輪轉基礎上改進

最高優先順序隊列運行一個時間片，次高兩個，低優先順序四個。當該進程用完所分配時間片仍未執行完時，需要調入下一級隊列，下一級隊列只有在上一級隊列為空時才有機會執行。如果進程執行時有新進程進入上級優先順序渣燃返的隊列，則會中斷該進程並放入原隊列的隊尾然後執行新進程。

非搶占式的先來先服務（First Come First Severd, FCFS）演算法了。

顧名思義，先來後到，每次從就緒隊列選擇最先進入隊列的進程，然後一直運行，直到進程退出或被阻塞，才會繼續從隊列中選擇第一個進程接著運行。

這似乎很公平，但是當一個長作業先運行了，那麼後面的短作業等待的時間就會很長，不利於短作業。

最短作業優先（Shortest Job First, SJF）調度演算法同樣也是顧名思義，它會優先選擇運行時間最短的進程來運行，這有助於提高系統的吞吐量。

這顯然對長作業不利，很容易造成一種極端現象。

高響應比優先 （Highest Response Ratio Next, HRRN）調度演算法主要是權衡了短作業和長作業。

每次進行進程調度時，先計算「響應比優先順序」，然後把「響應比優先順序」最高的進程投入運行，「響應比優先順序」的計算公式：

最古老、最簡單、最公平且使用最廣的演算法就是時間片輪轉（Round Robin, RR）調度演算法。

時間片的長度就是一個很關鍵的點：

如果時間片設得太短會導致過多的進程上下文切換，降低了 CPU 效率；如果設得太長又可能引起對短作業進程的響應時間變長。

靜態優先順序：創建進程時候，就已經確定了優先順序了，然後整個運行時間優先順序都不會變化；

動態優先順序：根據進程的動態變化調整優先順序，比如如果進程運行時間增加，則降低其優先順序，如果進程等待時間（就緒隊列的等待時間）增加，則升高其優先順序，也就是隨著時間的推移增加等待進程的優先順序。

（1）非搶占式：當就緒隊列中出現優先順序高的進程，運行完當前進程，再選擇優先順序高的進程。
（2）搶占式：當就緒隊列中出現優先順序高的進程，當前進程掛起，調度優先順序高的進程運行。

但是依然有缺點，可能會導致低優先順序的進程永遠不會運行。

設置了多個隊列，賦予每個隊列不同的優先順序，每個隊列優先順序從高到低，同時優先順序越高時間片越短；

新的進程會被放入到第一級隊列的末尾，按先來先服務的原則排隊等待被調度，如果在第一級隊列規定的時間片沒運行完成，則將其轉入到第二級隊列的末尾，段談以此類推，直至完成；

當較高優先順序的隊列為空，才調度較低優先順序的隊列中的進程運行。如果進程運行時，有新進程進入較高優先順序的隊列，則停止當前運行的進程並將其移入到原隊列末尾，接著讓較高優先順序的進程運行。

對於短作業可能可以在第一級隊列很快被處理完。對於長作如飢業，如果在第一級隊列處理不完，可以移入下次隊列等待被執行，雖然等待的時間變長了，但是運行時間也會更長了，所以該演算法很好的兼顧了長短作業，同時有較好的響應時間。

每次選擇淘汰的頁面將是以後永不使用，或者在最長時間內不再被訪問的頁面，這樣可以保證最低的缺頁率。

最佳置換演算法可以保證最低的缺頁率，但是實際上，只有進程執行的過程中才能知道接下來會訪問到的是哪個頁面。操作系統無法提前預判頁面的訪問序列。因此，最佳置換演算法是無法實現的。

演算法思想：每次選擇淘汰的頁面是最早進入內存的頁面。

該演算法很簡單，每次淘汰最在內存中待時間最久的各個，下面分別給出系統為進程分為配三個內存塊和四個內存塊的執行情況圖。訪問序列為3,2,1,0,3,2,4,3,2,1,0,4

演算法思想：每次淘汰的頁面是最近最久未使用的頁面。

實現方法：賦予每個頁面對應的頁表項中，用訪問欄位記錄該頁面自上次被訪問以來所經歷的時間t。當需要淘汰一個頁面時，選擇現有頁面中t最大的頁面，即最近最久未使用。

最佳置換演算法性能最好，但無法實現。先進先出置換演算法實現簡單，但是演算法性能差。最近最久未使用置換演算法性能好，是最接近OPT演算法性能的，但是實現起來需要專門的硬體支持，演算法開銷大。時鍾置換演算法是一種性能和開銷均平衡的演算法。又稱CLOCK演算法，或最近未用演算法（NRU，Not Recently Used）

簡單CLOCK演算法演算法思想：為每個頁面設置一個訪問位，再將內存中的頁面都通過鏈接指針鏈接成一個循環隊列。當某個頁被訪問時，其訪問位置1.當需要淘汰一個頁面時，只需檢查頁的訪問位。如果是0，就選擇該頁換出；如果是1，暫不換出，將訪問位改為0，繼續檢查下一個頁面，若第一輪掃描中所有的頁面都是1，則將這些頁面的訪問位一次置為0後，再進行第二輪掃描（第二輪掃描中一定會有訪問位為0的頁面，因此簡單的CLOCK演算法選擇一個淘汰頁面最多會經過兩輪掃描）。

除了考慮一個頁面最近有沒有被訪問過之外，操作系統還需要考慮頁面有沒有被修改過。

改進型時鍾置換演算法的演算法思想：在其他在條件相同時，應該優先淘汰沒有被修改過的頁面，從而來避免I/O操作。