五章節(jié)處理機管理CPUScheduling課件

1、第五章 處理機管理 CPU Scheduling處理機調(diào)度類型和模型調(diào)度算法的選擇和評價調(diào)度算法處理機調(diào)度的目的處理機的高利用率High processor utilization高吞吐量High throughputnumber of processes completed per unit time快速的響應(yīng)時間Low response timetime elapse from the submission of a request to the beginning of the response調(diào)度的類型作業(yè)調(diào)度( Long-term scheduling)中級調(diào)度( Medium-te

2、rm scheduling)進程調(diào)度( Short-term scheduling)作業(yè)及作業(yè)步的概念作業(yè)OS為用戶服務(wù)，用戶交給計算機做的工作稱為作業(yè)作業(yè)由程序、數(shù)據(jù)、作業(yè)說明書三部分組成程序是問題求解的算法描述數(shù)據(jù)是程序加工的對象，但有些程序未必使用數(shù)據(jù)；作業(yè)說明書是告訴操作系統(tǒng)本作業(yè)的程序和數(shù)據(jù)按什么樣的控制要求使之執(zhí)行。作業(yè)步一個作業(yè)的一次活動中若干相對獨立的加工步驟編譯原程序連接裝配程序運行程序作業(yè)的狀態(tài)轉(zhuǎn)換執(zhí)行等待就緒運行后備提交完成進程調(diào)度程序作業(yè)注冊程序作業(yè)調(diào)度程序作業(yè)終止程序作業(yè)控制塊JCB作業(yè)名作業(yè)類型資源要求資源使用情況 優(yōu)先級當(dāng)前狀態(tài)其它中級(交換)調(diào)度為了提高內(nèi)存利用

3、率和系統(tǒng)吞吐量實施的方法是“掛起”和“解掛”是存儲器管理中的對換功能常配置在具有掛起功能的OS中可改善內(nèi)存的利用率進程調(diào)度又稱為微調(diào)度通常幾十毫秒運行一次往往以原語方式存在CPU及I/O 猝發(fā)(Burst)周期Process execution consists of a cycle of CPU execution and I/O wait任何一種操作系統(tǒng)中都必須配置該級調(diào)度進程調(diào)度的方式CPU scheduling decisions may take place when a process:1.Switches from running to waiting state, e. g.,

4、 I/O request, wait for an event to occur(child completion,system object: semaphore,message queue, socket )2.Switches from running to ready state,e.g., interrupt3.Switches from waiting to ready.4.Terminates.Scheduling under 1 and 4 is nonpreemptive.(非搶占)All other scheduling is preemptive.(搶占)進程調(diào)度方式（續(xù)

5、）非搶占調(diào)度方式（nonpreemptive）實現(xiàn)簡單，系統(tǒng)開銷小，適用于批處理系統(tǒng)環(huán)境難于滿足緊近任務(wù)立即執(zhí)行的要求，實時系統(tǒng)中不宜采用搶占調(diào)度方式（preemptive）適用于分時系統(tǒng)和實時系統(tǒng)調(diào)度方式的原則時間片原則優(yōu)先級原則短進程優(yōu)先原則調(diào)度隊列模型僅具有進程調(diào)度的調(diào)度隊列模型等待事件（阻塞）事件發(fā)生（被喚醒）時間片用完交互用戶調(diào)度隊列模型具有作業(yè)調(diào)度和進程調(diào)度的調(diào)度隊列模型等待事件n等待事件2等待事件2相應(yīng)事件發(fā)生則喚醒相應(yīng)進程隊列中的進程作業(yè)調(diào)度調(diào)度算法的選擇選擇時考慮的因素系統(tǒng)各類資源的均衡使用用戶作業(yè)到達系統(tǒng)的時間用戶作業(yè)估計執(zhí)行的時間用戶公平并使用戶滿意作業(yè)的優(yōu)先級作業(yè)對內(nèi)存

6、和外設(shè)的要求及整個系統(tǒng)的效率各因素間往往相互矛盾算法選擇時主要考慮4個方面1 系統(tǒng)設(shè)計目標(biāo)批處理系統(tǒng)主要追求大的系統(tǒng)吞吐量實時系統(tǒng)主要關(guān)心實時處理分時系統(tǒng)主要注重保證用戶請求的及時響應(yīng)2 均衡處理系統(tǒng)和用戶的要求選擇算法時不應(yīng)使一個作業(yè)被無限期的推遲常采用優(yōu)先級可變方式即作業(yè)的優(yōu)先級可隨等待時間的增加而提高采用優(yōu)先級調(diào)度算法調(diào)度算法的性能評價1 周轉(zhuǎn)時間作業(yè)i從提交時刻tsi到完成時刻tei稱為作業(yè)的周轉(zhuǎn)時間。Ti=Tei - Tsi 完成時刻 提交時刻一個作業(yè)的周轉(zhuǎn)時間包括:作業(yè)在外存后備作業(yè)隊列中等待調(diào)度的時間作業(yè)進程在就緒隊列中等待獲取CPU的時間作業(yè)進程在CPU上執(zhí)行的時間作業(yè)等待I/

7、O操作等阻塞或掛起的時間調(diào)度算法的性能評價作業(yè)平均周轉(zhuǎn)時間 T用于衡量不同調(diào)度算法對同一作業(yè)流的調(diào)度性能作業(yè)平均帶權(quán)周轉(zhuǎn)時間 W周轉(zhuǎn)時間與實際運行時間之比用于衡量某種調(diào)度算法對不同作業(yè)流的調(diào)度性能W反映了作業(yè)對單位執(zhí)行時間所付出的平均等時間TRi是作業(yè)的實際運行時間調(diào)度算法調(diào)度算法是根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法實行調(diào)度目前有很多處理機調(diào)度算法,有些適用于作業(yè)調(diào)度,有些適用于進程調(diào)度,有些兩者都能適用常用的幾種調(diào)度算法先來先服務(wù)調(diào)度算法短作業(yè)(短進程)優(yōu)先調(diào)度算法優(yōu)先級調(diào)度算法時間片輪轉(zhuǎn)調(diào)度算法多級反饋隊列調(diào)度算法實時調(diào)度算法先來先服務(wù)調(diào)度算法(FCFS) First Come F

8、irst Served 作業(yè)調(diào)度: 選擇一個或多個最先進入并能被系統(tǒng)滿足的作業(yè)裝入內(nèi)存,分配資源,創(chuàng)建相應(yīng)進程,放入就緒隊列進程調(diào)度: 從就緒隊列中選最先進入隊列的進程分配處理機,讓它進入執(zhí)行狀態(tài),該進程一直執(zhí)行,直到完成或因等待某事件而阻塞時,才放棄處理機.FCFS調(diào)度例子假設(shè)：用戶區(qū)空間100KB，內(nèi)存連續(xù)分配且運行中不能移動。作業(yè)名進入SPOOLING的時間需計算的時間（分）需要內(nèi)存量（KB）A8:064215B8:183060C8:302450D8:362410E8:421220作業(yè)需時需內(nèi)存A4215B3060C2450D2410E1220作業(yè)名入時間作業(yè)調(diào)度時進程開始時結(jié)束時間周轉(zhuǎn)

9、時間帶權(quán)周轉(zhuǎn)時間A8:068:06B8:188:18C8:309:18D8:368:36E8:429:188:06 8:48 42 42/429:18 9:42 66 66/249:42 10:06 96 96/2410:06 10:18 96 96/12T=(42+60+66+96+96)/5=72(min)W=(1+2+2.75+4+8)/5=3.55內(nèi)存容量 100K8:48 9:18 60 60/30輪轉(zhuǎn)法設(shè)定時間片, 輪流將處理機分配為各就緒進程僅適用于進程調(diào)度時間片的選擇固定法q = R / Nmax根據(jù)當(dāng)前進程數(shù)量動態(tài)計算短作業(yè)(短進程)優(yōu)先調(diào)度算法Shortest-Job-Fi

10、rst/Shortest-Process-FirstSJF短作業(yè)優(yōu)先從后備作業(yè)中選擇一個或若干個估計運行時間最短且當(dāng)能獲得所要求資源的作業(yè)裝入內(nèi)存SPF短進程優(yōu)先從就緒隊列中選出一個估計運行時間最短的進程分配處理機,該進程立即執(zhí)行并一直執(zhí)行到完成或因等待事件發(fā)生而阻塞放棄處理機為止非搶占式SJF調(diào)度例子Example of Non-Preemptive SJF ProcessArrival Time UseTime P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4SJF (non-preemptive 非搶占)Average waiting time = (0 + 6 + 3 + 7)/4 = 4T = (7+10+4+11)/4= 8P1P3P273160P4812搶占式SJF調(diào)度例子Example of Preemptive SJFProcessArrival TimeUse Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4SJF (preemptive 搶占)Avera