01先把问题说具体
任务都有到达时间和运行时长。短任务尚未到达时,处理器该空等还是先处理已有任务?
02一步步得到方法
先定义指标再比较策略
完成时间 C,到达时间 A,运行时长 B。周转时间 C−A,等待时间 C−A−B;首次运行时间减 A 是响应时间。非抢占任务只有一次连续运行,所以响应等于等待;抢占后通常不同。
所有任务在零时刻到达时,最短处理时间优先能最小化总等待。不同到达时间下,非抢占地从当前就绪任务挑最短只是一个明确策略,不能无条件保证全局最优;是否允许故意空闲会改变问题。
把未来任务与就绪任务分开
按到达时间排序输入,用指针加入所有到达≤当前时间的任务;就绪堆按运行时长选最短。若堆为空,直接把时间跳到下一任务到达时刻,不必逐个时钟空转。
本课演示非抢占 SJF,不中断已开始任务。可抢占的最短剩余时间策略需要在新到达事件时重新比较剩余量,不能只改堆排序字段就完成。
优化指标决定是否能使用交换论证
所有任务同时可用时,交换相邻长短任务不会改变它们后面任务的开始时间,却能减少两项内部等待总和,因此短任务优先有明确证明。
若任务有释放时间、截止时间或不同权重,交换可能改变可行性和代价。先列出限制,再决定是否使用最短时长、最早截止或其他规则,不能把所有调度统一成一次按长度排序。
03把一个小例子完全算清楚
A:(到达0,时长5),B:(1,1),C:(1,2)。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| t=0 | 只有 A 就绪,执行到 5 | 非抢占,B 到来也不中断 |
| t=5 | 选择 B,完成于 6 | 等待 5−1=4 |
| t=6 | 选择 C,完成于 8 | 等待 6−1=5 |
窄屏可左右滑动表格,阅读完整计算与理由。
等待分别为 0、4、5。这个结果描述该策略,不声称对允许主动空闲的模型全局最优。
04为什么这个方法成立
- 任务仅在到达后入就绪堆,不会提前执行。
- 每次取就绪任务中最短者,精确实现所声明的非抢占 SJF。
- 时间推进到完成或下一到达事件,覆盖全部任务且不会遗漏空闲段。
05把推导翻译成代码
Python · 可独立运行的教学实现
import heapq
def sjf_schedule(tasks):
pending = sorted((arrival,duration,i) for i,(arrival,duration) in enumerate(tasks))
heap, result, time, index = [],[],0,0
while index < len(pending) or heap:
if not heap and index < len(pending):
time = max(time,pending[index][0])
while index < len(pending) and pending[index][0] <= time:
arrival,duration,i = pending[index]
assert duration > 0
heapq.heappush(heap,(duration,arrival,i)); index += 1
duration,arrival,i = heapq.heappop(heap)
start = time; time += duration
result.append((i,start,time,start-arrival))
return result逐个理解关键决定
time = max(time,pending[index][0])- 仅在就绪队列空时跳时间,不让时钟倒退。
(duration,arrival,i)- 先按时长,平局再按到达与编号,得到确定性结果。
06时间、空间与实现范围
排序与 n 次堆操作总 O(n log n),空间 O(n)。
策略最优性依赖到达、抢占、权重与是否可空闲;本模拟的正确性是符合规则,不等于证明调度全局最优。
07改变条件,检查哪里会出错
将周转时间直接当等待时间
周转还包含自身运行时长,要减去 B。
未知任务时长却当作精确输入
实际系统可能只能预测运行时长,预测误差应与理想离线模型区分。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
本例 A 的周转和等待是多少?
需要一点提示
C−A 与 C−A−B。
查看解析与答案
周转 5,等待 0。
只有任务在 t=100 到达,会循环 100 次吗?
需要一点提示
采用事件推进。
查看解析与答案
不会,直接把时间跳到 100。
如何改成最短剩余时间抢占?
需要一点提示
新任务到来可能改变当前最短者。
查看解析与答案
运行到下一到达或当前完成事件,更新剩余时长并重新选任务,记录首次开始和完成时间。