Shortest Time Remaining Next (STRN) Scheduling

Question

Another user posted this question on Shortest Job First (SJF). Here's the example:

How would this be solved for Shortest Remaining Time Next? The preemptive version of Shortest Job First.

I understand that the process with smallest amount of time remaining until completion is selected to execute. However, what happens if a new process arrives that has a burst time that is exactly the same as the remaining completion time of the currently executing process?

In the instance that a new process arrives that has a burst time that is the same as the current executing process (as evident in this example), then does the process currently executing continue?

Gantt chart showing how I understand the processes would be scheduled:

Am I correct in my understanding? Thank you in advance.

Sandipan Dey · Answer 1 · 2022-01-28T19:32:38.573

A process running on CPU is preempted by a new process iff the latter one has smaller execution time than the current one. We can implement the algorithm for preemptive shortest remaining time next scheduling using the following python function and simulate the execution of the processes on CPU:

import pandas as pd

def SRTN(df): # df is the data frame with arrival / burst time of processes

    queue = []
    cpu, cur_pdf = None, None
    alloc, dalloc = {}, {}

    time = 0

    while True: # simulate the CPU scheduling algorithm

        # check if all processes finished execution
        if df['RemainingTime'].max() == 0:
            break

        # get current process assigned to cpu, if any
        if cpu:
            cur_pdf =  df[df.Process == cpu]    

        # check if a process arrived at this time instance and put it into wait queue
        pdf = df[df.ArrivalTime == time]

        if len(pdf) > 0:
            for p in pdf['Process'].values:
                queue.append(p)

        if len(queue) > 0:
            pdf = df[df['Process'].isin(queue)]

            # find the process with shortest remaining time
            if len(pdf) > 0:
                pdf = pdf[pdf['RemainingTime']==pdf['RemainingTime'].min()]

            # allocate a process to CPU, pre-empt the running one if required
            if (cpu is None) or (len(pdf) > 0 and pdf['RemainingTime'].values[0] < cur_pdf['RemainingTime'].values[0]):
                if cpu:
                    # prempt the current process
                    dalloc[cpu] = dalloc.get(cpu, []) + [time]
                    queue.append(cpu)
                    print('Process {} deallocated from CPU at time {}'.format(cpu, time))
                cur_pdf = pdf
                cpu = cur_pdf['Process'].values[0]
                queue.remove(cpu)
                print('Process {} allocated to CPU at time {}'.format(cpu, time))
                alloc[cpu] = alloc.get(cpu, []) + [time]

        df.loc[df['Process']==cpu,'RemainingTime'] -= 1

        time += 1 # increment timer

        # deallocate process
        if df[df['Process']==cpu]['RemainingTime'].values[0] == 0:
            print('Process {} deallocated from CPU at time {}'.format(cpu, time))
            dalloc[cpu] = dalloc.get(cpu, []) + [time]
            cpu = cur_pdf = None
            
    return alloc, dalloc

Now, run SRTN on the following data (process arrival / burst times):

df = pd.DataFrame({'Process':['A','B','C','D'], 'BurstTime':[3,5,3,2], 'ArrivalTime':[0,2,5,6]})
df.sort_values('ArrivalTime', inplace=True)
df['RemainingTime'] = df.BurstTime

df

alloc, dalloc = SRTN(df)
# Process A allocated to CPU at time 0
# Process A deallocated from CPU at time 3
# Process B allocated to CPU at time 3
# Process B deallocated from CPU at time 8
# Process D allocated to CPU at time 8
# Process D deallocated from CPU at time 10
# Process C allocated to CPU at time 10
# Process C deallocated from CPU at time 13
 
# alloc
# {'A': [0], 'B': [3], 'D': [8], 'C': [10]}
# dalloc
# {'A': [3], 'B': [8], 'D': [10], 'C': [13]}

The following animation shows how the Gantt chart for the preemptive SRTN scheduling algorithm, obtained using the above implementation:

Let's consider the following input table for the arrival of the following 3 processes and run SRTN on the data frame to obtain the corresponding Gantt chart:

alloc, dalloc, events = SRTN(df)
# Process A allocated to CPU at time 0
# Process A deallocated from CPU at time 1
# Process B allocated to CPU at time 1
# Process B deallocated from CPU at time 5
# Process A allocated to CPU at time 5
# Process A deallocated from CPU at time 11
# Process C allocated to CPU at time 11
# Process C deallocated from CPU at time 19

The Gantt chart corresponding to the above table is shown in the following animation, obtained using the above algorithm:

score 1 · Accepted Answer · answered May 12 '18 at 19:31

Quoting from Wikipedia's Shortest remaining time:

In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute. Since the currently executing process is the one with the shortest amount of time remaining by definition, and since that time should only reduce as execution progresses, processes will always run until they complete or a new process is added that requires a smaller amount of time.

Shortest remaining time is advantageous because short processes are handled very quickly. The system also requires very little overhead since it only makes a decision when a process completes or a new process is added, and when a new process is added the algorithm only needs to compare the currently executing process with the new process, ignoring all other processes currently waiting to execute. // emphasis mine.

If a new process arrives that has a burst time that is exactly the same as the remaining completion time of the currently executing process, then the CPU will keep executing the current process. This decision is taken because process context switch is heavier, and hence in cases of equal burst time left, the process which is currently executing would continue to execute until finished, or a new short process arrives.

And, YES, your Gantt Chart is correctly drawn.

But, please read about the limitations too // from Wikipedia:

Like shortest job next scheduling, shortest remaining time scheduling is rarely used outside of specialized environments because it requires accurate estimates of the runtime of each process.

Shortest Time Remaining Next (STRN) Scheduling

2 Answers2