CPU Scheduling Techniques

Round-Robin Scheduling

It is the CPU Scheduling Technique specially designed  for the time shared systems. This Technique is similar to FCFS Technique but the difference is that processes are switched at a regular interval of time and the regular internal is called time quantum.The can be from 0 to 100 milliseconds.

The ready queue is used in a circular fashion. The CPU is allocated to each process for a regular interval of time of 1 time quantum each new process is added to the tail ready queue. CPU scheduling picks first process from ready queue, set a timer to interrupt after 1 time quantum and then process is dispatched.If the burst time of process is less than a time quantum then it will automatically release the CPU.The average waiting time a round Robin policy is often high.

Consider the following ready queue of processes.
Process               Burst time
   P1                           10
   P2                           20
   P3                           5


Let the time Quantum be 5 miliseconds. The Gantt chart will be as given below

Now the average wait time for P1 is (15-5) 10 milliseconds, for P2=(20-5) 15 Milliseconds,and for P3=10 millisecond. i.e. the total average wait time is :10 + 15 + 10 /3 =11.66 Milliseconds

The performance for this Technique depands upon time quantum. If it is too high this algorithm will work like FCFS Technique and if it is too low than it creates the appearance that n processes are running with their own processor at a speed of 1/n.

Priority Scheduling

It is a CPU Scheduling Technique in which CPU is allocated to the process with highest priority. Equal priority processes are served in FCFS order.Priority is indicated by fixed range of numbers, it can be 0 to 10 or 0 to 1000. However there is no protocol that whether 0 will be highest priority or lowest. Some systems used lower numbers as lower priority and some systems uses lower numbers as highest priority.

Consider the following set of processes assumed to arrive at 0 in the order P1, P2 and P3 with the CPU Burst time in milliseconds.
Process             Burst time           Priority
    P1                       10                        3
    P2                       5                          1
    P3                       6                          2


Gantt Chart using priority scheduling will be.

The average wait time is :   0+5+11/3= 5.3333 miliseconds

The priority cab be assigned internally or externally, priority scheduling can be preemptive or non-preemptive. Whenever a process comes to ready queue its priority is compared with current running process and if its priority is high CPU will be preempted. A non-preemptive priority algorithm just puts the new process at the head of ready queue.

Major problem with this scheduling Technique is indefinite blocking or starvation. Because a low priority process has to wait for a indefinite time until its turn come. To avoid the problem of starvation a Technique is used which is called aging. In this Technique priority of a process is increased which is waiting in the ready queue for long time.

Shortest Job First (SJF) CPU Scheduling

It is a CPU Scheduling Technique in which CPU is allocated to the process whose burst time is minimal.
Consider the following set of processes with the length of the CPU burst given in millisecond.
Process             Burst time
   P1                         10
   P2                          5
   P3                          1
   P4                          4



Using SJF Scheduling we Schedule these process according to Gantt chart as:

The waiting time for P3 is 0 for P4 it is 1, P2 is 5 and P1 is 10 Hence the average waiting time is (0+1+5+10/4)=4 milliseconds.
But if we calculate this by FCFS algorithm it comes: 0+10+15+16/4=10.25 milliseconds

Thus SJF gives optimal performance. It gives minimum average waiting for a set of processes.The main problem of this scheduling Technique is knowing the length of the next CPU request. This approach can not be used with short term scheduling because there is no way to know the length of next CPU burst time.

First Come First Serve (FCFS) CPU Scheduling

It is the simplest CPU scheduling algorithm in which CPU is allocated first to the process that request it first. This policy is managed by FCFS queue. When CPU is free it is allocated to the first process of the ready Queue and the running process is removed from the ready queue. The code generation for FCFS algorithm is simple. The main draw back of this technique is that average waiting time of a process is quite long.Consider the Following queue of process.

Process              Burst Time
    P1                         10
    P2                         40
    P3                         1


Let the process arrive in the order P1,P2 and P3 in ready queue and are to be served in FCFS order. The Gantt chart we will get is:

The waiting time for process P1 is 0 and P2 is 10 and for P3 is 50.The average wait time is 0+10+50/3=20 milliseconds.

This CPU scheduling Technique is a non-preemptive and if once the CPU has been allocated to a process, it will keep until it releases the CPU by termination request or process completion.