進程的調度演算法

⑴ 進程調度的方式有哪兩種試列舉至少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、多級反饋隊列：
多級隊列方法：將系統中所有進程分成若干類，每類為一級。多級反饋隊列方式是在系統中設置多個就緒隊列，並賦予各隊列以不同的優先權。

⑵ 操作系統處理機典型調度演算法

1.先來先服務演算法
作業調度、進程調度
先來的先分配處理機
優點：演算法簡單，對長作業有利，有利於CPU繁忙型作業（計算型）
缺點：效率低，不利於短作業，不利於IO繁忙型作業
不會導致飢餓
非搶占型的演算法

2.短作業優先演算法
進程調度
優先選擇預計運行時間最短的進程
優點：平均等待時間、平均周轉時間短
缺點：對長作業不利，造成飢餓現象，沒有考慮作業的緊迫性，用戶可能縮短作業預估時間，使得無法做到短作業優先
產生「飢餓」現象。如果一直得不到服務，則稱為「餓死」
SJF和SPF（短進程優先（SPF）演算法）是非搶占式的演算法。但是也有搶占式的版本——最短剩餘時間優先算雹激拍法

3.優先順序調度演算法
作業調度、進程調度

分類：
剝奪型：立即停止當前運行進程，將處理機分配給更高優先順序進程
非剝奪型：等待當前進程運行完成，然後將處理機分配給更高優先順序進程

優先順序分配：
靜態優先順序：進程創建後無法對優先順序進行修改
動態優先順序：可以根據進程運行狀態，對進程優先順序進行動態調整

優先順序設置原則：
系統進程>用戶進程
交互性進程>非交互性進程
I/O進程>計算型進程（CPU繁忙型）

產生「飢餓」現象
有搶占式的，也有非搶占式的

4.高響應比調度演算法
響應比=（等待時間+要求服務時間）/要求服務時間=1+等待時間/要求服務時間
等待時間相同情況下，要求服務時間越短響應比越大，有利於短作業進程
要求服務時間相同，作業響應比由其等待時間決定，等待時間越長響應比越高，實現先來先服務
對於長作業，作業的響應比可以隨等待時間的增加而提高，等待時間足夠長時，其響應比可以升到很高，從而獲得處理機
不會導致飢餓
非搶占式的演算法

6.時間片輪轉演算法
使用與分時系統，使用時間片，就緒進程按照到達先後排成隊列，依次在時間片內佔用處理機，時間片達到時就釋放處理機
時間片選擇很重要，過大就變成了先來先服務，過短又變成了短作業優先
時間片影響因素：系統響應時間，就緒隊列中的進程進程數目和系統的處理能力
不會導致飢餓
搶占式

7.多級反饋隊列調度演算法
實現思想：設置多個就緒隊列，為每個隊列設置不同的優先順序，優先鉛茄級一次遞減。每個隊列中的時間片各不相同，時間片依次遞減。每個隊列按照先來先服務原則進行進程排隊，若規定時間片內沒有完成，就將進程放入下一級。只有到高級隊列為空的時候，低等級隊列才能開始調度

優點：
終端型作業用戶：源羨短作業優先
短批處理作業用戶：周轉時間較短
長批處理作業用戶：前面幾個隊列得到部分執行，不會長期得不到處理

產生「飢餓」現象

搶占式

⑶ 進程調度演算法的國內外研究現狀有哪些

調度演算法是指：根據系統的資源分配策略所規定的資源分配演算法。常見的進程調度演算法有：

1.先來先去服務

2.時間片輪轉法

3.多級反饋隊列演算法

4.最短進程優先

5.最短剩餘時間優先

6.最高響應比優先

7.多級反饋隊列調度演算法

一、先來先去服務

先來先去服務調度演算法是一種最簡單的調度演算法，也稱為先進先出或嚴格排隊方案。當每個進程就緒後，它加入就緒隊列。當前正運行的進程停止執行，選擇在就緒隊列中存在時間最長的進程運行。該演算法既可以用於作業調度，也可以用於進程調度。先來先去服務比較適合於常作業（進程），而不利於段作業（進程）。

二、時間片輪轉法

輪轉法是基於適中的搶占策略的，以一個周期性間隔產生時鍾中斷，當中斷發生後，當前正在運行的進程被置於就緒隊列中，然後基於先來先去服務策略選擇下一個就緒作業的運行。這種技術也稱為時間片，因為每個進程再被搶占之前都給定一片時間。

三、最短進程優先

最短進程優先是一個非搶占策略，他的原則是下一次選擇預計處理時間最短的進程，因此短進程將會越過長作業，跳至隊列頭。該演算法即可用於作業調度，也可用於進程調度。但是他對長作業不利，不能保證緊迫性作業（進程）被及時處理，作業的長短只是被估算出來的。

四、最短剩餘時間優先

最短剩餘時間是針對最短進程優先增加了搶占機制的版本。在這種情況下，進程調度總是選擇預期剩餘時間最短的進程。當一個進程加入到就緒隊列時，他可能比當前運行的進程具有更短的剩餘時間，因此只要新進程就緒，調度程序就能可能搶占當前正在運行的進程。像最短進程優先一樣，調度程序正在執行選擇函數是必須有關於處理時間的估計，並且存在長進程飢餓的危險。

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

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

⑸ 進程調度演算法

FCFS調度演算法屬於不可剝奪演算法。從表面上看，它對所有作業都是公平的，但若一個長作業先到達系統，就會使後面許多短作業等待很長時間，因此它不能作為分時系統和實時系統的主要調度策略。但它常被結合在其他調度策略中使用。例如，在使用優先順序作為調度策略的系統中，往往對多個具有相同優先順序的進程按FCFS原則處理。

FCFS調度演算法的特點是演算法簡單，但效率低； 對長作業比較有利，但對短作業不利（相對SJF和高響應比）；

FCFS調度演算法有利於CPU繁忙型作業，而不利於I/O繁忙型作業。

​ 短作業優先調度演算法是一個非搶占策略，他的原則是下一次選擇預計處理時間最短的進程，因此短進程將會越過長作業，跳至隊列頭。該演算法即可用於作業調度，也可用於進程調度。 但是他對長作業不利，不能保證緊迫性作業（進程）被及時處理，作業的長短只是被估算出來的。

缺點：

該演算法對長作業不利，SJF調度演算法中長作業的周轉時間會增加。更嚴重的是，如果有一長作業進入系統的後備隊列，由於調度程序總是優先調度那些 (即使是後進來的）短作業，將導致長作業長期不被調度（「飢餓」現象，注意區分「死鎖」。後者是系統環形等待，前者是調度策略問題）。

該演算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業會被及時處理。

由於作業的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該演算法不一定能真正做到短作業優先調度。

SJF調度演算法的平均等待時間、平均周轉時間最少。

高響應比優先調度演算法既考慮作業的執行時間也考慮作業的等待時間，綜合了先來先服務和最短作業優先兩種演算法的特點。

該演算法中的響應比是指作業等待時間與運行比值，響應比公式定義如下：

響應比 =（等待時間+要求服務時間）/ 要求服務時間,即RR=（w+s）/s=1+w/s，因此 響應比一定是大於等於1的。

短作業與先後次序的兼顧，且不會使長作業長期得不到服務。

響應比計算系統開銷，增加系統開銷。

高響應比優先調度演算法適合批處理系統，主要用於作業調度。

為了實現 RR 調度，我們將就緒隊列視為進程的 FIFO 隊列。新進程添加到就緒隊列的尾部。CPU 調度程序從就緒隊列中選擇第一個進程，將定時器設置在一個時間片後中斷，最後分派這個進程。

接下來，有兩種情況可能發生。進程可能只需少於時間片的 CPU 執行。對於這種情況，進程本身會自動釋放 CPU。調度程序接著處理就緒隊列的下一個進程。否則，如果當前運行進程的 CPU 執行大於一個時間片，那麼定時器會中斷，進而中斷操作系統。然後，進行上下文切換，再將進程加到就緒隊列的尾部，接著 CPU 調度程序會選擇就緒隊列內的下一個進程。

採用 RR 策略的平均等待時間通常較長。

在 RR 調度演算法中，沒有進程被連續分配超過一個時間片的 CPU（除非它是唯一可運行的進程）。如果進程的 CPU 執行超過一個時間片，那麼該進程會被搶占，並被放回到就緒隊列。因此， RR調度演算法是搶占的。

演算法描述

1、進程在進入待調度的隊列等待時，首先進入優先順序最高的Q1等待。

2、首先調度優先順序高的隊列中的進程。若高優先順序中隊列中已沒有調度的進程，則調度次優先順序隊列中的進程。例如：Q1,Q2,Q3三個隊列，當且僅當在Q1中沒有進程等待時才去調度Q2，同理，只有Q1,Q2都為空時才會去調度Q3。

3、對於同一個隊列中的各個進程，按照FCFS分配時間片調度。比如Q1隊列的時間片為N，那麼Q1中的作業在經歷了N個時間片後若還沒有完成，則進入Q2隊列等待，若Q2的時間片用完後作業還不能完成，一直進入下一級隊列，直至完成。

4、在最後一個隊列QN中的各個進程，按照時間片輪轉分配時間片調度。

5、在低優先順序的隊列中的進程在運行時，又有新到達的作業，此時須立即把正在運行的進程放回當前隊列的隊尾，然後把處理機分給高優先順序進程。換而言之，任何時刻，只有當第1~i-1隊列全部為空時，才會去執行第i隊列的進程（搶占式）。特別說明，當再度運行到當前隊列的該進程時，僅分配上次還未完成的時間片，不再分配該隊列對應的完整時間片。

⑹ 進程調度有哪幾種方式有哪幾種評價方式

進程調度的幾種方式：

1、非剝奪（非搶占）調度方式：當一個進程正在處理機上執行時，即使有某個更為重要或者緊迫的進程進入就緒隊列，仍然讓正在執行的進程繼續執行，知道該進程完成或發生某種事件而進入阻塞態時，才把處理機分配給更為重要或緊迫（優先順序更高）的進程。其優點是實現簡單，系統開銷小，適用於大多數批處理系統，但它不能用於分時系統和大多數實時系統。

2、剝奪（搶占）調度方式：當一個進程正在處理機上執行時，若有某個更為重要或緊迫的進程（優先順序更高）的進程需要使用處理機，則立即暫停正在執行的進程，將處理機分配給這個更重要的進程。這種方式對提高系統吞吐率和響應效率都有明顯的好處。但搶占也要遵循一定原則。

(6)進程的調度演算法擴展閱讀：

為了比較處理機調度演算法的性能，人們提出了很多評價准則，主要有一下幾種：

1、CPU利用率：CPU是計算機系統中最重要和最昂貴的資源之一，所以應該盡可能使得CPU保持忙的狀態，資源利用率盡可能高。

2、系統吞吐量：單位時間內CPU完成的作業數量。長作業需要消耗較長的處理機時間，會降低系統的吞吐量。對於短作業，他們所需消耗的處理機時間較短，因此能提高系統吞吐量。調度演算法和方式不同，也會對系統的吞吐量產生較大影響。

3、周轉時間：周轉時間是指從作業提交到作業完成所經歷的時間，是作業等待、在就緒隊列中排隊，在處理機上運行及輸入輸出操作所花費的時間的總和。

4、等待時間：進程處於等處理機狀態的時間之和。等待時間越長，用戶滿意度越低。實際上，處理機調度演算法實際上並不影響作業執行或輸入輸出操作的時間，隻影響作業在就緒隊列中等待所花的時間。因此，衡量一個調度演算法的優劣，常常只需簡單地考察等待時間。

5、響應時間：用戶提交請求到系統首次產生響應所用的時間。在互動式系統中，周轉時間不可能是最好的評價准則，一般採用響應時間作業衡量調度演算法的重要准則之一。從用戶角度來看，調度策略應該盡量降低響應時間，使得響應時間處在用戶能接受的范圍之內。

⑺ 進程調度演算法

調度演算法是指：根據系統的資源分配策略所規定的資源分配演算法。
一、先來先服務和短作業（進程）優先調度演算法

1. 先來先服務調度演算法。先來先服務（FCFS）調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度， 也可用於進程調度。FCFS演算法比較有利於長作業（進程），而不利於短作業（進程）。由此可知，本演算法適合於CPU繁忙型作業， 而不利於I/O繁忙型的作業（進程）。
2. 短作業（進程）優先調度演算法。短作業（進程）優先調度演算法（SJ/PF）是指對短作業或短進程優先調度的演算法，該演算法既可用於作業調度， 也可用於進程調度。但其對長作業不利；不能保證緊迫性作業（進程）被及時處理；作業的長短只是被估算出來的。

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

1. 優先權調度演算法的類型。為了照顧緊迫性作業，使之進入系統後便獲得優先處理，引入了最高優先權優先（FPF）調度演算法。 此演算法常被用在批處理系統中，作為作業調度演算法，也作為多種操作系統中的進程調度，還可以用於實時系統中。當其用於作業調度， 將後備隊列中若干個優先權最高的作業裝入內存。當其用於進程調度時，把處理機分配給就緒隊列中優先權最高的進程，此時， 又可以進一步把該演算法分成以下兩種：
1)非搶占式優先權演算法
2)搶占式優先權調度演算法（高性能計算機操作系統）
2. 優先權類型 。對於最高優先權優先調度演算法，其核心在於：它是使用靜態優先權還是動態優先權， 以及如何確定進程的優先權。
3. 高響應比優先調度演算法
為了彌補短作業優先演算法的不足，我們引入動態優先權，使作業的優先等級隨著等待時間的增加而以速率a提高。 該優先權變化規律可描述為：優先權=（等待時間+要求服務時間）/要求服務時間；即 =（響應時間）/要求服務時間

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

1. 時間片輪轉法。時間片輪轉法一般用於進程調度，每次調度，把CPU分配隊首進程，並令其執行一個時間片。 當執行的時間片用完時，由一個記時器發出一個時鍾中斷請求，該進程被停止，並被送往就緒隊列末尾；依次循環。 2. 多級反饋隊列調度演算法 多級反饋隊列調度演算法多級反饋隊列調度演算法，不必事先知道各種進程所需要執行的時間，它是目前被公認的一種較好的進程調度演算法。 其實施過程如下：
1) 設置多個就緒隊列，並為各個隊列賦予不同的優先順序。在優先權越高的隊列中， 為每個進程所規定的執行時間片就越小。
2) 當一個新進程進入內存後，首先放入第一隊列的末尾，按FCFS原則排隊等候調度。 如果他能在一個時間片中完成，便可撤離；如果未完成，就轉入第二隊列的末尾，在同樣等待調度…… 如此下去，當一個長作業（進程）從第一隊列依次將到第n隊列（最後隊列）後，便按第n隊列時間片輪轉運行。
3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1到第（i-1）隊列空時， 才會調度第i隊列中的進程運行，並執行相應的時間片輪轉。
4) 如果處理機正在處理第i隊列中某進程，又有新進程進入優先權較高的隊列， 則此新隊列搶占正在運行的處理機，並把正在運行的進程放在第i隊列的隊尾。

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

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

⑼ linux系統的進程調度

Linux進程調度

1．調度方式

Linux系統的調度方式基本上採用「 搶占式優先順序 」方式，當進程在用戶模式下運行時，不管它是否自願，核心在一定條件下（如該進程的時間片用完或等待I/O）可以暫時中止其運行，而調度其他進程運行。一旦進程切換到內核模式下運行時，就不受以上限制，而一直運行下去，僅在重新回到用戶模式之前才會發生進程調度。

Linux系統中的調度基本上繼承了UNIX系統的 以優先順序為基礎 的調度。也就是說，核心為系統中每個進程計算出一個優先順序，該優先順序反映了一個進程獲得CPU使用權的資格，即高優先順序的進程優先得到運行。核心從進程就緒隊列中挑選一個優先順序最高的進程，為其分配一個CPU時間片，令其投入運行。在運行過程中，當前進程的優先順序隨時間遞減，這樣就實現了「負反饋」作用，即經過一段時間之後，原來級別較低的進程就相對「提升」了級別，從而有機會得到運行。當所有進程的優先順序都變為0（最低）時，就重新計算一次所有進程的優先順序。

2．調度策略

Linux系統針對不同類別的進程提供了3種不同的調度策略，即SCHED_FIFO、SCHED_RR及SCHED_OTHER。其中，SCHED_FIFO適合於 短實時進程 ，它們對時間性要求比較強，而每次運行所需的時間比較短。一旦這種進程被調度且開始運行，就一直運行到自願讓出CPU或被優先順序更高的進程搶占其執行權為止。

SCHED_RR對應「時間片輪轉法」，適合於每次運行需要 較長時間的實時進程 。一個運行進程分配一個時間片（200 ms），當時間片用完後，CPU被另外進程搶占，而該進程被送回相同優先順序隊列的末尾，核心動態調整用戶態進程的優先順序。這樣，一個進程從創建到完成任務後終止，需要經歷多次反饋循環。當進程再次被調度運行時，它就從上次斷點處開始繼續執行。

SCHED_OTHER是傳統的UNIX調度策略，適合於互動式的 分時進程 。這類進程的優先順序取決於兩個因素：一個是進程剩餘時間配額，如果進程用完了配給的時間，則相應優先順序降到0；另一個是進程的優先數nice，這是從UNIX系統沿襲下來的方法，優先數越小，其優先順序越高。nice的取值范圍是-20 19。用戶可以利用nice命令設定進程的nice值。但一般用戶只能設定正值，從而主動降低其優先順序；只有特權用戶才能把nice的值設置為負數。進程的優先順序就是以上二者之和。

後台命令對應後台進程（又稱後台作業）。後台進程的優先順序低於任何交互（前台）進程的優先順序。所以，只有當系統中當前不存在可運行的交互進程時，才調度後台進程運行。後台進程往往按批處理方式調度運行。

3．調度時機

核心進行進程調度的時機有以下5種情況：

（1）當前進程調用系統調用nanosleep( )或者pause( )，使自己進入睡眠狀態，主動讓出一段時間的CPU的使用權。

（2）進程終止，永久地放棄對CPU的使用。

（3）在時鍾中斷處理程序執行過程中，發現當前進程連續運行的時間過長。

（4）當喚醒一個睡眠進程時，發現被喚醒的進程比當前進程更有資格運行。

（5）一個進程通過執行系統調用來改變調度策略或者降低自身的優先順序（如nice命令），從而引起立即調度。

4．調度演算法

進程調度的演算法應該比較簡單，以便減少頻繁調度時的系統開銷。Linux執行進程調度時，首先查找所有在就緒隊列中的進程，從中選出優先順序最高且在內存的一個進程。如果隊列中有實時進程，那麼實時進程將優先運行。如果最需要運行的進程不是當前進程，那麼當前進程就被掛起，並且保存它的現場—— 所涉及的一切機器狀態，包括程序計數器和CPU寄存器等，然後為選中的進程恢復運行現場。

（二）Linux常用調度命令

· nohup命令

nohup命令的功能是以忽略掛起和退出的方式執行指定的命令。其命令格式是：

nohupcommand［arguments］

其中，command是所要執行的命令，arguments是指定命令的參數。

nohup命令告訴系統，command所代表的命令在執行過程中不受任何結束運行的信號（hangup和quit）的影響。例如，

$ nohup find / -name exam.txt -print>f1 &

find命令在後台運行。在用戶注銷後，它會繼續運行：從根目錄開始，查找名字是exam.txt的文件，結果被定向到文件f1中。

如果用戶沒有對輸出進行重定向，則輸出被附加到當前目錄的nohup.out文件中。如果用戶在當前目錄中不具備寫許可權，則輸出被定向到$HOME/nohup.out 中。

· at命令

at命令允許指定命令執行的時間。at命令的常用形式是：

attimecommand

其中，time是指定命令command在將來執行時的時間和日期。時間的指定方法有多種，用戶可以使用絕對時間，也可以用相對時間。該指定命令將以作業形式在後台運行。例如：

$ at 15:00 Oct 20

回車後進入接收方式，接著鍵入以下命令：

mail -s "Happy Birthday!" liuzheny

按下D鍵，屏幕顯示：

job 862960800.a at Wed Oct 20 15:00:00 CST 1999

$

表明建立了一個作業，其作業ID號是862960800.a，運行作業的時間是1999年10月20日下午3:00，給liuzheny發一條標題為「Happy Birthday！」（生日快樂）的空白郵件。

利用 at-l 可以列出當前at隊列中所有的作業。

利用 at-r 可以刪除指定的作業。這些作業以前由at或batch命令調度。例如，

at-r862960797.a

將刪除作業ID號是862960797.a的作業。其一般使用形式是：

at-rjob_id

注意，結尾是.a的作業ID號，表示這個作業是由at命令提交的；結尾是.b的作業ID號，表示這個作業是由batch命令提交的。

· batch命令

batch命令不帶任何參數，它提交的作業的優先順序比at命令提交的作業的優先順序低。batch無法指定作業運行的時間。實際運行時間要看系統中已經提交的作業數量。如果系統中優先順序較高的作業比較多，那麼，batch提交的作業則需要等待；如果系統空閑，則運行batch提交的作業。例如，

$ batch

回車後進入接收方式，接著鍵入命令：

find / -name exam.txt -print

按下D。退出接收方式，屏幕顯示：

job 862961540.b at Thu Nov 18 14:30:00 CST 1999

表示find命令被batch作為一個作業提交給系統，作業ID號是862961540.b。如果系統當前空閑，這個作業被立即執行，其結果同樣作為郵件發送給用戶。

· jobs命令

jobs命令用來顯示當前shell下正在運行哪些作業（即後台作業）。例如：

$ jobs

[2] + Running tar tv3 *&

[1] - Running find / -name README -print > logfile &

$

其中，第一列方括弧中的數字表示作業序號，它是由當前運行的shell分配的，而不是由操作系統統一分配的。在當前shell環境下，第一個後台作業的作業號為1，第二個作業的作業號為2，等等。

第二列中的「 」號表示相應作業的優先順序比「－」號對應作業的優先順序高。

第三列表明作業狀態，是否為運行、中斷、等待輸入或停止等。

最後列出的是創建當前這個作業所對應的命令行。

利用 jobs-l 形式，可以在作業號後顯示出相應進程的PID。如果想只顯示相應進程的PID，不顯示其它信息，則使用 jobs-p 形式。

· fg命令

fg命令把指定的後台作業移到前台。其使用格式是：

fg [job…]

其中，參數job是一個或多個進程的PID，或者是命令名稱或者作業號（前面要帶有一個「%」號）。例如：

$ jobs

[2] + Running tar tv3 *&

[1] - Running find / -name README -print > logfile&

$ fg %find

find / -name README -print > logfile

注意，顯示的命令行末尾沒有「&」符號。下面命令能產生同樣的效果：

$ fg %1

這樣，find命令對應的進程就在前台執行。當後台只有一個作業時，鍵入不帶參數的fg命令，就能使相應進程移到前台。當有兩個或更多的後台作業時，鍵入不帶參數的fg，就把最後進入後台的進程首先移到前台。

· bg命令

bg命令可以把前台進程換到後台執行。其使用格式是：

bg [job…]

其中，job是一個或多個進程的PID、命令名稱或者作業號，在參數前要帶「%」號。例如，在cc（C編譯命令）命令執行過程中，按下Z鍵，使這個作業掛起。然後鍵入以下命令：

$ bg %cc

該掛起的作業在後台重新開始執行。

⑽ linux環境下的進程調度演算法有哪些

第一部分： 實時調度演算法介紹

對於什麼是實時系統，POSIX 1003.b作了這樣的定義：指系統能夠在限定的響應時間內提供所需水平的服務。而一個由Donald Gillies提出的更加為大家接受的定義是：一個實時系統是指計算的正確性不僅取決於程序的邏輯正確性，也取決於結果產生的時間，如果系統的時間約束條件得不到滿足，將會發生系統出錯。

實時系統根據其對於實時性要求的不同，可以分為軟實時和硬實時兩種類型。硬實時系統指系統要有確保的最壞情況下的服務時間，即對於事件的響應時間的截止期限是無論如何都必須得到滿足。比如航天中的宇宙飛船的控制等就是現實中這樣的系統。其他的所有有實時特性的系統都可以稱之為軟實時系統。如果明確地來說，軟實時系統就是那些從統計的角度來說，一個任務（在下面的論述中，我們將對任務和進程不作區分）能夠得到有確保的處理時間，到達系統的事件也能夠在截止期限到來之前得到處理，但違反截止期限並不會帶來致命的錯誤，像實時多媒體系統就是一種軟實時系統。

一個計算機系統為了提供對於實時性的支持，它的操作系統必須對於CPU和其他資源進行有效的調度和管理。在多任務實時系統中，資源的調度和管理更加復雜。本文下面將先從分類的角度對各種實時任務調度演算法進行討論，然後研究普通的 Linux操作系統的進程調度以及各種實時Linux系統為了支持實時特性對普通Linux系統所做的改進。最後分析了將Linux操作系統應用於實時領域中時所出現的一些問題，並總結了各種實時Linux是如何解決這些問題的。

1. 實時CPU調度演算法分類

各種實時操作系統的實時調度演算法可以分為如下三種類別[Wang99][Gopalan01]：基於優先順序的調度演算法（Priority-driven scheling-PD）、基於CPU使用比例的共享式的調度演算法（Share-driven scheling-SD）、以及基於時間的進程調度演算法（Time-driven scheling-TD），下面對這三種調度演算法逐一進行介紹。

1.1. 基於優先順序的調度演算法

基於優先順序的調度演算法給每個進程分配一個優先順序，在每次進程調度時，調度器總是調度那個具有最高優先順序的任務來執行。根據不同的優先順序分配方法，基於優先順序的調度演算法可以分為如下兩種類型[Krishna01][Wang99]：

靜態優先順序調度演算法：

這種調度演算法給那些系統中得到運行的所有進程都靜態地分配一個優先順序。靜態優先順序的分配可以根據應用的屬性來進行，比如任務的周期，用戶優先順序，或者其它的預先確定的策略。RM（Rate-Monotonic）調度演算法是一種典型的靜態優先順序調度演算法，它根據任務的執行周期的長短來決定調度優先順序，那些具有小的執行周期的任務具有較高的優先順序。

動態優先順序調度演算法：

這種調度演算法根據任務的資源需求來動態地分配任務的優先順序，其目的就是在資源分配和調度時有更大的靈活性。非實時系統中就有很多這種調度演算法，比如短作業優先的調度演算法。在實時調度演算法中， EDF演算法是使用最多的一種動態優先順序調度演算法，該演算法給就緒隊列中的各個任務根據它們的截止期限（Deadline）來分配優先順序，具有最近的截止期限的任務具有最高的優先順序。

1.2. 基於比例共享調度演算法

雖然基於優先順序的調度演算法簡單而有效，但這種調度演算法提供的是一種硬實時的調度，在很多情況下並不適合使用這種調度演算法：比如象實時多媒體會議系統這樣的軟實時應用。對於這種軟實時應用，使用一種比例共享式的資源調度演算法（SD演算法）更為適合。

比例共享調度演算法指基於CPU使用比例的共享式的調度演算法，其基本思想就是按照一定的權重（比例）對一組需要調度的任務進行調度，讓它們的執行時間與它們的權重完全成正比。

我們可以通過兩種方法來實現比例共享調度演算法[Nieh01]：第一種方法是調節各個就緒進程出現在調度隊列隊首的頻率，並調度隊首的進程執行；第二種做法就是逐次調度就緒隊列中的各個進程投入運行，但根據分配的權重調節分配個每個進程的運行時間片。

比例共享調度演算法可以分為以下幾個類別：輪轉法、公平共享、公平隊列、彩票調度法（Lottery）等。

比例共享調度演算法的一個問題就是它沒有定義任何優先順序的概念；所有的任務都根據它們申請的比例共享CPU資源，當系統處於過載狀態時，所有的任務的執行都會按比例地變慢。所以為了保證系統中實時進程能夠獲得一定的CPU處理時間，一般採用一種動態調節進程權重的方法。

1.3. 基於時間的進程調度演算法

對於那些具有穩定、已知輸入的簡單系統，可以使用時間驅動（Time-driven:TD）的調度演算法，它能夠為數據處理提供很好的預測性。這種調度演算法本質上是一種設計時就確定下來的離線的靜態調度方法。在系統的設計階段，在明確系統中所有的處理情況下，對於各個任務的開始、切換、以及結束時間等就事先做出明確的安排和設計。這種調度演算法適合於那些很小的嵌入式系統、自控系統、感測器等應用環境。

這種調度演算法的優點是任務的執行有很好的可預測性，但最大的缺點是缺乏靈活性，並且會出現有任務需要被執行而CPU卻保持空閑的情況。

2. 通用Linux系統中的CPU調度

通用Linux系統支持實時和非實時兩種進程，實時進程相對於普通進程具有絕對的優先順序。對應地，實時進程採用SCHED_FIFO或者SCHED_RR調度策略，普通的進程採用SCHED_OTHER調度策略。

在調度演算法的實現上，Linux中的每個任務有四個與調度相關的參數，它們是rt_priority、policy、priority（nice）、counter。調度程序根據這四個參數進行進程調度。

在SCHED_OTHER 調度策略中，調度器總是選擇那個priority+counter值最大的進程來調度執行。從邏輯上分析，SCHED_OTHER調度策略存在著調度周期（epoch），在每一個調度周期中，一個進程的priority和counter值的大小影響了當前時刻應該調度哪一個進程來執行，其中 priority是一個固定不變的值，在進程創建時就已經確定，它代表了該進程的優先順序，也代表這該進程在每一個調度周期中能夠得到的時間片的多少； counter是一個動態變化的值，它反映了一個進程在當前的調度周期中還剩下的時間片。在每一個調度周期的開始，priority的值被賦給 counter，然後每次該進程被調度執行時，counter值都減少。當counter值為零時，該進程用完自己在本調度周期中的時間片，不再參與本調度周期的進程調度。當所有進程的時間片都用完時，一個調度周期結束，然後周而復始。另外可以看出Linux系統中的調度周期不是靜態的，它是一個動態變化的量，比如處於可運行狀態的進程的多少和它們priority值都可以影響一個epoch的長短。值得注意的一點是，在2.4以上的內核中， priority被nice所取代，但二者作用類似。

可見SCHED_OTHER調度策略本質上是一種比例共享的調度策略，它的這種設計方法能夠保證進程調度時的公平性--一個低優先順序的進程在每一個epoch中也會得到自己應得的那些CPU執行時間，另外它也提供了不同進程的優先順序區分，具有高priority值的進程能夠獲得更多的執行時間。

對於實時進程來說，它們使用的是基於實時優先順序rt_priority的優先順序調度策略，但根據不同的調度策略，同一實時優先順序的進程之間的調度方法有所不同：

SCHED_FIFO：不同的進程根據靜態優先順序進行排隊，然後在同一優先順序的隊列中，誰先准備好運行就先調度誰，並且正在運行的進程不會被終止直到以下情況發生：1.被有更高優先順序的進程所強佔CPU；2.自己因為資源請求而阻塞；3.自己主動放棄CPU（調用sched_yield）；

SCHED_RR：這種調度策略跟上面的SCHED_FIFO一模一樣，除了它給每個進程分配一個時間片，時間片到了正在執行的進程就放棄執行；時間片的長度可以通過sched_rr_get_interval調用得到；

由於Linux系統本身是一個面向桌面的系統，所以將它應用於實時應用中時存在如下的一些問題：

Linux系統中的調度單位為10ms，所以它不能夠提供精確的定時；

當一個進程調用系統調用進入內核態運行時，它是不可被搶占的；

Linux內核實現中使用了大量的封中斷操作會造成中斷的丟失；

由於使用虛擬內存技術，當發生頁出錯時，需要從硬碟中讀取交換數據，但硬碟讀寫由於存儲位置的隨機性會導致隨機的讀寫時間，這在某些情況下會影響一些實時任務的截止期限；

雖然Linux進程調度也支持實時優先順序，但缺乏有效的實時任務的調度機制和調度演算法；它的網路子系統的協議處理和其它設備的中斷處理都沒有與它對應的進程的調度關聯起來，並且它們自身也沒有明確的調度機制；

3. 各種實時Linux系統

3.1. RT-Linux和RTAI

RT -Linux是新墨西哥科技大學（New Mexico Institute of Technology）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，為了在Linux系統中提供對於硬實時的支持，它實現了一個微內核的小的實時操作系統（我們也稱之為RT-Linux的實時子系統），而將普通Linux系統作為一個該操作系統中的一個低優先順序的任務來運行。另外普通Linux系統中的任務可以通過FIFO和實時任務進行通信。RT-Linux的框架如圖 1所示：

圖 1 RT-Linux結構

RT -Linux的關鍵技術是通過軟體來模擬硬體的中斷控制器。當Linux系統要封鎖CPU的中斷時時，RT-Linux中的實時子系統會截取到這個請求，把它記錄下來，而實際上並不真正封鎖硬體中斷，這樣就避免了由於封中斷所造成的系統在一段時間沒有響應的情況，從而提高了實時性。當有硬體中斷到來時， RT-Linux截取該中斷，並判斷是否有實時子系統中的中斷常式來處理還是傳遞給普通的Linux內核進行處理。另外，普通Linux系統中的最小定時精度由系統中的實時時鍾的頻率決定，一般Linux系統將該時鍾設置為每秒來100個時鍾中斷，所以Linux系統中一般的定時精度為 10ms，即時鍾周期是10ms，而RT-Linux通過將系統的實時時鍾設置為單次觸發狀態，可以提供十幾個微秒級的調度粒度。

RT-Linux實時子系統中的任務調度可以採用RM、EDF等優先順序驅動的演算法，也可以採用其他調度演算法。

RT -Linux對於那些在重負荷下工作的專有系統來說，確實是一個不錯的選擇，但他僅僅提供了對於CPU資源的調度；並且實時系統和普通Linux系統關系不是十分密切，這樣的話，開發人員不能充分利用Linux系統中已經實現的功能，如協議棧等。所以RT-Linux適合與工業控制等實時任務功能簡單，並且有硬實時要求的環境中，但如果要應用與多媒體處理中還需要做大量的工作。

義大利的RTAI( Real-Time Application Interface )源於RT-Linux，它在設計思想上和RT-Linux完全相同。它當初設計目的是為了解決RT-Linux難於在不同Linux版本之間難於移植的問題，為此，RTAI在 Linux 上定義了一個實時硬體抽象層，實時任務通過這個抽象層提供的介面和Linux系統進行交互，這樣在給Linux內核中增加實時支持時可以盡可能少地修改 Linux的內核源代碼。

3.2. Kurt-Linux

Kurt -Linux由Kansas大學開發，它可以提供微秒級的實時精度[KurtWeb] [Srinivasan]。不同於RT-Linux單獨實現一個實時內核的做法，Kurt -Linux是在通用Linux系統的基礎上實現的，它也是第一個可以使用普通Linux系統調用的基於Linux的實時系統。

Kurt-Linux將系統分為三種狀態：正常態、實時態和混合態，在正常態時它採用普通的Linux的調度策略，在實時態只運行實時任務，在混合態實時和非實時任務都可以執行；實時態可以用於對於實時性要求比較嚴格的情況。

為了提高Linux系統的實時特性，必須提高系統所支持的時鍾精度。但如果僅僅簡單地提高時鍾頻率，會引起調度負載的增加，從而嚴重降低系統的性能。為了解決這個矛盾， Kurt-Linux採用UTIME所使用的提高Linux系統中的時鍾精度的方法[UTIMEWeb]：它將時鍾晶元設置為單次觸發狀態（One shot mode），即每次給時鍾晶元設置一個超時時間，然後到該超時事件發生時在時鍾中斷處理程序中再次根據需要給時鍾晶元設置一個超時時間。它的基本思想是一個精確的定時意味著我們需要時鍾中斷在我們需要的一個比較精確的時間發生，但並非一定需要系統時鍾頻率達到此精度。它利用CPU的時鍾計數器TSC (Time Stamp Counter)來提供精度可達CPU主頻的時間精度。

對於實時任務的調度，Kurt-Linux採用基於時間（TD）的靜態的實時CPU調度演算法。實時任務在設計階段就需要明確地說明它們實時事件要發生的時間。這種調度演算法對於那些循環執行的任務能夠取得較好的調度效果。

Kurt -Linux相對於RT-Linux的一個優點就是可以使用Linux系統自身的系統調用，它本來被設計用於提供對硬實時的支持，但由於它在實現上只是簡單的將Linux調度器用一個簡單的時間驅動的調度器所取代，所以它的實時進程的調度很容易受到其它非實時任務的影響，從而在有的情況下會發生實時任務的截止期限不能滿足的情況，所以也被稱作嚴格實時系統（Firm Real-time）。目前基於Kurt-Linux的應用有：ARTS（ATM Reference Traffic System）、多媒體播放軟體等。另外Kurt-Linux所採用的這種方法需要頻繁地對時鍾晶元進行編程設置。

3.3. RED-Linux

RED -Linux是加州大學Irvine分校開發的實時Linux系統[REDWeb][ Wang99]，它將對實時調度的支持和Linux很好地實現在同一個操作系統內核中。它同時支持三種類型的調度演算法，即：Time-Driven、 Priority-Dirven、Share-Driven。

為了提高系統的調度粒度，RED-Linux從RT-Linux那兒借鑒了軟體模擬中斷管理器的機制，並且提高了時鍾中斷頻率。當有硬體中斷到來時，RED-Linux的中斷模擬程序僅僅是簡單地將到來的中斷放到一個隊列中進行排隊，並不執行真正的中斷處理程序。

另外為了解決Linux進程在內核態不能被搶占的問題， RED-Linux在Linux內核的很多函數中插入了搶占點原語，使得進程在內核態時，也可以在一定程度上被搶占。通過這種方法提高了內核的實時特性。

RED-Linux的設計目標就是提供一個可以支持各種調度演算法的通用的調度框架，該系統給每個任務增加了如下幾項屬性，並將它們作為進程調度的依據：

Priority：作業的優先順序；

Start-Time：作業的開始時間；

Finish-Time：作業的結束時間；

Budget：作業在運行期間所要使用的資源的多少；

通過調整這些屬性的取值及調度程序按照什麼樣的優先順序來使用這些屬性值，幾乎可以實現所有的調度演算法。這樣的話，可以將三種不同的調度演算法無縫、統一地結合到了一起。