Question

1. In the videos we show that Shortest Job First is the best algorithm with respect to average turn around time when there is no Input Output (I/O) burst. When there is I/O bust we have three variants:

1. Shortest remaining burst time first (SRBTF)
2. Shortest next burst time first (SNBTF)
3. Shortest total burst time first (STBTF)

Does SRBTF have the least average turnaround time? If Yes prove it in explanation, If no give an example schedule which is not SRBTF but has lower turnaround time.

Does SNBTF have the least average turnaround time? If Yes prove it in explanation, If no give an example schedule which is not SNBTF but has lower turnaround time.

Does STBTF have the least average turnaround time? If Yes prove it in explanation, If no give an example schedule which is not STBTF but has lower turnaround time.

Answer 1

SRBTF have the least Average turn around time compare to SNBTF, STBTF

SRBTF(Shortest Remaining Burst Time First) :

• In this algorithm, the process that has the shortest CPU burst time is selected first for the execution.
• When the CPU is available it is assign to the process that has the smallest next CPU burst.
• If two processes have the same length of CPU burst then FCFS policy is used to solve the tie.
• In fact more appropriate term for this algorithm would be the “Next Shortest CPU Burst Time First” because it allocates the CPU by examining the length of the next CPU burst of a process rather than its total length of a burst time.
• SJF algorithm may be either preemptive or non-preemptive.
• When a new process arrives having a short CPU burst time than the currently executing process; preemptive SJF algorithm will preempt the currently executing process, and allocates the CPU to the newly arrived process where as a non-preemptive SJF algorithm will allow the current running process to finish its CPU burst,

Example:

Consider the following processes and their CPU burst time (in millis.) and find out average waiting time and average turnaround time using preemptive SJF technique.

Process	Burst Time (ms.)	Arrival Time
P1	9	0
P2	4	1
P3	5	2
P4	7	3
P5	3	4
Total	28

• Notice that all processes arrives at different time period so we also need to consider their arrival time while finding shortest CPU burst from the available processes.

• So if we look to the arrival order of processes, P1 is the first process as its arrival time is zero. At zero millisecond we have only one process available in ready queue i.e. P1 so obviously process P1 will get the CPU first as we have no choice for comparison.
• After one millisecond a new process enter into the ready queue i.e process P2 with burst time of 4 milliseconds. The execution of currently running process P1 is completed of about one milliseconds when new process P2 arrives. so now we have total two processes into the ready queue for selection based on shortest CPU burst time.
• After one millisecond the burst time of process P1 is 8 (9-1 millis.) and process P2 with burst time 4. Since P2 has shortest CPU burst time, execution of currently running process P1 will be stopped by deallocating the CPU from P1 and P2 will be selected for execution by allocating the CPU to it.
• Similarly, at the time of two milliseconds, another new process P3 with burst time of 5 milliseconds arrives into the ready queue. Current execution of P2 is one milliseconds and remaining burst time is 3 milliseconds (4-1).
• Now we have total three processes into the ready queue so again their burst time will be compared and process having shortest burst time will be selected. In our case remaining burst time of process P1 is 8, P2 has 3 and P3 with 5 milliseconds respectively. Process P2 will continue to execute as it has the shortest burst time.
• In similar fashion, whenever a new process arrives, their burst time will be compared to find out process with the minimum burst time for selection.

Turnaround Time = Total Turnaround Time- Arrival Time 

P1 = 28 – 0 =28 ms,

P2 = 5 – 1 = 4,

P3 = 13 – 2 = 11,

P4 = 20 – 3 = 17,

P5 = 8 – 4 = 4

Total Turnaround Time= 64 mills.

Avg. Turnaround Time  = Total Turnaround Time / No.of Process
= 64 / 5

= 12.8 mills. 

The average turn around time for SNBTF is : 13.8 mills

The average turn around time for STBTF is : 14.2 mils