第六章 處理機(jī)調(diào)度.ppt

第六章處理機(jī)調(diào)度 CPUScheduling 6 1引起進(jìn)程調(diào)度的原因6 2調(diào)度類型6 3進(jìn)程調(diào)度性能的衡量6 4進(jìn)程調(diào)度算法6 5調(diào)度的隊(duì)列模型 ModelingMultiprogramming CPUutilizationasafunctionofnumberofprocessesinmemory Degreeofmultiprogramming 6 1引起進(jìn)程調(diào)度的原因 進(jìn)程調(diào)度的方式 Windows是一個(gè)搶占式多任務(wù)多線程的操作系統(tǒng) 進(jìn)程調(diào)度的方式 剝奪方式 Preemptivemode 搶占式調(diào)度剝奪原則 優(yōu)先級原則短進(jìn)程優(yōu)先原則時(shí)間片原則強(qiáng)制性剝奪 極重要進(jìn)程或人工干預(yù) 進(jìn)程調(diào)度的方式 非剝奪方式 Non preemptivemode 非搶占式調(diào)度 進(jìn)程調(diào)度程序的功能 PCB表項(xiàng) 跟蹤進(jìn)程狀態(tài)及資源使用情況根據(jù)調(diào)度算法選擇一個(gè)就緒進(jìn)程分配處理機(jī)給進(jìn)程 OperatingSystem MainGoals InterleavetheexecutionofthenumberofprocessestomaximizeprocessorutilizationwhileprovidingreasonableresponsetimeOverhead ContextswitchSwitchtousermodeRestartuserprogramatrightlocationUpdateresourceuseandassignmentObservation processestendtoruninburstsofcpu i ouse BasicConcepts ObjectiveofMultiprogrammingCPU I OBurstCycleAnI O boundprogramtypicallywillhavemanyshortCPUburstsAnCPU boundprogrammighthaveafewlongCPUbursts Scheduling Typesofbehavior BurstsofCPUusagealternatewithperiodsofI OwaitaCPU boundprocessanI Oboundprocess 6 2TypesofScheduling Long termschedulingThedecisiontoaddtothepoolofprocessestobeexecutedMedium termschedulingThedecisiontoaddtothenumberofprocessesthatarepartiallyorfullyinmainmemoryShort termschedulingThedecisionastowhichavailableprocesswillbeexecutedbytheprocessorI OschedulingThedecisionastowhichprocess spendingI OrequestshallbehandledbyanavailableI Odevice 調(diào)度的隊(duì)列模型 只有進(jìn)程調(diào)度的隊(duì)列模型具有高級調(diào)度和低級調(diào)度的隊(duì)列模型具有三級調(diào)度的隊(duì)列模型 調(diào)度的類型和模型 高級調(diào)度又稱為作業(yè)調(diào)度或宏觀調(diào)度 它決定將哪些在外存上處于后備狀態(tài)的作業(yè)調(diào)入主機(jī)內(nèi)存 準(zhǔn)備執(zhí)行 因此 有時(shí)把它稱為接納調(diào)度 作業(yè)的狀態(tài)及其轉(zhuǎn)換作業(yè)從輸入到完成要經(jīng)歷提交 收容 執(zhí)行 完成四個(gè)階段 低級調(diào)度又稱為進(jìn)程調(diào)度或微觀調(diào)度 它決定就緒隊(duì)列中哪個(gè)進(jìn)程將獲得處理機(jī) 并實(shí)際執(zhí)行將處理機(jī)分配給進(jìn)程的操作 執(zhí)行分配處理機(jī)的程序稱為分派程序 只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 Admit ReadyQueue Processscheduling Time out EventWait Release Processor BlockedQueue EventOccurs 具有高級和低級調(diào)度的調(diào)度隊(duì)列模型 作業(yè)后備隊(duì)列 ReadyQueue Time out Release Processor Processscheduling Long termscheduling 中級調(diào)度 中級調(diào)度中級調(diào)度的主要作用是在內(nèi)存和外存之間進(jìn)行進(jìn)程交換 以解決內(nèi)存緊張的問題 如它將內(nèi)存中處于等待狀態(tài)的某些進(jìn)程調(diào)至外存對換區(qū) 以騰出內(nèi)存空間 而將外存對換區(qū)上已具備運(yùn)行條件的進(jìn)程重新調(diào)入內(nèi)存 準(zhǔn)備運(yùn)行 故又稱為交換調(diào)度 ThreeLevelScheduling SchedulingandProcessStateTransition New Ready suspend Ready Blocked Blocked suspend Running Exit Long termscheduling Long termscheduling Medium termscheduling Medium termscheduling Short termscheduling 6 3進(jìn)程調(diào)度性能的衡量 SchedulingCriteria 面向用戶的指標(biāo) 周轉(zhuǎn)時(shí)間 Turnaroundtime forbatchusers totaltimeofbatch 響應(yīng)時(shí)間 Responsetime minimize forinteractiveusers等待時(shí)間 Waitingtime minimizetheaverageoverprocesses可預(yù)測性 進(jìn)程調(diào)度性能的衡量Qualitycriteriaforscheduling algorithm 面向系統(tǒng)的指標(biāo) 吞吐量 Throughput maximalnumberofprocessedjobsperunittime處理器利用率 CPUUtilization Efficiency 公平性 Fairness eachprocessgetsa fairshare ofthecpu確保優(yōu)先權(quán)資源平衡 SchedulingAlgorithmGoals 平均周轉(zhuǎn)時(shí)間 三個(gè)并發(fā)進(jìn)程P1 P2 P3 其獨(dú)立運(yùn)行時(shí)間分別為21 6 3個(gè)單位P1 P2 P3P3 P2 P1 6 4進(jìn)程調(diào)度算法分析用例 SchedulingAlgorithms 先進(jìn)先出 先來先服務(wù) First Come First ServedScheduling短執(zhí)行進(jìn)程優(yōu)先Shortest Job FirstScheduling輪轉(zhuǎn)法Round RobinScheduling優(yōu)先級調(diào)度PriorityScheduling高響應(yīng)比優(yōu)先調(diào)度HighResponse RatioNextScheduling多級隊(duì)列法MultilevelQueueScheduling多級隊(duì)列反饋法MultilevelFeedback QueueScheduling First Come First ServedScheduling TheprocessthatrequeststheCPUfirstisallocatedtheCPUfirst TheimplementationoftheFCFSpolicyiseasilymanagedwithaFIFOqueue NonpreemptiveGanttChart 進(jìn)程調(diào)度算法分析用例 EachprocessjoinstheReadyqueueWhenthecurrentprocessceasestoexecute theoldestprocessintheReadyqueueisselectedAveragewaitingtimeis4 6 AverageTurnaroundis8 6 1 2 3 4 5 First Come First Served FCFS 先進(jìn)先出法的一個(gè)例子 ConvoyEffect 先來先服務(wù)調(diào)度算法 FCFS 按照進(jìn)程就緒的先后次序來調(diào)度進(jìn)程優(yōu)點(diǎn) 實(shí)現(xiàn)簡單缺點(diǎn) 看似公平 但服務(wù)質(zhì)量欠佳 利于長進(jìn)程 不利于短進(jìn)程 Shortest Job FirstScheduling Thisalgorithmassociateswitheachprocessthelengthofthelatter snextCPUburst WhentheCPUisavailable itisassignedtotheprocessthathasthesmallestnextCPUburst IftwoprocesseshavethesamelengthnextCPUburst FCFSschedulingisusedtobreakthetie 短進(jìn)程優(yōu)先算法 SJF 減少FCFS方法對長進(jìn)程的偏袒現(xiàn)象非剝奪方法預(yù)期執(zhí)行時(shí)間最短的進(jìn)程被選擇執(zhí)行問題所在 要預(yù)測下一進(jìn)程的執(zhí)行時(shí)間是很困難的 ShortestJobFirst Ifruntimesareknowninadvance 5 2 4 1 1 2 4 5 A B C D D B C A 5 7 11 12 4 8 75 1 3 7 12 4 5 75 andiftheyarenotknowntheycanbeapproximated 2 0 2 0 ShortestRemainingTime SRTF PreemptiveversionofshortestprocessnextpolicyMustestimateprocessingtimeAveragewaitingtimeis3 2 AverageTurnaroundis7 2 Question TheAverageTurnaroundTime FCFS SJF SPN SRT SRTF Round RobinScheduling Especiallydesignedfortime sharingsystemsTheCPUSchedulergoesaroundthereadyqueue allocatingtheCPUtoeachprocessforatimeintervalofupto1timequantum 時(shí)間片輪轉(zhuǎn)法 基于時(shí)鐘的剝奪算法把CPU劃分成若干時(shí)間片 并且按順序賦給就緒隊(duì)列中的每一個(gè)進(jìn)程 進(jìn)程輪流占有CPU 當(dāng)時(shí)間片用完時(shí) 即使進(jìn)程未執(zhí)行完畢 系統(tǒng)也剝奪該進(jìn)程的CPU 將該進(jìn)程排在就緒隊(duì)列末尾 同時(shí)系統(tǒng)選擇另一個(gè)進(jìn)程運(yùn)行 RRSchedulingExample1 Thetimequantumq 1 RRSchedulingExample2 Thetimequantumq 4 RRSchedulingExample3 TheAverageTurnaroundTime TimeQuantum 20 在采用RR調(diào)度的系統(tǒng)中 你認(rèn)為時(shí)間片長度是越短越好還是越長越好 為什么 Contextswitchoverhead example Assumeeach32bitsregistertakes2x100nanoseconds 10 9seconds tosaveFora32registers 8statusregistersmachine savingtimeis 32 8 x2x100 x10 9 8x10 6 8micro sec Fortime slicesof0 1msec Theschedulerhasanoverheadof16 2x8 oncontextswitch Real overheadismuchhigher schedulercomputes schedulersavesitsowncontext processmemoryhastobesavedtoo somecpushaveseveralsetsofregisters Dependenceontime quantum 時(shí)間片長度的確定問題 時(shí)間片選擇問題 固定時(shí)間片可變時(shí)間片與時(shí)間片大小有關(guān)的因素 系統(tǒng)響應(yīng)時(shí)間就緒進(jìn)程個(gè)數(shù)CPU能力 RoundRobin theoldestmethod Eachprocessgetsasmallunitofcputime time quantum usually10 100millisecondsFornreadyprocessesandtime quantumq noprocesswaitsmorethan n 1 qInthelimitofverylargeq FCFSQuantumoftime switchingtimerelativelylargewasteofcputime i e switching Quantumoftime switchingtimelongresponse waiting time FCFS 優(yōu)先級調(diào)度 優(yōu)先選擇就緒隊(duì)列中優(yōu)先級最高的進(jìn)程投入運(yùn)行優(yōu)先級 根據(jù)進(jìn)程執(zhí)行任務(wù)的輕重緩急程度賦予進(jìn)程的一個(gè)調(diào)度優(yōu)先級別 PriorityScheduling Apriorityisassociatedwitheachprocess andtheCPUisallocatedtotheprocesswiththehighestpriority Equal priorityprocessesarescheduledinFCFSorder PreemptiveorNonpreemptive Example1 Nonpreemptive Lownumbersrepresenthighpriority arrivedatthesametime Example2 Nonpreemptive Example3 Preemptive 優(yōu)先級的確定 靜態(tài)優(yōu)先級法 在進(jìn)程創(chuàng)建時(shí)指定優(yōu)先級 在進(jìn)程運(yùn)行時(shí)優(yōu)先級不變動(dòng)態(tài)優(yōu)先級法 在進(jìn)程創(chuàng)建時(shí)創(chuàng)立一個(gè)優(yōu)先級 但在其生命周期內(nèi)優(yōu)先級可以動(dòng)態(tài)變化 如等待時(shí)間長優(yōu)先級可改變 靜態(tài)優(yōu)先級的確定方法 按進(jìn)程類型確定系統(tǒng)進(jìn)程 用戶進(jìn)程按作業(yè)資源要求確定處理機(jī)時(shí)間 內(nèi)存需求 I O設(shè)備類型等按作業(yè)到達(dá)時(shí)間確定FCFS按用戶類型和要求確定如 收費(fèi)標(biāo)準(zhǔn) HighestResponseRatioNext HRRN Choosenextprocesswiththehighestratio timespentwaiting expectedservicetimeexpectedservicetime 1 2 3 4 5 MultilevelQueueScheduling ThisalgorithmpartitionsthereadyqueueintoseveralseparatequeuesTheprocessesarepermanentlyassignedtoonequeueEachqueuehasitsownschedulingalgorithm MultilevelQueueScheduling Systemprocesses Interactiveprocesses Batchprocesses Lowestpriority highestpriority High priorityprocesswillpreemptCPUallocatedtolow priorityprocess Multi LevelQueueScheduling systemprocesses Interactiveeditingprocesses batchprocesses studentprocesses interactiveprocesses Lowestpriority Highestpriority 如何處理多級隊(duì)列間的關(guān)系 隊(duì)列優(yōu)先權(quán)分配高優(yōu)先權(quán)隊(duì)列優(yōu)先高優(yōu)先權(quán)隊(duì)列搶占 不搶占 為各隊(duì)列分配一定的CPU時(shí)間占用比例 多級反饋隊(duì)列法 Feedback FB 將就緒隊(duì)列分為N級 每個(gè)就緒隊(duì)列分配給不同的時(shí)間片 隊(duì)列級別越高 時(shí)間越長 級別越小 時(shí)間片越小 最后一級采用時(shí)間片輪轉(zhuǎn) 其他隊(duì)列采用先進(jìn)先出 系統(tǒng)從第一級調(diào)度 當(dāng)?shù)谝患墳榭諘r(shí) 系統(tǒng)轉(zhuǎn)向第二個(gè)隊(duì)列 當(dāng)運(yùn)行進(jìn)程用完一個(gè)時(shí)間片 放棄CPU時(shí) 進(jìn)入下一級隊(duì)列 等待進(jìn)程被喚醒時(shí) 進(jìn)入原來的就緒隊(duì)列 當(dāng)進(jìn)程第一次就緒時(shí) 進(jìn)入第一級隊(duì)列 MultilevelFeedback QueueScheduling Quantum 8 Quantum 16 FCFS MultilevelFeedback QueueScheduling CPU 優(yōu)先級 時(shí)間片長 度 ReadyQueue Parametersindefiningamultilevelfeedback queuescheduler Numberofqueuesandschedulingpolicyineachqueue FCFS Priority WhentodemoteaprocesstoalowerqueueWhichqueuetopromoteaprocessto ElapsedtimesinceprocessreceivedCPU aging ExpectedCPUburstMemoryrequiredProcesspriority Multiple ProcessorScheduling 自學(xué) HomogeneousprocessorsTheprocessorsareidentical Multiple ProcessorScheduling AseparatequeueforeachprocessorCommonreadyqueuesharedbyallprocessorsSymmetricmultiprocessing SMP Asymmetricmultiprocessing 6 5實(shí)時(shí)調(diào)度 Real TimeComputing Real timecomputingmaybedefinedasthattypeofcomputinginwhichthecorrectnessofthesystemdependsnotonlyonthelogicalresultofthecomputation butalsoonthetimeatwhichtheresultsareproduced Deadlineofatask Adeadlineisassociatedwithaparticulartask Thedeadlinespecifieseitherastarttimeoracompletiontime Hard SoftReal TimeTask Hardreal timetaskThetaskmustmeetitsdeadline otherwiseitwillcauseundesirabledamageorafatalerrortothesystemSoftreal timetaskThetaskhasanassociateddeadlinethatisdesirablebutnotmandatory itstillmakessensetoscheduleandcompletethetaskevenifithaspasseditsdeadline Real TimeComputing Twotypesofreal timecomputingHardreal timeSpecial purposesoftwareDedicatedhardwareSoftreal timePriorityscheduling agingdisallowedLowdispatchlatency preemptiblesystemcallsToinsertpreemptionpointsinlong durationsystemcallsTomaketheentirekernelpreemptible Aperiodic Periodictask Aperiodictask 非周期性任務(wù) Thetaskhasadeadlinebywhichitmustfinishorstart oritmayhaveaconstraintonbothstartandfinishtime PeriodictaskTherequirementofthetaskmaybestatedas onceperperiodT or exactlyTunitsapart CharacteristicsofReal timeOperatingSystems DeterminismDelaybeforeacknowledginganinterruptResponsivenessDelayafteracknowledgementtoservicetheinterruptUserControlReliabilityFail softOperation FeaturesTypicallyIncludedinCurrentReal timeOperatingSystems FastprocessorthreadswitchSmallsize withitsassociatedminimalfunctionality AbilitytorespondtoexternalinterruptsquicklyMultitaskingwithinterprocesscommunicationtollssuchassemaphores signals andeventsUseofspecialsequentialfilesthatcanaccumulatedataatafastrate FeaturesTypicallyIncludedinCurrentReal timeOperatingSystems Cont PreemptiveschedulingbasedonpriorityMinimizationofintervalsduringwhichinterruptsaredisabledPrimitivestodelaytasksforafixedamountoftimeandtopause resumetasksSpecialalarmsandtimeouts 實(shí)時(shí)系統(tǒng)調(diào)度相關(guān)信息 Readytime 就緒時(shí)間 StartingdeadlineCompletiondeadlineProcessingtimeResourcerequirementsPrioritySubtaskstructure 實(shí)時(shí)調(diào)度算法 時(shí)間片輪轉(zhuǎn)調(diào)度秒級響應(yīng) 適于一般實(shí)時(shí)信息處理非搶占優(yōu)先權(quán)調(diào)度數(shù)秒至數(shù)百毫秒級響應(yīng) 適于不太嚴(yán)格實(shí)時(shí)控制系統(tǒng)基于時(shí)鐘中斷搶占的優(yōu)先權(quán)調(diào)度幾十毫秒至幾毫秒響應(yīng) 適于大多數(shù)實(shí)時(shí)