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

《现代电子技术》2006年第19期总第234期》通信与信息技术司2.4本地与全局算法当创建一个新进程时，系统要决定是否让这个进程在创建他的机器上运行。如果那台机器太忙，这个新的进程应该被转移到别的机器上去运行。这时就要决定是否只根据本地的信息来决定转移策略。2.5发送者发起与接收者发起算法一旦转移策略决定要清除一个进程，定位策略就要决定将该进程发送到何处。很明显，定位策略不能是本地的，他需要别处的负载信息来对进程传输到何处作出明智的决定。这个信息可以用2种方法来传递：一种是发送者发起，另一种是接收者来启动。在图1(a)中，一台过载机器向别的机器发送请求希望得到帮助，并将一些新进程卸载到别的机器上。在这个例子中，是由发送者主动定位其他CPU的。相反，在图1(b)中，一台空闲的或者说是欠载的机器向别的机器发送信息，声明自己是空闲的，可以承担一些额外的工作。他的目的是找到一台愿意给他些事情做的机器。不论是发送者发起的还是接收者发起的情况，不同的算法有不同的策略来决定由谁来搜集信息，及搜集多长时间和怎么样处理结果。机器判定他的负担A重机器寅告他可被位川a)发送者爿找空闲机_器fb)接收者j找工作做图1发送者发起和接收者发起算法原理示意图3处理机分配算法实例3.1图论确定性算法这种算法是基于这样的一个系统，构成他的进程知道他所要求的cPu和内存要求，并且知道系统中每对进程之间要求的平均通信量。如果系统的CPIJ数量忌小于进程数，则要求将多个进程指派到同一个CPU上。整个算法思想是使这种指派能够使网络的通信量最小化。整个系统表示为一张带权图，每个节点表示一个进程，每条边表示两个进程之间的通信量。图2表示了图的2种划分，这2种划分导致了2种不同的网络负载。图23个处理机分配9个进程的2种方法图2(a)中，将进程A，E，G划分在一个处理机上，B，F，H在第二个处理机上，C，D，I在第三个处理机上。整个网络通信量等于与虚线相交的边的权值的和，为30单位。在图2(b)中，由于采用不同的划分，网络通信量为28单位。他要求较小的网络通信量。3.2启发性算法——上一下算法该算法的特点是，每个用户公平地分享系统的计算能力，上一下算法是一种集中式算法。算法中存在一个协调者，由他来集中管理整个系统中所有处理机的分配，这种分配是由他管理的一张使用情况表来实现的。在表中每一台处理机都有一个条目(初值为O)。当有事件发生时，发消息给协调者，以便更新使用表中的相应条目值，该值可为正、负值或o。正值表示该机用户占有系统其他处理机，负值表示该用户需要系统资源，零值表示未占有且不需要资源。当有重要事件发生时，发消息给协调者更新使用表，并根据该表决定处理机分配。当用户创建进程时，如果该处理机认为这个进程应该到其他的机器上运行，他向协调者申请一台处理机，若此时系统中有处理机空闲且无竞争，就会得到响应，该进程即在空闲处理机上运行。否则，将暂时拒绝该请求，并且记录该请求。用户在其他处理机上运行进程时，协调者要收集惩罚点。在每秒钟使用表的相应条目中增加一个定值(如加1)，该值即为惩罚点。若该用户有”个进程同时在系统中其他处理机上运行，则相应的条目值按时间段加n。如果没有处理机可用，该请求被暂时拒绝并等待。就从他的使用表条目中按每个固定的时间段减去一个定值。当没有发出请求且未占有系统中其他处理机时，对应的使用表条目值向零移动(通过在每秒钟减1)，直至为零，这样使用表中各条目的值可上可下，这就是其算法名字的由来。图3上一下算法的操作如图3所示，当某处理机上先后创建2个要求在系统中其他空闲处理机上运行的进程时，其条目值的变化情况。时刻≠.，用户在某处理机上创建进程1，并决定在其他处理机上运行。由于系统中当前无空闲处理机可用，该请求被暂时拒绝。经过2个固定时间段，到f。时刻，系统由于有了空闲处理机，响应进程1的请求。条目值开始按固定时间段增加，在时刻屯该处理机又创建了进程2，同样由于系统中当前无空闲处理机可用，该请求被暂时拒绝。故在时间岛～￡。期间，条目值由于一增一减相抵消而不变化。(下转第60页)53