任务分配与负载平衡.ppt

高级操作系统高级操作系统北京邮电大学北京邮电大学2024/9/9北京邮电大学北京邮电大学Outline第六章第六章 任务分配与负载平衡任务分配与负载平衡北京邮电大学北京邮电大学第六章第六章 任务分配与负载平衡v6.1 任务分配任务分配v6.2 负载平衡负载平衡北京邮电大学北京邮电大学6.1 任务分配v任务任务§若干个模块构成一个任务，一个任务若干个模块构成一个任务，一个任务是单一的处理实体是单一的处理实体v任务分解任务分解§把一个提交的任务划分成若干个独立把一个提交的任务划分成若干个独立的，具有最小的，具有最小IMC的模型 •IMC:每对模块间的数据传递 •IPC:处理机间的通信北京邮电大学北京邮电大学6.1 任务分配v任务划分任务划分§粒度大，降低并行度，粒度小，进程切换和通信的开销就会增加§划分方法划分方法•水平或垂直划分：在给定的任务优先图中水平或垂直划分；关键路径（最长路径） •通信延迟最小划分：把通信频繁的节点归成一类 v任务复制任务复制§在各个处理机节点上复制任务来降低通信开销北京邮电大学北京邮电大学6.1 任务分配v任务分配任务分配§把这些模块分配给处理机，使它们由于处理机间的通信引起的开销最小。

§一般算法假设一般算法假设•存储容量无限•每个处理机节点有相同的处理能力•忽略网络拥塞§评价准则评价准则•CPU的利用率最大化•平均响应时间最小化 北京邮电大学北京邮电大学6.1 任务分配v常见分配算法或策略常见分配算法或策略§基于图论的分配策略 §0-1程序设计策略§“合一 ——阈值”启发式分配算法§改进的启发式分配算法§基于进化（演化）算法的策略•遗传算法•模拟退火算法北京邮电大学北京邮电大学6.1 任务分配v遗传算法求解方法遗传算法求解方法§1、编码方法、编码方法(Encoding) •用一个n+1位的二进制串来表示：00000 11111 §2、初始化群体、初始化群体(Initialize)•随机生成初始化的串群体在串群体中，串长度都是相同的，串长为需要分配的文件数群体的大小根据需要(要求的分配时间等)，按经验或实验给出 •分布均匀的二进制串能使算法更加有效 北京邮电大学北京邮电大学6.1 任务分配§3、选择、选择 (Selection)•借用达尔文的生物进化论中的自然选择(Natural Selection)思想，按照“适者生存”的原则对串进行复制用适应度函数计算每个串的适应值，选择适应值高的串，生成下一代，去掉适应值差的串。

北京邮电大学北京邮电大学6.1 任务分配§4、交叉、交叉 (Crossover) •交叉是两个串按照一定的概率(交叉概率Pc)从某一位开始逐位互换这里先在串群体中，随机的选择两个串，成为一对串，变成多对串后，对每对串随机的选择一个交叉点，例如串长为n+1，则可选择一整数i，0≤i ≤n，i为交叉点，对两个串从第0位到第i位进行互换，形成两个新串是否发生交叉操作，还要受交叉概率的控制，选择好一对串后，在0、1之间产生一个随机数，若该随机数大于Pc则发生交叉，否则保持原状Pc也是根据经验或实验确定，一般可为左右北京邮电大学北京邮电大学6.1 任务分配§5、突变、突变 (Mutation) •二进制串的某一位按照一定的概率(突变概率Pm)发生反转，0变1，1变0这里Pm较小，Pm可小于0.001.§6、适应度函数、适应度函数(Fitness Function)•这里我们用Evaluation过程来实现 §7、停止条件、停止条件•可以是以下几种或其组合：–规定进化代数，也就是最大迭代次数–群体中某个解的适应值达到某一预先规定的范围内–连续若干代，群体中的个体不再变化 北京邮电大学北京邮电大学6.1 任务分配§8、相应的遗传算法描述、相应的遗传算法描述Begin Initialize; Evaluation; While (not termination-condition) do Begin Selection; Crossover; Mutation; Evaluation EndEnd. 北京邮电大学北京邮电大学6.1 任务分配v基于进化算法的方法有以下优点：基于进化算法的方法有以下优点：§具有一定的规律和随机性，不确定性。

为了处理这种特性引入了概率分析§适用于变化的环境能得到多个解，即可得到多个分配方案可供选择§算法具有良好的并行性，进化过程中的群体是一个可行解的集合适合于并行计算北京邮电大学北京邮电大学6.2 负载平衡v什么是负载什么是负载?§CPU队列的长度（比如进程的数目） §某段时间内CPU队列的平均长度 §可用内存的大小§上下文切换的速率§系统调用的速率§CPU的利用率 北京邮电大学北京邮电大学6.2 负载平衡v负载平衡负载平衡§对系统的负载情况进行动态调整，以尽量消除或减少系统中个场点负载不均匀的现象 §由于任务到达的随机性,各节点处理能力上的差异,当系统运行一段时间后，就会出现某些节点还有很多任务没有完成，而另外一些节点处于空闲 §目的：•发挥系统冗余资源•提高资源利用率•防止软件并行性和硬件并行性之间失配北京邮电大学北京邮电大学6.2 负载平衡v负载平衡算法分类负载平衡算法分类 §局部和全局§静态和动态 §最优和次优§近似和启发式§集中和分散式§协作和非协作§针对单个应用程序 和 多个应用程序§抢占式和非抢占式§自适应和非自适应北京邮电大学北京邮电大学6.2 负载平衡v负载平衡算法的组成负载平衡算法的组成 §转移策略 §选择策略 §定位策略 §信息策略•收集信息的方式：集中式（多对一，一对多）和分布式（多对多的指令）•收集的时机：周期或非周期 •收集的范围：全局还是局部 v收集的负载信息内容：节点机的负载信息。

在运行的静态和动态阶段所收集的负载信息内容应该是不同的北京邮电大学北京邮电大学6.2 负载平衡v负载平衡使用的参数负载平衡使用的参数§系统大小•如处理机的个数,处理机多，系统容易找到负载轻的节点，但系统消息传输量大§系统负载•一般用 CPU 队列长度来衡量系统负载 §系统通信速率•各个处理机上任务的到达率§移动阈值 北京邮电大学北京邮电大学6.2 负载平衡v负载平衡使用的参数负载平衡使用的参数§任务大小 •移动一个太小的任务是不合适的,对于一个太大的任务,或涉及到大量数据和文件的任务,也最好在本地处理机节点上执行 •决定任务大小难§管理成本 §响应时间§可选择的目标节点§资源要求 北京邮电大学北京邮电大学6.2 负载平衡v负载不平衡主要有：负载不平衡主要有： §某些算法的迭代大小不是固定的，但迭代的大小在编译时却可以求得 §某些算法的迭代大小不是固定的，但迭代的大小依赖于被处理的数据，在编译时无法求得§即使迭代大小是固定的，也会有许多不定因素导致计算速度的差异 北京邮电大学北京邮电大学6.2 负载平衡v动态负载平衡算法动态负载平衡算法(影响效率的影响效率的3个个主要因素主要因素): §算法 §网络拓扑结构•结点的度数 Davg= ∑ D(I,j)/N(N-1)§执行动态负载平衡代码的频率 •确定负载平衡的粒度 北京邮电大学北京邮电大学6.2 负载平衡v负载平衡中其他相关因素负载平衡中其他相关因素 §编码文件和数据文件 •比如地理上分布的系统，移动所需的代价。

§系统的稳定性 §系统体系结构 •总线连接系统中传递文件的成本比超立方体的要高vLinux Virtual Server ( LVS )Linux虚拟服务器，负载调度是在Linux内核中实现的北京邮电大学北京邮电大学6.2 负载平衡v负载调度算法负载调度算法§一组服务器通过网络连接，它们的前端有一个负载调度器（load balancer）负载调度器将网络请求调度到真实的服务器上§负载调度是以连接为粒度的§包括以下调度算法：•轮询调度：依次将请求调度到不同的服务器上假定：所有服务器处理性能相同，请求服务时间变化不大 北京邮电大学北京邮电大学6.2 负载平衡•加权轮询调度：用相应的权值表示服务器的处理性能，服务器的缺省权值为1可以解决服务器间性能不一致的情况•最小连接调度：把新的连接请求分配到当前连接最小的服务器假定：所有服务器处理性能相同•加权最小连接调度：用相应的权值表示服务器的处理性能 •基于局部性的最少连接调度：将相同目标IP地址的请求调度到同一台服务器，提高各台服务器的访问局部性和主存Cache命中率，从而提高集群系统的处理能力 北京邮电大学北京邮电大学6.2 负载平衡•带复制的基于局部性最少连接调度：将相同目标IP地址的请求调度到同一组服务器。

•目标地址散列调度：通过一个散列函数将一个目标IP地址映射到一台服务器上 •源地址散列调度：根据请求的源IP地址，从静态分配的散列表中找出对应服务器§应用于：•可伸缩的web服务、可伸缩的媒体服务（音频视频）、可伸缩的邮件服务 •Linux Virtual Server ( LVS )：Linux虚拟服务器，负载调度在Linux内核中实现 北京邮电大学北京邮电大学。