湖南大学并行计算课程报告

并行系统的调度设计问题我们组选取了五篇关于并行系统调度的相关论文，并进行了总结，完成了ppt的讲解和报告的制作。五篇论文的题目如下：solvingtheparalleltaskschedulingproblembymeansofageneticapproach通过遗传手段方法解决并行任务调度问题schedulingparalleltasksapproximationalgorithms调度并行任务的近似算法schedulingalgorithmsandsupporttoolsforparallelsystems调度算法和支持工具并行系统practicalmultiprocessorschedulingalgorithmsforefficientparallelprocessing实用的多处理机调度算法高效的并行处理AnewDAGbasedDynamicTaskSchedulingAlgorithm(DYTAS)forMultiprocessorSystems一种新的基于DAG的动态任务调度算法（DYTAS）的多处理器系统本次报告主要包括以下四个部分：1.分布式并行操作系统概述2.分布式并行操作系统调度的算法设计3.系统性能分析4.报告总结1.分布式并行操作系统概述1.1分布式操作系统的定义分布式软件系统（DistributedSoftwareSystems）是支持分布式处理的软件系统,是在由通信网络互联的多处理机体系结构上执行任务的系统。它包括分布式操作系统、分布式程序设计语言及其编译（解释）系统、分布式文件系统和分布式数据库系统等。其中分布式操作系统负责管理分布式处理系统资源和控制分布式程序运行。它和集中式操作系统的区别在于资源管理、进程通信和系统结构等方面。一个分布式计算机系统是一些独立的计算机的集合，但是对这个系统的用户来说，系统就象一台计算机一样。这个定义有两方面的含义，第一，从硬件角度来讲，每台计算机都是自主的；第二，从软件角度来讲，用户将整个系统看作是一台计算机。1.2分布式操作系统的优点分布式计算机系统的特点在于系统中具有多台计算机且所有的计算机都有相等的地位，由于有这个特点，所以与传统的集中式系统相比，分布式计算机系统具备许多优越的性能：经济性：多个计算机能提供比大型机更好的性能价格比。速度：分布式计算机系统能提供比大型机更强大的计算能力。固有的分布性：有一些应用包含了物理上分散的机器。可靠性：当某台机器崩溃时，整个系统仍能正常工作。可扩展性：处理能力可按需增加。1.3设计分布式操作系统需要注意的问题（1）透明性所谓透明性就是让用户觉得一群机器和一台普通的单处理器系统是一样的。可以在两种层次上达到透明性。最容易的作法就是对用户隐藏分布性；在更低的一个层次，也可以让系统对程序透明，即系统调用的接口被设计成看不出有多个处理器存在。（2）灵活性大多数分布式系统采用微内核结构，微内核具有很高的灵活性，它一般只提供4种最小的服务：进程问通信机制、某些内存管理工作、有限的低级进程管理和调度、低级的输入，输出。大部分操作系统的服务通过用户级的服务器来实现。（3）可靠性建立分布式系统的目的之一是提高系统的可靠性。它的基本思想是，如果有一台机器坏了，其他机器能够接替它进行工作。高可靠性的分布式系统必须有高可用性和高安全性，另外还应该有容错功能，即一个节点出了故障，修复以后应该能够恢复到原有的正常状态。（4）性能性能问题是任何时候都需要考虑的问题，一个分布式系统的性能在某些情况下可能比单一的计算机性能略差，这是因为分布式系统的性能和系统中的通信紧密相关。如果通信质量很差，则系统性能相应会很差。在任务调度的同时必须要考虑通信开销，这样才能保证系统的性能。2分布式操作系统调度算法的设计根据分布式系统的定义，分布式系统由多个处理机组成，这些处理机的组织形式可能是工作站集合、一个公共的处理机池或者是某种组合的形式。但无论是哪种形式，都要有一种算法来决定在哪台处理机上运行哪个进程，这就是分布式并行操作系统的调度。2.1分布式并行调度算法分析上面我们讨论了分布式调度算法的设计问题，这里简要分析几种常见的调度算法。（1）图论确定性算法一类广泛研究的算法是基于这样的一些系统，构成它的进程知道它所要求的CPU和内存要求，并且知道系统中每对进程之间要求的平均通信量。如果系统的CPU数量小于进程数目，则要求将多个进程指派到同一个CPU上。整个算法的思想是使这种指派能够使网络的通信量最小化。整个系统可以表示为一张带权图，每个节点表示一个进程，每条边表示两个进程之间的通信量。从数学的角度来讲，整个问题就变成了如何根据特定的限制将图划分为k个不相连的子图。对于每种满足限制的解决方案，子图内部的边意味着机器内部的通信，可以忽略。从一个子图连向另一个子图的边表示网络通信。算法的目标就是在满足所有的限制下，找到一种划分方式使网络通信量最小。显而易见，我们是在寻找紧耦合的聚集。但是这些聚集之间很少相互作分布式并行操作系统中调度的研究和实现（2）集中式算法图论算法应用非常有限，因为它需要事先了解完整的信息。这里讨论一种不需要事前了解任何信息的启发性算法。算法中有一个协调者，它保存着一张使用情况表，每个工作站在表中都有一个条目，初值为0。当有重要的事情发生时，将给协调者发消息以更新使用情况表。算法将根据使用情况表决定处理机的分配。这些决定发生在调度事件发生时，即有进程请求处理机、处理机进入空闲状态或者是发生了时钟中断时。这个算法所以是集中式的，是因为它所考虑的是使每台工作站的用户公平地享用系统的计算能力，而不是试图使处理机的利用率最大化。（3）层次式算法集中式的算法，不能很好地适应大型系统。中央节点很快会成为系统的瓶颈，更不用说是某个节点失效了。这些问题可以用层次式算法来解决。层次式算法基本保持了集中式算法的简单性，并且能够很好地适应大型系统。提出一个监视处理机集合的方法，就是将所有的处理机以一种与网络物理结构无关的方式组织成一个逻辑分层结构。对每组k个工作，分配给管理者一个任务，即跟踪各个工作者谁在忙，谁正空闲。如果系统很大，将会有众多的管理者，所以有的机器要变为管理的管理者。这种层次可以无限扩展下去。如果一个管理者停止了正常的工作，一个方案是选择一个它的直接下属成为临时管理者，取代它的位置。这个选择可以由它的下属共同作出，也可以由它的同级作出，还可以由它的上级作出。为了避免单个管理者在层次的最上层，可以截去最上层，而在最上层形成一个委员会，拥有最高权利。如果委员会中的一个成员无法工作，其他成员会在下一层中选出一名成员取代其位置。（4）发送者发起分布式启发性算法一个典型的算法是Eager等人在1986年提出的，在他们研究的“最有效代价”的算法中，当创建进程时，创建进程的机器将对一个随机选择的机器发送询问，询问那台机器的负载是否低于某个阚值。如果是，将发送进程，否则，将选择另一台机器并发送询问。这个过程不会一致持续下去，如果在N次询问内还没有找到合适的机器，算法将停止，新进程将在创建它分布式并行操作系统中调度的研究和实现然而，在负载十分重的情况下，所有的机器都会不停地毫无意义地向其他机器发送询问，想找到一台愿意接受更多工作的机器。在这种情况下，几乎没有机器会被减轻负载，但却引起系统相当可观的额外开销。（5）接收者发起分布式启发性算法根据这个算法，当一个进程结束时，系统将检查自己是否有足够的工作可以做，如果没有，将随机向一台机器申请工作。如果那台机器没有要给予的工作，系统将继续询问第二、第三台机器。如果连续N次询问都没有申请到工作，系统将暂时停止申请，开始处理系统队列中一个等待的进程，当这个进程结束后，再开始下一轮申请。如果系统无事可做，则将进入空闲状态，一定的时间后，它从新开始申请。这个算法的好处就是它不会在系统非常繁忙的时候给系统增加额外的负载，当然，在系统几乎没有事情可做的时候，会拼命向别的机器申请工作，会造成相当大的询问负载。然而，在系统欠载时使系统开销增大总比在系统过载时这样做要好得多。（6）投标算法这种算法试图将计算机系统变成小型的经济社会。由买卖双方和需求关系确定的价格组成。算法的核心参与者是进程，为了完成工作，进程必须购买CPU时间，而CPU则拍卖它的处理机周期给出价最高的买主。每个处理机在一个公共可读文件中公布它们的近似价格。这个价格并不是确定的，而是为了表示所提供服务的大概价格。根据处理机速度、内存容量、浮点运算能力以及其他一些特性，不同的处理机有不同的价格。所提供的服务的指示，如预期的响应时间也可以同时公布。当一个进程要启动一个子进程时，它将查询现在有谁在提供它所需要的服务，然后确定一个它可以支付得起的处理机集。通过计算，它将从这个处理机集中选出一个最好的。根据应用程序的不同，最好的可以指最便宜的、最快的或最高性能价格比的。然后它将向第一选中的处理机发出一个出价，所出的价格可能会高于或低于已公布的价格。处理机收集向它们发出的所有出价，然后作出决定，可能是选择出价最高的。然后通知选中的未选中的进程，并开始执行被选中的进程。公共文件中此处理机的价格将被更新，以反映处理机的最新价格。3.性能分析一个系统的性能可以用很多指标来体现，对于分布式并行调度子系统来说，最重要的指标是响应时间和负载均衡，以下我们就对这两个方面对分布式并行调度子系统来进行分析。（1）响应时间响应时间指的是客户从发起调度到获得一个可用的主机IP地址的时间。响应时间的长短可以衡量分布式并行调度的优劣，时间越短越好。（2）负载均衡负载均衡指的是提供服务的主机不能始终集中于某一台主机，而是随机分布在各个主机上。4.总结随着计算机技术的广泛应用，对分布式并行操作系统的需求越来越大，这也是当前国内外操作系统的发展趋势。任务调度是操作系统中一个非常重要的子系统，针对传统的集中式调度子系统的缺点，人们开发了分布式并行调度子系统。本文论述了分布式并行调度的技术，分析了现有的若干调度算法以及调度算法性能指标。设计一个分布式并行操作系统，可以有两途径。一是设计一个全新的系统。这样，由于针对性强，可以获得优秀的性能。但是，设计周期长，而难以继承现有的成功软件。第二种途径是通过对集中式操作系统进行扩充改造，它的优点是：集中式操作系统中的许多部分可以直接继承，研制周期短，而且原来的用户程序可以不加修改地在新系统中运行。