《6第六章任务分配与负载平衡.ppt

北京邮电大学 高级操作系统 北京邮电大学 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 北京邮电大学 Outline 第六章 任务分配与负载平衡 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 北京邮电大学 第六章 任务分配与负载平衡 6.1 任务分配 6.2 负载平衡 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 北京邮电大学 6.1 任务分配 任务 若干个模块构成一个任务，一个任务是单一的处理实体。 任务分解 把一个提交的任务划分成若干个独立的，具有最小IMC的模型。 IMC:每对模块间的数据传递。 IPC:处理机间的通信。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 北京邮电大学 6.1 任务分配 任务划分 粒度大，降低并行度，粒度小，进程切换和通信的开销就会增加。 划分方法 水平或垂直划分：在给定的任务优先图中水平或垂直划分；关键路径（最长路径） 通信延迟最小划分：把通信频繁的节点归成一类。 任务复制 在各个处理机节点上复制任务来降低通信开销。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 北京邮电大学 6.1 任务分配 任务分配 把这些模块分配给处理机，使它们由于处理机间的通信引起的开销最小。 一般算法假设 存储容量无限 每个处理机节点有相同的处理能力 忽略网络拥塞 评价准则 CPU的利用率最大化 平均响应时间最小化 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 北京邮电大学 6.1 任务分配 常见分配算法或策略 基于图论的分配策略 0-1程序设计策略 “合一 ——阈值”启发式分配算法 改进的启发式分配算法 基于进化（演化）算法的策略 遗传算法 模拟退火算法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 北京邮电大学 6.1 任务分配 遗传算法求解方法 1、编码方法(Encoding) 用一个n+1位的二进制串来表示： 00000 11111 2、初始化群体(Initialize) 随机生成初始化的串群体。在串群体中，串长度都是相同的，串长为需要分配的文件数。群体的大小根据需要(要求的分配时间等)，按经验或实验给出。 分布均匀的二进制串能使算法更加有效。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 北京邮电大学 6.1 任务分配 3、选择 (Selection) 借用达尔文的生物进化论中的自然选择(Natural Selection)思想，按照“适者生存”的原则对串进行复制。用适应度函数计算每个串的适应值，选择适应值高的串，生成下一代，去掉适应值差的串。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 北京邮电大学 6.1 任务分配 4、交叉 (Crossover) 交叉是两个串按照一定的概率(交叉概率P