操作系統(tǒng)：第五章 處理機管理

第五章處理機管理5.1引言5.2調(diào)度算法5.3調(diào)度算法性能分析5.4實時調(diào)度5.5多處理機調(diào)度5.6調(diào)度算法舉例處理機管理的工作是對CPU資源進行合理的分配使用，以提高處理機利用率，并使各用戶公平地得到處理機資源。這里的主要問題是處理機調(diào)度算法和調(diào)度算法特征分析。5.1引言5.1.1調(diào)度的類型(scheduling)5.1.2調(diào)度的性能準(zhǔn)則5.1.3進程調(diào)度返回5.1.1調(diào)度的類型(scheduling)作業(yè)：又稱為"宏觀調(diào)度"、"高級調(diào)度"。從用戶工作流程的角度，一次提交的若干個流程，其中每個程序按照進程調(diào)度。時間上通常是分鐘、小時或天。內(nèi)外存交換：又稱為"中級調(diào)度"。從存儲器資源的角度。將進程的部分或全部換出到外存上，將當(dāng)前所需部分換入到內(nèi)存。指令和數(shù)據(jù)必須在內(nèi)存里才能被CPU直接訪問。進程或線程：又稱為"微觀調(diào)度"、"低級調(diào)度"。從CPU資源的角度，執(zhí)行的單位。時間上通常是毫秒。因為執(zhí)行頻繁，要求在實現(xiàn)時達到高效率。從處理機調(diào)度的對象、時間、功能等不同角度，我們可把處理機調(diào)度分成不同類型。1.按照調(diào)度的層次處理機調(diào)度的層次2.按照調(diào)度的時間周期長期(long-term)：將進程投入"允許執(zhí)行"進程緩沖池中，或送到"退出"進程緩沖池中。進程狀態(tài)：New－>Readysuspend,Running－>Exit中期(medium-term)：將進程的部分或全部加載到內(nèi)存中。進程狀態(tài)：Ready<－>Readysuspend,Blocked<－>Blockedsuspend短期(short-term)：選擇哪個進程在處理機上執(zhí)行。進程狀態(tài)：Ready<－>RunningI/O調(diào)度：選擇哪個I/O等待進程，使其請求可以被空閑的I/O設(shè)備進行處理。3.按照OS的分類批處理調(diào)度－－應(yīng)用場合：大中型主機集中計算，如工程計算、理論計算（流體力學(xué)）分時調(diào)度、實時調(diào)度：通常沒有專門的作業(yè)調(diào)度多處理機調(diào)度5.1.2調(diào)度的性能準(zhǔn)則我們可從不同的角度來判斷處理機調(diào)度算法的性能，如用戶的角度、處理機的角度和算法實現(xiàn)的角度。實際的處理機調(diào)度算法選擇是一個綜合的判斷結(jié)果。周轉(zhuǎn)時間：作業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時間。包括：在收容隊列中等待，CPU上執(zhí)行，就緒隊列和阻塞隊列中等待，結(jié)果輸出等待－－批處理系統(tǒng)平均周轉(zhuǎn)時間T平均帶權(quán)周轉(zhuǎn)時間（帶權(quán)周轉(zhuǎn)時間W是T(周轉(zhuǎn))/T(CPU執(zhí)行)〕響應(yīng)時間：用戶輸入一個請求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時間－－分時系統(tǒng)截止時間：開始截止時間和完成截止時間－－實時系統(tǒng)，與周轉(zhuǎn)時間有些相似。公平性：不因作業(yè)或進程本身的特性而使上述指標(biāo)過分惡化。如長作業(yè)等待很長時間。優(yōu)先級：可以使關(guān)鍵任務(wù)達到更好的指標(biāo)。1.面向用戶的調(diào)度性能準(zhǔn)則2.面向系統(tǒng)的調(diào)度性能準(zhǔn)則吞吐量：單位時間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本身特性和調(diào)度算法都有關(guān)系－－批處理系統(tǒng)平均周轉(zhuǎn)時間不是吞吐量的倒數(shù)，因為并發(fā)執(zhí)行的作業(yè)在時間上可以重疊。如：在2小時內(nèi)完成4個作業(yè)，而每個周轉(zhuǎn)時間是1小時，則吞吐量是2個作業(yè)/小時處理機利用率：－－大中型主機各種設(shè)備的均衡利用：如CPU繁忙的作業(yè)和I/O繁忙（指次數(shù)多，每次時間短）的作業(yè)搭配－－大中型主機3.調(diào)度算法本身的調(diào)度性能準(zhǔn)則易于實現(xiàn)執(zhí)行開銷比5.1.3進程調(diào)度功能：調(diào)度程序(dispatcher)記錄所有進程的運行狀況（靜態(tài)和動態(tài)）當(dāng)進程出讓CPU或調(diào)度程序剝奪執(zhí)行狀態(tài)進程占用的CPU時，選擇適當(dāng)?shù)倪M程分派CPU完成上下文切換進程的上下文切換過程：用戶態(tài)執(zhí)行進程A代碼－－進入OS核心（通過時鐘中斷或系統(tǒng)調(diào)用）保存進程A的上下文，恢復(fù)進程B的上下文（CPU寄存器和一些表格的當(dāng)前指針）用戶態(tài)執(zhí)行進程B代碼注：上下文切換之后，指令和數(shù)據(jù)快速緩存cache通常需要更新，執(zhí)行速度降低5.2調(diào)度算法5.2.1先來先服務(wù)5.2.2短作業(yè)優(yōu)先5.2.3時間片輪轉(zhuǎn)算法5.2.4多級隊列算法5.2.5優(yōu)先級算法5.2.6多級反饋隊列算法返回通常將作業(yè)或進程歸入各種就緒或阻塞隊列。有的算法適用于作業(yè)調(diào)度，有的算法適用于進程調(diào)度，有的兩者都適應(yīng)。5.2.1先來先服務(wù)

(FCFS,FirstComeFirstService)按照作業(yè)提交或進程變?yōu)榫途w狀態(tài)的先后次序，分派CPU；當(dāng)前作業(yè)或進程占用CPU，直到執(zhí)行完或阻塞，才出讓CPU（非搶占方式）。在作業(yè)或進程喚醒后（如I/O完成），并不立即恢復(fù)執(zhí)行，通常等到當(dāng)前作業(yè)或進程出讓CPU。最簡單的算法。這是最簡單的調(diào)度算法，按先后順序進行調(diào)度。1.FCFS算法2.FCFS的特點比較有利于長作業(yè)，而不利于短作業(yè)。有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。5.2.2短作業(yè)優(yōu)先

(SJF,ShortestJobFirst)又稱為“短進程優(yōu)先”SPN(ShortestProcessNext)；這是對FCFS算法的改進，其目標(biāo)是減少平均周轉(zhuǎn)時間。1.SJF算法對預(yù)計執(zhí)行時間短的作業(yè)（進程）優(yōu)先分派處理機。通常后來的短作業(yè)不搶先正在執(zhí)行的作業(yè)。2.SJF的特點優(yōu)點：比FCFS改善平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，縮短作業(yè)的等待時間；提高系統(tǒng)的吞吐量；缺點：對長作業(yè)非常不利，可能長時間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級；難以準(zhǔn)確估計作業(yè)（進程）的執(zhí)行時間，從而影響調(diào)度性能。3.SJF的變型"最短剩余時間優(yōu)先"SRT(ShortestRemainingTime)允許比當(dāng)前進程剩余時間更短的進程來搶占"最高響應(yīng)比優(yōu)先"HRRN(HighestResponseRatioNext)響應(yīng)比R=(等待時間+要求執(zhí)行時間)/要求執(zhí)行時間是FCFS和SJF的折衷5.2.3時間片輪轉(zhuǎn)(RoundRobin)算法前兩種算法主要用于宏觀調(diào)度，說明怎樣選擇一個進程或作業(yè)開始運行，開始運行后的作法都相同，即運行到結(jié)束或阻塞，阻塞結(jié)束時等待當(dāng)前進程放棄CPU

。本算法主要用于微觀調(diào)度，說明怎樣并發(fā)運行，即切換的方式；設(shè)計目標(biāo)是提高資源利用率。其基本思路是通過時間片輪轉(zhuǎn)，提高進程并發(fā)性和響應(yīng)時間特性，從而提高資源利用率；1.時間片輪轉(zhuǎn)算法將系統(tǒng)中所有的就緒進程按照FCFS原則，排成一個隊列。每次調(diào)度時將CPU分派給隊首進程，讓其執(zhí)行一個時間片。時間片的長度從幾個ms到幾百ms。在一個時間片結(jié)束時，發(fā)生時鐘中斷。調(diào)度程序據(jù)此暫停當(dāng)前進程的執(zhí)行，將其送到就緒隊列的末尾，并通過上下文切換執(zhí)行當(dāng)前的隊首進程。進程可以未使用完一個時間片，就出讓CPU（如阻塞）。2.時間片長度的確定時間片長度變化的影響過長－>退化為FCFS算法，進程在一個時間片內(nèi)都執(zhí)行完，響應(yīng)時間長。過短－>用戶的一次請求需要多個時間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時間長。對響應(yīng)時間的要求：T(響應(yīng)時間)=N(進程數(shù)目)*q(時間片)時間片長度的影響因素：就緒進程的數(shù)目：數(shù)目越多，時間片越?。ó?dāng)響應(yīng)時間一定時）系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶輸入通常在一個時間片內(nèi)能處理完，否則使響應(yīng)時間，平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間延長。5.2.4多級隊列算法

(Multiple-levelQueue)根據(jù)作業(yè)或進程的性質(zhì)或類型的不同，將就緒隊列再分為若干個子隊列。每個作業(yè)固定歸入一個隊列。各隊列的不同處理：不同隊列可有不同的優(yōu)先級、時間片長度、調(diào)度策略等。如：系統(tǒng)進程、用戶交互進程、批處理進程等。本算法引入多個就緒隊列，通過各隊列的區(qū)別對待，達到一個綜合的調(diào)度目標(biāo)；5.2.5優(yōu)先級算法(PriorityScheduling)5.2.5.1靜態(tài)優(yōu)先級5.2.5.2動態(tài)優(yōu)先級5.2.5.3線性優(yōu)先級調(diào)度算法（SRR,SelfishRoundRobin）本算法是多級隊列算法的改進，平衡各進程對響應(yīng)時間的要求。適用于作業(yè)調(diào)度和進程調(diào)度，可分成搶先式和非搶先式；5.2.5.1靜態(tài)優(yōu)先級依據(jù)：進程類型（系統(tǒng)進程優(yōu)先級較高）對資源的需求（對CPU和內(nèi)存需求較少的進程，優(yōu)先級較高）用戶要求（緊迫程度和付費多少）創(chuàng)建進程時就確定，直到進程終止前都不改變。通常是一個整數(shù)。5.2.5.2動態(tài)優(yōu)先級在就緒隊列中，等待時間延長則優(yōu)先級提高，從而使優(yōu)先級較低的進程在等待足夠的時間后，其優(yōu)先級提高到可被調(diào)度執(zhí)行；進程每執(zhí)行一個時間片，就降低其優(yōu)先級，從而一個進程持續(xù)執(zhí)行時，其優(yōu)先級降低到出讓CPU。在創(chuàng)建進程時賦予的優(yōu)先級，在進程運行過程中可以自動改變，以便獲得更好的調(diào)度性能。如：5.2.5.3線性優(yōu)先級調(diào)度算法

（SRR,SelfishRoundRobin）就緒進程隊列分成兩個：新創(chuàng)建進程隊列：按FCFS方式排成；進程優(yōu)先級按速率a增加；享受服務(wù)隊列：已得到過時間片服務(wù)的進程按FCFS方式排成；進程優(yōu)先級按速率b增加；新創(chuàng)建進程等待時間的確定：當(dāng)新創(chuàng)建進程優(yōu)先級與享受服務(wù)隊列中最后一個進程優(yōu)先級相同時，轉(zhuǎn)入享受服務(wù)隊列；本算法是優(yōu)先級算法的一個實例，它通過進程優(yōu)先級的遞增來改進長執(zhí)行時間進程的周轉(zhuǎn)時間特征。1.SRR算法SRR算法的優(yōu)先級變化2.SRR算法與FCFS算法和時間片輪轉(zhuǎn)算法的關(guān)系當(dāng)b>a>0時，享受服務(wù)隊列中永遠只有一個進程；SRR算法退化成FCFS算法；當(dāng)a>b=0時，SRR算法就是時間片輪轉(zhuǎn)算法；5.2.6多級反饋隊列算法

(RoundRobinwithMultipleFeedback)多級反饋隊列算法是時間片輪轉(zhuǎn)算法和優(yōu)先級算法的綜合和發(fā)展。優(yōu)點：為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時間而照顧短進程為獲得較好的I/O設(shè)備利用率和縮短響應(yīng)時間而照顧I/O型進程不必估計進程的執(zhí)行時間，動態(tài)調(diào)節(jié)1.多級反饋隊列算法設(shè)置多個就緒隊列，分別賦予不同的優(yōu)先級，如逐級降低，隊列1的優(yōu)先級最高。每個隊列執(zhí)行時間片的長度也不同，規(guī)定優(yōu)先級越低則時間片越長，如逐級加倍新進程進入內(nèi)存后，先投入隊列1的末尾，按FCFS算法調(diào)度；若按隊列1一個時間片未能執(zhí)行完，則降低投入到隊列2的末尾，同樣按FCFS算法調(diào)度；如此下去，降低到最后的隊列，則按"時間片輪轉(zhuǎn)"算法調(diào)度直到完成。僅當(dāng)較高優(yōu)先級的隊列為空，才調(diào)度較低優(yōu)先級的隊列中的進程執(zhí)行。如果進程執(zhí)行時有新進程進入較高優(yōu)先級的隊列，則搶先執(zhí)行新進程，并把被搶先的進程投入原隊列的末尾。2.幾點說明I/O型進程：讓其進入最高優(yōu)先級隊列，以及時響應(yīng)I/O交互。通常執(zhí)行一個小時間片，要求可處理完一次I/O請求的數(shù)據(jù)，然后轉(zhuǎn)入到阻塞隊列。計算型進程：每次都執(zhí)行完時間片，進入更低級隊列。最終采用最大時間片來執(zhí)行，減少調(diào)度次數(shù)。I/O次數(shù)不多，而主要是CPU處理的進程：在I/O完成后，放回優(yōu)先I/O請求時離開的隊列，以免每次都回到最高優(yōu)先級隊列后再逐次下降。為適應(yīng)一個進程在不同時間段的運行特點，I/O完成時，提高優(yōu)先級；時間片用完時，降低優(yōu)先級；5.3調(diào)度算法性能分析FCFS,RoundRobin,線性優(yōu)先級算法SRR(SelfishRoundRobin)周轉(zhuǎn)時間長作業(yè)時：T(FCFS)<T(SRR)<T(RR)（運行時間是主要因素）短作業(yè)時：T(RR)<T(SRR)<T(FCFS)（等待時間是主要因素）返回調(diào)度算法的性能通常是通過實驗或計算得到的。5.4實時調(diào)度5.4.1實時調(diào)度的特點5.4.2實時調(diào)度算法返回5.4.1實時調(diào)度的特點要求更詳細的調(diào)度信息：如，就緒時間、開始或完成截止時間、處理時間、資源要求、絕對或相對優(yōu)先級（硬實時或軟實時）。采用搶先式調(diào)度。快速中斷響應(yīng)，在中斷處理時（硬件）關(guān)中斷的時間盡量短?？焖偕舷挛那袚Q：相應(yīng)地采用較小的調(diào)度單位（如線程）。5.4.2實時調(diào)度算法靜態(tài)表調(diào)度算法（Statictable-drivenscheduling）：適用于周期性的實時應(yīng)用。通過對所有周期性任務(wù)的分析預(yù)測（到達時間、運行時間、結(jié)束時間、任務(wù)間的優(yōu)先關(guān)系），事先確定一個固定的調(diào)度方案。這種方法的特點是有效但不靈活。靜態(tài)優(yōu)先級調(diào)度算法（Staticpriority-drivenscheduling）：把通用的優(yōu)先級調(diào)度算法用于實時系統(tǒng)，但優(yōu)先級的確定是通過靜態(tài)分析（運行時間、到達頻率）完成的。動態(tài)分析調(diào)度算法（Dynamicplanning-basedscheduling）：在任務(wù)下達后執(zhí)行前進行調(diào)度分析，要求滿足實時性要求。無保障動態(tài)調(diào)度算法（Dynamicbesteffortscheduling）：在任務(wù)下達時分配優(yōu)先級，開始執(zhí)行，在時限到達時未完成的任務(wù)被取消。用于非周期性任務(wù)的實時系統(tǒng)。5.5多處理機調(diào)度5.5.1與單處理機調(diào)度的區(qū)別5.5.2對稱式多處理系統(tǒng)(SMP)5.5.3非對稱式多處理系統(tǒng)(ASMP)的處理機調(diào)度5.5.4成組調(diào)度(gangscheduling)5.5.5專用處理機調(diào)度(dedicatedprocessorassignment)返回5.5.1與單處理機調(diào)度的區(qū)別注重整體運行效率（而不是個別處理機的利用率）更多樣的調(diào)度算法多處理機訪問OS數(shù)據(jù)結(jié)構(gòu)時的互斥（對于共享內(nèi)存系統(tǒng)）調(diào)度單位廣泛采用線程5.5.2對稱式多處理系統(tǒng)(SMP)集中控制靜態(tài)分配(staticassignment)：每個CPU設(shè)立一個就緒隊列，進程從開始執(zhí)行到完成，都在同一個CPU上。優(yōu)點：調(diào)度算法開銷小。缺點：容易出現(xiàn)忙閑不均。動態(tài)分配(dynamicassignment)：各個CPU采用一個公共就緒隊列，隊首進程每次分派到當(dāng)前空閑的CPU上執(zhí)行。按控制方式，SMP調(diào)度算法可分為集中控制和分散控制。下面所述靜態(tài)和動態(tài)調(diào)度都是集中控制，而自調(diào)度是分散控制。分散控制自調(diào)度(self-scheduling)：各個CPU采用一個公共就緒隊列，每個處理機都可以從隊列中選擇適當(dāng)進程來執(zhí)行。需要對就緒隊列的數(shù)據(jù)結(jié)構(gòu)進行互斥訪問控制。是最常用的算法，實現(xiàn)時易于移植采用單處理機的調(diào)度技術(shù)。變型：MachOS中局部和全局就緒隊列相結(jié)合，其中局部就緒隊列中的線程優(yōu)先調(diào)度。5.5.3非對稱式多處理系統(tǒng)(ASMP)的處理機調(diào)度主－從處理機系統(tǒng)，由主處理機管理一個公共就緒隊列，并分派進程給從處理機執(zhí)行。各個處理機有固定分工，如執(zhí)行OS的系統(tǒng)功能，I/O處理，應(yīng)用程序。5.5.4成組調(diào)度(gangscheduling)優(yōu)點通常這樣的一組線程在應(yīng)用邏輯上相互合作，成組調(diào)度提高了這些線程的執(zhí)行并行度，有利于減少阻塞和加快推進速度，最終提高系統(tǒng)吞吐量。每次調(diào)度可以完成多個線程的分派，在系統(tǒng)內(nèi)線程總數(shù)相同時能夠減少調(diào)度次數(shù)，從而減少調(diào)度算法的開銷將一個進程中的一組線程，每次分派時同時到一組處理機上執(zhí)行，在剝奪處理機時也同時對這一組線程進行。5.5.5專用處理機調(diào)度

(dedicatedprocessorassignment)為進程中的每個線程都固定分配一個CPU，直到該線程執(zhí)行完成。缺點：線程阻塞時，造成CPU的閑置。優(yōu)點：線程執(zhí)行時不需切換，相應(yīng)的開銷可以大大減小，推進速度更快。適用場合：CPU數(shù)量眾多的高度并行系統(tǒng)，單個CPU利用率已不太重要。5.6調(diào)度算法舉例5.6.1傳統(tǒng)UNIX的進程調(diào)度5.6.2Windows2000返回5.6.1傳統(tǒng)UNIX的進程調(diào)度調(diào)度由0號進程完成（始終在核心態(tài)執(zhí)行，與其他進程并不完全一樣）。時機：進程由核心態(tài)轉(zhuǎn)入用戶態(tài)時：在每次執(zhí)行核心代碼之后返回用戶態(tài)之前，檢查各就緒進程的優(yōu)先級并進行調(diào)度。如中斷――進程回到就緒隊列進程主動放棄處理機時：進程申請系統(tǒng)資源而未得到滿足（如read），或進行進程間同步而暫停（如wait或pause），進程退出（如exit）――進程進入阻塞隊列或exit狀態(tài)。未設(shè)置作業(yè)調(diào)度，進程調(diào)度采用基于時間片的多級反饋隊列算法，進程優(yōu)先級分為核心優(yōu)先級和用戶優(yōu)先級。1.調(diào)度時機2.調(diào)度標(biāo)志UNIXSystemV中有三個與調(diào)度有關(guān)的標(biāo)志：runrun：表示要求進行調(diào)度，當(dāng)發(fā)現(xiàn)有就緒進程優(yōu)先級高于當(dāng)前進程時，設(shè)置該標(biāo)識。在wakeup,setrun,setpri（設(shè)置優(yōu)先級）過程和時鐘中斷處理例程進行設(shè)置。runin：表示內(nèi)存中沒有適當(dāng)?shù)倪M程可以換出或內(nèi)存無足夠空間換入一個外存就緒進程。（內(nèi)存緊張）runout：表示外存交換區(qū)中沒有適當(dāng)?shù)倪M程可以換入。（交換區(qū)緊張）3.用戶優(yōu)先級進程在用戶態(tài)和核心態(tài)的優(yōu)先級是不同的，這里說的是用戶態(tài)進程的優(yōu)先級。它是基于執(zhí)行時間的動態(tài)優(yōu)先級，進程優(yōu)先級可為0~127之間的任一整數(shù)。優(yōu)先數(shù)越大，優(yōu)先級越低。0~49之間的優(yōu)先級為系統(tǒng)內(nèi)核保留用戶態(tài)下的進程優(yōu)先級為50~127之間系統(tǒng)設(shè)置部分：PUSER和NZERO是基本用戶優(yōu)先數(shù)的閾值，分別為25和20CPU使用時間部分：P_CPU表示該進程最近一次CPU使用時間。每次時鐘中斷則該值加1（最多可達80）。如果時鐘中斷的周期為16.6ms，則每秒鐘過后將該值為60。新創(chuàng)建進程的P_CPU值為0，因而具有較高的優(yōu)先級。不同系統(tǒng)對P_CPU的計算方法有所不同。有的固定一個因子，有的會考慮系統(tǒng)負荷。用戶設(shè)置部分：P_nice是用戶可以通過系統(tǒng)調(diào)用設(shè)置的一個優(yōu)先級偏移值。默認為20。超級用戶可以設(shè)置其在0到39之間，而普通用戶只能增大該值（即降低優(yōu)先級）。在UNIXSystemV中，進程優(yōu)先數(shù)：P_pri=P_CPU/2+PUSER+P_nice+NZERO4.核心優(yōu)先級內(nèi)核把進程阻塞事件與一個睡眠優(yōu)先級（0~49）聯(lián)系起來；當(dāng)進程從阻塞中醒來時，可及時進行處理。如：磁盤I/O操作對應(yīng)的睡眠優(yōu)先級為20終端輸入操作對應(yīng)的睡眠優(yōu)先級為29。核心優(yōu)先級分為可中斷和不可中斷兩類優(yōu)先級。當(dāng)一個軟中斷信號到達時，若進程正在可中斷優(yōu)先級上阻塞，則進程立即被喚醒；若正在不可中斷優(yōu)先級上，則繼續(xù)阻塞。其中：不可中斷優(yōu)先級：對換，等待磁盤I/O，等待緩沖區(qū)，等待文件索引結(jié)點－－關(guān)鍵操作，應(yīng)該很快完成可中斷優(yōu)先級：等待tty（虛終端）I/O，等待子進程退出5.調(diào)度的實現(xiàn)：分三個階段檢查是否作上下文切換（runrun標(biāo)志）和核心是否允許作上下文切換（對核心的各種數(shù)據(jù)結(jié)構(gòu)的操作都已經(jīng)完成，核心處于正確的狀態(tài)）。如果允許作上下文切換，則保存當(dāng)前進程的上下文?；謴?fù)0號進程的上下文，然后執(zhí)行0號進程，尋找最高優(yōu)先級的就緒進程，如果沒有這樣的進程存在，則執(zhí)行idle過程。如果有這樣的進程存在，則該進程作為當(dāng)前進程分派處理機，保存0號進程的上下文?；謴?fù)當(dāng)前進程的上下文，執(zhí)行該進程。5.6.2Windows2000每個優(yōu)先級的就緒進程排成一個先進先出隊列；當(dāng)一個線程狀態(tài)變成就緒時，它可能立即運行或排到相應(yīng)優(yōu)先級隊列的尾部?？傔\行優(yōu)先級最高的就緒線程；1.Windows2000的線程調(diào)度概述調(diào)度單位是線程而不是進程，采用嚴(yán)格的搶先式動態(tài)優(yōu)先級調(diào)度，依據(jù)優(yōu)先級和分配時間片來調(diào)度。完全的事件驅(qū)動機制，在被搶先前沒有保證的運行時間；沒有形式的調(diào)度循環(huán)；時間片用完事件；等待結(jié)束事件；主動掛起事件；在同一優(yōu)先級的各線程按時間片輪轉(zhuǎn)算法進行調(diào)度；在多處理機系統(tǒng)中多個線程并行運行；2.Windows2000的中斷優(yōu)先級3.NT線程的優(yōu)先級實時(real-time)：從16到31，如設(shè)備監(jiān)控線程?？勺儍?yōu)先級(variable-priority)：從1到15（級別0保留為系統(tǒng)使用）。線程的基本優(yōu)先級=[進程的基本優(yōu)先級-2，進程的基本優(yōu)先級+2]，由應(yīng)用程序控制線程的動態(tài)優(yōu)先級=[進程的基本優(yōu)先級-2,31]，由NT核心控制從0到31，數(shù)值越大，優(yōu)先級越高。分為兩類NT的線程優(yōu)先級（BasePriority）由進程優(yōu)先級類（PriorityClass）和線程優(yōu)先級偏移（PriorityLevel）構(gòu)成，分別由相關(guān)函數(shù)控制。進程優(yōu)先級類線程優(yōu)先級偏移有關(guān)API進程優(yōu)先級類函數(shù)：GetPriorityClass（讀取）SetPriorityClass（設(shè)置）線程優(yōu)先級偏移：GetThreadPriority（讀?。㏒etThreadPriority（設(shè)置）4.線程調(diào)度數(shù)據(jù)結(jié)構(gòu)就緒位圖(KiReadySummary)為了提高調(diào)度速度，Windows2000維護了一個稱為就緒位圖(KiReadySummary)的32位量。就緒位圖中的每一位指示一個調(diào)度優(yōu)先級的就緒隊列中是否有線程等待運行。B0與調(diào)度優(yōu)先級0相對應(yīng)，B1與調(diào)度優(yōu)先級1相對應(yīng)，等待?？臻e位圖(KiIdleSummary)Windows2000還維護一個稱為空閑位圖(KiIdleSummary)的32位量?？臻e位圖中的每一位指示一個處理機是否處于空閑狀態(tài)。調(diào)度器自旋鎖(KiDispatcherLock)為了防止調(diào)度器代碼與線程在訪問調(diào)度器數(shù)據(jù)結(jié)構(gòu)時發(fā)生沖突，處理機調(diào)度僅出現(xiàn)在DPC/調(diào)度層次。但在多處理機系統(tǒng)中，修改調(diào)度器數(shù)據(jù)結(jié)構(gòu)需要額外的步驟來得到內(nèi)核調(diào)度器自旋鎖(KiDispatcherLock)，以協(xié)調(diào)各處理機對調(diào)度器數(shù)據(jù)結(jié)構(gòu)的訪問。與線程調(diào)度相關(guān)的內(nèi)核變量5.Windows2000中的start命令可指定進程啟動時的優(yōu)先級；start/highmyprog6.線程時間配額(Quantum)時間配額是一個線程從進入運行狀態(tài)到Windows2000檢查是否有其他優(yōu)先級相同的線程需要開始運行之間的時間總和。一個線程用完了自己的時間配額時，如果沒有其它相同優(yōu)先級線程，Windows2000將重新給該線程分配一個新的時間配額，并繼續(xù)運行。每個線程都有一個代表本次運行最大時間長度的時間配額。時間配額不是一個時間長度值，而一個稱為配額單位(quantumunit)的整數(shù)。時間配額的計算缺省時，在Windows2000專業(yè)版中線程時間配額為6；而在Windows2000服務(wù)器中線程時間配額為36。在Windows2000服務(wù)器中取較長缺省時間配額的原因是，保證客戶請求所喚醒的服務(wù)器應(yīng)用有足夠的時間在它的時間配額用完前完成客戶的請求并回到等待狀態(tài)。每次時鐘中斷，時鐘中斷服務(wù)例程從線程的時間配額中減少一個固定值(3)。如果沒有剩余的時間配額，系統(tǒng)將觸發(fā)時間配額用完處理，選擇另外一個線程進入運行狀態(tài)。在Windows2000專業(yè)版中，由于每個時鐘中斷時減少的時間配額為3，一個線程的缺省運行時間為2個時鐘中斷間隔；在Windows2000服務(wù)器中，一個線程的缺省運行時間為12個時鐘中斷間隔。如果時鐘中斷出現(xiàn)時系統(tǒng)正在處在DPC/線程調(diào)度層次以上(如系統(tǒng)正在執(zhí)行一個延遲過程調(diào)用或一個中斷服務(wù)例程)，當(dāng)前線程的時間配額仍然要減少。甚至在整個時鐘中斷間隔期間，當(dāng)前線程一條指令也沒有執(zhí)行，它的時間配額在時鐘中斷中也會被減少。不同硬件平臺的時鐘中斷間隔是不同的，時鐘中斷的頻率是由硬件抽象層確定的，而不是內(nèi)核確定的。例如，大多數(shù)x86單處理機系統(tǒng)的時鐘中斷間隔為10毫秒，大多數(shù)x86多處理機系統(tǒng)的時鐘中斷間隔為15毫秒。在等待完成時允許減少部分時間配額。當(dāng)優(yōu)先級小于14的線程執(zhí)行一個等待函數(shù)(如WaitForSingleObject或WaitForMultipleObjects)時，它的時間配額被減少1個時間配額單位。當(dāng)優(yōu)先級大于等于14的線程在執(zhí)行完等待函數(shù)后，它的時間配額被重置。這種部分減少時間配額的做法可解決線程在時鐘中斷觸發(fā)前進入等待狀態(tài)所產(chǎn)生的問題。如果不進行這種部分減少時間配額操作，一個線程可能永遠不減少它的時間配額。例如，一個線程運行一段時間后進入等待狀態(tài)，再運行一段時間后又進入等待狀態(tài)，但在時鐘中斷出現(xiàn)時它都不是當(dāng)前線程，則它的時間配額永遠也不會因為運行而減少。時間配額的控制在系統(tǒng)注冊庫中的一個注冊項“HKLM\SYSTEM\CurrentControlSet\Control\PriorityControl\Win32PrioritySeparation”，允許用戶指定線程時間配額的相對長度(長或短)和前臺進程的進程的時間配額是否加長。該注冊項為6位，分成3個字段，每個字段占2位。時間配額長度字段(Shortvs.Long)：1表示長時間配額，2表示短時間配額。0或3表示缺省設(shè)置(Windows2000專業(yè)版的缺省設(shè)置為短時間配額，Windows2000服務(wù)器版的缺省設(shè)置為長時間配額)。前后臺變化字段(Variablevs.Fixed)：1表示改變前臺進程時間配額，2表示前后臺進程的時間配額相同。0或3表示缺省設(shè)置(Windows2000專業(yè)版的缺省設(shè)置為改變前臺進程時間配額，Windows2000服務(wù)器版的缺省設(shè)置為前后臺進程的時間配額相同)。前臺進程時間配額字段(ForegroundQuantumBoost)：該字段的取值只能是0、1或2(取3是非法的，被視為2)。該字段是一個時間配額表索引，用于設(shè)置前后臺進程的時間配額，后臺進程的時間配額為第一項，前臺進程的時間配額為第二項。該字段的值保存在內(nèi)核變量PsPrioritySeparation。時間配額的設(shè)置如果當(dāng)前窗口切換到一個優(yōu)先級高于空閑優(yōu)先級類的進程中某線程，Win32子系統(tǒng)將用注冊項Win32PrioritySeparation的前臺進程時間配額字段作為索引，依據(jù)一個有3個元素的數(shù)組PspForegroundQuantum中取值，來設(shè)置該進程中所有線程的時間配額。該數(shù)組的內(nèi)容由注冊項Win32PrioritySeparation的另外2個字段確定。提高前臺線程優(yōu)先級的潛在問題假設(shè)用戶首先啟動了一個運行時間很長的電子表格計算程序，然后切換到一個計算密集型的應(yīng)用(如一個需要復(fù)雜圖形顯示的游戲)。如果前臺的游戲進程提高它的優(yōu)先級，后臺的電子表格將會幾乎得不到CPU時間。但增加游戲進程的時間配額，則不會停止電子表格計算的執(zhí)行，只是給游戲進程的CPU時間多一些。如果用戶希望運行一個交互式應(yīng)用程序時的優(yōu)先級比其他交互進程的優(yōu)先級高，可利用任務(wù)管理器來修改進程的優(yōu)先級類型為中上或高級，也可利用命令行在啟動應(yīng)用時使用命令“start/abovenormal”或“start/high”來設(shè)置進程優(yōu)先級類型。7.Windows2000線程調(diào)度主動切換許多Win32等待函數(shù)調(diào)用(如WaitForSingleObject或WaitForMultipleObjects等)都使線程等待某個對象，等待的對象可能有事件、互斥信號量、資源信號量、I/O操作、進程、線程、窗口消息等。通常進入等待狀態(tài)線程的時間配額不會被重置，而是在等待事件出現(xiàn)時，線程的時間配額被減1，相當(dāng)于1/3個時鐘間隔；如果線程的優(yōu)先級大于等于14，在等待事件出現(xiàn)時，線程的優(yōu)先級被重置。搶先當(dāng)一個高優(yōu)先級線程進入就緒狀態(tài)時，正在處于運行狀態(tài)的低優(yōu)先級線程被搶先?？赡茉谝韵聝煞N情況下出現(xiàn)搶先：高優(yōu)先級線程的等待完成，即一個線程等待的事件出現(xiàn)。一個線程的優(yōu)先級被增加或減少。用戶態(tài)下運行的線程可以搶先內(nèi)核態(tài)下運行的線程。在判斷一個線程是否被搶先時，并不考慮線程處于用戶態(tài)還是內(nèi)核態(tài)，調(diào)度器只是依據(jù)線程優(yōu)先級進行判斷。當(dāng)線程被搶先時，它被放回相應(yīng)優(yōu)先級的就緒隊列的隊首。處于實時優(yōu)先級的線程在被搶先時，時間配額被重置為一個完整的時間片；處于動態(tài)優(yōu)先級的線程在被搶先時，時間配額不變，重新得到處理機使用權(quán)后將運行到剩余的時間配額用完。時間片用完線程完整用完一個規(guī)定的時間片值時，重新賦予新時間片值，優(yōu)先級降一級（不低于基本優(yōu)先級），放在相應(yīng)優(yōu)先級就緒隊列的尾部；如果剛用完時間配額的線程優(yōu)先級降低了，Windows2000將尋找一個優(yōu)先級高于剛用完時間配額線程的新設(shè)置值的就緒線程。如果剛用完時間配額的線程的優(yōu)先級沒有降低，并且有其他優(yōu)先級相同的就緒線程，Windows2000將選擇相同優(yōu)先級的就緒隊列中的下一個線程進入運行狀態(tài)，剛用完時間配額的線程被排到就緒隊列的隊尾(即分配一個新的時間配額并把線程狀態(tài)從運行狀態(tài)改為就緒狀態(tài))。如果沒有優(yōu)先級相同的就緒線程可運行，剛用完時間配額的線程將得到一個新的時間配額并繼續(xù)運行。結(jié)束(Termination)

當(dāng)線程完成運行時，它的狀態(tài)從運行狀態(tài)轉(zhuǎn)到終止?fàn)顟B(tài)。線程完成運行的原因可能是通過調(diào)用ExitThread而從主函數(shù)中返回或通過被其他線程通過調(diào)用TerminateThread來終止。如果處于終止?fàn)顟B(tài)的線程對象上沒有未關(guān)閉的句柄，則該線程將被從進程的線程列表中刪除，相關(guān)數(shù)據(jù)結(jié)構(gòu)將被釋放。優(yōu)先級調(diào)整線程由于調(diào)用等待函數(shù)而阻塞時，減少一個時間片，并依據(jù)等待事件類型提高優(yōu)先級；如等待鍵盤事件比等待磁盤事件的提高幅度大。在下列5種情況下，Windows2000會提升線程的當(dāng)前優(yōu)先級：I/O操作完成信號量或事件等待結(jié)束前臺進程中的線程完成一個等待操作由于窗口活動而喚醒圖形用戶接口線程線程處于就緒狀態(tài)超過一定時間，但沒能進入運行狀態(tài)(處理機饑餓)線程優(yōu)先級提升的目的是改進系統(tǒng)吞吐量、響應(yīng)時間等整體特征，解決線程調(diào)度策略中潛在的不公正性。但它也不是完美的，它并不會使所有應(yīng)用都受益。Windows2000永遠不會提升實時優(yōu)先級范圍內(nèi)(16至31)的線程優(yōu)先級。I/O操作完成后的線程優(yōu)先級提升在完成I/O操作后，Windows2000將臨時提升等待該操作線程的優(yōu)先級，以保證等待I/O操作的線程能有更多的機會立即開始處理得到的結(jié)果。為了避免I/O操作導(dǎo)致對某些線程的不公平偏好，在I/O操作完成后喚醒等待線程時將把該線程的時間配額減1。線程優(yōu)先級的實際提升值是由設(shè)備驅(qū)動程序決定的。與I/O操作相關(guān)的線程優(yōu)先級提升建議值在文件“Wdm.h”或“Ntddk.h”中。設(shè)備驅(qū)動程序在完成I/O請求時通過內(nèi)核函數(shù)IoCompleteRequest來指定優(yōu)先級提升的幅度。線程優(yōu)先級的提升幅度與I/O請求的響應(yīng)時間要求是一致的，響應(yīng)時間要求越高，優(yōu)先級提升幅度越大。線程優(yōu)先級提升的建議值線程優(yōu)先級提升是以線程的基本優(yōu)先級為基點的，不是以線程的當(dāng)前優(yōu)先級為基點。當(dāng)用完它的一個時間配額后，線程會降低一個優(yōu)先級，并運行另一個時間配額。這個降低過程會一直進行下去，直到線程的優(yōu)先級降低至原來的基本優(yōu)先級。優(yōu)先級提升策略僅適用于可變優(yōu)先級范圍(0到15)內(nèi)的線程。不管線程的優(yōu)先級提升幅度有多大，提升后的優(yōu)先級都不會超過15而進入實時優(yōu)先級。等待事件和信號量后的線程優(yōu)先級提升當(dāng)一個等待執(zhí)行事件對象或信號量對象的線程完成等待后，它的優(yōu)先級將提升一個優(yōu)先級。阻塞于事件或信號量的線程得到的處理機時間比處理機繁忙型線程要少，這種提升可減少這種不平衡帶來的影響。

SetEvent、PulseEvent或ReleaseSemaphore函數(shù)調(diào)用可導(dǎo)致事件對象或信號量對象等待的結(jié)束。提升是以線程的基本優(yōu)先級為基點的，而不是線程的當(dāng)前優(yōu)先級。提升后的優(yōu)先級永遠不會超過15。在等待結(jié)束時，線程的時間配額被減1，并在提升后的優(yōu)先級上執(zhí)行完剩余的時間配額；隨后降低1個優(yōu)先級，運行一個新的時間配額，直到優(yōu)先級降低到初始的基本優(yōu)先級。前臺線程在等待結(jié)束后的優(yōu)先級提升對于前臺進程中的線程，一個內(nèi)核對象上的等待操作完成時，內(nèi)核函數(shù)KiUnwaitThread會提升線程的當(dāng)前優(yōu)先級(不是線程的基本優(yōu)先級)，提升幅度為變量PsPrioritySeparation的值。在前臺應(yīng)用完成它的等待操作時小幅提升它的優(yōu)先級，以使它更有可能馬上進入運行狀態(tài)，有效改進前臺應(yīng)用的響應(yīng)時間特征。用戶不能禁止這種優(yōu)先級提升，甚至是在用戶已利用Win32的函數(shù)SetThreadPriorityBoost禁止了其他的優(yōu)先級提升策略時，也是如此。圖形用戶接口線程被喚醒后的優(yōu)先級提升擁有窗口的線程在被窗口活動喚醒(如收到窗口消息)時將得到一個幅度為2的額外優(yōu)先級提升。窗口系統(tǒng)(Win32k.sys)在調(diào)用函數(shù)KeSetEvent時實施這種優(yōu)先級提升，KeSetEvent函數(shù)調(diào)用設(shè)置一個事件，用于喚醒一個圖形用戶接口線程。這種優(yōu)先級提升的原因是改進交互應(yīng)用的響應(yīng)時間。對處理機饑餓線程的優(yōu)先級提升系統(tǒng)線程“平衡集管理器(balancesetmanager)”

會每秒鐘檢查一次就緒隊列，是否存在一直在就緒隊列中排隊超過300個時鐘中斷間隔的線程。如果找到這樣的線程，平衡集管理器將把該線程的優(yōu)先級提升到15，并分配給它一個長度為正常值兩倍的時間配額；當(dāng)被提升線程用完它的時間配額后，該線程的優(yōu)先級立即衰減到它原來的基本優(yōu)先級。如果在該線程結(jié)束前出現(xiàn)其他高優(yōu)先級的就緒線程，該線程會被放回就緒隊列，并在就緒隊列中超過另外300個時鐘中斷間隔后再次被提升優(yōu)先級。平衡集管理器只掃描16個就緒線程。如果就緒隊列中有更多的線程，它將記住暫停時的位置，并在下一次開始時從當(dāng)前位置開始掃描。平衡集管理器在每次掃描時最多提升10個線程的優(yōu)先級。如果在一次掃描中已提升了10個線程的優(yōu)先級，平衡集管理器會停止本次掃描，并在下一次開始時從當(dāng)前位置開始掃描。這種算法并不能解決所有優(yōu)先級倒置的問題，但它很有效。8.對稱多處理機系統(tǒng)上Windows2000的線程調(diào)度親合關(guān)系A(chǔ)ffinity描述該線程可在哪些處理機上運行。線程的親合掩碼是從進程的親合掩碼繼承得到的。缺省時，所有進程(即所有線程)的親合掩碼為系統(tǒng)中所有可用處理機的集合。應(yīng)用程序通過調(diào)用SetProcessAffinityMask或SetThreadAffinityMa