操作系统,处理机调度与死锁教案.

《操作系统,处理机调度与死锁教案.》由会员分享，可在线阅读，更多相关《操作系统,处理机调度与死锁教案.（102页珍藏版）》请在金锄头文库上搜索。

1、Operating SystemPage 1* Operating SystemPage 2* 第三章第三章 处理机调度与死锁处理机调度与死锁 q重点 v掌握进程调度算法，各适用于何种情况 v理解常用的几种实时调度算法 v理解产生死锁的原因 v掌握银行家算法避免死锁 q难点 v多道程序设计中的各种调度算法 v响应比高者优先调度算法的计算过程 v银行家算法 Operating SystemPage 3* 第三章第三章 处理机调度与死锁处理机调度与死锁 q知识点 v处理机调度及调度算法 v多处理机环境下的进程（线程）调度方式 v产生死锁的原因和必要条件 v预防死锁的方法，死锁的检测与解除 v银行家

2、算法 Operating SystemPage 4* 第三章第三章 处理机调度与死锁处理机调度与死锁 q处理机是计算机系统中的重要资源 q在多道程序环境下，进程数目通常多于处 理机的数目 q系统必须按一定方法动态地把处理机分配 给就绪队列中的一个进程 q处理机利用率和系统性能（吞吐量、响应 时间）在很大程度上取决于处理机调度 分配处理机的任务是由处理机调度程序完 成的。它是操作系统设计的中心问题之一 。 WHAT：按什么原则分配CPU进程调度算法 WHEN：何时分配CPU 进程调度的时机 HOW：如何分配CPU CPU调度过程（进程 的上下文切换） Operating SystemPage 5

3、* 第三章第三章 处理机调度与死锁处理机调度与死锁 q 处理机调度的层次和调度算法的目标 q 作业与作业调度 q 进程调度 q 实时调度 q 死锁概述 q 预防死锁 q 避免死锁 q 死锁的检测与解除 Operating SystemPage 6* 处理机调度的基本概念处理机调度的基本概念 q作业是用户在一次解题或一个事务处理过 程中要求计算机系统所做工作的集合，包 括用户程序、所需的数据及命令等 q作业的状态：一个作业进入系统到运行结 束，一般需要经历收容、运行、完成三个 阶段，与之相对应的是作业的三种状态 v后备状态 v运行状态 v完成状态 Operating SystemPage 7*

4、运行状态 处理机调度的基本概念处理机调度的基本概念 后备状态 完成状态 就绪 阻塞 执行 I/O完成I/O请求 时间片完 作业 注册 作业 调度 进程 调度 终止 作业 q作业状态间转换 Operating SystemPage 8* 3.1.1 处理机调度的层次 1. 高级调度(High Scheduling) 2. 低级调度(Low Level Scheduling) 3. 中级调度(Intermediate-Level Scheduling) 处理机调度的层次和调度算法的目标处理机调度的层次和调度算法的目标 Operating SystemPage 9* 高级、中级和低级调度高级、中级和

5、低级调度 q高级调度(High Scheduling) 作业调度或长程调度（Long-Term Scheduling） v主要任务是按一定的原则对外存上处于后备 状态的作业进行选择，给选中的作业分配内 存、输入/输出设备等必要的资源，并建立相 应的进程，放入就绪队列，以使该作业的进 程获得竞争处理机的权利 v也称为接纳调度（Admission Scheduling） v高级调度的时间尺度通常是分钟、小时或天 Operating SystemPage 10* 高级、中级和低级调度高级、中级和低级调度 在每次作业调度时，须决定： v接纳多少个作业 即允许多少个作业同时在内存中运行，取决于多 道程序

6、度（Degree of Multiprogramming） 作业太多 服务质量下降 作业太少 资源利用率低 v接纳哪些作业 取决于作业调度算法 先来先服务 短作业优先 作业优先权调度 响应比调度 周转时间太长 系统吞吐量太低 适当的折衷 多道程序度多道程序度：即允许多少个作业同时在内存中运行。 周转时间周转时间：从作业被提交给系统开始，到作业完成为 止的这段时间间隔。 吞吐量吞吐量：是指在单位时间内系统所完成的作业数。 Operating SystemPage 11* 高级、中级和低级调度高级、中级和低级调度 q 低级调度 进程调度或短程调度（Short-Term Scheduling） v主

7、要任务是按照某种策略和方法选取 一个处于就绪状态的进程，将处理机 分配给它 v常见的低级调度有非抢占式和抢占式 两种 v低级调度的时间尺度通常是毫秒级的 。由于低级调度算法的频繁使用，要 求在实现时做到高效 Operating SystemPage 12* 进程调度的任务进程调度的任务 q 进程调度的任务 是控制、协调进程对CPU的竞争, 即按一定的调度算法从就绪队列中选 中一个进程，把CPU的使用权交给被选 中的进程 Operating SystemPage 13* 进程调度方式进程调度方式 q 非抢占方式(Non-preemptive Mode) q 抢占方式(Preemptive Mod

8、e) Operating SystemPage 14* 进程调度方式进程调度方式 q 非抢占方式(Non-preemptive Mode) 当某一进程正在处理机上执行时，即使有某个更 为重要或紧迫的进程进入就绪队列，该进程仍继 续执行，直到其完成或发生某种事件而进入完成 或阻塞状态时，才把处理机分配给更为重要或紧 迫的进程 v引起进程调度的因素 正在执行的进程执行完毕， 或因发生某事 件而不能再继续执行 执行中的进程因提出I/O请求而暂停执行； 在进程通信或同步过程中执行了某种原语 操作，如wait、Block、Wakeup原语 优点：算法简单， 系统开销小 缺点：紧急任务不 能及时响应；短进

9、 程到达要等待长进 程运行结束 Operating SystemPage 15* 进程调度方式进程调度方式 q 抢占方式(Preemptive Mode) 当某一进程正在处理机上执行时，若有某个 更为重要或紧迫的进程进入就绪队列，则立即暂 停正在执行的进程，将处理机分配给这个更为重 要或紧迫的进程 抢占式调度主要有以下原则 优先权原则 允许高优先权的新到进程抢 占当前进程的处理机 短作业(进程)优先原则允许执行时间短 的新到进程抢占当前进程的处理机 时间片原则 时间片用完后停止执行， 重新进行调度，适用于分时系统 优点：适于时间要 求严格的实时系统 缺点：调度算法复 杂，系统开销大 Opera

10、ting SystemPage 16* 高级、中级和低级调度高级、中级和低级调度 q 中级调度(Intermediate-Level Scheduling) v又称为内存调度 v引入目的是为了提高内存利用率和系统吞 吐量。使那些暂时不能运行的进程不再占 用宝贵的内存资源，而将它们调至外存上 去等待 v主要任务是按照给定的原则和策略，将处 于外存对换区中的重又具备运行条件的就 绪进程调入内存，或将处于内存就绪状态 或内存阻塞状态的进程交换到外存对换区 Operating SystemPage 17* 3.1.2 处理机调度算法的目标 q 处理机调度算法的共同目标 v资源利用率 为提高系统的资源利

11、用率，应使系统中的处理机和其它所 有资源尽可能地保持忙碌状态。 CPU的利用率=CPU有效工作时间/（CPU有效工作时间+CPU空 闲等待时间） v公平性。指应使诸进程都获得合理的CPU时间，不会发生进程 饥饿现象。对相同类型的进程应获得相同的服务，对于不同类 型的进程，由于其紧急程度或重要性的不同，则应提供不同的 服务。 v平衡性。尽可能保持系统资源使用的平衡性，使内存、外存和 I/O设备的利用率高 v策略强制执行。对所制订的策略其中包括安全策略，只要需要 ，必须予以准确地执行，即使会造成某些工作的延迟也要执行 。 Operating SystemPage 18* (1) 平均周转时间短。

12、(2) 系统吞吐量高。 (3) 处理机利用率高。 3.1.2 处理机调度算法的目标 q 批处理系统的目标 Operating SystemPage 19* 周转时间是指从作业被提交给系统开始，到作业完成为止 的这段时间间隔。由四部分组成： 作业在外存后备队列上等待（作业）调度的时间 进程在就绪队列上等待进程调度的时间 进程在CPU上执行的时间 进程等待I/O操作完成的时间。 后3项是在一个作业的整个处理过程中，可能发生多次。 3.1.2 处理机调度算法的目标 q 周转时间 Operating SystemPage 20* v周转时间短 平均周转时间 带权周转时间：进程（或作业）的周转时 间T与

13、系统为它提供服务的时间TS之比，即 W=T/TS 。而平均带权周转时间则可表示为: 3.1.2 处理机调度算法的目标 Operating SystemPage 21* v系统吞吐量高 吞吐量指单位时间内系统所完成的作业数 作业调度的方式和算法对吞吐量的大小有较大影响 v处理机利用率高 对于大、中型计算机，CPU价格十分昂贵，致使处理机的 利用率成为衡量系统性能的十分重要的指标。而调度方 式和算法对处理机的利用率起着十分重要的作用。如果 单纯是为使处理机利用率高，应尽量多的选择计算量大 的作业运行。这些要求之间存在一定的矛盾。 3.1.2 处理机调度算法的目标 Operating SystemP

14、age 22* 3.1.2 处理机调度算法的目标 q 分时系统的目标 v响应时间快 响应时间是指从用户通过键盘提交一个请求开始， 直至系统中首次产生响应为止的时间 包括三部分时间：一是请求信息从键盘输入开始， 直到将其传送到处理机的时间；二是处理机对请求 信息进行处理的时间；三是将所形成的响应信息回 送到终端显示器的时间。 v均衡性 用户对响应时间的要求并非完全相同。对较复杂任 务的响应时间允许较长，而对简单任务的响应时间 要短。均衡性是指系统响应时间的快慢应与用户所 请求服务的复杂性相适应。 Operating SystemPage 23* q实时系统的目标 v截止时间保证 截止时间是指某任

15、务必须开始执行的最迟时 间或必须完成的最迟时间 截止时间是实时系统中的重要指标 可预测性。在实时系统中，可预测性显 得非常重要。 3.1.2 处理机调度算法的目标 Operating SystemPage 24* 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则 q各种系统主要目标 v 周转时间短 v 响应时间快 v 截止时间保证 批处理系统 分时系统 实时系统 等待时间短 优先权 Operating SystemPage 25* 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则 v等待时间短 等待时间是在就绪队列中等待所花的时间 调度算法并不影响进程运行和执行

16、I/O的时 间量；只影响进程在就绪队列中等待所花费 的时间 v优先权准则 在批处理、实时和分时系统中都可以选择优 先权准则，以便让紧急任务先处理 有时还选择抢占式调度方式 Operating SystemPage 26* 第三章第三章 处理机调度与死锁处理机调度与死锁 q处理机调度的层次和调度算法的目标 q作业与作业调度 q进程调度 q 实时调度 q 死锁概述 q 预防死锁 q 避免死锁 q 死锁的检测与解除 Operating SystemPage 27* 作业与作业调度作业与作业调度 q在OS中调度的实质是一种资源分配，因而 调度算法是指：根据系统的资源分配策略 所规定的资源分配算法 q问题提出 q如何制定分配策略：对不同的系统和系统 目标，通常采用不同的算法，如短作业优 先，时间片轮转等 q有些算法适用于作业调度，有些适用于