Question

Implement 3 scheduling algorithms, FIFO, SJF, SRT based on following actions:

The simulation maintains the current time, t, which is initialized to 0 and is incremented after each simulation step. Each simulation step then consists of the following actions:

repeat until Rᵢ == 0 for all n processes /* repeat until all processes have terminated */
while no process is active, increment t /* if no process is ready to run, just advance t */
choose active processes pᵢ to run next
according to scheduling algorithm /* Ex: FIFO, SJF, SRT */
decrement Rᵢ /* pᵢ has accumulated 1 CPU time unit */
if Rᵢ == 0 /* process i has terminated */
set active flag of pᵢ = 0 /* process i is excluded from further consideration */
TTᵢ = t - Aᵢ /* the turnaround time of process i is the time
since arrival, TTᵢ, until the current time t */
compute the average turnaround time,
ATT, by averaging all values TTᵢ

Answer 1

FIFO:

First Come, First Served (FCFS) also known as First In, First Out(FIFO) is the CPU scheduling algorithm in which the CPU is allocated to the processes in the order they are queued in the ready queue.

FCFS follows non-preemptive scheduling which mean once the CPU is allocated to a process it does not leave the CPU until the process will not get terminated or may get halted due to some I/O interrupt.

Example

Let’s say, there are four processes arriving in the sequence as P2, P3, P1 with their corresponding execution time as shown in the table below. Also, taking their arrival time to be 0.

Process	Order of arrival	Execution time in msec
P1	3	15
P2	1	3
P3	2	3

Gantt chart showing the waiting time of processes P1, P2 and P3 in the system

As shown above,

The waiting time of process P2 is 0

The waiting time of process P3 is 3

The waiting time of process P1 is 6

Average time = (0 + 3 + 6) / 3 = 3 msec.

As we have taken arrival time to be 0 therefore turn around time and completion time will be same.

Example

Input-:  processes = P1, P2, P3
        Burst time = 5, 8, 12
Output-:
Processes  Burst    Waiting    Turn around
1          5        0           5
2          8        5           13
3          12       13          25
Average Waiting time = 6.000000
Average turn around time = 14.333333

Algorithm

Start                                                                    
   Step 1-> In function int waitingtime(int proc[], int n, int burst_time[], int wait_time[])
   Set wait_time[0] = 0
   Loop For i = 1 and i < n and i++
      Set wait_time[i] = burst_time[i-1] + wait_time[i-1]
   End For
Step 2-> In function int turnaroundtime( int proc[], int n, int burst_time[], int wait_time[], int tat[])
   Loop For  i = 0 and i < n and i++
      Set tat[i] = burst_time[i] + wait_time[i]
   End For
Step 3-> In function int avgtime( int proc[], int n, int burst_time[])
   Declare and initialize wait_time[n], tat[n], total_wt = 0, total_tat = 0;
   Call waitingtime(proc, n, burst_time, wait_time)
   Call turnaroundtime(proc, n, burst_time, wait_time, tat)
   Loop For  i=0 and i<n and i++
      Set total_wt = total_wt + wait_time[i]
      Set total_tat = total_tat + tat[i]
      Print process number, burstime wait time and turnaround time
   End For
   Print "Average waiting time =i.e. total_wt / n
   Print "Average turn around time = i.e. total_tat / n
Step 4-> In int main()
   Declare the input int proc[] = { 1, 2, 3}
   Declare and initialize n = sizeof proc / sizeof proc[0]
   Declare and initialize burst_time[] = {10, 5, 8}
   Call avgtime(proc, n, burst_time)
Stop

shortest job first scheduling

Shortest job first scheduling is the job or process scheduling algorithm that follows the nonpreemptive scheduling discipline. In this, scheduler selects the process from the waiting queue with the least completion time and allocate the CPU to that job or process. Shortest Job First is more desirable than FIFO algorithm because SJF is more optimal as it reduces average wait time which will increase the throughput.

SJF algorithm can be preemptive as well as non-preemptive. Preemptive scheduling is also known as shortest-remaining-time-first scheduling. In Preemptive approach, the new process arises when there is already executing process. If the burst of newly arriving process is lesser than the burst time of executing process than scheduler will preempt the execution of the process with lesser burst time.

What is the Turnaround time, waiting time and completion time?

• Completion Time is the time required by the process to complete its execution

• Turnaround Time is the time interval between the submission of a process and its completion.

  Turnaround Time = completion of a process – submission of a process

• Waiting Time is the difference between turnaround time and burst time

  Waiting Time = turnaround time – burst time

Example

We are given with the processes P1, P2, P3, P4 and P5 having their corresponding burst time given below

Process	Burst Time	Arrival Time
P1	4	0
P2	2	1
P3	8	2
P4	1	3
P5	9	4

Since the arrival time of P1 is 0 it will be the first one to get executed till the arrival of another process. When at 1 the process P2 enters and the burst time of P2 is less than the burst time of P1 therefore scheduler will dispatch the CPU with the process P2 and so on.

Average waiting time is calculated on the basis of gantt chart. P1 have to wait for (0+4)4, P2 have to wait for 1, P3 have to wait for 7, P4 have to wait for 3 and P5 have to wait for 15. So, their average waiting time will be −

Algorithm:

Algorithm
Start
Step 1-> Declare a struct Process
   Declare pid, bt, art
Step 2-> In function findTurnAroundTime(Process proc[], int n, int wt[], int tat[])
   Loop For i = 0 and i < n and i++
      Set tat[i] = proc[i].bt + wt[i]
Step 3-> In function findWaitingTime(Process proc[], int n, int wt[])
   Declare rt[n]
   Loop For i = 0 and i < n and i++
      Set rt[i] = proc[i].bt
      Set complete = 0, t = 0, minm = INT_MAX
      Set shortest = 0, finish_time
      Set bool check = false
      Loop While (complete != n)
         Loop For j = 0 and j < n and j++
            If (proc[j].art <= t) && (rt[j] < minm) && rt[j] > 0 then,
               Set minm = rt[j]
               Set shortest = j
               Set check = true
            If check == false then,
               Increment t by 1
               Continue
               Decrement the value of rt[shortest] by 1
               Set minm = rt[shortest]
            If minm == 0 then,
               Set minm = INT_MAX
               If rt[shortest] == 0 then,
               Increment complete by 1
               Set check = false
               Set finish_time = t + 1
               Set wt[shortest] = finish_time - proc[shortest].bt -proc[shortest].art
            If wt[shortest] < 0
               Set wt[shortest] = 0
               Increment t by 1
Step 4-> In function findavgTime(Process proc[], int n)
   Declare and set wt[n], tat[n], total_wt = 0, total_tat = 0
   Call findWaitingTime(proc, n, wt)
   Call findTurnAroundTime(proc, n, wt, tat)
   Loop For i = 0 and i < n and i++
      Set total_wt = total_wt + wt[i]
      Set total_tat = total_tat + tat[i]
      Print proc[i].pid, proc[i].bt, wt[i], tat[i]
      Print Average waiting time i.e., total_wt / n
      Print Average turn around time i.e., total_tat / n
Step 5-> In function int main()
   Declare and set Process proc[] = { { 1, 5, 1 }, { 2, 3, 1 }, { 3, 6, 2 }, { 4, 5, 3 } }
   Set n = sizeof(proc) / sizeof(proc[0])
   Call findavgTime(proc, n)
Stop

SRT

SRTF, Which Stands for Shortest Remaining Time First is a scheduling algorithm used in Operating Systems, which can also be called as the preemptive version of the SJF scheduling algorithm. The process which has the least processing time remaining is executed first. As it is a preemptive type of schedule, it is claimed to be better than SJF scheduling Algorithm.

Let's understand this with the help of an example. Suppose we have the following 3 processes with process ID's P1, P2, and P3 and they arrive into the CPU in the following manner:

Gant Chart:

Explanation:

• At the 0^th unit of the CPU, we have only process P1, so it gets executed for the 1-time unit.
• At the 1^st unit of the CPU, the Process P2 also arrives. Now, the P1 needs 7 more units more to be executed, and P2 needs only 2 units. So, P2 is executed by preempting P1.
• P2 gets completed at time unit 3, and unit now no new process has arrived. So, after the completion of P2, again P1 is sent for execution.
• Now, P1 has been executed for one unit only, and we have an arrival of new process P3 at time unit 4. Now, the P1 needs 6-time units more and P3 needs only 3-time units. So, P3 is executed by preempting P1.
• P1 gets completed at time unit 7, and after that, we have the arrival of no other process. So again, P1 is sent for execution, and it gets completed at 13^th unit.

Algorithm steps with example:

    Total Turn Around Time = 13 + 2 + 3
                = 18 milliseconds
    Average Turn Around Time= Total Turn Around Time / Total No. of Processes
                = 18 / 3
                = 6 milliseconds

    Total Waiting Time = 5 + 0 + 0
                = 5 milliseconds
    Average Waiting Time = Total Waiting Time / Total No. of Processes
                = 5 / 3
                = 1.67 milliseconds