Round Robin scheduling is one of the commonly used preemptive scheduling in interactive
environments. The processor time is divided into slice or quanta, which are allocated to requestors. No process can run
more than one time slice where there are other processes waiting in the ready
queue.
RR scheduling is similar to FCFS scheduling, but
preemption is added to switch between processes. The time slice is range from
10 to 100 milliseconds.
 |
| |
Implementation
of the RR scheduling requires the support of a time. The timer is usually set to interrupt the operating system whenever a time slice expires and thus
forces the scheduler to be invoked. The
scheduler stores the context of the running process, move it to the end of the ready queue (means, to the tail of the
ready queue), and the process at the
head of the read queue is scheduled to run. The scheduler is also invoked to
dispatch a new process whenever the
running process surrenders control to the operating system before expiration of
its time quantum. The timer is reset that point.
RR scheduling is often regarded
as a fair scheduling discipline since it provides equal share of system
resources to requestors. The average waiting time under the RR policy is often
long. Short processes may be executed within a single time slice and thus
exhibit good response time. Long processes may require several quanta, and thus
be forced to cycle through the ready queue a few times before completion.
RR scheduling policy does
not do well in terms of system performance measured in terms of throughput,
since it treats all requests alike and does not give favoured treatment to
short jobs.
For example, consider the following five processes
P1, P2, P3, P4, and P5 in the same order of arrival.
Process
|
CPU time or Burst time
(in ms)
|
P1
|
5
|
P2
|
15
|
P3
|
12
|
P4
|
25
|
P5
|
8
|
Assume that we use a time
quantum of 10 milliseconds. The Gantt chart is given below;
 |
| Gantt Chart |
If there are n processes
in the ready queue and the time slice is x, then each process gets 1/n
of the CPU time in chunks of at most x time units. Each process must
wait no longer than (n — 1) * X time units until its next time
quantum.
For example, with five
processes and a time quantum of 10 milliseconds, each process will get up to 10
milliseconds every 50 milliseconds.
The performance of RR
scheduling is very sensitive to the choice of time slice. The relationship
between magnitude of the time slice and the response time is non-linear. For
example, too short time slices results in significant overhead due to frequent
timer interrupts and process switches. On the other hand, short time slices reduce
the preemption overhead but increases the response time and hence RR scheduler
transforms to an FCFS scheduler.
NEXT: LCN Scheduling
Previous: Deadline Scheduling
Index : Operating System
No comments:
Post a Comment