Petri Net: Design and Analysis of Parallel Task Scheduling Algorithm
In real time, most of the tasks are deadline based. The deadline-based task has different parameters: arrival time, start time, execution time, and deadline. Many performance-based task scheduling algorithms are proposed by number of researchers theoretic
- PDF / 487,694 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 68 Downloads / 221 Views
Abstract In real time, most of the tasks are deadline based. The deadline-based task has different parameters: arrival time, start time, execution time, and deadline. Many performance-based task scheduling algorithms are proposed by number of researchers theoretically. But due to change of implement environment, the performance varies. Petri net is a graphical and mathematical model to evaluate and analysis of the system. In Petri net, conflicts are occurred during firing. In this paper, we designed and modeled the Petri net for scheduling deadline-based task by resolving the conflicts. We also proposed a scheduling mechanism and firing rules to schedule deadline-based tasks. The designed model increases the resource utilization of a physical system in cloud computing. The performance of the proposed model is analyzed using the PIPE v4.3.0. We analyzed the reach ability graph, convertibility graph, and steady-state analysis of the model.
Keywords Task Deadline Scheduling Reach ability Convertibility
Backfilling Petri net
S. Parida (&) S.C. Nayak P. Priyadarshi G. Ray Department of Computer Science and Engineering, C.V. Raman College of Engineering, Bhubaneswar, India e-mail: [email protected] S.C. Nayak e-mail: [email protected] P. Priyadarshi e-mail: [email protected] G. Ray e-mail: [email protected] P.K. Pattnaik School of Computer Engineering, KIIT University, Bhubaneswar, India e-mail: [email protected] © Springer Nature Singapore Pte Ltd. 2018 A. Kalam et al. (eds.), Advances in Electronics, Communication and Computing, Lecture Notes in Electrical Engineering 443, https://doi.org/10.1007/978-981-10-4765-7_79
765
766
S. Parida et al.
1 Introduction Since the last few years, task scheduling in cloud computing comes forward as a challenging and interesting area for researchers. A better resource utilization can be achieved by adapting new and modified task scheduling algorithms. The basic concept of task scheduling is to schedule all the tasks within the deadline with limited resources. Optimal scheduling problem is known as NP-hard problem [1]. In cloud computing, the pool of resources is distributed geographically and is available for the users on pay for use basis. Resources are allocated or released according to the requirement of user applications at any time and charged. However, resource under-provisioning usually decreases the system’s performance, whereas resource over-provisioning always leads to idle resources [2]. Therefore, it is a challenge for cloud providers to provide the exact amount of cloud resources to the user with minimum cost. The OpenNebula is one of the open source cloud platforms which provides a flexible platform for both cloud users and cloud service providers. The OpenNebula supports basically three types of leases: (1) Advance reservation, (2) Best Effort Leases, and (3) Immediate Leases [3]. The user request is called task or lease in OpenNebula. In real time, when a time constraint is associated with the best effort lease, it is
Data Loading...
