Round-Robin Approach

The round-robin approach is commonly used for scheduling time-shared applications. When jobs are scheduled in a round-robin system, every job joins a first-in-first-out (FIFO) queue when it becomes ready for execution. The job at the head of the queue executes for at most one-time slice. If the job does not complete by the end of the time slice, it is preempted and placed at the end of the queue to wait for its next turn.

When there are n ready jobs in the queue, each job gets one time slice in n that is in every round. The length of the time slice is relatively short (typically tens of milliseconds) so the execution of each jobs begins almost immediately after it becomes ready.

Generally, each job gets 1/nth share of the processor when there are n jobs ready for execution. This is why the round-robin algorithm is also known as the processor-sharing algorithm.

Weighted Round-Robin Approach:

The weighted round-robin algorithm is used for scheduling real-time traffic in high-speed switched networks. In this approach, different jobs may be given different weights rather than giving an equal shares of the processor for ready jobs.

In weighted round robin each job Ji is assigned a weight Wi where each job will receive Wi consecutive time slices each round, and the duration of a round is equals to the sum of the weights of all the ready jobs for execution. We can speed up or slow down the progress of each job by adjusting the weights of jobs.

When fraction of time of processor allocated to a job then a round-robin scheduler delays the completion of every job. If round-robin scheduling is used to schedule precedence constrained jobs then response time of set of jobs becomes very large.

For this reason, the weighted round-robin approach is unsuitable for scheduling such jobs.

For example consider two sets of jobs J1 = {J1, 1, J1 , 2} and J2 = {J2, 1, J2 , 2}

  • The release times of all jobs are 0
  • The execution times of all jobs are 1
  • J1, 1 and J2, 1 execute on processor P1
  • J1, 2 and J2, 2 execute on processor P2
  • Suppose that J1, 1 is the predecessor of J1, 2
  • Suppose that J2, 1 is the predecessor of J2, 2

Figure (a) shows ‘weighted round-robin scheduling’ that both sets of jobs complete approximately at time 4. If the jobs are scheduled in a weighted round-robin manner one after the other, one of the chains can complete at time 2 and the other at time 3 shown in figure (b).

Suppose that the result of the first job in each set is piped to the second job in the set then second job be executed latter after each one or a few time slices of the former complete. Then it is better to schedule the jobs on a round-robin basis, because both sets can complete a few time slices after time 2.

In a switched network a downstream switch can begin to transmit an earlier portion of the message as soon as it receives the portion. It does not have to wait for the arrival of the rest of the message. The weighted round-robin approach does not require a sorted priority queue, only a round-robin queue. This is a distinct advantage for scheduling message transmissions in ultrahigh-speed networks since fast priority queues are very expensive