[计算机]3处理器调度.pptVIP

* 处理机调度 处理机调度的层次 选择调度算法的原则 作业和进程的关系 作业的管理与调度 1 处理机调度的层次 作业从进入系统成为后备作业开始，直到运行结束退出系统为止，需经历不同级别的调度。 ?高级调度 ?中级调度 ?低级调度 处理器三级调度模型 处理器 低级调度 高级调度 完成 超时 挂起就绪队列 挂起等待队列 等待队列 就绪队列 等待事件 交互式用户 事件 出现 后备作业队列 中级调度 处理器两级调度模型 等待事件 事件发生 进程完成 后备 作业 队列 就绪 队列 高级调度 低级调度 等待 队列 CPU 时间片完 2 选择调度算法的原则(1) l?资源利用率 CPU利用率=CPU有效工作时间/CPU总的运行时间， CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间。 选择调度算法的原则(2) 2?响应时间 ?交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。 ?使交互式用户的响应时间尽可能短，或尽快处理实时任务。 ?这是分时系统和实时系统衡量调度性能的一个重要指标。 选择调度算法的原则(3) 3周转时间 ?批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短。 ?这是批处理系统衡量调度性能的一个重要指标。 选择调度算法的原则(4) 4吞吐率 单位时间内处理的作业数。 5公平性 确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情况。 作业周转与平均周转时间 如果作业i提交给系统的时刻是ts，完成时刻是tf，该作业的周转时间ti为： ti = tf - ts 实际上，它是作业在系统里的等待时间与运行时间之和。 为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。 平均作业周转时间 T = (Σti) / n 作业带权周转时间和平均作业带权周转时间 如果作业i的周转时间为ti，所需运行时间为tk，则称wi=ti /tk为该作业的带权周转时间。 ti是等待时间与运行时间之和，故带权周转时间总大于1。 平均作业带权周转时间W = (Σwi) / n 3处理器调度算法 低级调度的功能和类型 作业调度和低级调度算法 实时调度算法 多处理机调度算法 低级调度的功能和类型 1 低级调度的主要功能 调度程序两项任务：调度和分派。 调度实现调度策略，确定就绪进程/线程竞争使用处理器的次序的裁决原则，即进程/线程何时应放弃CPU和选择哪个来执行； 分派实现调度机制，确定如何时分复用CPU，处理上下文交换细节，完成进程/线程和CPU的绑定和放弃的实际工作。 调度机制逻辑功能程序模块组成 队列管理程序： 进程/线程 状态变化时，它会被排入不同队列。 上下文切换程序： 负责进程/线程 上下文切换。 分派程序： 从就绪队列中选择下个运行的进程/线程 。 低级调度的基本类型 第一类称剥夺式： 两种处理器剥夺原则， (1)是高优先级进程/线程可剥夺低优先级进程/线程， (2)是当运行进程/线程时间片用完后被剥夺。 第二类称非剥夺式： 低级调度算法 1先来先服务算法 先来先服务是按照作业进入系统后备队列的先后次序来挑选作业，先进入系统的作业优先被挑选进入主存。 三个作业同时到达系统并立即进入调度：作业名/所需CPU时间:作业1/28，作业2/9，作业3/3。采用FCFS算法，平均作业周转时间为35。 ? 若三个作业提交顺序改为作业2、1、3，平均作业周转时间约为29。 若三个作业提交顺序改为作业3、2、1，平均作业周转时间约为18。 FCFS调度算法的平均作业周转时间与作业提交的顺序有关。 最短作业优先算法(1) SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。 算法易于实现，效率不高，主要弱点是忽视了作业等待时间。会出现饥饿现象。 SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好。 实现SJF调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。 最短作业优先算法(2) 四个作业同时到达系统并进入调度： 作业名/所需CPU时间:作业1/9，作业2/4 ，作业3/10，作业4/8。 SJF作业调度顺序为作业2、4、1、3， 平均作业周转时间T = 17， 平均带权作业周转时间W= 1.98。 如果施行FCFS调度算法， 平均作业周转时间T =1