python - 下一个剩余最短时间 (STRN) 调度

Question

另一位用户在最短作业优先 (SJF) 上发布了此问题。这是示例：

接下来如何解决最短剩余时间？Shortest Job First 的抢先版。

我了解选择执行剩余时间最少的过程。但是，如果一个新进程到达，其突发时间与当前执行进程的剩余完成时间完全相同，会发生什么？

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

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

我的理解正确吗？先感谢您。

Answer 1

引用维基百科的最短剩余时间：

在这种调度算法中，选择执行剩余时间最少的进程。由于根据定义，当前执行的进程是剩余时间最短的进程，并且由于该时间只会随着执行的进行而减少，因此进程将始终运行直到它们完成或添加需要更短时间的新进程。

最短的剩余时间是有利的，因为短的过程处理得非常快。该系统还需要很少的开销，因为它只在进程完成或添加新进程时做出决定，而当添加新进程时，算法只需将当前正在执行的进程与新进程进行比较，而忽略所有其他进程目前正在等待执行。//强调我的。

如果一个新进程到达，其突发时间与当前正在执行的进程的剩余完成时间完全相同，那么 CPU 将继续执行当前进程。做出这个决定是因为进程上下文切换更重，因此在剩余突发时间相等的情况下，当前正在执行的进程将继续执行直到完成，或者新的短进程到达。

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

但是，请也阅读这些限制 // 来自 Wikipedia：

与最短作业下一次调度一样，最短剩余时间调度很少在专业环境之外使用，因为它需要准确估计每个进程的运行时间。

Answer 2

如果新进程的执行时间比当前进程短，则在 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 调度算法的甘特图：

让我们考虑下面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

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