【正文】 多個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放入就緒隊列。在進程調(diào)度中采用 FCFS算法時，則每次調(diào)度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發(fā)生某事件而阻塞后才放棄處理機。 第三章 處理機調(diào)度與死鎖 FCFS算法比較有利于長作業(yè) (進程 )，而不利于短作業(yè)(進程 )。下表列出了 A、 B、 C、 D四個作業(yè)分別到達系統(tǒng)的時間、要求服務(wù)的時間、開始執(zhí)行的時間及各自的完成時間，并計算出各自的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間。 進程名 到達時間 服務(wù)時間 開始執(zhí)行時間 完成時間 周轉(zhuǎn)時間 帶權(quán)周 轉(zhuǎn)時間 A 0 1 0 1 1 1 B 1 100 1 101 100 1 C 2 1 101 102 100 100 D 3 100 102 202 199 1. 99 第三章 處理機調(diào)度與死鎖 從表上可以看出，其中短作業(yè) C的帶權(quán)周轉(zhuǎn)時間競高達100，這是不能容忍的；而長作業(yè) D的帶權(quán)周轉(zhuǎn)時間僅為 。據(jù)此可知， FCFS調(diào)度算法 有利于 CPU繁忙型的作業(yè) ，而不利于 I/O繁忙型的作業(yè) (進程 ). 第三章 處理機調(diào)度與死鎖 在此，我們通過一個例子來說明采用 FCFS調(diào)度算法時的調(diào)度性能。圖 34(a)示出有五個進程 A、 B、 C、 D、 E，它們到達的時間分別是 0、 3和 4，所要求的服務(wù)時間分別是 2和 4，其完成時間分別是 1 14和 18。從每個進程的完成時間中減去其到達時間，即得到其周轉(zhuǎn)時間，進而可以算出每個進程的帶權(quán)周轉(zhuǎn)時間。 第三章 處理機調(diào)度與死鎖 圖 34 FCFS和 SJF調(diào)度算法的性能 進程名 A B C D E 平 均 到達時間 0 1 2 3 4 作業(yè) 情況 調(diào)度 算法 服務(wù)時間 4 3 5 2 4 完成時間 4 7 12 14 18 周轉(zhuǎn)時間 4 6 10 11 14 9 FC FS (a ) 帶權(quán)周轉(zhuǎn)時間 1 2 2 5. 5 3. 5 2. 8 完成時間 4 9 18 6 13 周轉(zhuǎn)時間 4 8 16 3 9 8 SJF (b) 帶權(quán)周轉(zhuǎn)時間 1 2. 67 3. 1 1. 5 2. 25 2. 1 第三章 處理機調(diào)度與死鎖 2．短作業(yè) (進程 )優(yōu)先調(diào)度算法 短作業(yè) (進程 )優(yōu)先調(diào)度算法 SJ(P)F（ Shortest job first ） ，是指對短作業(yè)或短進程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進程調(diào)度。短作業(yè)優(yōu)先 (SJF)的調(diào)度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進程優(yōu)先 (SPF)調(diào)度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時再重新調(diào)度。 和 FCFS調(diào)度算法進行比較 第三章 處理機調(diào)度與死鎖 SJ(P)F調(diào)度算法缺點： (1) 該算法對長作業(yè)不利 ， 可能出現(xiàn)饑餓現(xiàn)象 (2) 因而不能保證緊迫性作業(yè) (進程 )會被及時處理 。 (3) 不一定能真正做到短作業(yè)優(yōu)先調(diào)度 。 第三章 處理機調(diào)度與死鎖 作業(yè) 提交時間 執(zhí)行時間 開始時間 完成時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 1 2 3 4 平均周轉(zhuǎn)時間 t = 平均帶權(quán)周轉(zhuǎn)時間 w = FCFS、 SJF算法填表（單位：小時，并以十進制計） 第三章 處理機調(diào)度與死鎖 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 1． 優(yōu)先權(quán)調(diào)度算法的類型 ? 為了照顧緊迫型作業(yè) /進程，使之在進入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先 (FPF、 HPF=highest priority first )調(diào)度算法。 ? 作為作業(yè)調(diào)度算法（ 批處理 ） ? 作為進程調(diào)度算法（ 分時、實時 ） ? 用于作業(yè)調(diào)度時，系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。 ? 用于進程調(diào)度時，把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程。 第三章 處理機調(diào)度與死鎖 ? 作為進程調(diào)度算法 1) 非搶占式優(yōu)先權(quán)算法 在這種方式下，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程后，該進程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一優(yōu)先權(quán)最高的進程。 主要用于 批處理系統(tǒng)進程調(diào)度 中；也可用于某些對實時性要求不嚴的實時系統(tǒng)中。 第三章 處理機調(diào)度與死鎖 2) 搶占式優(yōu)先權(quán)調(diào)度算法 系統(tǒng)把處理機分配給優(yōu)先權(quán)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進程，進程調(diào)度程序就 立即停止當前進程 (原優(yōu)先權(quán)最高的進程 )的執(zhí)行，重新將處理機分配給新到的優(yōu)先權(quán)最高的進程。 這種搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴格的 實時 系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。 第三章 處理機調(diào)度與死鎖 2． 優(yōu)先權(quán)的類型 如何確定 ？ 1) 靜態(tài)優(yōu)先權(quán) ? 作業(yè)的優(yōu)先級確定原則 ? 作業(yè)的緊急程度 ? 作業(yè)類型 ? 作業(yè)要求資源情況 第三章 處理機調(diào)度與死鎖 ? 進程的優(yōu)先級確定原則 ? 按進程的類型賦予不同的優(yōu)先級 ? 用戶進程類型： I/O 忙， CPU忙， I/O與 CPU 均衡 ? 系統(tǒng)進程類型：調(diào)度進程， I/O 進程，中斷處理，存儲各類等。 ? 進程對資源的要求 ? 用戶要求 ? 將作業(yè)的靜態(tài)優(yōu)先級作為它所屬進程的優(yōu)先級。 靜態(tài)優(yōu)先權(quán) 特點 ：簡單易行，系統(tǒng)開銷小；不夠精確，可能出現(xiàn)優(yōu)先級低的作業(yè)或進程，長期得不到調(diào)度。 第三章 處理機調(diào)度與死鎖 2) 動態(tài)優(yōu)先權(quán) 動態(tài)優(yōu)先權(quán)是指在創(chuàng)建進程時所賦予的優(yōu)先權(quán)，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性能。 改變進程優(yōu)先級的方式： ??? 線形優(yōu)先級調(diào)度策略 新創(chuàng)建的進程按 FCFS方式排成就緒隊列，優(yōu)先級以 a的速率增加，正在執(zhí)行的進程優(yōu)先級以 b的速率下降。 ? 非線形改變優(yōu)先級規(guī)則 第三章 處理機調(diào)度與死鎖 3． 高響應(yīng)比優(yōu)先調(diào)度算法 （ HRN） 先來先服務(wù)和短作業(yè)優(yōu)先算法都有其片面性 ， 先來先服務(wù)調(diào)度算法只考慮作業(yè)的等待時間 ， 而忽視了作業(yè)的運行時間 ， 短作業(yè)優(yōu)先算法則相反 ， 只考慮了作業(yè)的運行時間 ， 而忽視了作業(yè)的等待時間 。 HRN （ Highest Responseratio Next）是 對 FCFS和 SJF方式的一種綜合平衡 。 要求服務(wù)時間要求服務(wù)時間等待時間優(yōu)先權(quán) ??第三章 處理機調(diào)度與死鎖 由于等待時間與服務(wù)時間之和就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故 響應(yīng)比 RP =優(yōu)先權(quán)。據(jù)此，又可表示為： 要求服務(wù)時間響應(yīng)時間要求服務(wù)時間要求服務(wù)時間等待時間相應(yīng)比 ???PR每當要進行調(diào)度時，系統(tǒng)計算每個作業(yè)的響應(yīng)比，選擇其中 RP最大者 投入執(zhí)行。 第三章 處理機調(diào)度與死鎖 由上式可以看出： (1) 如果作業(yè)的等待時間相同 ， 則要求服務(wù)的時間愈短 ，其優(yōu)先權(quán)愈高 ， 因而該算法有利于短作業(yè) 。 (2) 當要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實現(xiàn)的是先來先服務(wù)。 (3) 對于長作業(yè) ， 作業(yè)的優(yōu)先級可以隨等待時間的增加而提高 ， 當其等待時間足夠長時 ， 其優(yōu)先級便可升到很高 ，從而也可獲得處理機 。 ?長短作業(yè)都得到照顧，但是增加系統(tǒng)開銷。 第三章 處理機調(diào)度與死鎖 ?這樣算法從 理論 上講是比較完備的，但作業(yè)調(diào)度程序要統(tǒng)計作業(yè)的等待時間，使用用戶的估計的運行時間，并要作浮點運算（這是系統(tǒng)程序最忌諱的）浪費大量的計算時間，這是系統(tǒng)程序所不允許的。 第三章 處理機調(diào)度與死鎖 基于時間片的輪轉(zhuǎn)調(diào)度算法 1． 時間片輪轉(zhuǎn)法 1) 基本原理 將 CPU 的處理時間分成固定大小的時間片，系統(tǒng)將所有就緒進程按先來先服務(wù)的原則排成隊列。每次調(diào)度時，把 CPU分配給隊首進程，令其執(zhí)行一個時間片，時間片用完后，若進程未結(jié)束，則重新排入就緒隊列尾部。 ?? 2）時間片的劃分 簡單循環(huán)輪轉(zhuǎn)調(diào)度 時間片 Q=R/Nmax R：響應(yīng)時間 Nmax：最大進程數(shù) 可變時間片輪轉(zhuǎn)調(diào)度 時間片 Q=R/N R：響應(yīng)時間 N：實際進程數(shù) 第三章 處理機調(diào)度與死鎖 2) 時間片大小的確定 時間片很小 ：將有利于短作業(yè) ， 會頻繁地發(fā)生中斷 、 進程上下文的切換 ， 從而增加系統(tǒng)的開銷； 時間片太長 ， 使得每個進程都能在一個時間片內(nèi)完成 ， 時間片輪轉(zhuǎn)算法便退化為 FCFS算法 ， 無法滿足交互式用戶的需求 。 若取時間片略大于一次典型的交互所需要的時間 ， 這樣可使大多數(shù)進程在一個時間片內(nèi)完成 。 圖 35示出了時間片分別為 q=1和 q=4時， A、 B、 C、 D、 E五個進程的運行情況，而圖 36為 q=1和 q=4時各進程的平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間。圖中的 RR(Round Robin)表示輪轉(zhuǎn)調(diào)度算法。 第三章 處理機調(diào)度與死鎖 圖 35 q=1和 q=4時的進程運行情況 ABCDEABCDEABCEACE( a ) q ＝ 1( b) q ＝ 41 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17tA、 B、 C、 D、 E？ A:4 B:3 C:4 D:2 E:4 第三章 處理機調(diào)度與死鎖 圖 36 q=1和 q=4時進程的周轉(zhuǎn)時間 進程名 A B C D E 平均 到達時間 0 1 2 3 4 作業(yè) 情況 時 間 片 服務(wù)時間 4 3 4 2 4 完成時間 15 12 16 9 17 周轉(zhuǎn)時間 15 11 14 6 13 1 1. 8 RR q =1 帶權(quán)周轉(zhuǎn)時間 3. 75 3. 67 3. 5 3 3. 33 3. 46 完成時間 4 7 11 13 17 周轉(zhuǎn)時間 4 6 9 10 13 8. 4 RR q =4 帶權(quán)周轉(zhuǎn)時間 1 2 2. 25 5 3. 33 2. 5 第三章 處理機調(diào)度與死鎖 2． 多級反饋隊列調(diào)度算法 (1) 設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。 第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進程執(zhí)行時間片的大小也各不相同， 在優(yōu)先權(quán)愈高的隊列中，為每個進程所規(guī)定的執(zhí)行時間片就愈小 。例如，第二個隊列的時間片要比第一個隊列的時間 片長一倍 ， …… ，第 i+1個隊列的時間片要比第 i個隊列的時間片長一倍。圖 37是多級反饋隊列算法的示意。 第三章 處理機調(diào)度與死鎖 圖 37 多級反饋隊列調(diào)度算法 就緒隊列 1就緒隊列 2就緒隊列 3就緒隊列 nS1S2S3至C P U至C P U至C P U至C P U( 時間片： S1＜ S2＜ S3)第三章 處理機調(diào)度與死鎖 ?? 多級反饋輪轉(zhuǎn)法 ?設(shè)置多個就緒隊列 ,每個隊列賦予不同地優(yōu)先級。隊列按 FCFS原則排列。 ?各隊列時間片不同。 ?當一個新進程進入內(nèi)存后，首先放在第一隊列尾，按FCFS原則調(diào)度；如果該時間片內(nèi)未結(jié)束，轉(zhuǎn)入第二隊列尾；直到最后的第 N隊列，在第 N隊列中便采取按時間片輪轉(zhuǎn)的方式執(zhí)行（不在轉(zhuǎn)下一個隊列了，因為沒有了）。 ?僅當?shù)?i隊列空閑時，才調(diào)度第 i+1隊列。如有新進程進入優(yōu)先級較高的隊列，則剝奪 CPU執(zhí)行新進程，舊進程放入原隊列尾 第三章 處理機調(diào)度與死鎖 3．多級反饋隊列調(diào)度 算法性能 ??? 終端型用戶：在第一隊列中完成，作業(yè)短，交互型。 ??? 短批處理用戶：周轉(zhuǎn)時間較短，通常三個隊列即可完成。 ??? 長批處理作業(yè)用戶：依次在前 N1個隊列中執(zhí)行，在第 N個隊列中按輪轉(zhuǎn)方式運行。 第三章 處理機調(diào)度與死鎖 思考：如下調(diào)度用的進程狀態(tài)變遷圖，調(diào)度算法