Weighted Round-Robin CPU Scheduling Algorithm
Department of Computer Science
Georgia State University
Atlanta, GA 30303 USA
Thursday April 29, 2004
ABSTRACT
There are advantages and disadvantages to many different CPU scheduling algorithms. The Weighted Round-Robin (WRR) CPU Scheduling algorithm is based on the round-robin and priority scheduling algorithms. The WRR retains the advantage of round-robin in eliminating starvation and also integrates priority scheduling. WRR is a preemptive algorithm that will implement several techniques. WRR will integrate an aging process, alter the time slice for each process according to “weight”, and also reorder the process queue according to “weight”.
1. INTRODUCTION
The round-robin (RR) CPU scheduling algorithm has advantages and disadvantages. An advantage of RR is that starvation is never a problem. RR ensures that all processes in the job (process) queue share a time slice on the processor. Time slicing is defined as the allocation of limited intervals of time (quanta) to programs in contention for use of the CPU. [2] A time slice is simply an amount of time that each job (process) will spend on the processor per iteration of the RR algorithm. All jobs are done in a FCFS algorithm fashion but are preempted after a time slice. The job will either finish in the time slice given or the job will be returned to the tail of the job queue and return to the processor at a later time. This is a disadvantage since all jobs are basically given the same priority. RR also favors short virtual processes and penalizes long ones. [3]
Another problem of RR is that the time slice value must be correct. If the time slice value is too small the context switching time is large in relation to actual work done on the CPU. The time slice value also needs to be small enough to prevent RR from becoming a non-preemptive FCFS algorithm. A good rule of thumb is that the value should be of adequate length to ensure that 80% of all jobs can be completed in one time slice. [5]
Priority scheduling can either be preemptive or non-preemptive. Regardless of type, priority scheduling has problems with starvation. A process will lose control of the CPU through one of the following: task completion, a higher priority task becoming ready, or a wait condition. [1] Higher priority processes becoming ready can cause lower priority processes to be neglected. Even in non-preemptive priority scheduling a high priority process that takes a long time on the CPU will create a starvation environment. Aging implementation and the weighting of processes along with the basic RR structure helped with the solution.
2. WEIGHTED ROUND-ROBIN CPU SCHEDULING ALGORITHM
The WRR CPU scheduling algorithm uses the advantage of RR in eliminating the problem of starvation. It then implements a priority-based technique in several areas. The structure for the WRR is similar to the RR in that it is simply a FCFS queue (job list). A full job queue cycle is when all jobs have had a chance to share time on the processor. In the case that all jobs are at the same weight, FCFS is implemented.
All processes in the job queue are given time on the processor in the form of a time slice, thereby eliminating concern for starvation. This means that with WRR no process can hold the CPU for extended periods of time. Also short processes that get re-queued often will not have to wait for longer higher priority processes since all jobs in the queue will be granted time on the processor. This is why the value of the time slice (minimum value), prior to change in relation to weight, is important. This time slice variable in WRR is varied for each individual job according to the weight given to it by the operating system. The time slice will never be below a certain threshold while as the weight increases the time slice increases. A higher weight process is given a longer time slice. This will give critical jobs a longer time on the processor per iteration.
The WRR also uses this priority weight to assign the order of the jobs in the job queue. The job queue will be reordered after a full job queue cycle with the highest priority jobs demanding the processor time first. This will enable high priority jobs to get the processor time first and always be at the beginning of the job queue. Once a job has completed, a new process is allowed in the queue. At this point, the jobs are reordered in descending weight and the algorithm continues.
The WRR also will implement the concept of aging. Aging is when a process that returns to the job queue will be given a “bump” in weight. In the case of WRR the algorithm will increase the weight of that job by a value of one for every three full job queue cycles it is processed.
A general sequence of the algorithm is listed below:
1. All new jobs are entered into the job queue
2. Aging: All jobs are evaluated if an increase in weight is needed
3. New jobs are assigned a time slice value according to weight
4. Job queue reordered with higher weight at front
5. All jobs are given time on processor.
6. Return to 1.
3. SIMULATION
We chose to simulate the WRR CPU scheduling algorithm in the .NET environment using C#. There are no considerations for context switching implemented. The program allows the user to manipulate the standard time slice (“time on processor”), job length (“CPU time”), and job weight individually. It then outputs the completion times for the processes and the user can visually compare the completion time for both the RR and the WRR algorithms. The program limits the user to choose from four processes and limits the weight levels from one to four. Even with these restrictions the program allows the user to vary different areas of the algorithm while holding other parts constant.
4. CONCLUSION
A scheduling algorithm needs to be tested in these three areas: fairness, responsiveness, and efficiency. [4] Measurement of the algorithm is critical in order to measure outcome. Our algorithm sacrificed in the efficiency area in order to be successful in the fairness and responsiveness areas.
The Weighted Round Robin CPU Scheduling algorithm implements the advantages of both the round robin and priority-based algorithms. Weight-based processes finish faster which makes up for some loss in efficiency. In several cases the average wait times were actually better in WRR than with RR. Also, the WRR will never encounter a starvation environment since all processes share time on the processor. The weight assigned to processes will create a longer time slice and also reorder the queue based on job priority.
5. REFERENCES
[1] Harry Katzan, Jr., “Operating Systems / A Pragmatic Approach”, pages 113, 157, 350-353, Van Nostrand Reinhold Company, 1973.
[2] Stanley A.Kurzban, Thomas S. Heines, and Anthony P Sayers, “Operating Systems Principles”, pages 50-52, 370-371, Van Nostrand Reinhold Company, 1984.
[3] Philipe A. Jansen, “Operating Systems / Structures and Mechanisms” pages 77-80, Academic Press, Inc., 1985.
[4] William Stallings, Ph.D., “Operating Systems / Internals and Design Principles”, pages 75-76, 406-408, Prentice Hall, 2001
[5] Silbershatz, Galvin, and Gagne, “Operating System Concepts”, pages 157-166, John Wiley and Sons, Inc., 2002.