windows操作系统课件 第3章调度.ppt

第三章 进程和处理器管理 处理机调度的四个层次 作业与进程的关系 作业可被看作是用户向计算机提交任务的任务实体，例如一次计算、一个控制过程等。 进程则是计算机为了完成用户任务实体而设置的执行实体，是系统分配资源的基本单位。计算机要完成一个任务实体，必须要有一个以上的执行实体。也就是说，一个作业总是由一个以上的多个进程组成的。 调度目标： 一般来说，调度目标主要是以下四点 (1)公平合理：对所有作业应该是公平合理的； (2)高利用率：应使设备有高的利用率， (3)吞吐量大：每天执行尽可能多的作业； (4)响应迅速：有快的响应时间。 任一调度算法要想同时满足上述目标是不可能的： 1）如要想吞吐量大，调度算法就应选择那些估计执行时间短的作业。这对那些估计执行时间长的作业不公平，并且可能使它们的得不到调度执行或响应时间很长。 2）如果考虑的因素过多，调度算法就会变得非常复杂。其结果是系统开销增加，资源利用率下降。 衡量调度策略的常用指标 周转时间：指将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间。 吞吐量：指在给定的时间内，一个计算机系统所完成的总工作量(作业数)。 响应时间：指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需要的时间。 设备利用率：输入输出设备的使用情况，在有些要求I／O处理能力强(如管理信息系统)的系统中，高的设备利用率也是一个衡量调度策略好坏的重要指标。 周转时间：作业i的周转时间Ti为 Ti＝Tei-Tsi其中Tei为作业i的完成时间；Tsi为作业的提交时间。 N个作业的平均周转时间T=（T1 + T2 + … + TN）/N 带权周转时间：周转时间Ti可分解为两部分，即Ti＝Twi+Tri这里，Twi主要指作业i由后备状态到执行状态的等待时间，它不包括作业进入执行状态后的等待时间；Tri指作业i的执行时间。带权周转时间是作业周转时间与作业执行时间的比：Wi＝Ti／Tri N个作业的平均带权周转时间W＝(W1 + W2 + … + WN)/N 常用作业调度算法 1 先来先服务（First come first serve,FCFS）方式： 执行时间很短的作业是在那些长作业的后面到达系统的话，则必须等待很长时间 2 短作业优先(Shortest Job first，SJF)方式 选择那些估计需要执行时间最短的作业投入执行，为它们创建进程和分配资源。有可能使得那些长作业永远得不到调度执行 3 响应比高者优先（ Highest Response-ratio Next ，HRN)方式 响应比R＝(W+T)／T＝1+W／TT：为估计需要的执行时间W：在后备状态队列中的等待时间T+W:响应时间 作业调度时，系统计算每个作业的响应比，选择R最大者投入执行。 长作业有机会获得调度执行(随着它等待时间的增加，W／T也就随着增加)。 HRN的吞吐量小于SJF，由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法。 系统开销增加：每次调度前要计算响应比。 HRN是对FCFS方式和SJF方式的一种综合平衡。 时间片轮转程序调度算法(RR） 把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行 本算法主要用于微观调度，说明怎样并发运行，即切换的方式；设计目标是提高资源利用率。 其基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率； 时间片长度的确定 时间片长度变化的影响 过长－退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。 过短－用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。 时间片长度的影响因素： 就绪进程的数目：数目越多，时间片越小（当响应时间一定时） 系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。 多队列反馈调度算法 例题 在一单道批处理系统中，一组作业的提交时刻和运行时间如表所示 试计算以下三种作业调度算法的平均周转时间T和平均带权周转时间W 先来先服务 短作业优先算法 HRN 例2 假设作业在时刻0以1、2、3、4、5的顺序到达。 用FCFS\RR\SJF\非剥夺优先级法 FCFS RR SJF 非剥夺优先级 线性优先级调度策略 新创建的进程按FCFS方式排成就绪队列，而其它已得到过时间片服务的进程也按FCFS方式排成另一个就绪队列或称享受服务队列 对于这两个不同队列中的进程，设新创建进程进入新创建进程就绪队列时的优先级P为0，进入就绪