处理机调度的层次和调度算法的目标

处理机调度的层次和调度算法的目标

在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。在多道批处理系统中，一个作业从提交到获得处理机执行，直至作业运行完毕，可能需要经历多级处理机调度，下面先来了解处理机调度的层次。

处理机调度的层次

1. 高级调度(High Level Scheduling)高级调度又称长程调度或作业调度，它的调度对象是作业。其主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。高级调度主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度。
2. 低级调度(Low Level Scheduling)低级调度又称为进程调度或短程调度，其所调度的对象是进程（或内核级线程）。主要功能是，根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。
3. 中级调度(Intermediate Scheduling)中级调度又称为内存调度。引入中级调度的主要目的是，提高内存利用率和系统吞吐量。为此，应把那些暂时不能运行的进程，调至外存等待，此时进程的状态称为就绪驻外存状态（或挂起状态）。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定，把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。中级调度实际上就是存储器管理中的对换功能，将在第四章中介绍。

   
   在上述三种调度中，进程调度的运行频率最高，在分时系统中通常仅10~100s便进行一次进程调度，因此把它称为短程调度。为避免调度本身占用太多的CPU时间，不宜使进程调度算法太复杂。作业调度往往是发生在一批作业已运行完毕并退出系统，又需要重新调入一批作业进入内存时，作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。中级调度的运行频率基本上介于上述两种调度之间，因此把它称为中程调度。

处理机调度算法的目标

一般而言，在一个操作系统的设计中，应如何选择调度方式和算法，在很大程度上取决于操作系统的类型及其设计目标，例如，在批处理系统、分时系统和实时系统中，通常都采用不同的调度方式和算法。

处理机调度算法的共同目标

1. 资源利用率

为提高系统的资源利用率，应使系统中的处理机和其它所有资源都尽可能地保持忙碌状态，其中最重要的处理机利用率可用以下方法计算：

CPU的利用率=CPU有效工作时间 / (CPU空闲等待时间+CPU有效工作时间)

2. 公平性。

公平性是指应使诸进程都获得合理的CPU时间，不会发生进程饥饿现象。 公平性是相对的，对相同类型的进程应获得相同的服务：但对于不同类型的进程，由于其紧急程度或重要性的不同，则应提供不同的服务。

3. 平衡性。

由于在系统中可能具有多种类型的进程，有的属于计算型作业，有的属于/O型。为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。

4. 策略强制执行。

对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。

批处理系统的目标

(1) 平均周转时间短。所谓周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔（称为作业周转时间）。它包括四部分时间：作业在外存后备队列上等待(作业)调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，以及进程等待/O操作完成的时间。其中的后三项在一个作业的整个处理过程中，可能发生多次。

对每个用户而言，都希望自己作业的周转时间最短。但作为计算机系统的管理者，则总是希望能使平均周转时间最短，这不仅会有效地提高系统资源的利用率，而且还可使大多数用户都感到满意。应使作业周转时间和作业的平均周转时间尽可能短。否则，会使许多用户的等待时间过长，这将会引起用户特别是短作业用户的不满。可把平均周转时间描述为：

为了进一步反映调度的性能,更清晰地描述各进程在其周转时间中,等待和执行时间的具体分配状况,往往使用带权周转时间,即作业的周转时间T与系统为它提供服务的时间Ts,之比,即W=T/Ts,而平均带权周转时间则可表示为:

(2) 系统吞吐量高。由于吞吐量是指在单位时间内系统所完成的作业数,因而它与批处理作业的平均长度有关。事实上,如果单纯是为了获得高的系统吞吐量,就应尽量多地选择短作业运行。

(3) 处理机利用率高。对于大、中型计算机, CPU价格十分昂贵,致使处理机的利用率成为衡量系统性能的十分重要的指标;而调度方式和算法又对处理机的利用率起着十分重要的作用。如果单纯是为使处理机利用率高,应尽量多地选择计算量大的作业运行。由上所述可以看出,这些要求之间是存在着一定矛盾的。

分时系统的目标

(1) 响应时间快。响应时间快是选择分时系统中进程调度算法的重要准则。所谓响应时间,是从用户通过键盘提交一个请求开始,直到屏幕上显示出处理结果为止的一段时间间隔。它包括三部分时间:一是请求信息从键盘输入开始,直至将其传送到处理机的时间;二是处理机对请求信息进行处理的时间:三是将所形成的响应信息回送到终端显示器的时间。

(2) 均衡性。用户对响应时间的要求并非完全相同。通常用户对较复杂任务的响应时间允许较长,而对较简单任务的响应时间则要短。所谓均衡性,是指系统响应时间的快慢应与用户所请求服务的复杂性相适应。

实时系统的目标

(1) 截止时间的保证。所谓截止时间,是指某任务必须开始执行的最迟时间,或必须完成的最迟时间。对于严格的实时系统,其调度方式和调度算法必须能保证这一点,否则将可能造成难以预料的后果。对于实时系统而言,调度算法的一个主要目标是保证实时任务对截止时间的要求。对于HRT任务,其调度方式和调度算法必须确保对截止时间的要求,否则将可能造成难以预料的后果;而对于SRT任务,其调度方式和调度算法也应基本上能保证对截止时间的要求。

(2) 可预测性。在实时系统中,可预测性显得非常重要。例如,在多媒体系统中,无论是电影还是电视剧都应是连续播放的,这就提供了请求的可预测性。如果系统中采用了双缓冲,则因为可实现第i帧的播放和第i+1帧的读取并行处理,进而可提高其实时性。