《并行计算机体系结构多进程多处理机实现资源分配.docx》由会员分享，可在线阅读，更多相关《并行计算机体系结构多进程多处理机实现资源分配.docx（4页珍藏版）》请在三一文库上搜索。
1、多处理机调度、资源分配学号：姓名：一.实验目的：首先实现多处理机调度，然后在某个处理机里实现多进程调度。二：资源分配负载平衡与任务分配/调度密切相关，任务分配通常有静态的和动态的两种方 法。静态分配一般是任务到进程的算术映射。静态分配的优点是没有运行时任务管 理的开销，但为了实现负载平衡，要求不同任务的工作量和处理器的性能是可以 预测的并且拥有足够的可供分配的任务。动态分配就相对灵活，可以运行时在不同处理器间动态地进行负载的调整。三：调度任务调度通常也有静态和动态两种。1 .静态调度静态调度方案一般是静态地为每个处理器分配En/pJ个连续的循环迭代，其中 N为迭代次数，p是处理器数。除了在所有
2、的循环迭代计算时间和每个处理器 的计算能力都相同的同构情况下外，这种静态调度的方案总会引起负载的不平 衡。另一方面，静态调度方案也可以采用轮转(Rou nd-robi n)的方式来给 处 理器分配任务，即将第i个循环迭代分配给第i mod p个处理器。这种方案 可以部分地解决应用程序本身负载不平衡的情况，如LU分解的执行时间随着 循环变量i的增长而减少。然而，采用轮转方式可能会导致高速缓存命中率降 低。2 .动态调度尽管动态调度技术通常可以取得较好的负载平衡的效果，但开销也 很大。因止匕如果静态高度技术有较好的负载平衡效果，就尽量采用静态调度 技术。而在元计算环境下，一般动态调度有较好的效果。
3、四：单处理器多进程调度调度任务之间的切换由任务优先级决定，低优先级任务不能抢占高优先级任 务，只有高优先级任务进入阻塞状态，低优先级任务才有机会运行。任务由OS根据任务的优先级和任务当前所处的状态(就绪、阻塞、运行)进行 调度，调度任务从任务控制块和进程控制块中获得调度进程运行时所需的有关数 据。进程也有三种运行状态：就绪态、阻塞态、运行态。因此每个调度 任务就有 三个队列：就绪进程队列、阻塞进程队列、运行进程队列，这三个队列分别用来 指示该调度任务下处于不同运行状态的进程。它的状态在消息激励下可以相互转 换，如图2所示。OS址肛船我趴化/丽、进购:站la呵雄提阻塞凰期颅进* 量瞬耻刿一 ，
4、1 |进杵4 |理程4世代19I进程S IJE朴g盘朋消息豳列为牢的址臭iii-xN拔示消息徽列平空询戎注：进和水因为同护垸送涓JM或建迟南阻瘩.匝即虽蚪消恿灵门下空，于阻秦队列中图1单处理器任务和进程关系图2进程状态转换当一个调度任务被OS调度运行后，该任务将从其所操作的OS消息队列上获得 消息，并把取到的消息指派给相应的进程，同时把阻塞且获得消息的进程放到任务 的进程就绪队列尾部，然后开始循环调度进程的执行。调度任务每次调度进 程就绪 队列中的第一个进程，当将被调度的进程是由于同步消息已经应答或延时已经到时 而被唤醒时，调度任务将控制转移到保存在进程堆栈中的指令地址； 否 则，如果进程消息
5、队列头上的是一条新消息、，调度任务依据进程消息队列头上的消 息和PCB中的数据为进程的主处理函数传递相应入口参数，并从主处理函数 的第一 条语句开始执行。在图3中，在派发消息链表中的消息时：(1)如果接收消息的进程处在阻塞状态，且此时不是在等待同步应答，消息 将成为进程PCB消息队列的当前消息，该进程PCB将从阻塞队列进入就绪队列 尾； 若此时在等待同步应答，贝U仅将该消息添加到进程 PCB消息队列尾。(2)如果接收消息的进程已经在就绪状态，贝U将该消息添加到进程PCB消息队列尾。(3)如果待分发的消息是同步定时器超时消息或同步应答消息，那么此消息 不 进入进程PCB的消息队列，直接把该PCB
6、从阻塞队列中挂到就绪队列头。五：多处理机多进程调度我们采用耦合调度(AS)策略实现多处理机多进程调度。由于耦合调度采用了分布式的任务队列，同时充分地考虑了处理器和数据之间 的耦合关系。我们把AS的调度过程分为三步：初始化阶段：将一个有N个循环迭代的循环分成p块，每块大小为N/p,第i 块就分配给第i个处理器的某个调度任务的就绪队列，然后进入运行队列(如 图1); )本地调度阶段：每个处理器从自己的局部任务队列中取出剩下循环迭代数量 的1/k, 一般推荐k的值等于P;远程调度阶段：当某个处理器自己的局部任务队列为空时，它就找到最忙的处 理器，并从该处理器的非运行任务队列中取走剩下任务的1/p,然后放到自己的 某个进程的就绪队列，并调度到运行队列(如图1);六：过程总结采用耦合调度(AS)策略首先实现多处理机调度，当调度到某个特定的处理机 后，再在单个处理机里实现多进程调度。也就是说，一个处理机有M个进程，而 N个处理机有N*M个进程。