操作系统 CPU调度 CCH06.ppt

AppliedOperatingSystemConcepts Module6 CPUScheduling BasicConcepts 基本概念 SchedulingCriteria 调度准则 SchedulingAlgorithms 调度算法 Multiple ProcessorScheduling 多处理器调度 Real TimeScheduling 实时调度 AlgorithmEvaluation 算法评估 AppliedOperatingSystemConcepts BasicConcepts MaximumCPUutilizationobtainedwithmultiprogramming 通过多道程序设计得到CPU的最高利用率 CPU I OBurstCycle ProcessexecutionconsistsofacycleofCPUexecutionandI Owait CPU I O脉冲周期 进程的执行包括进程在CPU上执行和等待I O CPUburstdistribution CPU脉冲的分布 AppliedOperatingSystemConcepts AlternatingSequenceofCPUAndI OBursts AppliedOperatingSystemConcepts HistogramofCPU burstTimes AppliedOperatingSystemConcepts CPUScheduler Selectsfromamongtheprocessesinmemorythatarereadytoexecute andallocatestheCPUtooneofthem 选择内存中的某个就绪进程 并分配CPU给其 CPUschedulingdecisionsmaytakeplaceunderthefollowingcircumstances CPU调度可能发生在以下情况下 1 Switchesfromrunningtowaitingstate 从运行转到等待 2 Switchesfromrunningtoreadystate 从运行转到就绪 3 Switchesfromwaitingtoready 从等待转到就绪 4 Terminates 终止运行 Schedulingunder1and4isnonpreemptive 发生在1 4两种情况下的调度称为非抢占式调度 Allotherschedulingispreemptive 其他情况下发生的调度称为抢占式调度 AppliedOperatingSystemConcepts 进程调度的方式 非抢占方式采用这种调度方式时 一旦把处理机分配给某进程后 便让进程一直执行 直到该进程完成或发生某事件而被阻塞时 才把处理机分配给其它进程 决不允许某进程抢占已经分配出去的处理机 优点 实现简单 系统开销小 适用于大多数批处理系统环境 缺点 难以满足紧急任务的要求 不适用于实时 分时系统要求 AppliedOperatingSystemConcepts 进程调度 抢占方式 Preemptivemode 这种调度方式 允许进程调度程序根据某个原则 去停止某个正在执行的进程 将已分配给进程的处理机 重新分配给另一个进程 抢占的原则有 时间片原则 各进程按时间片运行 当一个时间片用完后 便仃止该进程的执行而重新进行调度 这个原则适用于分时系统 优先权原则 通常是对一些重要的和紧急的进程赋予较高的优先权 当这种进程进入就绪队列时 例如由阻塞态转换为就绪态 或从静止就绪态转为活动就绪态时 或新创建进入就绪态的进程进入就绪队列时 如果其优先权比正在执行的进程优先权高 便仃止正在执行的进程 将处理机分配给优先权高的进程 使之执行 AppliedOperatingSystemConcepts 进程调度 短作业优先原则 当新到达的作业比正在执行的作业明显短时 将暂停当前长作业的执行 将处理机分配给新到的短作业 使之执行 缺点 额外开销例如 两个进程共享数据的情况 AppliedOperatingSystemConcepts 处理机三级调度 1 高级 Long term 调度 作业调度作业调度用于决定把外存输入井上处于作业后备队列上的哪些作业调入内存 并为它们创建进程 分配必要的资源 然后再将新创建的进程排在就绪队列上 准备执行 在批处理系统中 作业是先驻留在外存的输入井上的 因此需要有作业调度 然而在分时系统中 通过键盘输入的命令和数据直接进入内存 无需作业调度 2 低级 Short term 调度 进程调度进程调度决定就绪队列中哪个进程将获得处理机 然后由分派程序执行把处理机分配给该进程的操作 进程调度是最基本的调度 任何操作系统都有进程调度 AppliedOperatingSystemConcepts 低级 Short term 调度 进程调度 低级调度是由每秒可操作许多次的处理机调度程序执行 处理机调度程序应常驻内存 进程调度的方式 非抢占方式 抢占方式 抢占的方式有 1时间片原则 2优先级原则 3短进程优先原则 AppliedOperatingSystemConcepts 中级 Medium term 调度 对换 引入中级调度的目的是为了提高主存利用率和系统吞吐量 由于在进程并发执行过程中 为了充分发挥内存的效能 需将那些暂时不能运行的进程从内存调到外存盘交换区去等待 而将那些在盘交换区的等待事件已经发生急需调度运行的进程从盘交换区调入内存 AppliedOperatingSystemConcepts 处理机三级调度图 作业调度作业运行状态 外存 盘 交换区 作业收容状态 作业提交状态 作业完成状态 终止作业 静止就绪态 静止阻塞态 外存 中级调度 AppliedOperatingSystemConcepts 高级调度 作业调度 1 作业的状态作业从进入到运行结束 一般需要经历 提交 后备 运行 和 完成 四个阶段 提交状态一个作业被提交给机房后正在通过SPOOLing系统进行输入或用户通过终端向计算机中键入其作业时所处于的状态为提交状态 此时作业信息尚未全部进入系统 AppliedOperatingSystemConcepts 高级调度 作业调度 后备状态作业已经过SPOOLing系统输入到磁盘输入井 等待调入内存运行 此时作业处于后备状态 为了管理和调度作业 为每个作业设置一个作业控制块 JCB 作业控制块记录了作业类型和资源要求等有关信息 作业控制块按作业类型组成一个或多个后备作业队列 AppliedOperatingSystemConcepts 高级调度 作业调度 运行状态一个在后备作业队列的作业被作业调度程序选中后 分配必要的资源 建立一组相应的进程后 调入内存 该作业就进入运行状态 进程各状态 进程运行态 活动就绪态 活动阻塞态 静止就绪态 静止阻塞态等 都对应作业运行状态 完成状态当进程正常运行结束或因发生错误而终止时 作业进入完成状态 终止作业程序将负责善后处理 输出结果 回收资源等 AppliedOperatingSystemConcepts 高级调度 作业调度 2 作业状态的转换作业调度作业调度程序按一定算法从后备作业队列中选一个满足资源要求的作业 分配它所要求的资源 建立一组相应的进程 设置该进程状态为就绪态 并将该进程插入内存就绪队列 参加CPU争夺 AppliedOperatingSystemConcepts 高级调度 作业调度 终止作业当进程正常运行结束或因发生错误终止时 调用终止作业程序 它负责将输出文件缓冲输出到输出井 并调用SPOOLing系统输出进程将作业输出文件在打印机输出 同时回收作业所使用内 外存 I O设备等各种资源 最后调用记帐程序结清作业费用 AppliedOperatingSystemConcepts 作业状态及其转换图 spooling系统 提交 收容 外存 就绪 等待 运行 就绪 等待 交换调度 完成 作业调度 进程调度 AppliedOperatingSystemConcepts 后备作业队列空 按调度算法从作业中选出一作业 调用存储 设备管理程序 审核资源要求 资源要求能满足 放弃该作业 否 分配资源 调用进程管理程序建立进程 进程调度 否 是 出口 作业从后备状态到执行状态 AppliedOperatingSystemConcepts 撤销该作业的所有进程及作业的JCB 调用存储管理 设备管理回收分配给该作业的全部资源 调用会计程序 计算该作业的执行费用 调度下一个作业 作业从执行状态到完成状态 AppliedOperatingSystemConcepts 作业与进程的关系 作业是用户向计算机提交任务的任务实体 进程是计算机为了完成用户任务实体而设置的执行实体 显然 计算机要完成一个任务实体 必须要有一个以上的执行实体 一个作业总是由一个以上的多个进程组成 AppliedOperatingSystemConcepts 作业调度的功能 按某种算法从后备队列中挑选一个或一批作业调入内存 并创建PCB 1 后备作业队列与作业控制块系统中有若干作业在输入井中 为了管理和调度作业 就必须记录已进入系统的各作业的情况 系统为每个作业设置了一个作业控制块 JCB 内容 作业名 作业状态 作业调度 以及资源申请和一些控制信息 作业的调度 AppliedOperatingSystemConcepts 作业控制块JCB 作业控制块JCB AppliedOperatingSystemConcepts 按照某种调度算法从后备作业队列中选取作业 为被选取的作业分配内存和外设资源 当系统为动态分配外设时 作业所申请的外设只作为调度的参考因素 因此要用到内存分配程序和外设分配程序 为选中的作业建立相应的进程 为作业开始运行做好一切准备工作 如构造和读写作业运行时所需要的有关表格及建立负责其运行控制的作业运行控制程序 在作用运行完毕或运行过程中因某种原因需要撤离时 作业调度程序还有完成作业的善后处理工作 如收回分配给他的全部资源 作业调度应完成如下几方面的工作 AppliedOperatingSystemConcepts 调度目标 对所有作业应该是公平合理 应使设备有高的利用率 每天执行尽可能多的作业 有快的响应时间 作业调度目标与性能衡量 AppliedOperatingSystemConcepts 处理机调度模型仅有进程调度的调度队列模型 AppliedOperatingSystemConcepts 处理机调度模型 2 具有进程调度和中级调度队列模型在具有虚拟存储器技术的分时系统中 例如UNIX系统等 一般采用具有进程调度和中级调度的调度模型 在该模型中比第一种模型增加了中级调度 则相对于上模型也增加了静止就绪队列和静止阻塞队列 中级调度时或从活动就绪队列调到静止就绪队列 或从活动阻塞队列调到静止阻塞队列 或从静止就绪队列调到活动就绪队列 AppliedOperatingSystemConcepts 处理机调度模型 3 具有高级调度和低级调度的调度队列模型在多道批处理系统中 一般处理机管理设置作业和进程两级调度 它比第一个模型增加了高级调度 模型增加了在磁盘的作业后备队列 作业调度的任务是从作业后备队列中选一个作业为它创建至少一个进程 并分配资源 将它排入内存进程就绪队列末尾 AppliedOperatingSystemConcepts 处理机调度模型 4 同时具有三级调度的调度队列模型在通用系统的多模式OS中 一般采用具有三级调度的调度队列模型 由于多模式OS同时支持批处理 分时和实时处理 所以它必须具有以上模型 具有三级调度的调度队列模型是第二 三两模型的综合 见下图所示 AppliedOperatingSystemConcepts 处理机调度模型具有高 低两级调度的调度队列模型 完成 AppliedOperatingSystemConcepts 处理机调度模型具有三级调度的调度队列模型 AppliedOperatingSystemConcepts 进程调度的功能 选择占有处理机进程 进程调度的主要功能是按照一定的策略 由它决定的调度算法 选择一个处于就绪态的进程 使其获得处理机执行 进行进程上下文切换 进程上下文实际上是进程执行活动全过程的静态描述 一个进程的执行是在进程上下文中执行 当正在执行的进程由于某种原因要让出处理机时 系统要做上下文切换 以使另一个进程得以执行 记录系统中所有进程的执行情况 进程管理模块在各进程的PCB表中记录系统各进程的执行情况和状态特征 并将各PCB表根据进程状态特征和资源要求排成相应的队列 并进行动态队列转换 AppliedOperatingSystemConcepts Dispatcher DispatchermodulegivescontroloftheCPUtotheprocessselectedbytheshort termscheduler thisinvolves 进程调度模块负责将对CPU的控制权转交给短调度选择的进程 包括 switchingcontext 切换上下文 switchingtousermode 切换到用户态 jumpingtotheproperlocationintheuserprogramtorestartthatprogram 跳转到用户程序的适当位置并重新运行之 Dispatchlatency timeittakesforthedispatchertostoponeprocessandstartanotherrunning 调度时间 调度程序终止一个进程的运行并启动另一个进程运行所花的时间 AppliedOperatingSystemConcepts SchedulingCriteria 调度准则 CPUutilization keeptheCPUasbusyaspossible CPU利用率 使CPU尽可能的忙碌 Throughput thenumberofprocessesthatcompletetheirexecutionpertimeunit 吞吐量 单位时间内运行完的进程数 Turnaroundtime theintervalfromsubmissiontocompletion 周转时间 进程从提交到运行结束的全部时间 Waitingtime amountoftimeaprocesshasbeenwaitinginthereadyqueue 等待时间 进程在就绪队列中等待调度的时间片总和 Responsetime amountoftimeittakesfromwhenarequestwassubmitteduntilthefirstresponseisproduced notoutput fortime sharingenvironment 响应时间 从进程提出请求到首次被响应的时间段 在分时系统环境下不是输出完结果的时间 AppliedOperatingSystemConcepts OptimizationCriteria MaxCPUutilization 最大的CPU利用率 Maxthroughput 最大的吞吐量 Minturnaroundtime 最短的周转时间 Minwaitingtime 最短的等待时间 Minresponsetime 最短的响应时间 AppliedOperatingSystemConcepts 作业 进程调度算法 1 先来先服务First Come First Served FCFS是一种最简单的调度算法 可用于作业或进程调度 此算法的原则是按照作业到达后备作业队列 或进程进入就绪队列 的先后次序来选择作业 或进程 FCFS算法属于非抢占方式 一旦一个进程占有处理机 它就一直运行下去 直到该进程完成或者因等待某事件而不能继续运行时才释放处理机 FCFS算法易于实现 表面上很公平 实际上有利于长作业 不利于短作业 有利于CPU繁忙型 不利于I O繁忙型 AppliedOperatingSystemConcepts First Come First Served FCFS Scheduling Example ProcessBurstTimeP124P23P33Supposethattheprocessesarriveintheorder 假定进程到达顺序如下 P1 P2 P3TheGanttChartforthescheduleis 该调度的Gantt图为 Waitingtime 等待时间 forP1 0 P2 24 P3 27Averagewaitingtime 平均等待时间 0 24 27 3 17 AppliedOperatingSystemConcepts FCFSScheduling Cont Supposethattheprocessesarriveintheorder 假定进程到达顺序如下 P2 P3 P1 TheGanttchartforthescheduleis 该调度的Gantt图为 Waitingtime 等待时间 forP1 6 P2 0 P3 3Averagewaitingtime 平均等待时间 6 0 3 3 3Muchbetterthanpreviouscase 比前例好得多 Convoyeffectshortprocessbehindlongprocess 此种结果产生是由于长进程先于短进程到达 P1 P3 P2 6 3 30 0 AppliedOperatingSystemConcepts 作业 进程调度算法 2 短作业 进程优先 SJF ShortestProcessNext 调度算法这种调度算法主要用于作业调度 它从作业后备队列中挑选所需运行时间 估计值 最短的作业进入主存运行 这一算法有利于短作业 对长作业不利 采用SJF有利于系统减少平均周转时间和平均带权周转时间 提供系统吞吐量 在一般情况下SJF调度算法比先来先服务调度算法的效率要高一些 实现相对先来先服务调度算法要困难些 如果作业的到来顺序及运行时间不合适 会出现饿死现象 例如 系统中有一个运行时间很长的作业JN 和几个运行时间小的作业 然后 不断地有运行时间小于JN的作业的到来 这样 作业JN就得不可调度而饿死 另外 作业运行的估计时间也有问题 AlthoughtheSJFalgorithmisoptimal itcannotbeimplementedatthelevelofshort termCPUscheduling AppliedOperatingSystemConcepts Shortest Job First SJF Scheduling AssociatewitheachprocessthelengthofitsnextCPUburst Usetheselengthstoscheduletheprocesswiththeshortesttime 关联到每个进程下次运行的CPU脉冲长度 调度最短的进程 Twoschemes nonpreemptive onceCPUgiventotheprocessitcannotbepreempteduntilcompletesitsCPUburst 非抢占式调度 一旦进程拥有CPU 它的使用权限只能在该CPU脉冲结束后让出 Preemptive ifanewprocessarriveswithCPUburstlengthlessthanremainingtimeofcurrent法executingprocess preempt ThisschemeisknowastheShortest Remaining Time First SRTF 抢占式调度 发生在有比当前进程剩余时间片更短的进程到达时 也称为最短剩余时间优先调度 SJFisoptimal givesminimumaveragewaitingtimeforagivensetofprocesses SJF是最优的 对一组指定的进程而言 它给出了最短的平均等待时间 AppliedOperatingSystemConcepts ProcessArrivalTimeBurstTimeP10 07P22 04P34 01P45 04SJF non preemptive Averagewaitingtime 0 6 3 7 4 4 ExampleofNon PreemptiveSJF P1 P3 P2 7 3 16 0 P4 8 12 AppliedOperatingSystemConcepts ExampleofPreemptiveSJF ProcessArrivalTimeBurstTimeP10 07P22 04P34 01P45 04SJF preemptive Averagewaitingtime 9 1 0 2 4 3 P1 P3 P2 4 2 11 0 P4 5 7 P2 P1 16 AppliedOperatingSystemConcepts DeterminingLengthofNextCPUBurst Canonlyestimatethelength 其长度只能估计 CanbedonebyusingthelengthofpreviousCPUbursts usingexponentialaveraging 可以通过先前的CPU脉冲长度及计算指数均值进行 AppliedOperatingSystemConcepts ExamplesofExponentialAveraging 0 n 1 nRecenthistorydoesnotcount 1 n 1 tnOnlytheactuallastCPUburstcounts Ifweexpandtheformula weget n 1 tn 1 tn 1 1 j tn 1 1 n 1tn 0Sinceboth and 1 arelessthanorequalto1 eachsuccessivetermhaslessweightthanitspredecessor AppliedOperatingSystemConcepts 先来先服务调度算法和短作业优先调度算法 11 AppliedOperatingSystemConcepts 作业 进程调度算法 优先权 Priority 调度算法 按照进程的优先权大小来调度 使高优先权进程得到优先处理的调度策略称为优先权调度算法 进程的优先权的设置可以是静态的 也可以是动态的 优先权 Priority 的选择 静态优先权在进程创建时确定 且的在整个生命期中保持不变 确定进程优先权的依据有 进程类型 通常系统进程 例如对换进程 的优先权高于一般用户态进程的优先权 进程对资源的需求 如进程执行时间及内存需要省的进程应赋予较高的优先权 根据用户要求 由用户的紧迫程度及用户所付费用的多少来确定进程的优先权 动态优先权是指在创建进程时所赋予的优先权 可以随进程的推进而改变 以便获得更好的调度性能 改变优先权的因数 随系统不同而不同 最常考虑的因素的进程的等待时间 已使用处理机的时间 或者资源使用情况等 AppliedOperatingSystemConcepts PriorityScheduling Aprioritynumber integer isassociatedwitheachprocess 每个进程都有自己的优先数 整数 TheCPUisallocatedtotheprocesswiththehighestpriority smallestinteger highestpriority CPU分配给最高优先级的进程 假定最小的整数 最高的优先级 Preemptive 抢占式 Nonpreemptive 非抢占式 SJFisapriorityschedulingwherepriorityisthepredictednextCPUbursttime SJF是以下一次CPU脉冲长度为优先数的优先级调度 Problem Starvation lowpriorityprocessesmayneverexecute 问题 饥饿 低优先级的可能永远得不到运行 Solution Aging astimeprogressesincreasethepriorityoftheprocess 解决方法 老化 视进程等待时间的延长提高其优先数 AppliedOperatingSystemConcepts 系统中由两类进程 系统进程和用户进程 系统进程的优先数比用户进程的优先数高 特别是某些系统进程 必须赋予它一种特权 当它需要处理机时 应尽快的到满足 例如 设备管理器中的I O进程便是如此 这不仅是为了保证I O设备尽可能忙碌 一提高设备利用率 更主要的是为了避免由于响应不及时 将造成信息的丢失 在用户进程中 I O繁忙的进程应优先与CPU繁忙的进程 以保证CPU和I O设备之间的并行操作 在分时系统中 前台进程应优先于后台进程 AppliedOperatingSystemConcepts 作业 进程调度算法 时间片轮转Round Robin RR 调度算法用于进程调度 是分时系统采用的主要调度算法 进程调度程序总是选择就绪队列中第一个进程 允许其占有处理机一个时间片的时间 当执行的时间片用完时 调度程序便仃止该进程的执行 并将它送就绪队列的末尾 等待分配下一时间片再执行 然后把处理机分配给就绪队列中新的队首进程 在RR算法中 时间片的大小对系统性能有很大的影响 当时间片足够大时 当时间片很小时 AppliedOperatingSystemConcepts RoundRobin RR EachprocessgetsasmallunitofCPUtime timequantum usually10 100milliseconds Afterthistimehaselapsed theprocessispreemptedandaddedtotheendofthereadyqueue 每个进程将得到小单位的CPU时间 时间片 通常为10 100毫秒 时间片用完后 该进程将被抢占并插入就绪队列末尾 Iftherearenprocessesinthereadyqueueandthetimequantumisq theneachprocessgets1 noftheCPUtimeinchunksofatmostqtimeunitsatonce Noprocesswaitsmorethan n 1 qtimeunits 假定就绪队列中有n个进程 时间量为q 则每个进程每次得到1 n的 不超过q单位的成块CPU时间 没有任何一个进程的等待时间会超过 n 1 q单位 Performance 特性 qlarge FIFOqsmall qmustbelargewithrespecttocontextswitch otherwiseoverheadistoohigh q相对于切换上下文的时间而言足够长 否则将导致系统开销过大 AppliedOperatingSystemConcepts F C B A CPU 完成 A BC 时间片轮转算法 当时间片很大时 每个进程得到比完成该进程多的处理机时间 此时轮转调度模式退化为先进先出模式 当时间片非常小时 上下文转换开销就成了决定因素 系统性能降低 大多数时间都消耗在处理机的转换上 只有少许用在用户的计算上 AppliedOperatingSystemConcepts 这个最佳的时间片值是多少呢 显然 它将随系统而异 随负载而异 同时也随进程异 时间片的选取是实现各种调度算法的关键之处 而时间片的独额定通常应考虑终端数目 处理机能力 各终端任务的急迫程度 外存传输速度等方面的因素 时间片轮转法亦可应用于批处理系统的处理机调度 AppliedOperatingSystemConcepts Example RRwithTimeQuantum 20 ProcessBurstTimeP153P217P368P424TheGanttchartis Typically higheraverageturnaroundthanSJF butbetterresponse 典型的说 RR的平均周转时间比SJF长 但响应时间要短一些 0 20 37 57 77 97 117 121 134 154 162 AppliedOperatingSystemConcepts HowaSmallerTimeQuantumIncreasesContextSwitches AppliedOperatingSystemConcepts TurnaroundTimeVariesWithTheTimeQuantum AppliedOperatingSystemConcepts MultilevelQueue Readyqueueispartitionedintoseparatequeues 就绪队列分为 foreground interactive 前台 交互式 background batch 后台 批处理 Eachqueuehasitsownschedulingalgorithm 每个队列有自己的调度算法 foreground RRbackground FCFSSchedulingmustbedonebetweenthequeues 调度须在队列间进行 Fixedpriorityscheduling i e serveallfromforegroundthenfrombackground Possibilityofstarvation 固定优先级调度 即前台运行完后再运行后台 有可能产生饥饿 Timeslice eachqueuegetsacertainamountofCPUtimewhichitcanscheduleamongstitsprocesses e g 80 toforegroundinRR20 tobackgroundinFCFS 给定时间片调度 即每个队列得到一定的CPU时间 进程在给定时间内执行 如 80 的时间执行前台的RR调度 20 的时间执行后台的FCFS调度 AppliedOperatingSystemConcepts MultilevelQueueScheduling AppliedOperatingSystemConcepts 作业 进程调度算法 6 多级反馈 Feedback 队列调度算法 基于时间片轮转法前面介绍的各种用作进程调度的算法 都有在一定的局限性 如短进程优先算法仅照顾了短进程而怠慢了长进程 况且对进程运行的长短 往往难以正确估计 所以短进程优先的调度算法无法正确使用 而多级反馈队列调度算法 则不必事先知道各种进程所需的执行时间 仍能基本满足短进程优先和I O频繁的进程优先的需要 因而是目前公认的较好的一种进程调度算法 各个就绪队列中进程执行时间片的大小也各不相同 在优先级越高的队列中 每个进程的执行时间片就规定得越小 当一个线程执行完一个完整的时间段后被中断抢占处理器 而被抢占的线程优先级降低一级而进入下级就绪队列 如此继续 直至降到线程的基本优先级 而一个线程从阻塞态变为就绪态时要提高优先级 好处 终端型作业短批处理作业长批处理作业 AppliedOperatingSystemConcepts 图 多级反馈队列 AppliedOperatingSystemConcepts MultilevelFeedbackQueue Aprocesscanmovebetweenthevariousqueues agingcanbeimplementedthisway 进程能在不同的队列间移动 可实现老化 Multilevel feedback queueschedulerdefinedbythefollowingparameters 多级反馈队列调度程序由以下参数定义 numberofqueues 队列数 schedulingalgorithmsforeachqueue 每一队列的调度算法 methodusedtodeterminewhentoupgradeaprocess 决定进程升级的方法 methodusedtodeterminewhentodemoteaprocess 决定进程降级的方法 methodusedtodeterminewhichqueueaprocesswillenterwhenthatprocessneedsservice 决定需要服务的进程将进入哪个队列的方法 AppliedOperatingSystemConcepts MultilevelFeedbackQueues AppliedOperatingSystemConcepts ExampleofMultilevelFeedbackQueue Threequeues Q0 timequantum8millisecondsQ1 timequantum16millisecondsQ2 FCFSSchedulingAnewjobentersqueueQ0whichisservedFCFS WhenitgainsCPU jobreceives8milliseconds Ifitdoesnotfinishin8milliseconds jobismovedtoqueueQ1 新的作业进入FCFS的Q0队列 它得到CPU时能使用8毫秒 如果它不能在8毫秒内完成 将移动到队列Q1 AtQ1jobisagainservedFCFSandreceives16additionalmilliseconds Ifitstilldoesnotcomplete itispreemptedandmovedtoqueueQ2 作业在Q1仍将作为FCFS调度 能使用附加的16毫秒 如果它还不能完成 将被抢占 移至队列Q2 AppliedOperatingSystemConcepts Multiple ProcessorScheduling CPUschedulingmorecomplexwhenmultipleCPUsareavailable 多个CPU可用时 CPU调度将更为复杂 Homogeneousprocessorswithinamultiprocessor 多处理器内的同类处理器 Loadsharing 负载共享 ifseveralidenticalprocessorsareavailable thenloadsharingcanoccur useacommonreadyqueueSymmetricMultiprocessing SMP eachprocessormakesitsownschedulingdecisions 对称多处理器 每个处理器决定自己的调度方案 Asymmetricmultiprocessing onlyoneprocessoraccessesthesystemdatastructures alleviatingtheneedfordatasharing 非对称多处理器 仅一个处理器能处理系统数据结构 这就减轻了对数据的共享需求 AppliedOperatingSystemConcepts 什么是多处理机系统多处理机操作系统的分类多处理机系统调度策略 多处理机调度 AppliedOperatingSystemConcepts 多处理机系统 是一个具有两个或多个处理机并能相互进行通信以协同一个大的给定问题求解的计算机系统 特点 1 有两个或多个处理机2 共享主存或高速通信网络3 共享输入输出子系统4 有单一完整的操作系统5 各级硬件和软件相互作用 什么是多处理机系统 AppliedOperatingSystemConcepts 主要功能 进程分配 更好的利用多机硬件 资源在处理机之间的分配 改善程序的响应时间 处理机的负载平衡 处理机间的协调和同步 因处理机故障引起的系统重组 AppliedOperatingSystemConcepts 使用多处理机协调工作 来完成用户所要求任务的计算机系统 这包扩了并行处理系统 parallelprocessingsystem 也包扩了在物理上分散且通过不同的物理传输媒体传输数据的计算机网络系统和计算机网络为基础的 对用户透明的分布式系统 以及在同一的计算机系统里共享内存的多处理机系统 广义的计算机系统的一个共同的特点是有n个处理器 n 1 能做到真正的并行处理 也就是能同时执行n条指令 AppliedOperatingSystemConcepts 多处理机操作系统是指那些用来并行执行用户的几个程序 以提高系统的吞吐率 或并行操作以提高系统可靠性的多处理操作系统 这种系统由共享公共内存和外设的n n 1 个CPU组成 从概念上说 在多处理机系统中的各进程的行为与在单机系统下的行为相同 因此 对多处理机操作系统的要求与对多道程序的批处理系统没有太多的区别 但是 多处理环境下 进程可在各处理机间进行透明迁移 从而 由进程上下文切换等带来的系统开销将使得多处理机操作系统的复杂度大大增加 另外 由于多处理机系统并行地执行用户的几个程序 进程 这又带来了多处理机条件下的并发执行问题 多处理机操作系统的分类 AppliedOperatingSystemConcepts 使用多处理机系统的主要原因是提高系统的可靠性和在发生故障时能降级使用 另一个原因是提高系统吞吐 因此 一个多处理机操作系统除了提高资原分配和管理 进程和处理机管理 内存和数据集保护以及文件系统等功能之外 还能提供系统结构重组的能力 以支持系统的降级使用 因此 多处理机的调度策略也必须考虑到降级使用和结构重组问题 AppliedOperatingSystemConcepts 1 紧密耦合和松弛耦合紧密耦合 共享主存和I O松散耦合 通过通信线路与其他计算机交换信息2 对称多处理器系统和非对称多处理器系统对称多处理器系统 地位相同非对称多处理器系统 一个主处理器 多个从处理器 多处理器系统的类型 AppliedOperatingSystemConcepts 1 对称多处理器系统中的进程分配方式1 静态分配方式优点 进程调度的开销小缺点 各处理器的忙闲不均2 动态分配方式一个公共的就绪队列 进程在多个处理器上动态转移 对松散耦合系统开销太大 进程分配方式 AppliedOperatingSystemConcepts 2 非对称多处理器系统的进程分配方式进程调度由主机完成 主机中保持就绪队列 从机发出索求进程的请求优点 简单缺点 瓶颈 进程分配方式 AppliedOperatingSystemConcepts 1 自调度方式系统中设置一个公共的就绪队列 处理器在空闲时都可从该队列中按照一定的调度算法取得一个进程 优点 简单 均匀 不会出现处理机空闲缺点 互斥访问就绪队列 低效 线程切换频繁 进程调度方式 AppliedOperatingSystemConcepts 将一个进程中的一组线程 分配到一组处理器上去执行 两种方式 1 面向所有应用程序平均分配处理器时间2 面向所有线程平均分配处理器时间3 专用处理器分配方式专为应用程序分配一组处理器 2 成组调度方式 AppliedOperatingSystemConcepts 1 多处理机系统与单机调度的区别多处理机调度与单机调度的主要区别涉及两个资源分配问题 一是存放程序或数据的存储器分配及如何访问他们的问题 在多机系统中 由于各进程在物理上也同时执行而不是单机系统那样的交叉执行 这些在物理上同时执行的进程可能同时访问物理存储器的同一地址 处理机对同一存储块的访问必须是顺序的 各进程同时访问物理存储器上的同一地址是不允许的 多处理机系统调度策略 AppliedOperatingSystemConcepts 二是将等待执行的就绪进程分配到哪一个处理机上执行的问题 在单机系统中 由于只有一个处理机 在调度程序中选取了某个就绪状态的进程之后 不须再选择处理机 而在多机系统中 为了尽量做到让各处理机负荷平衡 可能会将处理机在进程之间进行多次切换 如果被切换进程正在执行其临界区部分或系统中进程数目相当多 这种频繁的上下文转换将会使系统效率大大下降 AppliedOperatingSystemConcepts 为了解决进程对处理机的分配问题 在有的多处理机系统中采用了局部就绪对列的方法限制进程的转移 局部就绪对列 就是把处于就绪状态的进程分成不同的组 并使每一组进程和一个处理机对应起来 这样 每个处理机只执行以其对应就绪对列中的进程 各个就绪对列中的进程不断发生横向转移 这种方法减少了调度程序的开销 但是 处理机的使用率却因此下降 例如 系统中某个局部就绪对列中因等待进程较多而使得对应的处理机十分繁忙 而另外的处理机则因就绪对列为空而处于空闲状态 AppliedOperatingSystemConcepts 多处理机系统的调度目标是 以最高的可靠性 使用最少的处理机在最短的时间内完成最多的可以并行完成的进程 AppliedOperatingSystemConcepts 多处理机的调度有两种评价模型 一种是确定性模型 另一种是随机性模性 确定性模型 进程调度执性之前 估计出这些被调度进程所须要的执行时间 以及这些进程之间的相互关系 调度程序的目的 是根据给定的执行时间和相互关系 确定出一个最佳的执行顺序 因此 确定性模型只用来确定给定进程的执行顺序 而随机性模性则常被用来研究动态调度技术 2 多处理机的调度评价 AppliedOperatingSystemConcepts Real TimeScheduling Hardreal timesystems requiredtocompleteacriticaltaskwithinaguaranteedamountoftime 硬件实现的实时系统 用于实现要求在给定的时间内执行完临界进程的场合 theprocessissubmittedalongwithastatementoftheamountoftimeinwhichitneedstocompleteorperform resourcereservation hardreal timesystemsarecomposedofspecialspecial purposesoftwarerunningonhardwarededicatedtotheircriticalprocess andlackthefullfunctionalityofmoderncomputersandoperatingsystems AppliedOperatingSystemConcepts Real TimeScheduling Softreal timecomputing requiresthatcriticalprocessesreceivepriorityoverlessfortunateones 软件实现的实时计算 当要求临界进程得到比其他进程更高的优先级时 implemention first thesystemmusthavepriorityscheduling andreal timeprocessesmusthavethehig