調(diào)度的隊(duì)列模型-中國(guó)科學(xué)技術(shù)大學(xué)

1、第四講 CPU調(diào)度,中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系 陳香蘭xlanchen@ustc.edu.cnFall 2013,內(nèi)容提要,調(diào)度的類型調(diào)度的隊(duì)列模型調(diào)度的準(zhǔn)則調(diào)度的算法,內(nèi)容提要,調(diào)度的類型調(diào)度的隊(duì)列模型調(diào)度的準(zhǔn)則調(diào)度的算法,調(diào)度的類型,按調(diào)度的層次：長(zhǎng)期（長(zhǎng)程、作業(yè)、高級(jí)）調(diào)度；中期（中級(jí)、中程）調(diào)度；短期（短程、進(jìn)程、低級(jí)）調(diào)度按OS的類型：批處理調(diào)度分時(shí)調(diào)度實(shí)時(shí)調(diào)度多處理機(jī)調(diào)度等等,作業(yè)調(diào)度,在批

2、處理系統(tǒng)中，一般需要進(jìn)行作業(yè)調(diào)度；分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)大多不需要作業(yè)調(diào)度作業(yè)調(diào)度要考慮1）接納多少個(gè)作業(yè)??多道程序度2）接納哪些作業(yè)??調(diào)度算法,中期調(diào)度,與掛起狀態(tài)相關(guān)目的：提高內(nèi)存利用率和系統(tǒng)吞吐量對(duì)換,進(jìn)程調(diào)度,在分時(shí)系統(tǒng)中，進(jìn)程調(diào)度的運(yùn)行頻率很高Linux中，常規(guī)經(jīng)驗(yàn)值，時(shí)間片大小50ms左右進(jìn)程調(diào)度要考慮1）什么時(shí)候 發(fā)生調(diào)度的時(shí)機(jī)2）哪個(gè)進(jìn)程 調(diào)度原則和調(diào)度算法3）如何分派 進(jìn)程上下文切換,調(diào)

3、度的方式：搶占式／非搶占式,可剝奪式（可搶占式Preemptive）： 當(dāng)有比正在運(yùn)行的進(jìn)程優(yōu)先級(jí)更高的進(jìn)程就緒時(shí)，系統(tǒng)可強(qiáng)行剝奪正在運(yùn)行進(jìn)程的CPU，提供給具有更高優(yōu)先級(jí)的進(jìn)程使用不可剝奪式（不可搶占式 Non-preemptive ）： 某一進(jìn)程被調(diào)度運(yùn)行后，除非由于它自身的原因不能運(yùn)行，否則一直運(yùn)行下去,Scheduling time 調(diào)度的時(shí)機(jī),When a processSwitches from run

4、ning to waiting stateSwitches from running to ready stateSwitches from waiting to readyTerminatesSchedulingNonpreemptive: for 1 & 4Till 1 or 4Win 3.x, old versions of MacOS, …Preemptive: for 2 & 3根據(jù)時(shí)間片搶

5、占、根據(jù)優(yōu)先關(guān)系搶占,,與進(jìn)程調(diào)度相關(guān)的進(jìn)程運(yùn)行規(guī)律分析,Process execution = n (CPU execution + I/O wait)Objective of multiprogrammingMaximum CPU utilization Scheduling is a fundamental OS function for almost all resources,Alternating Seq

6、uence of CPU And I/O Bursts,A property of process：CPU-I/O burst cycleProcess Starts as a CPU burstEnds as a CPU burstCPU burst distributionCPU-bound VS. I/O-bound,Histogram of CPU-burst Times,,內(nèi)容提要,調(diào)度的類型調(diào)度的隊(duì)列模型調(diào)

7、度的準(zhǔn)則調(diào)度的算法,調(diào)度隊(duì)列模型,按照系統(tǒng)中調(diào)度層次的數(shù)目，有3種模型僅有進(jìn)程調(diào)度的具有高級(jí)和低級(jí)調(diào)度的同時(shí)具有三種調(diào)度的,僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型,具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型,具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型,內(nèi)容提要,調(diào)度的類型調(diào)度的隊(duì)列模型調(diào)度的準(zhǔn)則調(diào)度的算法,選擇調(diào)度方式和算法的若干準(zhǔn)則,面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短響應(yīng)時(shí)間快截止時(shí)間的保證優(yōu)先權(quán)準(zhǔn)則面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐率高處理機(jī)利用率好各類資源的

8、平衡利用,面向用戶的準(zhǔn)則：1、周轉(zhuǎn)時(shí)間短,定義：作業(yè)周轉(zhuǎn)時(shí)間(Turnaround time)是指從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔。包括：1）作業(yè)在外存后備隊(duì)列上等待作業(yè)調(diào)度的時(shí)間2）進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間(waiting time)3）進(jìn)程在CPU上執(zhí)行的時(shí)間4）等待I/O操作完成的時(shí)間 其中，第2、3、4項(xiàng)在一個(gè)作業(yè)的處理過程中，可能發(fā)生多次用戶和系統(tǒng)管理員對(duì)周轉(zhuǎn)時(shí)間有不同的需求,,定義

9、：平均周轉(zhuǎn)時(shí)間定義：帶權(quán)周轉(zhuǎn)時(shí)間：作業(yè)周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供的實(shí)際服務(wù)時(shí)間Ts之比，即W=T/Ts定義：平均帶權(quán)周轉(zhuǎn)時(shí)間：通常將周轉(zhuǎn)時(shí)間作為評(píng)價(jià)批處理系統(tǒng)的性能、選擇作業(yè)調(diào)度方式和算法的準(zhǔn)則,面向用戶的準(zhǔn)則：2、響應(yīng)時(shí)間快,定義：響應(yīng)時(shí)間(Response time)是從用戶通過鍵盤提交一個(gè)請(qǐng)求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的的時(shí)間，或者說直到在屏幕上顯示出結(jié)果為止的一段時(shí)間間隔。包括：從鍵盤輸入的請(qǐng)求信息傳送到處理機(jī)的

10、時(shí)間處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間將所形成的響應(yīng)回送到終端顯示器的時(shí)間響應(yīng)時(shí)間常用于評(píng)價(jià)分時(shí)操作系統(tǒng)的性能，是選擇分時(shí)系統(tǒng)中進(jìn)程調(diào)度算法的重要準(zhǔn)則之一,面向用戶的準(zhǔn)則：3、截止時(shí)間的保證,定義：截止時(shí)間(Deadline)是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或者必須完成的最遲時(shí)間。截止時(shí)間是用來評(píng)價(jià)實(shí)時(shí)系統(tǒng)性能的重要指標(biāo)，因而是選擇實(shí)時(shí)調(diào)度算法的重要準(zhǔn)則實(shí)時(shí)系統(tǒng)軟實(shí)時(shí)系統(tǒng)(soft real-time) vs 硬實(shí)時(shí)系統(tǒng)

11、(hard real-time)非實(shí)時(shí)系統(tǒng),面向用戶的準(zhǔn)則：4、優(yōu)先權(quán)準(zhǔn)則,引入優(yōu)先權(quán)使用優(yōu)先數(shù)表示優(yōu)先權(quán)優(yōu)先權(quán)高者優(yōu)先執(zhí)行必要時(shí)，引入搶占,面向系統(tǒng)的準(zhǔn)則：1、系統(tǒng)吞吐率高,定義：吞吐率(Throughput)是指系統(tǒng)在單位時(shí)間內(nèi)完成的作業(yè)數(shù)是用于評(píng)價(jià)批處理系統(tǒng)性能的重要指標(biāo)，也是用于選擇批處理作業(yè)調(diào)度的重要準(zhǔn)則吞吐率與作業(yè)的平均長(zhǎng)度有關(guān)大型作業(yè)中、小型作業(yè)吞吐率與作業(yè)的調(diào)度算法也有關(guān),面向系統(tǒng)的準(zhǔn)則：2、處理