عنوان مقاله
یک الگوریتم برنامه‌ریزی منبع شبکه بندی بر پایه شبکه های پتری تصادفی تعمیم یافته
فهرست مطالب
چکیده
مقدمه
مدل زمان بندی خدمات شبکه بندی
نتیجه گیری
بخشی از مقاله
مدل زمان‌بندی خدمات شبکه بندی
در خدمات شبکه‌بندی، زمان‌بندی وظیفه برای ترسیم کردن وظایف برروی منبع محاسباتی توزیع شده غیر همگن می‌باشد و زمان‌بندی با هدف منابع بهینه را جستجو می‌کند. در این مقاله، زمان‌بندی وظیفه بر روی یک دسته از وظایف مستقل با محدودیت‌های کیفیت خدمات تمرکز کرده است.
کلمات کلیدی:
A GSPN-based Grid Resource Schedule Algorithm Zhi-xiang YUAN School of Computer Science Anhui University of Technology Maanshan, 243002,China zxyuan@ahut.edu.cn Jun Zhou School of Computer Science Anhui University of Technology Maanshan, 243002,China Hong Ye School of Computer Science Anhui University of Technology Maanshan, 243002,China Abstract—The paper analyses the load imbalance problem and the QoS-based fault-tolerant scheduling algorithm in Grid Resource Scheduling, and proposes a new scheduling algorithm based on the priority of a task-based parameters of Qos constrained scheduling strategy. The method is based on using the generalized stochastic Petri nets with inhibitor arc to establish the grid scheduling model and improve the Min-Min algorithm. Experimental results show that the algorithm can decrease the overall cost of time and cost, when the Grid Resource Schedule runs an urgent task. Keywords—Grid computing, Resource scheduling, The Generalized stochastic Petri net, QoS constraint, load balance I. INTRODUCTION Resource Scheduling has played an important role in Resource Optimization of Service Computing. There are many Resource Scheduling algorithms and models in recent years[1]. As methods of modeling and analyzing physical systems, Petri nets have shown their abilities to deal with concurrence conflict and have been widely used to model, analyze, and verify workflow . Because the application of Service Computing is similar to workflow , which is composed of service task, Petri Nets have mainly been used for modeling and analysis of grid service[2,3]. In this paper, we discuss the modeling and analysis approach for this kind of Grid services based on Petri net. In previous modeling approaches for grid computing based on Petri nets, Dario present a methodology to analyze performance in gLite Grids through the use of Generalized Stochastic Petri Nets (GSPNs),and introduce a cluster-level model of a typical gLite site taking into account the coexistence between normal and MPI-based jobs[4]. The application which runs on the grid and provides continuous service has the dynamic reconfiguration capability to ensure the consistency of the system. Reliable services composition can be achieved through modeling and analysis of Web service composition. The method of the use of Petri net for modeling and analysis of service composition is researched in the paper[5,6]. The problem of quality of service (QoS) is the vital issue to the grid scheduling model. The scheduler in the Grid environment needs to consider application and QoS constraints to get a better match between applications and resources [7,8,9,12,13]. A QoS guided task Min-Min algorithm has been proposed in the papersto solve the QoS based scheduling problem, which based on the task requirement of QoS, classifies tasks into two categories: high QoS-requiring tasks and low QoS-requiring tasks, and schedules the two groups separately. However the Min-Min scheduling algorithm has load imbalance problem. We investigate the influence of several parameters (e.g., priorities, scheduling policies)on both the performance and benefits, study Qos-based fault-tolerant scheduling algorithm in Grid Resource Scheduling, then propose a new scheduling algorithm based on the priority of a task-based parameters of Qos constrained scheduling strategy. The Petri Net-based model grid services is presented for the grid service scheduling, which is the generalized stochastic Petri nets with inhibitor arc. the new scheduling algorithm merges the efficiency of Min-Min and the load balance of Max-Min for every QoS level group scheduling. The experimental results show that the algorithm can decrease the overall cost of time and cost, When the Grid Resource Schedule runs an urgent task. II. THE GRID SERVICE SCHEDULING MODEL A. Problem Description In Grid service, task scheduling is to map tasks onto heterogeneous distributed computing resource and search the schedule with optimum resources objective. In this paper, task scheduling focuses on a class of independent tasks with QoS constraints. Let m independent tasks to be scheduled on n service resources(machines). Let {t1,t2,…,tm}be the metatask with all the dependent tasks, and {R1,R2,…,Rn} be machines in Grid. The problem for resource scheduling tries to find the schedule with optimum objective, which maps n tasks onto m machines. The goal of problem is that how to find the minimum makespan. Due to the heterogeneity of Grid resource and OoS requirements, the user can set the task priority, time and cost constraints, and set the ratio of time and cost. This paper mainly focuses on how to map tasks to machines in order to optimize cost, priority and completion time for the metatask. Let Lij be the completion time which task ti run on resource Rj. Let eij be the expected execution time which task ti runs on resource Rj. Let Sij be the transmission time which task ti transfer to resource Rj. Let rj be the ready time for resource Mj. Let Pij be the price which task ti transfer to resource Rj. Let the require data throughput of the task ti be Si. Let bw(j) be the bandwidth. Let Mi be the maximum running cost of task ti .Let Ti be the maximum running time of task ti.
