集群上并行作业的调度21.5基于通信的协同调度1、基于需求的协同调度 2、隐式协同调度21.5.1基于需求的协同调度基于需求的协同调度是在考虑通信模式的情况下决定哪 些进程应该被共同调度。这个方法要求通信子系统进行协作，将通 信事件通知给调度器。通信子系统能够监视带来消息的目的地，并 提高进程的优先级。因而，发送消息进程可能会使得接受进程与它 一起被调度。如果不当的提高接收信息进程的优先级，会带来不公平性问 题。用户可能会通过在它们的进程之间发送假消息来提高其程序的 优先级。因此，通信子系统只是在不损害公平的基础上才会提高接 收消息进程的优先级。21.5.1基于需求的协同调度当多个并行作业共同存在于一个系统中时会出现另一个 问题。 假设有两个节点，每个节点上都有两个进程，它们分别来 自两个并行作业。假定运行于节点1上的作业A的进程A1发送了一 个消息给运行于节点2上的作业A的另一个进程A2，于此同时，运 行于节点2上的作业B的进程B2发送了一个消息给运行于节点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/LSF21.6.1 进入许可控制HPC应用程序需要高性能，但同时它也给系统带来很重 的负载。因此,如果应用程序耗费了过多的系统资源，那么它们将 被加以控制。特别是可以在开始的时候就拒绝它们进入系统。一个通常的办法是使用批调度系统。这类系统定义了一 组队列，批处理作业将被提交到这些队列上。每一个队列中都包含 着具有某些特定属性，如预计执行时间以及存储需求等的作业。批 调度器然后基于作业的属性和可用资源，并根据本地的调度策略来 选择作业执行。其他的作业在队列中等待，以便不会使系统过载。21.6.1 进入许可控制批调度系统选择哪个工作站来使用也存在着同样的问题。一个 解决方法是只使用空闲工作站。然而，这同样存在问题,因为空闲 工作站池是在不断变化着的。另一个方法是使用所有的工作站，并 优先使用那些负载较轻的。这个方法似乎能起作用，因为工作站所 有者的平均交互工作负载虽然有时会有大的瞬间波动，但一般都是 相当稳定的。而且，每个工作姑在任 一时刻都只能容纳一个并行 作业，以使得交互式工作能够快速抢占系统资源。21.6.2 实例分析：Utopia/LSFUtopia是一个大规模异构集群上的负载共享环境。它由 三个主要部分组成：一个收集负载信息以做出进程放置决定的机 制.一个透明远程执行的机制和一个供应用程序使用库。在这个基 础上，工作负载控制与分析部件、批调度部件和并行应用程序支持 部件被建 立起来。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