《计算机操作系统操作系统第3章.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统操作系统第3章.ppt（76页珍藏版）》请在第壹文秘上搜索。
1、第三章处理机调度与死锁 3.1 处理机调度的层次处理机调度的层次3.2 调度队列模型和调度准则调度队列模型和调度准则3.3 调度算法调度算法3.4 实时调度实时调度 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件3.6 预防死锁的方法预防死锁的方法3.7 死锁的检测与解除死锁的检测与解除 3.1处理机调度的层次处理机调度的层次 3.1.13.1.1高级调度高级调度1 1作业和作业步作业和作业步(1) 作业作业(Job)。不仅包含通常的。不仅包含通常的程序程序和和数据数据，而，而且还配有一份且还配有一份作业说明书作业说明书，系统根据说明书来对程，系统根据说明书来对程序的运行进行控制。序
2、的运行进行控制。 批处理系统以作业为单位从外存调入内存。批处理系统以作业为单位从外存调入内存。 (2) (2) 作业步作业步(Job Step)(Job Step)。每个作业的相对。每个作业的相对独立、又相互关联的加工步骤。独立、又相互关联的加工步骤。例：例：一个典型的作业：一个典型的作业： “编译编译”作业步；作业步； “连结装配连结装配”作业步；作业步； “运行运行”作业步。作业步。2 2作业控制块作业控制块JCB(Job Control Block)JCB(Job Control Block)作业控制块，保存系统对作业进行管理和调度作业控制块，保存系统对作业进行管理和调度所需的全部信息：
3、所需的全部信息： 作业标识、用户名称、用户帐户、作业类型作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、繁忙型、I/O 繁忙型、批量型、终端型繁忙型、批量型、终端型)、作业、作业状态、调度信息状态、调度信息(优先级、作业已运行时间优先级、作业已运行时间)、资源需、资源需求求(预计运行时间、要求内存大小、要求预计运行时间、要求内存大小、要求I/O设备的类设备的类型和数量等型和数量等)、进入系统时间、开始处理时间、作业、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。完成时间、作业退出时间、资源使用情况等。 3 3作业调度作业调度根据作业控制块中的信息，审查系统能否
4、满足根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。程插入就绪队列，准备执行。3.1.2 3.1.2 低级调度低级调度调度的对象是进程调度的对象是进程( (或内核级线程或内核级线程) )。1 1低级调度的功能低级调度的功能(1) 保存处理机的现场信息。保存处理机的现场信息。(2) 按某种算法选取进程。按某种算法选取进
5、程。 (3) 把处理器分配给进程。把处理器分配给进程。2 2进程调度中的三个基本机制进程调度中的三个基本机制(1) (1) 排队器：就绪进程排成一个或多个队列。排队器：就绪进程排成一个或多个队列。(2) 分派器分派器: :从就绪队列中取出所选定进程，进从就绪队列中取出所选定进程，进行上下文切换，将处理机分配给行上下文切换，将处理机分配给所选进程所选进程。 (3) 上下文切换机制（两次）：上下文切换机制（两次）： A. 保存当前进程上下文，装入分派器程序上下文，保存当前进程上下文，装入分派器程序上下文，使分派器程序运行；使分派器程序运行； B. 移出分派程序，把新选进程的移出分派程序，把新选进程
6、的CPU现场信息装现场信息装入到处理机的各个相应寄存器中。入到处理机的各个相应寄存器中。 3 3进程调度方式进程调度方式1) 1) 非抢占方式非抢占方式(Nonpreemptive Mode)(Nonpreemptive Mode)把处理机分配给某进程后，直至该进程完成，把处理机分配给某进程后，直至该进程完成，自愿释放处理机，或发生某事件而被阻塞时，才再自愿释放处理机，或发生某事件而被阻塞时，才再把处理机分配给其他进程。把处理机分配给其他进程。 优点优点:实现简单，系统开销小。实现简单，系统开销小。 缺点：难以满足紧急任务的要求，可能造成难以缺点：难以满足紧急任务的要求，可能造成难以预料的后果
7、。预料的后果。2) 2) 抢占方式抢占方式(Preemptive Mode)(Preemptive Mode)优点：可防止一个长进程长时间占用处理机，优点：可防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的实时任务的需求。对响应时间有着较严格要求的实时任务的需求。 缺点：开销较大。缺点：开销较大。实现原则：实现原则： (1) 优先权原则。优先权原则。(2) 短作业短作业(进程进程)优先原则。优先原则。(3) 时间片原则。时间片原则。3.1.3 3.1.3 中级调度中级调度暂时不能运行的进程不再占用
8、宝贵的内存资源，暂时不能运行的进程不再占用宝贵的内存资源，调至外存上去等待，此时进程状态称为调至外存上去等待，此时进程状态称为就绪驻外存状就绪驻外存状态或挂起状态态或挂起状态。即是存储器管理中的对换功能（第四。即是存储器管理中的对换功能（第四章）。章）。 进程调度的运行频率最高，是短程调度。进程调度的运行频率最高，是短程调度。作业调度周期较长（几分钟一次），是长程调度。作业调度周期较长（几分钟一次），是长程调度。中级调度运行频率介于上述两种之间，称为中程调度。中级调度运行频率介于上述两种之间，称为中程调度。仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型 就 绪 队 列阻 塞 队 列进
9、程调度CPU进程完成等待事件交互用户事件出现时间片完3.2 调度队列模型和调度准则调度队列模型和调度准则 2具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 (1) 常用的就绪队列形式是优先权队列。常用的就绪队列形式是优先权队列。(2) 设置多个阻塞队列。每个队列对应于某一种进程设置多个阻塞队列。每个队列对应于某一种进程阻塞事件。阻塞事件。 具有高、低两级调度的调度队列模型具有高、低两级调度的调度队列模型 就 绪 队 列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现等待事件n事件n出现后 备 队 列3 3同时具有三级调度的调度队列模型同时具有三级
10、调度的调度队列模型OS中引入中级调度，把进程就绪状态分为内存中引入中级调度，把进程就绪状态分为内存就绪就绪(表示进程在内存中就绪表示进程在内存中就绪)和外存就绪和外存就绪(进程在外进程在外存中就绪存中就绪)。把阻塞状态进一步分成内存阻塞和外存。把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。阻塞两种状态。具有三级调度时的调度队列模型具有三级调度时的调度队列模型 就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现3.2.23.2.2选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则1 1面
11、向用户的准则面向用户的准则 (1) (1) 周转时间短。周转时间，是指从作业被提交周转时间短。周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔给系统开始，到作业完成为止的这段时间间隔( (称为称为作业周转时间作业周转时间) )。它包括四部分时间：作业在外存后。它包括四部分时间：作业在外存后备队列上等待备队列上等待(作业作业)调度的时间，进程在就绪队列上调度的时间，进程在就绪队列上等待进程调度的时间，进程在等待进程调度的时间，进程在CPU上执行的时间，上执行的时间，以及进程等待以及进程等待I/O操作完成的时间。操作完成的时间。系统平均周转时间系统平均周转时间: :niiTnT1
12、1带权周转时间带权周转时间: : W = T/Ts T:作业周转时间作业周转时间 Ts:系统为作业提供服务的时间系统为作业提供服务的时间平均带权周转时间：平均带权周转时间： niiTTnW1s1(2) 响应时间快。响应时间，是从用户通过键盘响应时间快。响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的提交一个请求开始，直至系统首次产生响应为止的时间。它包括三部分时间：从键盘输入的请求信息时间。它包括三部分时间：从键盘输入的请求信息传送到处理机的时间，处理机对请求信息进行处理传送到处理机的时间，处理机对请求信息进行处理的时间，以及将所形成的响应信息回送到终端显示的时间，以及将
13、所形成的响应信息回送到终端显示器的时间。器的时间。 (3) 截止时间的保证。截止时间，是指某任务截止时间的保证。截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。必须开始执行的最迟时间，或必须完成的最迟时间。（实时系统）。（实时系统）。(4) 优先权准则。优先权准则。2 2面向系统的准则面向系统的准则 (1) 系统吞吐量高。吞吐量是指在单位时间内系系统吞吐量高。吞吐量是指在单位时间内系统所完成的作业数。统所完成的作业数。 (2) 处理机利用率好。（大、中型多用户系统）。处理机利用率好。（大、中型多用户系统）。对于单用户微机或某些实时系统，此准则不重要。对于单用户微机或某些实时系
14、统，此准则不重要。 (3) 各类资源的平衡利用。各类资源的平衡利用。3.2.1先来先服务和短作业先来先服务和短作业(进程进程)优先调度算法优先调度算法1先来先服务调度算法先来先服务调度算法算法既可用于作业调度，也可用于进程调度。算法既可用于作业调度，也可用于进程调度。 FCFS算法比较有利于长作业算法比较有利于长作业(进程进程)，而不利于短作业，而不利于短作业(进程进程)。进程名 到达时间 服务时间 开始执行时间 完成时间 周转时间 带权周 转时间 A 0 1 0 1 1 1 B 1 100 1 101 100 1 C 2 1 101 102 100 100 D 3 100 102 202 1
15、99 1.99 3.3调调 度度 算算 法法 FCFS调度算法有利于调度算法有利于CPU繁忙型的作业，而不利于繁忙型的作业，而不利于I/O繁忙型的作业繁忙型的作业(进程进程)。2 2短作业短作业( (进程进程) )优先调度算法优先调度算法(SJF/SJP)SJF:从后备队列中选择一个或若干个估计从后备队列中选择一个或若干个估计运行时间最短的作业调入内存运行。运行时间最短的作业调入内存运行。 SJP:从就绪队列中选出一个估计运行时间从就绪队列中选出一个估计运行时间最短的进程，分配处理机。最短的进程，分配处理机。 FCFS和和SJF调度算法的性能调度算法的性能SJF调度算法能有效地降低作业的平均等
16、待时间，调度算法能有效地降低作业的平均等待时间，提高系统吞吐量。提高系统吞吐量。 进程名 A B C D E 平 均 到达时间 0 1 2 3 4 作业 情况 调度 算法 服务时间 4 3 5 2 4 完成时间 4 7 12 14 18 周转时间 4 6 10 11 14 9 FCFS (a) 带权周转时间 1 2 2 5.5 3.5 2.8 完成时间 4 9 18 6 13 周转时间 4 8 16 3 9 8 SJF (b) 带权周转时间 1 2.67 3.1 1.5 2.25 2.1 SJ(P)FSJ(P)F调度算法缺点：调度算法缺点：(1) (1) 由于调度程序总是优先调度那些由于调度程序总是优先调度那些( (即使是后即使是后进来的进来的) )短作业短作业( (进程进程) )，将导致长作业，将导致长作业( (进程进程) )长期不长期不被调度。被调度。(2) (2) 不能保证紧迫性作业不能保证紧迫性作业( (进程进程) )会被及时处理。会被及时处理。(3) (3) 由于作业由于作业( (进程进程) )的长短只是根据用户所提供的长短只是根据用户所提供的估计执行时间而定的，而用户又可能
