1. 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
該掛起的作業在後台重新開始執行。
2. 進程調度的演算法
演算法總是把處理機分配給最先進入就緒隊列的進程,一個進程一旦分得處理機,便一直執行下去,直到該進程完成或阻塞時,才釋放處理機。
例如,有三個進程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規則排隊,按一定的時間間隔把處理機分配給隊列中的進程。這樣,就緒隊列中所有進程均可獲得一個時間片的處理機而運行。
多級隊列方法:將系統中所有進程分成若干類,每類為一級。 多級反饋隊列方式是在系統中設置多個就緒隊列,並賦予各隊列以不同的優先權。
3. unix系統v的進程調度是採用怎樣的調度演算法完成的
答案為D。 多級反饋隊列輪轉法 調度演算法(作業調度、進程調度) 1、先來先服務調度演算法(FCFS) 按進入後備(或就緒)隊列的先後選擇目標作業(或進程)。 有利於長作業(進程),不利於短作業(進程)。 2、最短作業優先調度演算法SJ(P)F 從後備(或就緒)隊列中選擇估計運行時間最短的作業(或進程) tn+1=a tn+(1-a) tn tn為實際值, tn為預測值 SJF有效地降低作業的平均等待時間,提高了系統的吞吐量。 對長作業(或進程)不利,可能死等,且未考慮作業的緊迫程度。 3、時間片輪轉調度演算法(進程調度) 系統將所有的就緒進程按先來先服務原則,排成一個隊列,每次調度時把CPU分配給隊首進程,令其執行一個時間片。 就緒隊列中所有進程,在一個給定的時間內,均能獲得一個時間片的處理機執行時間。T=nq 4、優先權調度演算法 適用於作業調度和進程調度。 非搶占式、搶占式優先權調度演算法 優先權類型:靜態優先權、動態優先權 5、高響應比優先調度演算法(作業調度) 響應比RP= 響應時間/要求服務時間=(等待時間+要求服務時間)/要求服務時間 = 1+等待時間/要求服務時間 同時到達的作業(等待時間相同),要求服務時間越短(短作業),響應比越高,有利於短作業。 要求服務時間相同的作業,等待時間越長,響應比越高,相當於先來先服務。 長作業在等待足夠長時間後,響應比上升,也可被調度,避免長作業的死等。 每次調度需計算響應比,增加系統的開銷。 6、多級隊列調度 根據作業的性質或類型的不同,將就緒進程隊列分成若干個子隊列,各個作業固定分屬於一個隊列。每個隊列採用各自的調度演算法。 7、多級反饋隊列調度演算法 UNIX系統中的進程調度演算法。 處理方法: 設置多個就緒隊列,每個隊列賦予不同的優先權(S1>S2……>Sn ),且各隊列中進程執行的時間片的大小各不相同(q,2q……nq)。 新進程進入內存,首先放在S1的末尾,按FCFS排隊調度,執行q時間片,若未完成,該進程轉入S2,依次類推。 僅當Si空閑,才會調度Si+1中進程。 能較好地滿足各種類型用戶的需要。
4. 第三章 進程調度的幾種方式
進程調度概念:操作系統必須為多個,嗎進程可能有競爭的請求分配計算機資源。對處理器而言,可分配的資源是在處理器上的執行時間,分配途徑是調度。調度功能必須設計成可以滿足多個目標,包括公平、任何進程都不會餓死、有效地使用處理器時間和低開銷。此外,調度功能可能需要為某些進程的啟動或結束考慮不同的優先順序和實時最後期限。
這些年以來,調度已經成為深入研究的焦點,並且已經實現了許多不同的演算法。如今,調度研究的重點是開發多處理系統,特別是用於多線程的。
下面簡介幾種調度演算法。
一、先來先服務和短作業(進程)優先調度演算法
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隊列的末尾,把處理機分配給新到的高優先權進程。
5. 操作系統的進程調度演算法[總結]
操作系統的進程調度演算法直接關繫到用戶的使用體驗。
如果把用戶的體驗時間,引入到計算機裡面,我們引入以下幾個概念。
周轉時間,指作業從提交系統開始,直到作業完成為止的時間間隔。包括:
是指作業周轉時間與作業實際運行服務時間的比值。
平均周轉時間和平均帶權周轉時間是衡量批處理系統調度演算法的重要准則。
先來先服務調度演算法(First Come First Served, FCFS)是最簡單的調度演算法,可以用於作業調度和進程調度。
按照作業進入系統後備作業隊列的先後次序來挑選作業,加入就緒隊列,等待執行。
FCFS是非搶占式的,易於實現,效率不高,性能不好.
有利於長作業(CPU繁忙性)而不利於短作業(I/O繁忙性)。
服務時間:作業需要運行的時間
完成時間 = 開始時間 + 服務時間
等待時間 = 開始時間 - 提交時間
周轉時間 = 完成時間 - 提交時間
帶權周轉時間 = 周轉時間 / 服務時間
響應比 = (等待時間 + 服務時間) / 服務時間 = 等待時間/服務時間 + 1
該演算法每次從後備作業隊列中挑選估計服務時間最短的一個或幾個作業,
將他們調入內存,分配必要的資源,創建進程並放入就緒隊列。
在進程調度中的原理類似。
SJF是非搶占式的,優先照顧短作業,具有很好的性能,降低平均等待時間,提高吞吐量。
但是不利於長作業,長作業可能一直處於等待狀態,出現飢餓現象;
完全未考慮作業的優先緊迫程度,不能用於實時系統。
高響應比優先調度演算法(Highest Reponse Ratio First, HRRF)是非搶占式的,主要用於作業調度。
基本思想:每次進行作業調度時,先計算後備作業隊列中每個作業的響應比,挑選最高的作業投入系統運行。
響應比 = (等待時間 + 服務時間) / 服務時間 = 等待時間 / 服務時間 + 1
由響應比分析可知,該演算法介於FCFS和SJF之間,但是每次需要計算每個作業的響應比,增加系統開銷。
6. 進程調度
當計算機中有多個process處於ready狀態,將CPU分配給哪個進程呢?操作系統中做出這個決策的組件就是調度器,決策的演算法叫調度演算法,決策過程就是進程調度的過程。
進程調度一般發生在一下幾種情況下:
在非搶占式調度中,進程開始執行以後,除非它主動放棄CPU或被block, 否則就能一直執行。
搶占式調度中,如果在進程執行過程中來了一個優先順序更高的進程,CPU使用權就會被搶走,尤其在時間片調度中即使時間片沒用完也可以被搶占。但搶占也不是隨時可以發生的,如果設計不好可能會發生優先順序逆轉或者死鎖問題。
在不同的場景下,為了實現不同的目標,評價調度演算法的標准不盡相同。這里我們介紹一些常用的標准:
Fairness : 給每個進程公平的CPU使用機會
Balance : 讓系統的各個組件都能得到最大程度的利用率
Throughput 吞吐量 :單位時間內完成的任務數量
Turnaround Time :一般在批處理系統中,一個批任務從提交到結束的間隔時間
CPU Utilization :CPU的利用率
Waiting Time :進程在ready隊列里等待的時間
Response Time :一般在互動式系統中,從用戶提交任務到第一次得到響應(任務不一定完成)的間隔時間
Meeting Deadline :一般在實時系統中及時處理數據,避免丟失或失效
接下來我們看看在三種不同類型系統中常用的調度演算法。
1. FCFS : First Come, First Served
這是一種非搶占式的先來先服務演算法。ready process隊列只有一個。如果進程執行中被block,進入block隊列,ready之後作為新的進程排到ready隊列的尾部。
優點:容易理解,容易實現
缺點:平均等待時間往往很長,不好平衡CPU密集和IO密集型進程
2. SJF: Shortest Job First
SJF也是非搶占式調度,每次都選擇最短的任務來執行。
3. Shortest Remaining Time Next
是SJF的搶占式版本,只要有新任務到達就重新調度選擇剩餘時間最短的任務執行。
SJF和Shortest Remaining Time Next的問題在於一般情況下很難判斷進程的剩餘執行時間是多少。除非這是經常要執行的task,根據對歷史的統計分析能確定一個執行時間的大致范圍。
1. Round-Robin Scheling
輪詢調度。 給每個進程相同的時間片,輪流執行。一般時間片選擇在20-50msec比較合適,太短會導致進程切換浪費時間,太長會導致響應時間延長。
優點:比SJF響應快
缺點:turnaround時間長
2. Priority Scheling
優先順序調度為每個進程分配優先順序,高優先順序先執行,這也是時間片調度演算法。優先順序可以靜態分配也可以動態分配,為了避免高優先順序的進程一直佔用CPU不放,可以在依次執行結束後降低其優先順序。相同優先順序的進程之間可以使用其他的調度演算法如round-robin,不同隊列可以使用不同的調度演算法。
優點:引入了優先順序
3. Multiple Queues
為了避免執行時間長的進程頻繁進程切換,可以在不同的優先順序隊列之間分配不等長度的時間片。進程執行一次之後被分配其他擁有更長執行時間的優先順序。比如一個進程需要100個quanta, 第一次執行時分配1個,下一次執行分配2個,再下次分配4,8,16,32,64. 比每次都只分配1的純輪詢演算法減少了進程調度的次數。
4. Guaranteed Scheling
前面提到的演算法都不保證進程能夠得到的CPU時間,但有些情況下我們需要確保進程使用CPU的機會和時間,比如n個用戶同時登錄,一般要保證每個用戶都能獲得1/n的CPU,或者我們購買VPN服務,根據不同的用戶級別需要獲得一定的帶寬保證。這種演算法就叫Guaranteed 調度。在實現中,需要追蹤給每個進程分配的CPU,與承諾分配量比較,比值最小的進程會獲得下一次使用權。
5. Lottery Scheling
彩票調度演算法引入了隨機性,為每個進程發一張彩票,調度時就像開獎,誰中獎誰獲得資源。優先順序更高的進程可以獲得多張彩票以提高中獎機會。
彩票調度有趣的地方在於進程之間可以互贈彩票,比如process 1 pending在process 2上,它可以把自己的彩票都給process2提高它被調度的機會。process2結束以後再把彩票還給process1.
6. Fair-Share Scheling
下面考慮一種情況,所有進程並不屬於一個用戶,這在Linux 系統中非常常見。如果user1有99個process,user2隻有1個process,按照前面的演算法可能user1能得到99%的CPU,而user2隻有1%。為了實現用戶層面的公平性,調度時需要考慮進程屬於哪個user.
實時系統分兩種:
實時系統中,一般任務時間都比較短,調度器需要使所有進程都在deadline前完成。對於周期性發生的事件,如果事件發生的周期為 , 事件處理時間(需要佔用CPU的時間)為 , 只有 時,才是可調度的。
調度演算法只能由操作系統實現嗎,關於使用哪種調度演算法進程是否有話語權呢?答案是可以的。將機制與策略分離,由操作系統提供多種實現機制,並提供system call由process傳參數給OS指定具體使用哪一種調度策略。
如果線程是在用戶態實現的,那麼需要兩級調度,OS負責調度process,process負責調度thread。如果線程是在內核態實現的,OS直接調度thread,而不關心它屬於哪個process。