Scheduling Algorithms in CPU

 

 

 

   

    What do you mean by CPU Scheduling ?

    

     CPU Scheduling deals with deciding of allocation of processes to the CPU which 

     are in the  ready queue.Basically this allocation is done with the help of certain

     algorithms. Scheduling Algorithms in CPU are of two types

    

       1 Preemptive Scheduling Algorithm: In this algorithm the CPU is allocated the

          process by the operating system with respect to its priority ie it does not wait

          for the process requests. This type of scheduling is useful for high priority

          process which requires immediate response. Examples are as follows:

                

                a. Round Robin Scheduling Algorithm

                b. Priority based scheduling

                c. Shortest Remaining Time  Next.

      2. Non Preemptive Scheduling Algorithm:This algorithm always process the 

          request according to the scheduled time. once a CPU has been allocated to

         a process it cannot be taken back until the process is executed.Examples are

         as follows:

 

                a. First come First serve

                b. Shortest Job First

  

    Performance evaluation of the Scheduling algorithm:

 

     From the many scheduling algorithms the performance of  the algorithms 

     depends basically on two factors:

       1. Maximum CPU Utilization

       2. Maximum Throughput

 

     Lets see it with the help of an example where we have the following five processes

     arrived at time 0.

 

    

Process	Processing Time
P1	10
P2	20
P3	03
P4	07
P5	12

 

           

 

 If we apply the FCFS algorithm for the set of process The Gantt Chart will be as follows:

                    P1            P2            P3        P4           P5 

              0         10                39         42         49           61

 

 

      Process                   Processing Time                   Waiting Time

    

         P1                                  10                                     0

         P2                                  29                                    10

         P3                                  03                                    39

         P4                                  07                                    42

         P5                                  12                                    49

     Average Waiting Time = (0+10+39+42+49)/5 = 28milliseconds

 

 

     Now if we consider the Shortest Job First  Scheduling Algorithm The Gantt

     Chart will be as follows:

      
                   P3            P4            P1       P5           P2 

              0         3               10            20         32           61

     
    Process                   Processing Time                   Waiting Time

    

         P1                                  10                                    10

         P2                                  29                                    32 

         P3                                  03                                    00

         P4                                  07                                    03

         P5                                  12                                   20

 

Average Waiting Time =(10+32+03+20)/5 = 13milliseconds 

 

Now if we compare average waiting time of above algorithm we see that SJF 

policy result in half of the average waiting time that has been allocated to FCFS.