操作系統(tǒng)課件 2-處理器管理

操作系統(tǒng)教程(第4版)

第二章處理器管理

高等教育出版社出版2008年3月第二章處理器管理2.1中央處理器2.2中斷技術(shù)2.3進(jìn)程及其實現(xiàn)2.4線程及其實現(xiàn)2.5Linux進(jìn)程和線程2.6Windows2003進(jìn)程和線程2.7處理器調(diào)度2.8作業(yè)的管理與調(diào)度2.9處理器調(diào)度算法2.10Linux調(diào)度算法2.11Windows2003調(diào)度算法2.1中央處理器

2.1.1處理器2.1.2程序狀態(tài)字寄存器2.1.1處理器

1單處理器和多處理器系統(tǒng)共享存儲(緊密耦合)多處理機系統(tǒng)和分布存儲(松散耦合)多處理機系統(tǒng)。2寄存器(1)計算機系統(tǒng)的處理器包括一組寄存器，其個數(shù)根據(jù)機型的不同而不同，它們構(gòu)成了一級存儲，比主存容量小，但訪問速度快。這組寄存器所存儲的信息與程序的執(zhí)行有很大關(guān)系，構(gòu)成了處理器現(xiàn)場。寄存器(2)

通用寄存器--EAX，EBX，ECX和EDX指針及變址寄存器--ESP，EBP，ESI及EDI段選擇符寄存器--CS、DS、SS、ES、FS、GS指令指針寄存器和標(biāo)志寄存器--EIP、EFLAGS控制寄存器--CR0，CR1，CR2和CR3外部設(shè)備使用的寄存器3特權(quán)指令與非特權(quán)指令(1)機器指令的集合稱指令系統(tǒng)

(1)數(shù)據(jù)處理類指令；

(2)轉(zhuǎn)移類指令；

(3)數(shù)據(jù)傳送類指令；

(4)移位與字符串指令；

(5)I/O類指令。特權(quán)指令與非特權(quán)指令(2)從資源管理和控制程序執(zhí)行的角度出發(fā)，必須把指令系統(tǒng)中的指令分作兩部分：特權(quán)指令和非特權(quán)指令。特權(quán)指令是指只能提供給操作系統(tǒng)的核心程序使用的指令，如啟動I/O設(shè)備、設(shè)置時鐘、控制中斷屏蔽位、清主存、建立存儲鍵，加載PSW等。4處理器狀態(tài)處理器怎么知道當(dāng)前是操作系統(tǒng)還是一般用戶程序在運行呢?處理器狀態(tài)標(biāo)志:管理狀態(tài)（特權(quán)狀態(tài)、系統(tǒng)模式、特態(tài)或管態(tài)）和用戶狀態(tài)（目標(biāo)狀態(tài)、用戶模式、常態(tài)或目態(tài))。處理器狀態(tài)的轉(zhuǎn)換。處理器處于管理狀態(tài)時，程序可以執(zhí)行全部指令，使用所有資源，具有改變處理器狀態(tài)的能力；處理器處于用戶狀態(tài)時，程序只能執(zhí)行非特權(quán)指令I(lǐng)ntelPentium的處理器狀態(tài)有四種，支持4個保護(hù)級別，0級權(quán)限最高，3級權(quán)限最低2.1.5程序狀態(tài)字寄存器(1)計算機如何知道當(dāng)前處于何種工作狀態(tài)？這時能否執(zhí)行特權(quán)指令？通常操作系統(tǒng)都引入程序狀態(tài)字PSW（ProgramStatusWord）來區(qū)別不同的處理器工作狀態(tài)PSW用來控制指令執(zhí)行順序并保留和指示與程序有關(guān)的系統(tǒng)狀態(tài)，主要作用是實現(xiàn)程序狀態(tài)的保護(hù)和恢復(fù)每個程序都有一個與其執(zhí)行相關(guān)的PSW，每個處理器都設(shè)置一個PSW寄存器。程序占有處理器執(zhí)行，它的PSW將占有PSW寄存器程序狀態(tài)字寄存器(2)

PSW寄存器包括以下內(nèi)容：程序基本狀態(tài)：

(1)程序計數(shù)器；

(2)條件碼；

(3）處理器狀態(tài)位。中斷碼。保存程序執(zhí)行時當(dāng)前發(fā)生的中斷事件。中斷屏蔽位。指明程序執(zhí)行中發(fā)生中斷事件時，是否響應(yīng)出現(xiàn)的中斷事件。

IBM360/370系列計算機

程序狀態(tài)字的基本格式

XXXXXXXXXXXXXXXX8位系統(tǒng)屏蔽4位CMWP字段4位程序屏蔽4位保護(hù)鍵16位中斷碼字段指令長和條件碼24位指令地址IntelPentium程序狀態(tài)字IntelPentium中，PSW由標(biāo)志寄存器EFLAGS和指令指針寄存器EIP組成，均為32位。EFLAGS的低16位稱FLAGS，標(biāo)志可劃分為三組：狀態(tài)標(biāo)志、控制標(biāo)志、系統(tǒng)標(biāo)志。2.2中斷技術(shù)2.2.1中斷概念2.2.2中斷源分類2.2.3中斷和異常的響應(yīng)及服務(wù)2.2.4中斷事件處理2.2.5中斷優(yōu)先級和多重中斷2.2.6Linux中斷處理2.2.7Windows2003中斷處理2.2.1中斷的概念

?請求系統(tǒng)服務(wù)，?實現(xiàn)并行工作，?處理突發(fā)事件，?滿足實時要求，都需要打斷處理器正常的工作，為此，提出了中斷概念。中斷的定義

中斷是指程序執(zhí)行過程中，遇到急需處理的事件時，暫時中止CPU上現(xiàn)行程序的運行，轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序，待處理完成后再返回原程序被中斷處或調(diào)度其他程序執(zhí)行的過程。2.2.2中斷源分類(1)

從中斷事件的性質(zhì)和激活的手段來說，可以分成兩類：?強迫性中斷事件強迫性中斷事件不是正在運行的程序所期待的，而是由于某種事故或外部請求信息所引起的，分為：機器故障中斷事件。程序性中斷事件。外部中斷事件。輸入輸出中斷事件。?自愿性中斷事件自愿性中斷事件是正在運行的程序所期待的事件。

中斷源分類(2)

按中斷事件的性質(zhì)和激活方式劃分

運行程序中斷處理程序中斷裝置中斷處理程序中斷裝置機器故障中斷事件程序性中斷事件外部中斷事件輸入輸出中斷事件運行程序訪管指令中斷源分類(3)

硬中斷軟中斷外中斷(中斷、異步中斷)內(nèi)中斷(異常、同步中斷)信號軟件中斷按事件來源和實現(xiàn)手段分類中斷源分類(4)

?外中斷(中斷或異步中斷)--是指來自處理器之外的中斷信號，包括時鐘中斷、鍵盤中斷、它機中斷和設(shè)備中斷等；外中斷又分可屏蔽中斷和不可屏蔽中斷，每個不同中斷具有不同的中斷優(yōu)先級，表示事件的緊急程度，在處理高一級中斷時，往往會屏蔽部分或全部低級中斷。?內(nèi)中斷(異?；蛲街袛?--是指來自處理器內(nèi)部，通常由于程序執(zhí)行中，發(fā)現(xiàn)與當(dāng)前指令關(guān)聯(lián)的、不正常的、或是錯誤的事件。中斷和異常的區(qū)別

?中斷是由與現(xiàn)行指令無關(guān)的中斷信號觸發(fā)的(異步的)，且中斷的發(fā)生與CPU處在用戶模式或內(nèi)核模式無關(guān)，在兩條機器指令之間才可響應(yīng)中斷，一般來說，中斷處理程序提供的服務(wù)不是為當(dāng)前進(jìn)程所需的；?異常是由處理器正在執(zhí)行現(xiàn)行指令而引起的，一條指令執(zhí)行期間允許響應(yīng)異常，異常處理程序提供的服務(wù)是為當(dāng)前進(jìn)程所用的。異常包括很多方面，有出錯(fault)，也有陷入(trap)等。

Linux的異常

?Linux為例，異常按錯誤報告方式分四種：

故障、陷阱、終止、編程異常。

?故障發(fā)生時保存的返回指令地址指向觸發(fā)異常的當(dāng)前那條指令，故障處理后會重新執(zhí)行。編程異常和陷阱是由于執(zhí)行訪管指令引起的同步操作，異常返回時，回到觸發(fā)異常的下一條指令。

硬中斷與軟中斷

中斷和異常要通過硬件設(shè)施來產(chǎn)生中斷請求，是硬中斷。軟中斷是利用硬中斷的概念，用軟件方法對中斷機制進(jìn)行模擬，實現(xiàn)宏觀上的異步執(zhí)行效果。軟中斷分兩種：“信號”和“軟件中斷”。中斷的通常用法

“中斷”(硬中斷)用于外部設(shè)備對CPU的中斷(中斷的是正在運行的任何程序)，轉(zhuǎn)向中斷處理程序上半部分執(zhí)行；“異?！?硬中斷)因指令執(zhí)行不正常而中斷CPU(中斷的是正在執(zhí)行這條指令的程序)，轉(zhuǎn)向異常處理程序；“軟件中斷”(軟中斷)用于硬中斷服務(wù)程序?qū)?nèi)核的中斷，在上半部分中發(fā)出軟件中斷(即標(biāo)記下半部分)，使得中斷下半部分在適當(dāng)時刻獲得處理；“信號”(軟中斷)用于內(nèi)核或進(jìn)程對某個進(jìn)程的中斷，通知進(jìn)程某個特定事件發(fā)生或迫使進(jìn)程執(zhí)行信號處理程序。中斷機制與信號機制進(jìn)行類比

相同點是：(1)概念上是一致的，(2)兩者都是“異步”的，(3)實現(xiàn)上均采用“向量表”，(4）均具有“屏蔽”設(shè)施。區(qū)別是：中斷機制由硬件與軟件相結(jié)合來實現(xiàn)，而信號機制由軟件實現(xiàn)；中斷向量表和中斷處理程序(由系統(tǒng)提供)均在系統(tǒng)空間，而信號向量表雖在系統(tǒng)空間，但信號處理程序由應(yīng)用程序提供，并在用戶空間執(zhí)行。硬中斷與軟中斷BH進(jìn)行類比

(1)數(shù)組bh_base［］相當(dāng)于硬件中斷機制中的數(shù)組irq_desc[]；(2）bh_active在概念上相當(dāng)于硬件的“中斷請求寄存器”，而bh_mask相當(dāng)于硬件中的“中斷屏蔽寄存器”；(3)執(zhí)行一個BH函數(shù)時，就通過mark_bh()將bh_active中的某位設(shè)成1，相當(dāng)于中斷源發(fā)出(軟件)中斷請求，所設(shè)置的具體標(biāo)志位則類似于“中斷向量”；(4)如果bh_mask中的相應(yīng)位是l，就會在每次執(zhí)行完do_IRQ（）中的中斷服務(wù)程序后，及每次系統(tǒng)調(diào)用結(jié)束后，在函數(shù)do_bottom_half（）中執(zhí)行相應(yīng)BH函數(shù)，而do_bottom_half（），則類似于do_IRQ()。硬中斷或軟中斷處理延時問題

CPU接到和響應(yīng)硬中斷或異常后會立即調(diào)用中斷或異常處理程序處理；對于接收到的信號或軟件中斷，此時由于進(jìn)程未必占有處理器運行或內(nèi)核正在執(zhí)行敏感性操作，通常會有一定時間的延遲，在適當(dāng)?shù)臅r刻內(nèi)核或相關(guān)進(jìn)程才能加以處理。信號和軟件中斷雖然都由軟件產(chǎn)生，并都由軟件處理，但它們的中斷來源、使用場合、實現(xiàn)手段并不相同。中斷/異常響應(yīng)要做四件事發(fā)現(xiàn)中斷源：保護(hù)現(xiàn)場：轉(zhuǎn)向處理中斷/異常事件的處理程序：恢復(fù)現(xiàn)場：IBM中大型機中斷響應(yīng)過程

外中斷舊PSW訪管中斷舊PSW程序中斷舊PSW機器故障中斷舊PSWI/O中斷舊PSW外中斷新PSW訪管中斷新PSW程序中斷新PSW機器故障中斷新PSWI/O中斷新PSW18202830385860687078現(xiàn)行PSW②中斷時保存現(xiàn)行PSW③中斷時裝入現(xiàn)行PSW④中斷后恢復(fù)PSW主存專用雙字單元(16進(jìn)制)①裝配中斷碼

IBMPC機中斷的響應(yīng)過程

IPCSPSW現(xiàn)行PSW寄存器新IP新CS老IP老CS老PSW新棧頂主存新PSW2.2.4中斷事件處理1中斷和異常的一般處理過程2硬件故障中斷3程序性中斷4I/O中斷5訪管中斷

6時鐘中斷(1)時鐘是操作系統(tǒng)進(jìn)行調(diào)度工作的重要工具，如讓分時進(jìn)程作時間片輪轉(zhuǎn)、讓實時進(jìn)程定時發(fā)出或接收控制信號、系統(tǒng)定時喚醒或阻塞一個進(jìn)程、對用戶進(jìn)程進(jìn)行記賬時鐘可分成絕對時鐘和間隔時鐘兩種時鐘中斷(2)

1)絕對時鐘服務(wù)提供以下功能的函數(shù)：update_clock()更新當(dāng)前時間；get_time()返回當(dāng)前時鐘值；set_clock()把當(dāng)前時間設(shè)置為新值。時鐘中斷(3)

2)間隔定時器進(jìn)程可被延遲、阻塞，直到被間隔定時器中斷信號喚醒，應(yīng)提供以下函數(shù)：delay(tdel)把調(diào)用進(jìn)程阻塞由參數(shù)tdel指定的時間長度，進(jìn)程保持阻塞直到本地時間到達(dá)進(jìn)程阻塞時的當(dāng)前時間+tdel的時刻。set_timer(tdel)硬件間隔定時器被設(shè)置為起始的遞減值tdel，當(dāng)該值達(dá)到0時，產(chǎn)生間隔時鐘中斷，調(diào)用timeout()函數(shù)進(jìn)行處理。

時鐘中斷(4)

3)邏輯定時器需要提供函數(shù)：tn=creat_ltime()：創(chuàng)建邏輯定時器，tn中存放返回標(biāo)識符。destroy_ltime(tn)：撤銷tn標(biāo)識的邏輯定時器。set_ltime(tn,tv)：把tv值裝到邏輯定時器tn中，當(dāng)該值為0時，產(chǎn)生時間到中斷。時鐘中斷(5)

(1)使用帶有絕對喚醒定時器的優(yōu)先級隊列硬件時鐘絕對時鐘間隔時鐘10312定時器隊列P1115P2135P3140P41500定時器隊列P1115P2135P5138P3140P41500時鐘中斷(6)

(2)使用帶有時間差值的優(yōu)先級隊列硬件時鐘間隔時鐘12定時器隊列P112P220P35P4100定時器隊列P112P220P53P32P41002.2.5中斷優(yōu)先級和多重中斷1中斷的優(yōu)先級2中斷的屏蔽3多重中斷事件的處理1中斷優(yōu)先級

計算機執(zhí)行的每一瞬間，可能有幾個中斷事件同時發(fā)生，中斷裝置如何來響應(yīng)同時發(fā)生的中斷呢?以不發(fā)生中斷丟失為前提，把緊迫程度相當(dāng)?shù)闹袛嘣礆w在同一級，緊迫程度差別大的中斷源歸在不同級，級別高的有優(yōu)先獲得響應(yīng)的權(quán)力，中斷裝置預(yù)定的這個響應(yīng)順序稱為中斷優(yōu)先級。

2中斷的屏蔽

?主機可允許或禁止某類中斷的響應(yīng)，如允許或禁止所有的I/O中斷、外部中斷、及某些程序性中斷。?有些中斷是不能被禁止的，例如，計算機中的自愿性訪管中斷就不能被禁止。

3多重中斷事件的處理

中斷正在進(jìn)行處理期間，CPU又響應(yīng)新的中斷事件，于是暫時停止正在運行的中斷處理程序，轉(zhuǎn)去執(zhí)行新的中斷處理程序，就叫多重中斷（又稱中斷嵌套）。處理方法：(1)串行處理，(2)嵌套處理，(3)即時處理。

2.2.6Linux中斷處理1Linux內(nèi)核處理流程中斷自陷慢中斷快中斷

進(jìn)程正在運行用戶態(tài)核心態(tài)上半部分處理

返回原進(jìn)程運行

排隊下半部分

快中斷處理

系統(tǒng)調(diào)用處理

從系統(tǒng)調(diào)用返回ret_from_sys_call

調(diào)用schedule()

調(diào)度新進(jìn)程運行運行用戶態(tài)調(diào)度下半部分do_bottom_half()/do_softirq()

處理積累的信號do_signal()restore_all中斷快中斷與慢中斷

?Linux中，區(qū)分快中斷和慢中斷兩類中斷事件。?處理慢中斷前需保存所有寄存器的內(nèi)容，而快中斷處理僅要保存被常規(guī)C函數(shù)修改的寄存器；慢中斷處理時，不屏蔽其他中斷信號，而快中斷處理時會屏蔽所有其他中斷；?慢中斷處理完畢后，通常不立即返回被中斷的進(jìn)程，而是進(jìn)入調(diào)度程序重新調(diào)度，調(diào)度結(jié)果未必是被中斷的進(jìn)程運行(是搶先式調(diào)度)。而快中斷處理完畢后，通?；謴?fù)現(xiàn)場返回被中斷的進(jìn)程繼續(xù)執(zhí)行(是非搶先式調(diào)度)。2下半部分處理概述中斷處理程序的特點什么是下半部分處理TophalfBottomhalfLinux各種下半部分機制

bottomhalf、taskqueue、tasklet、workqueueSoftirq3下半部分(bottomhalf)實現(xiàn)原理

BH數(shù)組、函數(shù)入口指針bh_base、函數(shù)安裝標(biāo)志bh_mask、函數(shù)處理標(biāo)志bh_activeBH的缺點bh-mask310031

··bh-active310bh-base下半部分處理函數(shù)4任務(wù)隊列(taskqueue)實現(xiàn)原理預(yù)定任務(wù)隊列：1)定時器隊列(TQ_TIMER)：2)即時隊列(TQ_IMMEDIATE)：3)進(jìn)程調(diào)度隊列(TQ_SCHEDULE)：4)磁盤隊列(TQ_DISK)：定時器Tophalf與bottomhalf協(xié)調(diào)工作的例子5小任務(wù)(tasklet)

tasklet能更好支持SMP，它基于軟中斷來實現(xiàn)，但比軟中斷接口簡單，鎖保護(hù)要求低；softirq保留給執(zhí)行頻率及時間要求特高的下半部分使用(如網(wǎng)絡(luò)和SCSI)，多數(shù)場合下可使用tasklet。使用tasklet的步驟：BH全局串行處理，不適應(yīng)SMP環(huán)境，而不同tasklet可同時運行于不同CPU上，當(dāng)然，系統(tǒng)保證相同tasklet不會同時在不同CPU上運行，在這種情形下，tasklet就不需要是可重入的。在新版Linux中，tasklet是建議的異步任務(wù)延遲執(zhí)行機制。6工作隊列workqueue

Linux2.5內(nèi)核引入-工作隊列，它把一個任務(wù)延遲，并交給內(nèi)核線程去完成，且該任務(wù)總是在進(jìn)程上下文中執(zhí)行，通過工作隊列執(zhí)行的代碼能占盡進(jìn)程上下文的優(yōu)勢，最重要的是工作隊列允許重新調(diào)度及阻塞。如果延遲執(zhí)行的任務(wù)需要阻塞，需要獲取信號量或需要獲得大量主存時，那么，可選擇工作隊列，否則可使用tasklet或softirq。7軟中斷softirq

Linux沿用最早BH思想，已實現(xiàn)了龐大和復(fù)雜的軟中斷子系統(tǒng)-softirq，它是一種軟中斷機制，又是一個框架，包括tasklet，及為網(wǎng)絡(luò)操作專門設(shè)計的軟中斷。最多可注冊32個軟中斷，目前版本預(yù)定義六個元素，enum{HI_SOFTIRQ,//高優(yōu)先級taskletTIMER_SOFTIRQ,//定時器下半部分NET_TX_SOFTIRQ,//發(fā)送網(wǎng)絡(luò)數(shù)據(jù)包NET_RX_SOFTIRQ,//接收網(wǎng)絡(luò)數(shù)據(jù)包SCSI_SOFTIRQ,//SCSI下半部分TASKLET_SOFTIRQ,//公共tasklet};軟中斷使用步驟：軟中斷執(zhí)行時機：2.2.7Windows2003中斷處理

Window2003中斷類型中斷有I/O設(shè)備、處理器時鐘或定時器等，可以啟用或禁用。中斷是異步事件，可能隨時發(fā)生，與處理器正在執(zhí)行的內(nèi)容無關(guān)。異常是同步事件，它是某一個特定指令執(zhí)行的結(jié)果。異常的例子是主存訪問錯誤、調(diào)試指令及被零除。內(nèi)核也將系統(tǒng)服務(wù)調(diào)用視作異常。硬件和軟件都可以產(chǎn)生中斷和異常，如總線出錯異常由硬件造成，而被零除異常是由軟件引起的；同樣，I/O設(shè)備可產(chǎn)生中斷，而內(nèi)核自身也可以發(fā)出中斷。

Windows2000/XP陷阱調(diào)度

中斷服務(wù)例程中斷服務(wù)例程中斷服務(wù)例程異常調(diào)度器虛存管理的頁面管理器中斷調(diào)度器系統(tǒng)服務(wù)調(diào)度器異常調(diào)度器陷阱處理程序異常幀虛擬地址異常硬件異常軟件異常系統(tǒng)服務(wù)調(diào)用中斷

Windows2000/XP中斷請求級

系統(tǒng)關(guān)閉高31掉電30處理器內(nèi)的中斷29時鐘28配置文件設(shè)備n………設(shè)備1Dispatch/DPC2APC1低0硬件中斷軟件中斷正常的線程執(zhí)行Windows2000/XP中斷屏蔽

高掉電處理器內(nèi)的中斷時鐘配置文件設(shè)備n………設(shè)備1在處理器A上被屏蔽的中斷Dispatch/DPCAPC低IRQL=時鐘處理器A在處理器B上被屏蔽的中斷IRQL=Dispatch/DPC處理器BWindows2000/XP硬件中斷處理

低（無）………高掉電處理器間的中斷時鐘設(shè)備n………設(shè)備1②中斷調(diào)度程序接收到中斷源的IRQL，用作查詢IDT的索引Dispatch/DPCAPC①有中斷產(chǎn)生線程調(diào)度程序/DPC處理程序系統(tǒng)關(guān)閉例程系統(tǒng)調(diào)電例程處理器間中斷處理程序時鐘處理程序設(shè)備nISR設(shè)備1ISRAPC處理程序③中斷調(diào)度程序跟隨該指針，調(diào)用相應(yīng)的處理程序Windows2000/XP軟件中斷處理

多數(shù)中斷由硬件產(chǎn)生，但內(nèi)核也為多種任務(wù)產(chǎn)生軟件中斷，包括：啟動線程調(diào)度、處理計時器到時、在特定線程的描述表中異步執(zhí)行一個過程及支持異步I/O等。延遲過程調(diào)用DPC軟件中斷延遲過程調(diào)用--DPC提交和執(zhí)行

高掉電………②如果IRQL降到比Dispatch/DPC級低，則DPC中斷發(fā)生。Dispatch/DPCAPC低①定時器到時，內(nèi)核排好DPC隊列，準(zhǔn)備釋放等候在定時器上的所有線程，然后內(nèi)核請求軟件中斷?！{(diào)度程序③DPC中斷之后，控制傳送給（線程）調(diào)度程序DPCDPCDPC④調(diào)度程序執(zhí)行DPC中的每一個DPC例程，然后使隊列變空。如果需要，調(diào)度程序還重新安排處理器異步過程調(diào)用

異步過程調(diào)用APC為用戶程序和系統(tǒng)代碼提供了一種在特殊用戶線程的描述表(特殊的地址空間)中執(zhí)行代碼的方法。用戶態(tài)APC和核心態(tài)APC

異常調(diào)度

異常是由運行程序的執(zhí)行產(chǎn)生的情況。異常處理工具，允許應(yīng)用程序在異常發(fā)生時可以得到控制。應(yīng)用程序可以固定這個狀態(tài)并返回到異常發(fā)生的地方展開堆棧，也可以向系統(tǒng)聲明不能識別異常，并繼續(xù)搜尋能處理異常的異常處理程序。除陷阱處理程序解決的異常外，所有異常均由異常調(diào)度程序提供服務(wù)，它的任務(wù)是找到能處理該異常的異常處理程序。如果異常產(chǎn)生于核心態(tài)，異常調(diào)度程序?qū)⒄{(diào)用一個例程來定位處理該異常的異常處理程序。沒有被處理的核心態(tài)異常是一種致命的系統(tǒng)錯誤。用戶態(tài)核心態(tài)系統(tǒng)服務(wù)調(diào)用陷阱處理程序系統(tǒng)服務(wù)調(diào)度程序系統(tǒng)服務(wù)調(diào)度表0123………n系統(tǒng)服務(wù)擴展系統(tǒng)服務(wù)2系統(tǒng)服務(wù)調(diào)度(1)

系統(tǒng)服務(wù)調(diào)度(2)

調(diào)用NtWriteFile開中斷NTOSKRNL.EXE中的KiSystemService執(zhí)行操作返回調(diào)用者NTOSKRNL.EXE中的NtWriteFile調(diào)用WIN32例程開中斷NTOSKRNL.EXE中的KiSystemService執(zhí)行操作返回調(diào)用者WIN32K.SYS中的服務(wù)入口點核心態(tài)軟件中斷軟件中斷調(diào)用WriteFile()Win32應(yīng)用程序調(diào)用NtWriteFile返回調(diào)用者KERNEL32.DLL中的WriteFileINT2E返回調(diào)用者NTDLL.DLL中的NtWriteFile調(diào)用USER及GDI服務(wù)應(yīng)用程序INT2E返回調(diào)用者GDI32.DLL或USER32.DLL用戶態(tài)WIN32專用WIN32專用所有子系統(tǒng)使用WIN32內(nèi)核APIWIN32USER及GDIAPI2.3進(jìn)程及其實現(xiàn)

2.3.1進(jìn)程的定義和屬性2.3.2進(jìn)程的狀態(tài)和轉(zhuǎn)換2.3.3進(jìn)程的描述和組成2.3.4進(jìn)程切換與模式切換2.3.5進(jìn)程的控制和管理2.3.1進(jìn)程的定義和性質(zhì)

?進(jìn)程是可并發(fā)執(zhí)行的程序在某個數(shù)據(jù)集合上的一次計算活動，也是操作系統(tǒng)進(jìn)行資源分配和保護(hù)的基本單位。

?進(jìn)程是一個既能用來共享資源，又能描述程序并發(fā)執(zhí)行過程的一個基本單位。操作系統(tǒng)為什么要引入進(jìn)程概念?原因1-刻畫系統(tǒng)的動態(tài)性，發(fā)揮系統(tǒng)的并發(fā)性，提高資源利用率。原因2-它能解決系統(tǒng)的“共享性”，正確描述程序的執(zhí)行狀態(tài)?！翱稍儆谩背绦颉翱稍偃搿背绦颉翱稍偃搿背绦蚓哂械男再|(zhì)“可再入”程序舉例

編譯程序P(P的入口,處理源程序乙)(P把源程序甲的信息記盤等磁盤完成)AB源程序甲源程序乙

進(jìn)程的屬性

?結(jié)構(gòu)性：?共享性：?動態(tài)性：?獨立性：?制約性：?并發(fā)性：2.3.2進(jìn)程的狀態(tài)和轉(zhuǎn)換

進(jìn)程三態(tài)模型及其狀態(tài)轉(zhuǎn)換

運行態(tài)就緒態(tài)等待態(tài)選中落選出現(xiàn)等待事件等待事件結(jié)束進(jìn)程五態(tài)模型及其轉(zhuǎn)換運行態(tài)就緒態(tài)等待態(tài)選中落選出現(xiàn)等待事件等待事件結(jié)束新建態(tài)終止態(tài)進(jìn)程的掛起

進(jìn)程為什么要有“掛起”狀態(tài)?進(jìn)程掛起的原因?

具有掛起功能的進(jìn)程狀態(tài)及其轉(zhuǎn)換

掛起等待事件結(jié)束出現(xiàn)等待事件解除掛起掛起落選選中運行態(tài)就緒態(tài)等待事件結(jié)束終止態(tài)新建態(tài)掛起就緒態(tài)解除掛起掛起掛起等待態(tài)等待態(tài)提交提交掛起進(jìn)程具有如下特征

?該進(jìn)程不能立即被執(zhí)行。?掛起進(jìn)程可能會等待事件，但所等待事件是獨立于掛起條件的，事件結(jié)束并不能導(dǎo)致進(jìn)程具備執(zhí)行條件。?進(jìn)程進(jìn)入掛起狀態(tài)是由于操作系統(tǒng)、父進(jìn)程或進(jìn)程本身阻止它的運行。?結(jié)束進(jìn)程掛起狀態(tài)的命令只能通過操作系統(tǒng)或父進(jìn)程發(fā)出。2.3.3

進(jìn)程的描述和組成(1)

1進(jìn)程映象

進(jìn)程控制塊進(jìn)程程序塊進(jìn)程核心棧進(jìn)程數(shù)據(jù)塊進(jìn)程—用戶線程—內(nèi)核線程進(jìn)程的描述和組成(2)

操作系統(tǒng)中把進(jìn)程物理實體和支持進(jìn)程運行的環(huán)境合稱為進(jìn)程上下文。當(dāng)系統(tǒng)調(diào)度新進(jìn)程占有處理器時，新老進(jìn)程隨之發(fā)生上下文切換。進(jìn)程的運行被認(rèn)為是在上下文中執(zhí)行。進(jìn)程的描述和組成(2)

進(jìn)程上下文組成

?用戶級上下文：?系統(tǒng)級上下文：?寄存器上下文：

2進(jìn)程控制塊

進(jìn)程控制塊PCB，是操作系統(tǒng)用于記錄和刻劃進(jìn)程狀態(tài)及有關(guān)信息的數(shù)據(jù)結(jié)構(gòu)。也是操作系統(tǒng)掌握進(jìn)程的唯一資料結(jié)構(gòu)，它包括了進(jìn)程執(zhí)行時的情況，以及進(jìn)程讓出處理器后所處的狀態(tài)、斷點等信息。進(jìn)程控制塊包含三類信息標(biāo)識信息現(xiàn)場信息控制信息

3進(jìn)程隊列及其管理(1)處于同一狀態(tài)的所有PCB鏈接在一起的數(shù)據(jù)結(jié)構(gòu)稱為進(jìn)程隊列。同一狀態(tài)進(jìn)程的PCB既可按先來先到的原則排成隊列;也可按優(yōu)先數(shù)或其它原則排成隊列。通用隊列組織方式：線性方式、鏈接方式索引方式。

進(jìn)程隊列及其管理(2)PCB表PCB10PCB25PCB30PCB40PCB50PCB64運行隊列指針就緒隊列指針等待隊列1指針等待隊列2指針…PCBn7PCB70…空閑進(jìn)程隊列指針鏈接方式運行隊列指針就緒表指針等待表1指針…索引方式PCB表

PCB1PCB2PCB3PCB4PCB5PCB6……PCBn空閑表指針…就緒索引表…等待索引表1等待表2指針Linux進(jìn)程鏈表雙向循環(huán)鏈表進(jìn)程可運行隊列鏈表散列鏈表等待隊列鏈表

隊列管理和狀態(tài)轉(zhuǎn)換示意圖

處理器指派提交完成超時事件1等待隊列事件2等待隊列事件n等待隊列就緒隊列……等待事件1等待事件2等待事件n事件1出現(xiàn)事件2出現(xiàn)事件n出現(xiàn)2.3.4進(jìn)程切換與CPU模式切換

進(jìn)程切換是讓處于運行態(tài)的進(jìn)程中斷運行，讓出處理器，這時要做一次進(jìn)程上下文切換、即保存老進(jìn)程狀態(tài)而裝入被保護(hù)了的新進(jìn)程的狀態(tài)，以便新進(jìn)程運行進(jìn)程切換的步驟保存被中斷進(jìn)程的處理器現(xiàn)場信息修改被中斷進(jìn)程的進(jìn)程控制塊的有關(guān)信息，如進(jìn)程狀態(tài)等把被中斷進(jìn)程的進(jìn)程控制塊加入有關(guān)隊列選擇下一個占有處理器運行的進(jìn)程修改被選中進(jìn)程的進(jìn)程控制塊的有關(guān)信息根據(jù)被選中進(jìn)程設(shè)置操作系統(tǒng)用到的地址轉(zhuǎn)換和存儲保護(hù)信息根據(jù)被選中進(jìn)程恢復(fù)處理器現(xiàn)場調(diào)度和切換時機問題

?請求調(diào)度的事件發(fā)生后，就會運行低級調(diào)度程序，低級調(diào)度程序選中新的就緒進(jìn)程后，就會進(jìn)行上下文切換。實際上，由于種種原因，調(diào)度和切換并不一定能一氣呵成。?通常的做法是，由內(nèi)核置上請求調(diào)度標(biāo)志，延遲到上述工作完成后再進(jìn)行調(diào)度和進(jìn)程上下文切換，?Linux進(jìn)程調(diào)度標(biāo)志位need-resched，Windows延遲過程調(diào)用DPC/dispatch軟件中斷。處理器模式切換?當(dāng)中斷發(fā)生時，暫時中斷正在執(zhí)行的用戶進(jìn)程，把進(jìn)程從用戶狀態(tài)切換到內(nèi)核狀態(tài)，去執(zhí)行操作系統(tǒng)例行程序以獲得服務(wù)，這就是一次模式切換，?內(nèi)核在被中斷了的進(jìn)程的上下文中對這個中斷事件作處理，即使該中斷可能不是此進(jìn)程引起的模式切換的步驟1)保存被中斷進(jìn)程的處理器現(xiàn)場信息；2)處理器從用戶態(tài)切換到核心態(tài)，以便執(zhí)行服務(wù)程序或中斷處理程序；3)如果處理中斷，可根據(jù)規(guī)定的中斷級設(shè)置中斷屏蔽位；4)根據(jù)系統(tǒng)調(diào)用號或中斷號，從系統(tǒng)調(diào)用表或中斷入口表找到服務(wù)程序或中斷處理程序地址。CPU上執(zhí)行的進(jìn)程所處活動范圍

用戶空間中，處于進(jìn)程上下文，用戶進(jìn)程在運行，使用用戶棧。內(nèi)核空間中，處于進(jìn)程上下文，內(nèi)核代表某進(jìn)程在運行，使用核心棧。內(nèi)核空間中，處于中斷上下文，與任何進(jìn)程無關(guān)，中斷服務(wù)程序正在處理特定中斷，Intelx86未提供中斷棧，借用核心棧。UNIX/Linux中上下文切換和模式切換

核心態(tài)運行系統(tǒng)調(diào)用或中斷(隱含模式切換)模式切換用戶態(tài)運行等待狀態(tài)就緒狀態(tài)發(fā)生事件喚醒調(diào)度進(jìn)程中斷、中斷返回允許的上下文切換切換2.3.5進(jìn)程的控制和管理(1)

處理器管理的一個主要工作是對進(jìn)程的控制，包括：創(chuàng)建進(jìn)程、阻塞進(jìn)程、喚醒進(jìn)程、掛起進(jìn)程、激活進(jìn)程、終止進(jìn)程和撤銷進(jìn)程等。這些控制和管理功能由操作系統(tǒng)中的原語實現(xiàn)。原語是在管態(tài)下執(zhí)行、完成系統(tǒng)特定功能的過程。原語和機器指令類似，其特點是執(zhí)行過程中不允許被中斷，是一個不可分割的基本單位，原語的執(zhí)行是順序的而不可能是并發(fā)的。進(jìn)程的控制和管理(2)

進(jìn)程創(chuàng)建進(jìn)程撤銷進(jìn)程阻塞進(jìn)程喚醒進(jìn)程掛起進(jìn)程激活2.4線程及其實現(xiàn)

2.4.1引入多線程的動機2.4.2多線程環(huán)境中的進(jìn)程和線程2.4.3線程的實現(xiàn)

2.4.1引入多線程的動機

單線程(結(jié)構(gòu))進(jìn)程（SingleThreadedProcess）多線程（結(jié)構(gòu)）進(jìn)程（MultipleThreadedprocess）

單線程結(jié)構(gòu)進(jìn)程給并發(fā)程序設(shè)計效率帶來問題

?進(jìn)程切換開銷大?進(jìn)程通信代價大?進(jìn)程間的并發(fā)性粒度較粗，并發(fā)度不高?不適合并行計算和分布并行計算的要求?不適合客戶/服務(wù)器計算的要求。線程的概念(1)操作系統(tǒng)中引入進(jìn)程的目的是為了使多個程序并發(fā)執(zhí)行，以改善資源使用率和提高系統(tǒng)效率，操作系統(tǒng)中再引入線程，則是為了減少程序并發(fā)執(zhí)行時所付出的時空開銷，使得并發(fā)粒度更細(xì)、并發(fā)性更好。線程的概念(2)

解決問題的基本思路：?把進(jìn)程的兩項功能－－“獨立分配資源”與“被調(diào)度分派執(zhí)行”分離開來，?進(jìn)程作為系統(tǒng)資源分配和保護(hù)的獨立單位，不需要頻繁地切換；?線程作為系統(tǒng)調(diào)度和分派的基本單位，能輕裝運行，會被頻繁地調(diào)度和切換，在這種指導(dǎo)思想下，產(chǎn)生了線程的概念。2.4.2多線程環(huán)境中的進(jìn)程與線程

多線程結(jié)構(gòu)進(jìn)程進(jìn)程進(jìn)程PCB資源線程控制塊用戶棧核心棧線程控制塊用戶棧核心?！€程n控制塊用戶棧核心棧存儲區(qū)存儲空間全局?jǐn)?shù)據(jù)程序代碼線程1線程1線程控制塊…線程2線程1線程控制塊用戶棧核心棧線程i線程n多線程環(huán)境中進(jìn)程的定義

進(jìn)程是操作系統(tǒng)中進(jìn)行除處理器外的資源分配和保護(hù)的基本單位，它有一個獨立的虛擬地址空間，用來容納進(jìn)程映像(如與進(jìn)程關(guān)聯(lián)的程序與數(shù)據(jù))，并以進(jìn)程為單位對各種資源實施保護(hù)，如受保護(hù)地訪問處理器、文件、外部設(shè)備及其他進(jìn)程(進(jìn)程間通信)。

多線程環(huán)境中的線程概念

線程是操作系統(tǒng)進(jìn)程中能夠獨立執(zhí)行的實體（控制流），是處理器調(diào)度和分派的基本單位。線程是進(jìn)程的組成部分，每個進(jìn)程內(nèi)允許包含多個并發(fā)執(zhí)行的實體（控制流），這就是多線程。線程組成線程惟一標(biāo)識符及線程狀態(tài)信息；未運行時保存的線程上下文；可把線程看成是進(jìn)程中一個獨立的程序計數(shù)器在操作；核心棧，核心態(tài)下工作時，保存參數(shù)，函數(shù)調(diào)用時的返回地址等；用于存放線程局部變量及用戶棧的私有存儲區(qū)。線程又稱輕量進(jìn)程

?線程運行在進(jìn)程的上下文中,并使用進(jìn)程的資源和環(huán)境。?系統(tǒng)調(diào)度的基本單位是線程而不是進(jìn)程,每當(dāng)創(chuàng)建一個進(jìn)程時，至少要同時為該進(jìn)程創(chuàng)建一個線程，否則該進(jìn)程無法被調(diào)度執(zhí)行。

線程的狀態(tài)

線程狀態(tài)有：運行、就緒和阻塞，線程的狀態(tài)轉(zhuǎn)換也類似于進(jìn)程。掛起狀態(tài)對線程是沒有意義的，如果進(jìn)程掛起后被對換出主存，則它的所有線程因共享了進(jìn)程的地址空間，也必須全部對換出去。線程管理和線程庫(1)多線程技術(shù)利用線程包(庫)提供線程原語集來支持多線程運行，有的操作系統(tǒng)直接支持多線程，而有的操作系統(tǒng)不支持多線程。線程包(庫)可分成兩種：用戶空間中運行的線程包(庫)和內(nèi)核中運行的線程包(庫)。線程管理和線程庫(2)

線程包(庫)提供一組API，支持應(yīng)用程序創(chuàng)建、調(diào)度、撤銷和管理線程的運行?；揪€程控制原語：?孵化（Spawn）：又稱創(chuàng)建線程。?封鎖（Block）：又稱阻塞線程。?活化（Unblock）：又稱恢復(fù)線程。?結(jié)束（Finish）：又稱撤銷線程。并發(fā)多線程程序設(shè)計的優(yōu)點

?快速線程切換。?減少（系統(tǒng)）管理開銷。?(線程）通信易于實現(xiàn)。?(線程）通信易于實現(xiàn)。?并行程度提高。?節(jié)省主存空間。

多線程技術(shù)的應(yīng)用

進(jìn)程中線程多種組織方式：第一種是調(diào)度員／工作者模式第二種是組模式第三種是流水線模式

多線程技術(shù)的應(yīng)用

?前臺和后臺工作?C/S應(yīng)用模式?異步處理?加快執(zhí)行速度。?設(shè)計用戶接口。2.4.3線程的實現(xiàn)

從實現(xiàn)的角度看，線程分成:?用戶級線程ULT(如Java,Informix)?內(nèi)核級線程KLT(如OS/2)。?混合式線程(如，Solaris)。2.5Linux進(jìn)程與線程進(jìn)程描述符task_struct中包含：進(jìn)程標(biāo)識、鏈接信息、調(diào)度信息、文件信息、虛存空間信息、信號處理信息等，在v2.4以上內(nèi)核代碼中，它有將近100個成員。Linux中認(rèn)為線程就是共享地址空間及其他資源的進(jìn)程，故并沒有單獨為線程定義數(shù)據(jù)結(jié)構(gòu)，有一套在用戶模式下運行的線程庫-pthread，但每個線程都擁有惟一隸屬于自己的task_struct。Linux2.4進(jìn)程的核心棧、PCB

和虛存映象

esp存放堆棧棧頂指針核心棧structtask_struct8KB

00x080480000x400000000xc0000000內(nèi)核虛存用戶棧(運行時創(chuàng)建)共享庫主存映象區(qū)運行時堆空間堆(malloc創(chuàng)建)讀/寫段只讀段從可執(zhí)行文件加載esp用戶代碼不可見未用brkLinux2.6進(jìn)程的核心棧進(jìn)程核心棧進(jìn)程核心棧棧頂棧指針espthread_info{*task

…}}

currenttask_struct進(jìn)程的核心棧、*task和task_struct結(jié)構(gòu)Linux進(jìn)程的運行環(huán)境信息thread_info結(jié)構(gòu)

包含：進(jìn)程描述符task_struct指針、當(dāng)前CPU號、底層標(biāo)志、線程同步標(biāo)志、內(nèi)核搶占計數(shù)器等。Linux2.6task_struct

增加用于調(diào)度的新成員，主要有：動態(tài)優(yōu)先級prio靜態(tài)優(yōu)先級static_prio正常優(yōu)先級normal_prio優(yōu)先級數(shù)組prio_array進(jìn)程平均等待時間sleep_avg負(fù)載平衡權(quán)重load_weight等Linux進(jìn)程狀態(tài)TASK_RUNNINGTASK_INTERRUPTIBLETASK_UNINTERRUPTIBLETASK_ZOMBIE。TASK_STOPPEDTASK_SWAPPINGLinux進(jìn)程狀態(tài)及轉(zhuǎn)換

wake_up_interruptible()wake_up()TASK_ZOMBIETASK_RUNNINGTASK_UNINTERRUPTIBLETASK_INTERRUPTIBLETASK_STOPPED占有CPU運行schedule()時間片到schedule()interruptible_sleep_on()schedulle()sleep_on()wake_up()創(chuàng)建do_fork()do_exit()schedule()syscall_trace()sys_exit()收到SIG_KILL或SIG_CONT后，執(zhí)行wake_up()2.6Windows2003進(jìn)程與線程進(jìn)程是資源的容器，容納各種分配到的資源如主存、已打開文件等；線程是可被內(nèi)核調(diào)度的執(zhí)行實體，可被中斷，使CPU能轉(zhuǎn)向另一線程執(zhí)行。進(jìn)程和線程用對象來實現(xiàn)。Windows對象分類(1)

Windows是一個基于對象的操作系統(tǒng)，用對象來表示所有的系統(tǒng)資源。

(1)執(zhí)行體對象由執(zhí)行體的組件實現(xiàn)的對象，用來實現(xiàn)各種外部功能，用戶態(tài)程序(服務(wù)器對象)可訪問執(zhí)行體對象。執(zhí)行體對象：進(jìn)程、線程、區(qū)域、文件、事件、事件對、文件映射、互斥、信號量、計時器、對象目錄、符號連接、關(guān)鍵字、端口、存取令牌和終端等。

Windows對象分類(2)

(2)內(nèi)核對象內(nèi)核實現(xiàn)的更原始的對象集合，包括：內(nèi)核過程對象、異步過程調(diào)用對象、延遲過程調(diào)用對象、中斷對象、電源通知對象、電源狀態(tài)對象、調(diào)度程序?qū)ο蟮取?/p>

內(nèi)核對象對用戶態(tài)代碼是不可見的，僅在執(zhí)行體內(nèi)創(chuàng)建和使用，許多執(zhí)行體對象包含一個或多個內(nèi)核對象，而內(nèi)核對象能提供僅能由內(nèi)核來完成的基本功能。Windows對象分類(3)Windows對象結(jié)構(gòu)對象頭對象體對象管理器

進(jìn)程及控制和使用的資源

對象句柄表虛擬地址空間描述符文件x信號量y區(qū)域z…VADVADVADVAD進(jìn)程訪問令牌可用對象句柄1句柄2線程線程線程句柄3對象和句柄間的關(guān)系

應(yīng)用程序執(zhí)行體對象執(zhí)行體內(nèi)核用戶態(tài)核心態(tài)句柄內(nèi)核對象進(jìn)程對象(進(jìn)程描述表結(jié)構(gòu))

EPROCESS…void*UniqueprocessId;…KPROCESS…uint32kernelTime;uint32UserTime;…byteState;…NT內(nèi)核NT執(zhí)行體線程對象(進(jìn)程和線程描述表結(jié)構(gòu))

KTHREADKTHREADEPROCESSKPROCESSETHREADKTHREADKTHREADKTHREADNT內(nèi)核NT執(zhí)行體調(diào)用CreateProcess函數(shù)創(chuàng)建進(jìn)程

創(chuàng)建WIN32進(jìn)程的具體步驟：?打開將在進(jìn)程中被執(zhí)行的映像文件（.EXE）。?創(chuàng)建Windows2000/XP執(zhí)行體進(jìn)程對象。?創(chuàng)建初始線程（堆棧、描述表、執(zhí)行體線程對象）。?通知WIN32子系統(tǒng)已創(chuàng)建了一個新的進(jìn)程，以便它可設(shè)置新的進(jìn)程和線程。?啟動初始線程的執(zhí)行。?在新進(jìn)程和線程的描述表中完成地址空間的初始化，加載所需的DLL，并開始程序的執(zhí)行調(diào)用CreateThread函數(shù)創(chuàng)建線程

創(chuàng)建WIN32線程的具體步驟：?在進(jìn)程地址空間內(nèi)為線程創(chuàng)建用戶態(tài)堆棧；初始化線程描述表；?調(diào)用NtCreateThread創(chuàng)建執(zhí)行體線程對象。包括：增加進(jìn)程中的線程計數(shù)，創(chuàng)建并初始化執(zhí)行體線程塊，生成新線程ID，從非頁交換區(qū)分配線程的內(nèi)核堆棧，設(shè)置線程環(huán)境塊TEB，設(shè)置線程起始地址和用戶指定的WIN32起始地址，設(shè)置KTHREAD塊，設(shè)置指向進(jìn)程訪問令牌的指針和創(chuàng)建時間；?通知WIN32子系統(tǒng)已創(chuàng)建新線程，以便設(shè)置新的進(jìn)程和線程；?置新線程為準(zhǔn)備態(tài)，把其句柄和ID返回到調(diào)用進(jìn)程；調(diào)用ResumeThread，線程將被激活并調(diào)度執(zhí)行。Windows進(jìn)程和線程狀態(tài)

資源可用事件完成但資源不可用事件完成資源可用阻塞掛起終止可運行不可運行選中切換搶占或時間片到Running運行態(tài)Ready就緒態(tài)Standby準(zhǔn)備態(tài)Terminated中止態(tài)Waiting等待態(tài)Transition過渡態(tài)2.7處理機調(diào)度

2.7.1處理機調(diào)度的層次2.7.2選擇調(diào)度算法的原則

2.7.1處理機調(diào)度的層次

作業(yè)從進(jìn)入系統(tǒng)成為后備作業(yè)開始，直到運行結(jié)束退出系統(tǒng)為止，需經(jīng)歷不同級別的調(diào)度。?高級調(diào)度?中級調(diào)度?低級調(diào)度處理器三級調(diào)度模型處理器低級調(diào)度高級調(diào)度完成超時掛起就緒隊列掛起等待隊列等待隊列就緒隊列等待事件交互式用戶事件出現(xiàn)后備作業(yè)隊列中級調(diào)度處理器兩級調(diào)度模型等待事件事件發(fā)生進(jìn)程完成后備作業(yè)隊列

就緒隊列高級調(diào)度低級調(diào)度等待隊列CPU時間片完2.7.2選擇調(diào)度算法的原則(1)

l

資源利用率CPU利用率=CPU有效工作時間/CPU總的運行時間，CPU總的運行時間=CPU有效工作時間+CPU空閑等待時間。選擇調(diào)度算法的原則(2)

2

響應(yīng)時間?交互式進(jìn)程從提交一個請求(命令)到接收到響應(yīng)之間的時間間隔稱響應(yīng)時間。?使交互式用戶的響應(yīng)時間盡可能短，或盡快處理實時任務(wù)。?這是分時系統(tǒng)和實時系統(tǒng)衡量調(diào)度性能的一個重要指標(biāo)。選擇調(diào)度算法的原則(3)

3周轉(zhuǎn)時間?批處理用戶從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的時間間隔稱作業(yè)周轉(zhuǎn)時間，應(yīng)使作業(yè)周轉(zhuǎn)時間或平均作業(yè)周轉(zhuǎn)時間盡可能短。?這是批處理系統(tǒng)衡量調(diào)度性能的一個重要指標(biāo)。

選擇調(diào)度算法的原則(4)

4吞吐率單位時間內(nèi)處理的作業(yè)數(shù)。5公平性確保每個用戶每個進(jìn)程獲得合理的CPU份額或其他資源份額，不會出現(xiàn)餓死情況。

作業(yè)周轉(zhuǎn)與平均周轉(zhuǎn)時間如果作業(yè)i提交給系統(tǒng)的時刻是ts，完成時刻是tf，該作業(yè)的周轉(zhuǎn)時間ti為：ti=tf-ts

實際上，它是作業(yè)在系統(tǒng)里的等待時間與運行時間之和。為了提高系統(tǒng)的性能，要讓若干個用戶的平均作業(yè)周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間最小。平均作業(yè)周轉(zhuǎn)時間T=(Σti)/n作業(yè)帶權(quán)周轉(zhuǎn)時間和平均

作業(yè)帶權(quán)周轉(zhuǎn)時間如果作業(yè)i的周轉(zhuǎn)時間為ti，所需運行時間為tk，則稱wi=ti/tk為該作業(yè)的帶權(quán)周轉(zhuǎn)時間。ti是等待時間與運行時間之和，故帶權(quán)周轉(zhuǎn)時間總大于1。平均作業(yè)帶權(quán)周轉(zhuǎn)時間W=(Σwi)/n2.8作業(yè)的管理與調(diào)度

2.8.1作業(yè)和進(jìn)程的關(guān)系2.8.2作業(yè)的組織、調(diào)度和控制2.8.1作業(yè)和進(jìn)程的關(guān)系

?作業(yè)(JOB)，?作業(yè)步(JobStep)，?作業(yè)組織，?作業(yè)的提交、收容、執(zhí)行和完成。作業(yè)是任務(wù)實體，進(jìn)程是完成任務(wù)的執(zhí)行實體;沒有作業(yè)任務(wù)，進(jìn)程無事可干，沒有進(jìn)程，作業(yè)任務(wù)沒法完成。作業(yè)概念更多地用在批處理操作系統(tǒng)，而進(jìn)程則可以用在各種多道程序設(shè)計系統(tǒng)。2.8.2作業(yè)的組織、調(diào)度和控制

1批作業(yè)的組織和管理1)批作業(yè)的輸入

2)批作業(yè)的建立作業(yè)控制語言，作業(yè)說明書，

作業(yè)控制塊多道批處理操作系統(tǒng)具有獨立的作業(yè)管理模塊，必須像進(jìn)程管理一樣為每一個作業(yè)建立作業(yè)控制塊（JCB）。JCB通常是在批作業(yè)進(jìn)入系統(tǒng)時，由Spooling系統(tǒng)建立的，它是作業(yè)存在于系統(tǒng)的標(biāo)志，作業(yè)撤離時，JCB也被撤銷。

JCB的主要內(nèi)容包括：(1)作業(yè)情況(2)資源需求(3)資源使用情況作業(yè)生命周期狀態(tài)輸入狀態(tài)：后備狀態(tài)：執(zhí)行狀態(tài)：完成狀態(tài)：3)批作業(yè)的調(diào)度(1)選擇作業(yè)：(2)分配資源：(3)創(chuàng)建進(jìn)程：(4)作業(yè)控制：(5)后續(xù)處理：作業(yè)調(diào)度與進(jìn)程調(diào)度的關(guān)系

進(jìn)程調(diào)度運行就緒等待輸入狀態(tài)后備狀態(tài)完成狀態(tài)預(yù)輸入完成作業(yè)控制作業(yè)調(diào)度(選中并創(chuàng)建進(jìn)程)作業(yè)調(diào)度(作業(yè)終止并撤離)SPOOLing作業(yè)預(yù)輸入SPOOLing作業(yè)緩輸出2交互作業(yè)的組織和管理分時系統(tǒng)的作業(yè)就是用戶的一次上機交互過程，可認(rèn)為終端進(jìn)程的創(chuàng)建是一個交互型作業(yè)的開始，退出命令運行結(jié)束代表用戶交互型作業(yè)的中止。交互作業(yè)的情況和資源需求通過操作命令告知系統(tǒng)，分時用戶逐條輸入命令，即提交作業(yè)（步）和控制作業(yè)運行，系統(tǒng)則逐條執(zhí)行并給出應(yīng)答，每鍵入一條或一組有關(guān)操作命令，便在系統(tǒng)內(nèi)部創(chuàng)建一個進(jìn)程或若干進(jìn)程來完成相應(yīng)命令。鍵盤命令有：作業(yè)控制類；資源申請類；文件操作類；目錄操作類；設(shè)備控制類等。2.9處理器調(diào)度算法2.9.1低級調(diào)度的功能和類型2.9.2作業(yè)調(diào)度和低級調(diào)度算法2.9.3實時調(diào)度算法2.9.4多處理機調(diào)度算法

2.9.1低級調(diào)度的功能和類型1低級調(diào)度的主要功能調(diào)度程序兩項任務(wù)：調(diào)度和分派。調(diào)度實現(xiàn)調(diào)度策略，確定就緒進(jìn)程/線程競爭使用處理器的次序的裁決原則，即進(jìn)程/線程何時應(yīng)放棄CPU和選擇哪個來執(zhí)行；分派實現(xiàn)調(diào)度機制，確定如何時分復(fù)用CPU，處理上下文交換細(xì)節(jié)，完成進(jìn)程/線程和CPU的綁定和放棄的實際工作。調(diào)度機制邏輯功能程序模塊組成隊列管理程序：上下文切換程序：分派程序：2低級調(diào)度的基本類型第一類稱剝奪式：兩種處理器剝奪原則，一是高優(yōu)先級進(jìn)程/線程可剝奪低優(yōu)先級進(jìn)程/線程，二是當(dāng)運行進(jìn)程/線程時間片用完后被剝奪。第二類稱非剝奪式：

2.9.2作業(yè)調(diào)度和低級調(diào)度算法1先來先服務(wù)算法三個作業(yè)同時到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：作業(yè)名/所需CPU時間:作業(yè)1/28，作業(yè)2/9，作業(yè)3/3。采用FCFS算法，平均作業(yè)周轉(zhuǎn)時間為35。?若三個作業(yè)提交順序改為作業(yè)2、1、3，平均作業(yè)周轉(zhuǎn)時間約為29。若三個作業(yè)提交順序改為作業(yè)3、2、1，平均作業(yè)周轉(zhuǎn)時間約為18。FCFS調(diào)度算法的平均作業(yè)周轉(zhuǎn)時間與作業(yè)提交的順序有關(guān)。2

最短作業(yè)優(yōu)先算法(1)

SJF算法以進(jìn)入系統(tǒng)的作業(yè)所要求的CPU時間為標(biāo)準(zhǔn)，總選取估計計算時間最短的作業(yè)投入運行。算法易于實現(xiàn)，效率不高，主要弱點是忽視了作業(yè)等待時間。會出現(xiàn)饑餓現(xiàn)象。SJF的平均作業(yè)周轉(zhuǎn)時間比FCFS要小，故它的調(diào)度性能比FCFS好。實現(xiàn)SJF調(diào)度算法需要知道作業(yè)所需運行時間，否則調(diào)度就沒有依據(jù)，要精確知道一個作業(yè)的運行時間是辦不到的。最短作業(yè)優(yōu)先算法(2)

四個作業(yè)同時到達(dá)系統(tǒng)并進(jìn)入調(diào)度：作業(yè)名/所需CPU時間:作業(yè)1/9，作業(yè)2，作業(yè)3/10，作業(yè)4/8。SJF作業(yè)調(diào)度順序為作業(yè)2、4、1、3，平均作業(yè)周轉(zhuǎn)時間T=17，平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=1.98。如果施行FCFS調(diào)度算法，平均作業(yè)周轉(zhuǎn)時間T=19，平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=2.61。3最短剩余時間優(yōu)先算法(1)SRTF把SJF算法改為搶占式的。一個新作業(yè)進(jìn)入就緒狀態(tài)，如果新作業(yè)需要的CPU時間比當(dāng)前正在執(zhí)行的作業(yè)剩余下來還需的CPU時間短，SRTF強行趕走當(dāng)前正在執(zhí)行作業(yè)。稱最短剩余時間優(yōu)先算法此算法不但適用于JOB調(diào)度，同樣也適用于進(jìn)程調(diào)度。最短剩余時間優(yōu)先算法(2)四個作業(yè)其到達(dá)系統(tǒng)/所需CPU時間如下：Job1-0/8，Job2-1/4，Job3-2/9，Job4-3/5。SRTF調(diào)度平均等待時間=6.5毫秒。SJF調(diào)度平均等待時間=7.75毫秒。

J1J2J4J1J30151017264響應(yīng)比最高者優(yōu)先算法

FCFS與SJF是片面的調(diào)度算法。FCFS只考慮作業(yè)等候時間而忽視了作業(yè)的計算時問，SJF只考慮用戶估計的作業(yè)計算時間而忽視了作業(yè)等待時間。HRRF是介乎這兩者之間的折衷算法，既考慮作業(yè)等待時間，又考慮作業(yè)的運行時間，既照顧短作業(yè)又不使長作業(yè)的等待時間過長，改進(jìn)了調(diào)度性能。

響應(yīng)比定義響應(yīng)比＝1+已等待時間/估計運行時間?短作業(yè)容易得到較高響應(yīng)比，?長作業(yè)等待時間足夠長后，也將獲得足夠高的響應(yīng)比，?饑餓現(xiàn)象不會發(fā)生。HRRF算法舉例

四個作業(yè)到達(dá)系統(tǒng)時間/所需CPU時間:作業(yè)1-0/20，作業(yè)2-5/15，作業(yè)3-10/5，作業(yè)4-15/10。SJF調(diào)度順序為作業(yè)1、3、4、2，平均作業(yè)周轉(zhuǎn)時間T=25，平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=2.25。FCFS調(diào)度順序為作業(yè)1、3、4、2，平均作業(yè)周轉(zhuǎn)時間T=28.75，平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=3.125。HRRF調(diào)度順序為作業(yè)1、3、4、2，平均作業(yè)周轉(zhuǎn)時間T=26.25，平均帶權(quán)作業(yè)周轉(zhuǎn)時間W=2.46。5優(yōu)先級調(diào)度算法(1)

靜態(tài)優(yōu)先數(shù)法使用外圍設(shè)備頻繁者優(yōu)先數(shù)大，這樣有利于提高效率；重要算題程序的進(jìn)程優(yōu)先數(shù)大，這樣有利于用戶；進(jìn)入計算機時間長的進(jìn)程優(yōu)先數(shù)大，這樣有利于縮短作業(yè)完成的時間；交互式用戶的進(jìn)程優(yōu)先數(shù)大，這樣有利于終端用戶的響應(yīng)時間等等,

優(yōu)先權(quán)調(diào)度算法(2)

動態(tài)優(yōu)先數(shù)法①根據(jù)進(jìn)程占有CPU時間多少來決定,當(dāng)進(jìn)程占有CPU時間愈長,那么，在它被阻塞之后再次獲得調(diào)度的優(yōu)先級就越低，反之,進(jìn)程獲得調(diào)度的可能性越大;②根據(jù)進(jìn)程等待CPU時間多少來決定,當(dāng)進(jìn)程在就緒隊列中等待時間愈長,那么，在它被阻塞之后再次獲得調(diào)度的優(yōu)先級就越高，反之,進(jìn)程獲得調(diào)度的可能性越小。6

時間片輪轉(zhuǎn)調(diào)度算法時間片調(diào)度做法是：調(diào)度程序每次把CPU分配給就緒隊列首進(jìn)程使用一個時間片，例如100ms，就緒隊列中的每個進(jìn)程輪流地運行一個時間片。當(dāng)這個時間片結(jié)束時，強迫一個進(jìn)程讓出處理器，讓它排列到就緒隊列的尾部，等候下一輪調(diào)度輪轉(zhuǎn)策略可防止那些很少使用外圍設(shè)備的進(jìn)程過長的占用處理器而使得要使用外圍設(shè)備的那些進(jìn)程沒有機會去啟動外圍設(shè)備輪轉(zhuǎn)策略與間隔時鐘7

多級反饋隊列調(diào)度

又稱反饋循環(huán)隊列或多隊列策略。主要思想是將就緒進(jìn)程分為兩級或多級，系統(tǒng)相應(yīng)建立兩個或多個就緒進(jìn)程隊列，較高優(yōu)先級的隊列一般分配給較短的時間片。處理器調(diào)度先從高級就緒進(jìn)程隊列中選取可占有處理器的進(jìn)程，只有在選不到時，才從較低級的就緒進(jìn)程隊列中選取。一個三級反饋隊列調(diào)度策略

低級就緒隊列高級就緒隊列中級就緒隊列等待磁盤磁帶等待其他外設(shè)運行選中,時間片500ms超過時間片啟動磁盤磁帶啟動其他外設(shè)選中,時間片200ms選中,時間片100ms8彩票調(diào)度算法

基本思想：為進(jìn)程發(fā)放針對各種資源（如CPU時間）的彩票。調(diào)度程序隨機選擇一張彩票，持有該彩票的進(jìn)程獲得系統(tǒng)資源。進(jìn)程都是平等的，有相同的運行機會。如果某些進(jìn)程需要更多的機會，可被給予更多彩票，增加其中獎機會。2.9.3實時調(diào)度算法

實時系統(tǒng)是那些時間因素非常關(guān)鍵的系統(tǒng)。實時系統(tǒng)包括監(jiān)控系統(tǒng)、自動駕駛系統(tǒng)、安全控制系統(tǒng)等，這些系統(tǒng)中，遲到的響應(yīng)即使正確，也和沒有響應(yīng)一樣糟糕。硬實時系統(tǒng)和軟實時系統(tǒng)實時系統(tǒng)通常分為硬實時系統(tǒng)和軟實時系統(tǒng)。前者意味著存在必須滿足的時間限制；后者意味著偶爾超過時間限制時可以容忍的。

周期性和非周期性事件實時系統(tǒng)響應(yīng)的事件可劃分為周期性事件和非周期性事件。例如，m個周期性事件，事件i的周期為Pi，每個事件需要Ci秒的CPU時間來處理，則只有滿足以下條件：

C1/P1+C2/P2+…+Cm/Pm≤1

時，才可能處理所有的負(fù)載。滿足該條件的實時系統(tǒng)稱作任務(wù)可調(diào)度的。

實時調(diào)度算法(1)

1）單比率調(diào)度算法基本思想：為每個進(jìn)程分配一個與事件發(fā)生頻率成正比的優(yōu)先數(shù)。例如，周期為20ms的進(jìn)程優(yōu)先數(shù)為50，周期為100ms的進(jìn)程優(yōu)先數(shù)為10，運行時調(diào)度程序總是調(diào)度優(yōu)先數(shù)最高的就緒進(jìn)程，并采取搶占式分配策略。實時調(diào)度算法(2)

2）限期調(diào)度算法

基本思想：當(dāng)一個事件發(fā)生時，對應(yīng)的進(jìn)程就按照截止期限被加入就緒進(jìn)程隊列。對于一個周期性事件，其截止期限即為事件下一次發(fā)生的時間。該調(diào)度算法首先運行隊首進(jìn)程，即截止時間最近的那個進(jìn)程。實時調(diào)度算法(3)

3）最少裕度法

基本思想：首先計算各個進(jìn)程的富裕時間，即裕度（laxity），然后選擇裕度最少的進(jìn)程執(zhí)行。裕度=截止時間-(就緒時間+計算時間)2.9.4多處理器調(diào)度

1多處理機調(diào)度的設(shè)計要點1)如何為進(jìn)程分配處理機、2)在單個處理機上是否使用多道程序設(shè)計技術(shù)3)如何實際指派進(jìn)程，多處理器調(diào)度算法(1)

1）負(fù)載共享調(diào)度算法

基本思想：進(jìn)程并不指派到特定處理機上，系統(tǒng)維護(hù)全局性進(jìn)程就緒隊列，當(dāng)處理機空閑時，就選擇進(jìn)程的一個線程去運行。多處理器調(diào)度算法(2)2）群調(diào)度算法

基本思想：一群相關(guān)線程基于一對一的原則，被同時調(diào)度到一組處理機上運行。它具有的優(yōu)點：?當(dāng)緊密相關(guān)的進(jìn)程同時執(zhí)行時，同步造成的等待將減少，進(jìn)程切換也相應(yīng)減少，系統(tǒng)性能得到提高。?由于一次性同時調(diào)度一組處理器，調(diào)度的代價也將減少。多處理器調(diào)度算法(3)

3）處理器專派調(diào)度算法基本思想：給同屬一個進(jìn)程的一組線程，同時分派到一組處理機上運行，每個線程獲得一個處理機，且它專用于處理這個線程，直到進(jìn)程運行結(jié)束，這是群調(diào)度的一種極端形式。采用這一算法，處理器將不適用多道程序設(shè)計，即該應(yīng)用的一個線程阻塞后，線程對應(yīng)的處理器不會被調(diào)度給其他線程，而處于空閑狀態(tài)。多處理器調(diào)度算法(4)

4）動態(tài)調(diào)度算法(1)

基本思想：由操作系統(tǒng)和應(yīng)用進(jìn)程共同完成調(diào)度。操作系統(tǒng)負(fù)責(zé)在應(yīng)用進(jìn)程之間劃分處理器。應(yīng)用進(jìn)程在分配給它的處理器上執(zhí)行可運行線程的子集，哪一些線程應(yīng)該執(zhí)行，哪一些線程應(yīng)該掛起完全是應(yīng)用進(jìn)程自己的事。多處理器調(diào)度算法(5)

動態(tài)調(diào)度算法(2)

?

如果有空閑處理器，滿足要求。否則，對新到達(dá)進(jìn)程，從當(dāng)前分配了一個以上處理器的進(jìn)程中收回一個，并把它分給新到達(dá)進(jìn)程。?如果要求不能被滿足，則保留申請直到出現(xiàn)可用處理器或要求取消。?釋放了一個或多個處理器后，掃描申請?zhí)幚砥鞯倪M(jìn)程隊列，按照FCFS原則把處理器逐一分配給每個申請進(jìn)程直到?jīng)]有可用處理器。2.10Linux調(diào)度算法

2.10.1Linux傳統(tǒng)調(diào)度算法2.10.2Linux2.6調(diào)度算法2.10.1Linux傳統(tǒng)調(diào)度算法(1)

1進(jìn)程調(diào)度策略

1)policy：

SCHED_OTHER普通類任務(wù)SCHED_FIFO先進(jìn)先出實時類任務(wù)SCHED_RR輪轉(zhuǎn)法實時類任務(wù)

2)priority進(jìn)程靜態(tài)優(yōu)先級

3)nice進(jìn)程可控優(yōu)先級因子4)rt_priority實時進(jìn)程靜態(tài)優(yōu)先級

5)counter進(jìn)程目前時間片配額，也稱進(jìn)程動態(tài)優(yōu)先級Linux傳統(tǒng)調(diào)度算法(2)

2動態(tài)優(yōu)先級的產(chǎn)生和變化當(dāng)counter遞減到0時，運行進(jìn)程被迫出讓CPU；當(dāng)可運行隊列中所有進(jìn)程的counter值變?yōu)?后，表明一輪調(diào)度已經(jīng)結(jié)束。等待態(tài)進(jìn)程的動態(tài)優(yōu)先級通常會逐漸增加，當(dāng)所有可運行進(jìn)程的counter都為0時，系統(tǒng)重新計算所有進(jìn)程的counter，計算公式為：p->counter=(p->counter>>1)+NICE_TO_TICKS(P->nice)

對于就緒態(tài)進(jìn)程來說，因其counter都為0，計算結(jié)果就是nice轉(zhuǎn)換過來的時鐘滴答數(shù)；對于等待態(tài)進(jìn)程就不一樣，它們的counter都不為0，計算結(jié)束后，等待態(tài)進(jìn)程的動態(tài)優(yōu)先級會大于nice值。3Linux進(jìn)程調(diào)度機制進(jìn)程調(diào)度依據(jù)和時機進(jìn)程調(diào)度任務(wù)進(jìn)程切換

進(jìn)程切換時機

(1)進(jìn)程被動地放棄CPU，當(dāng)前進(jìn)程時間片用完或當(dāng)一個進(jìn)程被喚醒，且其優(yōu)先級高于當(dāng)前進(jìn)程的優(yōu)先級時，通過TIF_NEED_RESCHED位置1，來告訴內(nèi)核在適當(dāng)?shù)臅r刻需要重新調(diào)度。(2)進(jìn)程主動放棄CPU，是由于進(jìn)程執(zhí)行系統(tǒng)調(diào)用，狀態(tài)發(fā)生變化，直接調(diào)用schedule()進(jìn)入調(diào)度，這類系統(tǒng)調(diào)用有：yield()、pause()、sleep()、wait()和exit()。(3)進(jìn)程執(zhí)行等待系統(tǒng)調(diào)用，如read()或write()等，此時進(jìn)程進(jìn)入等待隊列，系統(tǒng)調(diào)用schedule()進(jìn)入調(diào)度，該函數(shù)的執(zhí)行結(jié)果往往是當(dāng)前進(jìn)程放棄處理器。進(jìn)程切換

上下文切換是從一個可運行進(jìn)程切換到另一個可運行進(jìn)程，由context_switch（）函數(shù)處理這項工作，每當(dāng)一個新的進(jìn)程被選出來準(zhǔn)備投入運行時，schedule（）就會調(diào)用該函數(shù)。它首先調(diào)用switch_mm（），把虛擬主存從上一個進(jìn)程映射切換到新進(jìn)程中；再調(diào)用switch_to（），從上一個進(jìn)程的處理器狀態(tài)切換到新進(jìn)程的處理器狀態(tài)。2.10.2Linux2.6調(diào)度算法0（1）調(diào)度程序--特點是能夠保證無論系統(tǒng)負(fù)載(進(jìn)程數(shù)目或處理器數(shù)目)如何增加，選擇合適進(jìn)程并且給它分配處理器的時間是恒定的，具有的新特性有：支持SMP，每個處理器擁有自己的可運行隊列；強化SMP的親和力，盡量將相關(guān)任務(wù)分配到一個處理器上連續(xù)運行；確保響應(yīng)時間，及時調(diào)度交互式進(jìn)程；保證公平性，沒有進(jìn)程會處于饑餓狀態(tài)。Linux2.6中，進(jìn)程描述符task_struct含有與調(diào)度有關(guān)的成員(1)

1)policy-進(jìn)程調(diào)度策略，有三種類型：·SCHED_NORMAL非實時進(jìn)程；·SCHED_FIFO實時進(jìn)程，采用先進(jìn)先出的調(diào)度算法；·SCHED_RR實時進(jìn)程，采用輪轉(zhuǎn)法。

Linux2.6中，進(jìn)程描述符task_struct含有與調(diào)度有關(guān)的成員(2)

2)rt_priority-實時進(jìn)程的優(yōu)先級。其值為1000+rt_priority，而MAX_RT_PRIO定義為100，故rt_priority范圍為0至99，且不參與優(yōu)先級計算；3)static_prio-非實時進(jìn)程靜態(tài)優(yōu)先級。由nice值轉(zhuǎn)換而來，公式為：static_prio=MAX_RT_PRIO+nice-20。Linux2.6中，進(jìn)程描述符task_struct含有與調(diào)度有關(guān)的成員(3)

4)sleep_avg-進(jìn)程平均等待時間。相當(dāng)于進(jìn)程等待時間與運行時間的差值，既反映該進(jìn)程的交互程度，又表示進(jìn)程需要運行的緊迫程度，該值越大，進(jìn)程的優(yōu)先級就越高；5)prio-進(jìn)程動態(tài)優(yōu)先級。在進(jìn)程運行過程中動態(tài)計算，主要影響因素為sleep_avg。創(chuàng)建時子進(jìn)程繼承父進(jìn)程的動態(tài)優(yōu)先級、喚醒等待進(jìn)程時對它進(jìn)行優(yōu)先級修正、時鐘中斷中重新計算進(jìn)程優(yōu)先級并進(jìn)入相應(yīng)隊列、負(fù)載平衡/修改nice值/修改調(diào)度策略（setscheduler（））都有可能改變進(jìn)程動態(tài)優(yōu)先級；Linux2.6中，進(jìn)程描述符task_struct含有與調(diào)度有關(guān)的成員(4)

6)prio_array_t*array-進(jìn)程優(yōu)先級數(shù)組。以進(jìn)程優(yōu)先級為序號排列；7)time_slice-進(jìn)程時間片余額。進(jìn)程默認(rèn)時間片與static_prio有關(guān)，內(nèi)核將100至139的優(yōu)先級映射列800ms至5ms的時間片區(qū)間；創(chuàng)建進(jìn)程時，子、父進(jìn)程平分父進(jìn)程的剩余時間片。終止進(jìn)程時，若子進(jìn)程如果從未重新分配過時間片，則把剩余時間片歸還給父進(jìn)程；Linux2.6中，進(jìn)程描述符task_struct含有與調(diào)度有關(guān)的成員(5)

8)load_weight;-平衡負(fù)載用的權(quán)重。解決可運行隊列出現(xiàn)的負(fù)載不均現(xiàn)象；9)CONFIG_PREEMPT-內(nèi)核可剝奪編譯選項，當(dāng)該開關(guān)開啟時，v2.6內(nèi)核將會在更多內(nèi)核安全點上檢測TIF_NEED_RESCHED位，從而讓剛被喚醒的高優(yōu)先級任務(wù)減少延遲而盡快獲得處理器運行。關(guān)于need_resched每個進(jìn)程都包含need_resched標(biāo)志，這是因為通過current宏訪問進(jìn)程描述符內(nèi)的數(shù)值要比訪問全局變量快，在v2.2以前內(nèi)核版本中，該標(biāo)志曾經(jīng)是一個全局變量；v2.2到v2.4版內(nèi)核中它放在進(jìn)程的task_struct中；v2.6版中，它被移到thread_info結(jié)構(gòu)體里，用特別的標(biāo)志變量中的一位TIF_NEED_RESCHED來表示。1調(diào)度算法的數(shù)據(jù)結(jié)構(gòu)調(diào)度程序中最主要的數(shù)據(jù)結(jié)構(gòu)是可運行隊列(runqueue)，它是給定處理器上的就緒進(jìn)程鏈表，每個處理器一個，每個就緒進(jìn)程都?xì)w屬于一個可運行隊列。它還包含每個處理器的調(diào)度信息，所以也是處理器的重要數(shù)據(jù)結(jié)構(gòu)?？蛇\行隊列(處理器)的優(yōu)先級數(shù)組一個是活躍的、一個是過期的。structprio_array{intnr_active;//數(shù)組中的進(jìn)程數(shù)unsignedlongbitmap[BITMAP_SIZE];