实现优先级队列
模型常常需要实现优先级排队系统,即不同类型的数据包在等待转发给其他模块时享有优先于其他数据包的待遇。在某些情况下,数据包可以被划分到一组离散的优先级级别。例如,某个系统可能只支持 high 和 low 两种优先级。在另一些情况下,则需要连续的优先级范围。例如,某个系统对排队中的数据包,存在时间越长就给予越高的优先级。
无论哪种情况,优先级机制都会在队列中为数据包建立一种次序。连续的优先级范围模型用于子队列内部,因为离散的优先级分类可以看作连续系统的一种特例。不过,队列内部的子队列集合也可以用作表示离散优先级的机制:为每个优先级级别创建一个子队列,并根据数据包的优先级把它们插入正确的子队列。当从队列中取出数据包时,按优先级次序扫描各个子队列,直到找到非空的子队列;这保证了可用的最高优先级数据包总是最先被取出。下面的代码片段演示了这一技术。
图 175:利用子队列实现离散优先级
/* Insert an arriving packet into the appropriate subqueue. */
/* The "get_prio()" function returns the priority, which */
/* may be derived from a packet field, or from the packet's */
/* "priority" attribute, and is an integer between 0 and */
/* NUM_PRIOS - 1, where NUM_PRIOS is the number of priority */
/* levels (and also of subqueues). 0 is the highest priority. */
prio = get_prio (pk_ptr);
op_subq_pk_insert (prio, pk_ptr, OPC_QPOS_TAIL);
/* Extract the packet with the highest priority, that is, */
/* the packet at the head of the lowest-numbered subqueue */
/* that contains packets. As before, NUM_PRIOS is the */
/* number of priority levels and subqueues. */
pk_ptr = OPC_NIL;
for (i = 0; i < NUM_PRIOS; i++)
{
if (op_subq_empty (i) == OPC_FALSE)
{
pk_ptr = op_subq_pk_remove (i, OPC_QPOS_HEAD);
break;
}
}
if (pk_ptr != OPC_NIL)
op_pk_send (pk_ptr, OUT_STRM);
在单个子队列内部,抽象数据包位置索引常量 OPC_QPOS_PRIO 提供了一种便捷的方式,在插入或取出数据包时遵循优先级次序。为此,数据包的优先级由其 “priority” 属性指定,该属性可用内核过程 op_pk_priority_set() 设置。如果把 OPC_QPOS_PRIO 常量作为数据包位置传给内核过程 op_subq_pk_insert(),则目标数据包会被插在所有优先级较低的数据包之前、所有优先级较高或相同的数据包之后。类似地,如果把这个常量传给 op_subq_pk_access() 或 op_subq_pk_remove(),这些内核过程将作用于该子队列中优先级最高的数据包。更多信息见第 21 章“Subqueue Package”第 1 页。
Modeler 的标准模型库中包含一个简单的优先级排队进程模型 pc_prio(passive concentrating priority queue,被动集中式优先级队列)。该进程模型只操作一个子队列,利用数据包的 “priority” 属性为其排序。许多优先级排队应用可以直接使用它的默认形式,也可以按需修改;它同时也是一个优先级队列实现的基本示例。