Developing a Platform Using Petri Nets and GPenSIM for Simulation of Multiprocessor Scheduling Algorithms
Source abstract
Abstract
Efficient multiprocessor scheduling is pivotal in optimizing the performance of parallel computing systems. This paper leverages the power of Petri nets and the tool GPenSIM to model and simulate a variety of multiprocessor scheduling algorithms (the basic algorithms such as first come first serve, shortest job first, and round robin, and more sophisticated schedulers like multi-level feedback queue and Linux’s completely fair scheduler). This paper presents the evaluation of three crucial performance metrics in multiprocessor scheduling (such as turnaround time, response time, and throughput) under various scheduling algorithms. However, the primary focus of the paper is to develop a robust simulation platform consisting of Petri Modules to facilitate the dynamic representation of concurrent processes, enabling us to explore the real-time interactions and dependencies in a multiprocessor environment; more advanced and newer schedulers can be tested with the simulation platform presented in this paper.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Petri Nets in System Modeling · Real-Time Systems Scheduling · Distributed systems and fault tolerance
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Electrical Engineering and Computer Science, University of Stavanger, 4036 Stavanger, Norway
School of Computer Science and Engineering, Chongqing Three Gorges University, Wanzhou, Chongqing 404000, China
References (27)
Show source-provided references
1. GPenSIM (2020, July 20). General-Purpose Petri Net Simulator. Technical Report. Available online: http://www.davidrajuh.net/gpensim.
2. The End of Moore’s Law: A New Beginning for Information Technology10.1109/MCSE.2017.29 ↗
3. Arpaci-Dusseau, R.H., and Arpaci-Dusseau, A.C. (2018). Operating System; Three Easy Pieces. Arpaci-Dusseau Books, CreateSpace Independent Publishing Platform.
4. Scheduling algorithms
5. Mohammadi, A., and Akl, S.G. (2005). Scheduling Algorithms for Real-Time Systems, School of Computing Queens University.
6. Some simple scheduling algorithms10.1002/nav.3800210113 ↗
7. Genetic algorithm for multiprocessor scheduling10.1109/71.265940 ↗
8. An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling10.1109/TPDS.2004.38 ↗
9. Multiprocessor Scheduling Using Hybrid Particle Swarm Optimization with Dynamically Varying Inertia
10. Multiprocessor Scheduling with the Aid of Network Flow Algorithms10.1109/TSE.1977.233840 ↗
11. An Application of Bin-Packing to Multiprocessor Scheduling10.1137/0207001 ↗
12. The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems10.1109/TC.2006.113 ↗
13. Leontyev, H., and Anderson, J.H. (2007, January 3–6). Generalized Tardiness Bounds for Global Multiprocessor Scheduling. Proceedings of the IEEE International Real-Time Systems Symposium, Tucson, AZ, USA.10.1109/RTSS.2007.33 ↗
14. Guan, N., Stigge, M., Yi, W., and Yu, G. (2010, January 12–15). Fixed-Priority Multiprocessor Scheduling with Liu and Layland’s Utilization Bound. Proceedings of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2010, Stockholm, Sweden.10.1109/RTAS.2010.39 ↗
15. Kasahara, H., and Narita, S. (1999). Practical multiprocessor scheduling algorithms for efficient parallel processing. Syst. Comput. Jpn., 16.10.1002/scj.4690160202 ↗
16. Liu, S., Quan, G., and Ren, S. (2011, January 21–24). On-line scheduling of real-time services with profit and penalty. Proceedings of the 2011 ACM Symposium on Applied Computing, Tai Chung, Taiwan.10.1145/1982185.1982501 ↗
17. Leakage-Aware Multiprocessor Scheduling10.1007/s11265-008-0176-8 ↗
18. Using processor-cache affinity information in shared-memory multiprocessor scheduling10.1109/71.207589 ↗
19. Veltman, B.B. (1993). Multiprocessor Scheduling with Communication Delays. [Ph.D. Thesis, CWI].
20. Garcia, R.C., Chung, J.M., Jo, S.W., Ha, T., and Kyong, T. (2014, January 22–25). Response time performance estimation in smartphones applying dynamic voltage & frequency scaling and completely fair scheduler. Proceedings of the IEEE International Symposium on Consumer Electronics, Jeju, Republic of Korea.10.1109/ISCE.2014.6884484 ↗
21. Petri nets: Properties, analysis and applications10.1109/5.24143 ↗
22. Peterson, J.L. (1981). Petri Net Theory and The Modeling of Systems, Prentice Hall PTR.
23. Davidrajuh, R. (2021). Petri Nets for Modeling of Large Discrete Systems, Springer.10.1007/978-981-16-5203-5 ↗
24. Davidrajuh, R. (2018). Modeling Discrete-Event Systems with GPenSIM, Springer International Publishing.10.1007/978-3-319-73102-5 ↗
25. Davidrajuh, R. (2023). Colored Petri Nets for Modeling of Discrete Systems: A Practical Approach with GPenSIM, Springer Nature.10.1007/978-981-99-6859-6 ↗
26. Jain, R. (1991). The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling, Wiley.
27. Summary cache: A scalable wide-area Web cache sharing protocol10.1109/90.851975 ↗