第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)度和度和實(shí)時(shí)調(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)的錯(cuò)誤與并發(fā)有關(guān)的錯(cuò)誤與并發(fā)有關(guān)的錯(cuò)誤與并發(fā)有關(guān)的錯(cuò)誤mxh3.2 3.2 3.2 3.2 進(jìn)程的概念進(jìn)程的概念進(jìn)程的概念進(jìn)程的概念問題引入引入 程序程序這個(gè)靜個(gè)靜態(tài)概念已不能如概念已不能如實(shí)反映程序并反映程序并發(fā)執(zhí)行行過程的特征。程的特征。為了深刻描述程序了深刻描述程序動(dòng)態(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í)行行時(shí)所所發(fā)生的活生的活動(dòng)(Dijkstra)(Dijkstra)。是一個(gè)容器，是一個(gè)容器，該容器用以聚集相關(guān)容器用以聚集相關(guān)資源。源。（A.S.TanenbaumA.S.Tanenbaum）進(jìn)程是一個(gè)具有獨(dú)立功能的進(jìn)程是一個(gè)具有獨(dú)立功能的程序程序關(guān)于某關(guān)于某個(gè)個(gè)數(shù)據(jù)集合數(shù)據(jù)集合的的一次運(yùn)行活動(dòng)一次運(yùn)行活動(dòng)。是系統(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í):圖形窗口界面形窗口界面:一個(gè)窗口就是一個(gè)一個(gè)窗口就是一個(gè)進(jìn)程程打開窗口：建立一個(gè)打開窗口：建立一個(gè)進(jìn)程程關(guān)關(guān)閉窗口：一個(gè)窗口：一個(gè)進(jìn)程程結(jié)束束字符命令界面字符命令界面:一條命令一般就是一個(gè)一條命令一般就是一個(gè)進(jìn)程程命令行尾回命令行尾回車:一個(gè)一個(gè)進(jìn)程開始程開始命令命令執(zhí)行行結(jié)束束(下一命令提示符出下一命令提示符出現(xiàn)):):一個(gè)一個(gè)進(jìn)程程結(jié)束束編程程級(jí)：進(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)程是程是動(dòng)態(tài)的。的。程序和程序和進(jìn)程的程的組成不同：成不同：進(jìn)程程=程序程序+數(shù)據(jù)數(shù)據(jù)+PCB 程序的存在是永久的，程序的存在是程序的存在是永久的，程序的存在是暫時(shí)的。的。一個(gè)程序可以一個(gè)程序可以對(duì)應(yīng)多個(gè)多個(gè)進(jìn)程，一個(gè)程，一個(gè)進(jìn)程可包含程可包含多個(gè)程序。多個(gè)程序。mxh進(jìn)程的特征進(jìn)程的特征進(jìn)程的特征進(jìn)程的特征動(dòng)態(tài)性性：進(jìn)程是個(gè)程是個(gè)動(dòng)態(tài)的概念，有一定的生命周期，要的概念，有一定的生命周期，要經(jīng)歷創(chuàng)建、建、執(zhí)行、撤行、撤銷過程。程。結(jié)構(gòu)性構(gòu)性：它由：它由進(jìn)程控制程控制塊、程序段和數(shù)據(jù)段、程序段和數(shù)據(jù)段組成成。并并發(fā)性性：在一個(gè)系：在一個(gè)系統(tǒng)內(nèi)可以同內(nèi)可以同時(shí)存在多個(gè)存在多個(gè)進(jìn)程，它程，它們通通過交替使用交替使用處理器，從而理器，從而實(shí)現(xiàn)并并發(fā)執(zhí)行。行。異步性：異步性：指指進(jìn)程之程之間在交替使用在交替使用計(jì)算機(jī)算機(jī)資源源時(shí)沒有沒有強(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)生至撤生至撤銷而消亡的整個(gè)生命周期，而消亡的整個(gè)生命周期，可用一可用一組狀狀態(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)行條件，但因?yàn)槠渌M(jìn)程已具備運(yùn)行條件，但因?yàn)槠渌M(jìn)程正在占用正在占用CPU,CPU,使它暫時(shí)不能運(yùn)行而使它暫時(shí)不能運(yùn)行而處于等待分配處于等待分配CPUCPU的狀態(tài)。的狀態(tài)。進(jìn)程因等待某種事件發(fā)生（例如等待進(jìn)程因等待某種事件發(fā)生（例如等待I/OI/O操作完成，等待其他進(jìn)程發(fā)來(lái)的信操作完成，等待其他進(jìn)程發(fā)來(lái)的信號(hào)）而暫時(shí)不能運(yùn)行的狀態(tài)，也就是說(shuō)，號(hào)）而暫時(shí)不能運(yùn)行的狀態(tài)，也就是說(shuō)，處于阻塞狀態(tài)的進(jìn)程尚不具備運(yùn)行條件，處于阻塞狀態(tài)的進(jìn)程尚不具備運(yùn)行條件，即使即使CPUCPU空閑它也無(wú)法使用?？臻e它也無(wú)法使用。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)行時(shí)間一到，一到，調(diào)度程序度程序選擇一個(gè)新的一個(gè)新的進(jìn)程運(yùn)行程運(yùn)行運(yùn)行運(yùn)行-就就緒運(yùn)行運(yùn)行進(jìn)程用完了程用完了時(shí)間片；運(yùn)行片；運(yùn)行進(jìn)程被中斷，因程被中斷，因?yàn)橐灰桓吒邇?yōu)先先級(jí)進(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)程所需的程所需的東西必西必須等待等待時(shí)對(duì)一一資源的源的訪問尚不能尚不能進(jìn)行行初始化初始化I/O I/O 且必且必須等待等待結(jié)果果等待某一等待某一進(jìn)程提供程提供輸入入阻塞阻塞-就就緒當(dāng)所等待的事件當(dāng)所等待的事件發(fā)生生時(shí)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) 有一個(gè)有一個(gè)計(jì)算機(jī)科學(xué)家，有一天女兒算機(jī)科學(xué)家，有一天女兒過生日，想生日，想親手手給女兒做一個(gè)生日蛋糕。所以他就找了一本有關(guān)做蛋女兒做一個(gè)生日蛋糕。所以他就找了一本有關(guān)做蛋糕的食糕的食譜，買了一些原料，面粉、了一些原料，面粉、雞蛋、糖、香料等，蛋、糖、香料等，然后然后邊看看邊學(xué)學(xué)邊做。做。食食譜程序；科學(xué)家程序；科學(xué)家CPUCPU；原料數(shù)據(jù)；做蛋糕原料數(shù)據(jù)；做蛋糕進(jìn)程；程；這時(shí)小兒子哭著跑小兒子哭著跑進(jìn)來(lái)，來(lái)，說(shuō)手被蜜蜂手被蜜蜂蟄了。教授只了。教授只好把蛋糕先放在一好把蛋糕先放在一邊。他在食。他在食譜上做了個(gè)上做了個(gè)標(biāo)記，把狀，把狀態(tài)信息信息記錄了起來(lái)。然后又去找了一本醫(yī)了起來(lái)。然后又去找了一本醫(yī)療手冊(cè)，手冊(cè)，查到了相關(guān)的內(nèi)容，按照上面的指令一步步地到了相關(guān)的內(nèi)容，按照上面的指令一步步地執(zhí)行。當(dāng)行。當(dāng)傷口口處理完之后，又回到廚房理完之后，又回到廚房繼續(xù)做蛋糕。做蛋糕。CPUCPU從一個(gè)從一個(gè)進(jìn)程（做蛋糕）切程（做蛋糕）切換到另一個(gè)到另一個(gè)進(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)程程對(duì)換到磁到磁盤中，中，暫時(shí)不參與不參與進(jìn)程程調(diào)度，已達(dá)到平衡操作系度，已達(dá)到平衡操作系統(tǒng)負(fù)荷的目的。荷的目的。引起引起進(jìn)程掛起原因程掛起原因(P45-46(P45-46：(1)-(4)1)-(4)mxh掛起（掛起（Suspend):把一個(gè)把一個(gè)進(jìn)程從內(nèi)存程從內(nèi)存轉(zhuǎn)到外到外存。存。激活（激活（Activate）:把一個(gè)把一個(gè)進(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個(gè)個(gè)進(jìn)程，運(yùn)行的程，運(yùn)行的進(jìn)程最多幾個(gè)，最少幾個(gè)；就程最多幾個(gè)，最少幾個(gè)；就緒進(jìn)程最程最多幾個(gè)最少幾個(gè)；等待多幾個(gè)最少幾個(gè)；等待進(jìn)程最多幾個(gè)，最少幾個(gè)？程最多幾個(gè)，最少幾個(gè)？解答解答：在：在單處理機(jī)系理機(jī)系統(tǒng)中，中，處于運(yùn)行狀于運(yùn)行狀態(tài)的的進(jìn)程最多程最多為1 1個(gè)，最少個(gè)，最少為0 0個(gè)；個(gè)；處于就于就緒進(jìn)程最多程最多為N-1N-1個(gè)，最少個(gè)，最少為0 0個(gè)；個(gè)；處于阻塞的于阻塞的進(jìn)程最多程最多為N N個(gè)，個(gè)，最少最少為0 0個(gè)。個(gè)。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)程的程的實(shí)體（靜體（靜態(tài)文本）文本）需要一個(gè)數(shù)據(jù)需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)描述構(gòu)來(lái)描述進(jìn)程當(dāng)前狀程當(dāng)前狀態(tài)、本身、本身特性、特性、對(duì)資源的占用以及源的占用以及調(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)場(chǎng)現(xiàn)場(chǎng)優(yōu)先級(jí)優(yōu)先級(jí)阻塞原因阻塞原因程序地址程序地址同步機(jī)制同步機(jī)制資源清單資源清單鏈接指針鏈接指針mxhCPUCPUCPUCPU在進(jìn)程之間的切換在進(jìn)程之間的切換在進(jìn)程之間的切換在進(jìn)程之間的切換mxhPCBPCBPCBPCB的組織的組織的組織的組織鏈表：同一狀表：同一狀態(tài)的的進(jìn)程其程其PCBPCB組成一成一鏈表，表，多個(gè)狀多個(gè)狀態(tài)對(duì)應(yīng)多個(gè)不同的多個(gè)不同的鏈表。表。各狀各狀態(tài)的的進(jìn)程形成不同的程形成不同的鏈表：就表：就緒鏈表、阻塞表、阻塞鏈表表mxh鏈鏈表表表表執(zhí)行指針執(zhí)行指針就緒隊(duì)列指針就緒隊(duì)列指針阻塞隊(duì)列指針阻塞隊(duì)列指針1PCB90PCB89PCB77PCB6PCB58PCB40PCB33PCB24PCB1PCBPCBPCBPCB的組織的組織的組織的組織mxhPCBPCBPCBPCB的組織的組織的組織的組織索引表：同一狀索引表：同一狀態(tài)的的進(jìn)程程歸入一個(gè)入一個(gè)indexindex表表（由（由indexindex指向指向PCBPCB），多個(gè)狀），多個(gè)狀態(tài)對(duì)應(yīng)多個(gè)不多個(gè)不同的同的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)程的位置程的位置（依（依賴于所使用的存于所使用的存儲(chǔ)管管理方案）理方案）必必須知道知道進(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í)行各種原語(yǔ)來(lái)實(shí)現(xiàn)的。3.3 3.3 3.3 3.3 進(jìn)程控制進(jìn)程控制進(jìn)程控制進(jìn)程控制mxh原原語(yǔ)是由若干條機(jī)器指令構(gòu)成的、用于完是由若干條機(jī)器指令構(gòu)成的、用于完成特定功能的一段程序。原成特定功能的一段程序。原語(yǔ)在在執(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)項(xiàng)相應(yīng)項(xiàng)PCB(i)PCB(i)入就緒隊(duì)列入就緒隊(duì)列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)建一個(gè)新的進(jìn)程。返回值：在子進(jìn)程中為0，在父進(jìn)程中為子進(jìn)程ID，出錯(cuò)為-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一般來(lái)說(shuō)，在fork之后是父進(jìn)程先執(zhí)行還是子進(jìn)程先執(zhí)行是不確定的。這取決于內(nèi)核所使用的調(diào)度算法。新創(chuàng)建的子進(jìn)程是父進(jìn)程的完全克隆完全克隆,會(huì)復(fù)制父進(jìn)程的數(shù)據(jù)段、堆、?？臻g（共享代碼段）。mxh進(jìn)程相關(guān)術(shù)語(yǔ)進(jìn)程相關(guān)術(shù)語(yǔ)進(jìn)程相關(guān)術(shù)語(yǔ)進(jìn)程相關(guān)術(shù)語(yǔ)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)程就變成了一個(gè)僵尸進(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)程因錯(cuò)誤而自行退出自殺：進(jìn)程因錯(cuò)誤而自行退出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從隊(duì)列中移出3.3.4 進(jìn)程的終止過程mxh入口查進(jìn)程鏈表有此PCB釋放該進(jìn)程所占資源釋放該P(yáng)CB結(jié)構(gòu)本身返回出錯(cuò)處理有子進(jìn)程無(wú)有有無(wú)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、喚醒原語(yǔ)的執(zhí)行過程mxh引起進(jìn)引起進(jìn)程阻塞程阻塞的事件的事件啟動(dòng)某種操作啟動(dòng)某種操作請(qǐng)求系統(tǒng)服務(wù)請(qǐng)求系統(tǒng)服務(wù)新數(shù)據(jù)尚未到達(dá)新數(shù)據(jù)尚未到達(dá)無(wú)新工作可做無(wú)新工作可做mxh 執(zhí)行狀態(tài)的進(jìn)程調(diào)用阻塞原語(yǔ) 進(jìn)程變?yōu)樽枞麪顟B(tài) PCB進(jìn)入阻塞隊(duì)列 轉(zhuǎn)進(jìn)程調(diào)度程序，進(jìn)行切換進(jìn)程阻塞的過程mxh被阻塞進(jìn)程期待的事件發(fā)生。由發(fā)現(xiàn)者進(jìn)程調(diào)用喚醒原語(yǔ) 喚醒阻塞進(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)程控制原程控制原語(yǔ):進(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)：時(shí)間空空間開開銷大，限制并大，限制并發(fā)度的提高度的提高將程序?qū)⒊绦驂K的的執(zhí)行從行從進(jìn)程中分離出來(lái)程中分離出來(lái)程序程序塊執(zhí)行需要行需要單獨(dú)的：獨(dú)的：執(zhí)行狀行狀態(tài)：寄存器內(nèi)容、：寄存器內(nèi)容、棧、局部?jī)?nèi)存、局部?jī)?nèi)存程序程序塊執(zhí)行不需要行不需要單獨(dú)的：獨(dú)的：進(jìn)程程資源：如文件、源：如文件、頁(yè)表內(nèi)容等表內(nèi)容等多多線程：將一個(gè)程序分成多個(gè)并程：將一個(gè)程序分成多個(gè)并發(fā)的活的活動(dòng)（程（程序序塊）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)度的度的實(shí)體（體（Thread）mxh3.4 3.4 3.4 3.4 線程線程線程線程線程描述程描述線程狀程狀態(tài)（運(yùn)行、就（運(yùn)行、就緒、等待）、等待）一個(gè)一個(gè)執(zhí)行行棧未運(yùn)行未運(yùn)行時(shí)保存的保存的線程上下文、靜程上下文、靜態(tài)存存儲(chǔ)局部局部變量量對(duì)內(nèi)存和其他內(nèi)存和其他進(jìn)程程資源的源的訪問與與該進(jìn)程中其他程中其他線程共享程共享資源源mxh3.4 3.4 3.4 3.4 線程線程線程線程用用戶級(jí)線程程由由應(yīng)用程序（用程序（線程程庫(kù)）實(shí)現(xiàn)線程管理（程管理（POSIX Pthreads、Win32 threads）內(nèi)核感內(nèi)核感覺不到不到線程的存在程的存在優(yōu)點(diǎn)點(diǎn)共享一個(gè)共享一個(gè)進(jìn)程用程用戶空空間中，中，線程管理不需要內(nèi)核模式的程管理不需要內(nèi)核模式的切切換可運(yùn)行任何可運(yùn)行任何OS上，內(nèi)核無(wú)需修改。上，內(nèi)核無(wú)需修改。缺點(diǎn)缺點(diǎn)全阻塞全阻塞不能運(yùn)用多不能運(yùn)用多處理技理技術(shù)mxh3.4 3.4 3.4 3.4 線程線程線程線程用戶級(jí)線程用戶級(jí)線程mxh內(nèi)核級(jí)線程（在處理機(jī)上被調(diào)度和執(zhí)行的對(duì)象）由內(nèi)核實(shí)現(xiàn)線程管理克服了用戶級(jí)線程的缺點(diǎn)線程切換需要到內(nèi)核的模式切換3.4 3.4 3.4 3.4 線程線程線程線程mxh內(nèi)核級(jí)線程內(nèi)核級(jí)線程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)度請(qǐng)思考：我思考：我們是如何確定在任意是如何確定在任意時(shí)刻到刻到底哪個(gè)底哪個(gè)進(jìn)程程執(zhí)行，哪個(gè)不行，哪個(gè)不執(zhí)行呢？行呢？進(jìn)程管理的一個(gè)主要任程管理的一個(gè)主要任務(wù)就是就是選擇下一下一個(gè)要運(yùn)行的個(gè)要運(yùn)行的進(jìn)程。程。mxh要解決的要解決的問題WHAT:按什么原按什么原則分配分配CPU-進(jìn)程程調(diào)度算法度算法WHEN:何何時(shí)分配分配CPU-進(jìn)程程調(diào)度度時(shí)機(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)時(shí)間系系統(tǒng)吞吐量吞吐量公平合理公平合理設(shè)備利用率利用率mxhWHEN:WHEN:WHEN:WHEN:進(jìn)程調(diào)度時(shí)機(jī)進(jìn)程調(diào)度時(shí)機(jī)進(jìn)程調(diào)度時(shí)機(jī)進(jìn)程調(diào)度時(shí)機(jī)時(shí)間片片過期期進(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.非搶占方式非搶占方式:簡(jiǎn)單，實(shí)時(shí)性差簡(jiǎn)單，實(shí)時(shí)性差 2.2.搶占方式搶占方式:（1 1）時(shí)間片原則）時(shí)間片原則（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有效工作有效工作時(shí)間/CPU/CPU總運(yùn)行運(yùn)行時(shí)間=CPU=CPU有效工作有效工作時(shí)間/(CPU/(CPU有效工作有效工作時(shí)間+CPU+CPU空空閑等待等待時(shí)間)（2 2）吞吐量（特）吞吐量（特別用于批用于批處理）理）使得使得單位位時(shí)間內(nèi)內(nèi)處理的作理的作業(yè)數(shù)盡可能多。數(shù)盡可能多。選擇調(diào)度算法的原則(面向系統(tǒng))mxh（3）周轉(zhuǎn)時(shí)間）周轉(zhuǎn)時(shí)間從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的時(shí)間間隔稱作作業(yè)周轉(zhuǎn)時(shí)間。作業(yè)周轉(zhuǎn)時(shí)間：作業(yè)周轉(zhuǎn)時(shí)間：ti=tf -ts 實(shí)際上，實(shí)際上，ti 是作業(yè)在系統(tǒng)里等待時(shí)間和運(yùn)行是作業(yè)在系統(tǒng)里等待時(shí)間和運(yùn)行時(shí)間之和。時(shí)間之和。平均作業(yè)周轉(zhuǎn)時(shí)間平均作業(yè)周轉(zhuǎn)時(shí)間:選擇調(diào)度算法的原則(面向用戶)mxh（4）響應(yīng)時(shí)間）響應(yīng)時(shí)間交互式進(jìn)程從提交一個(gè)請(qǐng)求到接收到響交互式進(jìn)程從提交一個(gè)請(qǐng)求到接收到響應(yīng)之間的時(shí)間間隔。應(yīng)之間的時(shí)間間隔。（5）公平性）公平性確保每個(gè)用戶每個(gè)進(jìn)程獲得合理的CPU份額和其它資源份額，不會(huì)出現(xiàn)餓死的情況。選擇調(diào)度算法的原則選擇調(diào)度算法的原則(面向用戶面向用戶)mxh調(diào)度算法一調(diào)度算法一調(diào)度算法一調(diào)度算法一(FCFS)(FCFS)(FCFS)(FCFS)1 1、先來(lái)先服、先來(lái)先服務(wù)(First-come,first-served,FCFS)(First-come,first-served,FCFS)最先最先進(jìn)入就入就緒進(jìn)程首先分配到程首先分配到CPUCPU，F(xiàn)CFSFCFS策略可用策略可用FIFOFIFO隊(duì)列列實(shí)現(xiàn) 缺點(diǎn)：只缺點(diǎn)：只顧及到等候及到等候時(shí)間，沒有考，沒有考慮要求服要求服務(wù)時(shí)間長(zhǎng)短。（不利于短作短。（不利于短作業(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)的先后順序分別如下面三圖所示，計(jì)算各種順序的平均周轉(zhuǎn)時(shí)間面三圖所示，計(jì)算各種順序的平均周轉(zhuǎn)時(shí)間面三圖所示，計(jì)算各種順序的平均周轉(zhuǎn)時(shí)間面三圖所示，計(jì)算各種順序的平均周轉(zhuǎn)時(shí)間進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間P1028P219P323進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間P209P1128P323進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間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)時(shí)間與作與作業(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時(shí)間長(zhǎng)短短為標(biāo)準(zhǔn)，準(zhǔn)，總是是選取估取估計(jì)計(jì)算算時(shí)間最短的作最短的作業(yè)投投入運(yùn)行。入運(yùn)行。mxh進(jìn)程名到達(dá)時(shí)間運(yùn)行時(shí)間P106P208P307P403采用采用SJFSJF調(diào)度：調(diào)度：P4P4P1P1P3P3P2P2T=13msT=13ms采用采用FCFSFCFS調(diào)度：調(diào)度：P1P1P2P2P3P3P4P4T=16.25msT=16.25msmxhSJFSJFSJFSJF缺點(diǎn)：缺點(diǎn)：難以精確估以精確估計(jì)作作業(yè)所需所需CPUCPU時(shí)間，如程序，如程序員估估計(jì)過低，系低，系統(tǒng)可能提前可能提前終止止該作作業(yè)。忽忽視作作業(yè)等待等待時(shí)間，由于系，由于系統(tǒng)不斷接受新作不斷接受新作業(yè)，而，而調(diào)度算法又度算法又總選計(jì)算算時(shí)間短的作短的作業(yè)投投入運(yùn)行，因此，使入運(yùn)行，因此，使進(jìn)入系入系統(tǒng)時(shí)間早但早但計(jì)算算時(shí)間長(zhǎng)的作的作業(yè)等待等待時(shí)間長(zhǎng)，會(huì)出，會(huì)出現(xiàn)饑餓現(xiàn)象。象。mxh可搶占式可搶占式可搶占式可搶占式SJFSJFSJFSJF算法算法算法算法(SRTF)(SRTF)(SRTF)(SRTF)當(dāng)一個(gè)新作當(dāng)一個(gè)新作業(yè)到達(dá)就到達(dá)就緒隊(duì)列，如果新作列，如果新作業(yè)需需要的要的CPUCPU時(shí)間短，短，則強(qiáng)行趕走當(dāng)前作行趕走當(dāng)前作業(yè)，這種算法也叫種算法也叫最短剩余最短剩余時(shí)間優(yōu)先算法先算法（shortest remaining time first,SRTFshortest remaining time first,SRTF）。）。mxh進(jìn)程名到達(dá)時(shí)間運(yùn)行時(shí)間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è)等候等候時(shí)間而忽而忽視了作了作業(yè)計(jì)算算時(shí)間，SJFSJF正好相反，本算法是一種折衷算法，正好相反，本算法是一種折衷算法，既考既考慮作作業(yè)等待等待時(shí)間，又考，又考慮作作業(yè)運(yùn)行運(yùn)行時(shí)間，這樣既照既照顧了短作了短作業(yè)又不使又不使長(zhǎng)作作業(yè)等待等待時(shí)間過長(zhǎng)，改，改進(jìn)了了調(diào)度性能。度性能。mxhHRRFHRRFHRRFHRRF響響應(yīng)比比=響響應(yīng)時(shí)間/要求服要求服務(wù)時(shí)間 =（等待（等待時(shí)間+運(yùn)行運(yùn)行時(shí)間）/運(yùn)行運(yùn)行時(shí)間 =1+=1+等待等待時(shí)間/運(yùn)行運(yùn)行時(shí)間缺點(diǎn)：每次缺點(diǎn)：每次計(jì)算各道作算各道作業(yè)的響的響應(yīng)比會(huì)有一比會(huì)有一定定時(shí)間開開銷，性能比，性能比SJFSJF略差。略差。mxh作業(yè)名到達(dá)時(shí)間運(yùn)行時(shí)間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)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法優(yōu)優(yōu)先先級(jí)級(jí)可可以以通通過過內(nèi)內(nèi)部部或或外外部部方方式式來(lái)來(lái)定定義義。內(nèi)內(nèi)部部?jī)?yōu)優(yōu)先先級(jí)級(jí)使使用用一一些些可可測(cè)測(cè)量量數(shù)數(shù)據(jù)據(jù)以以計(jì)計(jì)算算進(jìn)進(jìn)程程優(yōu)優(yōu)先先級(jí)級(jí)。外外部部?jī)?yōu)優(yōu)先先級(jí)級(jí)是是通通過操作系統(tǒng)之外的準(zhǔn)則來(lái)設(shè)置的。過操作系統(tǒng)之外的準(zhǔn)則來(lái)設(shè)置的。優(yōu)優(yōu)先先級(jí)級(jí)調(diào)調(diào)度度可可以以是是可可搶搶占占的的或或者者非非搶搶占的占的。mxh靜態(tài)優(yōu)先級(jí)：創(chuàng)建進(jìn)程時(shí)就確定，直到進(jìn)程終止前都不靜態(tài)優(yōu)先級(jí)：創(chuàng)建進(jìn)程時(shí)就確定，直到進(jìn)程終止前都不改變。通常是一個(gè)整數(shù)。依據(jù)：改變。通常是一個(gè)整數(shù)。依據(jù)：進(jìn)程類型（系統(tǒng)進(jìn)程優(yōu)先級(jí)較高）進(jìn)程類型（系統(tǒng)進(jìn)程優(yōu)先級(jí)較高）對(duì)資源的需求（對(duì)對(duì)資源的需求（對(duì)CPUCPU和內(nèi)存需求少的優(yōu)先級(jí)較高）和內(nèi)存需求少的優(yōu)先級(jí)較高）用戶要求（緊迫程度和付費(fèi)多少）用戶要求（緊迫程度和付費(fèi)多少）動(dòng)態(tài)優(yōu)先級(jí)：在創(chuàng)建進(jìn)程時(shí)賦予優(yōu)先級(jí)，在進(jìn)程運(yùn)行過動(dòng)態(tài)優(yōu)先級(jí)：在創(chuàng)建進(jìn)程時(shí)賦予優(yōu)先級(jí)，在進(jìn)程運(yùn)行過程中可以自動(dòng)改變，以后便獲得更好的調(diào)度性能。如：程中可以自動(dòng)改變，以后便獲得更好的調(diào)度性能。如：在就緒隊(duì)列中等待時(shí)間延長(zhǎng)則優(yōu)先級(jí)提高，使優(yōu)先級(jí)較低的進(jìn)程在就緒隊(duì)列中等待時(shí)間延長(zhǎng)則優(yōu)先級(jí)提高，使優(yōu)先級(jí)較低的進(jìn)程在等待足夠了的時(shí)間后，其優(yōu)先級(jí)提高到可被調(diào)度執(zhí)行。在等待足夠了的時(shí)間后，其優(yōu)先級(jí)提高到可被調(diào)度執(zhí)行。進(jìn)程每執(zhí)行一個(gè)時(shí)間片，就降低其優(yōu)先級(jí)。進(jìn)程每執(zhí)行一個(gè)時(shí)間片，就降低其優(yōu)先級(jí)。mxh進(jìn)程名進(jìn)程名 到達(dá)到達(dá)時(shí)間時(shí)間運(yùn)行運(yùn)行時(shí)間時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)P1P10 010103 3P2P20 01 11 1P3P30 02 24 4P4P40 01 15 5P5P50 05 52 2優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法P2P2P5 P5 P1P1 P3P3 P4 P4T=12T=12mxh優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法缺點(diǎn)：無(wú)缺點(diǎn)：無(wú)窮阻塞（阻塞（indefinite blockingindefinite blocking）或或饑餓（starvationstarvation）解決方案之一解決方案之一:老化老化在在19731973年關(guān)閉年關(guān)閉MITMIT的的IBM7094IBM7094時(shí)，發(fā)時(shí)，發(fā)現(xiàn)有一個(gè)低優(yōu)先級(jí)進(jìn)程是于現(xiàn)有一個(gè)低優(yōu)先級(jí)進(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)先出的原先出的原則排成一排成一個(gè)個(gè)隊(duì)列，將新來(lái)的列，將新來(lái)的進(jìn)程加到就程加到就緒隊(duì)列的末尾，列的末尾，每當(dāng)每當(dāng)執(zhí)行行調(diào)度度時(shí)，調(diào)度程序從就度程序從就緒隊(duì)列中列中選第一個(gè)第一個(gè)進(jìn)程，分配一個(gè)程，分配一個(gè)時(shí)間片，將片，將CPUCPU分配分配給進(jìn)程，程，時(shí)間片一般片一般為10ms10ms100ms100ms。mxhRRRRRRRR進(jìn)程需要程需要CPUCPU的的時(shí)間小于小于一個(gè)一個(gè)時(shí)間片的片的時(shí)間：進(jìn)程本身會(huì)程本身會(huì)釋放放CPUCPU，進(jìn)程程調(diào)度程序接著度程序接著處理就理就緒隊(duì)列的下一個(gè)列的下一個(gè)進(jìn)程。程。進(jìn)程所需程所需CPUCPU的的時(shí)間大于大于一個(gè)一個(gè)時(shí)間片的片的時(shí)間：定定時(shí)器會(huì)切斷當(dāng)前器會(huì)切斷當(dāng)前進(jìn)程，程，進(jìn)行上下文切行上下文切換，該進(jìn)程被加到程被加到隊(duì)列尾部，接著列尾部，接著進(jìn)程程調(diào)度程序度程序選擇就就緒隊(duì)列中的下一下列中的下一下進(jìn)程。程。mxh進(jìn)程名到達(dá)時(shí)間運(yùn)行時(shí)間P1024P203P303RRRR(注：時(shí)間片為注：時(shí)間片為4ms)4ms)P1P1P2P2P3P3P1P1P1P1P1P1P1P1P1P1T=15.67msT=15.67msmxhRRRRRRRR如果如果時(shí)間片太小片太小，以至于大多數(shù)，以至于大多數(shù)進(jìn)程都不可程都不可能在一個(gè)能在一個(gè)時(shí)間片內(nèi)運(yùn)行完片內(nèi)運(yùn)行完畢，切，切換就會(huì)就會(huì)頻繁，繁，系系統(tǒng)開開銷顯著增大，所以，從系著增大，所以，從系統(tǒng)效率來(lái)看，效率來(lái)看，時(shí)間片取大一點(diǎn)好。片取大一點(diǎn)好。如果如果時(shí)間片片較大大，那么，隨著就，那么，隨著就緒隊(duì)列里列里進(jìn)程數(shù)目的增加，程數(shù)目的增加，輪轉(zhuǎn)一次的一次的總時(shí)間增大，亦增大，亦即即對(duì)每個(gè)每個(gè)進(jìn)程的響程的響應(yīng)速度放慢了。速度放慢了。所以，所以，時(shí)間片大小的確定要從片大小的確定要從進(jìn)程個(gè)數(shù)，切程個(gè)數(shù)，切換開開銷，系，系統(tǒng)效率和響效率和響應(yīng)時(shí)間等多方面考等多方面考慮。mxh 例題：假如例題：假如5 5個(gè)就緒進(jìn)程其到達(dá)系統(tǒng)和所需個(gè)就緒進(jìn)程其到達(dá)系統(tǒng)和所需CPUCPU時(shí)間如下表所示時(shí)間如下表所示（單位：毫秒），如果忽略（單位：毫秒），如果忽略I/OI/O以及其他開銷分別計(jì)算采用以及其他開銷分別計(jì)算采用FCFSFCFS、非搶占式、非搶占式SJFSJF、搶占式、搶占式SJFSJF、HRRFHRRF調(diào)度算法進(jìn)行調(diào)度算法進(jìn)行CPUCPU調(diào)度調(diào)度的平均周轉(zhuǎn)時(shí)間。的平均周轉(zhuǎn)時(shí)間。進(jìn)程到達(dá)和運(yùn)行時(shí)間進(jìn)程到達(dá)和運(yùn)行時(shí)間進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間運(yùn)行時(shí)間運(yùn)行時(shí)間A A0 03 3B B2 26 6C C4 44 4D D6 65 5E E8 82 2mxh 解答如下：解答如下：（1 1）采用）采用FCFSFCFS的調(diào)度順序?yàn)椋旱恼{(diào)度順序?yàn)椋篈 AB BC CD DE E0 03 39 9131318182020平均周轉(zhuǎn)時(shí)間為：平均周轉(zhuǎn)時(shí)間為：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)時(shí)間為：帶權(quán)平均周轉(zhuǎn)時(shí)間為：W=2.56W=2.56mxh （2 2）采用非搶占）采用非搶占SJFSJF的調(diào)度順序?yàn)椋旱恼{(diào)度順序?yàn)椋篈 AB BE EC CD D0 03 39 9111115152020平均周轉(zhuǎn)時(shí)間為：平均周轉(zhuǎn)時(shí)間為：T=7.6T=7.6帶權(quán)平均周轉(zhuǎn)時(shí)間為：帶權(quán)平均周轉(zhuǎn)時(shí)間為：W=1.84W=1.84mxh （3 3）采用搶占）采用搶占SJFSJF的調(diào)度順序?yàn)椋旱恼{(diào)度順序?yàn)椋浩骄苻D(zhuǎn)時(shí)間為：平均周轉(zhuǎn)時(shí)間為：T=7.2T=7.2帶權(quán)平均周轉(zhuǎn)時(shí)間為：帶權(quán)平均周轉(zhuǎn)時(shí)間為：W=1.59W=1.59A AB1B1E EC CB2B20 03 38 8101015152020D D4 4mxh解答：解答：（4）HRRF算法：算法：在時(shí)刻在時(shí)刻0時(shí)進(jìn)程時(shí)進(jìn)程A就緒，此時(shí)，就緒，此時(shí)，CPU空閑，故空閑，故A運(yùn)行，運(yùn)行，到了時(shí)刻到了時(shí)刻2時(shí)進(jìn)程時(shí)進(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中選擇一個(gè)投入運(yùn)行，為此，中選擇一個(gè)投入運(yùn)行，為此，計(jì)算它們的響應(yīng)比：計(jì)算它們的響應(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個(gè)單位后結(jié)束個(gè)單位后結(jié)束mxh 進(jìn)程進(jìn)程C運(yùn)行運(yùn)行4個(gè)單位后結(jié)束，調(diào)度程序需要從個(gè)單位后結(jié)束，調(diào)度程序需要從D和和E進(jìn)程挑進(jìn)程挑選一個(gè)運(yùn)行，為此，計(jì)算它們的響應(yīng)比：選一個(gè)運(yùn)行，為此，計(jì)算它們的響應(yīng)比：RRd=12/5=2.40 RRe=7/2=3.5 因此，選擇因此，選擇E投入運(yùn)行。綜上所述，進(jìn)程的調(diào)度順序?yàn)椋和度脒\(yùn)行。綜上所述，進(jìn)程的調(diào)度順序?yàn)椋浩骄苻D(zhuǎn)時(shí)間為：平均周轉(zhuǎn)時(shí)間為：T=8.0 平均帶權(quán)周轉(zhuǎn)時(shí)間：平均帶權(quán)周轉(zhuǎn)時(shí)間：W=2.14A AB BC CE ED D0 03 39 9131315152020mxh調(diào)度算法六調(diào)度算法六調(diào)度算法六調(diào)度算法六(多級(jí)隊(duì)列調(diào)度多級(jí)隊(duì)列調(diào)度多級(jí)隊(duì)列調(diào)度多級(jí)隊(duì)列調(diào)度)mxh調(diào)度算法七調(diào)度算法七調(diào)度算法七調(diào)度算法七(多級(jí)反饋隊(duì)列調(diào)度多級(jí)反饋隊(duì)列調(diào)度多級(jí)反饋隊(duì)列調(diào)度多級(jí)反饋隊(duì)列調(diào)度)mxh調(diào)度算法七調(diào)度算法七調(diào)度算法七調(diào)度算法七(多級(jí)反饋隊(duì)列調(diào)度多級(jí)反饋隊(duì)列調(diào)度多級(jí)反饋隊(duì)列調(diào)度多級(jí)反饋隊(duì)列調(diào)度)特點(diǎn)：長(zhǎng)、短作業(yè)兼顧，有較好的響特點(diǎn)：長(zhǎng)、短作業(yè)兼顧，有較好的響 應(yīng)時(shí)間應(yīng)時(shí)間（1 1）短作業(yè)一次完成；）短作業(yè)一次完成；（2 2）中型作業(yè)周轉(zhuǎn)時(shí)間不長(zhǎng)；）中型作業(yè)周轉(zhuǎn)時(shí)間不長(zhǎng)；（3 3）大型作業(yè)不會(huì)長(zhǎng)期不處理。）大型作業(yè)不會(huì)長(zhǎng)期不處理。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)換