如发现有乱码，请点击下面链接浏览原文
正文摘录:

闰志军等：分布式系统中处理机的分配和调度研究分布式系统中处理机的分配和调度研究闰志军’，马礼举。(1.西安通信学院陕西西安710106；2.中国人民解放军驻847厂军事代表室陕西西安710100)摘要：进程在处理机上运行，在传统系统中仅有一个处理机，不会出现怎样利用处理机的问题。而在多个处理机的分布式系统中，处理机的分配算法就成了一个主要的设计问题。分布式系统中的处理机可用多种方式组织，本文对处理机分配模型与算法的设计进行了研究，并以具体实例详细分析了该问题。关键词：分布式系统；处理机分配；图论确定性算法；上一下算法中图分类号：TP311文献标识码：A文章编号：1004—373X(2006)19—052一02ResearchOfaProcessorAUocationandSchedulingDistributedSystemYANZhijun’，MAL巧u。(1.Xj’anCommunjcatlon5In5Dtute，Xi’an，710106，China；2.TheMilitaryRepresentatjveOffice0fPLAAssignedr0847Factory，Xi’an，7：10100，China)Abstract：Processesrunonprocesso／。s，inatraditionalsystem，theI’eisonlyoneprocessor，sothequestionofhowthepro—cessorshouldbeuseddoesnotcomeup.Inadistlributedsystem，withmultipleprocessor。s，processorallocationalgorithmisamaj’ordesignissue.Theprocessoisinadistributedsystemcanbeorganizedinseveralways.Inthispaper，designoftheproees—sorallocationmodelandalgorithinisstudied，anddetailanalyzedbyspecific：examples.Keywords：distributedsystem；processor。allocation；graph—theoreticdeterministic：algor‘ithm；up—downalgorithm分布式系统是由多台处理机组成的，这些处理机可以组织成个人工作站集合、处理机池模型或混合模型。但不管哪种情况，都要决定进程应当在哪台处理机上运行，即处理机的分配。分配算法是分布式系统设计的核心问题之一，他直接影响到整个系统的性能。1处理机分配模型在讨论特定的算法和设计原则之前，首先讨论处理机分配的基本模型、假设及其目标的问题。在这个领域中几乎所有的模型都假设所有的计算机都是一样的，或至少是代码兼容的，至多在速度上有所不同。只有个别模型假设系统是由多个不相关的处理机池组成，每个处理机池是同构的。这些假设通常都是有效的，并且能够简化问题。首先，假设所有的模型系统都是完全连接的，既每台处理机都能与其他任何一台处理机进行通信。处理机分配策略有2大类：不可迁移的和可迁移的。在不可迁移策略下，当创建一个进程时，系统就决定为该进程分配哪台处理机。一旦分配完毕，进程将一直在这台处理机上运行，直至结束。无论这台处理机是多么地严重超载，也不管其他的处理机有多少空闲，他都不能移到别的处理机上。相反，在可迁移的策略下，可将即使已经开始运行的进程迁移到别处的处理机上继续运行。可迁移策略能够提供更好的负载平衡.但同时也增加了系统的复杂性，对系统的设训‘有很大的影响。收稿日期：2006一06—292处理机分配算法的设计问题在设计算法时，设计者要考虑的问题可概括为以下5个方面：2.1确定性与启发性(试探性)算法确定性算法是用于当进程的所有行为都是事先知道的情况。试想一下，如果你有一张所有进程的清单：这些进程的计算需求、文件需求、通信需求等等，那么设计一个完美的分配方案是可能的。从理论上说，可以尝试所有的可能，从而找到一个最优解。只有极少数系统的所有信息是预先可知的。但有时可得到一个合理的近似。另一个极端是系统的负载是完全不可预测的。工作请求视用户正在做什么而定，并且每个小时，甚至每分钟都有可能发生很大的变化。在这种系统中，处理机分配不能用数学的、确定性的算法来实现，而只能使用特别的启发性(试探性)算法。2.2集中式与分布式算法把所有信息搜集到一个地点便于作出更好的决定，但这使得系统不够健壮，而且使中心计算机负载过重。通常倾向于采用分布式算法，但一些集中式算法仍被采用，因为缺少相应的可替代的分布式算法。2.3最优与次优算法用集中式和分布式算法都能得到最优解，但都比得到次优解的代价大得多。要得到最优解必须搜集更多的信息，并进行更全面的处理。在实际中，大多数分布式系统目标定位在启发性、分布式的、次优的解决方案上，因为要得到最优解太困难了。