论文部分内容阅读
任务分配是计算机研究领域的一个经典问题,其许多子问题尚未彻底解决,对它们进行研究具有重要的理论和实际价值。本文重点研究并解决(N, m)分布式系统和分布式服务器系统的任务分配问题,并且取得了如下创造性成果:严格定义了(N, m)分布式系统模型。已有工作提出了(N, m)分布式系统的概念,但并不完善。本文详细分析了(N, m)分布式系统各项特性,包括奖惩依赖关系、同构与异构、任务选择策略等,以精确地刻画该模型。提出了(N, m)分布式系统的两个任务分配算法。针对(N, m)分布式系统可以有两类任务分配算法,即动态算法与搜索算法,已有工作只研究了前者,且均存在一个重要限制:最大奖励概率不小于0.5。本文所提出两个算法突破了最大奖励概率限制,它们分属动态算法和搜索算法。证明了所提两个算法的正确性。本文使用多阶马尔科夫链,对第一个算法进行了正确性证明。对于第二个算法,由于平衡点不存在,难于使用马尔科夫链。本文结合概率论的相关知识,通过分段讨论和求极值,获得了一种很好的方法,部分地证明了该算法正确性。对于该算法而言,所获方法比马尔科夫链更适用,也更简洁。不仅如此,该方法还可分析更一般的问题。为方便两个算法的正确性证明,还提出并分析了两个辅助算法。分析了所提两个算法的性能。在实验的基础上指出:第一个算法比已有算法效率更高。在理论分析基础上指出:第二个算法在同类算法中具有最低时间复杂度。严格定义了分布式服务器系统模型,给出延迟比、任务级公平、服务器级公平和系统公平性量度的概念。详细分析了系统各项特性,特别是任务长度的长尾分布。针对该模型已有不少算法,如随机法、轮询法、集中队列法和TAGS算法。在服务器级公平性条件下,本文给出了各算法的性能计算式。在实验的基础上,指出了TAGS算法的扩展性限制。将TAGS算法与集中队列法结合,提出了两类共三个改进算法,并分析了前两个算法的性能。对于最后一个算法,由于理论上的性能分析比较困难,本文使用模拟实验将它与其他算法进行比较。<WP=5>针对TAGS算法和第一类扩展算法的参数设置问题,提出了使用二分法进行试探的辅助算法。该算法可保证系统快速、稳定地完成参数设置。