Various Variants of Round Robin Scheduling Algorithm

Abstract

In order to use the computer processor efficiently, different scheduling algorithms are used to manage the execution of multiple processes. One popular algorithm is called Round Robin (RR), where each process is given a short amount of time to run on the processor before switching to the next process in the queue. The length of this time period, called a time quantum, is important in determining how efficient the scheduling is. If the time quantum is too long, it can increase the time it takes for a process to respond. If it is too short, it can increase the amount of time the processor spends switching between processes instead of actually executing them. In this paper, we explore different variants of the RR algorithm and compare their performance in terms of waiting time, turnaround time, and the number of times the processor switches between processes.

Introduction

I. INTRODUCTION

An operating system manages computer programs, in- cluding scheduling them to use the CPU efficiently. Dif- ferent scheduling algorithms are used, such as ”First Come First Serve”, ”Shortest Job First”, ”Fixed Priority Preemptive Scheduling”, and ”Round Robin Scheduling”. The main goal of these algorithms is to maximize processor utilization and throughput, while minimizing waiting time, turnaround time, and response time. However, context switching can lead to wasted time and memory. CPU scheduling involves various algorithms to determine the order in which processes access the CPU. Key algorithms include First Come First Serve (FCFS), where processes are scheduled in the order they arrive, and Shortest Job First (SJF), which gives the CPU to the process with the shortest burst time first. SJF can be non-preemptive or preemptive, with the latter allowing a process to be preempted if a shorter job arrives. Fixed Priority Preemptive Scheduling assigns the CPU based on process priority, scheduling the highest priority process first. Round Robin Scheduling assigns each process a fixed time quantum in a cyclic order, preempting the process when its time quantum expires and placing it at the end of the ready queue. The main aim of scheduling algorithms is to maximize throughput and processor utilization. Performance parameters include context switches, which store and restore the state of preempted processes; processor utilization, which measures how busy the processor is; throughput, defined as the number of processes completed per unit of time; waiting time, which is the total time a process waits in the ready queue; turnaround time, the interval from submission to completion of a process; and response time, the time from submission of a request to the first response.

II. RELATED WORK

In recent years, numerous CPU scheduling algorithms have been developed. For instance, Rami J. Matarneh [6] proposed a method where the time quantum is selected based on the median of all processes in the ready queue. If the median is greater than 25, the time quantum is set to the median; otherwise, it is set to 25. This approach ensures that 50% of the remaining processes will be completed in each round.

Negi [7] introduced an approach that extends the time quantum for processes that require only a slightly more amount of time than the allocated fixed time quantum to complete.

Hiranwal et al. [8] suggested arranging processes in non- decreasing order of their burst time and using a smart time quantum for servicing the processes. If the number of pro- cesses is odd, the time quantum equals the burst time of the middle process; if even, the average burst time is used.

Dawood [9] proposed a method where the time quantum is determined by summing the maximum and minimum burst times and then multiplying the result by 0.80, based on the rationale that 80

III. DIFFERENT ROUND ROBIN TECHNIQUES:

1. Normal Round Robin scheduling algorithm assigns a fixed time slice to each process, regardless of their specific characteristics or resource requirements.

This fixed time slice may not be optimal for all processes, as some may require more time to complete their tasks, while others may need less. Therefore, the overall system performance may not be optimal with a fixed time slice.

2. Adaptive Round Robin scheduling algorithm adjusts the time slice dynamically based on the characteristics and resource requirements of each process. The algorithm monitors the behavior of the processes and adjusts the time slice accordingly. If a process is using fewer resources, it is assigned a smaller time slice, while if a process is using more resources, it is assigned a larger time slice. This helps to ensure that each process is given enough time to complete its tasks, while also maximizing the overall system performance. That is we initially sort the processes in order of there BurstTime and then take the median value of the burst time as the Time quantum (q).

3. Modified Additive Round Robin uses   a   dynamic time slice that changes according to the priority of the process and the time it has spent waiting in the ready queue.in MARR, the time slice is calculated by adding a dynamic factor to the base time slice, based on the priority and waiting time of the process. TQ = [(Burst Time of all processes) / Number of processes] + C

4. SARR is an adaptive algorithm that adjusts the time quantum for each process based on its behavior. SARR starts by allocating a small time quantum, and if a process finishes its work in that time, it gets a shorter time quantum in the next round. If a process requires more time, it gets a longer time quantum. This way, the algorithm can adapt to the behavior of different processes and optimize the use of CPU time. Time Quantum = Base Quantum * Round Robin Factor * Aging Factor Base Quantum = (Total Burst Time of all Processes)/(Number of Processes * RR fact) Aging Factor = (Time in Ready Queue + Base Quantum) / Base Quantum

5. AQMMRR stands for Adaptive Queue Management Multi-Round Robin scheduling algorithm. It is a CPU scheduling algorithm that aims to improve the perfor- mance of Round Robin by dynamically adjusting the time quantum for each process based on the process behavior and system load. This algorithm utilizes multiple queues to manage the processes based on their priority levels and their past execution behavior. The time quantum for each process is calculated using a dynamic formula that takes into account the priority level, the waiting time, and the execution history of the process. AQMMRR also includes a mechanism for preemptive execution of higher priority processes and ensures fairness by periodically redistributing the processes across the queues.[1,2,3] Now, as we have looked at the various forms of RoundRobin (RR), let’s implement them to a problem and see the difference in their performances. Also, for a better visual representation we will plot a bar graph for the same.

Conclusion

this paper explores different forms of the Round Robin (RR) algorithm, which is used to manage the execution of multiple processes and maximize processor utilization while minimizing waiting time, turnaround time, and response time. Different variants of the RR algorithm are compared based on their performance in terms of waiting time, turnaround time, and the number of times the processor switches between processes. The paper discusses Normal RR, Adaptive RR, Modified Additive RR, SARR, and AQMMRR scheduling algorithms. An implementation of these algorithms to a problem is provided, and a comparison is made based on the average waiting time and turnaround time. MARR and AQMMRR are found to give the lowest average waiting and turnaround time. Finally, the paper suggests combining MARR and AQMMRR for better performance. Hence, we have successfully found a new advanced algorithm which can be implemented for a far better average waiting and an average turn around time.

References

[1] Silberschatz, A., Galvin, P. B., Gagne, G. (2018). Operating System Concepts (10th ed.). John Wiley Sons, Inc. Tanenbaum, A. S., Bos, H. (2014). Modern Operating Systems (4th ed.). Prentice Hall Press. [2] Singh, S., Mahajan, S. (2019). Comparative analysis of round robin scheduling algorithms. International Journal of Computer Sciences and Engineering, 7(8), 649-654. [3] Zahran, A. H. (2018). Dynamic time slice in round robin scheduling algorithm. Journal of Computer Science and Technology, 18(2), 234-240. [4] Singh, A., Gupta, A., Saxena, N. (2017). AQMMRR: A novel adaptive queue management multi-round robin scheduling algorithm for real-time systems. Journal of Systems and Software, 125, 91-105. [5] Sandeep Negi, Priyanka Kalra A Comparative Performance Analysis of Various Variants of Round Robin Scheduling Algorithm International Journal of Information & Computation Technology ISSN 0974-2239 Volume 4, [6] Number 7 (2014), pp. 765-772 [7] Matarneh Rami J., “Self adjustment time quantum in round robin algorithm depending on burst time of the now running process”, Department of Management Information Systems, American Journal of Applied Sciences 6 (10): 1831-1837, 2009, ISSN 1546-9239. [8] Negi Sandeep, “An Improved Round Robin Approach using dynamic time quantum for improving average waiting time”, International Journal of Computer Applications: Vol. 69 No 14, 2013. [9] Hiranwal Saroj, Dr. Roy K. C., “ Adaptive round robin scheduling using shortest burst approach based on smart time slice”, Volume 2, No. 2, July-Dec 2011, pp:319-32. [10] Dawood Ali Jbaeer, “ Improving efficiency of round robin scheduling using ascending quantum and [11] minimum-maximum burst time”, Journal of University of ambar for pure science : Vol. 6: No 2, 2012,

Copyright

Copyright © 2024 Roshi Bhati, Rahul Thambi, Nikhil Nerurkar. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.