基于链表的队列调度方法与装置

摘要

本发明公开了一种基于链表的队列调度方法，包括：设置排队链表中的地址数不少于队列数，并按队列所属优先级将排队链表划分为不同的排队子链表，其中，排队子链表中的地址数不少于排队子链表所对应优先级下的所有队列数；为各队列设置标识其是否在排队链表中排队的排队链表标识符；在将符合排队条件的队列添入排队链表之前，根据队列的排队链表标识符判断队列是否已在排队链表中排队，若已排队则不作添入处理，若未排队则将队列添入队列优先级对应的排队子链表的链表尾部，并将队列的排队链表标识符修改为已在排队链表中排队的标识。本发明同时公开了一种基于链表的队列调度装置。本发明保证了同优先级队列调度时的公平性。

权利要求

1.一种基于链表的队列调度方法，其特征在于，包括：

设置排队链表中的地址数不少于队列数，并按队列所属优先级将所述排队链表划分为不同的排队子链表，其中，所述排队子链表中的地址数不少于所述排队子链表所对应优先级下的所有队列数；为各队列设置标识其是否在所述排队链表中排队的排队链表标识符；

以及

在将符合排队条件的队列添入所述排队链表之前，根据所述队列的排队链表标识符判断所述队列是否已在所述排队链表中排队，若已排队则不作添入处理，若未排队则将所述队列添入所述队列优先级对应的排队子链表的链表尾部，并将所述队列的排队链表标识符修改为已在所述排队链表中排队的标识。

2.根据权利要求1所述的方法，其特征在于，所述方法还包括：

在所述排队链表中选择优先级最高的非空排队子链表进行队列调度，优先级最高的非空排队子链表调度完毕后选择次优先级的非空排队子链表进行队列调度。

3.根据权利要求2所述的方法，其特征在于，排队子链表进行队列调度时，由链表的头部开始，按链表指针指示进行队列调度。

4.根据权利要求1所述的方法，其特征在于，所述方法还包括：优先级相同的已出队的队列与待入队的队列均符合排队条件时，优先将已出队的队列添入所述排队链表中。

5.根据权利要求1所述的方法，其特征在于，所述排队链表标识符为1比特，0标识已在所述排队链表中排队，1标识未在所述排队链表中排队；或者，0标识未在所述排队链表中排队，1标识已在所述排队链表中排队。

6.根据权利要求1所述的方法，其特征在于，每个队列号对应于排队链表中的一个地址。

7.一种基于链表的队列调度装置，其特征在于，包括：

设置单元，用于设置排队链表中的地址不少于总队列的数目，以及，为各队列设置标识其是否在所述排队链表中排队的排队链表标识符；

划分单元，用于按队列所属优先级将所述排队链表划分为不同的排队子链表，其中，所述排队子链表中的地址不少于所述排队子链表所对应优先级下的所有队列数；

判断单元，用于在将符合排队条件的队列添入所述排队链表之前，根据所述队列的排队链表标识符判断所述队列是否已在所述排队链表中排队，若已排队则不作添入处理，若未排队则触发添入单元；

添入单元，用于将所述队列添入所述队列优先级对应的排队子链表的链表尾部，并触发标识修改单元；以及标识修改单元，用于将所述队列的排队链表标识符修改为已在所述排队链表中排队的标识。

8.根据权利要求7所述的装置，其特征在于，所述装置还包括：

调度单元，用于在所述排队链表中选择优先级最高的排队子链表进行队列调度，优先级最高的排队子链表调度完毕后选择次优先级最高的排队子链表进行队列调度。

9.根据权利要求8所述的装置，其特征在于，所述调度单元排队子链表进行队列调度时，由链表的头部开始，按链表指针指示进行队列调度。

10.根据权利要求7所述的装置，其特征在于，所述添入单元在优先级相同的已出队的队列与入队的队列均符合排队条件时，优先将已出队的队列添入所述排队链表中。

11.根据权利要求7所述的装置，其特征在于，每个队列号对应于排队链表中的一个地址。

说明书

基于链表的队列调度方法与装置

技术领域

[0001] 本发明涉及队列调度技术，尤其涉及一种基于链表的多种调度技术混合的队列调度方法与装置。

背景技术

[0002] 队列调度，即队列通过某种触发检查(比如接收到授权触发等)，仲裁队列的出队条件，按照一定的规则调度队列有序的出队。常用的调度算法主要有轮询(RR，Round Robin)调度算法和严格优先级(SP，Strict Priority)调度算法。

[0003] 轮询调度算法的实现原理是按照一定的顺序逐个、循环轮询队列出队。在每个时钟周期调度一个队列出队，然后在下一个时钟周期轮询下一个队列调度出队。而严格优先级调度算法是给队列设定不同的优先级，每次调度最高优先级的队列出队，低优先级的队列只有在高优先级队列不满足出队条件后才能得到出队调度。

[0004] 目前，针对多优先级、多队列输出调度时，通常的处理方法是对相同优先级的队列用一个先入先出(FIFO，First Input First Output)队列进行缓存排队，然后在不同优先级排队FIFO间采用SP严格优先级调度输出。

[0005] 由于FIFO的原理是先进先得到服务，同一队列可以反复进入FIFO排队，在某一队列流量较大时，就会反复出现在FIFO中排队，这就会使得同一优先级中低流量的队列很长一段时间都得不到服务，只有等到高流量的队列反复出队很多次后才能轮到。这就体现不出对于同一优先级队列应该公平轮询出队的思想，造成了出队不公。另一个问题是当队列较多时，FIFO会出现溢出的风险，为避免出现这种现象，需要配置较大的FIFO队列，这将耗费相当巨大的RAM资源。出队队列数和队列优先级较多的情况如队列数为32K个，队列优先级为6个，为避免溢出现象的出现，出队排队就至少需要6个深度为32K的FIFO，这无疑耗费了大量的RAM资源，但上述所配置的RAM资源中的很大一部分并不能被使用，也造成了严重的资源浪费。

发明内容

[0006] 有鉴于此，本发明的主要目的在于提供一种基于链表的队列调度方法与装置，在保证严格优先级调度算法的同时，能保证同一优先级的队列被公平地调度。

[0007] 为达到上述目的，本发明的技术方案是这样实现的：

[0008] 一种基于链表的队列调度方法，包括：

[0009] 设置排队链表中的地址数不少于队列数，并按队列所属优先级将所述排队链表划分为不同的排队子链表，其中，所述排队子链表中的地址数不少于所述排队子链表所对应优先级下的所有队列数；为各队列设置标识其是否在所述排队链表中排队的排队链表标识符；以及

[0010] 在将符合排队条件的队列添入所述排队链表之前，根据所述队列的排队链表标识符判断所述队列是否已在所述排队链表中排队，若已排队则不作添入处理，若未排队则将所述队列添入所述队列优先级对应的排队子链表的链表尾部，并将所述队列的排队链表标识符修改为已在所述排队链表中排队的标识。

[0011] 优选地，所述方法还包括：

[0012] 在所述排队链表中选择优先级最高的非空排队子链表进行队列调度，优先级最高的非空排队子链表调度完毕后选择次优先级的非空排队子链表进行队列调度。

[0013] 优选地，排队子链表进行队列调度时，由链表的头部开始，按链表指针指示进行队列调度。

[0014] 优选地，所述方法还包括：优先级相同的已出队的队列与待入队的队列均符合排队条件时，优先将已出队的队列添入所述排队链表中。

[0015] 优选地，所述排队链表标识符为1比特，0标识已在所述排队链表中排队，1标识未在所述排队链表中排队；或者，0标识未在所述排队链表中排队，1标识已在所述排队链表中排队。

[0016] 优选地，每个队列号对应于排队链表中的一个地址。

[0017] 一种基于链表的队列调度装置，包括：

[0018] 设置单元，用于设置排队链表中的地址不少于总队列的数目，以及，为各队列设置标识其是否在所述排队链表中排队的排队链表标识符；

[0019] 划分单元，用于按队列所属优先级将所述排队链表划分为不同的排队子链表，其中，所述排队子链表中的地址不少于所述排队子链表所对应优先级下的所有队列数；

[0020] 判断单元，用于在将符合排队条件的队列添入所述排队链表之前，根据所述队列的排队链表标识符判断所述队列是否已在所述排队链表中排队，若已排队则不作添入处理，若未排队则触发添入单元；

[0021] 添入单元，用于将所述队列添入所述队列优先级对应的排队子链表的链表尾部，并触发标识修改单元；以及

[0022] 标识修改单元，用于将所述队列的排队链表标识符修改为已在所述排队链表中排队的标识。

[0023] 优选地，所述装置还包括：

[0024] 调度单元，用于在所述排队链表中选择优先级最高的排队子链表进行队列调度，优先级最高的排队子链表调度完毕后选择次优先级最高的排队子链表进行队列调度。

[0025] 优选地，所述调度单元排队子链表进行队列调度时，由链表的头部开始，按链表指针指示进行队列调度。

[0026] 优选地，所述添入单元在优先级相同的已出对的队列与入对的队列均符合排队条件时，优先将已出对的队列添入所述排队链表中。

[0027] 优选地，每个队列号对应于排队链表中的一个地址。

[0028] 本发明中，按队列数量设置排队链表的地址数，使排队链表的地址数不少于队列数量，再在排队链表中按队列的优先级设置不同的排队子链表，队列入对时，按队列优先级选择对应的排队子链表，在添入排队子链表之前，判断该队列是否已在排队子链表中排队，若排队则不再添入到排队子链表中，否则添入。调度时，在排队链表中选取优先级最高的非空排队子链表，从链表的头部开始，按链表指针指示进行队列调度，所选的非空排队子链表中的队列调度完毕后，选取次级优先级的非空排队子链表进行队列调度。本发明在处理同优先级队列时，按先入先出的方式进行调度，但对于已在排队链表中排队的队列而言，不可能再被添入到排队链表中，这样保证了同优先级队列调度时的公平性。

附图说明

[0029] 图1为本发明基于链表的队列调度方法的流程图；

[0030] 图2本发明队列添入排队子链表的结构示意图；

[0031] 图3为本发明基于链表的队列调度装置的组成结构示意图。

具体实施方式

[0032] 本发明的基本思想是：按队列数量设置排队链表的地址数，使排队链表的地址数不少于队列数量，再在排队链表中按队列的优先级设置不同的排队子链表，队列入对时，按队列优先级选择对应的排队子链表，在添入排队子链表之前，判断该队列是否已在排队子链表中排队，若排队则不再添入到排队子链表中，否则添入。调度时，在排队链表中选取优先级最高的非空排队子链表，从链表的头部开始，按链表指针指示进行队列调度，所选的非空排队子链表中的队列调度完毕后，选取次级优先级的非空排队子链表进行队列调度。本发明在处理同优先级队列时，按先入先出的方式进行调度，但对于已在排队链表中排队的队列而言，不可能再被添入到排队链表中，这样保证了同优先级队列调度时的公平性。

[0033] 为使本发明的目的、技术方案和优点更加清楚明白，以下举实施例并参照附图，对本发明进一步详细说明。

[0034] 图1为本发明基于链表的队列调度方法的流程图，如图1所示，本发明基于链表的队列调度方法包括以下步骤：

[0035] 步骤101：设置排队链表中的地址数不少于队列数，并按队列所属优先级将所述排队链表划分为不同的排队子链表，其中，所述排队子链表中的地址数不少于所述排队子链表所对应优先级下的所有队列数；为各队列设置标识其是否在所述排队链表中排队的排队链表标识符。

[0036] 根据系统中所有队列的数目设置排队链表的地址数，以前述背景技术中32K个队列为例，则设置排队链表的地址数至少为32K个，排队链表的地址需要至少15bit的字符来承载，即每个队列需有一个对应的排队链表的地址，以在将队列作添入处理时有存放该队列的地址。对于排队链表，再按队列优先级的不同设置为不同的排队子链表，以对相应优先级的队列进行排队时，将相应优先级的队列添入到对应优先级的排队子链表中，排队子链表中的地址数不能少于该优先级下的所有队列数，以将该优先级下的所有队列均能在相应的排队子链表中进行排队。本发明中，队列主要是指所属用户不同的数据队列。最好的方式是排队子链表中的地址数与所有队列一一对应。

[0037] 同时，为各队列设置标识其是否在所述排队链表中排队的排队链表标识符，该排队链表标识符为1比特的字符，其中，0标识已在所述排队链表中排队，1标识未在所述排队链表中排队；或者，0标识未在所述排队链表中排队，1标识已在所述排队链表中排队。本发明中，队列的排队链表标识符地址与队列的序号相对应，以方便查找队列对应的排队链表标识符。

[0038] 步骤102：在将符合排队条件的队列添入所述排队链表之前，根据所述队列的排队链表标识符判断所述队列是否已在所述排队链表中排队，若已排队则不作添入处理，若未排队则将所述队列添入所述队列优先级对应的排队子链表的链表尾部，并将所述队列的排队链表标识符修改为已在所述排队链表中排队的标识。

[0039] 设置完排队链表后，即判断哪些队列符合排队条件，对于符合排队条件的队列，将其添入到排队链表中，具体的，在添入排队链表之前，需要确定队列的优先级，然后，再查看该队列的排队链表标识符，确定该队列是否已在排队链表中排队，若已排队，则不再处理该队列，即不再将该队列添入到排队链表中，而如果未在排队链表中排队，则将该队列添入与该队列优先级对应的排队子链表中。以下通过具体的示例详细说明。

[0040] 假 设 依 次 入 队 的 队 列 号 是：35，13，0，8，0，6，1，64，0，3，55，30，20，80，9，101，...等等。其中，0，1，3号队列属于第一优先级(最高优先级)，6，8，9属于第二优先级，
13，20，30，35属于第三优先级，80，64，55，101属于第四优先级。假设各个队列均满足排队条件。35号队列是最先入队的，查询排队链表标识符地址35(排队链表标识符地址与队列序列完全对应，这将非常方便对队列排队链表标识符的查找)的内容，发现是0(假设0标识队列未在排队链表中排队)时，将35号队列添入排队链表中，同时，把该地址的排队链表标识符修改为1(标识队列已在排队链表中排队)。查询排队链表标识符地址35为1时，就表明该队列已经在链表中排队，不再处理该队列的入队。按照入队顺序，后面的队列13号，
0号，8号，0号等依次查询排队链表标识符。0号队列第二次查询排队链表标识符时，发现已经在链表里面了，将不再将其添入到排队链表中。

[0041] 排队链表的地址数与队列号(队列数)是对应的，每个队列均有排队的地址。本发明在将队列添入排队链表中时，是按队列的优先级将该队列添入到对应优先级的排队子链表中。仍以前述编号的队列为例，第一优先级的排队子链表中将依次添入队列号为0号，1号，3号的队列。图2本发明队列添入排队子链表的结构示意图，如图2所示，排队子链表地址0就是链表首地址，存放的是0号队列号，1号地址中存放的是1号队列号，3号地址中存放的是3号队列，由于排队子链表中只添入了3个队列，地址3指针的下一跳地址就是链表尾地址，内容为空。在将队列添入到排队子链表中时，从排队子链表的尾地址开始存放队列，前述的列号为0号，1号，3号的队列添入排队子链表时，在0号添入时，由于此时第一优先级的排队子链表为空，地址0就是链表尾地址，将0号队列存储于地址0中，此时，地址1就是链表尾地址，将1号队列再添入地址1中。如图2所示，对于第二优先级的队列如前述
8、6、9号队列，仍按前述方法添入到排队子链表中，对于第二优先级的排队子链表，首地址可以是地址8，地址8的下一跳为地址6，存储6号队列，而地址6的下一跳为地址9，用于存储9号队列。存储的队列严格按照排队子链表中的地址指针进行即可，首地址存储首个添入的队列，之后所有的队列依序存储到排队子链表的尾地址中。

[0042] 本发明最优的实现方式是地址数与队列数是相等的，此时，队列数和地址数一一对应。本发明中，只要避免同一个地址对应不同的队列即可。

[0043] 本发明仅以第一、二优先级的队列添入排队子链表为例进行了说明，其余优先级的队列添入相应优先级的排队子链表的方式与此完全相同，这里不再赘述。

[0044] 本发明还包括：在所述排队链表中选择优先级最高的非空排队子链表进行队列调度，优先级最高的非空排队子链表调度完毕后选择次优先级的非空排队子链表进行队列调度。在排队子链表中进行队列调度时，首先从排队子链表的头部输出，再按排队子链表头部指针的指示调度下一队列出队，直到排队子链表为空。

[0045] 仍以前述的队列为例，如第一优先级队列输出顺序依次为0号，1号，3号，...，在第一优先级对应的排队子链表中的队列调度完毕后，查找出当前优先级最高的非空排队子链表，如是第二优先级排队子链表，其队列输出依次为8号，6号，9号，...，接着是第三优先级排队子链表，其队列输出依次为35号，13号，30号，20号，等等。

[0046] 图3为本发明基于链表的队列调度装置的组成结构示意图，如图3所示，本发明基于链表的队列调度装置包括设置单元30、划分单元31、判断单元32、添入单元33和标识修改单元34，其中，设置单元30用于设置排队链表中的地址不少于总队列的数目，以及，为各队列设置标识其是否在所述排队链表中排队的排队链表标识符；划分单元31用于按队列所属优先级将所述排队链表划分为不同的排队子链表，其中，所述排队子链表中的地址不少于所述排队子链表所对应优先级下的所有队列数；判断单元32用于在将符合排队条件的队列添入所述排队链表之前，根据所述队列的排队链表标识符判断所述队列是否已在所述排队链表中排队，若已排队则不作添入处理，若未排队则触发添入单元33；添入单元33用于将所述队列添入所述队列优先级对应的排队子链表的链表尾部，并触发标识修改单元34；标识修改单元34用于将所述队列的排队链表标识符修改为已在所述排队链表中排队的标识。

[0047] 如图3所示，本发明基于链表的队列调度装置还包括调度单元35，用于在所述排队链表中选择优先级最高的排队子链表进行队列调度，优先级最高的排队子链表调度完毕后选择次优先级最高的排队子链表进行队列调度。。

[0048] 本领域技术人员应当理解，调度单元35是为优化本发明基于链表的队列调度装置的技术方案而设置的，并非实现本发明技术方案的必要部件。

[0049] 本领域技术人员应当理解，本发明图3所示的基于链表的队列调度装置是为实现图1所示的基于链表的队列调度方法而设计的，图3所示装置中的各处理单元及处理模块的实现功能可参照图1所示的方法中的相关描述而理解，各单元及各模块的功能可通过运行于处理器上的程序而实现，也可通过相应的逻辑电路而实现。

[0050] 以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。