處理器管理課件

第三章處理器管理09-處理機管理-1本次課主要內(nèi)容處理機調(diào)度調(diào)度性能評價標(biāo)準(zhǔn)進程調(diào)度算法進程調(diào)度時機與步驟常用調(diào)度算法09-處理機管理-1處理器管理的任務(wù)

在進程管理部分的設(shè)計中，目前我們已經(jīng)完成了進程描述結(jié)構(gòu)（PCB）的設(shè)計，以及進程創(chuàng)建、加載、同步、互斥、通信、終止等部分的設(shè)計，甚至考慮到了進程的死鎖，但還有一個非常重要的工作至今沒有涉及到，即進程的運行。所謂進程的運行，就是給進程分配處理器，也就是將進程調(diào)度到處理器上執(zhí)行程序。在進程管理中，負(fù)責(zé)進程運行的部分稱為進程調(diào)度，或CPU調(diào)度或處理器管理。09-處理機管理-1處理器管理(處理機調(diào)度)處理機是計算機系統(tǒng)中的重要資源處理機調(diào)度算法對整個計算機系統(tǒng)的綜合性能指標(biāo)有重要影響可把處理機調(diào)度分成三個層次：

高級調(diào)度中級調(diào)度低級調(diào)度09-處理機管理-1高級調(diào)度也稱為作業(yè)調(diào)度或宏觀調(diào)度高級調(diào)度的時間尺度通常是分鐘、小時或天中級調(diào)度涉及進程在內(nèi)外存間的交換，從存儲器資源管理的角度來看，把進程的部分或全部換出到外存上，可為當(dāng)前運行進程的執(zhí)行提供所需內(nèi)存空間。將當(dāng)前進程所需部分換入到內(nèi)存，指令和數(shù)據(jù)必須在內(nèi)存里才能被處理機直接訪問。低級調(diào)度也稱微觀調(diào)度，從處理機資源分配的角度來看，處理機需要經(jīng)常選擇就緒進程或線程進入運行狀態(tài)，低級調(diào)度的時間尺度通常是毫秒級的。由于低級調(diào)度算法的頻繁使用，要求在實現(xiàn)時做到高效處理機調(diào)度的三個層次09-處理機管理-1作業(yè)調(diào)度

在批處理時代，調(diào)度是以作業(yè)為單位的。因此，那時的處理器管理又稱為作業(yè)調(diào)度。作業(yè)調(diào)度的任務(wù)是：從處于后備狀態(tài)的作業(yè)中選擇一個作業(yè)，為其分配資源，讓它進入主機運行。在同一時間內(nèi)，系統(tǒng)中只有一個作業(yè)，該作業(yè)獨占所有的系統(tǒng)資源，包括處理器。只有當(dāng)一個作業(yè)結(jié)束后，作業(yè)調(diào)度程序才裝入下一個作業(yè)。此時的作業(yè)調(diào)度程序非常簡單，運行頻率也很低，不存在作業(yè)切換，也不用擔(dān)心處理器資源的回收問題。09-處理機管理-1在此后的發(fā)展中，為了提高處理器的利用率，人們提出了多道程序的概念，允許在系統(tǒng)中同時存在多個作業(yè)。這時作業(yè)調(diào)度的任務(wù)是：從處于后備狀態(tài)的作業(yè)中選擇一個或一批作業(yè)，讓它（它們）進入主機，為它們創(chuàng)建進程，準(zhǔn)備運行。此時，作業(yè)調(diào)度的主要工作是選擇作業(yè)、創(chuàng)建進程。為了充分發(fā)揮資源的作用，應(yīng)合理搭配作業(yè)，并控制系統(tǒng)中作業(yè)的數(shù)量。作業(yè)調(diào)度

09-處理機管理-1當(dāng)然，進入主機的作業(yè)并不一定能夠立刻運行，還需要另外一個調(diào)度程序為它們分配CPU，這就是CPU調(diào)度。所以，早期的操作系統(tǒng)要提供多個調(diào)度程序。作業(yè)調(diào)度又稱為高級調(diào)度、宏調(diào)度、長調(diào)度等，它選擇的作業(yè)具有了獲得處理器的資格。CPU調(diào)度又稱為低級調(diào)度、微調(diào)度、短調(diào)度等，它選擇能夠立刻投入運行的進程，并將處理器分配給它。兩者的關(guān)系如下圖：作業(yè)調(diào)度

輸入設(shè)備運行態(tài)就緒態(tài)封鎖態(tài)內(nèi)存輸入井后備狀態(tài)(外存)作業(yè)調(diào)度(高級)進程調(diào)度(低級)主機輸出設(shè)備作業(yè)調(diào)度與CPU調(diào)度的關(guān)系09-處理機管理-1作業(yè)調(diào)度與進程調(diào)度的關(guān)系功能不同

作業(yè)調(diào)度是宏觀調(diào)度，它從外存中處于后備狀態(tài)的作業(yè)中選擇作業(yè)進入內(nèi)存;進程調(diào)度是微觀調(diào)度，它們將CPU分配給選中的就緒進程，作業(yè)首先經(jīng)作業(yè)調(diào)度進入就緒隊列，然后才有資格被進程調(diào)度程序選中分配CPU。執(zhí)行的頻率不同 作業(yè)調(diào)度執(zhí)行的次數(shù)很少，進程調(diào)度執(zhí)行頻繁。09-處理機管理-1作業(yè)的概念主要用于批處理系統(tǒng)，這類系統(tǒng)的設(shè)計目標(biāo)是最大限度地發(fā)揮各種資源的利用率和保持系統(tǒng)內(nèi)各種活動的充分并行。作業(yè)調(diào)度的目標(biāo)是合理搭配對資源具有不同需求的作業(yè)，使系統(tǒng)中各部分資源得到均衡使用。分時系統(tǒng)中，用戶與系統(tǒng)直接交互，通過鍵盤、鼠標(biāo)等直接創(chuàng)建和啟動進程，不再需要作業(yè)調(diào)度。類似地，實時系統(tǒng)也不需要作業(yè)調(diào)度。下面主要考慮CPU調(diào)度（進程調(diào)度）的設(shè)計問題。作業(yè)調(diào)度

09-處理機管理-1處理機調(diào)度（CPU調(diào)度）要解決的問題WHAT：按什么原則分配CPU

—進程調(diào)度算法WHEN：何時分配CPU

—進程調(diào)度的時機HOW：如何分配CPU

—CPU調(diào)度過程（進程的上下文切換）09-處理機管理-1性能評價標(biāo)準(zhǔn)確定調(diào)度策略時考慮的主要因素：1、應(yīng)保證實現(xiàn)系統(tǒng)的設(shè)計目標(biāo)。2、公平對待所有作業(yè)或進程。3、均衡使用資源，盡量使系統(tǒng)中各種資源都同時得到利用。4、兼顧響應(yīng)時間和資源利用率。5、基于相對優(yōu)先級，但避免無限延期。6、系統(tǒng)開銷不應(yīng)太大。09-處理機管理-1進程調(diào)度算法確定算法的原則公平：保證每個進程得到合理的CPU時間高效：CPU保持忙碌狀態(tài)，CPU利用率高響應(yīng)時間：交互式系統(tǒng)，越短越好周轉(zhuǎn)時間：使批處理用戶等待時間盡可能短吞吐量：批處理系統(tǒng)情況下，單位時間內(nèi)處理的進程個數(shù)盡可能多09-處理機管理-1算法的評價標(biāo)準(zhǔn)很多，而且有些是互相矛盾的。根據(jù)應(yīng)用領(lǐng)域的不同，可以采用不同的評價標(biāo)準(zhǔn)。根據(jù)不同的評價標(biāo)準(zhǔn)，可以選出不同的調(diào)度算法。（1）響應(yīng)時間。從提交請求到收到第一個應(yīng)答所需要的時間。用戶的請求是由進程處理的，因此：響應(yīng)時間＝進程等待運行的時間＋產(chǎn)生第一個輸出的時間。當(dāng)然，在輸出第一個應(yīng)答以后，進程仍然可以繼續(xù)運行，并產(chǎn)生其它輸出。性能評價標(biāo)準(zhǔn)09-處理機管理-1好的調(diào)度算法應(yīng)使進程等待運行的時間盡可能地短，也就是說，應(yīng)盡快地將用戶的請求遞交給處理進程，并盡快地讓它投入運行。響應(yīng)時間是用戶可以直接感受的。研究表明，響應(yīng)時間越短，人的注意力就越容易集中，生產(chǎn)率就會越高。0.250.50.751.001.251.505001000150020002500300035004000響應(yīng)時間事務(wù)數(shù)/小時高手新手平均性能評價標(biāo)準(zhǔn)09-處理機管理-1（2）周轉(zhuǎn)時間。從進程創(chuàng)建到終止之間的時間間隔，包括進程實際的運行時間、等待資源的時間、等待調(diào)度的時間等。好的調(diào)度算法應(yīng)盡量減少進程等待調(diào)度的時間，從而減少其周轉(zhuǎn)時間。由于不同進程所完成的工作不同，其周轉(zhuǎn)時間很難統(tǒng)一。但是，如果同樣的一組進程，在同樣的機器上運行，其周轉(zhuǎn)時間越短，調(diào)度算法就越好。性能評價標(biāo)準(zhǔn)09-處理機管理-1（3）死線（Deadline）。一個進程最后完成的期限。如果允許進程聲明自己的死線，那么好的調(diào)度算法應(yīng)盡可能的滿足各進程的死線要求，并支持盡可能多的進程。（4）吞吐量。單位時間內(nèi)完成的任務(wù)（進程）數(shù)量。從系統(tǒng)角度來看，處理器調(diào)度的目的是最大化處理器的利用率。吞吐量取決于每個進程的運行長度，但它也受調(diào)度算法的影響。性能評價標(biāo)準(zhǔn)09-處理機管理-1（5）處理器利用率。百分比，表示處理器有多忙。對于大型計算機系統(tǒng)，這是一個重要指標(biāo)，但對PC機、實時系統(tǒng)等來說，并不太重要。（6）就緒等待時間。進程在就緒隊列中的等待時間。調(diào)度算法不真正影響進程的執(zhí)行時間或I/O操作的時間，它僅影響進程在就緒隊列中的等待時間。（7）公平。公平對待各個進程，不會出現(xiàn)餓死現(xiàn)象。性能評價標(biāo)準(zhǔn)09-處理機管理-1（8）優(yōu)先級。高優(yōu)先級的進程應(yīng)該受到照顧。（9）均衡利用資源。保證系統(tǒng)中的資源都處于忙狀態(tài)。不太使用緊缺資源的進程應(yīng)該受到重視，從而平衡資源的使用。（10）可預(yù)言性（Predictability）。同一個程序（作業(yè)）的每次運行應(yīng)該花費大致相同的時間和代價，不管系統(tǒng)的負(fù)載情況如何。性能評價標(biāo)準(zhǔn)09-處理機管理-1上述的標(biāo)準(zhǔn)都是獨立的，又是互相影響的，很難設(shè)計一種滿足所有標(biāo)準(zhǔn)的調(diào)度算法。如要縮短響應(yīng)時間，就必須盡快地在各個進程之間切換CPU，這必然會增加系統(tǒng)的開銷，從而降低系統(tǒng)的總吞吐量。在設(shè)計調(diào)度算法時，應(yīng)綜合考慮各種情況，在各種策略和標(biāo)準(zhǔn)之間找到一個折中，其關(guān)鍵是滿足系統(tǒng)的總體設(shè)計目標(biāo)。性能評價標(biāo)準(zhǔn)09-處理機管理-1各種進程調(diào)度算法一、先來先服務(wù)（FCFS）

基本思想：按進程（作業(yè)）到來的先后次序進行調(diào)度，先來先服務(wù)。

優(yōu)點：實現(xiàn)簡單

缺點：沒考慮進程的優(yōu)先級例：有三個進程，它們按1、2、3的順序處于就緒隊列中 進程 運行時間

P1 24 P2 3 P3 309-處理機管理-1按FCFS算法調(diào)度，執(zhí)行情況如下：P1P2

P30242730此時P1的周轉(zhuǎn)時間：TT1＝24，P2的周轉(zhuǎn)時間：

TT2＝27，P3的周轉(zhuǎn)時間：

TT3＝30平均同轉(zhuǎn)時間為： ATT＝（24＋27＋30）／3＝2709-處理機管理-1如果不是按FCFS原則調(diào)度而是按如下方式執(zhí)行：P2P3P1

03630則平均周轉(zhuǎn)時間 ATT＝（3＋6＋30）／3＝13這個結(jié)果比上面27減少了一半多。說明了什么？09-處理機管理-1二、短進程優(yōu)先(SPN--ShortestProcessNext)

基本思想：當(dāng)CPU可供使用時，SPN算法就把CPU分給最短的進程。所謂進程的長短是指進程要求運行時間的多少。

優(yōu)點：對一組給定的進程，SPN法給出最小的平均等待時間。缺點：當(dāng)一個長進程進入就緒隊列之后，若后面連續(xù)進入較短的進程，則前面這個進程就要一直等下去而無法運行。

*作業(yè)調(diào)度中的算法稱為短作業(yè)優(yōu)先