李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 第7讲 处理机调度与死锁(1) 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 1/

处理机调度与死锁 教学目标 教学内容 处理机调度的层次 理解处理机调度的层次； 理解调度队列模型和选择调度方式和算法的准则； 掌握先来先服务、短作业（进程）优先、时间片轮转和优 先权调度算法； 理解多级反馈队列调度算法； 教学内容 处理机调度的层次 调度队列模型和调度准则 调度算法 计算机科学与技术系 信息与教育技术中心 2/

复习 P、V操作 进程通信的类型 信箱类型 通信链路 进程与线路的比较 3/

处理机调度的层次 高级、中级和低级调度 高级调度 根据某种算法，把外存上处于后备队列中的那些作业调入内存。 作业：包括程序、数据以及作业说明书 作业步：在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果 ，其中每一个加工步骤称为一个作业步。 作业流 作业控制块 计算机科学与技术系 信息与教育技术中心 4/

处理机调度的层次 作业调度 在每次执行作业调度时，都须做出以下两个决定。 根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备对列中选取某些作业调入内存，并为为它们创建进程、分配必要的资源。 在每次执行作业调度时，都须做出以下两个决定。 接纳多少个作业 接纳哪些作业 5/

处理机调度的层次 低级调度 调度对象是进程（或内核级线程） 用于决定就绪队列中的哪个进程（或内核级线程）应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。 功能 保存处理机现场信息 按某种算法选取进程 把处理器分配给进程 进程调度中的三个基本机制 排队器、分配器、上下文切换机制 6/

处理机调度的层次 进程调度的方式 非抢占方式 引起进程调度的因素 优点：实现简单、系统开销小 缺点：难以满足紧急任务 抢占方式 优点：防止进程长时间占用处理机，满足实时任务的需求等。 缺点：系统开销大 抢占调度的原则 优先权原则、短作业（进程）优先原则、时间片原则 7/

处理机调度的层次 中级调度 引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。 8/

调度队列模型和调度准则 调度队列模型 仅有进程调度的调度队列模型 图 3 - 1 仅具有进程调度的调度队列模型 9/

调度队列模型和调度准则 具有高级和低级调度的调度队列模型 图 3-2 具有高、低两级调度的调度队列模型 10/

调度队列模型和调度准则 图 3-2 示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面。 就绪队列的形式。 设置多个阻塞队列。 11/

调度队列模型和调度准则 同时具有三级调度的调度队列模型 图 3-3 具有三级调度的调度队列模型 12/

调度队列模型和调度准则 选择调度方式和调度算法的若干准则 面向用户的准则 周转时间短 是指从作业被提交给系统开始,到作业完成为止的这段时间。其包括四个部分： (1)作业在外存后备队列上等待调度的时间； (2)进程在就绪队列上等待进程调度的时间； (3)进程在CPU上执行的时间； (4)进程等待I/O操作完成的时间.其中后三项在一个作业的整个处理过程中，可能发生多次。 13/

调度队列模型和调度准则 平均周转时间 可把平均周转时间描述为： 作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为： 14/

调度队列模型和调度准则 截止时间的保证 优先权准则 响应时间快 响应时间：从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者，直到屏幕上显示出结果为止的一段时间间隔。 截止时间的保证 截止时间：是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。 优先权准则 15/

调度队列模型和调度准则 面向系统的准则 系统吞吐量高 吞吐量：单位时间内系统所完成的作业数。 处理机利用率好 各类资源的平衡利用 16/

调 度 算 法 调度算法是指根据系统的资源分配策略所规定的资源分配算法。 常用的调度算法（作业、进程） 先来先服务调度算法 17/

调 度 算 法 18/

调 度 算 法 图 3-4 FCFS和SJF调度算法的性能 19/

调 度 算 法 短作业(进程)优先调度算法 短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。 SJ(P)F调度算法也存在不容忽视的缺点 该算法对长作业不利 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。 无法实现人--- 机交互 20/

小结 处理机调度的层次 调度队列模型和调度准则 调度算法 21/

作业 P118 1,8,10,12 分别使用FCFS和SPF算法求出以下进程的开始执行时间，完成时间，周转时间以及带权周转时间。 进程名 到达时间 服务时间 开始执行时间 完成时间 周转时间 带权周转时间 A 10 B 2 4 C 3 6 D 5 1 22/

作业 当时间片q=1和q=3时，分别使用时间片轮转算法求出以下进程的开始执行时间，完成时间，周转时间以及带权周转时间。 进程名 到达时间 服务时间 开始执行时间 完成时间 周转时间 带权周转时间 A 3 B 1 4 C 2 5 D 23/

作业 使用非抢占优先权调度算法求出以下进程的开始执行时间，完成时间，周转时间以及带权周转时间。 进程名 到达时间 服务时间 优先权 A 3 2   B 1 4 C 5 D 24/