FOR FREE MATERIALS

Shortest Remaining Time First (SRTF) (Preemptive SJF) 

SRTF process and examples:

The shortest remaining time First (SRTF) algorithm is preemptive version of SJF. In this algorithm, the scheduler always chooses the processes that have the shortest expected remaining processing time. When a new process joins the ready queue it may in fact have a shorter remaining time than the currently running process. Accordingly, the scheduler may preempt the current process when a new process (with a shorter burst time) becomes ready.

This feature helps to improve the turnaround times and weighted turnarounds of processes.

After every one unit of processing current process, scheduler can check any processes available at ready queue with shorter burst time.

Criteria: BT (Burst Time) + AT (Arrival Time)

Mode: Preemptive

Example: 

Gantt Chart

Process P1 is started at time 0, since it is the only process in the queue. Process P2 arrives at time 1. The remaining time for process P1 (7 milliseconds) is larger than the time required by process P2 (4 milliseconds), so process P1 is preempted, and process P2 is scheduled. 

TAT = CT - AT,  WT = TAT – BT 

And 

Response Time (RT) = FR (First Response) – AR (Arrival Time)

# In this algorithm there is no chance to occur convoy effect (no starvation). But long processes might face starvation. Like in the above example burst time of P3 is high as a result Response Time (RT) of P3 is pretty high (RT=15). 

# In general this algorithm is not used, because calculate burst time previously is not possible.  But if we can predict the burst time (See prediction method) in a better way, it can be used.

Example: (GATE 2011) 

Calculate average waiting time using Shorter Remaining Time First (SRTF).

Answer:

First, we design Gantt Chart according to SRTF policy.

Now we calculate Turn Around Time (TAT) and Waiting Time (WT) using the following formula:

TAT = CT – AT and WT = TAT – BT

Example: (GATE: 2007) 

Calculate the waiting time of process P2 using Shorter Remaining Time First (SRTF).

Answer: 

Gantt Chart as per SRTF.

Note: If the arrival time is long then don’t waste your time stopping after every unit. We can just stop at the next arrival time then check and carry on.

Now we calculate Turn Around Time (TAT) and Waiting Time (WT) using the following formula:

TAT = CT – AT and WT = TAT – BT.

Answer:  Waiting time of P2 is 15.