【正文】 42（ ） 1 B 30（ ） 1 2 C 24（ ） D 24（ ） E 12（ ） 6 入輸入井時(shí)間 (小時(shí) ) 平均周轉(zhuǎn)時(shí)間 t = (+1+++)/5=(小時(shí) ) 平均帶權(quán)周轉(zhuǎn)時(shí)間 w = (1+2+++6)/5=(小時(shí) ) 比 先來(lái)先服務(wù)算法調(diào)度 ,t,w都下降了 . 短作業(yè)優(yōu)先調(diào)度算法的優(yōu)缺點(diǎn)： 優(yōu)點(diǎn) :提高了系統(tǒng)的 吞吐能力 . 缺點(diǎn)：不斷地接受計(jì)算時(shí)間短的作業(yè) ,會(huì)使計(jì)算時(shí)間長(zhǎng)的作業(yè)長(zhǎng)期等待 ,長(zhǎng)作業(yè)用戶(hù)不滿(mǎn)意 . 每一次計(jì)算每個(gè)作業(yè)的響應(yīng)比 ,從滿(mǎn)足資源的作業(yè)中挑選響應(yīng)比高者優(yōu)先調(diào)度 . 注 :該算法是先來(lái)先服務(wù)調(diào)度算法和短作業(yè)優(yōu)先調(diào)度算法的折衷方案 . 響應(yīng)比 =———— 等待時(shí)間 計(jì)算時(shí)間 例子 :單道程序系統(tǒng)中 ,三個(gè)作業(yè) A,B,C達(dá)到輸入井的時(shí)間及要求的運(yùn)行時(shí)間 ,如下表 : 作業(yè) 進(jìn)入輸入井的 時(shí)間 要求運(yùn)行時(shí)間（小時(shí)） 不考慮資源要求 A 8:50 B 9:00 C 9:30 1 從達(dá)到的時(shí)間 9:30開(kāi)始 ,計(jì)算 A,B,C的響應(yīng)比 : A,B,C等待的時(shí)間分別 :40分 (9:308:50),30分 (9:309:00),0分 : 第一遍 A的響應(yīng)比 =40/90分 =4/9 B的響應(yīng)比 =30/24分 =5/4 C的響應(yīng)比 =0/60分 =0 應(yīng)該調(diào)度 B:周轉(zhuǎn)時(shí)間 t=(9:309:00=30分 = )+=(小時(shí) ) 帶權(quán)周轉(zhuǎn)時(shí)間 w=(小時(shí) ) 第二遍 :B結(jié)束 .開(kāi)始時(shí)間 :9:54小時(shí) (9:30+24分 (*6=24分 )) A的響應(yīng)比 =64/90分 =32/45 (9:548:50=64分 ) C的響應(yīng)比 =24/60分 =2/5(9:549:30=24分 ) 應(yīng)該調(diào)度 A:周轉(zhuǎn)時(shí)間 t=(9:548:50)+=(小時(shí) ) 帶權(quán)周轉(zhuǎn)時(shí)間 w=(小時(shí) ) 最后調(diào)度 C:開(kāi)始時(shí)間 11:24小時(shí) (9:54+ ) 周轉(zhuǎn)時(shí)間 t=(11:249:30= )+1=(小時(shí) ) 帶權(quán)周轉(zhuǎn)時(shí)間 w=(小時(shí) ) 平均周轉(zhuǎn)時(shí)間 :T=(++)/3=(小時(shí) ) 平均帶權(quán)周轉(zhuǎn)時(shí)間 :w=(++)/3=(小時(shí) ) 優(yōu)缺點(diǎn) : 優(yōu)點(diǎn) :既照顧了作業(yè)到來(lái)的先后次序 ,又考慮了要求系統(tǒng)服務(wù)時(shí)間的長(zhǎng)短 . 缺點(diǎn) :計(jì)算復(fù)雜 ,每調(diào)度一次 ,都要計(jì)算每個(gè)作業(yè)的響應(yīng)比 . 算法綜合考慮的因素 （ 作業(yè)等待時(shí)間 、 運(yùn)行時(shí)間 、 緩急程度 ， 系統(tǒng)資源使用等 ） ， 給每個(gè)作業(yè)設(shè)置一個(gè)優(yōu)先數(shù) ， 調(diào)度程序總是選擇一個(gè)優(yōu)先數(shù)最大 （ 或者最小 ） 的作業(yè)調(diào)入 （ 系統(tǒng) ） 內(nèi)存 。 輸出量以行計(jì) . 算法優(yōu)缺點(diǎn) : 優(yōu)點(diǎn) :保證優(yōu)先照顧運(yùn)行時(shí)間短的作業(yè) 。 依據(jù)作業(yè)對(duì)資源的要求分類(lèi) ,作業(yè)調(diào)度輪流地從不同類(lèi)的作業(yè)中去挑選作業(yè) ,盡可能地使得使用不同資源的作業(yè)同時(shí)執(zhí)行 . 優(yōu)點(diǎn) :減少作業(yè)等待同類(lèi)資源的時(shí)間 ,加快作業(yè)的執(zhí)行 . 缺點(diǎn) :算法實(shí)現(xiàn)復(fù)雜 . 2 167。 ②決定分配策略。 調(diào)度時(shí)機(jī)有如下幾種情況 : ? 正常終止 ? 系統(tǒng)服務(wù)請(qǐng)求：如：請(qǐng)求 I/O等； ? 異常終止：程序出錯(cuò)； ? 時(shí)間片到 ? 可剝奪方式下，高優(yōu)先級(jí)進(jìn)程進(jìn)入就緒隊(duì)列 ⑴ 非剝奪方式 讓正在執(zhí)行的進(jìn)程繼續(xù)執(zhí)行，直到該進(jìn)程完成或發(fā)生某事件而進(jìn)入“完成”或“阻塞”狀態(tài)時(shí)，才把處理機(jī)分配給“重要而緊迫”的進(jìn)程。 三 .調(diào)度用的進(jìn)程狀態(tài)變遷圖 例 :有一個(gè)分時(shí)系統(tǒng) 進(jìn)程狀態(tài)變遷圖如下 : 運(yùn)行 等待 高優(yōu)先就緒 低優(yōu)先就緒 超時(shí)間片 其次選擇500ms 請(qǐng)求 I/O I/O完成 首先選擇100ms 1 2 3 4 5 要求分析 :進(jìn)程的可能狀態(tài)，狀態(tài)間的變遷的原因，調(diào)度策略和調(diào)度效果。 解： (1) 發(fā)生變遷 3的原因：一個(gè)運(yùn)行的進(jìn)程要請(qǐng)求 系統(tǒng)服務(wù)。 或者：系統(tǒng)采用剝奪式調(diào)度，一個(gè)更高優(yōu)先級(jí) 的進(jìn)程進(jìn)入就緒隊(duì)列要求執(zhí)行。 (2) a. 2→ 1 :是因果變遷關(guān)系。 b. 3 → 5 ：是因果變遷關(guān)系。 c. 4 → 2 :不是因果變遷關(guān)系 。條件：高優(yōu)先就緒隊(duì) 列為空 ,低優(yōu)先就緒隊(duì)列為非空。 執(zhí)行次序： p3→p2 → p4→p1 等待時(shí)間： p1： 25＋ 12＝ 37（秒） p2： 0＋ 10＝ 10 （秒） p3： 0 （秒） p4： 10＋ 15＝ 25 （秒） 平均等待時(shí)間 ： (37＋ 10＋ 0＋ 25)/4＝ 18 （秒） 為每一個(gè)進(jìn)程規(guī)定使用 CPU的時(shí)間 ,使就緒隊(duì)列的進(jìn)程輪流地得到 CPU. 分為 :固定時(shí)間片的輪轉(zhuǎn)調(diào)度算法和可變式 時(shí)間片的輪轉(zhuǎn)調(diào)度算法。 例：考慮三個(gè)進(jìn)程 P1， P2， P3它們本次 CPC周期時(shí)值分別為 21ms。 設(shè) s＝ 4ms 則有 p1 p2 p3 p1 p2 p1 p1 p1 p1 4 0 8 15 11 17 25 21 29 30 1 2 3 5 平均等待時(shí)間 w＝ (0+4+8)/3＝ 4(ms) 平均周轉(zhuǎn)時(shí)間 T=(30+17+11)/3＝ 19(ms) 算法特征： ? 該算法是一種剝奪式的進(jìn)程調(diào)度算法，依據(jù)公平服務(wù)的原則為就緒進(jìn)程服務(wù)。 ? 時(shí)間片為一個(gè)固定值，進(jìn)程均以相等的速度向前推進(jìn)。N為進(jìn)程數(shù)目 若 s值取得足夠大 ,以至每一個(gè)進(jìn)程的 cpu周期都能在一個(gè)時(shí)間片內(nèi)完成，則輪轉(zhuǎn)算法退化成先來(lái)先服務(wù)算法。 ? 時(shí)間片 s的長(zhǎng)短與 4種因素有關(guān)： T N ：轉(zhuǎn)換時(shí)間，保證系統(tǒng)開(kāi)銷(xiāo)不大，一般在 10ms內(nèi)適中。 由系統(tǒng)設(shè)置多個(gè)就緒隊(duì)列，每個(gè)隊(duì)列按時(shí)間片輪轉(zhuǎn)算法調(diào)用 cpu。 4 UNIX進(jìn)程調(diào)度 一 .調(diào)度算法 ? UNIX系統(tǒng)采用優(yōu)先數(shù)調(diào)度算法 . 每進(jìn)程有一個(gè)優(yōu)先數(shù) p_pri ? p_pri取值范圍是－ 127～ 127， 其值越小 ， 進(jìn)程的優(yōu)先級(jí)越高 . 進(jìn)入核心狀態(tài)運(yùn)行的進(jìn)程優(yōu)先級(jí)高于進(jìn)入用戶(hù)狀態(tài)運(yùn)行的進(jìn)程優(yōu)先級(jí) . 一個(gè)進(jìn)程用完一個(gè)時(shí)間片而被剝奪 CPU,應(yīng)降低該進(jìn)程的優(yōu)先級(jí) . 進(jìn)入睡眠狀態(tài)的進(jìn)程 ,系統(tǒng)應(yīng)其等待事件的輕重緩急程度賦予它們不同的優(yōu)先級(jí) . 累計(jì)使用 CPU時(shí)間較長(zhǎng)的進(jìn)程 ,其優(yōu)先級(jí)相應(yīng)降低 . 設(shè)置法和計(jì)算法 . (1) 設(shè)置優(yōu)先數(shù)法 設(shè)置者 :sleep( )程序 . 設(shè)置原則 : 進(jìn)程進(jìn)入睡眠時(shí) ,系統(tǒng)按睡眠的原因設(shè)置優(yōu)先數(shù) . 因緊迫事件而入睡的進(jìn)程設(shè)置較小的優(yōu)先數(shù) ,一般為負(fù)數(shù) . 等待事件不會(huì)產(chǎn)生全局影響的 ,設(shè)置較大的優(yōu)先數(shù) ,一般為正數(shù) . 如 : 0＃進(jìn)程（－ 100優(yōu)先數(shù)）； ? 資源請(qǐng)求得不到滿(mǎn)足的進(jìn)程，磁盤(pán)（－ 80），打印機(jī)（－20）， … ； ? 等待塊設(shè)備 I/O完成的進(jìn)程 (－ 50)； ? 等待字符設(shè)備 I/O完成的進(jìn)程 (