论文部分内容阅读
【摘要】使用集群计算系统代替昂贵并行计算机平台已成为高性能计算领域的发展趋势，具有易用性、易伸缩性、易管理性和高性价比等优点。作业调度策略是提高集群系统执行并行作业的效率及系统资源利用率的关键因素，决定了整个集群系统的效率，对集群系统提高负载平衡并行处理能力具有重大的意义。
【关键词】集群系统；作业调度；负载平衡
1.linux集群系统作业管理系统概述
如果仅仅将节点连成网络，并不能形成集群，还需要有对这些节点进行管理的软件系统，集群所依赖的软件系统集群作业管理系统JMS（Job Management System）正是为适应这种需求而出现并快速得以发展。集群JMS可以根据用户的需求，统一管理和调度集群的软硬件资源，保证用户作业公平合理地共享集群资源，提高系统资源利用率和吞吐率。集群JMS包括系统资源管理和作业调度管理，作业调度技术是集群作业管理系统中关键的技术之一，作业调度的功能在于提供作业提交、调度、执行及控制的新机制，更加有效地利用系统资源、平衡网络负载、提高系统整体性能。在这种情况下，作业调度策略决定了整个集群系统的效率，尤其是提交计算量大的作业时，良好的作业调度策略可以大大加快执行速度。因此，作业调度策略是提高集群系统执行并行作业的效率及系统资源利用率的关键因素，对集群系统提高并行处理能力具有重大的意义。
2.linux集群系统下作业调度策略与负载平衡
负载平衡的基本作法是定期收集并分析系统各节点的实时负载信息，动态地将作业进程在处理机之间进行分配和调整，以消除系统中负载分布的不均匀性。通常表现节点负载的指标有：（1）CPU的利用率，表示单位时间内CPU处理用户进程和核心进程的时间比。（2）CPU就绪队列的长度，CPU利用率适合用来判断节点是否处于空闲状态，用就绪队列的长度可用来表达负载的大小。（3）测试特定进程的响应时间，对于使用固定时间片的操作系统来说这也是一个选择。（4）磁盘、内存、交换区的可用空间，换页的频率，以及I/O的利用率。如果所选用的指标不止一项，可以将这些指标作为变量组合进一个负载计算公式，实时信息代入公式所得的值应该能区分实际负载的大小。
对于集中式集群JMS的作业调度，实现负载平衡最普通的做法是在作业映射时依据所收集的各节点的负载信息，把作业进程派往能满足作业资源需求且预计作业在那里等待时间最小的节点。一个简化的思想是把负载最轻的节点当作所产生的局部等待时间最小的节点。在集群JMS对作业映射进行修正时，同样可以利用各节点当前的负载信息，通过对过载节点上进程的迁移来实现全系统的负载平衡。集群JMS通过各节点的负载信息，建立所谓的负载转移向量，即在这个向量中每个节点所对应的元素是该节点的相对负载与平均负载的差值（或正或负）。如果向量中对应某些节点的元素的绝对值大到一定程度，就启动负载平衡过程。再以各进程的工作量为基础，决定把哪个进程迁至何处。
3.通用作业调度策略的分析
3.1 资源碎片的产生
通用作业调度策略可以划分为两大类型：一类是面向提高资源利用率的调度类调度策略常见的有FirstFit。另一类是面向公平性的调度策略，确保作业在较短的时间内能够获得资源，避免同等优先级的作业因长时间无法执行而导致作业饥饿问题，这类调度策略常见的是FCFS。
在作业调度策略中，公平性往往与高效性目标是冲突的。若要提高资源利用率，应该使作业调度队列中选取的作业集可以尽可能多的利用资源，而不考虑调度队列中作业的等待时间，这就产生了作业的饿死问题。解决同等优先级作业的饿死问题，往往依靠的是先来先服务的方式，阻塞其他作业的执行，确保作业队列队首的作业获得足够的资源，避免作业的长时间等待，可这种阻塞的方式却导致了系统中产生大量的资源碎片。
3.2 负载平衡的实现
传统的集群作业调度策略实现负载平衡的方法都是相当简练的。例如，将实时的节点负载值与事先规定的阈值做比较，或利用综合负载计算公式将多项负载值换算成一个抽象的值来对比各节点间负载是否平衡，以此来判断节点负载是否适当。在匹配资源需求时，查看节点上剩余资源是否能够满足作业的资源请求量。通常来说，简明的策略不但便于实现，利于降低调度成本，而且一样能在广泛的集群环境内达到整体上理想的性能和效益。
不够细致的调度策略存在着隐患，当简单的方法遭遇一些特殊的问题就会带来调度行为的性能突然下降，需要一定时间来进行自动地恢复。随着计算机的处理能力越来越强大，使得较为复杂的调度策略的运转费用也得到降低。特别是相对于大型作业执行时间的长度和通过网络传输作业和通讯的成本，复杂调度策略的成本日益变得可以为集群使用者接受。所以，目前的集群作业调度策略可设计的更加细致和深入，去挖掘集群提高作业执行性能的潜力。
CPU资源是调度算法中进行优化调度时所使用的主要的资源项目，算法中提到“节点性能”，往往就是指节点的主频。根据系统的针对性和应用性的不同，存在很多种的应用节点负载指标，但没有统一的标准，具体环境下可采取不同的指标，较理想的负载指标应当满足：测量开销低，较易获得和计算，以满足频繁测量的需要；能客观体现所有竞争资源上的负载；各个负载指标在测量及控制上彼此独立。
4.回填策略
回填策略是由Lifka最先提出，它需要用户提供作业的估计执行时间和所需要的节点资源信息。如果队列中的下一个待调度作业由于缺少某些资源不能被启动，回填策略会试图在队列中寻找下一个可以使用已有的空闲资源，且其执行不会延迟该作业执行的作业。换句话说，回填策略允许一些队列后面的作业提前执行。回填策略的使用主要为了实现两个看起来冲突的目标：尽可能的将短作业前移，以提高资源利用率；尽可能的避免大作业等待，因此需要预测作业的运行时间。
保守回填策略的描述如下：
RunningTasklist={j1，j2，i3，...，jn}按照期望完成时间排序的运行的作业
QueuedTasklist={il，i2，i3，...，in}按照到达时间先后顺序排序的作业队列
对每一个在RunningTasklist的j任务，根据j任务占用的资源分配timeXprocessor的空间，形成timeXprocessor的运行作业描述文件P，对每一个在QueuedTasklist的i任务检查P，找到第一个能提供足够processor运行I的时间点anchor。
从anchor时间点开始扫描P中的time轴
{
if（直到作业i的预期完成时间都能保证足够的processor资源可用）
更新P，将anchorXprocessor资源分配给作业i；
else
继续扫描time轴，找到下一个可用的时间点anchor；
}
if（anchor=0）
执行该作业；
next i；
回填策略可以有效的提高基于队列的策略的性能，它在有效的提高小作业的响应时间的同时而不会导致大作业出现饥饿。
参考文献
[1]薛正华，刘伟哲，董小社，伍卫国.基于思维进化的集群作业调度方法研究[J].西安交通大学学报，2008（06）.
[2]张果桃，赵金雁，白中英.基于LT-backfilling算法的集群作业调度系统[J].计算机工程，2007（21）.
[3]赵宗弟，胡凯，胡建平.基于PBS的集群作业调度策略的设计与实现[J].计算机与数字工程，2006（11）.
【关键词】集群系统；作业调度；负载平衡
1.linux集群系统作业管理系统概述
如果仅仅将节点连成网络，并不能形成集群，还需要有对这些节点进行管理的软件系统，集群所依赖的软件系统集群作业管理系统JMS（Job Management System）正是为适应这种需求而出现并快速得以发展。集群JMS可以根据用户的需求，统一管理和调度集群的软硬件资源，保证用户作业公平合理地共享集群资源，提高系统资源利用率和吞吐率。集群JMS包括系统资源管理和作业调度管理，作业调度技术是集群作业管理系统中关键的技术之一，作业调度的功能在于提供作业提交、调度、执行及控制的新机制，更加有效地利用系统资源、平衡网络负载、提高系统整体性能。在这种情况下，作业调度策略决定了整个集群系统的效率，尤其是提交计算量大的作业时，良好的作业调度策略可以大大加快执行速度。因此，作业调度策略是提高集群系统执行并行作业的效率及系统资源利用率的关键因素，对集群系统提高并行处理能力具有重大的意义。
2.linux集群系统下作业调度策略与负载平衡
负载平衡的基本作法是定期收集并分析系统各节点的实时负载信息，动态地将作业进程在处理机之间进行分配和调整，以消除系统中负载分布的不均匀性。通常表现节点负载的指标有：（1）CPU的利用率，表示单位时间内CPU处理用户进程和核心进程的时间比。（2）CPU就绪队列的长度，CPU利用率适合用来判断节点是否处于空闲状态，用就绪队列的长度可用来表达负载的大小。（3）测试特定进程的响应时间，对于使用固定时间片的操作系统来说这也是一个选择。（4）磁盘、内存、交换区的可用空间，换页的频率，以及I/O的利用率。如果所选用的指标不止一项，可以将这些指标作为变量组合进一个负载计算公式，实时信息代入公式所得的值应该能区分实际负载的大小。
对于集中式集群JMS的作业调度，实现负载平衡最普通的做法是在作业映射时依据所收集的各节点的负载信息，把作业进程派往能满足作业资源需求且预计作业在那里等待时间最小的节点。一个简化的思想是把负载最轻的节点当作所产生的局部等待时间最小的节点。在集群JMS对作业映射进行修正时，同样可以利用各节点当前的负载信息，通过对过载节点上进程的迁移来实现全系统的负载平衡。集群JMS通过各节点的负载信息，建立所谓的负载转移向量，即在这个向量中每个节点所对应的元素是该节点的相对负载与平均负载的差值（或正或负）。如果向量中对应某些节点的元素的绝对值大到一定程度，就启动负载平衡过程。再以各进程的工作量为基础，决定把哪个进程迁至何处。
3.通用作业调度策略的分析
3.1 资源碎片的产生
通用作业调度策略可以划分为两大类型：一类是面向提高资源利用率的调度类调度策略常见的有FirstFit。另一类是面向公平性的调度策略，确保作业在较短的时间内能够获得资源，避免同等优先级的作业因长时间无法执行而导致作业饥饿问题，这类调度策略常见的是FCFS。
在作业调度策略中，公平性往往与高效性目标是冲突的。若要提高资源利用率，应该使作业调度队列中选取的作业集可以尽可能多的利用资源，而不考虑调度队列中作业的等待时间，这就产生了作业的饿死问题。解决同等优先级作业的饿死问题，往往依靠的是先来先服务的方式，阻塞其他作业的执行，确保作业队列队首的作业获得足够的资源，避免作业的长时间等待，可这种阻塞的方式却导致了系统中产生大量的资源碎片。
3.2 负载平衡的实现
传统的集群作业调度策略实现负载平衡的方法都是相当简练的。例如，将实时的节点负载值与事先规定的阈值做比较，或利用综合负载计算公式将多项负载值换算成一个抽象的值来对比各节点间负载是否平衡，以此来判断节点负载是否适当。在匹配资源需求时，查看节点上剩余资源是否能够满足作业的资源请求量。通常来说，简明的策略不但便于实现，利于降低调度成本，而且一样能在广泛的集群环境内达到整体上理想的性能和效益。
不够细致的调度策略存在着隐患，当简单的方法遭遇一些特殊的问题就会带来调度行为的性能突然下降，需要一定时间来进行自动地恢复。随着计算机的处理能力越来越强大，使得较为复杂的调度策略的运转费用也得到降低。特别是相对于大型作业执行时间的长度和通过网络传输作业和通讯的成本，复杂调度策略的成本日益变得可以为集群使用者接受。所以，目前的集群作业调度策略可设计的更加细致和深入，去挖掘集群提高作业执行性能的潜力。
CPU资源是调度算法中进行优化调度时所使用的主要的资源项目，算法中提到“节点性能”，往往就是指节点的主频。根据系统的针对性和应用性的不同，存在很多种的应用节点负载指标，但没有统一的标准，具体环境下可采取不同的指标，较理想的负载指标应当满足：测量开销低，较易获得和计算，以满足频繁测量的需要；能客观体现所有竞争资源上的负载；各个负载指标在测量及控制上彼此独立。
4.回填策略
回填策略是由Lifka最先提出，它需要用户提供作业的估计执行时间和所需要的节点资源信息。如果队列中的下一个待调度作业由于缺少某些资源不能被启动，回填策略会试图在队列中寻找下一个可以使用已有的空闲资源，且其执行不会延迟该作业执行的作业。换句话说，回填策略允许一些队列后面的作业提前执行。回填策略的使用主要为了实现两个看起来冲突的目标：尽可能的将短作业前移，以提高资源利用率；尽可能的避免大作业等待，因此需要预测作业的运行时间。
保守回填策略的描述如下：
RunningTasklist={j1，j2，i3，...，jn}按照期望完成时间排序的运行的作业
QueuedTasklist={il，i2，i3，...，in}按照到达时间先后顺序排序的作业队列
对每一个在RunningTasklist的j任务，根据j任务占用的资源分配timeXprocessor的空间，形成timeXprocessor的运行作业描述文件P，对每一个在QueuedTasklist的i任务检查P，找到第一个能提供足够processor运行I的时间点anchor。
从anchor时间点开始扫描P中的time轴
{
if（直到作业i的预期完成时间都能保证足够的processor资源可用）
更新P，将anchorXprocessor资源分配给作业i；
else
继续扫描time轴，找到下一个可用的时间点anchor；
}
if（anchor=0）
执行该作业；
next i；
回填策略可以有效的提高基于队列的策略的性能，它在有效的提高小作业的响应时间的同时而不会导致大作业出现饥饿。
参考文献
[1]薛正华，刘伟哲，董小社，伍卫国.基于思维进化的集群作业调度方法研究[J].西安交通大学学报，2008（06）.
[2]张果桃，赵金雁，白中英.基于LT-backfilling算法的集群作业调度系统[J].计算机工程，2007（21）.
[3]赵宗弟，胡凯，胡建平.基于PBS的集群作业调度策略的设计与实现[J].计算机与数字工程，2006（11）.