集群上并行作业的调度

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2014/4/23,#,集群上并行作业的调度,21.5,基于通信的协同调度,1,、基于需求的协同调度,2,、隐式协同调度,21.5.1,基于需求的协同调度,基于需求的协同调度是在考虑通信模式的情况下决定哪些进程应该被共同调度。这个方法要求通信子系统进行协作，将通信事件通知给调度器。通信子系统能够监视带来消息的目的地，并提高进程的优先级。因而，发送消息进程可能会使得接受进程与它一起被调度。,如果不当的提高接收信息进程的优先,级，会,带来不公平性问,题。用户可能会通,过在它们的进程之,间发,送假消息来提高其程序的优先,级。因此，通信子系统只是在不损害公平的基础上才会提高接收消息进程的优先级。,21.5.1,基于需求的协同调度,当,多个并行作业共同存在于一个系统中,时会出现,另一个问,题。,假,设,有,两个节点，每,个节,点上都有两个进程，它们分别来自两个并行作业。假定运行于节点1上的作,业,A,的,进,程,A1,发,送了一个消息给运行于节点2上的作,业,A,的,另一个进,程,A2,，,于此,同,时，运行于节点2,上的,作,业,B,的,进,程,B,2,发送了一个消息给运,行,于,节,点1上的作,业,B,的,另一个进,程,B1,。,如果系,统处,理不当,就,无,法,解决这个冲突问题，或者可能只是在两个节点上切换进程，而不会协调调度,任何,一个作业。,21.5.1,基于需求的协同调度,一个解,决方法是使,用纪元数。,节点上,的纪元,数每当,上下,文被自动切,换时就被增加。这个纪元数,被加到所有的向外发,送的消,息,屮。当,一个节点接收到一个消,息时，,它,将本地,的,纪元数,与,到来,消息所包,含的纪,元数进行比,较：,如果到来,消息包含的纪元数较大,就切换到到,来消息,所,指的,目的进程,中。在切,换的时候,节点同时将到来消息的纪元数作为本机的纪元,数。,如果到来消息包含的纪元数,较小,则拒绝其所要求的进程切换。这,样当,一个,消息到达时它就不会切,换回以,前的进,程。这样,就使得新的作业能尽快投入运行，并可在所,有的,节点上进,行,协,调调度,。,21.5.2,隐式协同调度,在一个,局域网环境中，基于通信的显式调度控制是很难实现的。然而，如果通信,是通过,UNIX,工,具,(,如套接字,，,socket),来进,行的，,并且应,用程厅是,粗粒度的（大量的计算中夹有,一些,密集,的通,信），,那么这样做,也可能,是不必要,的。原,因是,在,UNIX,中进行,I/O,的进程享有较高的,优先,级。因此，进,程,在通信时在它们各自的节点,上都具有较高的优,先级,，并且在通信过程中它们将会得,到协同调度。这,增,大了完全隐式协同调,度的可能性，隐式协,同调度中的协同调度行为是不会以任何显,式方式出现的。,21.5.2,隐式协同调度,当,显式调度方法,不需要的,时候,，需要,确定,的一点,就是如果一个通信进程正在等待另一,个进,程的响应，那么它并不是不可调度的。这是通过使用一个两阶段的,阻塞机,制来实现,的。,其主耍思想是等待进程最初将等,待一段时间，,以期望得到来自,另一个进程的,响应,。但是,如果在预定义的时间内没有得到响应，进程将会阻塞并释放处理机以,供其,他就绪进程使用。易见如果进程等待的时间与进程切换所带来的额外开销相等,就需要,有 一个算法来在二者之间进行,选择。然而实际情况表明，,等待时间应该是五,倍于进,程切换的 额外,开销，这样就为被,等,待进程,在阻塞悄况下,提供了足够的唤醒时间。,需,要注意的是，隐式协同调度只是当进程正,在通信时才要,保,持进程的,执行一致。在计,算阶,段，进程的执行可能不会保持步调一致。然而,这并不,重要,，因为这,时并不,交互，不需要,进,行协同,调度。,Dasic,算法,21.6,批调度,21.6.1,进入许可控制,21.6.2,实例分析：,Utopia/LSF,21.6.1,进入许可控制,HPC,应,用程序需要高性能，但同时它也给系统带来很重的负载。因此,如果应用程序耗费,了过,多的系统资源，那么它们将被加以控制。特别是可以在开始的时候就拒绝它们,进入系,统。,一,个通常的办法是使用批调度系,统。这类系,统定义了一组队列，批,处理,作业将被提交到这些队列上。每一个队列中都包含着具有某些特定属性，如预计执行时,间以,及存储需求等的作,业。批,调度器然后,基于作业,的属性和可用资源，并根据本地的调度策,略来,选择作业执行,。其他的作业在队列中等待，以便不,会使系统过载。,21.6.1,进入许可控制,批,调度系统选择哪个工作站来使,用也,存在着同样的问题。一个解决方法是只使用,空闲,工作站。然而，这同样存在问题,因为空闲工作站池是在不断变化着的。另一个方法是使,用所,有的工作站，并优先使用那,些,负载较轻的。,这,个方法似乎能起作用，因为工作站所有者的,平均,交互工作负载虽然有时会,有,大,的,瞬间波动，但一般都是相当稳定的。而且，每个工作姑在任 一时刻都只能容纳一个并行作业，以使得交互式工作能够快速抢占系统资源。,21.6.2,实例分析：,Utopia/LSF,Utopia,是一个大规模异构集群上的负载共享环境。它由三个主要部分组成：一个收集负载信息以做出进程放置决定的机制,.,一个透明远程执行的机制和一个供应用程序使用库。在这个基础上，工作负载控制与分析部件、批调度部件和并行应用程序支持部件被建 立起来。,LSF(Load Sharing Facility),是,Utopia,的商业化产物。,负,载信息的收集是通过一组守护进程来实现的，守护进程在每个节点上都有一个。守护进程选择具有最小,ID,的主机作为主负载信息管理,器,(LIM),。,该主节点收集集群中所有节点的负载 信息以得到负载向量,(,包括如最近,cpu,队列长度、存储器利用率以及用户数等信息,，并将此信息 发送给所有的从节点。从节点根据此信息来确定新产生的进程应放置在哪个节点上。,21.6.2,实例分析：,Utopia/LSF,由,于使用集中式的主节点不利于系统的扩展，这个机制只被应用于大小有限制的集群,之内,。集群间的负载共享是通过不同集群的,主,LIM,之,间的通信来实现的。而且，也可以产生,虚拟,集群，它能将物理上分布于系统中不同位置的强,力服务,器组合在一,起。,这样,与虚,拟集群,中,LIM,的,一次通信就可以获得系统中想要得到的全部服务器的信息。,Utopia,的,批调度系统用它来为队列中的并行应用程序获取可用资源信息。然而，由于,批处,理应用程序的运行时间一般都很长，因此要使用较长时间内的平均使用情况来对资源 进行度量，而不是采用最近的平均值。作业是,要进入队,列等待还是要被分配资源去执行是,由主,批处理守护进程决定的，该守护进程与,主,LIM,位,于同样的节点上。批处理进程的真正,执行和,控制是由位于不同节点上的子批处理守护进程来完成的。,21.7,小结,在,NOW,上,巳经提出并实现了很多不同的并行作业调度方法。遗憾的是，由于它们,基,的假设和实现的目标不同，因此很难将它们进行比较。,21.3,节至,21.6,节所描述的系统是基,于如,下的假设：,*平衡,不同机器上的负载以使所有进程都享有同样的服务。,*不影响工,作站所有者的工作，只为空闲工作站分配作业，并且一旦工作站所有者,返回就立,即将它释放。,*,为,并行程序提供一个合适的环境，如交互进程的同时执行等。,*不,能使优先级较低的,(,非交互的,),计算密集型任务充斥整个系统，因此需要进入许可,控制,以及批调度,。,尽,管这些假设是有效的：但是很难全部满足这些假设。因此，可以通过将多个假设结合,起来,以及合并不同系统所使,用的方,法来进行改进。,THANKS,