操作系统课件4.ppt

《操作系统课件4.ppt》由会员分享，可在线阅读，更多相关《操作系统课件4.ppt（54页珍藏版）》请在优知文库上搜索。

1、 处理机处理机调度调度1调度策略考虑：周转时间 吞吐率响应时间 设备利用率研究的内容有：作业与进程的关系 作业调度策略与算法进程调度策略与算法 本章主要讨论处理机分配问题 处理机处理机调度调度21.作业的状态及其转换提交状态：一个作业在其处于输入设备进入外部存储设备的过程称为提交状态后备状态（收容状态）：输入管理系统不断地将作业输入到外存对应部分（或称输入井），如果一个作业的全部信息已全部输入到输入井，在它还没有被调度去执行前，该作业处于后备状态。运行状态：作业一旦被作业调度程序选中而被送入主存中投入运行。完成状态：作业运行完毕，但它所占用的资源尚未被系统全部回收时，该作业处于完成状态4.1

2、分级调度 处理机处理机调度调度3 作业状态及其转换图 spoolingspooling系统系统提交提交收容收容就绪就绪等待等待交换调度交换调度完完成成作业调度作业调度进程调度进程调度运行运行就绪就绪等待等待外存线程调度线程调度内存输入井 处理机处理机调度调度4高级调度（作业调度、宏观调度）按一定原则对外存输入井上的作业进行调度，并建立进程PCB。它决定允许哪些作业竞争系统资源。由于这种调度决定哪些作业可以进入系统，所以也称收容调度。作业一旦被系统收容，就便成进程或进程组。 所做的工作：1 选择作业； 2 分配资源；3 建立作业的进程； 4 建立有关的表格 5 作业的善后处理。2调度的层次 处理

3、机处理机调度调度5中级调度（交换调度）它决定允许哪些进程竞争处理机。中级调度通过使进程临时挂起和激活的方法对系统负载波动作出反映，以便获得平稳的系统操作和实现较好的系统综合性能目标，中级调度的作用使作为作业进入系统和将中央处理机分配给这些作业二者之间的一个缓冲。引入中级调度的目的是为了提高内存的利用率和系统吞吐量调度的层次（续） 处理机处理机调度调度6低级调度（进程调度）它决定了存在就绪进程时，哪一个就绪进程将分配到中央处理机，并且把中央处理机实际分配给这个进程（即低级调度是将处理机分配给进程）。 低级调度是由每秒可操作许多次的处理机调度程序执行，处理机调度程序应常驻内存。进程调度的方式：非抢

4、占方式，抢占方式。抢占的方式有：1 时间片原则；2 优先级原则；3 短进程优先原则调度的层次（续） 处理机处理机调度调度7 作业是用户向计算机提交任务的任务实体。 进程是计算机为了完成用户任务实体而设置的执行实体。 显然，计算机要完成一个任务实体，必须要有一个以上的执行实体，一个作业总是由一个以上的多个进程组成。3作业与进程的关系 处理机处理机调度调度8作业调度的功能：按某种算法从后备队列中挑选一个或一批作业调入内存. 后备作业队列与作业控制块 系统中有若干作业在输入井中，为了管理和调度作业，就必须记录已进入系统的各作业的情况，系统为每个作业设置了一个作业控制块（JCB）。内容：作业名、作业状

5、态、作业调度，以及资源申请和一些控制信息。4.2 作业的调度 处理机处理机调度调度9 作业控制块JCB 作业名作业名 作业类型作业类型 资源要求资源要求 资源使用情况资源使用情况 优先级优先级 当前状态当前状态 其它其它作业控制块JCB 处理机处理机调度调度10作业调度按照某种调度算法从后备作业队列中选取作业，使其进入内存运行。 作业调度程序的主要功能是审查系统是否能满足用户作业的资源要求以及按照一定的算法选取作业。1作业调度及其功能 处理机处理机调度调度11按照某种调度算法从后备作业队列中选取作业。为被选取的作业分配内存和外设资源（当系统为动态分配外设时，作业所申请的外设只作为调度的参考因素

6、）。因此要用到内存分配程序和外设分配程序。为选中的作业建立相应的进程。为作业开始运行做好一切准备工作。如构造和读写作业运行时所需要的有关表格及建立负责其运行控制的作业运行控制程序。在作业运行完毕或运行过程中因某种原因需要撤离时，作业调度程序还有完成作业的善后处理工作，如收回分配给他的全部资源2.作业调度应完成如下几方面的工作 处理机处理机调度调度12 （1）作业从后备状态到执行状态 （2）作业从执行状态到完成状态 作业调度中状态的转换过程 处理机处理机调度调度13后备作业队列空按调度算法从作业中选出一作业调用存储、设备管理程序，审核资源要求资源要求能满足？放弃该作业否分配资源调用进程管理程序建

7、立进程进程调度否是出口作业从后备状态到执行状态是 处理机处理机调度调度14撤销该作业的所有进程及作业的JCB调用存储管理，设备管理回收分配给该作业的全部资源调用会计程序，计算该作业的执行费用调度下一个作业作业从执行状态到完成状态 处理机处理机调度调度151)调度目标 对所有作业应该是公平合理 应使设备有高的利用率 每天执行尽可能多的作业 有快的响应时间3.作业调度目标与性能衡量 处理机处理机调度调度162）.衡量一个作业调度算法是否满足系统设计的要求 给出两个常用的评价在批处理系统中对作业调度算法优劣的性能量度1周转时间：作业i从提交时刻tsi到完成时刻tei称为作业的周转时间。Ti = Te

8、i - Tsi 完成 提交作业调度目标与性能衡量 处理机处理机调度调度17作业平均周转时间为（有n个作业，n=1) nT=1/ /n Ti i=1一个作业的周转时间说明了该作业在系统内停留的时间包含两部分：一是等待时间；二为执行时间Ti = Twi + Tri(停留时间)作业调度目标与性能衡量 处理机处理机调度调度182带权周转时间Wi：Wi=Ti/ /Tri 平均带权周转时间为： nW=1/ /n Wi i=1作业调度目标与性能衡量 处理机处理机调度调度19 进程调度的功能：从就绪队列中挑选一个进程到处理机上运行。 作业调度程序在挑选作业进入主存运行时，要为该作业建立相应的进程。在作业完成后

9、要撤销该作业的全部进程。 一个进程被建立后，系统为了便于对进程的管理，将系统中的所有进程按其状态将其组织成不同的进程队列。 4.3进程调度 处理机处理机调度调度20 进程调度程序：负责进程调度功能的内核程序。作业调度与进程调度程序的区别：前者是挑选作业进主存运行、后者是挑选就绪进程到处理机上运行。进程调度的核心问题就是，采用什么算法把处理机分配给进程。进程调度 处理机处理机调度调度21进程调度4.3.1进程调度的功能 1记录系统中所有进程的执行情况 2选择占有处理机的进程 3进行进程上下文的切换4.3.2进程调度的时机1 执行完毕 2 执行中的进程阻塞自己3 执行P原语被阻塞，执行V原语唤醒4

10、 提出I/O请求被阻塞 5 时间片用完6 执行系统调用 处理机处理机调度调度22进程的上下文切换过程： 用户态执行进程A代码进入OS核心（通过时钟中断或系统调用） 保存进程A的上下文，恢复进程B的上下文（CPU寄存器和一些表格的当前指针） 用户态执行进程B代码注：上下文切换之后，指令和数据快速缓存cache通常需要更新，执行速度降低4.3.3进程上下文切换 处理机处理机调度调度23（1） 先来先服务（FCFS）调度算法 将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。它优先考虑在系统中等待时间最长的作业，而不管要求运行

11、时间的长短。 4.4调度算法 处理机处理机调度调度24在单道环境下，某批处理有四道作业，已知他们的进入系统的时刻、估计运算时间如下：作业进入时刻(h)运行时间(h)12348.008.509.009.502.000.500.100.20用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间FCFS调度算法（续） 处理机处理机调度调度25作业进入时刻 运行时间 开始时刻 完成时刻周转时间 带权周转12348.008.509.009.502.000.500.100.208.0010.0010.5010.6010.0010.5010.6010.802.002.001.601.301.004

12、.0016.006.50平均周转时间T1.725（h）平均带权周转时间T6.875FCFS调度算法（续） 处理机处理机调度调度26完成DCBACPU进程调度算法FCFS(先来先服务调度算法) 最简单的调度原则是先进先出就绪队列 处理机处理机调度调度27 根据进程到达就绪队列的时间来分配中央处理机，一旦一个进程获得了中央处理机，就一直运行到结束，先来先服务是非剥夺调度。 这种调度从形式上讲是公平的，但它使短作业要等待长作业的完成，重要的作业要等待不重要作业的完成。从这个意义上讲又是不公平的。 先进先出调度使响应时间的变化较小，因此它比其它大多数调度都可预测。由于这种调度方法不能保证良好的响应时间

13、，在处理交互式用户时很少用这种方法。FCFS(先来先服务调度算法) 处理机处理机调度调度28 FCFS的特点的特点比较有利于长作业，而不利于短作业。比较有利于长作业，而不利于短作业。有利于有利于CPU繁忙的作业，而不利于繁忙的作业，而不利于I/O繁忙的繁忙的作业。作业。 处理机处理机调度调度29 在当今系统中，先进先出很少作为调度主模式，而是常常嵌套在其它的调度模式中。例如，许多调度模式根据优先级将处理机分配给进程，但具有相同优先级的进程却按先进先出进行分配。FCFS(先来先服务调度算法) 处理机处理机调度调度30 选择调度算法时应考虑的问题进程调度的算法较多，在设计进程调度算法时应考虑的因素

14、多，比如：尽量提高资源利用率，减少处理机的空闲时间，对于用户作业要较合理的平均响应时间，以及尽可能地增强CPU的处理能力。 处理机处理机调度调度31（2）.最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业运行顺序 1 3 4 2作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.30 10.80 2.30 4.60 3 9.00 0.10 10.00 10.10 1.10 11.00 4 9.50 0.20 10.10

15、 10.30 0.80 4.00 平均周转时间 T1.55h平均带权周转时间T5.15 处理机处理机调度调度32 SJF的特点的特点优点：优点： 比比FCFS改善平均周转时间和平均带权周转改善平均周转时间和平均带权周转时间，缩短作业的等待时间；时间，缩短作业的等待时间； 提高系统的吞吐量；提高系统的吞吐量；缺点：缺点： 对长作业非常不利，可能长时间得不到执行；对长作业非常不利，可能长时间得不到执行； 未能依据作业的紧迫程度来划分执行的优先未能依据作业的紧迫程度来划分执行的优先级；级； 难以准确估计作业（进程）的执行时间，从难以准确估计作业（进程）的执行时间，从而影响调度性能。而影响调度性能。

16、处理机处理机调度调度33最高响应比作业优先算法是对FCFS方式和SJF方式的一种综合平衡响应比R定义： R1 W/T其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。(3)最高响应比作业优先算法（HRN） 处理机处理机调度调度34 响应比R不仅是要求运行时间的函数，而且还是等待时间的函数。由于R与要求运行时间成反比，故对短作业是有利的，另一方面，因R与等待时间成正比，故长作业随着其等待时间的增长，也可获得较高的响应比。这就克服了短作业优先算法的缺点，既照顾了先来者，又优待了短作业，是上述两种算法的一种较好的折中。 最高响应比作业优先算法（HRN） 处理机处理机调度调度35最高响应比作业优先算法（HRN）作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.10 10.60 2.10 4.20 3 9.00 0.10 10.00 10.10 1.10 11.00 4 9.50 0.20 10.60 10.80