基于语义网格环境的资源共享模型与分布式资源调度算法研究

王帅+马景奕

摘要：为解决多资源文件共享和语义网格环境下异构资源共享管理问题，提出了一种新的分布式调度算法。该算法采用语义网格的分布式技术，充分利用资源共享模型实现高效的资源调度。仿真实验表明，该算法具有较好的执行效率。与其它算法相比，在相同任务数量时响应更快。

关键词：语义网格；轻量级目录访问协议；资源共享模型；分布式调度算法；资源发现

DOIDOI：10.11907/rjdk.172030

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2017）012-0064-03

Abstract：rid is a hot technology for sharing， managing information resources and providing information services. In the current situation of increasingly serious environmental pollution， green cloud computing has become an important issue in the field of green communications.

In order to solve the problems in the management of heterogeneous resources in multi resource file sharing and semantic sharing in grid， this paper proposes a new distributed scheduling algorithm， the algorithm adopts the distributed semantic grid technology， and make full use of the resource sharing model， to achieve efficient resource scheduling， the simulation results show that the proposed algorithm has good execution efficiency， at the same time the number of tasks in response， faster response， and prove the effectiveness of the algorithm.

Key Words：semantic grid； lightweight directory access protocol； resources sharing model； distributed scheduling algorithm； resource discovery

0 引言

网格技术是新兴的互联网技术，是下一代互联网技术研究和应用的重要领域 [1]。近年来，物联网、车联网、云计算、大数据、绿色通信、量子通信、智慧城市、智能家居、深度學习等新概念和新技术层出不穷，语义网格逐渐引起人们的关注。网格是协调管理各种地理分布资源的手段，为用户提供透明、一致的访问接口，实现资源共享 [2]。

互联网页面大多数基于Web页面技术，它的缺点是用HTML编写，这种语言主要用于文本格式化，而不是识别和标记内容。同时，受限于用户端，加载效率、兼容性不高。新的HTML标准已经扩展（元标签），可向页面添加更多信息，用于标记整个页面，而不是在给定页面上的内容描述[3]。HTML页面的另一个目标是提供到其它页面和信息源链接。语义Web应用于网格环境，形成语义网格，用于描述网格中信息的语义网格元数据。语义网格是网格相关技术的延伸，包括信息和服务，可使计算机系统与人更好地协同工作。语义网格通常是网格和语义Web技术的多重组合，通过不同组合提高计算能力和数据集成能力。

为解决多资源文件共享和语义网格环境下的管理问题，本文提出了一种基于语义网格环境的文件资源共享模型和分布式调度算法。该模型将注册通知机制、确定性算法与非确定性算法消息传递机制互相组合，从而对网格中的各节点进行有效管理调度。本文提出一种新的分布式调度算法（NDSA），用于解决语义网格中的异构资源共享问题。图1 描述的是语义网格的文档结构。

通过应用语义网格的分布式技术，将两者有机结合，可极大提高资源调度的利用率。

1 语义网格资源共享模型

资源信息表现在两个方面：①存储在数据库或其它介质中的信息通过可视化呈现给用户；②针对存储介质中的信息 [4]创建多个中间层信息，中间层在应用逻辑层中用相应的数据表示。

元数据是描述数据的数据，是对数据对象的抽象描述，使各种信息体现在属性和值之间的关系上[5]。资源目录服务功能模块为分布式资源共享模型提供Grid信息服务[6]。资源目录由元数据描述的所有资源构成。资源目录服务的主要任务是管理网格中的各种资源，包括资源发现、注册、修改和取消。系统使用LDAP（轻量级目录访问协议）目录服务器存储资源目录信息[7]。LDAP目录树结构以树级结构存储数据，以条目的形式存储一组属性，每条记录包括属性类型和属性值，一个属性可以存储多个值。LDAP数据库的灵活性和可扩展性，非常适用于广域分布式资源共享系统。每个网格节点都要注册本地资源来查找和收集监控，并且每个节点维护本地LDAP服务器和本地存储的资源信息。图2描述的是语义网格之间的数据共享过程。

2 网格任务调度算法

通过互联网将不同地理位置的分布式计算资源、存储资源、通信资源、软件资源、信息资源和知识资源集成为一个巨大的超级计算机，各种资源实现共享，这是网格作业调度的主要任务[8]。用户向网格系统提交计算任务，为了共享网格资源和网格调度器，这些任务被分配到适当的调度资源上。高效的调度策略或算法可以利用网格系统的处理能力，提高面向对象的应用性能。在网格调度算法中，策略的主要目的是提高图2 语义网格之间的数据共享过程

系统吞吐量和利用率，通过经济系统和用户约束，使整个系统任务中的网格最小化。遗传算法创建一个调度集合，从中找到最佳调度，这种继承特性可以遗传到下一代，遗传算法通过适应度函数交叉和重组实现最优调度[9]。这是一种迭代算法，它具有吸收系统在演变过程中的变化差异优势，并能够适应网格系统的动态变化。

在网格技术的许多问题中，网格计算、任务调度是一般形式的NP问题，没有最优解。有效的调度算法，如并行资源分配决策和分布式调度算法，并不能很好地适应资源异构性网格的各种特性。因此，如何合理地分配和管理网格资源以满足广泛的服务需求，实现资源的最佳利用，成为该领域研究的关键。

网格任务调度可分为通信间任务、任务组调度和独立任务组调度。集中式调度是系统中的中央调度员，负责收集状态信息并作出所有调度决策。机器周期性地将分组更新到其发送状态，报告其负载信息；中央调度服务建立一个主机候选者序列表，以响应客户请求的远程执行。解决容错集中调度问题的典型方法是提供多个备用服务员[10]。

3 实验与结果分析

在Matlab环境下设计网格任务调度系统仿真程序。该程序根据主机处理能力、主机数量、任务数量、每个任务的预测执行时间、通信开销和时间的仿真等需求，生成任务开销和其它参数。

图3显示的是在语义网格环境中3种算法的负载均衡度比较。负载均衡度越高，表明该算法执行的效果越理想，资源利用的公平性越好。随着系统任务数量的不断增加，NDSA算法性能始终优于其它两种算法。

图4显示的是3种调度算法的响应时间比较。图5和图6分别显示在不同进化代数和不同任务规模时，3种调度算法的执行时间情况。

4 结语

网格技术作为一种高性能的广域分布式计算模型，是许多机构的研究热点。Matlab仿真实验结果表明，本文提出的分布式调度算法（NDSA）具有较好的执行效率，在相同任务数量时响应速度更快，可在网格资源中实现公平有效的任务调度；在负载均衡度、系统响应时间、系统执行时间等方面，NDSA算法都比传统的Max-min算法和GA算法表现出更佳的性能，该算法能有效应用到語义网格各领域。

参考文献：

[1] I FOSTER， C KESSELMAN，S TUECKE.The anatomy of the grid： enabling scalable virtual organizations[J]. International Journal Supercomputing Application， 2001，15（3）：200-222.

[2] M KAYA.Multi-objective genetic algorithm based approaches for mining optimized fuzzy association rules[J]. Soft Comput，2006，10（7）：578-586.

[3] L C JIAO， L WANG. A novel genetic algorithm based on immunity [J].IEEE Transaction on Systems， Man， and Cybernetics-Part A，Systems and Humans， 2000，30（5）：552-561.

[4] ZHONG WEI CAI， LIU JING， XUE MING ZHI， et al. A multi-agent genetic algorithm for global numerical optimization[J]. IEEE Trans.System，Man and Cybernetics—Part B，2004，34（2）：1128-1141.

[5] T HONG， C CHEN， Y WU， et al.A GA-based fuzzy mining approach to achieve a trade-off between number of rules and suitability of membership functions[J].Soft Comput，2006，10（11）：1091-1101.

[6] WANNENG SHU， SHIJUE ZHENG.A Real-course-based load balanced algorithm of VOD cluster[C].2005 International Symposium on Computer Science and Technology （ISCST 2005），Ningbo，2005.

[7] ZHANG JIANG SHE， XU ZONG BEN， LIANG YI. Global Annealing genetic algorithm and its convergence well necessary condition [J].science in China（Series E），1997，27（2）：154-164.

[8] WANG XIA， ZHOU GUO BIAO. Strong convergence of global annealing genetic algorithm[J]. mathematica applicata，2003，16（3）：1-7.

[9] RAJKUMAR BUYYA， DAVID ABRAMSON， JONATHAN GIDDY. Grid resource management， scheduling， and computational economy [C].WGCC，Japan， 2000.

[10] 孙清超，孙伟，郭钢.多项目环境下复杂产品开发资源动态分配技术[J].中国机械工程，2011，22（23）：2844-2848.

[11] 熊张悦，姜俊颖，舒万能.绿色云计算的任务调度与能耗优化机制研究[J].软件导刊，2016，15（4）：38-40.

（责任编辑：杜能钢）