【正文】 。清除 runrun標記。 其次， 按計算優(yōu)先數(shù)的公式從內(nèi)存就緒隊列中尋找優(yōu)先級最高的進程作為上行進程。 5． 5． 4 調度的實現(xiàn) UNIX 系統(tǒng)的進程調度是由 swtch過程實現(xiàn)的， swtch過程是進程 0的一部分。 5． 5． 3 優(yōu)先數(shù)計算 p_nice是系統(tǒng)允許用戶使用 nice系統(tǒng)調用影響進程優(yōu)先數(shù)的偏移值，范圍在 0~40之間。此外，秒中斷時對p_CPU執(zhí)行除以 2的衰減操作。優(yōu)先數(shù)基于進程類型和運行歷史，計算公式如下： N Z E R On icepP U S E RC P Upp r ip ???? _2__其中， PUSER和 NZERO分別取常數(shù) 25和 20，稱它們?yōu)榛居脩魞?yōu)先數(shù)的閾值， p_CPU為進程最近一次使用 CPU的時間。 5． 5． 3 優(yōu)先數(shù)計算 傳統(tǒng)的 UNIX System V采用動態(tài)優(yōu)先數(shù)調度策略，優(yōu)先數(shù)越大優(yōu)先級越低。若 wakeup，setrun以及 setpri（設置優(yōu)先級）命令發(fā)現(xiàn)某進程的優(yōu)先級高于現(xiàn)行進程時，置 runrun為 1。 5． 5． 1 調度時機 UNIX System V在以下 5種情況之一發(fā)生時進行進程調度： ?現(xiàn)行進程自己調用 sleep或 wait等進入睡眠狀態(tài)時； ?現(xiàn)行進程調用 exit自我終止時； ?現(xiàn)行進程的時間片到期且優(yōu)先級低于其它就緒進程時； ?現(xiàn)行進程在完成中斷和陷入處理后返回用戶態(tài)時，它的優(yōu)先級已低于其它就緒進程或者調度標記被置位； ?現(xiàn)行進程從系統(tǒng)調用執(zhí)行結束后返回用戶態(tài)時，它的優(yōu)先級已低于其它就緒進程或者調度標記被置位。 5． 4． 7 多級反饋隊列調度算法 多級反饋隊列調度算法如下圖所示： … 第一級隊列 （ FIFO） 完成 … 第二級隊列 （ FIFO） 完成 … 第 n級隊列 （ FIFO） 完成 ：： 5． 5 實例分析： UNIX進程調度 UNIX System V的進程調度涉及調度時機 、 調度標記設置 、 優(yōu)先數(shù)計算 、 調度的實現(xiàn)等 。 如隊列 1的優(yōu)先級最高 ， 然后逐級降低 。 5． 4． 7 多級反饋隊列調度算法 多級反饋隊列 （ Round Robin with Multiple Feedback， RRMF） 調度算法是時間片輪轉算法和優(yōu)先級調度算法的綜合和發(fā)展 。 在多級隊列調度算法中 ， 根據(jù)作業(yè)或進程的性質或類型的不同 ， 將就緒隊列再分成若干個子隊列 ， 每個作業(yè)固定歸入一個隊列 ， 例如 ， 系統(tǒng)進程 、 用戶交互進程 、批處理進程等不同隊列 。 在時刻 0，由于只有作業(yè) 1，因此調度 作業(yè) 1投入運行，作業(yè) 1運行到時刻 6結束，在時刻 6時進行調度； 在時刻 6，計算各作業(yè)的響應比為： 作業(yè) 2的響應比： R2=1+（ 61） /4= 作業(yè) 3的響應比： R3=1+（ 62） /4=2 作業(yè) 4的響應比： R4=1+（ 63） /1=4 作業(yè) 5的響應比： R5=1+（ 64） /3= 選擇 作業(yè) 4投入運行，作業(yè) 4運行到時刻 7時結束，在時刻 7時進行調度； 5． 4 ． 5 最高響應比優(yōu)先調度算法 在時刻 7，計算各作業(yè)的響應比為： 作業(yè) 2的響應比： R2=1+（ 71） /4= 作業(yè) 3的響應比： R3=1+（ 72） /4= 作業(yè) 5的響應比： R5=1+（ 74） /3=2 選擇 作業(yè) 2投入運行，作業(yè) 2運行到時刻 11時結束，在時刻 11時進行調度； 作業(yè) 3的響應比： R3=1+（ 112） /4= 作業(yè) 5的響應比： R5=1+（ 114） /3= 選擇 作業(yè) 5投入運行，作業(yè) 5運行到時刻 14時結束，在時刻 14時進行調度； 在時刻 14，只有作業(yè) 3等待運行，因此五道作業(yè)的調度順序是 1， 4， 2， 5， 3。 5． 4 ． 5 最高響應比優(yōu)先調度算法 【 例 54】 假設有五道作業(yè)，它們的進入時間、運行時間由下表給出： 系統(tǒng)采用 HRN調度算法，試計算采用該調度算法時的平均周轉時間和平均帶權周轉時間。 5． 4 ． 5 最高響應比優(yōu)先調度算法 ?算法思想： 在當前進程完成或被阻塞時，選擇 Rp值最大的就緒進程投入運行。 HRN調度算法同時考慮每個作業(yè)的等待時間和估計的運行時間。 5． 4 ． 4 高優(yōu)先權優(yōu)先調度算法 解： 采用靜態(tài) FPF調度算法，調度順序是 1， 3， 5， 2， 4。 ?優(yōu)先數(shù)與優(yōu)先級的關系 ； 在 UNIX和許多其他的系統(tǒng)中，優(yōu)先級數(shù)值越大，表示的進程優(yōu)先權越低；而在某些系統(tǒng)中的用法則剛好相反，如 Windows，大數(shù)值表示高優(yōu)先級。但由于靜態(tài)優(yōu)先權一旦確定之后，直到運行結束為止始終保持不變，從而使優(yōu)先級低的進程長時間得不到調度。 ?優(yōu)先權確定方法： ?靜態(tài)優(yōu)先權： 靜態(tài)優(yōu)先權是在創(chuàng)建進程時確定的，在整個運行期間不再改變。 5． 4 ． 3 時間片輪轉調度算法 時刻 運行進程 排隊進程 時刻 運行進程 排隊進程 0～ 1 A 9～ 10 D AEC 1～ 2 B A 10～ 11 A ECD 2～ 3 A CB 11～ 12 E CD 3～ 4 C BDA 12～ 13 C DE 4～ 5 B DAEC 13～ 14 D EC 5～ 6 D AEC 14～ 15 E C 6～ 7 A ECD 15～ 16 C 7～ 8 E CDA 16～ 17 C 8～ 9 C DAE 解：當時間片 q=1時，列出下表，找出運行序列： 5． 4 ． 3 時間片輪轉調度算法 根據(jù)上表，畫出調度圖如下圖所示： A B C D E 0 1 2 3 4 5 6 7 8 9 11 10 12 13 14 15 16 17 5． 4 ． 3 時間片輪轉調度算法 從上圖得出的五道作業(yè)的完成時間和周轉時間如下表所示： 作業(yè)號 進入時間 運行時間 完成時間 周轉時間 A 0 4 11 11 B 1 2 5 4 C 2 5 17 15 D 3 3 14 11 E 4 3 15 11 平均周轉時間 T＝（ 11+4+15+11+11） / 5= 平均帶權周轉時間