Source-linked AI summary
A New Round Robin Based Scheduling Algorithm for Operating Systems: Dynamic Quantum Using the Mean Average
Abbas Noon, Ali Kalakech, Seifedine Kadry
TL;DR
RR’s fixed time quantum is presented as a source of scheduling problems, and the paper proposes AN, which dynamically selects the quantum from burst times in the ready queue. The authors report improved results over RR, including lower turnaround and waiting times in tested cases.
Problem
Method
AN dynamically adjusts the time quantum using burst times of processes in the ready queue.
Source: §1 · p. 2, §3.1 · p. 2Results
Takeaways & Limitations
The authors present automatically calculated dynamic quantum as a route toward an operating system that adapts to user requirements without user intervention.
Source: §5 · pp. 5–6
Abstract
from arXiv · showhide
Round Robin, considered as the most widely adopted CPU scheduling algorithm, undergoes severe problems directly related to quantum size. If time quantum chosen is too large, the response time of the processes is considered too high. On the other hand, if this quantum is too small, it increases the overhead of the CPU. In this paper, we propose a new algorithm, called AN, based on a new approach called dynamic-time-quantum; the idea of this approach is to make the operating systems adjusts the time quantum according to the burst time of the set of waiting processes in the ready queue. Based on the simulations and experiments, we show that the new proposed algorithm solves the fixed time quantum problem and increases the performance of Round Robin.
1. Introduction
The introduction frames CPU scheduling as a central operating-system task and presents Round Robin (RR) as widely used for time-sharing. It identifies fixed time quantum as a weakness and introduces AN’s dynamic-quantum approach.
1. Introduction
- CPU scheduling allocates CPU time to a process, while the dispatcher gives control to the process selected by the short-term scheduler.The introduction lists fairness, efficiency, response time, turnaround, and throughput as scheduling criteria.Source: §1 · p. 1
- FCFS dispatches processes in arrival order and lets each run to completion, so long jobs can make short jobs wait.The paper describes FCFS as formally or humanly fair, but unfair in how long or unimportant jobs delay others.Source: §1 · p. 2
- SJF orders processes by their estimated remaining processing time and minimizes average turnaround and waiting time, but requires prior burst-time knowledge and can starve processes.The paper describes SJF as usable in both preemptive and non-preemptive forms.Source: §1 · p. 2
- RR uses a fixed per-process time unit and cycles through processes, but the paper associates that fixed quantum with poor turnaround and waiting times.RR is described as designed for responsiveness; the quantum is usually 10–100 milliseconds.Source: §1 · p. 2
- AN is proposed to address RR’s constant-time-quantum problem by adjusting the quantum to the burst times of processes in the ready queue.The paper outlines the proposed algorithm, simulations, and conclusion as the following sections.Source: §1 · p. 2
2. Previous works
Prior work addresses RR’s fixed-quantum problem through median-based quantum selection, process weighting, and combinations with other scheduling algorithms. The paper positions AN among these efforts.
2. Previous works
- RR’s fixed, predetermined time quantum is described as a persistent problem despite its widespread use, and prior efforts are said to remain insufficient.The paper notes RR’s use in operating systems including Windows, BSD, and UNIX-based systems.Source: §2 · p. 2
- Matarneh uses the median burst time as the quantum, with a 25 ms minimum to avoid context-switch overhead; other median-based work also reports good results.The minimum applies when the median is below 25 ms.Source: §2 · p. 2
- Helmy et al. weight processes to combine low RR scheduling overhead with preference for short jobs, while other work [4] uses mathematical procedures.Higher weights give relatively longer time quanta, intended to let shorter jobs leave the ready queue earlier.Source: §2 · p. 2
- Other proposed algorithms combine priority scheduling with RR or combine SJF with RR.The paper also cites additional efforts to improve scheduling performance,, and.Source: §2 · p. 2
3. AN Algorithm
AN sets the time quantum dynamically from burst times in the ready queue. Its procedure initializes and updates queue statistics as processes arrive, execute, finish, or return to the queue.
3. AN Algorithm
- AN adjusts the time quantum according to the burst times of processes in the ready queue.The method is presented as a solution to the time-quantum problem.Source: §3 · p. 2
3.1 Methodology
- At startup, the quantum equals the first dispatched process’s burst time; when a process arrives, the system averages the queue’s burst times, including the arrival.SR stores the sum of remaining burst times and AR stores their average; both are updated as processes finish a slice or burst, with unfinished processes returned to the queue.Source: §3.1 · pp. 2–3
3.2 Pseudo Code and Flow Chart
- The pseudocode sets the quantum to the process burst time when the queue is empty, or to the average burst time of queued processes otherwise, then updates the queue statistics after execution.A process that is not terminated returns to the ready queue with its updated burst time.Source: §3.2 · p. 3
4. Simulations
The simulations compare AN with Round Robin using fixed quantum values, evaluating average turnaround and waiting times across test samples. AN reports lower values in every tested case, with the same result across several fixed quantum choices.
4. Simulations
- The comparison function evaluated 50 samples, each with four processes and randomly chosen arrival and burst times from 10 to 100 ms.The figures use samples on the x-axis and average turnaround time or average waiting time on the y-axis.Source: §4 · p. 4
- AN produced lower average turnaround and waiting times in every tested case than Round Robin with a 10 ms quantum.The figures plot the tested samples; lower vertices represent lower averages.Source: §4 · p. 4, Figure 2 · p. 4, Figure 3 · p. 4
- The authors report the same results when Round Robin’s fixed quantum is 15, 20, 25, or 30 ms.Source: §4 · p. 4
4. Results and Observations
Across the reported four-process cases, the dynamic-quantum approach based on mean burst time outperformed fixed-quantum Round Robin and the method in on the reported measures. The paper also describes a repeated halving pattern in processes remaining across rounds and a way to avoid unnecessary switches when only one process remains.
4. Results and Observations
- The four numerical cases compare AN with fixed 20 ms Round Robin and the method in, using both simultaneous and staggered arrivals.Source: §4 · p. 4
- Across four cases, the mean-based dynamic quantum was more effective than fixed-quantum Round Robin and the method in, reducing context switches, turnaround time, and waiting time.The authors also report that calculating the mean has very small complexity.Source: §4 · pp. 4–5
4.3 Success in Statistics
- The success statistic counts samples where AN’s vertex is below Round Robin’s, divided by the total number of samples.Table 2 is captioned as reporting AN’s success-over-failure percentage; its values are not stated in the supplied passages.Source: §4.3 · p. 5, Table 2 · p. 5
4.4 Improvement in Context Switches
- The authors report that half the processes terminate in the first round and half the remainder in each later round, with at most six rounds regardless of process count or burst time.Figure 4 depicts the decrease in the number of processes in each round.Source: §4.4 · p. 5, Figure 4 · p. 5
- When one process remains in the ready queue, AN sets its quantum to its remaining burst time, avoiding the extra switch described for other Round Robin variants.The paper also relates context-switch count to the number of processes in each round.Source: §4.4 · p. 5
5. Conclusion
The paper presents AN’s dynamic-quantum approach as a step toward optimal scheduling, with simulations reporting higher performance than RR. The authors say further research is needed to reach that goal.
5. Conclusion
- AN uses dynamic time quantum so the operating system finds the optimal quantum without user intervention.The paper frames this as an answer to the question of what RR time quantum to use.Source: §5 · p. 5
- The authors describe AN as a simple step toward an optimal scheduling algorithm, while noting that reaching that goal needs much more research.Source: §5 · p. 5
- Simulations report AN performs better than RR in any system.The authors also say dynamic scheduling increased operating-system performance and stability and supports building a self-adapting operating system.Source: §5 · p. 6