下一个(STRN)计划剩余的最短时间

Question

接下来的最短剩余时间如何解决这个问题？“最短作业优先”的抢占式版本。

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

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

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

Answer 1

在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

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

Answer 2

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

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

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

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

是的，你的甘特图画得很正确。

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

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