分组公平排队实现及时间戳老化问题解决方案
在分组公平排队的实际应用中,存在多种实现方式和挑战,下面将详细介绍相关内容。
基于 D 的分组公平排队实现
在分组公平排队的实现里,相较于传统使用 F 的方法,使用 D 是更优选择。S 依旧存在 0 和 1 两个区域,D 为 0 的行属于虚拟行。该方法的优势在于,由于 D 不存在溢出问题,所以仅需考虑 S 的溢出情况。并且,无需进行掩码操作,因为每列中的 V 位可由 D 明确排序。
不过每个内存库对于 F 仍可划分为两个区域:
- 溢出区域:$F = S + D \geq M$
- 非溢出区域:$F < M$
Z 和 CZ 各需要 1 位。其代价是,需要额外的加法器或加法操作从 $F = S + D$ 恢复 F 的值。同时,调度器要处理那些被读出且 F 溢出的合格分组。实际上,F 溢出的处理从整形器队列的二维 RSE 转移到了调度器队列的 RSE。
时间戳老化问题及影响
当会话 i 的一个分组离开时,其完成时间 $F_i$ 会被存储在查找表(即完成时间队列)中,以便后续根据特定规则使用。会话 i 的其他信息,像 S 和 $r_i$ 等,也能存储在由 i 寻址的同一位置。当该会话的新分组到达队列头部并成为 HOL 分组时,需要读出 $F_i$ 并与当前系统虚拟时间比较,从而确定新的 $S_i$。
然而,由于系统虚拟时间在实现中用有限位表示,它会像时间戳一样溢出。在没有历史记录或特定约束的情况下,尤其是队列空闲一段时间后,很难判断系统虚拟时间和时间戳哪个更大,这就是时间戳的老化问题。当系统虚拟时间超过 $F_i$ 时,$F_i$ 就会