【正文】 非搶占式 ，另一種是 可搶占式 。前者是此進(jìn)程占用處理器后一直運(yùn)行到結(jié)束，除非本身主動(dòng)讓出處理器，后者則是嚴(yán)格保證任何時(shí)刻總是讓優(yōu)先數(shù)最高的進(jìn)程在處理器上運(yùn)行。 ?進(jìn)程的切換 進(jìn)程調(diào)度將從就緒隊(duì)列中另選一個(gè)進(jìn)程占用處理器，使一個(gè)進(jìn)程讓出處理器，由另一個(gè)進(jìn)程占用處理器的過(guò)程稱 進(jìn)程切換。 若有一個(gè)進(jìn)程從運(yùn)行態(tài)變成等待態(tài)，或完成工作后就撤消，則必定會(huì)發(fā)生進(jìn)程切換。若一個(gè)進(jìn)程從運(yùn)行態(tài)或等待態(tài)變成就緒態(tài)，則不一定發(fā)生進(jìn)程切換。 ? 進(jìn)程的優(yōu)先級(jí)確定原則 ? 按進(jìn)程的類型賦予不同的優(yōu)先級(jí) ? 用戶進(jìn)程類型： I/O 忙， CPU忙， I/O與 CPU 均衡 小 ? 系統(tǒng)進(jìn)程類型：調(diào)度進(jìn)程， I/O 進(jìn)程，中斷處理，存儲(chǔ)各類等 大 ? 進(jìn)程對(duì)資源的要求 少的大 ? 用戶要求 緊急大，付費(fèi)多的大 ? 將作業(yè)的靜態(tài)優(yōu)先級(jí)作為它所屬進(jìn)程的優(yōu)先級(jí)。 靜態(tài)優(yōu)先權(quán) 特點(diǎn) ：簡(jiǎn)單易行，系統(tǒng)開銷小；不夠精確，可能出現(xiàn)優(yōu)先級(jí)低的作業(yè)或進(jìn)程，長(zhǎng)期得不到調(diào)度。 ?時(shí)間片輪轉(zhuǎn)法 1) 基本原理 將 CPU 的處理時(shí)間分成固定大小的時(shí)間片，系統(tǒng)將所有就緒進(jìn)程按 先來(lái)先服務(wù) 的原則排成隊(duì)列。每次調(diào)度時(shí)，把 CPU分配給隊(duì)首進(jìn)程，令其執(zhí)行一個(gè)時(shí)間片，時(shí)間片用完后，若進(jìn)程未結(jié)束，則重新排入就緒隊(duì)列尾部。 ?? 2）時(shí)間片的劃分 簡(jiǎn)單循環(huán)輪轉(zhuǎn)調(diào)度 時(shí)間片 Q=R/Nmax R：響應(yīng)時(shí)間 Nmax：最大進(jìn)程數(shù) 可變時(shí)間片輪轉(zhuǎn)調(diào)度 時(shí)間片 Q=R/N R：響應(yīng)時(shí)間 N：實(shí)際進(jìn)程數(shù) 2) 時(shí)間片大小的確定 時(shí)間片很小 ：將有利于短作業(yè) ， 會(huì)頻繁地發(fā)生中斷 、 進(jìn)程上下文的切換 ， 從而增加系統(tǒng)的開銷； 時(shí)間片太長(zhǎng) ， 使得每個(gè)進(jìn)程都能在一個(gè)時(shí)間片內(nèi)完成 ， 時(shí)間片輪轉(zhuǎn)算法便退化為 FCFS算法 ， 無(wú)法滿足交互式用戶的需求 。 若取時(shí)間片略大于一次典型的交互所需要的時(shí)間 ， 這樣可使大多數(shù)進(jìn)程在一個(gè)時(shí)間片內(nèi)完成 。 下圖 1時(shí)間片分別為 q=1和 q=4時(shí)， A、 B、 C、 D、E五個(gè)進(jìn)程的運(yùn)行情況，而圖 2為 q=1和 q=4時(shí)各進(jìn)程的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。圖中的 RR(Round Robin)表示輪轉(zhuǎn)調(diào)度算法。 A、 B、 C、 D、 E分別在 0、 4時(shí)刻到達(dá)，分別需要 4個(gè)單位時(shí)間。 圖 1 q=1和 q=4時(shí)的進(jìn)程運(yùn)行情況 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 A B C D E 圖 2 q=1和 q=4時(shí)進(jìn)程的周轉(zhuǎn)時(shí)間 進(jìn)程名 A B C D E 平均 到達(dá)時(shí)間 0 1 2 3 4 作業(yè) 情況 時(shí) 間 片 服務(wù)時(shí)間 4 3 4 2 4 完成時(shí)間 15 12 16 9 17 周轉(zhuǎn)時(shí)間 15 11 14 6 13 1 1. 8 RR q =1 帶權(quán)周轉(zhuǎn)時(shí)間 3. 75 3. 67 3. 5 3 3. 33 3. 46 完成時(shí)間 4 7 11 13 17 周轉(zhuǎn)時(shí)間 4 6 9 10 13 8. 4 RR q =4 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 2. 25 5 3. 33 2. 5 ?時(shí)間片輪轉(zhuǎn)調(diào)度法 把規(guī)定進(jìn)程一次使用處理器的最長(zhǎng)時(shí)間稱為 時(shí)間片 。時(shí)間片輪轉(zhuǎn)調(diào)度算法讓就緒進(jìn)程按就緒的先后次序排成隊(duì)列，每次總選擇該隊(duì)列中第一個(gè)進(jìn)程占用處理器，但規(guī)定只能使用一個(gè)時(shí)間片，如該進(jìn)程尚未完成，則排入隊(duì)尾，等待下一個(gè)供它使用的時(shí)間片。各個(gè)進(jìn)程就這樣輪轉(zhuǎn)運(yùn)行。時(shí)間片輪轉(zhuǎn)算法經(jīng)常用于分時(shí)操作系統(tǒng)中。 ? 分級(jí)調(diào)度 （ 多級(jí)反饋隊(duì)列調(diào)度 ） 算法 (1) 設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。 第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同， 在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小 。例如，第二個(gè)隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間 片長(zhǎng)一倍 ， …… ，第 i+1個(gè)隊(duì)列的時(shí)間片要比第 i個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍。圖 3是多級(jí)反饋隊(duì)列算法的示意。 圖 多級(jí)反饋隊(duì)列調(diào)度算法 就緒隊(duì)列 1就緒隊(duì)列 2就緒隊(duì)列 3就緒隊(duì)列 nS1S2S3至C P U至C P U至C P U至C P U( 時(shí)間片： S1＜ S2＜ S3)優(yōu)先級(jí)：隊(duì)列 1隊(duì)列 2隊(duì)列 3… 隊(duì)列 n Si=2Si1 時(shí)間片到 時(shí)間片到 時(shí)間片到 時(shí)間片到 ?? 多級(jí)反饋輪轉(zhuǎn)法 ?設(shè)置多個(gè)就緒隊(duì)列 ,每個(gè)隊(duì)列賦予不同地優(yōu)先級(jí)。隊(duì)列按 FCFS原則排列。 ?各隊(duì)列時(shí)間片不同。 ?當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先放在第一隊(duì)列尾，按FCFS原則調(diào)度；如果該時(shí)間片內(nèi)未結(jié)束，轉(zhuǎn)入第二隊(duì)列尾；直到最后的第 N隊(duì)列，在第 N隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式執(zhí)行（不在轉(zhuǎn)下一個(gè)隊(duì)列了，因?yàn)樵诖岁?duì)列都執(zhí)行完了）。 ?僅當(dāng)?shù)?i隊(duì)列空閑時(shí)，才調(diào)度第 i+1隊(duì)列。如有新進(jìn)程進(jìn)入優(yōu)先級(jí)較高的隊(duì)列，則剝奪 CPU執(zhí)行新進(jìn)程，舊進(jìn)程放入原隊(duì)列尾 ? 多級(jí)反饋隊(duì)列調(diào)度 算法性能 ??? 終端型用戶：在第一隊(duì)列中完成，作業(yè)短，交互型。 ??? 短批處理用戶：周轉(zhuǎn)時(shí)間較短，通常三個(gè)隊(duì)列即可完成。 ??? 長(zhǎng)批處理作業(yè)用戶：依次在前 N1個(gè)隊(duì)列中執(zhí)行，在第 N個(gè)隊(duì)列中按輪轉(zhuǎn)方式運(yùn)行。 思考：如下調(diào)度用的進(jìn)程狀態(tài)變遷圖，有幾個(gè)隊(duì)列？調(diào)度算法和調(diào)度效果如何？ 運(yùn)行 低優(yōu)先就緒 高優(yōu)先就緒 等待 首先選擇100ms 其次選擇500ms 請(qǐng)求 I/O I/O完成 超時(shí)間片 隊(duì)列結(jié)構(gòu) ? I/O等待隊(duì)列 —— 一個(gè)進(jìn)程如果請(qǐng)求 I/O，則進(jìn)入 I/O等待隊(duì)列。 ?低優(yōu)先就緒隊(duì) —— 一個(gè)進(jìn)程如果在運(yùn)行中超過(guò)了它的時(shí)間量就進(jìn)入低優(yōu)先就緒隊(duì)列。 ? 高優(yōu)先就緒隊(duì)列 —— 當(dāng)進(jìn)程從等待狀態(tài)變?yōu)榫途w狀態(tài)時(shí)則進(jìn)入高優(yōu)先就緒隊(duì)列。 進(jìn)程調(diào)度算法 優(yōu)先調(diào)度與時(shí)間片調(diào)度相結(jié)合的調(diào)度策略： (1) 當(dāng) CPU空閑時(shí)，若高優(yōu)先就緒隊(duì)列非空，則從高優(yōu)先就緒隊(duì)列中選擇一個(gè)進(jìn)程運(yùn)行，分配時(shí)間片為 100ms (2) 當(dāng) CPU空閑時(shí)，若高優(yōu)先就緒隊(duì)列為空，則從低優(yōu)先就緒隊(duì)列中選擇一個(gè)進(jìn)程運(yùn)行，分配時(shí)間片為 500ms 調(diào)度效果 優(yōu)先照顧了 I∕O量大的進(jìn)程； 適當(dāng)照顧了計(jì)算量大的進(jìn)程。 UNIX系統(tǒng)的進(jìn)程調(diào)度算法 ?動(dòng)態(tài)優(yōu)先數(shù)調(diào)度算法 ?設(shè)置法 ?計(jì)算法 ? 進(jìn)程調(diào)度程序 Switch 思考 ?若在操作系統(tǒng)的就緒進(jìn)程隊(duì)列中等待運(yùn)行的共有三個(gè)進(jìn)程 P P P3，已知它們各自的運(yùn)行時(shí)間為 a、 b、 c，且滿足關(guān)系 a b c。請(qǐng)證明采用最短作業(yè)優(yōu)先調(diào)度算法能夠獲得最小平均周轉(zhuǎn)時(shí)間。 證明： ? 短作業(yè)優(yōu)先調(diào)度，調(diào)度順序?yàn)?1， 2， 3，三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為： T1=a+(a+b)+(a+b+c) ? 若不按短作業(yè)優(yōu)先調(diào)度，采用非時(shí)間片輪轉(zhuǎn)法，不失一般性，假設(shè)調(diào)度順序?yàn)?2， 1， 3，則總周轉(zhuǎn)時(shí)間為 ? T2= ? 由此可見(jiàn)，非時(shí)間片輪轉(zhuǎn)法中短作業(yè)優(yōu)先調(diào)度算法可獲得最小平均周轉(zhuǎn)時(shí)間。 ? 證明： 假設(shè)進(jìn)程被調(diào)度運(yùn)行的順序?yàn)?P P P3，每個(gè)進(jìn)程的運(yùn)行時(shí)間為 T T T3。 若采用非時(shí)間片輪轉(zhuǎn)算法，則平均周轉(zhuǎn)時(shí)間的計(jì)算公式為： 平均周轉(zhuǎn)時(shí)間 ＝ （ 3T1 + 2T2 ＋ T3） / 3 = T1 + 2T2/3 + T3/3； 若采用時(shí)間片輪轉(zhuǎn)算法，設(shè)每個(gè)進(jìn)程需要 N1,N2,N3個(gè)時(shí)間片可以運(yùn)行完，則周轉(zhuǎn)時(shí)間為 : 其中 Ts為時(shí)間片大小 平均周轉(zhuǎn)時(shí)間 ＝ 顯然可見(jiàn)，采用非時(shí)間片輪轉(zhuǎn)的平均周轉(zhuǎn)時(shí)間小于采用時(shí)間片輪轉(zhuǎn)算法，在各種非時(shí)間片輪轉(zhuǎn)的線程調(diào)度算法中，保證平均周轉(zhuǎn)時(shí)間最小的條件為 T1 T 2 T3，即遵循最短作業(yè)優(yōu)先的思想調(diào)度進(jìn)程運(yùn)行。 T=【 (N1+N11+N11)+(N2+N1+N21)+(N3+N2+N1)】 Ts =5T1+3T2+T33Ts 復(fù)習(xí)題 ? 實(shí)現(xiàn)多道設(shè)程序設(shè)計(jì)的前提條件是（ ）。 A、成批處理作業(yè) B、分時(shí)多用戶 C、設(shè)置管、目態(tài) D、處理機(jī)與外設(shè)并行操作 ? 進(jìn)程有多個(gè)狀態(tài)，不會(huì)發(fā)生的狀態(tài)轉(zhuǎn)換是（ ） A、就緒態(tài)轉(zhuǎn)換為運(yùn)行態(tài) B、運(yùn)行態(tài)轉(zhuǎn)換為就緒態(tài) C、就緒態(tài)轉(zhuǎn)換為等待態(tài) D、等待態(tài)轉(zhuǎn)換為就緒態(tài) ? 進(jìn)程調(diào)度算法有多種，不是進(jìn)程調(diào)度算法的算法是（ ）。 A、先來(lái)先服務(wù)調(diào)度算法 B、最高響應(yīng)比優(yōu)先調(diào)度算法 C、優(yōu)先數(shù)調(diào)度算法 D、時(shí)間片輪轉(zhuǎn)調(diào)度算法 ? 多項(xiàng)選擇：進(jìn)程由（ ）組成。 A、程序狀態(tài)字 B、程序模塊 C、就緒隊(duì)列 D、數(shù)據(jù)集合 E、進(jìn)程控制塊 ? 進(jìn)程所請(qǐng)求的一次打印輸出結(jié)束后，將使進(jìn)程狀態(tài)從（ ）。 A、運(yùn)行態(tài)變?yōu)榫途w態(tài) B、運(yùn)行態(tài)變?yōu)榈却龖B(tài) C、就緒態(tài)變?yōu)檫\(yùn)行態(tài) D、等待態(tài)變?yōu)榫途w態(tài) ? 多項(xiàng)選擇：引入多道程序設(shè)計(jì)的主要目的在于（ ） A、提高實(shí)時(shí)響應(yīng)速度 B、充分利用處理機(jī)、減少處理機(jī)的空閑時(shí)間。 C、有利于代碼共享 D、充分利用外圍設(shè)備 E、減少存儲(chǔ)器碎片 ?進(jìn)程存在的標(biāo)志是 __________，從操作系統(tǒng)的角度來(lái)看，可將進(jìn)程分為______________、 _____________兩大類。 ?進(jìn)程在用完一個(gè)器時(shí)間片后被強(qiáng)迫進(jìn)入的等待狀態(tài)屬于 _________。 ?簡(jiǎn)答題：進(jìn)程調(diào)度中“可搶占”和“非搶占”兩種方式，哪一種系統(tǒng)的開銷更大？為什么？ ?簡(jiǎn)答題：簡(jiǎn)述進(jìn)程調(diào)度的功能。 ?1簡(jiǎn)答題：引起進(jìn)程調(diào)度的原因很多，試指出這些原因。 ? D C B BD D BD ? 進(jìn)程控制塊 系統(tǒng)進(jìn)程 用戶進(jìn)程 就緒態(tài) ? 這兩種方式下，“可搶占”方式的系統(tǒng)開銷更大。因?yàn)榇藭r(shí)系統(tǒng)必須監(jiān)視每一個(gè)進(jìn)入就緒態(tài)進(jìn)程的優(yōu)先數(shù)，當(dāng)優(yōu)先數(shù)高于當(dāng)前運(yùn)行態(tài)進(jìn)程時(shí)就產(chǎn)生中斷把更高優(yōu)先數(shù)的進(jìn)程調(diào)入運(yùn)行，這種情況勢(shì)必增加進(jìn)程調(diào)度的次數(shù)和保護(hù)現(xiàn)場(chǎng)的開銷。 ? 在多道程序設(shè)計(jì)系統(tǒng)中，同時(shí)有多個(gè)進(jìn)程處于就緒狀態(tài)，它們都要求占用處理器運(yùn)行。進(jìn)程調(diào)度的功能就是們競(jìng)爭(zhēng)處理器問(wèn)題的，它按照某種調(diào)度算法從就緒隊(duì)列中選擇一個(gè)進(jìn)程，讓它占用處理器。 ? 1引起進(jìn)程調(diào)度的原因包括：（ 1）一個(gè)進(jìn)程從運(yùn)行狀態(tài)變成了等待狀態(tài)。（ 2）一個(gè)進(jìn)程從運(yùn)行狀態(tài)變成了就緒狀態(tài)。（ 3）一個(gè)進(jìn)程從等待狀態(tài)變成了就緒狀態(tài)（ 4）一個(gè)進(jìn)程完成工作后被撤消。