分布计算系统笔记——第九章 分布式调度

什么东西啊，前半段还挺好看，后半段长篇大论根本看不懂

调度算法概述 ​

分类 ​

其他分类方法：

1. 非抢先式的(non-preemptive)和抢先式的(preemptive)。对非抢先式的调度算法，一个进程开始执行后就不能中断。在抢先式调度算法中，进程可以中断，从一个处理机上移走，到另一个处理机上继续执行。
2. 适应性(adaptive)和非适应性的(non-adaptive)。非适应性调度算法只使用一种负载分配策略，不会根据系统的反馈而改变自己的行为。适应性调度算法能够根据系统的反馈调整自己的行为，采用不同的负载分配策略。典型地，一个适应性调度算法是许多种调度算法的集合，根据系统的各种参数来选择一种合适的算法。

目标 ​

1. 负载平衡。维持整个分布式系统各个资源的负载大致相同->提高整个系统流量
2. 负载共享。防止某个处理机负载过重->缩短特定程序的执行时间

次优调度 ​

最优调度、次优调度

最优调度是NP完全问题，所以常采用次优调度

有效性评价参数：通信代价、执行代价、资源利用率

次优调度分类：近似的次优调度算法和启发式的次优调度算法

近似 ​

近似的次优调度常和最优调度使用相同的算法，但是近似的次优调度不搜索这个算法的所有解空间，而是在这个算法的解空间中的一个子集中搜索，目的是尽快地找到一个较好的解。而最优调度则是搜索这个算法的整个解空间，目的是获得最好的解。使用近似的次优调度算法必须能够判定所得到的解是否是可以被接受的，也就是说，必须能够确定最优解和次优解之间的近似程度。

启发式 ​

使用比较简明的规则和一些直觉的规则来进行调度。这些启发式的规则往往是不能证明其正确性，在特定情况下可能还是错误的，但是在绝大多数的情况下是能够被接受的。

一些常使用的启发式规则：

1. 相互依赖性较大的进程，由于它们之间常有比较多的进程通信应该分配到比较接近的执行节点上，可能的话，应该在同一个节点上。
2. 访问共享文件的进程应该分配到比较接近的执行节点上，可能的话，应该分配在文件服务员节点上。
3. 很少有内在关系的进程可以分布在不同的机器上。
4. 如果一个节点已经是重负载的，不应该向该节点分配另外一个进程。

静态调度 ​

任务优先图：节点表示执行时间，边表示启动后续任务所需时间间隔

任务交互作用图：节点表示执行时间，每条边一对数，第一个数表示两个任务在同一处理机上的通信开销，第二个数表示在不同处理机的通信开销

任务聚类 ​

$$\text{粒度} = \frac{\text{计算量}}{\text{通信量}}$$

粒度大->通信量小，潜在的并行小任务可能聚类进一个任务，分配给一个处理器->限制并行性

粒度小->进程切换和通信开销大->降低性能

在图模型中，任务聚类，即在给定的图模型中对小任务进行分类。任务聚类把任务图当作一个整体，将图中的小任务(节点)划分成不同的聚类，聚类中的小任务串行执行，不同的聚类之间并行执行。任务聚类中可以使用两种策略：

1. 将不相关的任务映射到一个聚类中；
2. 将DAG中一条优先路径上的任务映射到一个聚类中。

常见聚类算法

1. 关键路径聚类。关键路径(最长路径)的概念常常在垂直聚类中使用，即用在线性聚类中。应该清楚的是，依赖于任务优先图中关键路径的细粒度任务必须串行执行。
2. 消除通信延迟的聚类。消除通信的额外开销，把通信频繁的节点聚集成一类。通常的方法是将一个节点的后继节点与节点自身聚集成一类，只要总的执行时间不会被延长。
3. 任务复制。为了消除任务间的通信开销，将任务在处理机上进行复制有时是最有效的方法。它是任务划分的一个可选方法。任务复制不仅能保留程序最初的并行性，同时也能减少通信开销。
4. 其他技术。Kim和Browne的线性聚类技术，在每一步，计算量和通信量最大的有向路径上的节点聚集成一个单独的线性聚类，并且这些节点被从图中除去。对图中剩余的节点迭代执行这个过程，直到整个任务图已经全部被划分成一些聚类。Sarkar的内在化聚类方案，将每个节点最初放在一个单独的聚类中，并且以弧上通信开销的下降顺序考虑将图中的节点划分成一些聚类。这个算法不断地将两个聚类合并成一个更大的聚类，如果在合并过程中生成的更大聚类不会增加这个图的估计并行执行时间，那么这个合并过程就被接受。这个过程一直进行下去，直到不再需要合并为止。

基于任务优先图的任务调度 ​

甘特图

甘特图以处理器为纵坐标，以时间为横坐标。图中的每个方块表示进程在某个系统中的开始时间、持续时间和结束时间。处理器内的时间延迟和处理器间的时间延迟都能够在图中体现。

线性聚类

右图出现了两个独立任务在同一聚类中，所以是非线性聚类

分叉与合并

$$\text{粒度} = \frac{\text{最小计算量}}{\text{最大通信量}}$$

任务优先图的粒度为图内所有粒度的最小值

粒度 > 1，即为粗粒度，≤1为细粒度

对于粗粒度优先图，线性聚类优于非线性聚类

两种最优调度算法（假设通信代价可忽略，执行时间都一样）

1. 优先图为树结构
2. 只有两个处理器可用

两种情况都按最高层优先的方法进行调度

基于任务相互关系图的任务调度 ​

？没看懂

动态调度 ​

策略：

1. 启动策略的责任是决定谁应该激活负载平衡活动。
2. 转移策略决定一个节点是否在合适的状态参与负载转移。
3. 选择策略选择最适合转移最能起平衡作用的任务，并发送给合适的目标处理器。
4. 收益性策略量化系统中负载不平衡程度，并且作为系统负载平衡潜在受益的估计，评估系统负载平衡是否是有收益的。
5. 定位策略是寻找合适的节点共享负载。
6. 信息策略决定收集系统中其他节点状态信息的时机、收集的方法和收集的信息。

分类：

1. 全局的和局部的。局部负载平衡算法在相邻的节点间转移工作负载。全局负载平衡算法不仅在相邻节点间转移负载，还在全系统内计算负载，根据全局情况调整处理器负载。
2. 集中控制的和分散控制的。在集中控制算法中，中心控制器收集状态信息，做出负载平衡决策。分散控制算法把控制机制分散到全系统的各个节点。混合式负载平衡算法是集中控制和分散控制算法的折衷。
3. 不协作的和协作的。在不协作方法中，各个节点不知道系统中其他节点的状态，独立决定自己的定位和负载转移规则。在协作算法中，节点间相互配合来决定负载平衡决策。
4. 适应性的和非适应性的。在适应性算法中，负载平衡策略根据系统状态变化而改变；而非适应性方法中，这些策略是不变的。

设计决策：

1. 非抢先式的和抢先式的:抢先式的主要目的是负载共享，节点只分配新到达的任务，又称为任务放置(placement)。抢先式的算法的主要目的是充分利用系统资源，能够重新分配正在运行的任务，又称为进程迁移(migration)。
2. 采用何种信息策略。与信息策略有关的问题有：(a)周期性收集信息还是非周期性收集信息；(b)收集局部信息还是全局信息；©处理器负载指标。
3. 集中控制算法和分散控制算法：集中控制算法有一个中心处理器从系统中其他处理器收集负载信息。分散控制算法是通过每个处理器发送自己负载变化情况给所有处理器或者它的邻居来实现的。
4. 采用何种启动策略。启动策略有三种：发送者启动的、接受者启动的和对称启动的。
5. 资源复制。任务转移的时候，涉及到的文件和数据也必须被复制到目标处理器。为了减少转移的代价，常用的任务和数据可以事先被复制和分配到不同的处理器。
6. 进程分类。依据特征来区分进程类型。如果系统中运行的进程有很大的区别，它们就必须分在不同的类。当系统中有多个进程类型时，负载平衡算法必须考虑进程的类型，根据不同的类型做出改变。

使用参数：

1. 系统的规模。系统中处理器的数目是影响负载平衡决策的一个参数。
2. 系统负载情况。 需要避免颠簸现象。
3. 处理器的输入流量。进程可以以任何随机模式到达处理器，如果处理器能够测定自己的输入流量并且和其他处理器比较，它就能比较容易评估系统即时的负载水平，从而对任务转移做出更好的决策。
4. 转移的负载门限。系统中触发任务转移的负载门限是一个关键参数，因为选择不当会导致系统不平衡和任务转移的连锁反应。
5. 任务大小。一般来说，转移一个运行时间太短的任务是不恰当的。类似的，太大的进程或者涉及到大量数据和文件的进程最好在本地处理器上执行。
6. 管理成本。组成管理成本的主要因素是：处理器当前负载的测量、处理器决策使用的负载信息、决策发生的位置和处理器间任务的传送。
7. 负载平衡的视界。一个节点能够在其邻接节点范围内为一个任务寻找可能的目标节点，在其上运行该任务。这个邻接节点范围的直径称为视界(horizon)。这个参数设置了寻找目标节点过程中探查的邻接节点的数量。
8. 资源要求。任务对系统资源的要求会影响它的转移。需要较多资源的进程可能会持续等待资源变得可用，这就可能影响系统的响应时间。

全局动态调度机构 ​

主要目标：

1. 性能要求：调度机构占用整个系统的开销最小，它们不应该占用不使用此机构的应用程序的时间，也不应该使被调度的应用程序的执行产生大的延迟。
2. 支持的系统规模：应该能支持几百个甚至上千个工作站。
3. 容错：一个或几个机器崩溃时，系统的远程执行设备应该在几秒钟之后能够继续工作。
4. 公平性：不管分配作业到哪个机器上，为该作业提供的性能都是同样可接受的。

三个主要问题：

1. 有关负载的信息是如何传送的，使用公布的还是回答查询的办法？即选择哪一种信息策略。
2. 谁主动发起远程执行的请求，是作业进入的顾客节点(源节点)还是处理此作业的节点(服务员节点)？一个物理节点处理机可以是一个源节点，也可以是一个服务员节点。在服务员主动的情况下，此服务员主动寻找工作。这里所要解决的是选择什么样的启动策略。
3. 谁来决策为一个作业(程序)选择一个合适的执行主机，请求的发起者还是一个集中的服务员节点？这里要解决的是定位策略的问题。

集中式调度 ​

在系统中有一个中央调度服务员，负责搜集状态信息并做出全部调度决策。各机器周期性地向它发送状态更新报文，报告它们的负载信息；顾客向它发送远程执行请求。中央调度服务员根据负载情况，建立一个主机候选者的有序表，依次选择主机，对顾客的远程执行请求进行响应。使用中央调度服务员查询状态会减少报文传送数目。但是因为机器由于本地活动可以在任何时间改变其负载，所以将产生状态信息过时的问题。

解决集中式调度的容错问题的典型方法是提供多个备用服务员。

集中调度的最后一个问题是在何处运行调度程序。调度程序没有任何特殊要求，可放到任何空闲机器上，并可根据需要迁移。

分散式调度 ​

在全分散方案中，每个机器自己进行选择活动。它必须不断地记录整个系统状态或者当需要时查询系统状态信息。在前一种情况下，每个机器(即使是忙碌的机器)要定期地产生更新报文并向其他主机广播(公布)。而每个主机中维持一个主机状态表。在后一种情况下只有对主机选择有兴趣的那些主机才关心状态信息(查询)。采用查询方法，即每个需要获得空闲主机的顾客机发送查询报文请求得到当前状态信息，请求中包括所需资源的说明。该顾客从所有愿意成为候选主机的机器那里得到回答，并从中选取一个最合适的机器

两个要解决的问题。第一是查询者可能要求接收大量的、几乎是同时到来的回答报文， 以及 $N^2$ 报文的传送要消耗网络的带宽。第二是可能产生冲突。

第一个问题的解决方法：一个相当简单的办法是放宽选择主机的标准，它可以不是最佳的，即不是负载最轻的，但可以是较轻的、较好的。查询者只考虑全部回答报文中的一部分，扔掉其余部分。

第二个问题解决办法是在迁移程序前先发送一个执行请求，被选择机只对第一个请求回答并等待申请者传送被执行的程序。

混合式调度 ​

集中式方法支持的规模较大，但集中式方法可靠性较差，不易扩充。分散式方法具有较高可靠性，实现简单，容易扩充，但效率较低。

混合式调度结构中，每个工作站有一个局部调度程序，还有一个后台作业队列，用户提交的作业和远程作业都放到此队列中。有一个工作站除了局部调度程序和作业队列外，还有一个协调程序(协调者)。协调者定期(例如每两分钟)向各个工作站查询，看有哪些工作站可用作远程执行的源，哪些工作站后台作业队列中有作业等待处理。中央协调者为有后台作业等候的工作站上的调度程序分配空闲工作站资源。各工作站如果其队列中有多个后台作业，则由本地调度执行程序决定下次应执行哪个作业。

进程转移和远程执行 ​

目的是使由个人工作站组成的系统的计算资源容易共享：用户在执行若干相对独立的任务时，可把它们从某些重负载工作站移到另外一些轻负载工作站上加快完成。

进程转移的形式有两种：抢先方式和非抢先方式，非抢先方式又称为进程放置，抢先方式又称为进程迁移。进程放置是为进程选择一个执行节点，在此节点上启动此进程。进程迁移是把进程转移到一个较好的执行节点继续执行。

进程转移和远程执行的一般要求有以下两点：

1. 透明性。进程运行的结果与该进程在系统中什么地方执行无关。为了转移此进程不必用特定方式重新编写程序。也就是说，这些进程转移到远程执行环境后必须与在原地一样(名字、操作和数据，但不包括硬件)。
2. 有效性。迁移一个进程需要时间，支持该进程远程执行也需要时间，这些时间应尽量短。

判断是否值得进行进程迁移和远程执行：

1. 有多个计算量很大的进程在一个工作站上运行；
2. 运行时间远远超过在远程启动执行一个进程的时间；
3. 从所选择的远程节点上被驱逐的可能性很小；
4. 进程刚建立不久，还未来得及使用很多地址空间。

Sprite的进程迁移和远程执行设备

Sprite系统实现透明性的方法：当一个被迁移的进程调用一个与位置有关的系统调用(这种调用在不同位置执行可能产生不同的结果)时，该系统调用由RPC设备转发到此进程的基地节点执行。

Sprite系统把系统调用分成以下几类：

1. 和地址无关的，共有38个。远程节点处理与位置无关的系统调用。
2. 和地址有关的，有24个。基地节点为大多数和进程位置有关的系统调用服务，对进程的这种环境的任何操作都被转发给基地。
3. 合作的，有5个。在一些情况下，远程节点和基地节点必须合作处理一个系统调用。
4. 不可迁移的，有一个。这个调用把内核的地址空间的一部分变换到用户存储器中。一个远程进程不可能把存储器从内核变换到它的基地节点上，所以任何使用此调用的进程必须在调用完成前迁移到基地。

Sprite系统的进程迁移包括以下几个步骤：

1. 向目的节点发送一个RPC，确认是否允许迁移该进程。
2. 当要迁移该进程时，使用标准信号中断该进程的执行。
3. 传送该进程的“进程状态”，包括各寄存器的内容、用户标识符和小组标识符、信号处理信息、基地节点和该进程标识符。
4. 传送虚拟地址空间。把所有重写的页送到文件服务器，把对应的交换文件的页表和说明符送到目的节点。
5. 将该进程已打开的文件的说明符和当前工作目录打包并传送。
6. 发送一个RPC结束迁移，允许被迁移的进程在目的节点上恢复执行。
7. 最后，该进程在目的节点上恢复。

V系统中的可抢先的远程执行设备

V系统的可抢先远程执行设备使用预复制方法提高性能：

为了减少冻结时间，可使用预复制方法，在冻结前就多次复制全部地址空间，每次复制上次复制以来被修改的页。多次复制后被修改的部分仅剩下很少的部分，这时再冻结，把剩余部分复制过去。这样仅用最短时间冻结。

NEST中的透明的远程执行设备

NEST使用逻辑机的概念。它被定义为属于一个物理机的所有进程集合(包括本地的和远程的)。在逻辑机边界内透明地保持全部UNIX系统的能力，具体有以下几点：

1. 远程机上运行的远程进程所访问的文件都是原主机上的文件。
2. 远程进程能够向逻辑机边界内任何进程发送所有标准UNIX系统信号，也能接收来自逻辑机边界内任何进程的标准UNIX系统的信号。
3. 原有的UNIX进程组关系仍在逻辑机内保持。
4. 在逻辑机边界内保持原有的进程之间的父子关系。
5. 远程进程能以透明方式访问其远程终端，即原来登录的终端。