A Hybrid Algorithm for Processor Scheduling Using Game Theory Variants

Year : 2025 | Volume : 12 | Issue : 01 | Page : 48-56
    By

    Yamuna Mundru,

  • Manas Kumar Yogi,

  1. Assistant Professor, Department of Computer Science and Engineering, Artificial Intelligence & Machine Learning, Pragati Engineering College (Autonomous), Surampalem, Andhra Pradesh, India
  2. Assistant Professor, Department of Computer Science and Engineering, Pragati Engineering College (Autonomous), Surampalem, Andhra Pradesh, India

Abstract

This study proposes a novel hybrid algorithm for processor scheduling in modern operating systems, integrating the strengths of traditional scheduling methods with game theory variants. Traditional schedulers often struggle to adapt to dynamic workload changes, leading to suboptimal performance. Our hybrid approach addresses this by treating processes as “players” in a game, where the “payoff” is CPU time. A base scheduler (e.g., Weighted Fair Queuing, Earliest Deadline First) provides a foundation for fairness and efficiency. A game theory module then refines scheduling decisions by dynamically adjusting parameters based on process utilities, reflecting their importance, resource needs, and behavior. We explore various game theory approaches, including non-cooperative, cooperative, and evolutionary games, each offering different trade-offs between individual process benefit and overall system performance. The algorithm dynamically adapts scheduling parameters (e.g., priorities, time slices) based on the game’s outcome. This combined method strives to create a more effective balance between fairness, efficiency, and adaptability. We discuss the algorithm’s components, including utility function design and game variant selection, and analyze its potential advantages and challenges, such as computational complexity and parameter tuning. Future research directions, including exploring machine learning for adaptation, are also outlined.

Keywords: Game theory, processor, operating system, convoy effect, scheduling

[This article belongs to Journal of Operating Systems Development & Trends ]

How to cite this article:
Yamuna Mundru, Manas Kumar Yogi. A Hybrid Algorithm for Processor Scheduling Using Game Theory Variants. Journal of Operating Systems Development & Trends. 2025; 12(01):48-56.
How to cite this URL:
Yamuna Mundru, Manas Kumar Yogi. A Hybrid Algorithm for Processor Scheduling Using Game Theory Variants. Journal of Operating Systems Development & Trends. 2025; 12(01):48-56. Available from: https://journals.stmjournals.com/joosdt/article=2025/view=203780


References

  1. Dirdal DO, Vo D, Feng Y, Davidrajuh R. Developing a Platform Using Petri Nets and GPenSIM for Simulation of Multiprocessor Scheduling Algorithms. Appl Sci. 2024 Jun 29; 14(13): 5690.
  2. Papp PA, Anegg G, Karanasiou A, Yzelman AJ. Efficient Multi-Processor Scheduling in Increasingly Realistic Models. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures. 2024 Jun 17; 463–474.
  3. Acharya B, Panda S, Sivakumar E. An analytical study of multiprocessor scheduling using metaheuristic approach. SN Comput Sci. 2022 Sep 29; 3(6): 497.
  4. Lima G, Massa E, Regnier P. Practical considerations in optimal multiprocessor scheduling. In Handbook of real-time computing. Singapore: Springer Nature Singapore; 2022 Aug 9; 193–231.
  5. Liu X, Li W. Approximation algorithms for the multiprocessor scheduling with submodular penalties. Optim Lett. 2021 Sep; 15: 2165–80.
  6. González-Rodríguez M, Otero-Cerdeira L, González-Rufino E, Rodríguez-Martínez FJ. Study and evaluation of CPU scheduling algorithms. Heliyon. 2024 May 15; 10(9): e29959.
  7. Omar HK, Jihad KH, Hussein SF. Comparative analysis of the essential CPU scheduling algorithms. Bull Electr Eng Inform. 2021 Oct 1; 10(5): 2742–50.
  8. Gandhi N, Yadav M, Senthil A. Multiprocessor Scheduling Algorithm based on 2D Cellular Automata. International Conference on Innovative Science & Engineering Technology (ICISET-11). 2011.
  9. Ali SM, Alshahrani RF, Hadadi AH, Alghamdi TA, Almuhsin FH, El-Sharawy EE. A review on the cpu scheduling algorithms: Comparative study. International Journal of Computer Science & Network Security (IJCSNS). 2021; 21(1): 19–26.
  10. Chen J, Wang Y, Zhang Y, Lu Y, Li Q, Shu Q. Non-Preemptive Scheduling of Periodic Tasks with Data Dependencies in Heterogeneous Multiprocessor Embedded Systems. ACM Trans Des Autom Electron Syst. 2025 Feb 7; 30(2): 1–25.
  11. Tian S, Ren W, Deng Q, Zou S, Li Y. A predictive energy consumption scheduling algorithm for multiprocessor heterogeneous system. IEEE Trans Green Commun Netw. 2021 Nov 30; 6(2): 979–91.
  12. Gong M, Goebel R, Lin G, Miyano E. Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing. J Comb Optim. 2022 Aug; 44(1): 877–93.
  13. Gong M, Lin G. Improved approximation algorithms for multiprocessor scheduling with testing. In International Workshop on Frontiers in Algorithmics. Cham: Springer International Publishing; 2021 Aug 16; 65–77.
  14. Sotskov YN, Mihova EI. Scheduling multiprocessor tasks with equal processing times as a mixed graph coloring problem. Algorithms. 2021 Aug; 14(8): 246.
  15. Sudvarg M, Gill C, Baruah S. Improved implicit-deadline elastic scheduling. In 2024 IEEE 14th International Symposium on Industrial Embedded Systems (SIES). 2024 Oct 23; 50–57.
  16. Acharya B, Panda S, Ray NK. Multiprocessor task scheduling optimization for cyber-physical system using an improved salp swarm optimization algorithm. SN Comput Sci. 2024 Jan 10; 5(1): 184.
  17. Zhao Q, Qu M, Gu Z, Zeng H. Minimizing stack memory for partitioned mixed-criticality scheduling on multiprocessor platforms. ACM Trans Embed Comput Syst. 2022 Mar 4; 21(2): 1–30.
  18. Agarwal G, Gupta S, Ahuja R, Rai AK. Multiprocessor task scheduling using multi-objective hybrid genetic Algorithm in Fog–cloud computing. Knowl-Based Syst. 2023 Jul 19; 272: 110563.
Regular Issue Subscription Review Article
Volume 12
Issue 01
Received 21/02/2025
Accepted 25/02/2025
Published 18/03/2025
Publication Time 25 Days
Total Visits: 44


My IP

PlumX Metrics