中科大操作系统原理与实现课件5_CPU_Scheduling1.pdf

《中科大操作系统原理与实现课件5_CPU_Scheduling1.pdf》由会员分享，可在线阅读，更多相关《中科大操作系统原理与实现课件5_CPU_Scheduling1.pdf（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.操作系统原理与设计第5章 CPU Scheduling II陈香兰中国科学技术大学计算机学院2009年09月01日.提纲Multiple-Processor SchedulingReal-Time SchedulingOS examplesAlgorithm Evaluation小结和作业.OutlineMultiple-Processor SchedulingReal-Time SchedulingOS examplesAlgorithm Evaluation小结和作业.Multiple-Processor SchedulingIOne single processor multiple

2、CPUSICPU scheduling more complexILoad sharingITo be simple,supposeIthe processors are identical homogeneous in terms oftheir functionalityIso,any processor can execute any process in the queue.Approches to Multiple-Processor SchedulingIAsymmetric multiprocessing only one processor accessesthe system

3、 data structures,alleviating the need for datasharingISymmetric multiprocessingIone common ready queue,orIone private ready queue for each processor.Processor AffinityIMigration of processes from one processor to anotherprocessor COSTs much.IFor example:cacheImost SMP systems try to avoid such migra

4、tionIProcessor affinity:a process has an affinity for the processor on which it iscurrently running.ISOFT affinity VS.HARD affinity.Load BalancingILoad balanceing attempts to keep the workload evenlyIfor SMP system with one private ready queue for eachprocessorItwo general approachesIpush migrationI

5、pull migrationoften works together in load balancing systemsIload balancing VS.processor affinity.Symmetric Multithreading IIINTEL:hyperthreading technology(HT)Ilogical processors VS.physical processorsIeach logical processor has its own architecture state,including general-purpose registers and mac

6、hine-state registers,and interruptsIshare:cache memory and buesesI?from the viewpoint of OS?.OutlineMultiple-Processor SchedulingReal-Time SchedulingOS examplesAlgorithm Evaluation小结和作业.Real-Time Scheduling.IHard real-time systems required to complete a criticaltask within a guaranteed amount of tim

7、eISoft real-time computing requires that critical processesreceive priority over less fortunate onesIOS1.priority scheduling2.short dispatch latencyIapproaches for short dispatch latency1.preemption1.1 preemption point(抢占点)in system calls with long period1.2 preemptible kernel2.priority inversion2.1

8、 priority-inheritance protocol2.2 priority-ceiling protocol.dispatch latencyconflicts=preemption+resource releasing by processes with lowerpriority.OutlineMultiple-Processor SchedulingReal-Time SchedulingOS examplesAlgorithm Evaluation小结和作业.OS examplesIREADINGISolaris(thread)IWindows(thread)ILinux(p

9、rocess).Linux Scheduling IILinux既支持分时，也支持实时I是多种调度策略和调度算法的混合。I什么是调度策略？是一组规则，它们决定什么时候以怎样的方式选择一个新进程运行。Linux 2.6.26中ISCHED NORMALISCHED FIFO(for real-time process)ISCHED RR(for real-time process)ISCHED BATCHISCHED IDLEILinux的调度基于分时和优先级I随着版本的变化，分时技术在不断变化ILinux的进程根据优先级排队I根据特定的算法计算出进程的优先级，用一个值表示.Linux Sche

10、duling III这个值表示把进程如何适当的分配给CPUILinux中进程的优先级是动态的I调度程序会根据进程的行为周期性的调整进程的优先级I较长时间未分配到CPU的进程，通常I已经在CPU上运行了较长时间的进程，通常.ILinux 2.4的调度算法I需要遍历可运行队列，算法O(n)IEpoch，基本时间片，动态优先级ILinux 2.6.17的调度算法（2.6.23之前）I采用双队列（Active；expire），按照优先级组队，O(1)ILinux 2.6.26的调度算法I非实时：CFS，vruntime，红黑树I实时：优先级队列.The Relationship Between Pri

11、orities and Time-slice lengthList of Tasks.Indexed According to Prorities.OutlineMultiple-Processor SchedulingReal-Time SchedulingOS examplesAlgorithm Evaluation小结和作业.Algorithm EvaluationIHow do we select a CPU scheduling algorithm for a particularsystem?Ifirstly,which criteria?What is the relative

12、importance of thesemeasuresIthen,evaluate the algorithmsIDeterministic ModelingIQueueing ModelsISimulationsIImplementation.Deterministic Modeling IIanalytic evaluationIDeterministic modeling takes a particular predeterminedworkload and defines the performance of each algorithm forthat workloadIExamp

13、leIconsider FCFS,SJF,and RR(quantum=10ms)schedulingalgorithms for 5 processesProcessBurstTimeP110P229P33P47P512IFCFS:average waiting time=(0+10+39+42+49)/5=28.Deterministic Modeling IIISJF:average waiting time=(10+32+0+3+20)/5=13IRR:average waiting time=(0+(10+20+2)+20+23+(30+10)/5=23Iadvantages and

14、 disadvantagesI确定性 vs.适用性和实用性.Queueing ModelsIUsually,two distributions can be measured and thenapproximated or simply estimatedIthe distribution of CPU and I/O burstsIthe arrival-time distributionIqueueing-network analysisIexample:In:the average queue lengthIW:the average waiting timeI:the average

15、arrival rateIfor a steady waits:n=W.Simulations IIRunning simulations involves programming a model of thecomputer system.ISoftware data structures represent the major componentsIa clockIthe system state is modified to reflect the activities of thedevices,the processes and the scheduler.Ifinally,the

16、statictics are gatheredIHow to generate the data to drive the simulation?Idistribution-driven simulationIramdon-number generator,according to probabilitydistributions,to generate processes,CPU burst times,arrivals,departures,.Ithe distributions can be defined mathematically(uniform,exponential,Poiss

17、on)or empiricallyImay be inaccurateItrace tapes.Simulations II.ImplementationIThis approach put the actual algorithm in the real systemfor evaluation under real operating conditionsIthe main difficulty:high cost.OutlineMultiple-Processor SchedulingReal-Time SchedulingOS examplesAlgorithm Evaluation小结和作业.小结Multiple-Processor SchedulingReal-Time SchedulingOS examplesAlgorithm Evaluation小结和作业.作业I华夏班I英文恐龙书：5.2,5.4,5.5,5.9,5.10I非华夏班I中文恐龙书：6.1,6.3,6.4,6.7,6.8.ProjectI华夏班：I在实验3的基础上，实现某一种进程调度算法，对一组进程进行调度。I进程个数10I非华夏班：I参见助教提供的链接.谢谢！