第3章 處理器管理

L/O/G/O第三章第三章第三章第三章 處理器管理處理器管理處理器管理處理器管理mxh處理器管理的地位處理器管理的地位處理器管理的地位處理器管理的地位mxh主要內(nèi)容主要內(nèi)容主要內(nèi)容主要內(nèi)容3.1 3.1 進(jìn)程的引入程的引入3.23.2進(jìn)程的概念程的概念3.33.3進(jìn)程控制程控制3.43.4線程程3.53.5處理器理器調(diào)度度3.63.6調(diào)度算法度算法3.73.7處理器理器調(diào)度和度和實時調(diào)度度mxh3.1.13.1.13.1.13.1.1程序的執(zhí)行方式程序的執(zhí)行方式程序的執(zhí)行方式程序的執(zhí)行方式(順序順序順序順序)順序序執(zhí)行行特征：特征：順序性、封序性、封閉性、可再性、可再現(xiàn)性性I1C1P1I2C2P2mxh3.1.23.1.23.1.23.1.2程序的執(zhí)行方式程序的執(zhí)行方式程序的執(zhí)行方式程序的執(zhí)行方式(并發(fā)并發(fā)并發(fā)并發(fā))并并發(fā)執(zhí)行行I1I2I3I4C1C2C3C4P1P2P3P4tmxh3.1.13.1.13.1.13.1.1程序的執(zhí)行方式程序的執(zhí)行方式程序的執(zhí)行方式程序的執(zhí)行方式(并發(fā)并發(fā)并發(fā)并發(fā))特征特征mxh與并發(fā)有關(guān)的錯誤與并發(fā)有關(guān)的錯誤與并發(fā)有關(guān)的錯誤與并發(fā)有關(guān)的錯誤mxh3.2 3.2 3.2 3.2 進(jìn)程的概念進(jìn)程的概念進(jìn)程的概念進(jìn)程的概念問題引入引入 程序程序這個靜個靜態(tài)概念已不能如概念已不能如實反映程序并反映程序并發(fā)執(zhí)行行過程的特征。程的特征。為了深刻描述程序了深刻描述程序動態(tài)執(zhí)行行過程的性程的性質(zhì)，人，人們引入引入“進(jìn)程程（ProcessProcess）”概念。概念。mxh3.2 3.2 3.2 3.2 進(jìn)程的概念進(jìn)程的概念進(jìn)程的概念進(jìn)程的概念程序在程序在處理機(jī)上理機(jī)上執(zhí)行行時所所發(fā)生的活生的活動(Dijkstra)(Dijkstra)。是一個容器，是一個容器，該容器用以聚集相關(guān)容器用以聚集相關(guān)資源。源。（A.S.TanenbaumA.S.Tanenbaum）進(jìn)程是一個具有獨(dú)立功能的進(jìn)程是一個具有獨(dú)立功能的程序程序關(guān)于某關(guān)于某個個數(shù)據(jù)集合數(shù)據(jù)集合的的一次運(yùn)行活動一次運(yùn)行活動。是系統(tǒng)進(jìn)。是系統(tǒng)進(jìn)行資源分配和調(diào)度的單位。行資源分配和調(diào)度的單位。mxh3.2 3.2 3.2 3.2 進(jìn)程的概念進(jìn)程的概念進(jìn)程的概念進(jìn)程的概念操作操作級:圖形窗口界面形窗口界面:一個窗口就是一個一個窗口就是一個進(jìn)程程打開窗口：建立一個打開窗口：建立一個進(jìn)程程關(guān)關(guān)閉窗口：一個窗口：一個進(jìn)程程結(jié)束束字符命令界面字符命令界面:一條命令一般就是一個一條命令一般就是一個進(jìn)程程命令行尾回命令行尾回車:一個一個進(jìn)程開始程開始命令命令執(zhí)行行結(jié)束束(下一命令提示符出下一命令提示符出現(xiàn)):):一個一個進(jìn)程程結(jié)束束編程程級：進(jìn)程建立：程建立：“建立建立進(jìn)程程”函數(shù)或系函數(shù)或系統(tǒng)調(diào)用用進(jìn)程程結(jié)束：束：“撤消撤消進(jìn)程程”函數(shù)或系函數(shù)或系統(tǒng)調(diào)用，或者程序用，或者程序的正?；蚍钦５恼；蚍钦＝Y(jié)束。束。mxh進(jìn)程和程序的區(qū)別進(jìn)程和程序的區(qū)別進(jìn)程和程序的區(qū)別進(jìn)程和程序的區(qū)別 程序靜程序靜態(tài)的，的，進(jìn)程是程是動態(tài)的。的。程序和程序和進(jìn)程的程的組成不同：成不同：進(jìn)程程=程序程序+數(shù)據(jù)數(shù)據(jù)+PCB 程序的存在是永久的，程序的存在是程序的存在是永久的，程序的存在是暫時的。的。一個程序可以一個程序可以對應(yīng)多個多個進(jìn)程，一個程，一個進(jìn)程可包含程可包含多個程序。多個程序。mxh進(jìn)程的特征進(jìn)程的特征進(jìn)程的特征進(jìn)程的特征動態(tài)性性：進(jìn)程是個程是個動態(tài)的概念，有一定的生命周期，要的概念，有一定的生命周期，要經(jīng)歷創(chuàng)建、建、執(zhí)行、撤行、撤銷過程。程。結(jié)構(gòu)性構(gòu)性：它由：它由進(jìn)程控制程控制塊、程序段和數(shù)據(jù)段、程序段和數(shù)據(jù)段組成成。并并發(fā)性性：在一個系：在一個系統(tǒng)內(nèi)可以同內(nèi)可以同時存在多個存在多個進(jìn)程，它程，它們通通過交替使用交替使用處理器，從而理器，從而實現(xiàn)并并發(fā)執(zhí)行。行。異步性：異步性：指指進(jìn)程之程之間在交替使用在交替使用計算機(jī)算機(jī)資源源時沒有沒有強(qiáng)制制的的順序，按各自獨(dú)立的、不可序，按各自獨(dú)立的、不可預(yù)知的速度向前推知的速度向前推進(jìn)。獨(dú)立性：獨(dú)立性：進(jìn)程是系程是系統(tǒng)分配分配資源和源和進(jìn)行行調(diào)度的獨(dú)立度的獨(dú)立單位。位。mxh3.2.2 3.2.2 3.2.2 3.2.2 進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài) 進(jìn)程從程從創(chuàng)建而建而產(chǎn)生至撤生至撤銷而消亡的整個生命周期，而消亡的整個生命周期，可用一可用一組狀狀態(tài)加以刻畫，按加以刻畫，按進(jìn)程在程在執(zhí)行行過程中的狀程中的狀況至少定況至少定義三種不同的三種不同的進(jìn)程狀程狀態(tài)：a 運(yùn)行運(yùn)行態(tài)（RunningRunning）a 就就緒狀狀態(tài)（ReadyReady）a 阻塞狀阻塞狀態(tài)（BlockedBlocked）當(dāng)前進(jìn)程已經(jīng)分配到當(dāng)前進(jìn)程已經(jīng)分配到CPUCPU，它的程，它的程序正在處理機(jī)上執(zhí)行的狀態(tài)。序正在處理機(jī)上執(zhí)行的狀態(tài)。已具備運(yùn)行條件，但因為其他進(jìn)程已具備運(yùn)行條件，但因為其他進(jìn)程正在占用正在占用CPU,CPU,使它暫時不能運(yùn)行而使它暫時不能運(yùn)行而處于等待分配處于等待分配CPUCPU的狀態(tài)。的狀態(tài)。進(jìn)程因等待某種事件發(fā)生（例如等待進(jìn)程因等待某種事件發(fā)生（例如等待I/OI/O操作完成，等待其他進(jìn)程發(fā)來的信操作完成，等待其他進(jìn)程發(fā)來的信號）而暫時不能運(yùn)行的狀態(tài)，也就是說，號）而暫時不能運(yùn)行的狀態(tài)，也就是說，處于阻塞狀態(tài)的進(jìn)程尚不具備運(yùn)行條件，處于阻塞狀態(tài)的進(jìn)程尚不具備運(yùn)行條件，即使即使CPUCPU空閑它也無法使用?？臻e它也無法使用。mxh3.2.2 3.2.2 3.2.2 3.2.2 進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)引起引起進(jìn)程狀程狀態(tài)轉(zhuǎn)換原因原因就就緒-運(yùn)行運(yùn)行時間一到，一到，調(diào)度程序度程序選擇一個新的一個新的進(jìn)程運(yùn)行程運(yùn)行運(yùn)行運(yùn)行-就就緒運(yùn)行運(yùn)行進(jìn)程用完了程用完了時間片；運(yùn)行片；運(yùn)行進(jìn)程被中斷，因程被中斷，因為一一高高優(yōu)先先級進(jìn)程程處于就于就緒狀狀態(tài)mxh3.2.2 3.2.2 3.2.2 3.2.2 進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)引起引起進(jìn)程狀程狀態(tài)轉(zhuǎn)換原因原因運(yùn)行運(yùn)行-阻塞阻塞當(dāng)一當(dāng)一進(jìn)程所需的程所需的東西必西必須等待等待時對一一資源的源的訪問尚不能尚不能進(jìn)行行初始化初始化I/O I/O 且必且必須等待等待結(jié)果果等待某一等待某一進(jìn)程提供程提供輸入入阻塞阻塞-就就緒當(dāng)所等待的事件當(dāng)所等待的事件發(fā)生生時mxh3.2.2 3.2.2 3.2.2 3.2.2 進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程三種狀程三種狀態(tài)的的轉(zhuǎn)換mxh3.2.2 3.2.2 3.2.2 3.2.2 進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài) 有一個有一個計算機(jī)科學(xué)家，有一天女兒算機(jī)科學(xué)家，有一天女兒過生日，想生日，想親手手給女兒做一個生日蛋糕。所以他就找了一本有關(guān)做蛋女兒做一個生日蛋糕。所以他就找了一本有關(guān)做蛋糕的食糕的食譜，買了一些原料，面粉、了一些原料，面粉、雞蛋、糖、香料等，蛋、糖、香料等，然后然后邊看看邊學(xué)學(xué)邊做。做。食食譜程序；科學(xué)家程序；科學(xué)家CPUCPU；原料數(shù)據(jù)；做蛋糕原料數(shù)據(jù)；做蛋糕進(jìn)程；程；這時小兒子哭著跑小兒子哭著跑進(jìn)來，來，說手被蜜蜂手被蜜蜂蟄了。教授只了。教授只好把蛋糕先放在一好把蛋糕先放在一邊。他在食。他在食譜上做了個上做了個標(biāo)記，把狀，把狀態(tài)信息信息記錄了起來。然后又去找了一本醫(yī)了起來。然后又去找了一本醫(yī)療手冊，手冊，查到了相關(guān)的內(nèi)容，按照上面的指令一步步地到了相關(guān)的內(nèi)容，按照上面的指令一步步地執(zhí)行。當(dāng)行。當(dāng)傷口口處理完之后，又回到廚房理完之后，又回到廚房繼續(xù)做蛋糕。做蛋糕。CPUCPU從一個從一個進(jìn)程（做蛋糕）切程（做蛋糕）切換到另一個到另一個進(jìn)程（醫(yī)程（醫(yī)療救救護(hù)）。）。mxh3.2.2 3.2.2 3.2.2 3.2.2 進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)五狀態(tài)模型：新建態(tài)新建態(tài)就緒態(tài)：允許進(jìn)入就緒態(tài)：允許進(jìn)入運(yùn)行態(tài)運(yùn)行態(tài)完成態(tài)完成態(tài)：執(zhí)行完：執(zhí)行完mxh3.2.2 3.2.2 3.2.2 3.2.2 進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)問題出出現(xiàn)進(jìn)程掛起（程掛起（suspendsuspend）進(jìn)程不斷程不斷創(chuàng)建，系建，系統(tǒng)資源已不源已不滿足足進(jìn)程程運(yùn)行的要求，系運(yùn)行的要求，系統(tǒng)就必就必須把某些把某些進(jìn)程掛起，程掛起，即將即將進(jìn)程程對換到磁到磁盤中，中，暫時不參與不參與進(jìn)程程調(diào)度，已達(dá)到平衡操作系度，已達(dá)到平衡操作系統(tǒng)負(fù)荷的目的。荷的目的。引起引起進(jìn)程掛起原因程掛起原因(P45-46(P45-46：(1)-(4)1)-(4)mxh掛起（掛起（Suspend):把一個把一個進(jìn)程從內(nèi)存程從內(nèi)存轉(zhuǎn)到外到外存。存。激活（激活（Activate）:把一個把一個進(jìn)程從外存程從外存轉(zhuǎn)到到內(nèi)存。內(nèi)存。mxh引入掛起狀態(tài)后的七狀態(tài)模型引入掛起狀態(tài)后的七狀態(tài)模型mxhLinuxLinuxLinuxLinux進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)進(jìn)程的狀態(tài) D Uninterruptible sleep(usually IO)R Running or runnable(on run queue)S Interruptible sleep(waiting for an event to complete)T Stopped,either by a job control signal or because it is being traced.X dead(should never be seen)Z Defunct(zombie)process,terminated but not reaped by its parent.high-priority(not nice to other users)N low-priority(nice to other users)L has pages locked into memory(for real-time and custom IO)s is a session leaderl is multi-threaded(using CLONE_THREAD,like NPTL pthreads do)+is in the foreground process groupmxh例題例題例題例題 1 1如果系如果系統(tǒng)中有中有N N個個進(jìn)程，運(yùn)行的程，運(yùn)行的進(jìn)程最多幾個，最少幾個；就程最多幾個，最少幾個；就緒進(jìn)程最程最多幾個最少幾個；等待多幾個最少幾個；等待進(jìn)程最多幾個，最少幾個？程最多幾個，最少幾個？解答解答：在：在單處理機(jī)系理機(jī)系統(tǒng)中，中，處于運(yùn)行狀于運(yùn)行狀態(tài)的的進(jìn)程最多程最多為1 1個，最少個，最少為0 0個；個；處于就于就緒進(jìn)程最多程最多為N-1N-1個，最少個，最少為0 0個；個；處于阻塞的于阻塞的進(jìn)程最多程最多為N N個，個，最少最少為0 0個。個。2.2.有沒有有沒有這樣的狀的狀態(tài)轉(zhuǎn)換，為什么？什么？（1 1）等待等待運(yùn)行；運(yùn)行；（2 2）就就緒等待等待mxh3.2.3 3.2.3 3.2.3 3.2.3 進(jìn)程控制塊進(jìn)程控制塊進(jìn)程控制塊進(jìn)程控制塊進(jìn)程描述程描述進(jìn)程控制程控制塊程序和數(shù)據(jù)程序和數(shù)據(jù)組成了成了進(jìn)程的程的實體（靜體（靜態(tài)文本）文本）需要一個數(shù)據(jù)需要一個數(shù)據(jù)結(jié)構(gòu)來描述構(gòu)來描述進(jìn)程當(dāng)前狀程當(dāng)前狀態(tài)、本身、本身特性、特性、對資源的占用以及源的占用以及調(diào)度信息等，即度信息等，即進(jìn)程程控制控制塊（Process Control Block,PCBProcess Control Block,PCB）進(jìn)程進(jìn)程程序程序+數(shù)據(jù)數(shù)據(jù)+PCB+PCBmxh3.2.3 3.2.3 3.2.3 3.2.3 進(jìn)程控制塊進(jìn)程控制塊進(jìn)程控制塊進(jìn)程控制塊mxh3.2.3 3.2.3 3.2.3 3.2.3 進(jìn)程控制塊進(jìn)程控制塊進(jìn)程控制塊進(jìn)程控制塊PCBPCB是進(jìn)程存在是進(jìn)程存在的唯一標(biāo)志；的唯一標(biāo)志；PCBPCB常駐內(nèi)存常駐內(nèi)存pidpid進(jìn)程狀態(tài)進(jìn)程狀態(tài)現(xiàn)場現(xiàn)場優(yōu)先級優(yōu)先級阻塞原因阻塞原因程序地址程序地址同步機(jī)制同步機(jī)制資源清單資源清單鏈接指針鏈接指針mxhCPUCPUCPUCPU在進(jìn)程之間的切換在進(jìn)程之間的切換在進(jìn)程之間的切換在進(jìn)程之間的切換mxhPCBPCBPCBPCB的組織的組織的組織的組織鏈表：同一狀表：同一狀態(tài)的的進(jìn)程其程其PCBPCB組成一成一鏈表，表，多個狀多個狀態(tài)對應(yīng)多個不同的多個不同的鏈表。表。各狀各狀態(tài)的的進(jìn)程形成不同的程形成不同的鏈表：就表：就緒鏈表、阻塞表、阻塞鏈表表mxh鏈鏈表表表表執(zhí)行指針執(zhí)行指針就緒隊列指針就緒隊列指針阻塞隊列指針阻塞隊列指針1PCB90PCB89PCB77PCB6PCB58PCB40PCB33PCB24PCB1PCBPCBPCBPCB的組織的組織的組織的組織mxhPCBPCBPCBPCB的組織的組織的組織的組織索引表：同一狀索引表：同一狀態(tài)的的進(jìn)程程歸入一個入一個indexindex表表（由（由indexindex指向指向PCBPCB），多個狀），多個狀態(tài)對應(yīng)多個不多個不同的同的indexindex表表各狀各狀態(tài)的的進(jìn)行形成不同的索引表：就行形成不同的索引表：就緒索引表、阻塞索引表索引表、阻塞索引表mxh3.2.3 3.2.3 3.2.3 3.2.3 進(jìn)程控制塊進(jìn)程控制塊進(jìn)程控制塊進(jìn)程控制塊PCBPCB的的組織索引表索引表執(zhí)行指針執(zhí)行指針就緒表指針就緒表指針阻塞表指針阻塞表指針PCB7PCB6PCB5PCB4PCB3PCB2PCB1mxh補(bǔ)充補(bǔ)充補(bǔ)充補(bǔ)充PCBPCB和進(jìn)程的代碼數(shù)據(jù)放在一起嗎？和進(jìn)程的代碼數(shù)據(jù)放在一起嗎？系統(tǒng)態(tài)和用戶態(tài)系統(tǒng)態(tài)和用戶態(tài)系統(tǒng)空間和用戶空間系統(tǒng)空間和用戶空間mxh3.3 3.3 3.3 3.3 進(jìn)程控制進(jìn)程控制進(jìn)程控制進(jìn)程控制OS如何管理和控制如何管理和控制進(jìn)程程必必須知道知道進(jìn)程的位置程的位置（依（依賴于所使用的存于所使用的存儲管管理方案）理方案）必必須知道知道進(jìn)程的屬性程的屬性（PCB）必必須能能夠創(chuàng)建、撤建、撤銷進(jìn)程程必必須能能夠改改變進(jìn)程的狀程的狀態(tài)mxhl 進(jìn)程控制的職責(zé)：l 進(jìn)程的創(chuàng)建l 進(jìn)程的撤消l 進(jìn)程的阻塞與喚醒l 進(jìn)程控制是通過執(zhí)行各種原語來實現(xiàn)的。3.3 3.3 3.3 3.3 進(jìn)程控制進(jìn)程控制進(jìn)程控制進(jìn)程控制mxh原原語是由若干條機(jī)器指令構(gòu)成的、用于完是由若干條機(jī)器指令構(gòu)成的、用于完成特定功能的一段程序。原成特定功能的一段程序。原語在在執(zhí)行行過程程中是不可分割的。（中是不可分割的。（P47）3.3 3.3 3.3 3.3 進(jìn)程控制進(jìn)程控制進(jìn)程控制進(jìn)程控制mxh3.3.3 3.3.3 3.3.3 3.3.3 進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建進(jìn)程圖進(jìn)程圖引起創(chuàng)建進(jìn)程的事件引起創(chuàng)建進(jìn)程的事件進(jìn)程的創(chuàng)建過程進(jìn)程的創(chuàng)建過程123mxh3.3.3 3.3.3 3.3.3 3.3.3 進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建A AB BC CD DE EI IJ JF FHHL LMMKKGGA AB BC CD DE EI IJ JF FHHL LMMKKGGmxh入口入口查查PCBPCB鏈表鏈表有空有空PCBPCB取空表取空表PCB(i)PCB(i)填填PCB(i)PCB(i)相應(yīng)項相應(yīng)項PCB(i)PCB(i)入就緒隊列入就緒隊列PCB(i)PCB(i)入進(jìn)程家族入進(jìn)程家族返回返回創(chuàng)建失敗創(chuàng)建失敗YNmxh進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建#include#include pid_t fork(void);功能：創(chuàng)建一個新的進(jìn)程。返回值：在子進(jìn)程中為0，在父進(jìn)程中為子進(jìn)程ID，出錯為-1mxh進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建該函數(shù)被調(diào)用一次，但返回兩次。兩次返回的區(qū)別是子進(jìn)程的返回值是0，而父進(jìn)程的返回值則是子進(jìn)程的進(jìn)程ID一般來說，在fork之后是父進(jìn)程先執(zhí)行還是子進(jìn)程先執(zhí)行是不確定的。這取決于內(nèi)核所使用的調(diào)度算法。新創(chuàng)建的子進(jìn)程是父進(jìn)程的完全克隆完全克隆,會復(fù)制父進(jìn)程的數(shù)據(jù)段、堆、棧空間（共享代碼段）。mxh進(jìn)程相關(guān)術(shù)語進(jìn)程相關(guān)術(shù)語進(jìn)程相關(guān)術(shù)語進(jìn)程相關(guān)術(shù)語init 進(jìn)程領(lǐng)養(yǎng)：當(dāng)父進(jìn)程在子進(jìn)程結(jié)束前結(jié)束，子進(jìn)程變成了孤兒進(jìn)程，孤兒進(jìn)程被init進(jìn)程收養(yǎng)，子進(jìn)程的父進(jìn)程就變成了init進(jìn)程。僵尸進(jìn)程當(dāng)子進(jìn)程在父進(jìn)程結(jié)束前結(jié)束，如果父進(jìn)程沒有釋放子進(jìn)程的資源(默認(rèn))，那么子進(jìn)程就變成了一個僵尸進(jìn)程。mxh進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建mxh3.3.4 3.3.4 3.3.4 3.3.4 引起進(jìn)程終止的事件引起進(jìn)程終止的事件引起進(jìn)程終止的事件引起進(jìn)程終止的事件壽終：進(jìn)程運(yùn)行完自行退出壽終：進(jìn)程運(yùn)行完自行退出自殺：進(jìn)程因錯誤而自行退出自殺：進(jìn)程因錯誤而自行退出mxh3.3.2 3.3.2 3.3.2 3.3.2 引起進(jìn)程終止的事件引起進(jìn)程終止的事件引起進(jìn)程終止的事件引起進(jìn)程終止的事件他殺：進(jìn)程被其它進(jìn)程強(qiáng)行殺他殺：進(jìn)程被其它進(jìn)程強(qiáng)行殺死或由用戶殺死死或由用戶殺死處決：進(jìn)程因異常而強(qiáng)行終結(jié)處決：進(jìn)程因異常而強(qiáng)行終結(jié)mxh 檢索相應(yīng)的PCB，讀其狀態(tài) 若處于執(zhí)行狀態(tài)，則終止執(zhí)行 若有子孫進(jìn)程則終止子孫進(jìn)程 釋放終止進(jìn)程的全部資源 將PCB從隊列中移出3.3.4 進(jìn)程的終止過程mxh入口查進(jìn)程鏈表有此PCB釋放該進(jìn)程所占資源釋放該P(yáng)CB結(jié)構(gòu)本身返回出錯處理有子進(jìn)程無有有無mxh3.3.3 3.3.3 3.3.3 3.3.3 進(jìn)程的阻塞與喚醒進(jìn)程的阻塞與喚醒進(jìn)程的阻塞與喚醒進(jìn)程的阻塞與喚醒1、引起進(jìn)程阻塞的事件2、進(jìn)程阻塞的過程3、進(jìn)程喚醒的過程4、喚醒原語的執(zhí)行過程mxh引起進(jìn)引起進(jìn)程阻塞程阻塞的事件的事件啟動某種操作啟動某種操作請求系統(tǒng)服務(wù)請求系統(tǒng)服務(wù)新數(shù)據(jù)尚未到達(dá)新數(shù)據(jù)尚未到達(dá)無新工作可做無新工作可做mxh 執(zhí)行狀態(tài)的進(jìn)程調(diào)用阻塞原語 進(jìn)程變?yōu)樽枞麪顟B(tài) PCB進(jìn)入阻塞隊列 轉(zhuǎn)進(jìn)程調(diào)度程序，進(jìn)行切換進(jìn)程阻塞的過程mxh被阻塞進(jìn)程期待的事件發(fā)生。由發(fā)現(xiàn)者進(jìn)程調(diào)用喚醒原語 喚醒阻塞進(jìn)程。阻塞進(jìn)程進(jìn)入就緒狀態(tài)。進(jìn)程喚醒的過程mxh3.3 3.3 3.3 3.3 進(jìn)程控制進(jìn)程控制進(jìn)程控制進(jìn)程控制Linux進(jìn)程控制原程控制原語:進(jìn)程程創(chuàng)建建 fork進(jìn)程程監(jiān)控控 ps進(jìn)程程終止止 killmxh3.4 3.4 3.4 3.4 線程線程線程線程線程的引入程的引入進(jìn)程：程：資源分配源分配單位和位和CPU調(diào)度度單位位缺點(diǎn)：缺點(diǎn)：時間空空間開開銷大，限制并大，限制并發(fā)度的提高度的提高將程序?qū)⒊绦驂K的的執(zhí)行從行從進(jìn)程中分離出來程中分離出來程序程序塊執(zhí)行需要行需要單獨(dú)的：獨(dú)的：執(zhí)行狀行狀態(tài)：寄存器內(nèi)容、：寄存器內(nèi)容、棧、局部內(nèi)存、局部內(nèi)存程序程序塊執(zhí)行不需要行不需要單獨(dú)的：獨(dú)的：進(jìn)程程資源：如文件、源：如文件、頁表內(nèi)容等表內(nèi)容等多多線程：將一個程序分成多個并程：將一個程序分成多個并發(fā)的活的活動（程（程序序塊）mxh3.4 3.4 3.4 3.4 線程線程線程線程進(jìn)程程=線程程+資源集源集進(jìn)程作程作為擁有有資源的基本源的基本單位，位，線程是系程是系統(tǒng)調(diào)度的基本度的基本單位。位。mxh3.4 3.4 3.4 3.4 線程線程線程線程進(jìn)程和程和線程程資源所有源所有權(quán)（Process）調(diào)度的度的實體（體（Thread）mxh3.4 3.4 3.4 3.4 線程線程線程線程線程描述程描述線程狀程狀態(tài)（運(yùn)行、就（運(yùn)行、就緒、等待）、等待）一個一個執(zhí)行行棧未運(yùn)行未運(yùn)行時保存的保存的線程上下文、靜程上下文、靜態(tài)存存儲局部局部變量量對內(nèi)存和其他內(nèi)存和其他進(jìn)程程資源的源的訪問與與該進(jìn)程中其他程中其他線程共享程共享資源源mxh3.4 3.4 3.4 3.4 線程線程線程線程用用戶級線程程由由應(yīng)用程序（用程序（線程程庫）實現(xiàn)線程管理（程管理（POSIX Pthreads、Win32 threads）內(nèi)核感內(nèi)核感覺不到不到線程的存在程的存在優(yōu)點(diǎn)點(diǎn)共享一個共享一個進(jìn)程用程用戶空空間中，中，線程管理不需要內(nèi)核模式的程管理不需要內(nèi)核模式的切切換可運(yùn)行任何可運(yùn)行任何OS上，內(nèi)核無需修改。上，內(nèi)核無需修改。缺點(diǎn)缺點(diǎn)全阻塞全阻塞不能運(yùn)用多不能運(yùn)用多處理技理技術(shù)mxh3.4 3.4 3.4 3.4 線程線程線程線程用戶級線程用戶級線程mxh內(nèi)核級線程（在處理機(jī)上被調(diào)度和執(zhí)行的對象）由內(nèi)核實現(xiàn)線程管理克服了用戶級線程的缺點(diǎn)線程切換需要到內(nèi)核的模式切換3.4 3.4 3.4 3.4 線程線程線程線程mxh內(nèi)核級線程內(nèi)核級線程3.4 3.4 3.4 3.4 線程線程線程線程mxh3.4 3.4 3.4 3.4 線程線程線程線程mxh程序、程序、進(jìn)程、程、線程的比程的比較程序：程序：一一組有序指令的集合有序指令的集合進(jìn)程：程：系系統(tǒng)分配分配資源的基本源的基本單位位線程：程：處理機(jī)理機(jī)調(diào)度的基本度的基本單位位3.4 3.4 3.4 3.4 線程線程線程線程mxh3.4 3.4 3.4 3.4 線程線程線程線程多多線程程編程程優(yōu)點(diǎn)：點(diǎn)：響響應(yīng)程度高程度高資源共享源共享經(jīng)濟(jì)多多處理器體系理器體系結(jié)構(gòu)利用構(gòu)利用mxhmxhmxh3.5 3.5 3.5 3.5 處理器調(diào)度處理器調(diào)度處理器調(diào)度處理器調(diào)度請思考：我思考：我們是如何確定在任意是如何確定在任意時刻到刻到底哪個底哪個進(jìn)程程執(zhí)行，哪個不行，哪個不執(zhí)行呢？行呢？進(jìn)程管理的一個主要任程管理的一個主要任務(wù)就是就是選擇下一下一個要運(yùn)行的個要運(yùn)行的進(jìn)程。程。mxh要解決的要解決的問題WHAT:按什么原按什么原則分配分配CPU-進(jìn)程程調(diào)度算法度算法WHEN:何何時分配分配CPU-進(jìn)程程調(diào)度度時機(jī)機(jī)HOW：如何分配：如何分配CPU-進(jìn)程程調(diào)度方式度方式 3.5 3.5 3.5 3.5 處理器調(diào)度處理器調(diào)度處理器調(diào)度處理器調(diào)度mxhWHAT:WHAT:WHAT:WHAT:選擇進(jìn)程調(diào)度算法的標(biāo)準(zhǔn)選擇進(jìn)程調(diào)度算法的標(biāo)準(zhǔn)選擇進(jìn)程調(diào)度算法的標(biāo)準(zhǔn)選擇進(jìn)程調(diào)度算法的標(biāo)準(zhǔn)CPUCPU利用率利用率用用戶程序響程序響應(yīng)時間系系統(tǒng)吞吐量吞吐量公平合理公平合理設(shè)備利用率利用率mxhWHEN:WHEN:WHEN:WHEN:進(jìn)程調(diào)度時機(jī)進(jìn)程調(diào)度時機(jī)進(jìn)程調(diào)度時機(jī)進(jìn)程調(diào)度時機(jī)時間片片過期期進(jìn)程退出程退出進(jìn)程阻塞程阻塞I/O中斷中斷發(fā)生生mxhHOW:HOW:HOW:HOW:進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式 1.1.非搶占方式非搶占方式:簡單，實時性差簡單，實時性差 2.2.搶占方式搶占方式:（1 1）時間片原則）時間片原則（2 2）優(yōu)先權(quán)原則）優(yōu)先權(quán)原則（3 3）短作業(yè)優(yōu)先原則。）短作業(yè)優(yōu)先原則。mxh處理器調(diào)度的層次處理器調(diào)度的層次處理器調(diào)度的層次處理器調(diào)度的層次mxh（1 1）CPUCPU利用率利用率 CPUCPU利用率利用率=CPU=CPU有效工作有效工作時間/CPU/CPU總運(yùn)行運(yùn)行時間=CPU=CPU有效工作有效工作時間/(CPU/(CPU有效工作有效工作時間+CPU+CPU空空閑等待等待時間)（2 2）吞吐量（特）吞吐量（特別用于批用于批處理）理）使得使得單位位時間內(nèi)內(nèi)處理的作理的作業(yè)數(shù)盡可能多。數(shù)盡可能多。選擇調(diào)度算法的原則(面向系統(tǒng))mxh（3）周轉(zhuǎn)時間）周轉(zhuǎn)時間從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的時間間隔稱作作業(yè)周轉(zhuǎn)時間。作業(yè)周轉(zhuǎn)時間：作業(yè)周轉(zhuǎn)時間：ti=tf -ts 實際上，實際上，ti 是作業(yè)在系統(tǒng)里等待時間和運(yùn)行是作業(yè)在系統(tǒng)里等待時間和運(yùn)行時間之和。時間之和。平均作業(yè)周轉(zhuǎn)時間平均作業(yè)周轉(zhuǎn)時間:選擇調(diào)度算法的原則(面向用戶)mxh（4）響應(yīng)時間）響應(yīng)時間交互式進(jìn)程從提交一個請求到接收到響交互式進(jìn)程從提交一個請求到接收到響應(yīng)之間的時間間隔。應(yīng)之間的時間間隔。（5）公平性）公平性確保每個用戶每個進(jìn)程獲得合理的CPU份額和其它資源份額，不會出現(xiàn)餓死的情況。選擇調(diào)度算法的原則選擇調(diào)度算法的原則(面向用戶面向用戶)mxh調(diào)度算法一調(diào)度算法一調(diào)度算法一調(diào)度算法一(FCFS)(FCFS)(FCFS)(FCFS)1 1、先來先服、先來先服務(wù)(First-come,first-served,FCFS)(First-come,first-served,FCFS)最先最先進(jìn)入就入就緒進(jìn)程首先分配到程首先分配到CPUCPU，F(xiàn)CFSFCFS策略可用策略可用FIFOFIFO隊列列實現(xiàn) 缺點(diǎn)：只缺點(diǎn)：只顧及到等候及到等候時間，沒有考，沒有考慮要求服要求服務(wù)時間長短。（不利于短作短。（不利于短作業(yè)）mxh例例例例:如下一組進(jìn)程如下一組進(jìn)程如下一組進(jìn)程如下一組進(jìn)程P1P1P1P1、P2P2P2P2、P3P3P3P3，到達(dá)系統(tǒng)的先后順序分別如下，到達(dá)系統(tǒng)的先后順序分別如下，到達(dá)系統(tǒng)的先后順序分別如下，到達(dá)系統(tǒng)的先后順序分別如下面三圖所示，計算各種順序的平均周轉(zhuǎn)時間面三圖所示，計算各種順序的平均周轉(zhuǎn)時間面三圖所示，計算各種順序的平均周轉(zhuǎn)時間面三圖所示，計算各種順序的平均周轉(zhuǎn)時間進(jìn)程到達(dá)時間運(yùn)行時間P1028P219P323進(jìn)程到達(dá)時間運(yùn)行時間P209P1128P323進(jìn)程到達(dá)時間運(yùn)行時間P303P219P1228mxhP1P1P2P2P3P3T=(28+36+38)/3=T=(28+36+38)/3=3434P2P2P1P1P3P3T=(9+36+38)/3=T=(9+36+38)/3=27.627.6P3P3P2P2P1P1T=(3+11+38)/3=T=(3+11+38)/3=17.317.3可可見，F(xiàn)CFSFCFS算法的平均作算法的平均作業(yè)周周轉(zhuǎn)時間與作與作業(yè)提交及提交及調(diào)度的度的順序有關(guān)。序有關(guān)。mxh調(diào)度算法二調(diào)度算法二調(diào)度算法二調(diào)度算法二(SJF)(SJF)(SJF)(SJF)2 2、短作、短作業(yè)優(yōu)先（先（shortest-job-first,SJFshortest-job-first,SJF）以以進(jìn)入系入系統(tǒng)的作的作業(yè)所要求的所要求的CPUCPU時間長短短為標(biāo)準(zhǔn)，準(zhǔn)，總是是選取估取估計計算算時間最短的作最短的作業(yè)投投入運(yùn)行。入運(yùn)行。mxh進(jìn)程名到達(dá)時間運(yùn)行時間P106P208P307P403采用采用SJFSJF調(diào)度：調(diào)度：P4P4P1P1P3P3P2P2T=13msT=13ms采用采用FCFSFCFS調(diào)度：調(diào)度：P1P1P2P2P3P3P4P4T=16.25msT=16.25msmxhSJFSJFSJFSJF缺點(diǎn)：缺點(diǎn)：難以精確估以精確估計作作業(yè)所需所需CPUCPU時間，如程序，如程序員估估計過低，系低，系統(tǒng)可能提前可能提前終止止該作作業(yè)。忽忽視作作業(yè)等待等待時間，由于系，由于系統(tǒng)不斷接受新作不斷接受新作業(yè)，而，而調(diào)度算法又度算法又總選計算算時間短的作短的作業(yè)投投入運(yùn)行，因此，使入運(yùn)行，因此，使進(jìn)入系入系統(tǒng)時間早但早但計算算時間長的作的作業(yè)等待等待時間長，會出，會出現(xiàn)饑餓現(xiàn)象。象。mxh可搶占式可搶占式可搶占式可搶占式SJFSJFSJFSJF算法算法算法算法(SRTF)(SRTF)(SRTF)(SRTF)當(dāng)一個新作當(dāng)一個新作業(yè)到達(dá)就到達(dá)就緒隊列，如果新作列，如果新作業(yè)需需要的要的CPUCPU時間短，短，則強(qiáng)行趕走當(dāng)前作行趕走當(dāng)前作業(yè)，這種算法也叫種算法也叫最短剩余最短剩余時間優(yōu)先算法先算法（shortest remaining time first,SRTFshortest remaining time first,SRTF）。）。mxh進(jìn)程名到達(dá)時間運(yùn)行時間P108P214P329P435SRTF:SRTF:P1P1P2P2P4P4P1P1P3P3T=13msT=13msSJF:SJF:P1P1P2P2P4P4P3P3T=14.25msT=14.25msmxh調(diào)度算法三調(diào)度算法三調(diào)度算法三調(diào)度算法三(HRRF)(HRRF)(HRRF)(HRRF)3 3、高響、高響應(yīng)比比優(yōu)先先調(diào)度（度（Highest Response Ratio Highest Response Ratio First,HRRF)First,HRRF)FCFSFCFS和和SJFSJF都是比都是比較片面和片面和調(diào)度算法，度算法，F(xiàn)CFSFCFS只考只考慮作作業(yè)等候等候時間而忽而忽視了作了作業(yè)計算算時間，SJFSJF正好相反，本算法是一種折衷算法，正好相反，本算法是一種折衷算法，既考既考慮作作業(yè)等待等待時間，又考，又考慮作作業(yè)運(yùn)行運(yùn)行時間，這樣既照既照顧了短作了短作業(yè)又不使又不使長作作業(yè)等待等待時間過長，改，改進(jìn)了了調(diào)度性能。度性能。mxhHRRFHRRFHRRFHRRF響響應(yīng)比比=響響應(yīng)時間/要求服要求服務(wù)時間 =（等待（等待時間+運(yùn)行運(yùn)行時間）/運(yùn)行運(yùn)行時間 =1+=1+等待等待時間/運(yùn)行運(yùn)行時間缺點(diǎn)：每次缺點(diǎn)：每次計算各道作算各道作業(yè)的響的響應(yīng)比會有一比會有一定定時間開開銷，性能比，性能比SJFSJF略差。略差。mxh作業(yè)名到達(dá)時間運(yùn)行時間P1020P2515P3105P41510SJF:SJF:P1P1P3P3P4P4P2P2T=25msT=25msFCFS:FCFS:P1P1P2P2P3P3P4P4T=28.75msT=28.75msHRRF:HRRF:P1P1P3P3P2P2P4P4T=26.25msT=26.25msmxh調(diào)度算法四調(diào)度算法四調(diào)度算法四調(diào)度算法四 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法優(yōu)優(yōu)先先級級可可以以通通過過內(nèi)內(nèi)部部或或外外部部方方式式來來定定義義。內(nèi)內(nèi)部部優(yōu)優(yōu)先先級級使使用用一一些些可可測測量量數(shù)數(shù)據(jù)據(jù)以以計計算算進(jìn)進(jìn)程程優(yōu)優(yōu)先先級級。外外部部優(yōu)優(yōu)先先級級是是通通過操作系統(tǒng)之外的準(zhǔn)則來設(shè)置的。過操作系統(tǒng)之外的準(zhǔn)則來設(shè)置的。優(yōu)優(yōu)先先級級調(diào)調(diào)度度可可以以是是可可搶搶占占的的或或者者非非搶搶占的占的。mxh靜態(tài)優(yōu)先級：創(chuàng)建進(jìn)程時就確定，直到進(jìn)程終止前都不靜態(tài)優(yōu)先級：創(chuàng)建進(jìn)程時就確定，直到進(jìn)程終止前都不改變。通常是一個整數(shù)。依據(jù)：改變。通常是一個整數(shù)。依據(jù)：進(jìn)程類型（系統(tǒng)進(jìn)程優(yōu)先級較高）進(jìn)程類型（系統(tǒng)進(jìn)程優(yōu)先級較高）對資源的需求（對對資源的需求（對CPUCPU和內(nèi)存需求少的優(yōu)先級較高）和內(nèi)存需求少的優(yōu)先級較高）用戶要求（緊迫程度和付費(fèi)多少）用戶要求（緊迫程度和付費(fèi)多少）動態(tài)優(yōu)先級：在創(chuàng)建進(jìn)程時賦予優(yōu)先級，在進(jìn)程運(yùn)行過動態(tài)優(yōu)先級：在創(chuàng)建進(jìn)程時賦予優(yōu)先級，在進(jìn)程運(yùn)行過程中可以自動改變，以后便獲得更好的調(diào)度性能。如：程中可以自動改變，以后便獲得更好的調(diào)度性能。如：在就緒隊列中等待時間延長則優(yōu)先級提高，使優(yōu)先級較低的進(jìn)程在就緒隊列中等待時間延長則優(yōu)先級提高，使優(yōu)先級較低的進(jìn)程在等待足夠了的時間后，其優(yōu)先級提高到可被調(diào)度執(zhí)行。在等待足夠了的時間后，其優(yōu)先級提高到可被調(diào)度執(zhí)行。進(jìn)程每執(zhí)行一個時間片，就降低其優(yōu)先級。進(jìn)程每執(zhí)行一個時間片，就降低其優(yōu)先級。mxh進(jìn)程名進(jìn)程名 到達(dá)到達(dá)時間時間運(yùn)行運(yùn)行時間時間優(yōu)先級優(yōu)先級P1P10 010103 3P2P20 01 11 1P3P30 02 24 4P4P40 01 15 5P5P50 05 52 2優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法P2P2P5 P5 P1P1 P3P3 P4 P4T=12T=12mxh優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法缺點(diǎn)：無缺點(diǎn)：無窮阻塞（阻塞（indefinite blockingindefinite blocking）或或饑餓（starvationstarvation）解決方案之一解決方案之一:老化老化在在19731973年關(guān)閉年關(guān)閉MITMIT的的IBM7094IBM7094時，發(fā)時，發(fā)現(xiàn)有一個低優(yōu)先級進(jìn)程是于現(xiàn)有一個低優(yōu)先級進(jìn)程是于19671967年年提交但是一直未運(yùn)行提交但是一直未運(yùn)行mxh調(diào)度算法五調(diào)度算法五調(diào)度算法五調(diào)度算法五(RR)(RR)(RR)(RR)4 4、輪轉(zhuǎn)法法調(diào)度（度（Round-robin,RRRound-robin,RR）系系統(tǒng)將所有的將所有的進(jìn)程按先程按先進(jìn)先出的原先出的原則排成一排成一個個隊列，將新來的列，將新來的進(jìn)程加到就程加到就緒隊列的末尾，列的末尾，每當(dāng)每當(dāng)執(zhí)行行調(diào)度度時，調(diào)度程序從就度程序從就緒隊列中列中選第一個第一個進(jìn)程，分配一個程，分配一個時間片，將片，將CPUCPU分配分配給進(jìn)程，程，時間片一般片一般為10ms10ms100ms100ms。mxhRRRRRRRR進(jìn)程需要程需要CPUCPU的的時間小于小于一個一個時間片的片的時間：進(jìn)程本身會程本身會釋放放CPUCPU，進(jìn)程程調(diào)度程序接著度程序接著處理就理就緒隊列的下一個列的下一個進(jìn)程。程。進(jìn)程所需程所需CPUCPU的的時間大于大于一個一個時間片的片的時間：定定時器會切斷當(dāng)前器會切斷當(dāng)前進(jìn)程，程，進(jìn)行上下文切行上下文切換，該進(jìn)程被加到程被加到隊列尾部，接著列尾部，接著進(jìn)程程調(diào)度程序度程序選擇就就緒隊列中的下一下列中的下一下進(jìn)程。程。mxh進(jìn)程名到達(dá)時間運(yùn)行時間P1024P203P303RRRR(注：時間片為注：時間片為4ms)4ms)P1P1P2P2P3P3P1P1P1P1P1P1P1P1P1P1T=15.67msT=15.67msmxhRRRRRRRR如果如果時間片太小片太小，以至于大多數(shù)，以至于大多數(shù)進(jìn)程都不可程都不可能在一個能在一個時間片內(nèi)運(yùn)行完片內(nèi)運(yùn)行完畢，切，切換就會就會頻繁，繁，系系統(tǒng)開開銷顯著增大，所以，從系著增大，所以，從系統(tǒng)效率來看，效率來看，時間片取大一點(diǎn)好。片取大一點(diǎn)好。如果如果時間片片較大大，那么，隨著就，那么，隨著就緒隊列里列里進(jìn)程數(shù)目的增加，程數(shù)目的增加，輪轉(zhuǎn)一次的一次的總時間增大，亦增大，亦即即對每個每個進(jìn)程的響程的響應(yīng)速度放慢了。速度放慢了。所以，所以，時間片大小的確定要從片大小的確定要從進(jìn)程個數(shù)，切程個數(shù)，切換開開銷，系，系統(tǒng)效率和響效率和響應(yīng)時間等多方面考等多方面考慮。mxh 例題：假如例題：假如5 5個就緒進(jìn)程其到達(dá)系統(tǒng)和所需個就緒進(jìn)程其到達(dá)系統(tǒng)和所需CPUCPU時間如下表所示時間如下表所示（單位：毫秒），如果忽略（單位：毫秒），如果忽略I/OI/O以及其他開銷分別計算采用以及其他開銷分別計算采用FCFSFCFS、非搶占式、非搶占式SJFSJF、搶占式、搶占式SJFSJF、HRRFHRRF調(diào)度算法進(jìn)行調(diào)度算法進(jìn)行CPUCPU調(diào)度調(diào)度的平均周轉(zhuǎn)時間。的平均周轉(zhuǎn)時間。進(jìn)程到達(dá)和運(yùn)行時間進(jìn)程到達(dá)和運(yùn)行時間進(jìn)程進(jìn)程到達(dá)時間到達(dá)時間運(yùn)行時間運(yùn)行時間A A0 03 3B B2 26 6C C4 44 4D D6 65 5E E8 82 2mxh 解答如下：解答如下：（1 1）采用）采用FCFSFCFS的調(diào)度順序為：的調(diào)度順序為：A AB BC CD DE E0 03 39 9131318182020平均周轉(zhuǎn)時間為：平均周轉(zhuǎn)時間為：T=(3-0)+(9-2)+(13-4)+(18-6)+(20-8)/5=8.6T=(3-0)+(9-2)+(13-4)+(18-6)+(20-8)/5=8.6帶權(quán)平均周轉(zhuǎn)時間為：帶權(quán)平均周轉(zhuǎn)時間為：W=2.56W=2.56mxh （2 2）采用非搶占）采用非搶占SJFSJF的調(diào)度順序為：的調(diào)度順序為：A AB BE EC CD D0 03 39 9111115152020平均周轉(zhuǎn)時間為：平均周轉(zhuǎn)時間為：T=7.6T=7.6帶權(quán)平均周轉(zhuǎn)時間為：帶權(quán)平均周轉(zhuǎn)時間為：W=1.84W=1.84mxh （3 3）采用搶占）采用搶占SJFSJF的調(diào)度順序為：的調(diào)度順序為：平均周轉(zhuǎn)時間為：平均周轉(zhuǎn)時間為：T=7.2T=7.2帶權(quán)平均周轉(zhuǎn)時間為：帶權(quán)平均周轉(zhuǎn)時間為：W=1.59W=1.59A AB1B1E EC CB2B20 03 38 8101015152020D D4 4mxh解答：解答：（4）HRRF算法：算法：在時刻在時刻0時進(jìn)程時進(jìn)程A就緒，此時，就緒，此時，CPU空閑，故空閑，故A運(yùn)行，運(yùn)行，到了時刻到了時刻2時進(jìn)程時進(jìn)程B就緒，進(jìn)程就緒，進(jìn)程A結(jié)束后，進(jìn)程結(jié)束后，進(jìn)程B進(jìn)入運(yùn)行，進(jìn)入運(yùn)行，接著進(jìn)程接著進(jìn)程C、D、E先后到達(dá)，進(jìn)入就緒狀態(tài)。進(jìn)程先后到達(dá)，進(jìn)入就緒狀態(tài)。進(jìn)程B運(yùn)行結(jié)運(yùn)行結(jié)束后，調(diào)度程序要從束后，調(diào)度程序要從C、D和和E中選擇一個投入運(yùn)行，為此，中選擇一個投入運(yùn)行，為此，計算它們的響應(yīng)比：計算它們的響應(yīng)比：RRc=9/4=2.25 RRd=8/5=1.60 RRe=3/2=1.50 因此，因此，C進(jìn)程被選擇投入運(yùn)行。進(jìn)程運(yùn)行進(jìn)程被選擇投入運(yùn)行。進(jìn)程運(yùn)行4個單位后結(jié)束個單位后結(jié)束mxh 進(jìn)程進(jìn)程C運(yùn)行運(yùn)行4個單位后結(jié)束，調(diào)度程序需要從個單位后結(jié)束，調(diào)度程序需要從D和和E進(jìn)程挑進(jìn)程挑選一個運(yùn)行，為此，計算它們的響應(yīng)比：選一個運(yùn)行，為此，計算它們的響應(yīng)比：RRd=12/5=2.40 RRe=7/2=3.5 因此，選擇因此，選擇E投入運(yùn)行。綜上所述，進(jìn)程的調(diào)度順序為：投入運(yùn)行。綜上所述，進(jìn)程的調(diào)度順序為：平均周轉(zhuǎn)時間為：平均周轉(zhuǎn)時間為：T=8.0 平均帶權(quán)周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間：W=2.14A AB BC CE ED D0 03 39 9131315152020mxh調(diào)度算法六調(diào)度算法六調(diào)度算法六調(diào)度算法六(多級隊列調(diào)度多級隊列調(diào)度多級隊列調(diào)度多級隊列調(diào)度)mxh調(diào)度算法七調(diào)度算法七調(diào)度算法七調(diào)度算法七(多級反饋隊列調(diào)度多級反饋隊列調(diào)度多級反饋隊列調(diào)度多級反饋隊列調(diào)度)mxh調(diào)度算法七調(diào)度算法七調(diào)度算法七調(diào)度算法七(多級反饋隊列調(diào)度多級反饋隊列調(diào)度多級反饋隊列調(diào)度多級反饋隊列調(diào)度)特點(diǎn)：長、短作業(yè)兼顧，有較好的響特點(diǎn)：長、短作業(yè)兼顧，有較好的響 應(yīng)時間應(yīng)時間（1 1）短作業(yè)一次完成；）短作業(yè)一次完成；（2 2）中型作業(yè)周轉(zhuǎn)時間不長；）中型作業(yè)周轉(zhuǎn)時間不長；（3 3）大型作業(yè)不會長期不處理。）大型作業(yè)不會長期不處理。mxh重點(diǎn)概念和內(nèi)容提示重點(diǎn)概念和內(nèi)容提示重點(diǎn)概念和內(nèi)容提示重點(diǎn)概念和內(nèi)容提示常用進(jìn)程調(diào)度算法常用進(jìn)程調(diào)度算法進(jìn)程的概念、進(jìn)程與程序的區(qū)別進(jìn)程的概念、進(jìn)程與程序的區(qū)別進(jìn)程的結(jié)構(gòu)、狀態(tài)及轉(zhuǎn)換進(jìn)程的結(jié)構(gòu)、狀態(tài)及轉(zhuǎn)換