操作系统 作业调PPT学习教案

1、会计学1 操作系统操作系统 作业调作业调PPT课件课件 第1页/共51页 在大型通用系统中，可能有数百个批处理作 业存放在磁盘的作业队列中，有数百个终端同主 机相联接。因此如何从这些作业中挑选作业进入 主存运行、如何在作业或进程间分配处理等，问 题无疑是操作系统的资源管理功能中的一个重要 问题。本章主要讨论处理机分配问题，或称处理 机调度。 第2页/共51页 一般来说，处理机调度可以分成三级： (1) 高级调度：高级调度：又称作业调度，其主要功能是按照 某种原则从磁盘某些盘区的作 业队列中选取作业进入主存， 并为作业做好运行前的准备工 作和作业完成后的善后工作。 第3页/共51页 (2) 中级

2、调度：中级调度：它决定哪些进程被允许参与竞争处理机 资源。中级调度主要只是起到短 期调整系统负荷的作用，以平顺 系统的操作。其所使用的方法是 通过“ 挂起 ” 和“ 解除挂起 ” 一些进程，来达到平顺系统操 作的目的。 第4页/共51页 (3) 低级调度：低级调度：又称进程调度，其主要功能是按照某 种原则将处理机分配给就绪进程 。执行低级调度功能的程序称为 进程调度程序，由它实现处理机 在进程间的转换。它必须常驻主 存，是操作系统内核的主要部分 。 第5页/共51页 RUN readya blockeda readysblokeds 后备完成 作业后备状态 执行内存 时间片到I/O请求 I/O

3、完成 高级调度(作业调度) 挂起 解挂 挂起 解挂 进程调度 低级调度 中级调度 第6页/共51页 5.1 作业的状态与处理流程作业的状态与处理流程 一、一、 作业状态作业状态 提交收容执行完成 提交状态后备状态运行状态完成状态 第7页/共51页 作业从提交给系统直到它完成后离开系统前的整 个活动常划分为若干阶段。作业在每一阶段中所处的 状况称为作业的状态。系统中的作业通常分为四种状 态： (1) 提交状态：提交状态：一个作业被提交给机房后或用户通过 终端键盘向计算机中键入其作业 时所处的状态为提交状态。 第8页/共51页 (2) 后备状态：后备状态：作业的全部信息都已通过输入机输入， 并由操

4、作系统将其存放在磁盘的 某些盘区中等待运行，则称为后 备状态。 (3) 运行状态：运行状态：作业一旦被作业调度程序先中而被送入 主存中投入运行，称之为运行状 态。 (4) 完成状态：完成状态：作业完成其全部运行，释放出其所占用 的全部资源，准备退出系统的作 业状况称为完成状态。 第9页/共51页 5.2 作业的调度作业的调度 系统中往往有成百个作业被收容在磁盘输 入井中，为了管理和调度作业，就必须记录已 进入系统的各作业的情况。因此同进程中的情 况类似，系统也为每个作业设置一个作业控制 块 (记为JCB)，它记录了作业的有关信息。不同 系统的 JCB 所包含的信息有所不同，这取决系 统对作业调

5、度的要求。 JCB结构 见书P122 图6.8 第10页/共51页 JCB 是在作业进入系统时由 SPOOL 系统为其建立 的。其内容由作业控制卡中得到。同样 JCB 也是作业 存在于系统的标志，作业进入系统时，则为之建立 JCB。当作业退出系统时，则其 JCB 也被撤消。 在磁盘输入井中的所有后备作业按作业类型将它 们组成一个或多个后备作业队列。所谓后备作业队列 是由作业控制块 JCB 用表格或链指针组成的队列。作 业队列可按优先数大小和作业到达系统的时间顺序排 列。 第11页/共51页 一、一、 作业调度作业调度: (JCB作业控制块作业控制块) 根据系统内所有资源的使用情况， 按照 某种

6、调度算法选择一个后备作业进入系统， 并为其创造一个进程。 为此，作业调度还要为选中的作业分配 资源，作好作业支行前的准备。完成作业调度 功能的程序称为作业调度程序。 第12页/共51页 作业调度程序要完成以下工作： (1) 按照某种调度算法从后备作业队列中挑选作业。 (2) 为选中的作业分配主存和外设资源。 (3) 为选中的作业建立相应的进程。 (4) 构造和填写作业运行时所需的有关表格。(如作业表) (5) 作业结束时完成该作业的善后处理工作，如收回资 源，输出必要的信息，撤消该作业的全部进程 (PCB) 和作业控制块 JCB。 第13页/共51页 5.3 进程调度进程调度 作业调度程序在挑

7、选作业进入主存运行时， 要为该作业建立相应的进程。在作业完成后要撤 消该作业的全部进程。因此作业调度程序要调用 操作系统内核所提供的有关的进程管理原语。由 于进程只能由其父进程建立，所以在一般系统中 ，作业调度程序都以进程的形式在系统中存在和 活动，称为作业调度进程。作业调度进程可以说 是系统中的祖先进程，由它完成作业调度的诸多 功能。 第14页/共51页 一个进程被建立后，系统为了便于对进程的管理， 将系统中的所有进程按其状态，将其组织成不同的进程 队列。于是系统中有运行进程队列、就绪进程队列和各 种事件的进程等待队列。 进程调度的功能是从就绪队列中挑选一个进程到处 理机上运行。负责进程调度

8、功能的内核程序称为进程序 调度程序。 第15页/共51页 所谓作业调度程序挑选作业进主存运行是个宏 观的概念，实际上被选进主存运行的作业只是具有 了竞争处理机的机会(将来真正在处理机上运行的 是该作业的一个进程)。而进程调度程序才是真正 让某个就绪进程到处理机上运行。 第16页/共51页 5.4 选择调度算法时应考虑的问题选择调度算法时应考虑的问题 目前比较普遍使用的几种调度算法 ，对于作业调度和进程调度大致上都是 适用的。 第17页/共51页 在设计系统的调度程序时，首先要决定选择何种 调度算法，依据此算法来编制相应的调度程序。而调 度算法实际上就是系统所采取的调度策略，选择时所 要考虑的因

9、素很多。如系统各类资源的均衡使用；对 用户公平并使用户满意；用户作业到达系统的时间； 作业的优先数；对主存和外设的要求；以及整个系统 的效率等。 第18页/共51页 设计时应将那些对系统运行影响较大的关键因素 作为调度算法考虑的主要依据。 (1) 设计目标：设计目标：目标不同，系统的设计要求自 然不同。如批处理系统所追求的是充分发挥和提高计 算机的效率；实时系统所关心的是不要丢失实时信息 并及时给以处理；而分时系统则侧重于保证用户的请 示及时给予响应；计算中心要求系统吞吐量在大等等 。 第19页/共51页 (2) 资源利用率：资源利用率：在考虑设计目标的前提下应充 分发挥各种资源的效能，最大限

10、度地使它们忙碌。科 学计算型作业和数据处理型作业搭配运行就是一种方 法。 (3) 均衡地处理系统和用户的要求：均衡地处理系统和用户的要求：例如个别用 户可能要求使用系统中的几乎全部外设，却只要求很 少的主存。系统若满足这类用户的愿望，势必影响主 存利用率，从而降低系统效率，所以一般都不得不推 迟这种作业的运行时间，等到有要求内存多而外设少 的作业与之搭配运行。但是我们选择的算法也不应使 一个作业的运行被无限制地推迟。 第20页/共51页 (4) 在使用优先级的系统中，每个进程都有一个 优先数，调度算法应优先运行高优先级进程 。 (5) 在使用优先数的系统中，调度策略还分为“ 可抢占 ” 和“

11、不可抢占 ” 两种方式。抢 占策略通常使用于需要迅速响应高优先级进 程的系统中。 第21页/共51页 1. 目标目标: 每天运行尽可能多的作业 选择短作 业(吞吐量) 使处理机保持“ 忙” 选择大运输量 (I/O少) 使I/O保持“ 忙” 选大I/O 效率效率: 5.5 调度算法调度算法 公平性 FCFS(先来先服务) 对所有进 程公平 第22页/共51页 2. 调度算法的衡量调度算法的衡量 尽量缩短周转时间 周转时间: 作业提交作业完成之间的时间 (1) 作业平均周转时间: n T T n i i) ( 1 其中 n 作业流中的作业数 Ti 第i个作业周转时间 Ti= tci tsi 其中

12、tsi 作业i提交时间 tci 作业i完成时间 第23页/共51页 (2) 平均带权周转时间: n t T n w w n iRi i n i i )()( 11 其中: tRi 作业i的实际运行时间 wi 作业i的带权周转时间 第24页/共51页 一、引起进程调度的原因一、引起进程调度的原因 (1) 时间片到 (按时间片运行) (2) 进程提出I/O请求 阻塞，调新进程 (3) 进程挂起 (4) 执行P操作而信号量不足，而被阻塞 (5) 来了更高优先权 (可被剥夺) (6) 进程运行完了 补充： 第25页/共51页 3. 单道批处理作业调度算法及衡量单道批处理作业调度算法及衡量 (1) FC

13、FS 先来先服务先来先服务 先来先服务算法是最简单的调度方法 。其基本原则是按照作业到达系统或进程 进入就绪队列的先后次序来选择。FCFS 策 略是属于不可抢占策略。 第26页/共51页 作业提交时间运行时间开始时间完成时间周转时间带权周 转时间 ts(时)tR(时)tB(时)tC(时)ti(时)Wi(Z) 1 2 3 4 8.00 8.50 9.00 9.50 2.00 0.50 0.10 0.20 8.00 10.00 10.50 10.60 10.00 10.50 10.60 10.80 2.00 2.00 1.60 1.30 6.90 1.00 4.00 16.00 6.50 27.5

14、0 平均周转时间 T=6.90/4=1.725(小时) 平均带权时间 W=27.5/4=6.875 第27页/共51页 从表面上来说，对于所有进程和作业都是公平的， 并且一个作业的等待时间是可以预告估计的。另一方面 来说这个方法也不见得公平，当一个大作业先到达系统 时就会使许多小作业等待很长时间，提高了平均的作业 周转时间，会使许多小作业的用户不满。 先来先服务算法已很少作主要的调度策略，常被结 合在其它的调度策略中使用。例如，在使用优先级作为 调度策略的系统中，往往对许多具有相同优先级的进程 ，使用先来先服务的原则。 第28页/共51页 (2) 优先级调度算法优先级调度算法 按照进程的优先级

15、大小来调度，使高优先级 进程得到优先的处理的高度策略称为优先级调度 算法。 但在许多采用优先级调度的系统中，通常采 用动态优先数策略。进程的优先级不是固定的， 往往随许多因素的变化而变化。尤其随作业（进 程）的等待时间、已使用的处理机时间或其它资 源的使用情况而定。 第29页/共51页 优先级调度方法又可分为： 非抢占的优先级调度法：即一旦某个高优先级的进 程占有了处理机，就一直运行下去，直到由于其 自身的原因而主动让出处理机时(任务完成或等待 事件)才让另一高优先级进程运行。 可抢占的优先级调度法：任何时刻都严格按照高优 先级进程在处理机上运行的原则进行进程的调度 。 第30页/共51页 例

16、：某些I/O繁忙型的进程，它们大部分时间是在等 待I/O操作完成，对于这一类进程，当它们要求 CPU运行时，应立即给予满足，以便让它们开 始下一个I/O操作和其它计算型的进程并行工作 。否则，这些I/O繁忙型的进程将长时间占据存 储器，降低系统并行度。 第31页/共51页 一个行之有效的算法是在进程每次获取CPU运 行后，重新指定该进程的优先级为 1/f。这里的f表示 进程上次在CPU上实际运行时间与时间片之比。例如 ，若时间片为100毫秒，进程上次在CPU上的实际运 行时间为2毫秒，则它的优称级为50；若它上次实际 运行时间为50毫秒，则它的优级为2。由于I/O繁忙型 的进程每次在CPU上运

17、行的时间很短，依此算法，它 们的优先级将较高，从而优先得到服务。 第32页/共51页 (3) 时间片轮转法时间片轮转法 轮转法是最简单又最公平的进程调度算法，因此 也是使用得最多的算法之一。 轮转法分配给每一进程在CPU上运行的时间长度 ，称之为时间片。诸进程以此时间片为限制，轮流使 用CPU。如果时间片到期时，进程尚未完成运行，调 度程序将剥夺它正在使用的CPU，转让给另一进程使 用；如果进程在使用完它的某一时间片之前已经完成 运行或已阻塞，CPU也立即转让给另一进程使用。 第33页/共51页 轮转法在实现上也很容易，调度程序只要维护 一个先进先出的队列数据结构，将就绪进程排队， 每当一个进

18、程的时间片运行完后，便把它从原来的 队头位置移到队尾，然后把现在处于队头位置的进 程调度到CPU上运行。时间片的计数则可通过定时 中断实现。 第34页/共51页 轮转法的性能取决于时间片长度的选择，进程间的 CPU上的切换需要时间。若一次切换时间为5毫秒，时间 片长度选择为20毫秒，则20的CPU时间花费于进程调 度程序。为了改善CPU的利用率，可以增大时间片，比 如说为500毫秒，此时CPU利用率达99之多，但每一进 程的响应时间也因之增大。若就绪队列中共有10个进程 ，则每一进程需要等待5秒钟，才能在CPU上服务一次。 通常来说，选择时间片为100毫秒左右比较适宜。 第35页/共51页 实

19、际中，优先级算法常和轮转法结合使用， 也就是按优先级将进程分组，组间采用优先级调 度算法，而组内优先级相同的进程则按轮转法调 度。显然，若优先级不动态地进行调整，则优先 级低的就绪进程就可能饿死。 第36页/共51页 二、轮转法二、轮转法 (Round Robin) 简单轮转法 分配给就绪队列，每一进程一个时间片(每一 进程在CPU上运行的时间长度)轮流执行。 时间q T = N q 就绪队列 第37页/共51页 q足够大到每一进程执行完，FCFC (先到先服务) q 适当 进程均匀执行 q 太小 开销太大，有切换时间，CPU利用率低。 例：切换t = 5ms, q = 20ms, 则CPU利

20、 率率80，有20花费在进程调度程 序。 决定q 大小因素：响应时间T (进程等待时间)、 队列长度N、轮换时间 (切换时间)、CPU能力 (运算 速度)。 第38页/共51页 例：上例中为改善CPU的利用率，可增大时间片 ，设q = 500ms，此时CPU利用率为99之 多，但每个P 的相应时间也因而增大。若N = 10，则每个P 的相应时间需等5秒，才能 在CPU上服务一次。 考虑上述条件，选择时间片为100ms左右比 较适宜。 第39页/共51页 固定周期轮转法 q 为时间片， T 为周期， N 为进程数 固定T ： max N T q 固定T，N q，开销减少 第40页/共51页 (4

21、) SJF最短作业优先的调度算法最短作业优先的调度算法 要求运行时间最短的作业作为下一次服 务的对象 对于上述作业流， 作业运行结束后， 后 备作业表中已有作业2， 3， 4， 因为作业3要 求运行时间最短， 故选3， 4， 2。 第41页/共51页 tstRtBTiWi 1 2 3 4 8.00 8.50 9.00 9.50 2.00 0.50 0.10 0.20 8.00 10.30 10.00 10.10 2.00 2.30 1.10 0.80 6.20 1.00 4.60 11.00 4.00 20.60 T = 1.55 W=5.15 优: 比FCFS， T W 缺: 有的作业始终得

22、不到运行 tc 10.00 10.80 10.10 10.30 作业提交时间运行时间开始时间完成时间周转时间带权周 转时间 第42页/共51页 (5) 最短剩余时间优先调度算法最短剩余时间优先调度算法 最短剩余时间优先调度算法是把最短作业优称算 法使用于分时环境中的变型。其基本思想是让运行到 作业完成时所需的运行时间最短的进程优先得到处理 ，其中包括新进入系统的进程。在最短作业优先策略 中，一个作业一旦得到处理机就一直运行到完成（或 等待事件）而不能被抢占（除非主动让出处理机）。 而最短剩余时间优先策略是可以被一个新进入系统的 ，并且其运行时间少于当前运行进程的剩余运行时间 的进程所抢占。 第

23、43页/共51页 本策略的优点是可以用于分时系统，保证及时响 应用户要求。缺点是系统开销增加，首先要保存进程 的运行情况记录，以比较其剩余时间大小。其次，抢 占本身也要消耗处理机时间。这个策略使短作业一进 入系统就能立即得到服务，从而降低作业的平均等待 时间。 第44页/共51页 (6) 响应比高者优先响应比高者优先(HRN)算法算法 响应比 作业运行时间 作业等待时间 作业运行时间 作业响应时间 1 p R 上题: 顺序1-3-2-4 1 2 3 4 8.00 8.50 9.00 9.50 2.00 0.50 0.10 0.20 8.00 10.10 10.00 10.60 10.00 10.60 10.10 10.80 2.00 2.10 1.10 1.30 6.50 1.00 4.20 11.00 6.50 22.7 T= 1.625W= 5.675 作业提交时间运行时间开始时间完成时间周转时间带权周 转时间 第45页/共51页 响应比的计算: 第一步: 5 . 3 2 . 0 5 .