最短剩余时间 (STRN) 调度

Question

另一位用户发布了 this question on Shortest Job First (SJF). Here's the example:

下一个最短剩余时间如何解决？ Shortest Job First 的抢占式版本。

我了解选择执行距离完成剩余时间最少的进程。但是，如果新进程的突发时间与当前正在执行的进程的剩余完成时间完全相同，会发生什么情况？

在新进程到达的实例中，其突发时间与当前正在执行的进程相同（如本例所示），那么当前正在执行的进程是否继续？

甘特图显示了我如何理解流程的安排：

我的理解正确吗？提前谢谢你。

Answer 1

引用自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.

如果新进程到达，其突发时间与当前正在执行的进程的剩余完成时间完全相同，则CPU将继续执行当前进程。做出此决定是因为process context switch is heavier，因此在剩余突发时间相等的情况下，当前正在执行的进程将继续执行直到完成，或者一个新的短进程到达。

是的，您的甘特图已正确绘制。

但是，请也阅读维基百科的限制 //：

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.

Answer 2

进程运行ning on CPU 被一个新进程抢占，前提是后一个进程的执行时间比当前进程短。我们可以使用下面的python函数实现抢占式最短剩余时间下一次调度的算法，模拟进程在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

现在，运行 SRTN 对以下数据（处理到达/突发时间）：

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]}

下面的动画展示了甘特图抢占式SRTN调度算法是如何使用上面的实现得到的：

我们考虑下面的输入table对于下面3个进程的到达和运行数据框上的SRTN得到对应的甘特图：

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

上面table对应的甘特图如下动画所示，使用上面的算法得到：

最短剩余时间 (STRN) 调度

Shortest Time Remaining Next (STRN) Scheduling

python

algorithm

operating-system

scheduling

job-scheduling