4.2.1 调度队列模型
前面所介绍的高级调度、低级调度以及中级调度，都将涉及作业或进程的队列，由此可以形成如下三种类型的调度队列模型。
1.仅具有进程调度的调度队列模型
在分时操作系统中，通常仅设置了进程调度，用户键入的命令和数据都直接送入内存。对于命令，是由OS为之建立的一个进程。系统可以把处于就绪态的进程组织成栈、树或一个无序链表，至于到底采用其中哪种形式，则与OS类型和所采用的调度算法有关。例如，在分时操作系统中，常把就绪进程组织成FIFO队列形式。每当OS创建一个新进程时，便将它挂在就绪队列的末尾，然后按时间片轮转方式运行。
每个进程在执行时都可能出现以下三种情况：
（1）任务在给定的时间片内已经完成，该进程便在释放处理机后进入完成状态。
（2）任务在本次分得的时间片内尚未完成，OS便将该任务再放入就绪队列的末尾。
（3）在执行期间，进程因为某事件而被阻塞后，被OS放入阻塞队列。
图4-2示出了仅具有进程调度的调度队列模型。
图4-2 仅具有进程调度的调度队列模型
2.具有高级和低级调度的调度队列模型
在批处理系统中，不仅需要进程调度，而且还需要作业调度，由后者按一定的作业调度算法，从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列，然后才由进程调度按照一定的进程调度算法选择一个进程，把处理机分配给该进程。图4-3示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面：
图4-3 具有高、低两级调度的调度队列模型
（1）就绪队列的形式。在批处理系统中，最常用的是最高优先权优先调度算法，相应地，最常用的就绪队列形式是优先权队列。进程在进入优先级队列时，根据其优先权的高低，被插入具有相应优先权的位置上，这样调度程序总是把处理机分配给就绪队列中的队首进程。在最高优先权优先的调度算法中，也可采用无序链表方式，即每次把新到的进程挂在链尾，而调度程序每次调度时，是依次比较该链中各进程的优先权，从中找出优先权最高的进程，将之从链中摘下，并把处理机分配给它。显然，与优先权队列相比，无序链表方式的调度效率较低。
（2）设置多个阻塞队列。对于小型系统，可以只设置一个阻塞队列；但当系统较大时，若仍只有一个阻塞队列，其长度必然会很长，队列中的进程数可以达到数百个，这将严重影响对阻塞队列操作的效率。故在大、中型系统中通常都设置了若干个阻塞队列，每个队列对应于某一种进程阻塞事件。
3.具有三级调度的调度队列模型
当在OS中引入中级调度后，人们可把进程的就绪态分为内存就绪（表示进程在内存中就绪）和外存就绪（进程在外存中就绪）。类似地，也可把阻塞态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪。图4-4示出了具有三级调度的调度队列模型。
(www.xing528.com)
图4-4 具有三级调度的调度队列模型
4.2.2 调度准则
在批处理系统、分时操作系统和实时系统中，通常都采用不同的调度方式和算法。应如何选择调度方式和算法，在很大程度上取决于操作系统的类型及其目标。选择调度方式和算法的准则，包括面向用户的准则和面向系统的准则。
1.面向用户的准则
这是为了满足用户的需求所应遵循的一些准则。其中，比较重要的有以下几点：
（1）周转时间短。通常把周转时间的长短作为评价批处理系统的性能、选择作业调度方式与算法的重要准则之一。所谓周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔（称为作业周转时间）。它包括四部分时间：作业在外存后备队列上等待（作业）调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，以及进程等待I／O操作完成的时间。其中后三项在一个作业的整个处理过程中可能会发生多次。
对每个用户而言，都希望自己作业的周转时间最短。但作为计算机系统的管理者，则总是希望能使平均周转时间最短，这不仅能有效地提高系统资源的利用率，而且还可使大多数用户都感到满意。可把平均周转时间描述为
作业的周转时间T与系统为它提供服务的时间T s之比，即W＝T／T s，称为带权周转时间，而平均带权周转时间则可表示为
（2）响应时间快。常把响应时间的长短用来评价分时操作系统的性能，这是选择分时操作系统中进程调度算法的重要准则之一。所谓响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说，直到屏幕上显示出结果为止的一段时间间隔。它包括三部分时间：从键盘输入的请求信息传送到处理机的时间，处理机对请求信息进行处理的时间，以及将所形成的响应信息回送到终端显示器的时间。
（3）截止时间的保证。这是评价实时系统性能的重要指标，因而是选择实时调度算法的重要准则。所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。对于严格的实时系统，其调度方式和调度算法必须能保证这一点，否则将可能造成难以预料的后果。
（4）优先权准则。在批处理、分时和实时系统中选择调度算法时，都可遵循优先权准则，以便让某些紧急的作业能得到及时处理。在要求较严格的场合，往往还须选择抢占式调度方式，才能保证紧急作业得到及时处理。
2.面向系统的准则
这是为了满足系统要求而应遵循的一些准则。其中，较重要的有以下几点：
（1）系统吞吐量高。这是用于评价批处理系统性能的另一个重要指标，因而是选择批处理作业调度的重要准则。由于吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度具有密切关系。对于大型作业，一般吞吐量约为每小时一道作业；对于中、小型作业，其吞吐量则可能达到数十道作业之多。作业调度的方式和算法对吞吐量的大小也将产生较大影响。事实上，对于同一批作业，若采用了较好的调度方式和算法，则可显著地提高系统的吞吐量。
（2）处理机利用率高。对于大、中型多用户系统，由于CPU价格十分高昂，致使处理机的利用率成为衡量系统性能的十分重要的指标；而调度方式和算法对处理机的利用率起着十分重要的作用。在实际系统中，CPU的利用率一般在40%（系统负荷较轻）～90%。在大、中型系统中，在选择调度方式和算法时，应考虑到这一准则。但对于单用户微机或某些实时系统，则此准则就不那么重要了。
（3）各类资源的平衡利用。在大、中型系统中，不仅要使处理机的利用率高，而且还应能有效地利用其他各类资源，如内存、外存和I／O设备等。选择适当的调度方式和算法可以保持系统中各类资源都处于忙碌状态。但对于微型机和某些实时系统而言，该准则并不重要。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
