Scheduling and Synchronization Algorithms in Operating System: A Survey

Main Article Content

Mohammed Y. Shakor

Abstract

An operating system is software that is designed to manage computer hardware and software resources. However, this management requires applying an ample number of techniques and algorithms which are called synchronization and scheduling. The scheduling algorithms are used to arrange the way that the CPU is assigned to the processes, while synchronization is utilized to indicate how to work with multi-processes at the same time. Therefore, they are related to each other. CPU scheduling is a vital phenomenon of an operating system. At present, numerous CPU scheduling algorithms exist as First Come First Serve) FCFS(Shortest Job First (SJF), Shortest Remaining Time First (SRTF), Priority Scheduling, and Round Robin (RR). In this paper, a survey of the current synchronization and scheduling algorithms have been presented. An overview of each technique with the main algorithms have been described in detail with the advantages and the issues of each algorithm. Furthermore, this paper has dug deep into the real-time operating system scheduling issues, which is the current trend in operating system researches.

Article Details

How to Cite
Shakor, M. Y. (2021). Scheduling and Synchronization Algorithms in Operating System: A Survey. Journal of Studies in Science and Engineering, 1(2), 1–16. https://doi.org/10.53898/josse2021121
Section
Review Articles

References

M. L. Pinedo, Scheduling: theory, algorithms, and systems. Springer, 2016.

K. Ramamritham and J. A. Stankovic, “Scheduling algorithms and operating systems support for real-time systems,” Proc. IEEE, vol. 82, no. 1, pp. 55–67, 1994.

B. Andersson, S. Baruah, and J. Jonsson, “Static-priority scheduling on multiprocessors,” in Real-Time Systems Symposium, 2001.(RTSS 2001). Proceedings. 22nd IEEE, 2001, pp. 193–202.

A. Singh, P. Goyal, and S. Batra, “An optimized round robin scheduling algorithm for CPU scheduling,” Int. J. Comput. Sci. Eng., vol. 2, no. 7, pp. 2383–2385, 2010.

R. K. Yadav and A. Upadhayay, “A fresh loom for multilevel feedback queue scheduling algorithm,” Int. J. Adv. Eng. Sci., vol. 2, no. 3, pp. 21–23, 2012.

H. S. Behera, R. K. Naik, and S. Parida, “Improved multilevel feedback queue scheduling using dynamic time quantum and its performance analysis,” Int. J. Comput. Sci. Inf. Technol., vol. 3, pp. 3801–3807, 2012.

L. M. Ni and K. Hwang, “Optimal load balancing in a multiple processor system with many job classes,” IEEE Trans. Softw. Eng., no. 5, pp. 491–496, 1985.

D. M. Brooks et al., “Power-aware microarchitecture: Design and modeling challenges for next-generation microprocessors,” IEEE Micro, vol. 20, no. 6, pp. 26–44, 2000.

L. Wang, J. Tao, G. von Laszewski, and H. Marten, “Multicores in Cloud Computing: Research Challenges for Applications.,” JCP, vol. 5, no. 6, pp. 958–964, 2010.

C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” J. ACM, vol. 20, no. 1, pp. 46–61, 1973.

A. Burns, Preemptive priority based scheduling: An appropriate engineering approach. University of York, Department of Computer Science, 1993.

N. C. Audsley, A. Burns, R. I. Davis, K. W. Tindell, and A. J. Wellings, “Fixed priority pre-emptive scheduling: An historical perspective,” Real-Time Syst., vol. 8, no. 2–3, pp. 173–198, 1995.

S. B. N. Meghanathan, “A survey of contemporary real-time operating systems,” Informatica, vol. 29, no. 2, 2005.

J. A. Stankovic and R. Rajkumar, “Real-time operating systems,” Real-Time Syst., vol. 28, no. 2–3, pp. 237–253, 2004.

M. Quigley et al., “ROS: an open-source Robot Operating System,” in ICRA workshop on open source software, 2009, vol. 3, no. 3.2, p. 5.

A. Silberschatz, P. B. Galvin, and G. Gagne, Operating system concepts essentials. John Wiley & Sons, Inc., 2014.

E. W. Dijkstra, “Solution of a problem in concurrent programming control,” in Pioneers and Their Contributions to Software Engineering, Springer, 2001, pp. 289–294.

A. S. Tanenbaum, “Processes and Threads,” Mod. Oper. Syst., 2008.