調(diào)度算法舉例

1、調(diào)度算法舉例1.傳統(tǒng)UNIX的進(jìn)程調(diào)度未設(shè)置作業(yè)調(diào)度，進(jìn)程調(diào)度采用基于時(shí)間片的多級(jí)反饋隊(duì)列算法，進(jìn)程優(yōu)先級(jí)分核心優(yōu)先級(jí)和用戶優(yōu)先級(jí)。1. 調(diào)度時(shí)機(jī)調(diào)度由0號(hào)進(jìn)程完成（始終在核心態(tài)執(zhí)行）。時(shí)機(jī)：l 進(jìn)程由核心態(tài)轉(zhuǎn)入用戶態(tài)時(shí)：在每次執(zhí)行核心代碼之后返回用戶態(tài)之前，檢查各就緒進(jìn)程的優(yōu)先級(jí)并進(jìn)行調(diào)度。如中斷進(jìn)程回到就緒隊(duì)列l(wèi) 進(jìn)程主動(dòng)放棄處理機(jī)時(shí)：進(jìn)程申請(qǐng)系統(tǒng)資源而未得到滿足（如read），或進(jìn)行進(jìn)程間同步而暫停（如wait或pause），或進(jìn)程退出（如exit）進(jìn)程進(jìn)入阻塞隊(duì)列或exit狀態(tài)。2. 調(diào)度標(biāo)志UNIX System V中有三個(gè)與調(diào)度有關(guān)的標(biāo)志：l runrun：表示要求進(jìn)行調(diào)度，當(dāng)發(fā)現(xiàn)

2、有就緒進(jìn)程優(yōu)先級(jí)高于當(dāng)前進(jìn)程時(shí)，設(shè)置該標(biāo)識(shí)。在wakeup, setrun, setpri（設(shè)置優(yōu)先級(jí)）過程和時(shí)鐘中斷處理例程進(jìn)行設(shè)置。l runin：表示內(nèi)存中沒有適當(dāng)?shù)倪M(jìn)程可以換出或內(nèi)存無足夠空間換入一個(gè)外存就緒進(jìn)程。l runout：表示外存交換區(qū)中沒有適當(dāng)?shù)倪M(jìn)程可以換入。3. 用戶優(yōu)先級(jí)進(jìn)程在用戶態(tài)和核心態(tài)的優(yōu)先級(jí)是不同的，這里說的是用戶態(tài)進(jìn)程的優(yōu)先級(jí)。它是基于執(zhí)行時(shí)間的動(dòng)態(tài)優(yōu)先級(jí)，進(jìn)程優(yōu)先級(jí)可為0127之間的任一整數(shù)。優(yōu)先數(shù)越大，優(yōu)先級(jí)越低。049之間的優(yōu)先級(jí)為系統(tǒng)內(nèi)核保留，用戶態(tài)下的進(jìn)程優(yōu)先級(jí)為50127之間。在UNIX System V中：進(jìn)程優(yōu)先數(shù)：P_pri = P_CPU

3、/ 2 + PUSER + P_nice + NZEROl 系統(tǒng)設(shè)置部分：PUSER和NZERO是基本用戶優(yōu)先數(shù)的閾值，分別為25和20l CPU使用時(shí)間部分：P_CPU表示該進(jìn)程最近一次CPU使用時(shí)間。每次時(shí)鐘中斷則該值加1（最多可達(dá)80）。如果時(shí)鐘中斷的周期為16.6ms，則每秒鐘過后將該值為60。l 新創(chuàng)建進(jìn)程的P_CPU值為0，因而具有較高的優(yōu)先級(jí)。l 用戶設(shè)置部分：P_nice是用戶可以通過系統(tǒng)調(diào)用設(shè)置的一個(gè)優(yōu)先級(jí)偏移值。默認(rèn)為20。超級(jí)用戶可以設(shè)置其在0到39之間，而普通用戶只能增大該值（即降低優(yōu)先級(jí)）。4. 核心優(yōu)先級(jí)內(nèi)核把進(jìn)程阻塞事件與一個(gè)睡眠優(yōu)先級(jí)（049）聯(lián)系起來；當(dāng)進(jìn)程從

4、阻塞中醒來時(shí)，可及時(shí)進(jìn)行處理。核心優(yōu)先級(jí)分為可中斷和不可中斷兩類優(yōu)先級(jí)。當(dāng)一個(gè)軟中斷信號(hào)到達(dá)時(shí)，若進(jìn)程正在可中斷優(yōu)先級(jí)上阻塞，則進(jìn)程立即被喚醒；若正在不可中斷優(yōu)先級(jí)上，則繼續(xù)阻塞。其中：l 不可中斷優(yōu)先級(jí)：對(duì)換，等待磁盤I/O，等待緩沖區(qū)，等待索引結(jié)點(diǎn)關(guān)鍵操作，應(yīng)該很快完成。l 可中斷優(yōu)先級(jí)：等待tty（虛終端）I/O，等待子進(jìn)程退出。5. 調(diào)度的實(shí)現(xiàn)調(diào)度的實(shí)現(xiàn)分三個(gè)階段：l 檢查是否作上下文切換（runrun標(biāo)志）和核心是否允許作上下文切換（對(duì)核心的各種數(shù)據(jù)結(jié)構(gòu)的操作都已經(jīng)完成，核心處于正確的狀態(tài)）。如果允許作上下文切換，則保存當(dāng)前進(jìn)程的上下文。l 恢復(fù)0進(jìn)程的上下文，然后執(zhí)行0進(jìn)程，尋找最

5、高優(yōu)先級(jí)就緒進(jìn)程，若沒有這樣的進(jìn)程存在，則執(zhí)行idle過程。若有這樣的進(jìn)程存在，則該進(jìn)程作為當(dāng)前進(jìn)程分派處理機(jī)，保存0進(jìn)程的上下文。l 恢復(fù)當(dāng)前進(jìn)程的上下文，執(zhí)行該進(jìn)程。2. Windows NT1. NT的調(diào)度策略l 調(diào)度單位是線程，采用搶先式動(dòng)態(tài)優(yōu)先級(jí)調(diào)度，依據(jù)優(yōu)先級(jí)和分配時(shí)間片來調(diào)度。l 線程由于調(diào)用等待函數(shù)而阻塞時(shí)，減少一個(gè)時(shí)間片，并依據(jù)等待事件類型提高優(yōu)先級(jí)；如等待鍵盤事件比等待磁盤事件的提高幅度大。l 線程被搶先時(shí)，放在相應(yīng)優(yōu)先級(jí)就緒隊(duì)列的前面，時(shí)間片值不重設(shè)。l 線程完整用完一個(gè)規(guī)定的時(shí)間片值時(shí)，重新賦予新時(shí)間片值，優(yōu)先級(jí)降一級(jí)（不低于基本優(yōu)先級(jí)），放在相應(yīng)優(yōu)先級(jí)就緒隊(duì)列的尾部。

6、2. NT線程的優(yōu)先級(jí)從0到31，數(shù)值越大，優(yōu)先級(jí)越高。分為兩類：l 實(shí)時(shí)(real-time)：從16到31，不會(huì)自動(dòng)改變？如設(shè)備監(jiān)控進(jìn)程。l 可變優(yōu)先級(jí)(variable-priority)：從1到15（級(jí)別0保留為系統(tǒng)使用），可由OS自動(dòng)改變。 進(jìn)程優(yōu)先級(jí)類ClassNormal base priorityIDLE_PRIORITY_CLASS4NORMAL_PRIORITY_CLASS9 if the window of the process is in the foreground; and 7 if the window is in the backgroundHIGH_PRIO

7、RITY_CLASS13REALTIME_PRIORITY_CLASS24l 線程的基本優(yōu)先級(jí) = 進(jìn)程的基本優(yōu)先級(jí) - 2，進(jìn)程的基本優(yōu)先級(jí) + 2，由應(yīng)用程序控制l 線程的動(dòng)態(tài)優(yōu)先級(jí) = 進(jìn)程的基本優(yōu)先級(jí) - 2, 31，由NT核心控制l NT的線程優(yōu)先級(jí)（Base Priority）由進(jìn)程優(yōu)先級(jí)類（Priority Class）和線程優(yōu)先級(jí)偏移（Priority Level）構(gòu)成，分別由相關(guān)函數(shù)控制。線程優(yōu)先級(jí)偏移PriorityMeaningTHREAD_PRIORITY_ABOVE_NORMALIndicates 1 point above normal priority for t

8、he priority class.THREAD_PRIORITY_BELOW_NORMALIndicates 1 point below normal priority for the priority class.THREAD_PRIORITY_HIGHESTIndicates 2 points above normal priority for the priority class.THREAD_PRIORITY_LOWESTIndicates 2 points below normal priority for the priority class.THREAD_PRIORITY_NO

9、RMALIndicates normal priority for the priority class.THREAD_PRIORITY_IDLEIndicates a base priority level of 1 for IDLE_PRIORITY_CLASS, NORMAL_PRIORITY_CLASS, or HIGH_PRIORITY_CLASS processes, and a base priority level of 16 for REALTIME_PRIORITY_CLASS processes.THREAD_PRIORITY_TIME_CRITICALIndicates a base priority level of 15 for IDLE_PRIORITY_CLASS, NORMAL_PRIORITY_CLASS, or HIGH_PRIORITY_CLASS processes, and a base priority level of 31 for REALTIME_PRIORITY_CLASS processes.l 有關(guān)A