本文说明Zephyr使用的三种列队管理算法。

Zephyr维护了1个就绪列队和多个内核对象等待列队。所有就绪线程被放入就绪列队等待调度器来选择线程进入调度，等待信号量，互斥量等其它内核对象的线程，会分别放到对应内核对象的等待列队中，当等待的资源就绪时，将从对应的列队中选出线程使用资源。

在Zephyr运行过程中，根据运行的情况任意一个列队中都可能存在多个线程，随时都会有线程会从列队中加入，取出。这些对列队的操作需要满足选择出优先级最高且等待最久的线程，Zephyr中提供三种算法用于管理列队，不同的工作环境可以通过配置Zephyr选择不同的算法管理不同的列队。

列队管理算法

Zephyr提供三种列队管理算法管理列队，不同的的列队管理算法适用于不同的场景，Zephyr列队管理算法在一开始就配置好后通过编译的方式固定下来，运行过程中是无法修改的。任何列队的管理算法都提供“插入”，“查询”，“删除”三种操作。

单链表

单链表是用一条双向链表将列队内的所有线程串接起来，单链表列队算法的代码量和占用内存都非常小，在列队内线程较少的情况下O(n)的时间复杂度基本可以忽略，因此存储敏感的系统且列队内只需要管理较少线程的情况下可选用该算法。

对单链表列队进行插入时，会从前向后遍历单链表，当遇到有插入线程优先级级小的线程节点时，将线程插入到该线程节点前，其插入算法的时间复杂度为O(n)：

dumbadd

对单链表列队进行查询时，需要取出优先级最高且等待最久的线程。在插入的时候已经将链表排序，因此直接取出单链表的第一个节点就可以满足该条件，查询的时间复杂度为O(1):

dumbbest

对单链表列队进行删除时，可能是列队中任何线程，因此会从前向后遍历单链表，当遇到指定的线程时将其从单链表中移除，其删除的时间复杂度为O(n)，这个过程是标准的单链表操作，不再画图说明。

红黑树

红黑树在插入，查询，删除三个操作上都有稳定的时间复杂度O(logn)，适用于管理列队线程超过20以上的系统。在Zephyr中大多数情况下红黑树会使用大约2KB的代码量，存储敏感的系统不适合选择该算法。

线程插入列队时，在红黑树中依据线程优先级排序，同时为了辨别那个线程被先加入列队会维护一个order_key，每插入一个线程到列队中order_key就加一，并将该order_key值和插入的线程绑定，因此越先插入的线程等待的时间就越久，对应的order_key就越小。当线程优先级一样时就以绑定给线程的order_key排序：

rbadd

对红黑树列队进行查询时，需要取出优先级最高且等待最久的线程。将从根节点开始遍历，右叶子节点的优先级级比父节点的优先级高，如果右叶子几点和父节点的优先级相等，那么右叶子节点的order_key要比父节点小(order_key小的先加入列队，等待时间更长):

rbdel

对红黑树列队进行删除时，会按照和查询一样的算法进行遍历，找到指定的线程后执行删除和变换红黑树，上图演示了该过程。

多链表列队

多链表队列是有一个数组加多个链表组成，每个数组元素指向一个链表，每个链表内保存相同优先级的线程。多链表列队在代码量上和单链表列队相差无几，但会多使用内存。为了控制内存的用量, Zephyr限制在多链表队列下只允许线程32个优先级。多链表列队在插入，查询，删除的算法都是一致的，第一步先在数组中定位线程所在的链表，再操作链表。多链表列队的数据结构如下：

struct _priq_mq {
	sys_dlist_t queues[32];
	unsigned int bitmask; /* bit 1<<i set if queues[i] is non-empty */
};

queues对应32个优先级的链表，bitmask中以bit的位置标识有哪些优先级上有线程在链表中，Zephyr中配置了最高优先级K_HIGHEST_THREAD_PRIO，假设要定位优先级为prio所在的链表是queues[prio-K_HIGHEST_THREAD_PRIO]，Zephyr中优先级越高其数字越低，所以这里会用减。

对多链表列队进行插入时，会先通过插入线程的优先级定位到线程链表，再将线程插入到链表末尾，其插入算法的时间复杂度为O(1)：

对多链表列队进行查询时，先计算bitmask低位的连续0数量，该数量就是最高优先级在多链表数组中的下标，通过下标取得最高优先级所在链表，其链表的头节点就是等待最久的线程，直接取出该节点完成查询，可见查询的时间复杂度为O(1)：

multibest

对多链表列队进行删除时，可能是列队中任何线程，会根据要删除线程的优先级直接找到对应的链表，再从前向后遍历单链表，当遇到指定的线程时将其从链表中移除，如果该优先级链表中只有一个线程，删除的时间复杂度最优为O(1)，如果所有的线程都集中在这个优先级上，时间复杂度变为O(n)，因此在使用多链表列队算法时要适当安排线程优先级。

5.2.1.2 列队算法选择

在Zephyr中不是所有的列队都可以任意选择列队管理算法，用户要根据实际的需求选择Zephyr允许用列队算法。

就绪列队可选算法

就绪列队用于管理就绪线程，三种列队算法都可任选一种，通过下面配置项选择

单链表队列：CONFIG_SCHED_DUMB=y
红黑树：CONFIG_SCHED_SCALABLE=y
多链表队列(CONFIG_SCHED_MULTIQ=y

内核对象等待列队

等待信号量，互斥量等内核对象的线程被放入内核对象等待列队，每个可等待的内核对象都有一个自己的等待列队，所有内核对象只能使用相同的列队等待算法，通过配置可以选择下面两种算法之一：

单链表队列：CONFIG_WAITQ_DUMB=y
红黑树：CONFIG_WAITQ_SCALABLE=y

参考

https://docs.zephyrproject.org/latest/reference/kernel/scheduling/index.html