Modeling and Performance Analysis of Grid Task Scheduling Based on Composition and Reduction of Petri Nets
Modeling and Performance Analysis of Grid Task Scheduling Based on Composition and Reduction of Petri Nets
复制标题
DOI：
10.1109/gcc.2006.62
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
Yaojun Han;Xuemei Luo
中科院分区：
文献类型：
--
作者：
Yaojun Han;Xuemei Luo
任务调度是网格计算环境中最重要和最困难的问题之一。尽管提出了一些网格任务调度算法，但网格计算中任务调度的形式化建模和分析尚未引起更多关注。在我们之前的工作中，提出了一种高级定时 Petri 网来对网格任务的工作流程进行建模。但它只专注于独立任务。在本文中，我们解决由一组通信子任务组成的任务的调度问题。首先，构建子任务的扩展定时 Petri 网模型（ETPN）。为了降低模型复杂度和Petri网可达性分析中的状态爆炸问题，利用Petri网的复合和约简得到任务的Petri网模型。给出了ETPN可达任务图(RTG)的构造算法。最后，通过分析ETPN的RTG，给出了验证网格任务调度正确性和分析系统时间性能的方法。
Task scheduling is one of the most important and difficult issues in grid computing environment. Although some algorithms for grid task scheduling were proposed, formal modeling and analysis for task scheduling in grid computing have not given more attention. In our previous work, a high-level timed Petri net to model the workflow of grid tasks was proposed. But it only focused on independent tasks. In this paper, we tackle the scheduling problem of task that consists of a set of communicating subtasks. First, an extended timed Petri net model (ETPN) for a subtask is constructed. In order to reduce the complexity of model and the state explosion problem in reachability analysis of Petri nets, a Petri net model for a task is gotten using composition and reduction of Petri nets. A construction algorithm for reachable task graph (RTG) of ETPN is given in this paper. Finally, we give the methods to verify the correctness of the grid task scheduling and analyze time performance of system by analyzing RTG of ETPN