操作系统OS_03_处理机调度与死锁.ppt

第三章 处理机调度与死锁 3.1 处理机调度的层次 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 3.1 处理机调度的基本概念 在多道程序环境下，进程数目往往多于处理机数目。这就要求系统能够按某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。 3.1 处理机调度的基本概念 按调度的层次： 高级调度 中级调度 低级调度。 按OS的类型： 批处理调度 分时调度 实时调度 多处理机调度。 3.1.1 高级调度 高级调度（作业调度，长程调度） 决定把外存上处于后备队列中的哪些作业调入内存。 术语：作业，作业步，作业流，作业控制块 3.1.1 高级调度 1.作业：包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。 在批处理系统中，是以作业为基本单位从外存调入内存的。 分时、实时系统不需要作业调度。 3.1.1 高级调度 作业步(Job Step)：在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。 作业流：若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。 3.1.1 高级调度 2.作业控制块JCB(Job Control Block) 为了管理和调度作业，为每个作业设置了一个作业控制块，它是作业在系统中存在的标志。 包含的内容有：作业标识、用户名称、用户帐户、作业类型、作业状态、调度信息(优先级、已运行时间)、资源需求、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。 3.1.1 高级调度 3.作业调度（接纳调度） 功能：按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配资源。然后将新创建的进程插入就绪队列。 决定接纳多少个作业 取决于多道程序度，即允许多少个作业同时在内存中运行 决定接纳哪些作业 取决于所采用的调用算法 3.1.2 低级调度 1.低级调度（进程调度，短程调度） 配置在：多道批处理、分时、实时系统。 功能：决定就绪队列中哪个进程获得处理机。 保存处理机的现场信息。 按某种算法选取进程。 把处理器分配给进程。 3.1.2 低级调度 2.进程调度中的三个基本机制 排队器。 分派器(分派程序)。 上下文切换机制。 两对上下文切换： 保存当前进程，装入分派程序的上下文； 移出分派程序，装入新选进程的CPU现场信息。 3.1.2 低级调度 上下文切换机制。 缺点：上下文切换时间开销大。 通过硬件(两组或多组寄存器)方法减少切换时间。一组寄存器供处理机在系统态时使用，另一组寄存器供应用程序使用。上下文切换只需改变指针，指向对应寄存器组。 3.1.2 低级调度 进程调度方式 非抢占方式 调度原因：执行完毕；IO请求；P操作、Block、Wackup等原语。 优点：简单，系统开销小，适用于大多数的批处理系统环境。不适合实时系统。 抢占方式 优点：提供更公平的服务。 缺点：系统开销大。 基于的原则：优先权、短作业（进程）优先、时间片原则 3.1.3 中级调度 中级调度（ 中程调度） 引入目的：提高内存利用率和系统吞吐量。 实现： 将暂时不用的进程调至外存，把此时的进程状态称为就绪驻外存状态或挂起状态。 进程具备条件、且内存有空闲时重新调入内存，状态改为就绪状态。 实质：对换功能（存储器管理） 3.2 调度队列模型和调度准则 在分时系统中通常仅设置了进程调度。 1.仅有进程调度的调度队列模型： 多个阻塞队列的调度队列模型 2.具有高级和低级调度的调度队列模型 3.具有三级调度的调度队列模型 3.2.2 选择调度方式和调度算法的若干准则 1.面向用户的准则 （1）周转时间短 周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。 包括四部分时间：作业在外存后备队列上等待调度的时间，进程在就绪队列上等待调度的时间，进程在CPU上执行的时间，以及进程等待I/O操作完成的时间。 平均周转时间： 平均带权周转时间： 3.2.2 选择调度方式和调度算法的若干准则 1.面向用户的准则 （2）响应时间快 响应时间：从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。 （3）截止时间的保证 截止时间：指某任务必须开始执行的最迟时间，或必须完成的最迟时间。 （4）优先权准则 3.1.3 选择调度方式和调度算法的若干准则 2.面向系统的准则 系统吞吐量高 吞吐量：单位时间内系统所完成的作业数。 处理机利用率好 各种资源的平衡利用 3.3 调度算法 调度算法：根