算法思路分析.docxVIP

1.动态负载平衡算法组成动态负载平衡算法由四个部分组成:1.1转移策略 用于确定一个结点是否处于参与任务转移的状态，是作为发送者，还是作为接收者。转移策略分手动策略(即由用户指明某特点作为发送者或接收者)，门限策略(当结点上的负载大于或等于某门限T，时，它作为发送者;低于某门限Tz时，它作为接收者。Ti与Tz可相等或不等)、相对策略(当结点的负载高于其它结点负载某一差值时，它作为发送者;低于某一差值时，它作为接收者)等。1.2 选择策略 一旦转移策略确定了发送者，选择策略将选择哪个任务被转移，较为简单的选择策略是选择新产生的任务作为被转移的对象。还有一些因素可以作为选择策略的考虑范围，如:转移开销的大小、运行时间的长短、对发送者的依赖度等。转移一个任务可以是抢先式的(preemptive)或非抢先式的(non-preemptive)。抢先式意味着可以转移一个正在运行的任务，而非抢先式只能转移那些还未被启动执行的任务，显然，前者代价大于后者，但任务却能够在转移后继续执行而优于后者。1.3 定位策略 负责寻找一个结点的搭挡结点，即当转移策略确定了某结点为发送者时，它负责寻找一个接收者。定位策略可以是集中式的或非集中式的，可分为手动策略、顺序查找策略、随机查找策略、门限策略、最短CPU队列策略、匹配策略等。1.4 信息策略 用于确定何时、到何处去搜集有关系统中其它结点的哪些状态信息。它可分为三种，即需求驱动策略(当一个结点变为发送者或接收者时，它才去搜集其它结点的状态信息以寻找搭档，属于非集中式策略)、周期策略(周期性地搜集系统的状态信息，可以是集中式的或非集中式的)、状态变化驱动策略(只有当某结点上状态发生某种程度的变化时，它才散布自己的状态信息，可以是集中式的或非集中式的)。 动态平衡算法一个主要参数是负载索引，它表示计算机的综合能力，包括CPU队列长度，可用存储量，上下文切换时间等等。对负载索引的选择应根据机器环境和应用特点来确定，不可能包含所有相关因素。2负载平衡算法 负载平衡技术是一种提高分布式系统整体性能和吞吐量的有效方法。平衡策略设计的好坏直接决定了分布式系统在负载均衡上的表现，设计不好的策略算法会导致系统的负载失衡。2.1轮转算法 在一个任务队列里，队列的每个成员都具有相同的地位，轮转法简单的在这组成员中顺序轮转选择。在负载平衡环境中，均衡器将新的请求轮流发给节点队列中的下一个节点，如此连续，周而复始，每个集群的节点都在相同的地位下被轮流选择。轮转法的活动是可预知的，每个节点被选择的机会是1/N，因此很容易计算出节点的负载分布，轮转法典型的适用于集群中所有节点的处理能力和性能均相同的情况，在实际应用中，一般将它与其它方法联合使用时比较有效。3设计思路3.1绘制界面大致形状如下图，5个处理机，进程个数任意。五个正方形代表五个处理机 3.2选择调度算法使用轮转算法，其算法思想如前面所介绍的。网上时间片轮转算法思想如下while (k == 1) { for (i = 0; i N; i++) { if (a[i] != 0) { if (a[i] = t) { a[i] -= t; b += t; cnt[i] = cnt[i] + 1; Console.WriteLine(\t{0}\t\t{1}\t\t{2}\t\t{3}, i + 1, cnt[i], b, a[i]); } else { b = b + a[i]; cnt[i] = cnt[i] + 1; a[i] = 0; Console.WriteLine(\t{0}\t\t{1}\t\t{2}\t\t{3}, i + 1, cnt[i], b, a[i]); } } else { continue; } } for (i = 0; i N; i++) { if (a[i] != 0) { k = 1; break; } else { continue; } } if (i = N) { k = 0; } }通过借鉴上述算法，设计一个多处理机的轮转算法，并在图形界面上动态的实时跟进。3.3 模拟输出输出算法所用的总时间，以及模拟处理机空闲/忙碌状态。