云环境中DAG调度仿真器的设计与实现

云环境中DAG调度仿真器的设计与实现大连理工大学本科毕业设计（论文）云环境中DAG调度仿真器的设计与实现Design and implementation of DAG scheduling simulator in cloud environment学部（学院）：电子信息与电气工程学部专 业： 计算机科学与技术 学 生 姓 名： 郭宇辰 学 号： 201181267 指 导 教 师： 王宇新 评 阅 教 师： 完 成 日 期： 大连理工大学Dalian University of Technology云环境中DAG调度仿真器的设计与实现摘 要随着计算机网络的快速发展，智能计算、面向服务的体系架构等新技术和新概念的广泛应用，有效地促使人们实现计算机支持与协同工作。工作流技术作为计算机完成协同工作的抽象化手段，在企业流水线生产、办公自动化和科研领域等方面扮演者重要角色，有效促进业务系统的自动化和柔性化。工作流调度是工作流管理系统中的关键技术，随着工作流的服务资源从无偿服务转换为有偿服务，根据工作流的服务质量 QoS (Quality of Service)属性，如服务的执行时间、费用、可靠性等，如何选择最优的服务资源来动态地满足不同用户的业务需求。本文主要学习云计算环境中的任务执行流程，使用DAG工作流模拟云环境中的任务调度，设计并实现出DAG调度仿真器。该仿真器能够根据指定参数完成工作流的自动生成，并按照选定的调度算法对生成的DAG工作流进行调度，最终给出算法执行结果的对比图表。论文的主要工作是DAG仿真器的设计与实现。只要输入DAG的节点数，选择相应的调度算法，系统便会随机生成相应的数据，然后利用JAVA中的XML工具将数据保存在xml文件中。之后我的工作是利用JAVA中的dom解析方法解析xml文件中的数据，将DAG的最重要的信息节点集和边集保存在一个邻接矩阵中，其余的服务费用等信息保存在节点或边所对应的类当中，方便调用和处理。我们要对邻接矩阵进行分析，其中利用深度优先遍历可以确定这个DAG图中每一个节点在哪一层，每一个节点的深度确定之后便可以得到DAG图的深度和宽度。使每一个节点对号入座组成一个二维数组，通过数组下标便可以确定每一个节点的坐标，利用JAVA中的Graphics工具中的画图函数便可以画出DAG图。当实现多DAG时，可以通过定义类的数组和坐标平移实现画图。同时还支持直接打开xml文件进行DAG画图。关键词：DAG；工作流；XML解析；JAVA Graphics绘图- I -云环境中DAG调度仿真器的设计与实现 Design and implementation of DAG scheduling simulator in cloud environmentAbstract With the rapidly development of computer network, the widely used of some new technologies and concepts, such as intelligent computing, SOA (Service Oriented Architecture) and so on, has promoted the realization of computer supported and cooperative work. Workflow is regard as an abstract model in computers cooperative work, which plays a more important role in pipeline production of enterprises, office automation, researching and so on, and it can also increase the automation and flexibility of business process. Thus, workflow scheduling is becoming a critical technique of workflow management. With the services of workflow from free to paid, it should select the optimized service according to the value of the Quality of Service (QoS), like time, cost and reliable, to satisfy users requirements.This paper mainly studies the task execution flow in cloud computing environment, and uses DAG workflow to simulate the task scheduling in cloud environment, and designs and implements the DAG scheduling simulator. The simulator can be according to the automatic generation of parameter specifies the complete workflow, and according to the selected scheduling algorithm to generate the DAG workflow scheduling, finally give the algorithm execution results comparison chart.The main work of this paper is the design and implementation of DAG simulator. As long as the number of nodes entered DAG, select the corresponding scheduling algorithm, the system will randomly generate the corresponding data, and then use the XML tool in JAVA to save the data in the XML file. After my work is using java DOM parsing XML file parsing data, DAG the most important information node set and edge set stored in an adjacency matrix and the rest of the service fees and other information saved at the node or edge corresponding to class, easy call and physical. We want to analysis of the adjacency matrix, including the use of depth first traversal can determine the DAG in a per node where a layer, determine the depth of each node can get the depth and width of the DAG. Make yourself in each node consists of a two-dimensional array, the array subscript can determine the coordinates of each node and using the drawing function of java graphics tools can draw a directed acyclic graph (DAG). When the implementation of multi DAG, you can achieve drawing by defining the array and coordinates of the class of the array. Also support to open the XML file directly DAG drawing.Key Words：DAG；Workflow；XML analysis；JAVA Graphics mapping- IV -目 录摘 要IAbstractII1 引言12 领域知识介绍22.1 云计算相关知识22.1.1 云计算的定义及特征22.1.2 云计算的分类32.1.3 云计算的基本服务42.1.4 云计算的关键技术42.1.5 云计算的发展趋势52.2 DAG相关知识62.2.1 工作流的DAG模型62.2.2 工作流的DAG表示72.3 调度算法介绍82.3.1 分层算法82.3.2 TCDBL82.3.3 CACO83 仿真器的设计103.1 Java简介103.2 NetBeans简介123.3 XML简介133.4 DAG的XML表示143.5 邻接矩阵分析163.6 节点数组建立184 仿真器的实现194.1 DAG的随机生成194.1.1 参数定义194.1.2 DAG生成194.2 Java的DOM解析XML204.3 Java的Graphics工具224.3.1 容器选择224.3.2 屏幕坐标系234.3.2 绘制文字234.3.2 绘制线段234.3.2 绘制椭圆244.4 DAG绘制254.4 坐标美化274.5 多DAG的实现274.6 界面294.7 使用说明295 总结与展望30参 考 文 献31致 谢32云环境中DAG调度仿真器的设计与实现1 引言云计算作为一种新兴的商业计算模式，是目前国内外商业和科研机构研究的热点之一，它采用成熟的虚拟化技术将数据中心的资源打包为互联网上的用户提供按需服务。云计算的两个关键技术是作业调度与资源分配，在具体的实施过程中它更关注对用户所提供的服务质量。作业调度和资源分配问题可以通过建立有向无环图模型（DAG）模拟工作流来进行分析和优化。随着计算机网络的快速发展，智能计算、面向服务的体系架构等新技术和新概念的广泛应用，有效地促使人们实现计算机支持与协同工作。工作流技术(Workflow)起源于早期的办公自动化领域，随着集成工作流的商业应用的广泛使用，工作流技术以及工作流管理系统的研究也逐渐成熟。工作流管理系统是通过计算机按照预定的规则实现信息的传递和任务的自动化执行，解决了传统的工作方式效率低、信息延迟、成本开销较大等的问题。工作流技术作为计算机完成协同工作的抽象化手段，在企业流水线生产、办公自动化和科研领域等方面扮演者重要角色，由于这些业务或生产环节需要分成不同的执行阶段，并且各阶段之间存在依赖关系，因此，通过构建工作流可以高效的完成该类网格应用的监控和管理，有效促进业务或生产系统的自动化和柔性化。工作流调度是工作流管理系统中的关键技术，根据工作流的服务质量 QoS (Quality of Service)属性，如服务的执行时间、费用、可靠性等，如何选择最优的服务资源来动态地满足不同用户的业务需求。在云环境下，针对任务调度如何降低算法执行过程中所需时间这一问题，对比DBL、DTL、TCDL和CACO这四种算法模拟工作流调度，通过仿真实验将不同算法与不考虑费用的算法进行比较。论文第一章为引言，简要说明工作目的与实现方法。第二章介绍相关领域知识，包括云计算和工作流。第三章介绍仿真器的设计，首先介绍工作中用到的一些工具，比如编程语言JAVA，可扩展标记语言XML，使用的软件NetBeans，然后是数据处理方法，比如用XML表示DAG，邻接矩阵方法分析DAG的属性等。第四章介绍仿真器的实现，包含JAVA的DOM解析XML，使用Graphics工具进行画图，以及之后的优化工作，最后是软件的具体使用说明。最后一章是对整个毕业设计工作的总结与展望。2 领域知识介绍2.1 云计算相关知识2.1.1 云计算的定义及特征云计算是继个人计算机变革、互联网变革之后的第三次 IT 浪潮。它是基于互联网的相关服务的增加、使用和交付模式，通常涉及通过互联网来提供动态易扩展且经常是虚拟化的资源，云是网络、互联网的一种比喻说法。像亚马逊、谷歌、微软、戴尔、IBM、SUN 等许多大型企业都在积极研究云计算技术和基于云计算的服务。中国物联网校企联盟评价云计算为“信息时代商业模式上的创新”。现阶段，云计算仍然在发展中，暂时没有被广泛接受的定义。通过阅读大量文献，云计算定义被总结为：云计算是一种通过 Internet 以服务的方式提供动态可伸缩的虚拟化的资源的计算模式。它具有如下特征：（1）资源配置动态化。因为消费者的需求、用户数量、云中资源的数量、资源的可用性等都是在不断变化的，所以需要动态划分或释放不同的物理和虚拟资源来适应动态变化的环境。云中资源的分布式特性使其能够很好的适应这一环境，因而能够实现 IT资源利用的可扩展性。（2）需求服务自助化。客户能够独立、自主的选择适合自身应用需求的资源服务，在整个选择过程中不需要同提供商进行交互。（3）网络访问便捷化。用户可以不受终端设备的限制，随时随地对网络进行访问，真正实现无处不在的网络访问。（4）服务可计量化。用户在使用云服务的过程中，接受的服务类型是不同的，通过自动控制技术对提供的服务进行统计，从而有效的均衡资源分配。（5）资源的虚拟化。利用虚拟化技术，实现不同地区的计算资源、数据资源以及基础设施资源的充分共享。2.1.2 云计算的分类图2.1 云环境的分类云计算涉及了两个方面，一个是使用 Internet 以服务的形式传递应用，另一个是硬件和系统软件为提供服务所构建的数据中心。数据中心的硬件和软件就是我们所说的云，按提供服务范围的不同被分为三种类型，如上图 2.1 所示。公有云，由若干企业和用户共同使用的云环境，通过互联网广泛的为外部用户提供IT 业务和相关的功能；在公有云环境下，使 Internet 及其相关服务真正的走进千家万户将不在是梦想；在使用过程中用户无需具备该服务在技术层面的知识，无需雇佣相关的技术专家，无需拥有或管理对应的 IT 基础设施。例如 AmazonEC2、Google App Engine和 S 都属于公有云的范畴。私有云，是一个可伸缩的云环境，比公有云更加的灵活、敏捷、高效。它是建立在个人的、专用的基础设施架构上的，可以被托管在自己的数据中心，也可被托管在合作伙伴的数据中心。当你需要加速创新、有大量计算和存储需求、对实时控制和安全性要求较高的时候，私有云是最理想的选择之一。目前开源平台 Rackspace Private Cloud Software 是一个比较成功的能够帮助个人方便、快捷的创建私有云平台的软件。混合云，由公有云环境与私有云环境整合而成。具体的整合方式是由用户根据业务需求和自身因素来选择的。混合云能够有效的解决突发需求、信息实时控制、可扩展性，以及故障转移等问题。通常，公有云和私有云是协调工作，例如网络会议、远程培训这样的服务由公有云提供，而数据仓库、统计分析与决策这样的服务则由私有云提供。由于混合云充分利用并结合了公有云和私有云各自的优势，使其能够更好的协助企业进行构建，有助于企业获得更大的经济效益。2.1.3 云计算的基本服务通常，用户在申请的云平台或云环境中的 IT 基础设施上运行相应的应用。因此，云计算是以透明的方式提供给用户访问硬件、软件和数据资源的服务的综合计算平台：（1）软件即服务（SaaS：Software as a Service）：SaaS 是一种软件交付模式，很多业务应用利用其作为公共交付模式，以减低成本、简化部署，该模式集中托管于云计算环境中，用户可通过互联网随时随地访问。（2）平台即服务（PaaS：Platform as a Service）：平台即服务（PaaS）是一套云交付服务，为云应用开发、部署、管理及整合创造环境。PaaS 借助云工具将应用生命周期中的关键应用开发任务标准化，以降低成本和复杂性，同时加速创造价值。典型平台有：GoogleApps Engine、Windows、Azure（Platform）、F 等。（3）基础设施即服务（IaaS：Infrastructure as a Service）：IaaS 是一个复杂的、可扩展的、可管理的、能够满足用户需求的服务，IaaS 服务可以释放各类企业用于存放、运行、维护设备的资源，尤其适合开发与测试等资源密集型活动。2.1.4 云计算的关键技术云计算的关键技术包括虚拟机、安全管理、数据管理、云检测和能耗管理等（1）虚拟机是云计算的关键技术之一，VMware Infrastructure 是目前主要使用的虚拟机之一,它是一个虚拟数据中心操作系统，可以将离散的硬件资源整合起来以创建共享应用平台。（2）安全管理。云环境是由各种各样的计算资源整合而成的，通过云环境中的任何一台计算机，任何个人信息都能够被找到。云计算安全问题已经成为急需解决的重要问题。为最大限度的保护云中的个人信息，Siani persion 等提出了一些设计原则来解决此问题。（3）数据管理。云计算具有计算能力可变，数据存储在不信任的主机上，数据是远程复制等特点，因此，只有两种数据管理应用程序可能适合部署到云环境中：一是和事务处理相关的数据管理系统；另一种是和分析相关的数据管理系统。（4）云监测和能耗管理。云监测是伴随着云设施的不断增加、云计算的大量普及推广，以及检测云计算强大的计算处理能力而设置的对虚拟机监控的能力。能耗管理的目标是如何节省云设施中计算设施所需要的能源、提高资源的利用率、降低成本。（5）云计算的计算模型。开源框架 Hadoop 是一个典型的云计算模型。Hadoop 是一个由 Apache 开发的分布式系统基本架构，利用 Hadoop 用户可以在不了解分布式底层细节的情况下，开发分布式程序。简单点说 Hadoop 是一个可以更容易开发和运行大规模数据的软件平台。2.1.5 云计算的发展趋势通常花费大部分的资金预算维护已有系统的正常运行，而只有很少的资金用来满足企业日益增长的发展需求，这一反复的循环已成为 IT 领域所面临的核心挑战。目前，已有越来越多的企业，通过利用云来打破这一循环，同时，释放更多的资源来加速企业的革新与发展。云计算赋予了 IT 基础设施灵活、自动、高效，以及提供在线实时服务的力量，这有助于企业把资源从现有系统转移到新的系统上，进而改进操作并推进企业的发展。云是一个强有力的计算组合，它融合了网络、存储、管理，以及商业应用，有利于向消费者提供新一代的 IT 服务。这些服务能够被随时随地的在线提供，而且服务的收费也很合理，安全性也不存在任何争议。我们将进入一个内部互连的“多云的世界”，这将使人们能够在任何时间，任何终端设备上，在世界的任何一个角落，随时享受到需要的服务。为了充分的利用云计算，企业需要根据云服务产品的投入与产出，不断的改进他们的 IT 策略，来实现更大的商业价值，云服务提供商则要更好的管理、监督云资源，为顾客提供高效的服务，与此同时，也实现了利益最大化。2013 年中国云计算发展的趋势如下：（1）努力打造“多云世界”，交通云、政务云、教育云、医疗云等将陆续建成。（2）云计算产业集聚将成为科技园区建设的新热点。（3）国内外企业将在我国云计算市场抢点布局，市场竞争局面初步形成。（4）面向云的软硬件及相关服务将会大面积推广普及，私有云的规划和部署将提到一个更加重要的地位。（5）云计算服务将努力朝着社会化、协作化、网络化的方向发展。（6）政府仍将大力鼓励、支持云计算基础技术的自主研发。（7）大数据的运用将进一步深入到金融企业、电信运营商、电子商务交易平台、社交网络等领域。（8）国内面向个人的云计算服务开始普及推广。（9）开源云平台和工具类软件快速发展，在国内得到广泛应用。（10）国内桌面云部署将兴起，云端时代到来。2.2 DAG相关知识通常使用 DAG(Directed Acyclic Graph)作为一个抽象化的模型来描述工作流，DAG 中的节点表示工作流的任务，节点之间的弧表示工作流任务间的依赖关系。本节着重介绍 DAG作为抽象化模型的一些相关定义、工作流调度算法的分类以及算法的性能评估。2.2.1 工作流的DAG模型一般工作流可分为顺序、并行、选择、循环等结构，其结构示意图如图 2.2 所示。对于复杂的工作流会含有上述的多种结构，目前的工作流调度算法处理的大都是顺序和并行结构的工作流，由于选择和循环结构会出现存在不会执行的节点，和存在不止一次执行的节点，因此需要对含有这两种结构的工作流转换成顺序或者并行结构。a)顺序结构b)并行结构c)选择结构d)循环结构图2.2工作流的常见结构2.2.2 工作流的DAG表示给定工作流的 DAG 模型图 G=, V 表示 DAG 的工作流任务节点集合，即 V=1,2, , n，A 表示 DAG 的有向弧集合，即 A=|i j，i 是 j 的直接前驱，i ,j V。对于 i ,jA，表示i和j存在时间依赖关系，即只有任务i执行完成，节点j 才能开始执行。为了方便描述，工作流有唯一的入口节点和出口节点。对于图 G 中的任意节点 i（入口节点和出口节点除外），都应有至少一个直接前驱和直接后继，用 pre(i)表示节点i的直接前驱的集合，succ(i)表示节点i的直接后继的集合。假设节点i的执行时间为ti，采用关键路径算法可计算出节点i的最早开始时间ESTi(Earliest Start Time)，最早完成时间EFTi(Earliest Finish Time)，最晚开始时间LSTi(Latest Start Time)和最晚完成时间LFTi( Latest Finish Time)，具体的计算式如下：ESTi=0, i=1ESTi=maxjpre(i)EFTj, i1EFTi=ESTi+tiLFTi=EFTi, i=nLFTi=minjsucc(i)LSTj, inLSTi=LFTi-ti根据上述关键路径算法可计算每个节点的最早开始时间和最晚开始时间，如果节点i的ESTi和LSTi相同，则该节点为关键节点。由关键节点组成的路径称为关键路径，记作CP(Critical Path)。对于复杂的 DAG 图，可能存在多条关键路径，本文仅随机选择一条作为该 DAG 的关键路径。2.3 调度算法介绍2.3.1 分层算法逆向分层的截止期分解策略DBL（deadline bottom level）正向分层算法DTL（deadline top level）分层算法DTL和DBL 基于DAG 图中活动的并行和同步特征将截止期分割为层期限，活动在限定时间区间内选择费用最小的服务，所有活动所需的最小费用之和得到工作流的近似最优费用解。两算法均以最快服务为初始分配，松弛时间平均分配到各分组中，且设定第1 层活动的开始时间是0。两者区别在于：DTL 按结点正向深度( 入口结点到该结点的最大路径长度) 分层，规定每层活动有相同开始时间和截止时间，层开始时间是前驱组截止时间，截止时间取同层活动执行时间的最大值；DBL按结点逆向深度( 该结点到出口结点的最大路径长度) 分层，同层活动仅有相同截止时间，取同层活动完成时间的最大值，开始时间分别取所有前驱活动截止时间的最大值。2.3.2 TCDBL基于时序一致的截止期约束逆向分层算法（temporal consistency based deadline bottom level，TCDBL）。TCDBL通过一致性时间点来保证时间约束，解决了DBL的适用性受限问题；同时基于各层并行度分配冗余时间，基于宽松时间约束策略进行费用优化，达到了进一步减少工作流执行费用的目标。TCDBL的主要贡献如下：首先是将时间约束目标从时间分配过程中分离出来，通过任务的一致性时间点来保证工作流的时间约束，解决了DBL中由于缺乏有效的截止时间确定策略而使得算法适用性受限的问题；还有在时间分配过程中考虑各层任务的并行度，为任务数较多的层分配较大的费用优化空间，整体上提高了工作流的费用优化效果；最后是在费用优化过程中采用宽松时间约束策略在任务约束时间的两侧选择服务，减少了执行过程中产生的“时间碎片”，达到了进一步提高算法性能的目标。2.3.3 CACO在不可忽视的通信开销加的工作流费用优化模型中，提出针对该模型的费用优化调度算法CACO（communication aware cost optimization）。CACO基于分层算法，采用前向一致规则（forward consistent，FC）求解最小完工时间，得到准确的截止时间下限，作为有无解的判断；在任务调度过程中，使用动态规划的方法迭代地调整任务的最终最早开始时间和最晚结束时间，收集任务在选择服务时产生的零散“时间碎片”，增加任务的执行时间窗口，提高费用优化效果.实验表明，在考虑通信开销时，CACO费用优化效果较DTL（deadline top level），DBL，TCDBL都有所提高。CACO基于分层算法，在引入通信开销后，由于任务之间通信开销的不确定，加入动态分层。CACO调度CA-DAG模型表示的工作流进行费用优化分为3步：（1）使用FC确定工作流的最小完工时间，作为判断此工作流是否可以调度的依据；（2）分层阶段，采用已有的逆向分层算法，将固定的通信开销（即不考虑2个任务是否在同1台物理机上执行）加入到分层算法中；并得到分层最小完工时间，作为调度阶段的初始状态；（3）调度阶段，使用迭代方式重新调整已调度任务的最终完成时间以及未调度任务的最终最早开始时间，确定未调度任务的时间窗口，进一步收集零散“时间碎片”。在仿真环境中实现了CACO，DTL，DBL和TCDBL，对这些算法的费用优化效果进行了评估.其中DTL和DBL分别是基于正向与逆向分层的工作流优化方法，TCDBL是在逆向分层的基础上提出按并行度分配冗余时间，并基于任务的时序一致性进行调度，将具有同步特征的任务分配到同层进行费用优化。3 仿真器的设计3.1 Java简介Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java是一种简单的，面向对象的，分布式的，解释型的，健壮安全的，结构中立的，可移植的，性能优异、多线程的动态语言。Java技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网等，这次毕设工作选择Java作为编程语言让我可以掌握第二种编程语言，也体会到Java的很多优点，与本科学习的C/C+语言作比较，更好的理解编程语言。 （1）Java语言是简单的。Java语言的语法与C语言和C+语言很接近，使得大多数程序员很容易学习和使用Java。另一方面，Java丢弃了C+中很少使用的、很难理解的、令人迷惑的那些特性，如操作符重载、多继承、自动的强制类型转换。特别地，Java语言不使用指针，并提供了自动的废料收集，使得程序员不必为内存管理而担忧。（2）Java语言是一个面向对象的。Java语言提供类、接口和继承等原语，为了简单起见，只支持类之间的单继承，但支持接口之间的多继承，并支持类与接口之间的实现机制（关键字为implements）。Java语言全面支持动态绑定，而C+语言只对虚函数使用动态绑定。总之，Java语言是一个纯的面向对象程序设计语言。（3）Java语言是分布式的。Java语言支持Internet应用的开发，在基本的Java应用编程接口中有一个网络应用编程接口（javanet），它提供了用于网络应用编程的类库，包括URL、URLConnection、Socket、ServerSocket等。Java的RMI(远程方法激活)机制也是开发分布式应用的重要手段。（4）Java语言是健壮的。Java的强类型机制、异常处理、废料的自动收集等是Java程序健壮性的重要保证。对指针的丢弃是Java的明智选择。Java的安全检查机制使得Java更具健壮性。（5）Java语言是安全的。Java通常被用在网络环境中，为此，Java提供了一个安全机制以防恶意代码的攻击。除了Java语言具有的许多安全特性以外，Java对通过网络下载的类具有一个安全防范机制（类ClassLoader），如分配不同的名字空间以防替代本地的同名类、字节代码检查，并提供安全管理机制（类SecurityManager）让Java应用设置安全哨兵。（6）Java语言是体系结构中立的。Java程序（后缀为java的文件）在Java平台上被编译为体系结构中立的字节码格式（后缀为class的文件）,然后可以在实现这个Java平台的任何系统中运行。这种途径适合于异构的网络环境和软件的分发。（7）Java语言是可移植的。这种可移植性来源于体系结构中立性，另外，Java还严格规定了各个基本数据类型的长度。Java系统本身也具有很强的可移植性，Java编译器是用Java实现的，Java的运行环境是用ANSIC实现的。（8）Java语言是解释型的。如前所述，Java程序在Java平台上被编译为字节码格式，然后可以在实现这个Java平台的任何系统中运行。在运行时，Java平台中的Java解释器对这些字节码进行解释执行，执行过程中需要的类在联接阶段被载入到运行环境中。（9）Java是高性能的。与那些解释型的高级脚本语言相比，Java的确是高性能的。事实上，Java的运行速度随着JIT(Just-In-Time)编译器技术的发展越来越接近于C+。（10）Java语言是多线程的。在Java语言中，线程是一种特殊的对象，它必须由Thread类或其子（孙）类来创建。通常有两种方法来创建线程：其一，使用型构为Thread(Runnable)的构造子将一个实现了Runnable接口的对象包装成一个线程，其二，从Thread类派生出子类并重写run方法，使用该子类创建的对象即为线程。值得注意的是Thread类已经实现了Runnable接口，因此，任何一个线程均有它的run方法，而run方法中包含了线程所要运行的代码。线程的活动由一组方法来控制。Java语言支持多个线程的同时执行，并提供多线程之间的同步机制（关键字为synchronized）。（11）Java语言是动态的。Java语言的设计目标之一是适应于动态变化的环境。Java程序需要的类能够动态地被载入到运行环境，也可以通过网络来载入所需要的类。这也有利于软件的升级。另外，Java中的类有一个运行时刻的表示，能进行运行时刻的类型检查。Java语言的优良特性使得Java应用具有无比的健壮性和可靠性，这也减少了应用系统的维护费用。Java对对象技术的全面支持和Java平台内嵌的API能缩短应用系统的开发时间并降低成本。Java的编译一次，到处可运行的特性使得它能够提供一个随处可用的开放结构和在多平台之间传递信息的低成本方式。特别是Java企业应用编程接口（JavaEnterpriseAPIs）为企业计算及电子商务应用系统提供了有关技术和丰富的类库。3.2 NetBeans简介NetBeans 由Sun公司（2009年被甲骨文收购）在2000年创立，它是开放源运动以及开发人员和客户社区的家园，旨在构建世界级的JavaIDE。NetBeans当前可以在Solaris、Windows、Linux和Macintosh OS X平台上进行开发，并在SPL (Sun公用许可)范围内使用。NetBeans包括开源的开发环境和应用平台，NetBeans IDE可以使开发人员利用Java平台能够快速创建Web、企业、桌面以及移动的应用程序，NetBeans IDE已经支持PHP、Ruby、JavaScript、Groovy、Grails和C/C+等开发语言。NetBeans项目由一个活跃的开发社区提供支持， NetBean开发环境提供了丰富的产品文档和培训资源以及大量的第三方插件。NetBeans是开源软件开发集成环境，是一个开放框架，可扩展的开发平台，可以用于Java、C/C+，PHP等语言的开发，本身是一个开发平台，可以通过扩展插件来扩展功能。在 NetBeans Platform 平台中，应用软体是用一系列的软体模组(Modular Software Components)建构出来。而这些模组是一个jar档(Java Archive File)它包含了一组Java程式的类别而它们实作全依据依 NetBeans 定义了的公开介面以及一系列用来区分不同模组的定义描述档(Manifest File)。有赖于模组化带来的好处，用模组来建构的应用程式可只要加上新的模组就能进一步扩充。NetBeans 平台是一种可重复使用的框架用于简化其他桌面应用程式的开发。当基于NetBeans 平台的应用被执行，平台主要类别的main方法便会被执行。可用的模组会被放置在存储器中，并且开始执行任务。通常模组会只在被需要时，其代码才会被装进内存。应用程式能动态安装模组。任何应用程式能包括更新模组，允许用户申请下载的应用程式升级和加入新功能。这样安装，升级以及新发并行不必迫使用户每次再下载整个应用程式。整个 Netbeans 平台提供对桌面应用程式常用的服务，允许开发者集中于仅限于他的应用程式的逻辑设计。其中 NetBeans 平台的主要特征是：（1） 用户界面管理 User interface management (例如 选单和工具条)（2） 用户设定管理 User settings management（3） 存储管理 Storage management(保留和装任何种类数据)（4） 视窗管理 Window management（5） 引导框架 Wizard framework(一步一步支援对话框)3.3 XML简介可扩展标记语言XML（eXtensible Markup Language）是一种简单灵活的文本格式的可扩展标记语言，起源于SGML(Standard Generalized Markup Language)，是SGML的一个子集合，也就是SGML的一个简化版本，非常适合于在Web上或者其它多种数据源间进行数据的交换。（1）用途可扩展标记语言 (Extensible Markup Language, XML) ，用于标记电子文件使其具有结构性的标记语言，可以用来标记数据、定义数据类型，是一种允许用户对自己的标记语言进行定义的源语言。XML是标准通用标记语言 (SGML) 的子集，非常适合 Web 传输。XML提供统一的方法来描述和交换独立于应用程序或供应商的结构化数据。（2）格式特性XML与Access、Oracle和SQL Server等数据库不同，数据库提供了更强有力的数据存储和分析能力，例如：数据索引、排序、查找、相关一致性等，XML仅仅是存储数据。事实上XML与其他数据表现形式最大的不同是：他极其简单，这是一个看上去有点琐细的优点，但正是这点使XML与众不同。XML与HTML的设计区别是：XML 被设计为传输和存储数据，其焦点是数据的内容。而HTML 被设计用来显示数据，其焦点是数据的外观。HTML 旨在显示信息，而 XML 旨在传输信息。XML和HTML语法区别：HTML的标记不是所有的都需要成对出现，XML则要求所有的标记必须成对出现；HTML标记不区分大小写，XML则 大小敏感,即区分大小写。（3）结合SGML、HTML是XML的先驱。SGML是指“通用标识语言标准”(Standard Generalized Markup Language), 它是国际上定义电子文件结构和内容描述的标准，是一种非常复杂的文档的结构，主要用于大量高度结构化数据的防卫区和其他各种工业领域，利于分类和索引。同XML相比，定义的功能很强大，缺点是它不适用于Web数据描述，而且SGML软件价格非常昂贵。 HTML相信大家都比较熟悉，即“Hyper Text Markup Language” （超文本标识语言）,它的优点是比较适合web 页面的开发。但它有一个缺点是标记相对少，只有固定的标记集如.等。缺少SGML的柔性和适应性。不能支持特定领域的标记语言，如对数学、化学、音乐等领域的表示支持较少。举个例子来说，开发者很难在web pape 上表示数学公式、化学分子式和乐谱。 Xml 结合了sgml 和html的优点并消除其缺点。Xml 仍然被认为是一种sgml语言。比sgml要简单，但能实现sgml的大部分的功能。1996年的夏天，Sun Microssystem的John Bosak开始开发W3C SGML工作组（现在称为xml工作组）。他们的目标是创建一种sgml，使其在Web中，既能利用Sgml的长处，又保留html的简单性。现在目标基本达到。XML的简单使其易于在任何应用程序中读写数据，这使XML很快成为数据交换的唯一公共语言，虽然不同的应用软件也支持其它的数据交换格式，但不久之后他们都将支持XML，那就意味着程序可以更容易的与Windows、Mac OS、Linux以及其他平台下产生的信息结合，然后可以很容易加载XML数据到程序中并分析它，并以XML格式输出结果。（4）友好为了使得SGML显得用户友好，XML重新定义了SGML的一些内部值和参数，去掉了大量的很少用到的功能，这些繁杂的功能使得SGML在设计网站时显得复杂化。XML保留了SGML的结构化功能，这样就使得网站设计者可以定义自己的文档类型，XML同时也推出一种新型文档类型，使得开发者也可以不必定义文档类型。（5）简明语法SGML常用来定义针对HTML的文档类型定义（DTD），同时它也常用于编写XML的DTD。SGML的问题就在于它允许出现一些奇怪的语法，这让创建HTML的解析器成为一个大难题：这些问题使建立一个SGML语言的解析器变成了一项艰巨的任务，判断何时应用以上规则的困难导致了SGML语言的定义一直停滞不前，以这些问题作为出发点，XML逐渐步入我们的视野。XML去掉了之前令许多开发人员头疼的SGML的随意语法。在XML中，采用了如下的语法：这些规则使得开发一个XML解析器要简便得多，而且也除去了解析SGML中花在判断何时何地应用那些奇怪语法规则上的工作。仅仅在XML出现后的前六年就衍生出多种不同的语言，包括MathML、SVG、RDF、RSS、SOAP、XSLT、XSL-FO，而同时也将HTML改进为XHTML。3.4 DAG的XML表示XML表示DAG有着结构清楚，表达方便，让人理解起来比较简单。修改方便，生成和解析都有已有的工具，学习和应用比较容易。XML表示DAG结构图如图3.1所示。在xml文件中最大的标签DAG下属包含表示DAG最主要信息的节点和边集标签Nodes和Edges。Nodes中包含着一个DAG图的所有节点及其属性。一个节点中含有多个服务，服务总标签为Services，包含多个service小标签。service中是每一个具体服务的参数，子标签包括serviceName、cost、time、machine。Edges中包含着一个DAG图的所有边信息，下属是每一个边的具体信息，一个edge标签表示一条边，子标签包含edgeName和transTime。其中edgeName是以边的起始节点到终止节点表示的，中间以“-”分割的。图3.1 XML表示DAG结构图XML表示DAG代码实例T0