专题进阶 · 贪心策略推荐总顺序 · 第 82 / 148 课

分清等待、周转与响应时间,依据到达条件选择调度模型。

先学会这些,再进入本课 贪心思想 优先队列
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 贪心策略

调度问题Scheduling

任务顺序与目标函数决定策略,最小等待和最大收益未必能用同一排序规则。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

分清等待、周转与响应时间,依据到达条件选择调度模型。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 任务仅在到达后入就绪堆,不会提前执行。
  2. 每次取就绪任务中最短者,精确实现所声明的非抢占 SJF。
  3. 时间推进到完成或下一到达事件,覆盖全部任务且不会遗漏空闲段。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

本例 A 的周转和等待是多少?

需要一点提示

C−A 与 C−A−B。

查看解析与答案

周转 5,等待 0。

练习 2 · 边界与辨析

只有任务在 t=100 到达,会循环 100 次吗?

需要一点提示

采用事件推进。

查看解析与答案

不会,直接把时间跳到 100。

练习 3 · 变式与迁移

如何改成最短剩余时间抢占?

需要一点提示

新任务到来可能改变当前最短者。

查看解析与答案

运行到下一到达或当前完成事件,更新剩余时长并重新选任务,记录首次开始和完成时间。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。