【正文】 TTnW11作業(yè)的周轉(zhuǎn)時間 T與系統(tǒng)為它提供服務(wù)的時間 TS之比 ， 即W=T/TS， 稱為帶權(quán)周轉(zhuǎn)時間 ， 而平均帶權(quán)周轉(zhuǎn)時間則可表示為 : 第三章 處理機調(diào)度與死鎖 (2) 響應(yīng)時間快。 (2) 設(shè)置多個阻塞隊列。 引入中級調(diào)度的主要目的 ， 是為了提高內(nèi)存利用率和系統(tǒng)吞吐量 。 第三章 處理機調(diào)度與死鎖 2) 搶占方式 (Preemptive Mode) (1) 優(yōu)先權(quán)原則。 1) 接納多少個作業(yè) 2) 接納哪些作業(yè) 第三章 處理機調(diào)度與死鎖 2. 低級調(diào)度 (Low Level Scheduling) 1) 非搶占方式 (Nonpreemptive Mode) 在采用非搶占調(diào)度方式時 ， 可能引起進程調(diào)度的因素可歸結(jié)為這樣幾個： ① 正在執(zhí)行的進程執(zhí)行完畢 ， 或因發(fā)生某事件而不能再繼續(xù)執(zhí)行； ② 執(zhí)行中的進程因提出 I/O請求而暫停執(zhí)行； ③ 在進程通信或同步過程中執(zhí)行了某種原語操作 ， 如 P操作 (wait操作 )、 Block原語 、 Wakeup原語等 。 這種調(diào)度方式的優(yōu)點是實現(xiàn)簡單 、 系統(tǒng)開銷小 ， 適用于大多數(shù)的批處理系統(tǒng)環(huán)境 。 (2) 短作業(yè) (進程 )優(yōu)先原則。 為此 ， 應(yīng)使那些暫時不能運行的進程不再占用寶貴的內(nèi)存資源 ， 而將它們調(diào)至外存上去等待 ， 把此時的進程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài) 。 圖 32 示出了具有高 、 低兩級調(diào)度的調(diào)度隊列模型 。 (3) 截止時間的保證。 (3) 各類資源的平衡利用。 而短進程優(yōu)先 (SPF)調(diào)度算法 ， 則是從就緒隊列中選出一估計運行時間最短的進程 ， 將處理機分配給它 ， 使它立即執(zhí)行并一直執(zhí)行到完成 ， 或發(fā)生某事件而被阻塞放棄處理機時 ， 再重新調(diào)度 。 (3) 由于作業(yè) (進程 )的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的 ， 而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間 ， 致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度 。 但在其執(zhí)行期間 ， 只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進程 ， 進程調(diào)度程序就立即停止當前進程 (原優(yōu)先權(quán)最高的進程 )的執(zhí)行 ， 重新將處理機分配給新到的優(yōu)先權(quán)最高的進程 。 第三章 處理機調(diào)度與死鎖 2. 優(yōu)先權(quán)的類型 1) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進程時確定的 ， 且在進程的整個運行期間保持不變 。 (2) 進程對資源的需求。 若所有的進程都具有相同的優(yōu)先權(quán)初值 ， 則顯然是最先進入就緒隊列的進程 ， 將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機 ， 此即 FCFS算法 。 據(jù)此 ， 又可表示為： 要求服務(wù)時間響應(yīng)時間要求服務(wù)時間要求服務(wù)時間等待時間優(yōu)先權(quán) ???第三章 處理機調(diào)度與死鎖 (1) 如果作業(yè)的等待時間相同 ， 則要求服務(wù)的時間愈短 ， 其優(yōu)先權(quán)愈高 ， 因而該算法有利于短作業(yè) 。 時間片的大小從幾ms到幾百 ms。 第一個隊列的優(yōu)先級最高 ， 第二個隊列次之 ， 其余各隊列的優(yōu)先權(quán)逐個降低 。 第三章 處理機調(diào)度與死鎖 圖 35 多級反饋隊列調(diào)度算法 就緒隊列 1就緒隊列 2就緒隊列 3就緒隊列 nS1S2S3至 C P U至 C P U至 C P U至 C P U( 時間片： S1＜ S2＜ S3)第三章 處理機調(diào)度與死鎖 (2) 當一個新進程進入內(nèi)存后 ， 首先將它放入第一隊列的末尾 ， 按 FCFS原則排隊等待調(diào)度 。 第三章 處理機調(diào)度與死鎖 3. 多級反饋隊列調(diào)度算法的性能 (1) 終端型作業(yè)用戶 。 (2) 開始截止時間和完成截止時間。 第三章 處理機調(diào)度與死鎖 2. 系統(tǒng)處理能力強 在實時系統(tǒng)中 ， 通常都有著多個實時任務(wù) 。 解決的方法是提高系統(tǒng)的處理能力 ， 其途徑有二：其一仍是采用單處理機系統(tǒng) ， 但須增強其處理能力 ， 以顯著地減少對每一個任務(wù)的處理時間；其二是采用多處理機系統(tǒng) 。 但在設(shè)計這種調(diào)度機制時 ，應(yīng)使所有的實時任務(wù)都比較小 ， 并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后 ， 能及時地將自己阻塞起來 ， 以便釋放出處理機 ， 供調(diào)度程序去調(diào)度那種開始截止時間即將到達的任務(wù) 。 在完成任務(wù)調(diào)度后 ， 便應(yīng)進行任務(wù)切換 。 第三章 處理機調(diào)度與死鎖 2. 搶占式調(diào)度算法 (1) 基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。 例如 ， 一個任務(wù)在 200ms時必須完成 ，而它本身所需的運行時間就有 100ms， 因此 ， 調(diào)度程序必須在100 ms之前調(diào)度執(zhí)行 ， 該任務(wù)的緊急程度 (松弛程度 )為 100 ms。 假如在一個實時系統(tǒng)中 ， 有兩個周期性實時任務(wù) A和 B， 任務(wù) A要求每 20 ms執(zhí)行一次 ， 執(zhí)行時間為 10 ms；任務(wù) B只要求每 50 ms執(zhí)行一次 ，執(zhí)行時間為 25 ms。 在 t4=40 ms時 ， A3的松弛度為 10 ms(即 601040)， 而 B1的松弛度僅為 5 ms(即 50540)， 故又應(yīng)重新調(diào)度 B1執(zhí)行 。 第三章 處理機調(diào)度與死鎖 圖 39 利用 ELLF算法進行調(diào)度的情況 t1A1( 1 0 )10 20 30 40 50 60 80t0t1＝ 0B1( 2 0 )t2t370A2( 1 0 ) A3( 1 0 ) A4( 1 0 )t4t5t6t7t8B1( 5 ) B2( 1 5 ) B2( 1 0 )第三章 處理機調(diào)度與死鎖 多處理機系統(tǒng)中的調(diào)度 多處理器系統(tǒng)的類型 (1) 緊密耦合 (Tightly Coupted)MPS。 第三章 處理機調(diào)度與死鎖 (2) 松散耦合 (Loosely Coupled)MPS。 第三章 處理機調(diào)度與死鎖 2. 對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng) (1) 對稱多處理器系統(tǒng) SMPS(Symmetric MultiProcessor System)。 在系統(tǒng)中有多種類型的處理單元 ， 它們的功能和結(jié)構(gòu)各不相同 ， 其中只有一個主處理器 ， 有多個從處理器 。 每當從機空閑時 ， 便向主機發(fā)送一索求進程的信號 ， 然后 ， 便等待主機為它分配進程 。 它是直接由單處理機環(huán)境下的調(diào)度方式演變而來的 。其次 ， 只要系統(tǒng)中有任務(wù) ， 或者說只要公共就緒隊列不空 ，就不會出現(xiàn)處理機空閑的情況 ， 也不會發(fā)生處理器忙閑不均的現(xiàn)象 ， 因而有利于提高處理器的利用率 。 第三章 處理機調(diào)度與死鎖 2. 成組調(diào)度 (Gang Scheduling) 在成組調(diào)度時 ， 如何為應(yīng)用程序分配處理器時間 ， 1) 面向所有應(yīng)用程序平均分配處理器時間 2) 面向所有線程平均分配處理器時間 圖 3 10 兩種分配處理器時間的方法 第三章 處理機調(diào)度與死鎖 3. 專用處理器分配 (Dedicated Processor Assigement)方式 圖 311 線程數(shù)對加速比的影響 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 241234567加速比線程數(shù)矩陣相乘FFT0第三章 處理機調(diào)度與死鎖 產(chǎn)生死鎖的原因和必要條件 產(chǎn)生死鎖的原因 (1) 競爭資源。 因為 ， 這時兩進程再向前推進 ， 便可能發(fā)生死鎖 。 (3) 檢測死鎖。 所謂安全狀態(tài) ， 是指系統(tǒng)能按某種進程順序 (P1, P2, …，Pn)(稱 〈 P1, P2, …, Pn〉 序列為安全序列 )， 來為每個進程 Pi分配其所需資源 ， 直至滿足每個進程對資源的最大