第7课作业调度算法

1、内容回顾：进程和线程间的几点不同 地址空间地址空间：不同进程的地址空间相互独立，进程各线程共享一个地址空间。 通信关系通信关系：不同进程间使用系统提供的进程通信机制；同一进程各线程直接通过访问共享的进程地址空间来实现。 调度切换调度切换：不同进程间切换要花很大开销，同一进程的线程切换开销很少。 PCB数据程序用户栈系统栈寄存器单线程进程模型进程PCB数据程序用户栈系统栈寄存器TCB用户栈系统栈寄存器TCB用户栈系统栈寄存器TCB线程1线程2线程3进程多线程进程模型(a)(b)内容回顾：用户与操作系统的程序接口操作系统管理了计算机的软硬件资源，当用户要使用这些资源时必须通过操作系统来实现，操作系

2、统通过系统调用命令来响应用户的请求，这就是操作系统提供的程序接口程序接口。 操作系统预先编写了很多不同功能的子程序，这子程序完成相应资源的具体管理，用户在自己的程序里通过调用这些子程序来得到系统提供的相应功能服务。这些子程序就是“系统功系统功能调用程序能调用程序”，简称“系统调用系统调用”。特权指令与非特权指令把CPU的指令分为两类：一类是操作系统和用户都能使用的指令，称为“非特权指令”；一类是只能由操作系统使用的指令，称为“特权指令”。 管态与目态计算机可以执行这些“特权指令”的状态，我们称之为“管态管态”。管态下可以执行包括特权指令在内任何指令。当系统处于只能执行用户自己程序而不能执行特权

3、指令的状态时，我们称之为“目态目态”。CUP处于“管态”还是“目态”由硬件系统自动识别。内容回顾内容回顾 访管指令用户程序在执行的过程中，通过系统提供的访管指令由“目态”转为“管态”，从而实现特殊指令的执行，而达到实现系统调用的目的。访管指令访管指令是一条非特权指令，功能是执行它就会产生一个软中断，促使中央处理机由目态转为管态，进入操作系统 。内容回顾：作业内容回顾：作业作业作业：指用户要求计算机系统做的一个计算问题或一次事务处理的完整过程。从作业提交给系统，到作业运行完毕被撤消，是一个作业的生命期。在这期间，作业随着自己的推进及环境变化，状态也在不断变化。内容回顾：作业的生命期内容回顾：作业

4、的生命期作业的四个基本状态后备作业内容回顾：作业调度内容回顾：作业调度按某种规则从后备作业队列里挑选作业进入内存，参与对处理机的竞争，称为作业调度作业调度，它由作业调度程序作业调度程序完成。所 采用的规则，称作业调度算法作业调度算法。处理机调度处理机调度高级调度（作业调度）低级调度 （进程调度）今日内容 选择作业调度算法要考虑的要素选择作业调度算法要考虑的要素 作业调度原则作业调度原则 衡量作业调度算法优劣的指标衡量作业调度算法优劣的指标 调度算法的详细讲解调度算法的详细讲解 先来先服务作业调度算法先来先服务作业调度算法 短作业优先作业调度算法短作业优先作业调度算法 响应比高者优先作业调度算法

5、响应比高者优先作业调度算法选择作业调度算法要考虑的要素设计目标 作业调度算法要与系统的整体设计目标一致，如批处理系统应考虑的是提高计算机效率和增加系统的吞吐能力；分时系统应考虑的是对用户的请求响应时间；实时系统应考虑信息的准确性以及保证及时响应。选择作业调度算法要考虑的要素 资源利用率 均衡的资源利用率是评价系统性能优劣的重要指标。在选择作业调度算法时，在考虑系统设计目标的前提下，应最大限度地发挥各种资源的效能，注意考虑系统资源的均衡使用，使“I/O繁忙”的作业与“CPU繁忙”的作业搭配调度，例如将科学计算型（CPU型）作业和数据处理型（输入输出型）作业搭配运行就是一种方法。选择作业调度算法要

6、考虑的要素作业的周转时间 设法缩短作业的周转时间以应保证提交的作业在规定的截止时间内完成，提高衡量调度性能的指标 大多数操作系统都采用折中方案，尽量选择算法比较简单的调度算法。作业调度原则作业调度原则 尽可能使后备作业队列中每个作业都得到公平对待，避免一个作业无限期地延迟得不到执行。 使进入内存中的作业均衡地使用系统各种资源，避免出现有的资源空闲，有的资源被争抢的局面。 尽可能提高吞吐能力，在单位时间内为多个作业提供服务。 衡量作业调度算法优劣的指标衡量作业调度算法优劣的指标 CPU利用率利用率好的算法应尽可能地提高CPU利用率。CPU利用率=CPU有效工作时间/CPU总的运行时间 吞吐量吞吐

7、量指单位时间内平均完成的作业数量。吞吐量=完成的作业道数/完成的时间 作业周转时间作业周转时间作业周转时间是指一个作业从提交到完成总共花费的时间作业周转时间=作业完成时间-作业提交时间作业周转时间=作业运行时间+作业等待时间 对于一批n个作业而言，它们的“平均周转时间平均周转时间” T 应该是： T=( T1 + T2 + + Tn ) / n先来先服务作业调度算法先来先服务作业调度算法以作业进入后备队列中的先后次序作业选择作业的依据。也就是说哪个作业在后备队列中等待的时间最长，它就是下次调度选中者。但前提是这个作业的资源需求要得到满足，否则就要被推迟选中例：有3个作业，所需CPU时间如下表所

8、示。按1、2、3的顺序，同时提交给系统，采用先来先服务的作业调度算法。求每个作业的周转时间及它们的平均周转时间。作业作业所需所需CPU时间时间1232433例：有3个作业，所需CPU时间如下表所示。按1、2、3的顺序，同时提交给系统，采用先来先服务的作业调度算法。求每个作业的周转时间及它们的平均周转时间。作业作业所需所需CPU时间时间1232433提交时间提交时间 开始时间开始时间完成时间完成时间周转时间周转时间例：有3个作业，所需CPU时间如下表所示。按1、2、3的顺序，同时提交给系统，采用先来先服务的作业调度算法。求每个作业的周转时间及它们的平均周转时间。作业作业所需所需CPU时间时间12

9、32433提交时间提交时间 开始时间开始时间000完成时间完成时间周转时间周转时间例：有3个作业，所需CPU时间如下表所示。按1、2、3的顺序，同时提交给系统，采用先来先服务的作业调度算法。求每个作业的周转时间及它们的平均周转时间。作业作业所需所需CPU时间时间1232433提交时间提交时间 开始时间开始时间0000完成时间完成时间周转时间周转时间24例：有3个作业，所需CPU时间如下表所示。按1、2、3的顺序，同时提交给系统，采用先来先服务的作业调度算法。求每个作业的周转时间及它们的平均周转时间。作业作业所需所需CPU时间时间1232433提交时间提交时间 开始时间开始时间00002427完

10、成时间完成时间周转时间周转时间242730例：有3个作业，所需CPU时间如下表所示。按1、2、3的顺序，同时提交给系统，采用先来先服务的作业调度算法。求每个作业的周转时间及它们的平均周转时间。作业作业所需所需CPU时间时间1232433提交时间提交时间 开始时间开始时间00002427完成时间完成时间周转时间周转时间242730242730例：有3个作业，所需CPU时间如下表所示。按1、2、3的顺序，同时提交给系统，采用先来先服务的作业调度算法。求每个作业的周转时间及它们的平均周转时间。作业作业所需所需CPU时间时间1232433 开始时间开始时间024完成时间完成时间周转时间周转时间2427

11、3024273024这三个作业的平均周转时间为： T= (T1+T2+T3 ) / 3 = (24+27+30) / 3 = 81 / 3 = 27例：有五个作业如下表所示，采用先来先服务调度算法算出每个例：有五个作业如下表所示，采用先来先服务调度算法算出每个 作业的周转时间作业的周转时间作 业到达时间所需CPU时间18：00628：02238：03748：05358：064例：有五个作业如下表所示，采用先来先服务调度算法算出每个例：有五个作业如下表所示，采用先来先服务调度算法算出每个 作业的周转时间作业的周转时间作 业到达时间所需CPU时间开始时间完成时间周转时间18：00628：02238

12、：03748：05358：064例：有五个作业如下表所示，采用先来先服务调度算法算出每个例：有五个作业如下表所示，采用先来先服务调度算法算出每个 作业的周转时间作业的周转时间作 业到达时间所需CPU时间开始时间完成时间周转时间18：0068：008：0628：02238：03748：05358：064例：有五个作业如下表所示，采用先来先服务调度算法算出每个例：有五个作业如下表所示，采用先来先服务调度算法算出每个 作业的周转时间作业的周转时间作 业到达时间所需CPU时间开始时间完成时间周转时间18：0068：008：0628：0228：068：0838：0378：088：1548：0538：15

13、8：1858：0648：188：22例：有五个作业如下表所示，采用先来先服务调度算法算出每个例：有五个作业如下表所示，采用先来先服务调度算法算出每个 作业的周转时间作业的周转时间作 业到达时间所需CPU时间开始时间完成时间周转时间18：0068：008：06628：0228：068：08638：0378：088：151248：0538：158：181358：0648：188：2216这五个作业的平均周转时间为：（6+6+12+13+16）/5=10.6。短作业优先作业调度算法短作业优先作业调度算法基本思想：要求每个用户对自己作业所需CPU时间做出估计，填入作业说明书。作业调度程序工作时，是从后

14、备作业队列里挑需CPU时间最少、且资源能得到满足的作业进入内存投入运行。 例：有3个作业，所需CPU时间如下表所示。按1、2、3的顺序，同时提交给系统，采用短作业优先的作业调度算法。求每个作业的周转时间及它们的平均周转时间。作业作业所需所需CPU时间时间1232433例：有3个作业，所需CPU时间如下表所示。按1、2、3的顺序，同时提交给系统，采用短作业优先的作业调度算法。求每个作业的周转时间及它们的平均周转时间。作业作业所需所需CPU时间时间1232433提交时间提交时间 开始时间开始时间000完成时间完成时间周转时间周转时间作业作业所需所需CPU时间时间1232433完成时间完成时间周转时

15、间周转时间例：有3个作业，所需CPU时间如下表所示。按1、2、3的顺序，同时提交给系统，采用短作业优先的作业调度算法。求每个作业的周转时间及它们的平均周转时间。作业作业所需所需CPU时间时间1232433提交时间提交时间 开始时间开始时间0000完成时间完成时间周转时间周转时间33作业作业所需所需CPU时间时间1232433完成时间完成时间周转时间周转时间例：有3个作业，所需CPU时间如下表所示。按1、2、3的顺序，同时提交给系统，采用短作业优先的作业调度算法。求每个作业的周转时间及它们的平均周转时间。作业作业所需所需CPU时间时间1232433提交时间提交时间 开始时间开始时间00003完成

16、时间完成时间周转时间周转时间3636作业作业所需所需CPU时间时间1232433完成时间完成时间周转时间周转时间例：有3个作业，所需CPU时间如下表所示。按1、2、3的顺序，同时提交给系统，采用短作业优先的作业调度算法。求每个作业的周转时间及它们的平均周转时间。作业作业所需所需CPU时间时间1232433提交时间提交时间 开始时间开始时间000603完成时间完成时间周转时间周转时间30363036作业作业所需所需CPU时间时间1232433完成时间完成时间周转时间周转时间这三个作业的平均周转时间为： T= (T1+T2+T3 ) / 3 = (30+3+6) / 3 = 13例：有五个作业如下

17、表所示，采用短作业优先调度算法算出每个例：有五个作业如下表所示，采用短作业优先调度算法算出每个 作业的周转时间作业的周转时间作 业到达时间所需CPU时间开始时间完成时间周转时间18：00628：02238：03748：05358：064例：有五个作业如下表所示，采用短作业优先调度算法算出每个例：有五个作业如下表所示，采用短作业优先调度算法算出每个 作业的周转时间作业的周转时间作 业到达时间所需CPU时间开始时间完成时间周转时间18：0068：008：0628：02238：03748：05358：064例：有五个作业如下表所示，采用短作业优先调度算法算出每个例：有五个作业如下表所示，采用短作业优

18、先调度算法算出每个 作业的周转时间作业的周转时间作 业到达时间所需CPU时间开始时间完成时间周转时间18：0068：008：0628：0228：068：0838：03748：05358：064例：有五个作业如下表所示，采用短作业优先调度算法算出每个例：有五个作业如下表所示，采用短作业优先调度算法算出每个 作业的周转时间作业的周转时间作作 业业到达时间到达时间所需所需CPU时间时间开始时间开始时间完成时间完成时间周转时间周转时间18：0068：008：0628：0228：068：0838：0378：158：2248：0538：088：1158：0648：118：15例：有五个作业如下表所示，采用

19、短作业优先调度算法算出每个例：有五个作业如下表所示，采用短作业优先调度算法算出每个 作业的周转时间作业的周转时间作作 业业到达时间到达时间所需所需CPU时间时间开始时间开始时间完成时间完成时间周转时间周转时间18：0068：008：06628：0228：068：08638：0378：158：221948：0538：088：11658：0648：118：159这五个作业的平均周转时间为：（6+6+19+6+9）/5=9.2。响应比高者优先作业调度算法响应比高者优先作业调度算法基本思想：在进行作业调度时，先计算每个作业当时的响应比： 响应比响应比 = ( 已等待时间已等待时间 ) / ( 所需所需CPU时间时间 ) 然后从中挑选出响应比最高的作业作为调度的对象。作业到达时间所需时间A8：005B8：023C8：031D8：042例：有四个作业如下表所示，采用响应比高者例：有四个作业如下表所示，采用响应比高者优先调度算法算出作业的周转时间优先调度算法算出作业的周转时间 在刚开始时，只有作业A，因此先运行作业A。 当A于8：05运行完成时，其它三个作业B、C、D都已到达，按响应比高者优先算法要求，现在要计算这三个作业的响应比。 此时在8:05时状态如下表所示： 作业到达时间所需时间等待时间响应比B8：023C8：031D8：042 此时在8:05时状态如下