【文章內(nèi)容簡介】 高于后臺進程的優(yōu)先級 . 優(yōu)點 :算法容易實現(xiàn) ,系統(tǒng)開銷小 . 缺點 :死板 .不能精確地調(diào)度進程 ,可能導(dǎo)致低優(yōu)先級的進程長期等待 . (2) 動態(tài)優(yōu)先級的確定 進程優(yōu)先級在運行時可以調(diào)整 . 確定 : ● 進程優(yōu)先級隨占用 CPU時間的延長而下降 ,隨等待CPU時間的延長而上升 . ● 當(dāng)?shù)却煌庠O(shè)的進程較多時 ,可提高使用該外設(shè)進程的優(yōu)先級 ,使它盡快運行 ,以釋放該外設(shè) ,滿足其它進程的服務(wù) . 優(yōu)點 :調(diào)度效果比較好 . 缺點 :算法實現(xiàn)困難 . 例：已知 p1， p2， p3， p4四個進程依次進入就緒隊列，它們所需的 CPU的時間和優(yōu)先數(shù)如下表 ： 進程 CPU時間 (秒 ) 優(yōu)先數(shù) p1 20 2 p2 15 3 p3 10 5 p4 12 3 寫出采用非搶占式的優(yōu)先數(shù)調(diào)度算法選中的進程執(zhí)行的次序；計算它們在就緒隊列中的等待時間和平均等待時間。 執(zhí)行次序： p3→p2 → p4→p1 等待時間： p1： 25＋ 12＝ 37（秒） p2： 0＋ 10＝ 10 （秒） p3： 0 （秒） p4： 10＋ 15＝ 25 （秒） 平均等待時間 ： (37＋ 10＋ 0＋ 25)/4＝ 18 （秒） 為每一個進程規(guī)定使用 CPU的時間 ,使就緒隊列的進程輪流地得到 CPU. 分為 :固定時間片的輪轉(zhuǎn)調(diào)度算法和可變式 時間片的輪轉(zhuǎn)調(diào)度算法。 （ 1）固定式時間片的輪轉(zhuǎn)調(diào)度算法 按規(guī)定的時間片 s設(shè)置時鐘，以使 s值到時限時產(chǎn)生時鐘中斷，中止進程執(zhí)行。 例：考慮三個進程 P1， P2， P3它們本次 CPC周期時值分別為 21ms。 6ms和 3ms，且以 P1， P2， P3的次序處于就緒隊列中，不妨以為它進入就緒隊列的相對時刻均為 0。 設(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 平均等待時間 w＝ (0+4+8)/3＝ 4(ms) 平均周轉(zhuǎn)時間 T=(30+17+11)/3＝ 19(ms) 算法特征： ? 該算法是一種剝奪式的進程調(diào)度算法，依據(jù)公平服務(wù)的原則為就緒進程服務(wù)。 ? 適用于分時系統(tǒng)；只要時間片恰當(dāng)，大多數(shù)終端用戶都能在一個時間片完成，可及時響應(yīng)每個用戶要求。 ? 時間片為一個固定值，進程均以相等的速度向前推進。 4 6 關(guān)鍵問題是怎樣確定時間片 s值？ 一般時間片 s值的確定： s=T/N 其中： T：用戶可接受響應(yīng)的時間 。N為進程數(shù)目 若 s值取得足夠大 ,以至每一個進程的 cpu周期都能在一個時間片內(nèi)完成，則輪轉(zhuǎn)算法退化成先來先服務(wù)算法。 若 s值很小勢必導(dǎo)致頻繁地時間片中斷和調(diào)度，增加了 cpu的開銷，降低了 cpu的效率。 ? 時間片 s的長短與 4種因素有關(guān)： T N ：轉(zhuǎn)換時間，保證系統(tǒng)開銷不大，一般在 10ms內(nèi)適中。 ： cpu速度越高，時間片越短 . （ 2）可變時間片的輪轉(zhuǎn)算法 思想 ?保持響應(yīng)時間不變 (T不變 )，每一輪開始時，系統(tǒng)就根據(jù)就緒隊列已有進程數(shù)目，按 s＝T/N計算一次 s，然后進行輪轉(zhuǎn) (在此期間所達到的就緒進程都暫不進入隊列中，等待下一輪一并進入 ),下輪重新計算 s，如此輪轉(zhuǎn)。 由系統(tǒng)設(shè)置多個就緒隊列，每個隊列按時間片輪轉(zhuǎn)算法調(diào)用 cpu。 167。 4 UNIX進程調(diào)度 一 .調(diào)度算法 ? UNIX系統(tǒng)采用優(yōu)先數(shù)調(diào)度算法 . 每進程有一個優(yōu)先數(shù) p_pri ? p_pri取值范圍是－ 127～ 127， 其值越小 ， 進程的優(yōu)先級越高 . 進入核心狀態(tài)運行的進程優(yōu)先級高于進入用戶狀態(tài)運行的進程優(yōu)先級 . 一個進程用完一個時間片而被剝奪 CPU,應(yīng)降低該進程的優(yōu)先級 . 進入睡眠狀態(tài)的進程 ,系統(tǒng)應(yīng)其等待事件的輕重緩急程度賦予它們不同的優(yōu)先級 . 累計使用 CPU時間較長的進程 ,其優(yōu)先級相應(yīng)降低 . 設(shè)置法和計算法 . (1) 設(shè)置優(yōu)先數(shù)法 設(shè)置者 :sleep( )程序 . 設(shè)置原則 : 進程進入睡眠時 ,系統(tǒng)按睡眠的原因設(shè)置優(yōu)先數(shù) . 因緊迫事件而入睡的進程設(shè)置較小的優(yōu)先數(shù) ,一般為負(fù)數(shù) . 等待事件不會產(chǎn)生全局影響的 ,設(shè)置較大的優(yōu)先數(shù) ,一般為正數(shù) . 如 : 0＃進程（－ 100優(yōu)先數(shù)）； ? 資源請求得不到滿足的進程，磁盤（－ 80），打印機（－20）， … ； ? 等待塊設(shè)備 I/O完成的進程 (－ 50)； ? 等待字符設(shè)備 I/O完成的進程 (0～ 20）； ? 所有處于用戶態(tài)運行進程同步（一般情況下為大于 100）。 設(shè)置優(yōu)先數(shù)法的目的 :保證系統(tǒng)資源得到充分利用 ,提高資源利用效率。 （ 2）計算優(yōu)先數(shù)法 目的：保證各終端用戶（進程）能均衡地占用 CPU（保證系統(tǒng)的交互速度）。 對終端進程采用動態(tài)計算優(yōu)先數(shù)法。 計算公式： p_pri = min{127, (p_cpu/16p_nice+PUSER)} 其中： ? p_cpu 進程占用 CPU的程度：如：每隔一個時鐘周期（ 20ms） 其值＋ 1 ? p_nice 用戶通過系統(tǒng)調(diào)用 nice(priority)設(shè)置的進程優(yōu)先數(shù) 。 取值： 0－ 39 ? PUSER 常數(shù) ， 其值為 100 計算優(yōu)先數(shù)的時機： ， 每秒末計算滿足下面條件進程的優(yōu)先數(shù)： p_pri PUSER trap( )末尾重新計算本進程的優(yōu)先數(shù) . ? 目的 :調(diào) 用 nice() 設(shè)置的本進程的優(yōu)先數(shù) p_nice的 改變反映到 p_pri中去； C. 現(xiàn)運行進程在執(zhí)行時鐘中斷處理程序時，若發(fā)現(xiàn)中斷前為用戶態(tài)，則每隔 1秒鐘重新計算本進程的優(yōu)先數(shù)。 二 .進程調(diào)度時機 :swtch( ). 分為 : (1) 現(xiàn)行進程本身不具備繼續(xù)占用 cpu的條件 ●進程終止 :完成任務(wù) ,調(diào)用 exit()命令后 . ● 進程等待某個事件的發(fā)生而進入睡眠狀態(tài)時 ,調(diào)用 sleep( )程序 . ● 進程用完一個時間片 . ● 進程與其它進程共同完成一個任務(wù) ,因同步需要主動放棄cpu. (2) 強迫放棄 cpu ● 在喚醒睡眠狀態(tài)的進程時 ,被喚醒的進程比現(xiàn)行進程的更緊迫 ,系統(tǒng)設(shè)置強迫調(diào)度標(biāo)志 runrun. ● 異常處理時 ,強迫對 cpu的再調(diào)度 . 第二部分 死 鎖 167。 5. 死鎖 主要內(nèi)容：●什么是死鎖？ ● 預(yù)防死鎖。 ●避免死鎖。 ●檢測死鎖。 一 .死鎖的概念 ? 兩個或多個進程已占有一定資源，又申請別的進程已占用的資源，造成互相死等的這種現(xiàn)象 ,稱為死鎖。 例： 因資源分配不當(dāng)引起的死鎖。 銀行家問題的例子 ? 銀行共有資金 10萬元，客戶 u1需貸款 3萬，客戶 u2需貸款 8萬，客戶 u3需貸款 9萬 。 u2 u3 u1 已貸款 還需資金 1萬 2萬 2萬 6萬 6萬 3萬 銀行只剩下 一萬元，造 成死