任务到达后可能先排队,再由执行器处理。只看结束减到达的总时间,会把等待与实际工作混在一起,难以判断卡顿来自队列积压还是单项任务本身。
固定规则与输入
只有一个执行器,按到达时间排序,同一时刻到达时按编号排序。任务不中断,执行器空闲就立即取队头。每项有到达时刻和正整数处理时长。
到达时刻[4, 5, 7, 11, 14, 18, 18, 21, 23, 27, 30, 34] 处理时长[3, 1, 3, 2, 1, 3, 1, 2, 5, 6, 6, 4]
逐步观察结果
任务0在4到达,处理需3,从4开始到7结束;等待0,周转3,其中周转等于等待加处理。
任务1在5到达,处理需1,从7开始到8结束;等待2,周转3,其中周转等于等待加处理。
任务2在7到达,处理需3,从8开始到11结束;等待1,周转4,其中周转等于等待加处理。
任务3在11到达,处理需2,从11开始到13结束;等待0,周转2,其中周转等于等待加处理。
任务4在14到达,处理需1,从14开始到15结束;等待0,周转1,其中周转等于等待加处理。
任务5在18到达,处理需3,从18开始到21结束;等待0,周转3,其中周转等于等待加处理。
任务6在18到达,处理需1,从21开始到22结束;等待3,周转4,其中周转等于等待加处理。
任务7在21到达,处理需2,从22开始到24结束;等待1,周转3,其中周转等于等待加处理。
任务8在23到达,处理需5,从24开始到29结束;等待1,周转6,其中周转等于等待加处理。
任务9在27到达,处理需6,从29开始到35结束;等待2,周转8,其中周转等于等待加处理。
任务10在30到达,处理需6,从35开始到41结束;等待5,周转11,其中周转等于等待加处理。
任务11在34到达,处理需4,从41开始到45结束;等待7,周转11,其中周转等于等待加处理。
逐单位时刻的等待队列长度[0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],面积总和22,各任务等待总和22。忙碌时间共37,其余时间是执行器空闲,不应记成某项任务的处理耗时。
独立复核
开始时刻为到达时刻与上一项结束时刻的较大值。等待等于开始减到达,周转等于结束减到达。把每个时刻处于等待状态的任务数加起来,应等于全部任务等待时间之和。
复核时先保留本例输入,再自己写出中间状态。若结果不同,应从最早出现差异的位置检查,尤其留意边界是否包含、索引从哪里开始、取整何时发生,以及是否使用了尚未更新的旧状态。计算得到的结论仅适用于已经说明的规则,修改规则后需要重新验证。
适用范围
本例没有任务优先级、取消或多执行器。等待队列不包括当前正在处理的那一项,统计区间采用到达含、开始不含。改用其他口径后,面积关系也必须相应调整。
