最短剩余下一时间(STRN)调度
另一位用户发布了关于最短作业优先(SJF)的这问题。下面是一个例子：
接下来如何在最短的时间内解决这个问题？最短作业优先的先发制人版本。
据我所知，在完成之前所剩时间最少的过程被选中执行。但是，如果到达的新进程的突发时间与当前正在执行的进程的剩余完成时间完全相同，会发生什么情况？
在新进程到达的实例中，其突发时间与当前正在执行的进程相同(如本例所示)，那么当前执行的进程是否继续？
甘特图，显示我如何理解进程将被调度：
我的理解正确吗？提前谢谢你。
回答 2
Stack Overflow用户
发布于 2018-05-12 19:31:08
在该调度算法中，选择待完成时间最小的进程执行。由于当前正在执行的进程是定义中剩余时间最短的进程，而且该时间只应随着执行进度的增加而减少，因此进程将始终运行，直到它们完成或添加了一个需要较小时间的新进程。 最短的剩余时间是有利的，因为短的过程处理非常快。系统也只需要很少的开销，因为它只在进程完成或添加新进程时做出决定，而在添加新进程时，算法只需要将当前正在执行的进程与新进程进行比较，而忽略了当前等待执行的所有其他进程。//强调我的。
如果到达的新进程的突发时间与当前正在执行的进程的剩余完成时间完全相同，那么CPU将继续执行当前进程。之所以作出这一决定，是因为进程上下文切换比较重。，以及在剩余相同突发时间的情况下，当前正在执行的进程将继续执行，直到完成，或者一个新的短进程到达。
是的，你的甘特图是正确的。
但是，也请从维基百科上读到这些限制：
与最短作业下一次调度一样，最短剩余时间调度很少在特定环境之外使用，因为它需要准确估计每个进程的运行时。
Stack Overflow用户
发布于 2022-01-27 15:31:41
在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]}下面的动画展示了使用上述实现获得的抢占式调度算法的甘特图：
让我们考虑以下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与上表对应的甘特图显示在以下动画中，使用上述算法获得：
https://stackoverflow.com/questions/50305423
复制相似问题
腾讯云开发者
