Process Scheduling

Process Scheduling

First-Come, First-Served (FCFS) Scheduling

FCFS is the simplest schedule algorithm. By this algorithm processes enter into processor as arrival order. Process stays in processor until finishes. During this process other processes are queued and they wait to finish the current process. Below there is simulation example for this algorithm:

Process No	Burst Time
P₁	8
P₂	5
P₃	13
P₄	3

Shortest Job First (SJF)

SJF algorithm was developed on the assumption that burst time is known for every process. Firstly all bust times are sorted in ascending order. Then starting from smallest burst time processes are sent to processor. Here is the example of this algorithm:

----------------------------------

| Shortest Job First |

|--------------------------------|

| P4 Wait: 0 |

| P2 Wait: 3 |

| P1 Wait: 8 |

| P3 Wait: 16 |

| Average Waiting Time: 6.75 |

----------------------------------

Round Robin (RR)

RR is one of the oldest, best and fairest algorithms. Firstly for every process a time range (time quantum,) is determined. Secondly if the process still didn’t finish its bust time but time quantum is full, then it is postponed and is sent to the end of waiting queue. Then other process, waiting at the top of the queue, enters into processor. During process switching an amount of time is spent. An optimum must be determined in order to have a smallest switch time. Otherwise RR technique may become worse then SJF.

This algorithm also contains a prediction for next process’ operation time. This can be formulated as:

Here is the sample execution output for RR.

α = 1, n = 4, t_q = 5

α = 0.2, n = 4, t_q = 5

C Source Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct {
    int p_no;
    short burst;
    short wait;
    short r_times; // number of CPU processes
} p_b;

//  Initially L = 0, R = n-1
void QuickSort(p_b a[], long L, long R)
{

    long j, i, x;
    p_b k;

    i = L;
    j = R;
    x = a[(L+R) / 2].burst;
    do
    {
      while (a[i].burst < x)
                 i++;
      while (a[j].burst > x)
                 j--;
      if (i <= j)
      {
         k = a[i];
         a[i] = a[j];
         a[j] = k;
         i++;
         j--;
      }
    }
    while (i < j);
    if (L < j)
                QuickSort(a,L,j);
    if (i < R)
                QuickSort(a,i,R);
}

int FCFS(p_b Prc[], char n)
{
   int i, t;
   float awt;
   printf("----------------------------------\n");
   printf("|    First Come, First Served    |\n");
   printf("|--------------------------------|\n");
   t=0;
   for(i=0;i<n;i++)
   {
               printf("|  P. No: %3d Wait: %3d          |\n", Prc[i].p_no, t);
               Prc[i].wait = t;
               t += Prc[i].burst;
   }
   awt = 0.0;
   for(i=0;i<n;i++)
               awt += Prc[i].wait;
   printf("| Average Waiting Time: %4.2f    |\n", awt/(float)n);
   printf("----------------------------------\n");
   getch();

   return 0;
}

int SJF(p_b Prc[], char n)
{
    int i, t;
    float awt;

    QuickSort(Prc, 0, n-1);
    printf("----------------------------------\n");
    printf("|      Shortest Job First        |\n");
    printf("|--------------------------------|\n");
    t=0;
    for(i=0;i<n;i++)
    {
       printf("|  P. No: %3d Wait: %3d          |\n", Prc[i].p_no, t);
       Prc[i].wait = t;
       t += Prc[i].burst;
    }
    awt = 0.0;
    for(i=0;i<n;i++)
       awt += Prc[i].wait;
    printf("| Average Waiting Time: %3.2f     |\n", awt/(float)n);
    printf("----------------------------------\n");
    getch();

    return 0;
}

int RR(p_b Prc[], int tq,float a, char n)
{
    int i, t, p_count, before;
    float awt, Tn;

    printf("----------------------------------\n");
    printf("|           Round Robin          |\n");
    printf("|--------------------------------|\n");
    t=0;
    i = 0;
    p_count=0;
    before = -1;
    Tn=0.0; // total process time
    while(p_count != n)
    {
       if (Prc[i].burst > 0 )
       {
          printf("|  P%d  Rem. Burst:%3ld  Wait: %3d |", Prc[i].p_no, Prc[i].burst, t);
          printf("   T(n+1)= %2.2f\n", Tn);
          Tn = a*tq + (1-a)*Tn;
          if ( Prc[i].p_no != before)
          {
                      Prc[i].wait += t; // i. process total wait time
                      Prc[i].r_times++; // increment by one
          }
          if(Prc[i].burst >= (int)Tn)
          {
                      t += (int)Tn;
                      Prc[i].burst -= (int)Tn;
          }
          else
          {
                      t += Prc[i].burst;
                      Prc[i].burst = 0;
          }
          if (Prc[i].burst <= 0)  // process ended. max counter value is "n"
                      p_count++;
          before = Prc[i].p_no;
          i++;
       }
       else
       {
          i++;
       }
       if (i >= n)  // go back to starting point
       {
           printf("|********************************|\n");
           i = 0;
       }
    }
    awt = 0.0;
    for(i=0;i<n;i++)
    {
                if (Prc[i].r_times > 0)
                {
                           awt += (float)Prc[i].wait/(float)Prc[i].r_times;
                }
                else
                           awt += (float)Prc[i].wait;
    }
    printf("| Average Waiting Time: %3.2f    |\n", awt/(float)n);
    printf("----------------------------------\n");
    return 0;
}

int main(void)
{

    p_b Prc[50];
    int i, n, tq;
    float a;

    printf("How many processes: ");scanf("%d",&n);
    for(i=0;i<n;i++)
    {
                Prc[i].p_no = i;
                Prc[i].r_times = 0;
                Prc[i].wait = 0;
                printf("%d. Process Birst Time:", i);
                scanf("%d", &Prc[i].p_no);
    }
    printf("Time quantum:");scanf("%d",&tq);
    printf("Previus process weight:");scanf("%f",&a);

    FCFS(Prc, n);
    SJF(Prc, n);
    RR(Prc, tq, a, n);

    return 0;
}

References

[1] Silberschatz, Galvin and Gagne, Operating System Concepts, John Wiley and Sons Inc., Chapter 6, Page 157, 2002.

[2] Tanenbaum, Andrew S., Modern Operating Systems, Second Edition, Prentice Hall, Chapter2, page 139, 2002.