第四章-处理器调度

1、第第 4 4 章章 处理器调度的类型处理器调度的类型v处理器调度的目标是以满足系统目标（如响应时间、处理器调度的目标是以满足系统目标（如响应时间、吞吐率、处理器效率）的方式，把进程指定到一个吞吐率、处理器效率）的方式，把进程指定到一个处理器或多个处理器中执行。处理器或多个处理器中执行。v长程调度长程调度 决定加入到待执行的进程池中；决定加入到待执行的进程池中；v中程调度中程调度 决定加入到部分或全部在主存中的进程集合中；决定加入到部分或全部在主存中的进程集合中；v短程调度短程调度 决定哪一个可用进程将被处理器执行；决定哪一个可用进程将被处理器执行；长程调度长程调度v 长程调度器决定哪一个程序可

2、以进入到系统中被处理，因此，长程调度器决定哪一个程序可以进入到系统中被处理，因此，它可以控制系统并发度。一旦允许进入，一个作业或用户程它可以控制系统并发度。一旦允许进入，一个作业或用户程序就成为一个进程，并被添加到供短程调度器使用的队列中。序就成为一个进程，并被添加到供短程调度器使用的队列中。在某些系统中，一个新近创建的进程开始处于被换出状态。在某些系统中，一个新近创建的进程开始处于被换出状态。在这种情况下，它被添加到供中程调度器使用的队列中。在这种情况下，它被添加到供中程调度器使用的队列中。v 在批处理系统中（或是通用操作系统中的批处理部分），新在批处理系统中（或是通用操作系统中的批处理部分

3、），新提交的作业被发送到磁盘，并保存在一个批处理队列中。长提交的作业被发送到磁盘，并保存在一个批处理队列中。长程调度器运行时，从队列中创建相应的进程。这里涉及到两程调度器运行时，从队列中创建相应的进程。这里涉及到两个决策。个决策。 调度器必须决定什么时候操作系统能够接纳一个进程或者调度器必须决定什么时候操作系统能够接纳一个进程或者多个进程。多个进程。 调度器必须决定接受哪个作业或哪些作业，并将其转变成调度器必须决定接受哪个作业或哪些作业，并将其转变成进程。进程。v批处理文件是无格式的文本文件，它包含一条或多批处理文件是无格式的文本文件，它包含一条或多条命令。它的文件扩展名为条命令。它的文件扩展

4、名为 .bat.bat 或或 .cmd.cmd。v在命令提示下键入批处理文件的名称，或者双击该在命令提示下键入批处理文件的名称，或者双击该批处理文件，系统就会调用批处理文件，系统就会调用Cmd.exeCmd.exe按照该文件中各按照该文件中各个命令出现的顺序来逐个运行它们。个命令出现的顺序来逐个运行它们。v可以用批处理文件来给系统打补丁、批量植入后门可以用批处理文件来给系统打补丁、批量植入后门程序等。程序等。用批处理实现用批处理实现windows更新自动安装更新自动安装 v http:/ 前两天重装了前两天重装了windows xpwindows xp系统，装完可把我害惨了。系统，装完可把我害

5、惨了。由于我一直不喜欢用由于我一直不喜欢用windowswindows的自动更新，因为它下载速度的自动更新，因为它下载速度实在不敢恭维。就一直用实在不敢恭维。就一直用360safe360safe扫描漏洞，有补丁就装上扫描漏洞，有补丁就装上。感觉也很轻松了。那天装完系统用。感觉也很轻松了。那天装完系统用360safe360safe一扫，居然有一扫，居然有6060多个漏洞。天哪！还好我上次重装系统时已经下了多个漏洞。天哪！还好我上次重装系统时已经下了5050多个多个补丁了。于是就把剩余的几个也赶快下了下来。补丁了。于是就把剩余的几个也赶快下了下来。剩下的就是装补丁了，那可是一个一个点呀。而有的更新

6、装剩下的就是装补丁了，那可是一个一个点呀。而有的更新装上后还会问你要不要立即重启，一不小心忘记勾上上后还会问你要不要立即重启，一不小心忘记勾上“现在不现在不重新启动重新启动”那就惨了，你就等着再欣赏一次开机画面吧。最那就惨了，你就等着再欣赏一次开机画面吧。最后点得我手都酸了，总算装完了。后点得我手都酸了，总算装完了。鉴于这次安装更新的痛苦，这两天我一直在想鉴于这次安装更新的痛苦，这两天我一直在想windowswindows自动自动安装更新时不就说安装更新时不就说“正在安装更新，你可以继续你的工作正在安装更新，你可以继续你的工作”么？可见么？可见windowswindows更新还是支持后台安装的

7、，于是我就准备更新还是支持后台安装的，于是我就准备研究一番。一定要实现更新自动安装。研究一番。一定要实现更新自动安装。v 首先想到了批处理，对，想名字就知道了，因为装完系统后首先想到了批处理，对，想名字就知道了，因为装完系统后有一大堆更新要装，不想一个一个点击安装的话就只能成批有一大堆更新要装，不想一个一个点击安装的话就只能成批处理它们了。处理它们了。闲话少说，切入正题。思路既然有了，于是我就拿了几个更闲话少说，切入正题。思路既然有了，于是我就拿了几个更新包做试验。心想只要在批处理中依次执行这几个更新包不新包做试验。心想只要在批处理中依次执行这几个更新包不就行了么！就行了么！于是写了一个于是写

8、了一个batbat文件文件windowswindows更新自动安装更新自动安装.bat.bat。内容。内容如下：如下：v echooffWindowsXP-KB920213-x86-CHS.exeWindowsXP-KB922760-x86-CHS.exeWindowsXP-KB922819-x86-CHS.exeechowindows更新安装完毕!v 这样就简单的实现了更新的自动安装，但是只是免去了双击这样就简单的实现了更新的自动安装，但是只是免去了双击各个更新包的痛苦，还是要点各个更新包的痛苦，还是要点“我同意我同意”，“确定确定”等按钮等按钮，我能心甘么？就想有没有更好的办法让它真正实现

9、自动安，我能心甘么？就想有没有更好的办法让它真正实现自动安装就好了。于是就想呀想，试呀试。装就好了。于是就想呀想，试呀试。又半个小时过去了，我把那个又半个小时过去了，我把那个batbat文件改来改去的，但是好文件改来改去的，但是好像进展不大。像进展不大。思考思考ingingv 偶然间，在我把一个更新包无意中拖到另一个更新包上的时偶然间，在我把一个更新包无意中拖到另一个更新包上的时候，奇迹出现了。居然弹出了一个帮助对话框。上面清清楚候，奇迹出现了。居然弹出了一个帮助对话框。上面清清楚楚的说明了更新包的各个使用参数。楚的说明了更新包的各个使用参数。v 一眼就看到了一眼就看到了 /quiet (/q

10、uiet (安静模式安静模式) )和和 /norestart (/norestart (安装完安装完成后不要重新启动成后不要重新启动) ) 两个参数，呵呵。要的就是它们。两个参数，呵呵。要的就是它们。Lets go!Lets go!现在把上面的现在把上面的windowswindows更新自动安装更新自动安装.bat .bat 修改一修改一下，并且加上进度提示：下，并且加上进度提示：v echooffecho安装WindowsXP-KB920213-x86-CHS.exeWindowsXP-KB920213-x86-CHS.exe/quiet/norestartecho安装WindowsXP-K

11、B922760-x86-CHS.exeWindowsXP-KB922760-x86-CHS.exe/quiet/norestartecho安装WindowsXP-KB922819-x86-CHS.exeWindowsXP-KB922819-x86-CHS.exe/quiet/norestartechowindows更新安装完毕!v 这下好多了。每次安装一个更新前，先提示安装某某更新。这下好多了。每次安装一个更新前，先提示安装某某更新。v不过新问题也随之而来，你可能早就猜出来了，呵不过新问题也随之而来，你可能早就猜出来了，呵呵。就是更新包多的时候，光是写这个批处理文件呵。就是更新包多的时候，光是

12、写这个批处理文件你就得不停得你就得不停得Ctrl+CCtrl+C，Ctrl+VCtrl+V的的copycopy来来copycopy去，再去，再说每次安装新的更新包时，还要新写一个说每次安装新的更新包时，还要新写一个batbat文件，文件，把各个更新包的名字写进去，这样这个把各个更新包的名字写进去，这样这个batbat文件就显文件就显得很笨拙了。得很笨拙了。v那有没有更好的通用一点的办法呢？那有没有更好的通用一点的办法呢？v 偶然间想到了偶然间想到了forfor命令，它的功能可强大了。如果能用命令，它的功能可强大了。如果能用forfor对对每个更新包进行判断不就可以自动安装更新了么？于是写了每个

13、更新包进行判断不就可以自动安装更新了么？于是写了一个一个batbat文件，主要语句为文件，主要语句为v forfor /r/r %a%a inin ( (* *.exe).exe) dodo %a%a /quiet /quiet /norestart/norestartv 其中其中 /r /r 参数用于遍历整个目录树，参数用于遍历整个目录树，inin ( (* *.exe).exe) 表示遍历当表示遍历当前文件夹的所有前文件夹的所有exeexe文件。运行时通配符文件。运行时通配符%a%a依次用当前文件依次用当前文件夹中的夹中的exeexe文件名代替，这样执行文件名代替，这样执行dodo %a%

14、a /quiet /quiet /norestart/norestart就是依次运行各个更新包了。终于大功告成了。就是依次运行各个更新包了。终于大功告成了。v 关于关于forfor命令的详细解释，有兴趣的朋友请参阅相关的批处命令的详细解释，有兴趣的朋友请参阅相关的批处理资料。或者在理资料。或者在cmdcmd里也可以查到里也可以查到forfor命令的信息，打开命令的信息，打开cmdcmd，输入，输入forfor /? /? ，回车即可。，回车即可。v 终于写完了，以后重装系统后只要写一个这样的终于写完了，以后重装系统后只要写一个这样的batbat文件，文件，放在放在windowswindows更

15、新包所在的文件夹下，执行这个更新包所在的文件夹下，执行这个batbat文件就可文件就可以了。以了。v 这下再也不用一个一个点击更新包安装了，你只要下载更新这下再也不用一个一个点击更新包安装了，你只要下载更新包，其它的都交给包，其它的都交给 “ “windowswindows更新自动安装更新自动安装.bat.bat” 吧。有吧。有了它，你会发现原来生活可以更美的。了它，你会发现原来生活可以更美的。长程调度长程调度处理器调度的类型处理器调度的类型调度和进程状态转换调度和进程状态转换处理器调度的类型处理器调度的类型调度的层次调度的层次长程调度长程调度v 何时创建一个新进程？何时创建一个新进程？ 创建

16、的进程越多，每个进程可执行的时间百分比就越小。创建的进程越多，每个进程可执行的时间百分比就越小。 为了给当前进程集提供满意的服务，长程调度器可能限制为了给当前进程集提供满意的服务，长程调度器可能限制并发度。每当一个作业终止时，调度器可决定增加一个或并发度。每当一个作业终止时，调度器可决定增加一个或多个新作业。多个新作业。 此外，如果处理器的空闲时间片超过了一定的阈值，则会此外，如果处理器的空闲时间片超过了一定的阈值，则会启动长程调度器。启动长程调度器。v 对于分时系统中的交互程序，用户试图连接到系统的动作可对于分时系统中的交互程序，用户试图连接到系统的动作可能产生一个进程创建的请求。分时用户并

17、不是仅仅排队等待，能产生一个进程创建的请求。分时用户并不是仅仅排队等待，直到系统接受它们。相反，操作系统将接受所有的授权用户，直到系统接受它们。相反，操作系统将接受所有的授权用户，直到系统饱和为止。这时，连接请求将会遇到指示系统已经直到系统饱和为止。这时，连接请求将会遇到指示系统已经饱和并要求用户重新尝试的消息。饱和并要求用户重新尝试的消息。短程调度短程调度v 长程调度器执行的频率相对较低，并且仅粗略地决定是否接长程调度器执行的频率相对较低，并且仅粗略地决定是否接受新进程、接受哪一个。受新进程、接受哪一个。v 为进行交换决策，中程调度器执行得略微频繁一些。为进行交换决策，中程调度器执行得略微频

18、繁一些。v 短程调度器，也称为分派器短程调度器，也称为分派器(dispatcher)(dispatcher)，执行得最频繁，执行得最频繁，并且精确地决定下一次执行哪一个进程。并且精确地决定下一次执行哪一个进程。v 当可能导致当前进程阻塞或可能抢占剥夺当前正在运行的进当可能导致当前进程阻塞或可能抢占剥夺当前正在运行的进程的事件发生时，调用短程调度器。这类事件包括程的事件发生时，调用短程调度器。这类事件包括: : 时钟中断时钟中断 I/OI/O中断中断 操作系统调用操作系统调用 信号信号( (如信号量如信号量) )调度准则调度准则v 短程调度的主要目标是优化系统行为的一个或多个方面，它短程调度的主

19、要目标是优化系统行为的一个或多个方面，它根据这个目标来分配处理器时间。根据这个目标来分配处理器时间。v 通常使用的准则可以按两维来分类：通常使用的准则可以按两维来分类： 面向用户的准则面向用户的准则单个用户或进程感知到的系统行为。单个用户或进程感知到的系统行为。例如交互式系统中的响应时间。例如交互式系统中的响应时间。 面向系统的准则面向系统的准则重点是处理器使用的效果和效率。例重点是处理器使用的效果和效率。例如吞吐量，也就是进程完成的速度。该准则的重点是系统如吞吐量，也就是进程完成的速度。该准则的重点是系统的性能，而不是提供给用户的服务。吞吐量是系统管理员的性能，而不是提供给用户的服务。吞吐量

20、是系统管理员所关注的，而不是普通用户所关注的。所关注的，而不是普通用户所关注的。v 面向用户的准则在所有系统中都非常重要，而面向系统的原面向用户的准则在所有系统中都非常重要，而面向系统的原则在单用户系统中的重要性就低一些。在单用户系统中，只则在单用户系统中的重要性就低一些。在单用户系统中，只要系统对用户应用程序的响应时间是可以接受的，则实现处要系统对用户应用程序的响应时间是可以接受的，则实现处理器高利用率或高吞吐量可能并不是很重要。理器高利用率或高吞吐量可能并不是很重要。几种重要的调度准则几种重要的调度准则v 提供较好的响应时间可能需要调度算法在进程间频繁地切提供较好的响应时间可能需要调度算法

21、在进程间频繁地切换，这就增加了系统开销，降低了吞吐量。因此，设计一换，这就增加了系统开销，降低了吞吐量。因此，设计一个调度策略涉及到在互相竞争的各种要求之间进行折中。个调度策略涉及到在互相竞争的各种要求之间进行折中。 进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的程的PCBPCB表中，进程管理模块根据各进程的状态特征和资源需求，将表中，进程管理模块根据各进程的状态特征和资源需求，将各进程的各进程的PCBPCB表排成相应的队列。进程管理模块通过表排成相应的队列。进程管理模块通过PCBPCB变化来掌握系变化来掌握系统中所

22、有进程的执行情况和状态特征，并在适当的时机从就绪队列中统中所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择一个进程占据处理器。选择一个进程占据处理器。 按照一定的策略，选择一个处于就绪状态的进程，使其获得处理器，按照一定的策略，选择一个处于就绪状态的进程，使其获得处理器，得到执行机会。根据不同的系统设计目的，有多种选择策略，如系统得到执行机会。根据不同的系统设计目的，有多种选择策略，如系统开销小的静态优先级调度法，适合于分时系统的轮转法、多级反馈轮开销小的静态优先级调度法，适合于分时系统的轮转法、多级反馈轮转法等。这些选择策略决定了调度算法的性能。转法等。这些选择策略决定了调度算法

23、的性能。 在做上下文切换时，首先要检查是否可以做上下文切换（例如，如果在做上下文切换时，首先要检查是否可以做上下文切换（例如，如果系统正在执行某个不允许中断的原语，就不允许上下文切换）。系统正在执行某个不允许中断的原语，就不允许上下文切换）。进程调度的时机进程调度的时机调度算法调度算法FCFSFCFS最简单的最简单的CPUCPU调度算法调度算法是先到先是先到先服务调度服务调度算法（算法（FCFSFCFS）。）。采用这种采用这种方案，先方案，先请求请求CPUCPU的的进程先分进程先分配到配到CPUCPU。调度算法调度算法FCFSFCFSv FCFSFCFS策略可以用策略可以用FIFOFIFO队列

24、来容易地实现。当一个进程进入到队列来容易地实现。当一个进程进入到就绪队列，其就绪队列，其PCBPCB链接到队列的尾部。当链接到队列的尾部。当CPUCPU空闲时，空闲时，CPUCPU分分配给位于队列头的进程，接着该运行进程从队列中删除。配给位于队列头的进程，接着该运行进程从队列中删除。FCFSFCFS调度的代码编写简单且容易理解。调度的代码编写简单且容易理解。v 采用采用FCFSFCFS策略的平均等待时间通常较长。考虑如下一组进程，策略的平均等待时间通常较长。考虑如下一组进程，它们在时间它们在时间0 0时到达，其时到达，其CPUCPU区间时间长度按区间时间长度按msms计：计：调度算法调度算法F

25、CFSFCFSv 如果进程按如果进程按P1P1、P2P2、P3P3的顺序到达，且按的顺序到达，且按FCFSFCFS顺序处理，那顺序处理，那么得到如下结果：么得到如下结果：v 进程进程P1P1等待等待0ms0ms，进程，进程P2P2等待等待24ms24ms，进程，进程P3P3等待等待27ms27ms。平均。平均等待时间为等待时间为(0+24+27)/3 = 17ms(0+24+27)/3 = 17ms。v 如果进程按如果进程按P2P2、P3P3、P1P1的顺序到达，那么结果为：的顺序到达，那么结果为：v 现在平均等待时间为现在平均等待时间为(6+0+3)/3 = 3ms(6+0+3)/3 = 3

26、ms。调度算法调度算法FCFSFCFSv 因此，采用因此，采用FCFSFCFS策略的平均等待时间通常不是最小，且如果策略的平均等待时间通常不是最小，且如果进程进程CPUCPU区间时间变化很大，平均等待时间也会变化很大。区间时间变化很大，平均等待时间也会变化很大。v FCFSFCFS的另一个难点是相对于受的另一个难点是相对于受I/OI/O限制的进程，它更偏向受限制的进程，它更偏向受处理器限制的进程。处理器限制的进程。v 考虑有一组进程，其中有一个进程大多数时候都使用处理器考虑有一组进程，其中有一个进程大多数时候都使用处理器( (受处理器限制受处理器限制) ) ，还有许多进程大多数时候进行，还有许

27、多进程大多数时候进行I/OI/O操作操作( (受受I/OI/O限制限制) )。如果一个受处理器限制的进程正在运行，则。如果一个受处理器限制的进程正在运行，则所有受所有受I/OI/O限制的进程都必须等待。有一些进程可能在限制的进程都必须等待。有一些进程可能在I/OI/O队队列中列中( (阻塞态阻塞态) ) ，但是当受处理器限制的进程正在执行时，但是当受处理器限制的进程正在执行时，它们可能移回就绪队列。这时，大多数或所有它们可能移回就绪队列。这时，大多数或所有I/OI/O设备都可设备都可能是空闲的，即使它们可能还有工作要做。在当前正在运行能是空闲的，即使它们可能还有工作要做。在当前正在运行的进程离

28、开运行态时，就绪的受的进程离开运行态时，就绪的受I/OI/O限制的进程迅速地通过限制的进程迅速地通过运行态，又阻塞在运行态，又阻塞在I/OI/O事件上。如果受处理器限制的进程也事件上。如果受处理器限制的进程也被阻塞了，则处理器空闲。因此，被阻塞了，则处理器空闲。因此，FCFSFCFS可能导致处理器和可能导致处理器和I/OI/O设备都没有得到充分利用。设备都没有得到充分利用。调度算法调度算法FCFSFCFSv对于单处理器系统，对于单处理器系统， FCFS FCFS自身并不是很有吸引力的自身并不是很有吸引力的选择。但是，它通常与优先级策略相结合，以提供选择。但是，它通常与优先级策略相结合，以提供一

29、种更有效的调度方法。一种更有效的调度方法。v调度器可以维护许多队列，每个优先级一个队列，调度器可以维护许多队列，每个优先级一个队列，每个队列中的调度基于先来先服务原则。每个队列中的调度基于先来先服务原则。最短进程优先法最短进程优先法v在在FCFSFCFS方式中，如果执行时间很短的进程是在长进程之方式中，如果执行时间很短的进程是在长进程之后到达系统，则必须等待长进程执行完成之后才能有机后到达系统，则必须等待长进程执行完成之后才能有机会获得执行。会获得执行。v减少减少FCFSFCFS固有的对长进程的偏向的一种方法是最短进程固有的对长进程的偏向的一种方法是最短进程优先优先(Shortest Proc

30、ess Next ,SPN)(Shortest Process Next ,SPN)策略。这是一个非策略。这是一个非抢占的策略，其原则是下一次选择所需处理时间最短的抢占的策略，其原则是下一次选择所需处理时间最短的进程。因此，短进程将会越过长作业，跳到队列头。进程。因此，短进程将会越过长作业，跳到队列头。v采用这种策略，整体性能有显著提高，但响应时间的差采用这种策略，整体性能有显著提高，但响应时间的差别也增加，可预测性降低。这种方法有可能使长进程永别也增加，可预测性降低。这种方法有可能使长进程永远得不到调度运行的机会。远得不到调度运行的机会。最高响应比优先法最高响应比优先法v 考虑下面比值：考虑

31、下面比值：v其中，其中，R R为响应比，为响应比，w w为等待处理器的时间，为等待处理器的时间，s s为期待的为期待的服务时间。服务时间。v调度规则为：当前进程完成或被阻塞时，选择调度规则为：当前进程完成或被阻塞时，选择R R值最大值最大的就绪进程。该方法非常具有吸引力，因为它说明进程的就绪进程。该方法非常具有吸引力，因为它说明进程的年龄。当偏向短作业时的年龄。当偏向短作业时( (因为小分母产生大比值因为小分母产生大比值) ) ，长进程由于得不到服务的时间不断地增加，从而增大了长进程由于得不到服务的时间不断地增加，从而增大了比值，最终在竞争中胜了短进程。比值，最终在竞争中胜了短进程。调度算法调

32、度算法轮转法轮转法v为了减少在为了减少在FCFS FCFS 策略下短作业的不利情况，一种简策略下短作业的不利情况，一种简单的方法是采用使用基于时钟的抢占策略，最简单单的方法是采用使用基于时钟的抢占策略，最简单的是轮转法。的是轮转法。具有具有8 8个进程的时闾片轮转调度示意图个进程的时闾片轮转调度示意图调度算法调度算法轮转法轮转法v 将就绪的进程排列为一个就绪进程队列。将就绪的进程排列为一个就绪进程队列。v 调度器每次把处理器分配给处在队列首部的进程，并使之运调度器每次把处理器分配给处在队列首部的进程，并使之运行一个规定的时间。行一个规定的时间。v 当时间片结束时，强迫当前进程让出处理器，并把这

33、个进程当时间片结束时，强迫当前进程让出处理器，并把这个进程插入就绪进程队列的尾部，然后把处理器分配给排在队列首插入就绪进程队列的尾部，然后把处理器分配给排在队列首部的进程，并同样使之运行一个规定的时间。部的进程，并同样使之运行一个规定的时间。v 之后再重复上述过程，如此循环轮转地运行系统中的所有就之后再重复上述过程，如此循环轮转地运行系统中的所有就绪进程。绪进程。调度算法调度算法轮转法轮转法v在轮转法中，时间片长度的选取非常重要。时间片长度在轮转法中，时间片长度的选取非常重要。时间片长度的选择会直接影响系统开销和响应时间。的选择会直接影响系统开销和响应时间。 时间片长度过短时间片长度过短调度程

34、序剥夺处理器的次数增多，进调度程序剥夺处理器的次数增多，进程上下文切换次数也大大增加，加重系统开销。程上下文切换次数也大大增加，加重系统开销。 时间片过长时间片过长例如一个时间片能使就绪队列中所需执行例如一个时间片能使就绪队列中所需执行时间最长的进程能执行完毕，则轮转法变成了先来先服务时间最长的进程能执行完毕，则轮转法变成了先来先服务法。法。v 时间片长度的选择是根据系统对响应时间的要求时间片长度的选择是根据系统对响应时间的要求R和就绪队和就绪队列中所允许的最大进程数列中所允许的最大进程数Nmax确定的。可表示为：确定的。可表示为： q = R/ Nmaxv 一种可行的办法是，每当一轮调度开始

35、时，系统便根据就绪一种可行的办法是，每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次队列中已有进程数目计算一次q q值，作为新一轮调度的时间值，作为新一轮调度的时间片。这种方法得到的时间片是随就绪队列中的进程数变化的。片。这种方法得到的时间片是随就绪队列中的进程数变化的。调度算法调度算法优先级法优先级法v系统或用户按照某种原则为作业或进程指定一个优系统或用户按照某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的调度优先权，调先级来表示该作业或进程所享有的调度优先权，调度器总是选择具有较高优先级的进程。度器总是选择具有较高优先级的进程。调度算法调度算法优先级法优先级法v算法

36、的核心算法的核心确定进程的优先级。确定进程的优先级。v确定优先级的方法可以分为两类：静态法和动态法。确定优先级的方法可以分为两类：静态法和动态法。 静态法根据进程的静态特性，在进程开始执行之静态法根据进程的静态特性，在进程开始执行之前就确定它们的优先级，一旦开始执行之后就不前就确定它们的优先级，一旦开始执行之后就不能改变。能改变。 动态法把进程的静态特性和动态特性结合起来，动态法把进程的静态特性和动态特性结合起来，确定进程的优先级，随着进程的执行，优先级不确定进程的优先级，随着进程的执行，优先级不断变化。断变化。调度算法调度算法优先级法优先级法v进程静态优先级确定原则进程静态优先级确定原则按进

37、程类型给予不同的优先按进程类型给予不同的优先级。例如：级。例如： 系统进程具有比用户进程更高的优先级。系统进程具有比用户进程更高的优先级。 频繁使用外围设备的进程具有的优先级要大一些，有利于提高效率；频繁使用外围设备的进程具有的优先级要大一些，有利于提高效率；承担重要计算任务的进程具有的优先级要大一些，有利于尽早得到计承担重要计算任务的进程具有的优先级要大一些，有利于尽早得到计算结果；交互式用户的进程具有的优先级要大一些，可使用户等待响算结果；交互式用户的进程具有的优先级要大一些，可使用户等待响应的时间短一些，等等。应的时间短一些，等等。 将用户进程划分为：将用户进程划分为：I/OI/O限制（

38、繁忙），限制（繁忙），CPUCPU限制，限制，I/OI/O与与CPUCPU均衡等类均衡等类别，对系统进程，也可以根据所要完成的功能划分为不同类型，如调别，对系统进程，也可以根据所要完成的功能划分为不同类型，如调度进程、度进程、I/OI/O进程、中断处理进程、存储管理进程等，这些进程还可进程、中断处理进程、存储管理进程等，这些进程还可以进一步划分和赋予不同的优先级。以进一步划分和赋予不同的优先级。v 给予静态优先级的调度算法实现简单，系统开销小，但由于给予静态优先级的调度算法实现简单，系统开销小，但由于静态优先级一旦确定以后，直到执行结束为止始终保持不变，静态优先级一旦确定以后，直到执行结束为止

39、始终保持不变，因此系统效率较低，调度性能不高。现代操作系统中，如果因此系统效率较低，调度性能不高。现代操作系统中，如果使用优先级调度，则大多采用动态优先级的调度策略。使用优先级调度，则大多采用动态优先级的调度策略。调度算法调度算法优先级法优先级法v进程动态优先级确定原则进程动态优先级确定原则 根据进程占有根据进程占有CPUCPU时间的长短来确定。一个进程占有处时间的长短来确定。一个进程占有处理器的时间越长，则被阻塞之后再次获得调度的优先级理器的时间越长，则被阻塞之后再次获得调度的优先级就越低，反之，获得调度的可能性就会越大。就越低，反之，获得调度的可能性就会越大。 根据就绪进程等待根据就绪进程

40、等待CPUCPU的时间长短来决定。一个就绪进的时间长短来决定。一个就绪进程在就绪队列中等待的时间越长，则它获得的优先级就程在就绪队列中等待的时间越长，则它获得的优先级就越高。越高。 由于动态优先级随时间推移而变化，系统要经常计算各由于动态优先级随时间推移而变化，系统要经常计算各进程的优先级，因此，系统要为此付出一定的开销。进程的优先级，因此，系统要为此付出一定的开销。动态法动态法线性优先级调度策略线性优先级调度策略v 使用轮转法调度进程时，新创建的进程也放入就绪队列末尾使用轮转法调度进程时，新创建的进程也放入就绪队列末尾享受平等的处理器时间片。这对于执行时间长的进程来说是享受平等的处理器时间片

41、。这对于执行时间长的进程来说是不公平的，因为它们需要多个时间片才能完成。不公平的，因为它们需要多个时间片才能完成。v 线性优先级调度策略中，新创建的进程按线性优先级调度策略中，新创建的进程按FCFSFCFS方式排成就绪方式排成就绪队列，而其它已得到过时间片服务的进程也按队列，而其它已得到过时间片服务的进程也按FCFSFCFS方式排成方式排成另一个就绪队列或称享受服务队列。另一个就绪队列或称享受服务队列。线性优先级调度策略线性优先级调度策略v 对于这两个不同队列中的进程，设新创建进程就绪队列中对于这两个不同队列中的进程，设新创建进程就绪队列中进程的优先级进程的优先级P P以下列速率增加：以下列速

42、率增加： P=aP=a* *t (a0)t (a0) 另外，享受服务队列中进程的优先级另外，享受服务队列中进程的优先级P P以下列速率增加：以下列速率增加： P=bP=b* *t (ab0)t (ab0)v 设某一进程在时刻设某一进程在时刻t t1 1 被创建，在时刻被创建，在时刻t t时，该进程的优先时，该进程的优先级为：级为： P(t) = a P(t) = a* *(t-t(t-t1 1) (t) (t1 1 t t t t1 1 ) )；线性优先级调度策略线性优先级调度策略v 当新创建进程就绪队列中的第一个进程的优先级当新创建进程就绪队列中的第一个进程的优先级P(t)= P(t)= a

43、 a* *(t-t(t-t1 1) ) 与享受服务队列中最后一个就绪进程的优先级与享受服务队列中最后一个就绪进程的优先级P(t) P(t) = b= b* *t t 相等时，新创建进程队列中的第一个进程可以转入享相等时，新创建进程队列中的第一个进程可以转入享受服务进程队列，优先级变化曲线如图。受服务进程队列，优先级变化曲线如图。v 设该进程在设该进程在t t1 1时刻转入享受服务队列，则在时刻时刻转入享受服务队列，则在时刻t t，该进程，该进程的优先级变为：的优先级变为： P(t) = a P(t) = a* *(t(t1 1 -t-t1 1)+b)+b* *(t-t(t-t1 1 ) ) (

44、t1 (t1tt2tt2) )v 另外，当享受服务进另外，当享受服务进程队列为空时，新创程队列为空时，新创建进程队列的第一个建进程队列的第一个进程也将移入享受服进程也将移入享受服务进程队列。务进程队列。调度算法调度算法多级反馈轮转法多级反馈轮转法v 调度基于抢占原则调度基于抢占原则( (按时间段按时间段) )并且使用动态优先级机制。并且使用动态优先级机制。 当一个进程第一次进入系统时，它被放置在当一个进程第一次进入系统时，它被放置在RQORQO。 当它第一次被抢占后并返回就绪状态时，它被放置在当它第一次被抢占后并返回就绪状态时，它被放置在RQ1RQ1。 在随后的时间里，每当它被抢占时，就被降级

45、到下一个低优先级队列中。在随后的时间里，每当它被抢占时，就被降级到下一个低优先级队列中。 在每个队列中，除了在优先级最低的队列中之外，都使用简单的在每个队列中，除了在优先级最低的队列中之外，都使用简单的FCFSFCFS机机制。一旦一个进程处于优先级最低的队列中，它就不可能再降低，但是制。一旦一个进程处于优先级最低的队列中，它就不可能再降低，但是会重复地返回该队列，直到运行结束。因此，该队列可按照轮转方式对会重复地返回该队列，直到运行结束。因此，该队列可按照轮转方式对待。待。v一个短进程很快会执行完，不会在就绪队列中降很多级。一个短进程很快会执行完，不会在就绪队列中降很多级。一个长进程会逐级下降

46、。因此，新到的进程和短进程优先一个长进程会逐级下降。因此，新到的进程和短进程优先于老进程和长进程。于老进程和长进程。v 这种方法称为多级反馈，表示操作系统把处理器分配给一个进这种方法称为多级反馈，表示操作系统把处理器分配给一个进程，当该进程阻塞或被抢占时，就反馈到多个优先级队列中的程，当该进程阻塞或被抢占时，就反馈到多个优先级队列中的一个队列中。一个队列中。调度算法调度算法多级反馈轮转法多级反馈轮转法调度算法调度算法多级反馈轮转法多级反馈轮转法v 这个方案有许多变体。这个方案有许多变体。v 该简单方案存在的一个问题是长进程的周转时间可能惊人地该简单方案存在的一个问题是长进程的周转时间可能惊人地

47、增加。事实上，如果频繁地有新作业进入系统，就有可能出增加。事实上，如果频繁地有新作业进入系统，就有可能出现饿死的情况。现饿死的情况。v 为补偿这一点，可以按照队列改变抢占次数为补偿这一点，可以按照队列改变抢占次数: :从从RQ0RQ0中调度的中调度的进程允许执行一个时间单位，然后被抢占进程允许执行一个时间单位，然后被抢占; ;从从RQ1RQ1中调度的进中调度的进程允许执行两个时间单位，等等。一般而言，从程允许执行两个时间单位，等等。一般而言，从RQiRQi中调度中调度的进程允许执行的进程允许执行2 2i i的时间，然后才被抢占。的时间，然后才被抢占。v 即使给较低的优先级分配较长的时间，长进程

48、仍然有可能饿即使给较低的优先级分配较长的时间，长进程仍然有可能饿死。一种可能的补救方法是当一个进程在它的当前队列中等死。一种可能的补救方法是当一个进程在它的当前队列中等待服务的时间超过一定的时间量后，把它提升到一个优先级待服务的时间超过一定的时间量后，把它提升到一个优先级较高的队列中。较高的队列中。v 把系统中的所有进程分成若干个具有不同优先级别的组，同把系统中的所有进程分成若干个具有不同优先级别的组，同一组的进程都具有与所在组同样的优先级别，并且把每组进一组的进程都具有与所在组同样的优先级别，并且把每组进程组织成一个先进先出的队列。在设计时，按优先级别越高程组织成一个先进先出的队列。在设计时

49、，按优先级别越高的组中的进程应得时间片越短的原则分配时间片。的组中的进程应得时间片越短的原则分配时间片。v 在调度时，调度在调度时，调度器每次都从优先器每次都从优先级高的就绪队列级高的就绪队列中选择队首的就中选择队首的就绪进程。当在高绪进程。当在高优先级的队列中优先级的队列中找不到就绪进程找不到就绪进程时，才到低优先时，才到低优先级的就绪进程队级的就绪进程队列中选取。列中选取。Windows NTWindows NT操作系统的优先级调度操作系统的优先级调度v 在在Windows NTWindows NT操作系统中，一个进程通常定义为程序的一个操作系统中，一个进程通常定义为程序的一个实体，是一段调入内存准备执行的一段应用程序。它可以使实体，是一段调入内存准备执行的一段应用程序。它可以使用位的虚地址空间用位的虚地址空间(Windows NT(Windows NT所使用的所使用的3232位保护模式，采位保护模式，采用页面交换技术，容许应用程序在运行时拥有虚地址空间用页面交换技术，容许应用程序在运行时拥有虚地址空间) )来放有应用程序来放有应用程序(EXE(EXE文件文件) )的代码和数据。的代码和数据。v 但是进程是没有活力的，因其并未得到运行所必须的其它资