基于BACKFILL的并行计算作业调度算法研究
发布时间：2020-09-27 13:46
在众多的并行作业调度算法中,Backfill通常被广泛认为是有效提高CPU利用率的一种算法,该算法是在FCFS算法的基础上,将队列中较小的作业回填(backfill)到空闲CPU,以提高CPU利用率。但是,当空闲CPU数量仍然无法满足Backfill算法中小作业的回填要求时,系统仍有部分CPU闲置,因而也难以达到更好的提高CPU利用率的目的。 为了改进Backfill算法不能充分利用空闲CPU这一不足之处,本文提出了基于Backfill算法的需求自适应改进算法;而对于共享内存体系结构的并行计算机系统,本文还提出了基于Backfill算法的资源自动回收改进算法。 在Backfill的基础上,需求自适应改进算法利用CPU的空闲空间作为判断依据,扩展了可参与填充操作作业的数量。该算法通过合理修改队列中作业的参数——所需CPU数量和估计运行时间,以满足Backfill算法下无法利用的CPU空闲,弥补了Backfill算法的不足,大大提高了并行计算机系统的CPU资源的利用率。 资源自动回收改进算法以正在运行的作业的CPU利用率为依据,通过动态调整正在运行的作业的CPU数,扩大可供回填(backfill)的CPU空间,使得Backfill算法无法回填(backfill)的作业得到运行,弥补了Backfill算法的不足,也很好的提高了共享内存体系结构并行计算机系统的CPU利用率。两种改进算法都是在Backfill的基础上,从不同的技术层面来改进Backfill算法,通过与FCFS、Backfill相结合,共同参与并行计算机系统的作业调度,实现CPU资源利用率的不断提高。
【学位单位】：湖南大学
【学位级别】：硕士
【学位年份】：2007
【中图分类】：TP338.6
【部分图文】：
以对它有一个总体上的了解，为并行程序设计奠定基础。并行计算机可以按多种方式进行分类，如果按照存储机构划分，可以分为共享内存式并行计算机和分布式内存并行计算机[29]，如图2.1所示。 ...................，，， ，，，，， ，，，， ， ，， ，共共享内存 存 ‘‘‘ ‘‘‘ ‘‘‘ 且且 且 且且 且且且 且又又夕夕 夕女参夕夕夕冬_乡 乡互互连网络 络 ///_\\\\\滩止卜卜 卜矛粼粼粼 百百 百 百林落 落 落万 万 丫 丫 丫丫 丫 丫 丫 官官共享内存并行计算机分布式内存并行计算机分布式共享内存并行计算机不具有局部存储的处理单元共享存储的局部处理单元具有局部存储的处理单元回目回﨎图2.1按存储方式对并行计算机进行分类对于共享内存的并行计算机，各个处理单元之间是通过共享内存来访问来交换信息、协调各处理器对并行任务进行处理。对这种共享内存的编程
EEExternalJobsehedulerrrrr衬。 dennn图2.2一个典型的资源管理系统可以通过图2.2[’l所示，对作业调度有一个整体的认识。这是一个典型的资源管理系统(Atypiealresourcemanagementsystem)，作业调度器从资源管理器获取有关作业的排队情况、作业的优先权和系统可用资源等信息，然后决定作业将在哪一个节点被执行以及被执行的时间顺序。2.2.3几种经典并行作业调度算法的描述由多CPU组成的并行计算机系统或通过以太网或其他网络连接的多个超级计算节点构成的并行计算集群己实现了大规模的并行计算能力，相对公平的作业调度成为并行计算系统急需改进和提高的问题。一个“好的”作业调度器要同时兼顾“公平、简单易懂以及提高可用资源的利用率”，而这三者之间却又相互矛盾。在不同的环境下，可以选择不同的作业调度算法或者通过多种作业调度算法并用来实现三者之间的折中，得到一个较为和谐、满意的作业调度器。如今
Ti衅图2.4FCFS作业调度2.SJF(最短先服务);LJF(最长先服务)如果说FCFS的调度原则是依据作业被提交的时间先后顺序来排序作业的序，而最终被确定为作业被执行的顺序，那么最短先服务SJF(shortest的调度原理则是:系统周期性地检索用户提交的作业，将占用资源最小排在队列前面最先执行它。这种调度方式是以作业所需求资源的大小来排列中资源需求小的作业总是排在资源需求大的作业前面而被提前调度运图2.4FCFS的作业调度中，作业T7、T:在SJF调度下就会比作业T6提在作业T，和T6之间就不会存在大量空闲CPU的浪费，这样在一定程度FCFS调度过程所导致的大量的CPU碎片，从而很好的提高了CPU资。但这种调度方式使小作业成为了系统可用资源的主宰，而大作业的执可预计的延缓，失去一定的公平性，并且还会导致大作业因长时间分配
本文编号：2827954
【学位单位】：湖南大学
【学位级别】：硕士
【学位年份】：2007
【中图分类】：TP338.6
【部分图文】：
以对它有一个总体上的了解，为并行程序设计奠定基础。并行计算机可以按多种方式进行分类，如果按照存储机构划分，可以分为共享内存式并行计算机和分布式内存并行计算机[29]，如图2.1所示。 ...................，，， ，，，，， ，，，， ， ，， ，共共享内存 存 ‘‘‘ ‘‘‘ ‘‘‘ 且且 且 且且 且且且 且又又夕夕 夕女参夕夕夕冬_乡 乡互互连网络 络 ///_\\\\\滩止卜卜 卜矛粼粼粼 百百 百 百林落 落 落万 万 丫 丫 丫丫 丫 丫 丫 官官共享内存并行计算机分布式内存并行计算机分布式共享内存并行计算机不具有局部存储的处理单元共享存储的局部处理单元具有局部存储的处理单元回目回﨎图2.1按存储方式对并行计算机进行分类对于共享内存的并行计算机，各个处理单元之间是通过共享内存来访问来交换信息、协调各处理器对并行任务进行处理。对这种共享内存的编程
EEExternalJobsehedulerrrrr衬。 dennn图2.2一个典型的资源管理系统可以通过图2.2[’l所示，对作业调度有一个整体的认识。这是一个典型的资源管理系统(Atypiealresourcemanagementsystem)，作业调度器从资源管理器获取有关作业的排队情况、作业的优先权和系统可用资源等信息，然后决定作业将在哪一个节点被执行以及被执行的时间顺序。2.2.3几种经典并行作业调度算法的描述由多CPU组成的并行计算机系统或通过以太网或其他网络连接的多个超级计算节点构成的并行计算集群己实现了大规模的并行计算能力，相对公平的作业调度成为并行计算系统急需改进和提高的问题。一个“好的”作业调度器要同时兼顾“公平、简单易懂以及提高可用资源的利用率”，而这三者之间却又相互矛盾。在不同的环境下，可以选择不同的作业调度算法或者通过多种作业调度算法并用来实现三者之间的折中，得到一个较为和谐、满意的作业调度器。如今
Ti衅图2.4FCFS作业调度2.SJF(最短先服务);LJF(最长先服务)如果说FCFS的调度原则是依据作业被提交的时间先后顺序来排序作业的序，而最终被确定为作业被执行的顺序，那么最短先服务SJF(shortest的调度原理则是:系统周期性地检索用户提交的作业，将占用资源最小排在队列前面最先执行它。这种调度方式是以作业所需求资源的大小来排列中资源需求小的作业总是排在资源需求大的作业前面而被提前调度运图2.4FCFS的作业调度中，作业T7、T:在SJF调度下就会比作业T6提在作业T，和T6之间就不会存在大量空闲CPU的浪费，这样在一定程度FCFS调度过程所导致的大量的CPU碎片，从而很好的提高了CPU资。但这种调度方式使小作业成为了系统可用资源的主宰，而大作业的执可预计的延缓，失去一定的公平性，并且还会导致大作业因长时间分配
【引证文献】
相关硕士学位论文 前1条
1 江启洲;异构集群的作业管理及作业调度的研究与实现[D];华南理工大学;2010年
本文编号：2827954
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/2827954.html
