高优先级任务需要一个低优先级任务持有的资源时,只提高前者的优先级并不能让资源立即释放。中等优先级任务还可能反复抢占持有者,让高优先级任务等待更久。
规则与边界
本例单核逐时间单位执行。低优先级任务从零时刻开始持有锁,需要L单位完成后释放;高任务和中任务在h时刻同时到达,高任务也需要这把锁,中任务不需要。普通策略只按原优先级调度;继承策略让被高任务等待的锁持有者暂时使用高优先级。
本例记录
低任务持锁工作9,高与中到达时刻3,高任务工作7,中任务工作11。第t格代表区间[t,t+1)。
时间 | 普通调度 | 优先级继承 0 | 低 | 低 1 | 低 | 低 2 | 低 | 低 3 | 中 | 低 4 | 中 | 低 5 | 中 | 低 6 | 中 | 低 7 | 中 | 低 8 | 中 | 低 9 | 中 | 高 10 | 中 | 高 11 | 中 | 高 12 | 中 | 高 13 | 中 | 高 14 | 低 | 高 15 | 低 | 高 16 | 低 | 中 17 | 低 | 中 18 | 低 | 中 19 | 低 | 中 20 | 高 | 中 21 | 高 | 中 22 | 高 | 中 23 | 高 | 中 24 | 高 | 中 25 | 高 | 中 26 | 高 | 中 普通完成时间和高任务等待:{'中': 14, '低': 20, '高': 27} / 17 继承完成时间和高任务等待:{'低': 9, '高': 16, '中': 27} / 6表中编号只标记本例对象,不表示排名或另一组数据中的身份。先确认输入单位与边界约定,再逐步核对中间值。零、空结果和不存在是不同状态,不能因为显示相近就互相替代;分数用精确形式保留,便于重新演算。
复核方法
高任务发现锁不可用后进入等待,等待动作本身不消耗本例的执行时间。锁释放后高任务执行H单位,中任务执行M单位;三项任务总工作量不变。比较的是高任务何时完成,而不是凭空减少全部工作。
逐格检查时间线,确认同一时刻只有一个任务运行,未到达的任务不能提前执行。高任务等待期间低任务是否得到执行机会,是两种策略的关键差异。最后分别核对每个任务运行次数和锁释放时刻,不要只看总结束时间。
能说明什么
这是一个锁、三个任务的确定性演算,没有嵌套锁、多核、超时或抢占开销。优先级继承可缓解这种等待,但不能让正在持锁的任务跳过必要工作,也不是解决所有调度问题的通用保证。
这份记录用于理解明确规则下的游戏机制。改变输入后,结果也应随之重新计算;若操作规则不同,应先把新规则写清再比较。可以从一两个步骤手算开始,找出第一处差异,而不是只对照最后一个数值。全部中间记录都属于当前案例,不能直接当成其他场景的固定答案。
