19、分组公平排队实现及时间戳老化问题解决方案

分组公平排队实现及时间戳老化问题解决方案

在分组公平排队的实际应用中，存在多种实现方式和挑战，下面将详细介绍相关内容。

基于 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$ 就会