【正文】 its own, ? master/slave assignment. 自調(diào)度 (self scheduling) ? 均衡調(diào)度 (balanced scheduling) ? 一個就緒隊列 (多處理機訪問互斥 ) ? 優(yōu)點 ? 不需要專門的處理機從事任務(wù)分派工作 ? 任務(wù)分配均衡 ? 缺點 ? 當 CPU較多時 ,就緒隊列成為瓶頸 ? 線程兩次調(diào)度可能處于不同處理機 ? 不能保證同組線程同時調(diào)度 自調(diào)度 (self scheduling) 就緒隊列 進程 (線程 ) 進程 (線程 ) 進程 (線程 ) CPU CPU CPU 自調(diào)度 (self scheduling) ? 例子 : ? Mach, 改進的自調(diào)度 ? 全局隊列 :系統(tǒng)一個 ? 局部隊列 :每個 CPU一個 ? 調(diào)度時 ? 首先考慮局部隊列 ? 然后考慮全局隊列 組調(diào)度 (gang scheduling) ? 將一組相關(guān) (合作 )的線程 同時 分派到多個處理機上運行 ? 避免合作線程之間的相互等待 ? 降低開銷 ,提高運行效率 ? 例子 : ? Cm* ? Task force (一組相關(guān)的計算 ) 系統(tǒng)舉例 ? Linux進程調(diào)度 ? Windows2022/XP線程調(diào)度 ? UNIX進程調(diào)度（見第 12章） ? 三種特征進程 ? Realtime FIFO ? Realtime Round Robin ? Timesharing ? Goodnessbased scheduling ? priority ? 040, (缺省值 20 ),可通過 nice系統(tǒng)調(diào)用調(diào)整 ，nice(value)中 value的取值范圍為 (20,20)之間 ,取priority=20value. ? counter ? 進程尚可運行的剩余時間 Linux 進程調(diào)度 Linux 進程調(diào)度 – counter ? 對于運行進程來說，每個時鐘間隔 (10ms，稱為一個jiffy)，將 counter減 1 ? 當所有就緒進程的 counter配額下降到 0時，重新計算所有進程 (包括等待進程 )的 counter值 – counter= (counter/2) + priority – goodness ? if(Realtime)goodness=1000+priority ? if(Timesharing amp。amp。 counter=0)goodness=0 ? if(Timesharing amp。amp。 counter0)goodness=counter+priority Linux 進程調(diào)度 ? 調(diào)度發(fā)生時刻： – 運行進程的 counter減至 0； – 運行進程執(zhí)行系統(tǒng)調(diào)用 exit 。 – 運行進程因等待 I/O、信號燈而被封鎖 。 – 原來具有高 goodness的進程被解除封鎖 . ? 調(diào)度效果 : – 實時優(yōu)先于分時 – 交互和 I/O進程優(yōu)先于 CPU進程 Linux 對稱多處理 ? Linux核心 。 – 進程或線程可以同時運行在多個處理機上 . ? 為保持核心非剝奪同步要求， SMP通過一個唯一的核心自旋鎖 (spinlock)來保證任何時刻最多只有一個處理機執(zhí)行核心代碼 , – 支持真正意義上的 SMP：將一個自旋鎖分解為若干個相互獨立的自旋鎖，分別用于保護核心代碼不相交的子集 . Windows 2022/XP線程 調(diào)度 ? Main Features： ? Thread level scheduling。 ? Real time + foreground + background。 ? real time: no deadline scheduling。 ? foreground: GUI window ? background: noninteractive ? Preemptive + dynamic priority + RR + Feed back。 ? Symmetric MultiProcessor(SMP) support。 優(yōu)先級別 ? 16個實時優(yōu)先級（ 1631） ? 一些內(nèi)核線程 ? 應(yīng)用程序提升為實時優(yōu)先級需要有權(quán)限 ? 不是真正意義上的實時調(diào)度 ? 15個可變線程優(yōu)先級（ 115） ? 基本優(yōu)先級 vs. 當前優(yōu)先級 ? 線程基本優(yōu)先級繼承進程基本優(yōu)先級 , 可上下浮動 2 ? 如 : 進程基本優(yōu)先級 4, 其線程基本優(yōu)先級 2— 6, ? 當前優(yōu)先級在 2— 15范圍內(nèi)變動 . ? 可動態(tài)提升 ? 運行完一個 quantum之后自動下降 , 不低于基本優(yōu)先級 ? 1個系統(tǒng)線程優(yōu)先級（ 0） 優(yōu)先級提升 ? 優(yōu)先級提升 ? IO操作完成 ? 事件等待結(jié)束 ? 前臺進程中的線程完成一個等待操作 ? 由于窗口活動而喚醒 GUI線程 ? 就緒超過一定時限，未獲得處理機 ? 優(yōu)先級提升不會超過 15 搶占 CPU ? 搶先情形 ? 被喚醒線程優(yōu)先級高于運行線程優(yōu)先級； ? 某線程的優(yōu)先級動態(tài)變化 ? 被搶先線程 ? 回到相應(yīng)就緒隊列 ? 時間配額 ? 實時線程：重新分配完整時間配額 ? 其它線程：保持剩余配額 時間配額 (quantum) ? 配額長度： 636 ? 時鐘中斷（ 15ms發(fā)生一次）減 3， 212次時鐘中斷（ 30ms180ms）配額用完 ? 配額用完后進入就緒隊列，優(yōu)先級下降 SMP上的線程調(diào)度 ? 線程與 CPU的親合關(guān)系 ? 每個進程有一個處理器親合掩碼，缺省為所有處理器的集合 ? 線程繼承其進程的親合掩碼 ? 親合掩碼可以修改 ? SetProcessAffinityMask, ? SetThreadAffinityMask。 SMP上的線程調(diào)度 ? 線程的理想處理器（ Ideal processor） ? 首選處理器： ? 第二處理器：（在內(nèi)核線程控制塊中） ? 理想處理器確定 ? 線程創(chuàng)建時隨機確定， ? 分散各個線程與處理機對應(yīng)關(guān)系。 ? 線程可修改 SetThreadIdealProcessor 就緒線程對處理器的選擇 ? 有空閑處理器 ? 首選處理器 ? 第二處理器 ? 當前執(zhí)行處理器（正執(zhí)行調(diào)度代碼） ? 由高到低順序找空閑的處理器 ? 無空閑處理器，考慮搶先 ? 首選處理器 ? 第二處理器 ? 可運行編號最大處理器 ? 不能搶先進入相應(yīng)的就緒隊列 處理器對就緒線程的選擇 ? 空閑處理器調(diào)度 ? 線程上次在此 CPU上運行（二級緩沖利用） ? 線程的理想處理器是該 CPU ? 處于就緒狀態(tài)時間超過 2個 quantum ? 優(yōu)先級別大于等于 24 作業(yè) 1 1. 進程切換時需要保存哪些現(xiàn)場信息？請盡量考慮完全。 2. 由核心返回目態(tài)程序時，進程的 PSW和 PC為何必須用一條機器指令同時恢復(fù)？ 3. 對如下三個實時任務(wù) : T1=100, C1=50。 T2=200, C2=30。 T3=500, C3=100. 采用 EDF算法和 RMS算法是否可調(diào)度 ?如是畫出對應(yīng)的 Gantt圖 ,否則說明原因 。