03、处理机调度与死锁.ppt

第3章 处理机调度与死锁 第3章 处理机调度与死锁 在多道程序系统中，一个作业从提交到执行完成，要经历多级调度，调度的好坏要影响系统的运行性能，因此调度是多道系统的关键。 为了改善系统资源的利用率和提高系统处理能力，多道程序系统中采用多个进程的并发执行，但它也可能发生死锁的危险，研究死锁的原因和产生条件，采用预防死锁、避免死锁、检测死锁和解除死锁等多种方法防止死锁是多道程序系统重要的研究课题。 第3章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 产生死锁的原因和必要条件 3.5 预防死锁的方法 3.6 死锁的检测与解除 3.1 处理机调度的基本概念 在多道程序中，一个作业被提交后，必须经过处理机调度，方能获得处理机而执行。 对于批量作业而言，通常要经历作业调度和进程调度 对于终端型作业，通常只需经过进程调度 在较完善的操作系统中，往往还设置中级调度 3.1.1 高级、中级和低级调度 高级调度(High Scheduling) 又称作业调度、长程调度 作业调度用于决定把外存输入井上处于作业后备队列上的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。 在批处理系统中，作业是先驻留在外存的输入井上的，因此需要有作业调度。在分时系统中，通过键盘输入的命令和数据直接进入内存，无需作业调度。 在每次执行作业调度时，都须做出以下两个决定。 1) 接纳多少个作业 2) 接纳哪些作业 3.1.1 高级、中级和低级调度 低级调度(Low Level Scheduling) 又称进程调度、短程调度 进程调度决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。进程调度是最基本的调度，任何操作系统都有进程调度。 进程调度可采用两种方式 非抢占式 抢占式 3.1.1 高级、中级和低级调度 非抢占方式(Non-preemptive Mode) 在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个： 正在执行的进程执行完毕， 或因发生某事件而不能再继续执行 执行中的进程因提出I/O请求而暂停执行； 在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。 这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式。 3.1.1 高级、中级和低级调度 抢占方式(Preemptive Mode) 抢占的原则有： 优先权原则。 短作业(进程)优先原则。 时间片原则。 3.1.1 高级、中级和低级调度 中级调度(Intermediate-Level Scheduling) 又称中程调度(Medium-Term Scheduling)。 引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。 为此，应使那些暂时不能运行的进程调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。 当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。 3.1.1 高级、中级和低级调度 三级调度 3.1.2 调度队列模型 仅有进程调度的调度队列模型 在分时系统中通常仅设置了进程调度。 系统有一个就绪队列，每个进程运行一个时间片，进程运行一个时间片后如未完成，则被放在就绪队列末尾。 进程运行中因等待某事件（例如申请I/O而等待I/O完成），则需排入阻塞队列，系统因阻塞的原因不同可设几个阻塞队列。 3.1.2 调度队列模型 具有高级和低级调度的调度队列模型 多道批处理系统中，一般处理机管理设置作业和进程两级调度。它比第一个模型增加了高级调度。模型增加了在磁盘的作业后备队列，作业调度的任务是从作业后备队列中选一个作业为它创建至少一个进程，并分配资源，将它排入内存进程就绪队列末尾。 3.1.2 调度队列模型 同时具有三级调度的调度队列模型 3.1.3 选择的准则 面向用户的准则 周转时间短 它是评价批处理系统的重要性能指标。作业周转时间Ti是指从作业提交给系统开始，到作业完成为止的这段时间间隔。 3.1.3 选择的准则 面向用户的准则 响应时间快 响应时间是评价分时系统的性能指标。响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。 截止时间的保证 它是用来评价实时系统的重要指标，截止时间是某任务必须执行的最迟时间，或完成的最迟时间。 优先权准则 在选择批处理、分