分布式系统中的处理机管理

1、1 1 进程调度进程调度1.1.进程的状态与切换进程的状态与切换 进程的状态可以分为活跃态与非活跃态两大类。进程的状态可以分为活跃态与非活跃态两大类。 运行态：所属线程正在占用运行态：所属线程正在占用CPUCPU运行运行 就绪态：具备运行条件，但未占有就绪态：具备运行条件，但未占有CPUCPU运行运行 等待态：由于自身原因不能运行，但传输尚未结束等待态：由于自身原因不能运行，但传输尚未结束 挂起态：由于自身原因不能运行，放弃所占用的资源挂起态：由于自身原因不能运行，放弃所占用的资源 原则上，统一进程的线程应该在同一原则上，统一进程的线程应该在同一CPUCPU上运行。上运行。 现在，线程是系统中

2、的调度单位。现在，线程是系统中的调度单位。 线程调度管理的方式线程调度管理的方式 核心管理模式：核心管理模式： 对每一个进程。核心为其建立一个线程调度表。同一个对每一个进程。核心为其建立一个线程调度表。同一个进程的线程可以并行。进程的线程可以并行。线线程程线线程程线线程程线线程程核核 心心 进程管理模式：进程管理模式： 在用户区内进程创建一个虚拟处理器（又称为进程在用户区内进程创建一个虚拟处理器（又称为进程的运行系统），对应一个物理的运行系统），对应一个物理CPU。线程可以在阻塞时调线程可以在阻塞时调用运行系统保留现场和挂起，运行系统负责调度线程运行。用运行系统保留现场和挂起，运行系统负责调度

3、线程运行。这样进程可以设定自己的调度策略，但效率较低。这样进程可以设定自己的调度策略，但效率较低。 现代分布式系统中，线程是独立的运行单位和调度单现代分布式系统中，线程是独立的运行单位和调度单位。位。2. 线程组织模型线程组织模型 线程工作的组织方式分为三种：派遣工作模型（在进程线程工作的组织方式分为三种：派遣工作模型（在进程中设立派遣进程负责选择工作线程运行）、小组模型（线中设立派遣进程负责选择工作线程运行）、小组模型（线程平等工作）和管道模型（流水线方式）。程平等工作）和管道模型（流水线方式）。 派遣模型派遣模型 派遣线程派遣线程工作线程工作线程邮邮 箱箱核核 心心共享共享cache进进

4、程程工作请求工作请求工作请求工作请求 小组模型小组模型 邮邮 箱箱核核 心心工作请求工作请求进进 程程共享共享cache工作请求工作请求 管道模型管道模型 邮邮 箱箱工作请求工作请求核核 心心进进 程程共享共享cache工作请求工作请求 动态模型动态模型 进程初启时只有一个线程，称为服务线程，向核心输进程初启时只有一个线程，称为服务线程，向核心输入进程的接口。入进程的接口。 核心准备调用数据借口，例如数据栈，供服务线程和核心准备调用数据借口，例如数据栈，供服务线程和客户线成共享。客户线成共享。 客户线程初启后，从核心输入这些接口。客户线程初启后，从核心输入这些接口。 客户线程调用过程时，将参数

5、入栈，将过程名存入指客户线程调用过程时，将参数入栈，将过程名存入指定寄存器，通过定寄存器，通过trap进入核心。进入核心。 核心查看知道是本地调用，将客户线程内存映射到服核心查看知道是本地调用，将客户线程内存映射到服务线程地址空间，启动服务进程，执行过程调用。务线程地址空间，启动服务进程，执行过程调用。 远程调用到来时，核心创建一个线程，将远程请求消远程调用到来时，核心创建一个线程，将远程请求消息映射到它的地址空间，线程相应服务请求，执行过程调息映射到它的地址空间，线程相应服务请求，执行过程调用，结束后自动消亡。用，结束后自动消亡。2 2 负载平衡与系统模型负载平衡与系统模型1.1.工作站模型

6、工作站模型 属于对称型模型，各结点是平等的。属于对称型模型，各结点是平等的。 负载平衡的要点负载平衡的要点之一是如何发现空载结点（潜在的计算服务器）。涉及三个之一是如何发现空载结点（潜在的计算服务器）。涉及三个问题：问题： 如何发现空载结点如何发现空载结点 远程进程如何透明地运行远程进程如何透明地运行 当本地进程需要运行时，如何处理当本地进程需要运行时，如何处理 服务器驱动服务器驱动 每个结点装备空载监测程序，监测自身。每个结点装备空载监测程序，监测自身。 设管理者，维护空载注册表，记录空载结点地址。设管理者，维护空载注册表，记录空载结点地址。 每个结点发现自己空载时，发消息给管理者，后者将其

7、每个结点发现自己空载时，发消息给管理者，后者将其地址记入空载注册表。地址记入空载注册表。 A结点需要分散计算负载，发远程命令询问管理者，后结点需要分散计算负载，发远程命令询问管理者，后者给它发送空载结点地址者给它发送空载结点地址B，A结点向结点向B发送远程任务，发送远程任务，B执行远程任务，负载增加，发消息要求管理者删去自己。执行远程任务，负载增加，发消息要求管理者删去自己。 为避免几个结点同时发现某空载结点引起冲突，可引入二为避免几个结点同时发现某空载结点引起冲突，可引入二次确认：请求者向空载结点发送请求确认消息，空载结点次确认：请求者向空载结点发送请求确认消息，空载结点选择其中一个结点为雇

8、主，要求管理者从空载表中删去自选择其中一个结点为雇主，要求管理者从空载表中删去自己，向雇主发回确认消息。未接到确认的结点只好再次向己，向雇主发回确认消息。未接到确认的结点只好再次向管理者询问。管理者询问。管理者管理者注册程序注册程序空载注空载注册表册表请求者请求者空载结点空载结点远程过程远程过程远程过程远程过程1. 空载注册空载注册2. 请求空载结点请求空载结点3. 回复空载结点回复空载结点4. 要求确认要求确认5. 注销空载注销空载6. 确认确认7. 设置运行环境设置运行环境8. 启动远程进程启动远程进程9. 进程运行进程运行10. 进程结束进程结束11. 返回结果返回结果 客户驱动客户驱动

9、 结点需要分散负载时，广播请求，指明具体要求。结点需要分散负载时，广播请求，指明具体要求。 其他结点收到后，根据情况自行判断，同意者回复。其他结点收到后，根据情况自行判断，同意者回复。 收到所有回复后，选取负载最小者，分散计算负载。收到所有回复后，选取负载最小者，分散计算负载。请求者请求者其他结点其他结点其他结点其他结点其他结点其他结点其他结点其他结点11112341广播分散负载请求广播分散负载请求234应答：负载空应答：负载空发送运行环境发送运行环境 分散负载注意问题分散负载注意问题 远程进程的运行环境必须与本地环境一样远程进程的运行环境必须与本地环境一样 远程进程运行中的某些系统调用必须发

10、回本地执行，远程进程运行中的某些系统调用必须发回本地执行，如键盘、鼠标操作等人机交互工作如键盘、鼠标操作等人机交互工作 涉及时间处理要十分慎重，因为机器时间可能不同涉及时间处理要十分慎重，因为机器时间可能不同 空载结点本地进程要求运行时的策略空载结点本地进程要求运行时的策略 不理，等远程进程完成：简单但不友好不理，等远程进程完成：简单但不友好 立即杀死远程进程，让位于本地进程：简单但造成计立即杀死远程进程，让位于本地进程：简单但造成计算浪费，有时会产生完整性问题（如文件），需要额外维算浪费，有时会产生完整性问题（如文件），需要额外维护工作护工作 先给警告，留一段善后处理时间，然后杀死远程进程先

11、给警告，留一段善后处理时间，然后杀死远程进程 注意：远程进程执行完成以后，接点必须恢复到空载时注意：远程进程执行完成以后，接点必须恢复到空载时的状况。的状况。 包括：包括： 清除所有远程进程及其子进程清除所有远程进程及其子进程 清除这期间的邮箱内容、网络连接以及其它系统级数据清除这期间的邮箱内容、网络连接以及其它系统级数据 清除这期间的临时文件清除这期间的临时文件 清理清理Cache 做好以后可能到来的与远程进程有关的消息的拒绝预防做好以后可能到来的与远程进程有关的消息的拒绝预防工作工作2. 处理器池模型处理器池模型 单服务器基本排队模型单服务器基本排队模型 令用户产生请求令用户产生请求 /秒

12、，处理机能处理请求秒，处理机能处理请求 /秒，平均周转时间秒，平均周转时间T 1/( - )如果服务器处理能力加大，有如果服务器处理能力加大，有n个个CPU，处理能力将为处理能力将为n ，而请求率同步，而请求率同步扩大为扩大为n ，平均周转时间将为，平均周转时间将为1/(n -n ) = T/n 原因：减少了原因：减少了CPU的空闲率的空闲率 排队论的结论是反对分布式计算的重要论据，但分布式的潜在好处（代排队论的结论是反对分布式计算的重要论据，但分布式的潜在好处（代价、灵活、方便、坚固价、灵活、方便、坚固）也是不可替代的。）也是不可替代的。M1M2M3M4M5S用用 户户用用 户户用用 户户

13、分布式系统任务分配示意分布式系统任务分配示意 假定：所有机器兼容，全连通。假定：所有机器兼容，全连通。 优化目标：平均相应时间最小化，响应率最小化优化目标：平均相应时间最小化，响应率最小化 响应率响应率 = 进程实际运行时间进程实际运行时间/在无负载标准在无负载标准CPU上的运行时间上的运行时间 实际运行时间包括排队、调度、通信、计算的花费的时间实际运行时间包括排队、调度、通信、计算的花费的时间 任务类型：可迁移任务，不可迁移任务任务类型：可迁移任务，不可迁移任务 考虑：考虑： 任务间的通信开销（任务间的通信开销（ITC）问题问题 m1m2m3m4m5SP1P2Pn 基于图论的任务分配策略基于

14、图论的任务分配策略 通信图通信图 图中：圆圈表示任务，旁边的数字表示计算工作量；连线表示有通图中：圆圈表示任务，旁边的数字表示计算工作量；连线表示有通信，连线的权（可以是信，连线的权（可以是 ，显然两个任务不能异地计算），显然两个任务不能异地计算）表示开销。表示开销。 假定同一个结点上的两个任务的通信量为零。任务优化的目标是处假定同一个结点上的两个任务的通信量为零。任务优化的目标是处理开销和理开销和ITC之和最小。之和最小。ABCD512 863639 数据结构定义数据结构定义 分配矩阵分配矩阵 X 1 若任务若任务mi分配给处理机分配给处理机Pk xik = 0 若任务若任务mi不在处理机不

15、在处理机Pk上上 处理开销矩阵处理开销矩阵Q qik表示任务表示任务mi在处理机在处理机Pk上的处理开销，若为上的处理开销，若为 ，表示，表示mi不不能在能在Pk上运行上运行 ITC开销矩阵开销矩阵C cij表示任务表示任务mi和和mj之间的之间的ITC开销，若为开销，若为0，表示两个任务，表示两个任务在同一处理机上在同一处理机上 于是，于是，ITC总开销总开销T = qkixik + cijxikxjhkihkji 其中，第一项是每个任务在其分配的处理机上的运行开销，第二其中，第一项是每个任务在其分配的处理机上的运行开销，第二项代表不同处理机上任务间的项代表不同处理机上任务间的ITCITC开

16、销。开销。 以上图为例，任务以上图为例，任务C和和D之间通信量为无穷大，显然应该分配在一之间通信量为无穷大，显然应该分配在一个结点上。如有两个结点，那么分配将是个结点上。如有两个结点，那么分配将是 ITC ITC开销：开销： A B C D 处理开销：处理开销： A B C D A 0 0 8 6 0 8 6 处理机处理机1 3 9 6 3 1 3 9 6 3 B 0 0 12 0 12 0 处理机处理机2 3 9 6 3 2 3 9 6 3 C 8 12 0 0 0 D 6 0 0 0 A，BC，D 显然，优化的方向是力求使得目标函数显然，优化的方向是力求使得目标函数X最小。最小。 例：例：

17、 一张完全图一张完全图利用最小分割算法得到分配结果为利用最小分割算法得到分配结果为 P1：A，B，C，D，E； P2：F； 计算复杂性为计算复杂性为O(m2n2)P1P2AFCBED6124115812354102465443分割线分割线815 评论：评论： 最小分割法以图论为基础，可以作为分配负载的一种方最小分割法以图论为基础，可以作为分配负载的一种方法。通过对目标函数求极小值的方法进行。法。通过对目标函数求极小值的方法进行。优点：简明优点：简明缺点：计算复杂性较大，只能处理缺点：计算复杂性较大，只能处理2、3个处理机的情形个处理机的情形 不能考虑处理机负载平衡问题以及由此带来的排队延不能考

18、虑处理机负载平衡问题以及由此带来的排队延迟、存储限制、实时（即时）要求等问题。迟、存储限制、实时（即时）要求等问题。 0 01 1策略策略 指导思想：将任务分配概括为一个优化问题。指导思想：将任务分配概括为一个优化问题。 数据结构数据结构 分配矩阵分配矩阵X，处理开销矩阵处理开销矩阵Q， 引入卷宗矩阵引入卷宗矩阵V，vij表示表示mi向向mj发送的数据卷宗发送的数据卷宗 引入距离矩阵引入距离矩阵D，dij表示处理机表示处理机Pi与与Pj的距离，代表的距离，代表互连状况（交通条件），为互连状况（交通条件），为则表示不连通，于是则表示不连通，于是dij vij就是就是两个任务的两个任务的ITC开销

19、了。开销了。 目标函数目标函数 T = qkixik + w vijdijxikxjh kihk j0，用随机方法在用随机方法在Pj上选取一个任务迁移到上选取一个任务迁移到Pj+1上，否则上，否则不做任何动作。重复进行，直到所有的不做任何动作。重复进行，直到所有的Dj都不大于都不大于0；必要时可对合一的；必要时可对合一的任务进行分解。任务进行分解。 若若Dm大于大于0，失败！，失败！评论：评论： 算法以追求次优解为目标，合一时采用算法以追求次优解为目标，合一时采用“贪心贪心”策略，不一定会实策略，不一定会实现最佳分配；现最佳分配； 调整过程采用随机迁移，有盲目性；调整过程采用随机迁移，有盲目性

20、； 成功的合一可以减少通信开销，成功的调整可使负载基本平衡，有成功的合一可以减少通信开销，成功的调整可使负载基本平衡，有利于提高系统吞吐量；利于提高系统吞吐量； 合一阶段计算复杂性合一阶段计算复杂性O(n3)，调整阶段调整阶段O(m2) ，可以忍受；可以忍受； 合一结束后，任务数目可能大于处理机数，需将多余任务分配给各合一结束后，任务数目可能大于处理机数，需将多余任务分配给各处理机，甚至需要分解任务，这时寻找通信量最大的任务对工作量大；处理机，甚至需要分解任务，这时寻找通信量最大的任务对工作量大； 在特殊情况，如存在附属任务（某个任务必须分给特定的一个或数在特殊情况，如存在附属任务（某个任务必

21、须分给特定的一个或数个处理机），合一时以附属任务为中心形成组合任务，先分配对处理机个处理机），合一时以附属任务为中心形成组合任务，先分配对处理机有特殊要求的组合任务，再分配包含其他附属任务的组合任务，最后分有特殊要求的组合任务，再分配包含其他附属任务的组合任务，最后分配不含附属任务的组合任务。调整阶段先排除负载平衡的处理机，在轻配不含附属任务的组合任务。调整阶段先排除负载平衡的处理机，在轻载和重载处理机之间进行调整。载和重载处理机之间进行调整。 改进后的启发式算法改进后的启发式算法 数据结构定义数据结构定义 系统中有系统中有n个处理机，个处理机，m个计算任务（个计算任务（mn）。）。 任务间通

22、信开销矩阵任务间通信开销矩阵Cmm： Cmm = cij | 1im，1jm ，为任务为任务ti，tj之间的通信开销之间的通信开销 任务执行开销矩阵任务执行开销矩阵Qmn： Qmn = qij | 1im，1jn ，为为ti在在Pj上的运行开销上的运行开销 任务优先矩阵任务优先矩阵Amn： aij = 1 表示任务表示任务ti不能分配给处理机不能分配给处理机Pj，否则为否则为0 任务互斥矩阵任务互斥矩阵Emm： eij = 1 表示任务表示任务ti与与tj不能分配给同一台处理机，否则为不能分配给同一台处理机，否则为0 任务分配矩阵任务分配矩阵Xmn： xij = 1 表示任务表示任务ti已经分

23、配给处理机已经分配给处理机Pj ，否则为，否则为0 处理机处理机Pk上的负载：上的负载： Lk = w qikxik，其中常数其中常数w w用来调整执行开销与通信开销的量纲用来调整执行开销与通信开销的量纲 某个任务与组合任务中的任一分任务互斥，即为与该组合任务互某个任务与组合任务中的任一分任务互斥，即为与该组合任务互斥。斥。 算法算法 将附属于同一处理机的任务合一，得到压缩后的矩阵将附属于同一处理机的任务合一，得到压缩后的矩阵A和和E, ,A的行数为的行数为m，E的行列数均为的行列数均为m，记为，记为Am n和和Em m。同样，。同样，Q和和C也变为也变为Qm n，Cm m，它们的元素值也会相

24、应改变。，它们的元素值也会相应改变。 对对Cm m的每一行进行排序，查找最大通信量的任务对的每一行进行排序，查找最大通信量的任务对 对处理机按现有负载建栈，栈顶为负载最轻的对处理机按现有负载建栈，栈顶为负载最轻的P Pk k。若栈非空，。若栈非空，选选P Pk k，否则转，否则转。i=1m 若所有任务已分配完，转若所有任务已分配完，转，否则，若，否则，若Pk有附属任务，记该任有附属任务，记该任务为务为t,若若Pk无附属任务，任选一个未分配任务为无附属任务，任选一个未分配任务为t。 寻找与寻找与t由最大通信量的未分配任务由最大通信量的未分配任务tj，若加入后仍满足：，若加入后仍满足： 实时限制实

25、时限制Rk，存储限制，存储限制Sk； aij = 0= 0，即，即tj可以分配到可以分配到Pk上；上； tj不与任何已分配到不与任何已分配到Pk上的任务互斥；上的任务互斥； 将将tj分配到分配到Pk上。否则选下一个与上。否则选下一个与t有最大通信量的未分配任务有最大通信量的未分配任务tj，重复，重复。若无法找到这样的。若无法找到这样的tj，若可分配就将，若可分配就将t分配给分配给Pk。 若没有这样的任务若没有这样的任务t和和tj能分配给能分配给Pk，将，将Pk从栈中删去。否则从栈中删去。否则修改修改Pk的负载，转的负载，转 。 检查剩余任务，如有，设当前任务为检查剩余任务，如有，设当前任务为t

26、i，其优先任务为，其优先任务为tj，若，若tj已经分配给已经分配给Pk，则从，则从Pk中取出中取出tj，将，将ti分配给分配给Pk，并寻找可以接收，并寻找可以接收tj的的处理机。若剩余任务不能分配给任何处理机，分配失败，退出。处理机。若剩余任务不能分配给任何处理机，分配失败，退出。 计算处理机计算处理机Pk（k=1,2,，n）的负载）的负载Lk并求出平均负载并求出平均负载L，定，定义义rk = Lk/L。 若若1-drk1+d ，Pk为平衡；为平衡； 若若rk 1-d，Pk为轻载；为轻载； 若若rk 1+d，Pk为超载；为超载； 去掉分配给平衡处理机的任务，将轻载处理机上的任务合一为一去掉分配

27、给平衡处理机的任务，将轻载处理机上的任务合一为一个组合任务。以轻载、超载处理机上的任务集合为对象，转个组合任务。以轻载、超载处理机上的任务集合为对象，转重新建重新建栈。若此次分配未引起负载变化，算法终止。栈。若此次分配未引起负载变化，算法终止。 基于遗传算法和模拟退火算法的任务分配算法基于遗传算法和模拟退火算法的任务分配算法 数据结构数据结构 建立一个五元组建立一个五元组 = =（ T， ，Q，C，X ） 其中其中T为任务集合；为任务集合；“ ”为为T上的优先关系，上的优先关系，ti tj 表示表示ti必须在必须在tj执行之前完成；执行之前完成；Q为为mm矩阵，矩阵，qij表示任务表示任务ti

28、在处理机在处理机Pj上的执行时上的执行时间；间；C是一个是一个mn矩阵，矩阵，Cij表示任务表示任务ti与任务与任务tj的通信开销；的通信开销；X是一个是一个mn的任务分配矩阵，的任务分配矩阵，xij=1=1表示表示ti分配到处理机分配到处理机Pj上，否则为上，否则为0 0。 设计目标函数设计目标函数cost，例如，例如 cost = (qik xik+w ckr xik xjr) 其中常数其中常数w w用来调节量纲差异用来调节量纲差异 i=1 k=1mnr=1 j=1K-1 i-1 迭代过程迭代过程 进行初始化，随机生成一个初始任务分配集合。例如：进行初始化，随机生成一个初始任务分配集合。例

29、如：处理机处理机任务任务P0P1P1t1t2t3t4t5t6t7110000000110000000111 描述与生成一个初始任务分配集合描述与生成一个初始任务分配集合TA。 其中，特定的任务分配方案用（其中，特定的任务分配方案用（S，R1.n）表示。其中，）表示。其中，S 是一个是一个 log2n m 的二进制串，每个的二进制串，每个 log2n 位称为一节，自左到右的第位称为一节，自左到右的第i节就表节就表示任务示任务ti所在的处理机号码。上例中，所在的处理机号码。上例中，S = 00 00 01 01 10 10 10。R是一个是一个有有n个分量的链表数组，每个分量的类型为个分量的链表数

30、组，每个分量的类型为m元整数数组，自左向右表示元整数数组，自左向右表示任务执行的顺序。假定上例中的优先次序为任务执行的顺序。假定上例中的优先次序为t1 t2，t4 t5，t6 t7，这样，这样R为：为：R0：12，R1：34，R2：567（或（或675，或，或657，因为只有，因为只有6、7有次序有次序关系）。关系）。 这样，这样，TA1.S = 00 00 01 01 10 10 10； TA1,R =（ 12 34 567） TA2.S = 00 00 01 01 10 10 10; TA2.R =（ 12 34 675） TA3.S = 00 00 01 01 10 10 10; TA3

31、.R =（ 12 34 657） 于是，可以选取若干分配方案，形成初始任务分配集合：于是，可以选取若干分配方案，形成初始任务分配集合： TA = S，R1.n 设置退火算法中的初始温度设置退火算法中的初始温度temp0和收敛率和收敛率 （0 1），温度），温度tempi+1 = tempi，逐步降低。这里，逐步降低。这里，i既代表第既代表第i次迭代，也代表遗传次迭代，也代表遗传算法中的地算法中的地i代个体。代个体。 一般在任务量较大的情形，一般在任务量较大的情形，temp0可以取可以取1000， temp 取为取为1， 取取0.9，效果较好。，效果较好。 进行迭代循环。对初始任务分配集合中的方

32、案采用交叉繁殖、变进行迭代循环。对初始任务分配集合中的方案采用交叉繁殖、变异等方法，形成新一代分配方案集合，不断进行。异等方法，形成新一代分配方案集合，不断进行。 交叉繁殖交叉繁殖 对父代的两个分配方案中对父代的两个分配方案中S的某些节进行替换，选取其中的优的某些节进行替换，选取其中的优良者（良者（cost较小）插入分配集合，形成第二代分配集合。较小）插入分配集合，形成第二代分配集合。 例例 两个父代方案：两个父代方案： TA1.S = 00 00 01 01 10 10 10； TA1.R =（12 34 567） TA2.S = 01 01 01 00 10 00 10； TA2.R =（

33、46 123 57 ） 用用TA1.S中的中的1、3、6节替换节替换TA2.S中的相应节，形成新方案：中的相应节，形成新方案： TA3.S = 00 01 01 00 10 10 10； TA3.R = （ 14 23 567） 计算计算 cost = cost(TA3) cost(TA2)： 0 表示新方案优于原方案，将表示新方案优于原方案，将TA3插入新的分配集合；插入新的分配集合； 0表示原方案优于新方案，计算概率值：表示原方案优于新方案，计算概率值： prob = exp | cost/k temp | ，式中，式中k为波尔兹曼常数，为波尔兹曼常数，temp为为当前温度；当前温度； 由

34、系统产生（由系统产生（0，1）之间的随机数）之间的随机数rand，若，若probrand，将，将新方案加入分配集合，反之舍弃。新方案加入分配集合，反之舍弃。 变异变异 对某些方案作变异处理，形成新方案。如对对某些方案作变异处理，形成新方案。如对TA.S某些节求反、某些节求反、互换处理任务等。变异不会造成个体数量的变化。每次变异后，对一互换处理任务等。变异不会造成个体数量的变化。每次变异后，对一个原方案只保留一种有效的变异方案。个原方案只保留一种有效的变异方案。 通过这种方法，可以得到比较理想的分配方案。通过这种方法，可以得到比较理想的分配方案。 基于有向任务图的调度策略基于有向任务图的调度策略

35、 假定：已知每个任务的执行时间，任务之间的时序假定：已知每个任务的执行时间，任务之间的时序关系、任务间的通信量、可使用计算机的数目；关系、任务间的通信量、可使用计算机的数目；分布式系分布式系统中有统一的时钟、结点同构（从而保证每个任务在不同统中有统一的时钟、结点同构（从而保证每个任务在不同计算机上的处理时间相同、通信开销固定）计算机上的处理时间相同、通信开销固定）；计算任务除；计算任务除通信以外的资源都可以从本机上获得。通信以外的资源都可以从本机上获得。 步骤步骤 生成非循环的任务有向图生成非循环的任务有向图 G = V，E，e，c T14T23T37T492522 上图中，上图中， 结点集合

36、结点集合 V = T1，T2，T3，T4 有向边集合有向边集合 E = (T1,T2)，(T1,T3)，(T2,T4)，(T3,T4) 运行开销集合运行开销集合 e = 4，3，7，9 通信开销集合通信开销集合 c = 2，5，2，2 任务复制任务复制 使任务在两个以上的计算机上有执行副本。使任务在两个以上的计算机上有执行副本。T13T27T3276 上图中，三个任务在两个计算机上有三种分配方案（未复制）：上图中，三个任务在两个计算机上有三种分配方案（未复制）： T1T1T1T2T2T2T3T3T367 第一种情况：总时间第一种情况：总时间11 第二种情况：总时间第二种情况：总时间17 第三种

37、情况：总时间第三种情况：总时间12（在一个计算机上）（在一个计算机上） 如果进行任务复制：如果进行任务复制：T1T1T3T2总时间：总时间：10任务复制将带来好处任务复制将带来好处 计算最早开始时间计算最早开始时间 贪心函数贪心函数f：假定假定C是包含结点是包含结点v以及它的父结点以及它的父结点 1， 2， 3， k 的聚集。定义的聚集。定义 f ( 1， 2， 3， k )为全部完成为全部完成 1， 2， 3， k 的最早可能结束时间。的最早可能结束时间。定义定义s ( v )为结点为结点 v 的开始执行时间。显然：的开始执行时间。显然： s ( v ) f ( 1， 2， 3， k ) =

38、 f ( C v ) 考虑：考虑：T14T22T32T44贪心函数贪心函数 f ( C T4 ) = 0 + 4 + 2 = 6只有只有T1，T3，T4分配在同一个计算机分配在同一个计算机上才能达到：上才能达到：868 最大弦值函数最大弦值函数maxg：非循环优先图中的边非循环优先图中的边( u,w ) E，定义弦值函数定义弦值函数 g ( u,w ) = s ( u ) + e ( u ) + c ( u,w )； 这里这里 s (u) 是结点是结点u u的最早开始时间，的最早开始时间，e(u)e(u)是是 u的运行时间，的运行时间，c ( u,w )是是u，w的通信开销。的通信开销。 最大

39、弦值函数最大弦值函数macg(C)定义为由不属于定义为由不属于C的节点到的节点到C中中节点的最大弦值。节点的最大弦值。 T14T22T32T4451令令 C = T3，T4，maxg（C）= 9 在一个给定的分配方案里，节点在一个给定的分配方案里，节点v的最早开始时间的最早开始时间 sv f（Cv）；）； 在上例中，在上例中，T4的最早开始时间为的最早开始时间为11。 计算聚集的算法计算聚集的算法 令结点集合令结点集合G，刚开始时，所有结点均未作标记。刚开始时，所有结点均未作标记。 取取G中未标记结点中未标记结点v； 若若v未根结点，作标记后转未根结点，作标记后转 ； 令令C为空，为空，v加入

40、加入C，计算计算 s = maxg ( C )； 选择具有最大弦值的选择具有最大弦值的( u,w )，其中其中u C，且且u为第一次被选择，为第一次被选择， w C，C = C + u ，若无转若无转 ； 若若maxg 、f ( C-v )均不大于均不大于S， 则则S = max( maxg(C) , f( C v)），），否则否则C = C u ，转转 ； C = C u 输出输出C和和v，对对v做标记，若做标记，若G中为全部标记转中为全部标记转 ，否则结束。，否则结束。 评述：评述： 总思路：对任一非根结点，计算其最大聚集弦值，找出满总思路：对任一非根结点，计算其最大聚集弦值，找出满足该弦

41、值得一对结点。尝试将聚集外的结点加入该聚集，足该弦值得一对结点。尝试将聚集外的结点加入该聚集，看能否降低其最大弦值，若能则继续，否则去掉加入的结看能否降低其最大弦值，若能则继续，否则去掉加入的结点，输出聚集。点，输出聚集。例例T110T35T29T45T55T661412643起始，起始，C中有中有T6，这时，这时maxg(C) = 41；第一次循环结束，第一次循环结束，C = T5,T6 , maxg(C) = 33；第二次循环开始，第二次循环开始，u = T4，取，取u = T4， 则则f ( C T4 ) = 27，送入，送入s；加入加入T4，则，则maxg(C) 21 该算法对每一个非

42、根结点都会输出一个聚集，若某一聚该算法对每一个非根结点都会输出一个聚集，若某一聚集为另一个聚集的子集，则删去，最后得到若干相互没有集为另一个聚集的子集，则删去，最后得到若干相互没有包含的狙击。若聚集的数目不大于计算机的数目，为每一包含的狙击。若聚集的数目不大于计算机的数目，为每一个聚集分配一个计算机，否则根据情况再进行调整。个聚集分配一个计算机，否则根据情况再进行调整。 在上例中，如果有两台计算机，那么分配方案：在上例中，如果有两台计算机，那么分配方案： T2T4T5T6T1T3若有三台计算机，分配方案改为：若有三台计算机，分配方案改为：T2T4T1T3T5T63. 调度问题调度问题 正常情况

43、下，分布式系统中的各结点机有自己的本地调正常情况下，分布式系统中的各结点机有自己的本地调度程序，负责调度本机上的任务进程。度程序，负责调度本机上的任务进程。 问题：问题： 在需要进行远程通信时，各自计算机上的独立调度可能在需要进行远程通信时，各自计算机上的独立调度可能会影响系统的性能。会影响系统的性能。 例例 两个节点的系统，每个结点各有两个进程，结点两个节点的系统，每个结点各有两个进程，结点1有进程有进程A，B：结点：结点2有进程有进程C，D。两个结点各自采用分时。两个结点各自采用分时方式调度方式调度，时间片为方式调度方式调度，时间片为100ms。 时间片时间片处处 理理 机机0 10123

44、45ACBDCACABDDB 在时间片在时间片0 0，A A启动后立即向启动后立即向D D发出远发出远程调用，自己等待结果；但处理机程调用，自己等待结果；但处理机1 1上上C C正在运行。到第二个时间片，正在运行。到第二个时间片，D D立即立即处理远程调用并返回结果，但此时处理远程调用并返回结果，但此时A A已已经不在运行状态（经不在运行状态（B B在运行）在运行） 由于通信与运行不同步，将导致处由于通信与运行不同步，将导致处理机无谓等待。理机无谓等待。 解决办法解决办法1： 处理机采用时间片轮转方法时，将进程按通信关系编组，尽可能处理机采用时间片轮转方法时，将进程按通信关系编组，尽可能将处于

45、同一通信组的进程安排在相同时间片里运行。将处于同一通信组的进程安排在相同时间片里运行。 问题：远程调用发生的时机是随机的，很难做到准确问题：远程调用发生的时机是随机的，很难做到准确。 解决办法解决办法2： 处理机调度采用分时和可抢占方法相结合。当一个远程调用到来时，处理机调度采用分时和可抢占方法相结合。当一个远程调用到来时，被调用进程所在的处理机将当前运行进程挂起，调度相应进程运行；被调用进程所在的处理机将当前运行进程挂起，调度相应进程运行；调用结束后再恢复原进程运行完剩余的时间片。处理远程调用不占进调用结束后再恢复原进程运行完剩余的时间片。处理远程调用不占进程的时间片。程的时间片。 好处：通

46、信量较大的进程可以在运行时间上有所优待，以保证与其好处：通信量较大的进程可以在运行时间上有所优待，以保证与其通信的它机进程正常运行。通信的它机进程正常运行。 缺点：进程间切换可能过于频繁，影响处理机的有效利用率。缺点：进程间切换可能过于频繁，影响处理机的有效利用率。3 3 系统容错系统容错1.1.需要讨论的问题需要讨论的问题 设备故障的两种情况设备故障的两种情况 fail and stop Byzantine 容错的通常做法容错的通常做法 冗余技术，包括信息冗余、时间冗余和物理设备的冗冗余技术，包括信息冗余、时间冗余和物理设备的冗余。余。 信息冗余：增加效验码、镜像存放、多副本等信息冗余：增加

47、效验码、镜像存放、多副本等 时间冗余：必要的重复执行，如原子事务技术等时间冗余：必要的重复执行，如原子事务技术等 物理冗余：增加设备，包括主动备份、被动备份物理冗余：增加设备，包括主动备份、被动备份 2. 主动备份主动备份 对对fail and stop类型故障比较有效类型故障比较有效 容错级别：容错级别： 系统称为系统称为K级容错，是指级容错，是指k个部件出现故障，系统仍能个部件出现故障，系统仍能正常工作，需要配备正常工作，需要配备K+1套设施。套设施。 对服务器，设置对服务器，设置K+1个，要求每个个，要求每个ClientClient的请求按照的请求按照相同的（服务器）次序执行并应答，称为

48、原子广播。但在相同的（服务器）次序执行并应答，称为原子广播。但在网络环境很难实现。网络环境很难实现。 方法方法1 1：对远程请求实行全局编号，需要一台编号服务器实现编号：对远程请求实行全局编号，需要一台编号服务器实现编号与分发，集中式弊病。与分发，集中式弊病。 方法方法2 2：使用逻辑时钟，请求加盖时间邮戳。但有麻烦：如何知道：使用逻辑时钟，请求加盖时间邮戳。但有麻烦：如何知道 还有没有更早的请求正在路上？还有没有更早的请求正在路上？ 2. 被动备份被动备份 指定一台设备为主设备，处理一切有关的事务，其它同指定一台设备为主设备，处理一切有关的事务，其它同类设备为备份设备。只有当主设备故障时，才

49、由备份机接类设备为备份设备。只有当主设备故障时，才由备份机接替工作。替工作。 正常情况下，运行策略简单：消息秩序相主服务器发送，正常情况下，运行策略简单：消息秩序相主服务器发送，不必向整个服务器群发送，次序问题基本上不存在。而且不必向整个服务器群发送，次序问题基本上不存在。而且备份机也比较节省。备份机也比较节省。 clientPrimaryserverbackupserver 发送请求发送请求 工作，完成请求任务工作，完成请求任务 发送更新要求发送更新要求 工作，完成更新工作，完成更新 确认，完成更新确认，完成更新 返回结果返回结果 在执行一个在执行一个RPC过程中，服务器故障时刻分析：过程中，服务器故障时刻分析： 在在以前，不会有影响，以前，不会有影响，client发现响应超时重新请求，再三请求未发现响应超时重新请求，再三请求未果，确认服务器故障，转向备份服务器；果，确认服务器故障，转向备份服务器； 在在、阶段，同上面情况，备份机接替工作，完成服务；阶段，同上面情况，备份机接替工作，完成服务； 在在以后，以后，完成前，备份机接替工作。完成前，备份机接替工作。 系统运行过程中，备份机与主机不断通信，询问是否正常。系统运行过程中，备份机与主机不断通信，询问是否正常。 改进方法：主机与备份机共享磁盘，采用磁盘镜像或交改进方法：主机与备份机共享磁盘，采用磁盘镜像或交换式磁盘两种方法