【正文】 第三章 進(jìn)程和處理器管理 處理器調(diào)度概述 處理機調(diào)度的四個層次 執(zhí)行 等待 就緒 等待 就緒 完成 狀態(tài) 收容 狀態(tài) 進(jìn)程調(diào)度 交換調(diào)度 作業(yè)調(diào)度 內(nèi)存 外存 線程調(diào)度 高級調(diào)度： 作業(yè)調(diào)度 中級調(diào)度： 交換調(diào)度 低級調(diào)度： 進(jìn)程調(diào)度 線程調(diào)度 作業(yè)與進(jìn)程的關(guān)系 ? 作業(yè)可被看作是用戶向計算機提交任務(wù)的任務(wù)實體，例如一次計算、一個控制過程等。 ? 進(jìn)程則是計算機為了完成用戶任務(wù)實體而設(shè)置的執(zhí)行實體，是系統(tǒng)分配資源的基本單位。計算機要完成一個任務(wù)實體，必須要有一個以上的執(zhí)行實體。也就是說，一個作業(yè)總是由一個以上的多個進(jìn)程組成的。 ? 調(diào)度目標(biāo)： 一般來說，調(diào)度目標(biāo)主要是以下四點 (1)公平合理：對所有作業(yè)應(yīng)該是公平合理的； (2)高利用率：應(yīng)使設(shè)備有高的利用率， (3)吞吐量大：每天執(zhí)行盡可能多的作業(yè)； (4)響應(yīng)迅速：有快的響應(yīng)時間。 ? 任一調(diào)度算法要想同時滿足上述目標(biāo)是不可能的： 1）如要想吞吐量大，調(diào)度算法就應(yīng)選擇那些估計執(zhí)行時間短的作業(yè)。這對那些估計執(zhí)行時間長的作業(yè)不公平，并且可能使它們的得不到調(diào)度執(zhí)行或響應(yīng)時間很長。 2）如果考慮的因素過多，調(diào)度算法就會變得非常復(fù)雜。其結(jié)果是系統(tǒng)開銷增加，資源利用率下降。 衡量調(diào)度策略的常用指標(biāo) ? 周轉(zhuǎn)時間 ：指將一個作業(yè)提交給計算機系統(tǒng)后到該作業(yè)的結(jié)果返回給用戶所需要的時間。 ? 吞吐量 ：指在給定的時間內(nèi)，一個計算機系統(tǒng)所完成的總工作量 (作業(yè)數(shù) )。 ? 響應(yīng)時間 ：指從用戶向計算機發(fā)出一個命令到計算機把相應(yīng)的執(zhí)行結(jié)果返回給用戶所需要的時間。 ? 設(shè)備利用率 ：輸入輸出設(shè)備的使用情況，在有些要求 I／ O處理能力強 (如管理信息系統(tǒng) )的系統(tǒng)中，高的設(shè)備利用率也是一個衡量調(diào)度策略好壞的重要指標(biāo)。 – 周轉(zhuǎn)時間： 作業(yè) i的周轉(zhuǎn)時間 Ti為 Ti＝ TeiTsi 其中 Tei為作業(yè) i的完成時間； Tsi為作業(yè)的提交時間。 N個作業(yè)的平均周轉(zhuǎn)時間 T=（ T1 + T2 + … + T N） /N – 帶權(quán)周轉(zhuǎn)時間： 周轉(zhuǎn)時間 Ti可分解為兩部分，即 Ti＝ Twi+Tri 這里， Twi主要指作業(yè) i由后備狀態(tài)到執(zhí)行狀態(tài)的等待時間，它不包括作業(yè)進(jìn)入執(zhí)行狀態(tài)后的等待時間； Tri指作業(yè) i的執(zhí)行時間。 帶權(quán)周轉(zhuǎn)時間 是作業(yè)周轉(zhuǎn)時間與作業(yè)執(zhí)行時間的比： Wi＝ Ti／ Tri N個作業(yè)的平均帶權(quán)周轉(zhuǎn)時間 W＝ (W1 + W2 + … + W N)/N ? 常用作業(yè)調(diào)度算法 1 先來先服務(wù)（ First e first serve,FCFS） 方式： 執(zhí)行時間很短的作業(yè)是在那些長作業(yè)的后面到達(dá)系統(tǒng)的話，則必須等待很長時間 2 短作業(yè)優(yōu)先 (Shortest Job first， SJF)方式 選擇那些估計需要執(zhí)行時間最短的作業(yè)投入執(zhí)行，為它們創(chuàng)建進(jìn)程和分配資源。 有可能使得那些長作業(yè)永遠(yuǎn)得不到調(diào)度執(zhí)行 3 響應(yīng)比高者優(yōu)先（ Highest Responseratio Next ，HRN)方式 ? 響應(yīng)比 R＝ (W+T)／ T＝ 1+W／ T T： 為估計需要的執(zhí)行時間 W： 在后備狀態(tài)隊列中的等待時間 T+W:響應(yīng)時間 ? 作業(yè)調(diào)度時，系統(tǒng)計算每個作業(yè)的響應(yīng)比，選擇 R最大者投入執(zhí)行。 – 長作業(yè)有機會獲得調(diào)度執(zhí)行 (隨著它等待時間的增加， W／ T也就隨著增加 )。 – HRN的吞吐量小于 SJF， 由于長作業(yè)也有機會投入運行，在同一時間內(nèi)處理的作業(yè)數(shù)顯然要少于SJF法。 – 系統(tǒng)開銷增加：每次調(diào)度前要計算響應(yīng)比。 – HRN是對 FCFS方式和 SJF方式的一種綜合平衡。 時間片輪轉(zhuǎn)程序調(diào)度算法 (RR） 把 CPU劃分成若干時間片 ,并且按順序賦給就緒隊列中的每一個進(jìn)程，進(jìn)程輪流占有 CPU， 當(dāng)時間片用完時，即使進(jìn)程未執(zhí)行完畢，系統(tǒng)也剝奪該進(jìn)程的 CPU， 將該進(jìn)程排在就緒隊列末尾。同時系統(tǒng)選擇另一個進(jìn)程運行 本算法主要用于 微觀調(diào)度 ，說明怎樣并發(fā)運行，即 切換的方式 ；設(shè)計目標(biāo)是提高 資源利用率 。 其基本思路是通過 時間片輪轉(zhuǎn) ，提高進(jìn)程 并發(fā)性 和 響應(yīng)時間 特性，從而提高 資源利用率 ； 時間片長度的確定 ? 時間片長度變化的影響 – 過長－ 退化為 FCFS算法，進(jìn)程在一個時間片內(nèi)都執(zhí)行完，響應(yīng)時間長。 – 過短－ 用戶的一次請求需要多個時間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時間長。 ? 時間片長度的影響因素： – 就緒進(jìn)程的數(shù)目：數(shù)目越多，時間片越小（當(dāng)響應(yīng)時間一定時） – 系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶輸入通常在一個時間片內(nèi)能處理完，否則使響應(yīng)時間，平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間延長。 多隊列反饋調(diào)度算法 * 首先系統(tǒng)中設(shè)置多個就緒隊列 * 每個就緒隊列分配給不同時間片，優(yōu)先級高的為第一級隊列，時間片最小，隨著隊列級別的降低，時間片加大 * 各個隊列按照先進(jìn)先出調(diào)度算法 * 一個新進(jìn)程就緒后進(jìn)入第一級隊列 * 進(jìn)程由于等待而放棄 CPU后，進(jìn)入等待隊列，一旦等待的事件發(fā)生，則回到原來的就緒隊列 * 當(dāng)有一個優(yōu)先級更高的進(jìn)程就緒時，可以搶占 CPU， 被搶占進(jìn)程回到原來一級就緒隊列末尾 * 當(dāng)?shù)谝患夑犃锌諘r，就去調(diào)度第二級隊列，如此類推 * 當(dāng)時間片到后，進(jìn)程放棄 CPU， 回到下一級隊列 例題 ? 在一單道批處理系統(tǒng)中，一組作業(yè)的提交時刻和運行時間如表所示 試計算以下三種作業(yè)調(diào)度算法的平均周轉(zhuǎn)時間 T和平均帶權(quán)周轉(zhuǎn)時間 W 作業(yè) 提交時刻 運行時間 1 2 3 4 ? 先來先服務(wù) 次序 提交 運行 等待 開始 完成 周轉(zhuǎn) 帶權(quán)周轉(zhuǎn) 1 8:0 1 0 2 8:5 3 9:0 4 9:10 平均周轉(zhuǎn)時間 T=(1+1++)/4= 平均帶權(quán)周轉(zhuǎn)時間 W=(1+2++7.)/4= 短作業(yè)優(yōu)先算法 次序 提交 運行 等待 開始 完成 周轉(zhuǎn) 帶權(quán)周轉(zhuǎn) 1