操作系统-(1)()

《操作系统-(1)()》由会员分享，可在线阅读，更多相关《操作系统-(1)()（52页珍藏版）》请在金锄头文库上搜索。

1、第三章 处理机调度与死锁 第三章 处理机调度与死锁 3.1 处理机调度的层次3.2 调度队列模型和调度准则3.3 调度算法3.4 实时调度 3.5 产生死锁的原因和必要条件3.6 预防死锁的方法第三章 处理机调度与死锁 在多道程序环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的，算法的优劣直接影响整个系统的性能。它是操作系统设计的中心问题之一。进程调度要解决的问题: WHAT： 按什么原则分配CPU进程调度算法WHEN： 何时分配CPU进程调度的时机HOW： 如何分配CP

2、UCPU调度过程（进程的上下文切换）第三章 处理机调度与死锁 处理机调度可以分为3层：1）高级调度（作业调度、长程调度）：按一定原则选择若干个后备作业调入主存，分配资源，并建立相应 的进程，投入运行。当该作业执行完毕时，还负责回收资源。2）中级调度（交换调度、中程调度、均衡调度）：按照给定的原则实现进程在主存和外存交换区之间的换进换出，以 解决内存紧张问题，特别是具有虚拟存储器的系统中。 3）低级调度（进程调度、短程调度）：按照某种策略从进程就绪队列中选择一个就绪进程，使其占有处理 机运行。3.1 处理机调度的层次 第三章 处理机调度与死锁 一、高级调度-作业调度1作业的基本概念1）作业、作业

3、步作业：是用户一次请求计算机系统为它完成任务所进行的工作总和。作业步：作业加工工作中的一个相对独立的步骤称为作业步。对作业的处理一般有这样几个作业步：编辑（修改）、编译、连接、运行 。作业管理: 一个作业从输入到输出的一个过程。大致分成：作业提交、作业调度、作业控制、和作业退出。作业步之间的关系： 每个作业步运行的结果产生下一个作业步所需要的文件。 一个作业步能否正确地执行，依赖于前一个作业步是否成功的完成 。例如： user.c user.obj user.exe编辑 编译 连接 运行第三章 处理机调度与死锁 对于被调度 的作业，OS 要对它在系 统中整个运 行过程实行 控制。 编译运行装配

4、目标 程序 段目标 程序装配 程序运行 程序源程序输入数据输出信息输出信息输出信息子程序库函数动态 库函 数运行结果编译 程序图： 作业的控制过程结束第三章 处理机调度与死锁 2）作业的类型根据计算机系统的作业处理方式不同，可以把作业分成两类：脱机作业（批处理作业）：使用作业控制语言来书写一份作业控制说明书，规定如何控制作业的执行。联机作业（交互式作业或终端型作业）：使用OS提供的命令语言直接提出对作业的控制要求。3）作业的组织 程序 作业由三部分组成 数据作业说明书 （说明用户的控制意图）第三章 处理机调度与死锁 4）作业控制块（JCB）：为了管理和调度作业，在多道批处理系统中为每个作业设置

5、了一个 作业控制块，作业控制块JCB是作业存在的标志，记录与该作业有关的信 息。作业控制块（JCB）的主要内容：(1)作业的基本情况用户名、作业名、作业的状态和使用的语言等。(2)作业的控制要求控制方式、类型、优先数、操作顺序和出错处理等。(3)作业的资源要求作业建立的时间、要求运行的时间、最迟完成的时间、需要的主存容 量、外设的种类及数量和资源使用情况。第三章 处理机调度与死锁 作业名 资源要求估计执行时间 最迟完成时间 要求的主存量 要求外设的类型及台数 要求文件量和输出量 资源使用情况进入系统时间 开始执行时间 已执行时间 主存地址 外设台号 类型控制方式 作业类型 优先级 状态联机和脱

6、机第三章 处理机调度与死锁 5）作业的状态一个作业从提交给计算机系统到执行结束退出系统，一般都要经历4个 状态：提交、后备（收容）、执行和完成。（1）提交状态：通过终端设备向计算机的磁盘输入作业信息时所处的 状态。（2）后备状态：作业的全部信息已输入到磁盘的一个专用区(输入井) 中等待作业调度时所处的状态。（3）执行状态：在后备作业队列中的作业一旦被作业调度程序选中， 为它分配了必要的资源，并且建立了进程, 开始处理时所处的状态。（4）完成状态：作业完成其全部任务后，进程撤消, 做善后处理时的作 业状态称为完成状态。第三章 处理机调度与死锁 106）作业状态的及其转换 作业的状态及其转换 执行

7、 进程调度 内存 线程调度运 行等 待就 绪外存 就 绪等 待提 交后 备完 成作业输入 作业调度 交换调度 作业调度 执 行第三章 处理机调度与死锁 7）作业的建立包括： 作业的输入；作业控制块（JCB）的建立；多道批处理系统第三章 处理机调度与死锁 作业进入 系统建立 JCB调入后备队列插入作业 调度 算法创建进程 分配资源 插入就绪队列内存 调度CPU完成收回资源 撤消JCB合格作业审核2. 作业调度批处理系统需要，分时系统不需要第三章 处理机调度与死锁 用户希望：自己作业的周转时间尽少。系统希望：作业的平均周转时间尽少。执行作业调度考虑： 1) 决定接纳多少个作业。（取决于多道程序度）

8、折衷： 太多，影响到系统的服务质量，如周转时间长。少时，系统的资源利用率和系统吞吐量太低。2) 决定接纳哪些作业取决于所采用的调度算法。调度算法： 先来先服务； 简单短作业优先， 常用基于作业优先级 较常用响应比高者优先 比较好第三章 处理机调度与死锁 二、低级调度进程调度多道批处理、分时和实时OS都必须配置这级调度。系统按照某种算法把CPU动态地分配给某一就绪进程。进程调度工作是通过进程调度程序来完成的。1低级调度的任务(1) 保存处理机的现场信息。PC（程序计数器）、通用寄存器内容等送入PCB 。(2) 按某种算法选取进程。如：优先数算法、轮转法。 (3) 把处理器分配给进程。由分派程序(

9、Dispatcher)把处理器分配给进程。从选中的进程PCB中恢复处理机现场。第三章 处理机调度与死锁 2进程调度中的三个基本机制(1) 排队器。排成一个或多个队列，调度程序能最快地找到它。(2) 分派器(分派程序)。分派器把由进程调度程序所选定的进程，将处理机分配给它。(3) 上下文切换机制。当前 进程新选 进程分派 程序切换第一个上 下文切换第二个上 下文切换第三章 处理机调度与死锁 PC 寄存器CPU硬件现场当前程序分派程序新选进程PCB现场保留区PCB现场保留区PCB现场保留区CPU第三章 处理机调度与死锁 3.确定算法的原则 具有公平性 资源利用率高（特别是CPU利用率）。 在交互式

10、系统情况下要追求响应时间（越短越好）。 在批处理系统情况下要追求系统吞吐量。第三章 处理机调度与死锁 4进程调度方式1) 非抢占方式(Nonpreemptive Mode)分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。优点：实现简单，系统开销小，适用批处理系统。缺点：难满足紧急任务的要求，实时系统不宜采用。2) 抢占方式(Preemptive Mode)当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它 的处理机，将之分配给其它进程。抢占原则有：优先权原则、短进程优先原则、时间片原则。第三章 处理机调度与死锁 5进程

11、调度的时机 当一个进程运行完毕，或由于某种错误而终止运行。 当前运行进程执行了I/O指令（要求I/O）。 当前运行进程请求资源，若得不到满足，只好调用阻塞原语，将自己阻塞。 分时系统中时间片到。 当有一个优先级更高的进程就绪（可抢占式）。例如：新创建一个进程；一个等待进程变成就绪。 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）。第三章 处理机调度与死锁 三、中级调度中级调度的主要目的是为了提高内存利用率和系统吞吐量。暂时不 能运行的进程将它们调至外存上去等待，此时的进程状态称为就绪驻外 存状态或挂起状态。进程重又具备运行条件且内存又稍有空闲时，由中级调度来决定把

12、外存上的那些又具备运行条件的就绪进程重新调入内存，并修改其状态 为就绪状态。三种调度方式的比较： 进程调度：运行频率最高、不宜太复杂（避免占用太多的CPU时间）作业调度：运行频率低（一批一批） 、作业调度的周期较长。中级调度：介于上述两种调度之间。第三章 处理机调度与死锁 3.2 调度队列模型和调度准则 一、 调度队列模型1仅有进程调度的调度队列模型适用：分时系统中。FIFO新进程第三章 处理机调度与死锁 仅有进程调度的调度队列模型阻塞队列阻塞队列交互用户阻塞阻塞进程调度是最基本的调度，进程调度是最基本的调度， 必须配置必须配置CPUCPU进程调度进程调度就绪队列就绪队列结束结束时间片完时间片

13、完/ /被中断被中断唤醒唤醒第三章 处理机调度与死锁 进程调度原因（调度时刻）阻塞队列阻塞队列交互用户阻塞阻塞进程调度进程调度就绪队列就绪队列结束结束时间片完时间片完唤醒唤醒现进程运行完毕现进程运行完毕现进程阻塞现进程阻塞优先权高的进程进入就绪队列优先权高的进程进入就绪队列现进程现进程“ “超时超时” ”/ /被中断被中断CPUCPU第三章 处理机调度与死锁 2具有高级和低级调度的调度队列模型适用：批处理系统优先权队列多个 阻塞 队列第三章 处理机调度与死锁 3同时具有三级调度的调度队列模型引入中级调度后:就绪状态: 内存就绪、外存就绪 阻塞状态： 内存阻塞、外存阻塞换进时间片到执行就绪阻塞进

14、程调度等待某事件发生 阻塞所等待的事件发生唤醒进程状态转换及进程控制外存内存就绪阻塞 所等待的事件发生唤醒换出换出换进撤消创建创建挂起挂起激活激活活动 阻塞静止 阻塞静止 就绪活动 就绪第三章 处理机调度与死锁 图 3-3 具有三级调度时的调度队列模型 就绪队列进程调度CPU就绪，挂起队列（外存）中级调度(调入内存)阻塞，挂起队列（外存）阻塞队列（内存） 等待事件进程完成时间片完作业调度交互型作业后备队列 批量作业挂起事件出现事 件 出 现活动 阻塞静止 阻塞静止 就绪活动 就绪第三章 处理机调度与死锁 二、选择调度方式和调度算法的若干准则1面向用户的准则(1) 周转时间短。周转时间是指从作业

15、被提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。包括四部分：1、作业在外存后备队列上等待(作业)调度的时间（作业等待）2、进程在就绪队列上等待进程调度的时间（在就绪队列排队）3、进程在CPU上执行的时间4、进程等待I/O操作完成的时间。第三章 处理机调度与死锁 （a）周转时间 = 完成时刻 提交时刻（到达时间）= 等待时间 + 运行时间(CPU) 对于进入系统的n个作业而言，平均周转时间T为:i1用于衡量不同调度算法对同一作业流的调度性能：平均周转时间越小，该作业调度算法的性能越好。等待时间越长，用户的满意度越低。第三章 处理机调度与死锁 (b)带权周转时间 W = 作业周

16、转时间T提供服务时间（CPU)它能说明作业i的相对等待时间。n平均带权周转时间 W = （ Wi）n i=1用于衡量同一调度算法对不同作业流的调度性能(长短任务差别)：平均带权周转时间越小，作业调度算法对该作业流的调度性能越好。 对于批处理系统，主要依据平均周转时间和平均带权周转时间来作为衡量调度算法性能的指标；而对于分时系统和实时系统，外加平均响应时间作为衡量调度算法性能的指标。 第三章 处理机调度与死锁 (2) 响应时间快。评价分时系统的性能。响应时间: 是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。包括三部分：1、从键盘输入的请求信息传送到处理机的时间。2、处理机对请求信息进行处理的时间。3、响应信息回送到终端显示器的时间。 (3) 截止时间的保证。 评