LMT NEW PBS作业排队计算系统的调度算法

章鱼大丸子

            LMT NEW PBS作业排队计算系统的调度算法

    一个作业定义为一个完整的、有用的一段信息的传送。一个作业的长度由传送的字节数来度量。为简便起见，定义一个短作业为能在一个IP分组中封装的作业。现在实际使用的路由和交换机所有数据分组处理方式是一致的，而不管它们来自短作业还是长作业。

作业源地址指送出作业的主机，作业的目标地址是指接收并处理数据的主机，一个作业的完成是指作业的最后一个分组被成功传送到目的地。作业的响应时间是第一个分组被传送出的时间与最后一个分组被传送到作业目标地址的时间间隔。

作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，再从外存的后备队列中选取某些作业调入到内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。因此，有时也把作业调度称为接纳调度。

在LMT NEW PBS作业排队计算系统中，就利用到了诸多的调度算法，这些调度算法都遵循着根据系统的资源分配策略所规定的资源分配算法。

LMT NEW PBS系统选择调度方式和算法的若干准则如下：

1)   面向用户的准则：周转时间短、响应时间快、截止时间的保证、优先权准则。

2)   面向系统的准则：系统吞吐量、处理机利用率好、各类资源平衡利用。

3)   最优准则：最大的CPU利用率、最大的吞吐量、最短的周转时间、最短的等待时

  间、最短的响应时间。

    以下就是具体介绍LMT NEW PBS系统的调度算法：

1、先来先服务调度算法

   先来先服务调度算法是一种简单的调度算法，该算法可以用于作业调度也 可以用于进程调度。作业调度中采用该算法时，每次调度都是从后备作业 队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们 分配资源、创建进程，然后放入就绪队列。在进程中采用先来先服务算法 时，每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配 处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才 放弃处理机。该算法有利于常作业而不利于短作业。

2、最短作业优先调度算法

   短作业优先算法是针对短作业或短进程优先调度的算法，可以用用于作业 调度也可以用于进程调度。短作业优先算法是从后备队列中选择一个或多 个估计运行时间较短的作业将它们调入内存中运行。而短进程优先调度算 法则是在后备队列中选择一个估计运行时间最短的进程，将处理机分配给 它使他立即执行并一直执行到完成，或发生某事件而阻塞后才放弃处理机 时再从新调度。

   最短作业优先调度算法有效的降低作业的平均等待时间，提高了系统的吞吐量。

   对长作业（或进程）不利，可能死等，且未考虑作业的紧迫程度。

3、 高优先权优先调度算法

   为了考虑作业的紧迫程度，引入了最高优先权调度算法

1)   优先权调度算法类型

a)  非抢占式优先权算法

    系统把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直到完成；或因发生某时间使该进程放弃处理机时，系统才可将处理机重新分配给另一优先权最高的进程。

b)  抢占式优先权算法

    系统把处理机优先权最高的进程，使之执行。若在其执行期间，只要又出现另一个优先权更高的进程，则立即停止当前进程的执行，重新分配处理机给新来的优先权更高的进程。

2)   优先权类型

a)   静态优先权

   静态优先权是在创建进程的时确定的，且在进程的整个运行期间保持不变。一般，利用某一范围内的整数来表示，如，0~7或0～255中的整数。

b)   动态优先权

   是指在创建进程时确定的优先权，在进程的运行期间会发生变化。

4、高响应比优先调度算法

利用响应比也就是优先权来决定给作业分配处理机。

   高响应比优先调度算法

   响应比=响应时间/要求服务时间=（等待时间+要求服务时间）/要求服务时间=1+等待时间/要求服务时间

   同时到达的作业（等待时间相同），要求服务时间越短（短作业），响应比越高，越有利于短作业。

   要求服务时间相同的作业，等待时间越长，响应比越高，相当于先来先服务。

   长作业在等待足够长时间后，响应比上升，也可被调度，避免长作业的死等。

   每次调度需计算响应比，增加系统的开销。

　 我们可以看出，优先权随等待时间的增加而提高，因此长作业在等待一定时间后，就有机会分配到处理机执行。

5、基于时间片的轮转调度算法

1)   时间片轮转法

   系统将所有就绪进程按先到先服务的原则，排成一个队列，依次调度，把CPU分配给队首进程，并令其执行一个时间片/CPU时间，通常为几个毫秒～几百毫秒。时间片用完后，该进程将被抢占并插入就绪队列末尾。

2)   多级反馈队列调度算法

   多级反馈队列调度算法是时间片轮转算法和优先级调度算法的综合和发展，通过动态调整进程优先级和时间片大小，不必事先估计进程的执行时间，多级反馈队列可兼顾多方面的系统目标，是目前公认的一种较好的进程调度算法。

实现过程：

1)   设置多个就绪队列，并为每个队列赋予不同的优先级。队列1的优先级最高，其余队列逐个降低。

2)   每个队列中进程执行时间片的大小也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。

3)   当一个新进程进入系统时，首先将它放入队列1的末尾，按先到先服务等待调度。如能完成，便可准备撤离系统，反之由调度程序将其转入队列2的末尾，按先到先服务再次等待调度，如此下去，进入队列n按时间片轮转算法调度执行。

4)   仅当队列1为空时，才调度队列2中的进程运行。若队列I中的进程正执行，此时有新进程进入优先级较高的队列中，则新进程将抢占运行。原进程转移至下一队列。

结论：

1)   如等待时间相同,则要求服务时间愈短,其优先权愈高。就是短作业优先算法。

2)   如要求服务时间相同,优先权决定于等待时间。就是先来先服务算法。

3)   对长作业,若等待时间足够长，优先权也高，也能获得CPU。是多级反馈队列算法的优点，解决了短作业优先算法中，长作业的运行得不到保证的情况。

LMT NEW PBS作业队列计算系统支持多个队列，每个队列可配置一定的资源量，每个队列采用先来先服务调度策略，为了防止同一个用户的作业独占队列中的资源，该调度器会对同一用户提交的作业所占资源量进行限定。调度是，首先按以下策略选择一个合适队列：（计算每个队列中正在运行的任务数与其应该分得的计算资源之间的比值，选择一个该比值最小的队列。）；然后按以下策略选择该队列中一个作业：（按照作业优先级和提交时间顺序选择，同时考虑用户资源量限制和内存限制。）。

特性：

1、计算能力保证。支持多个队列某个队列可以被提交到某一个队列中。每个队列会配置一定比例的计算资源，且所有提交到队列中的作业共享该队列中的资源。

2、灵活性。空闲资源会被分配给那些未达到资源使用上的队列，当某个未到达资源的队列需要资源时，一旦出现空闲资源，便会分配给它们。

3、支持优先级。队列支持作业优先级调度。

4、多重租赁。综合考虑多重约束防止单个作业、用户或者队列独占队列或集群中的资源。

5、基于资源的调度。支持资源密集型作业，允许作业使用的资源量高于默认值，进而可容纳不同资源需求的作业。不过，当前仅支持内存资源的调度。

总结

    一个功能强大、富有效率的作业计算管理系统 不但能大大方便用户的使用，而且能够极大地提高机群系统的利用率。
    LMT NEW PBS作业排队调度管理系统作为lanmantech公司研发产品的一个重要组成部分，今后也将在调度策略、安全性以及高可用性、好用性方面作进一步的改进。同时，面对不断更新的网络系统环境的出现，我们也将在支持系统应用方面作一些改进，使其适应新的计算环境。