OpenHarmony——内核对象队列之算法详解（下）
前言
OpenAtom OpenHarmony（以下简称“OpenHarmony”） LiteOS-M 内核是面向 IoT 领域构建的轻量级物联网操作系统内核，具有小体积、低功耗、高性能的特点。在嵌入式领域的开发工作中，无论是自研还是移植系统，均绕不开内核，开发者只有掌握内核的相关知识，才能更好地深耕物联网产品领域。OpenHarmony LiteOS-M 内核对象队列的算法包括 FIFO 和 FILO，在上一期发布的《OpenHarmony-内核对象队列之算法详解（上）》文章中，我分享了 OpenHarmonyLiteOS-M 内核对象队列的 FIFO 的算法，今天给大家介绍另外一种算法——FILO 算法。
关键数据结构
首先关注队列的关键数据结构 LosQueueCB，有了这个数据，才能理解队列是如何工作的：
queue：指向消息节点内存区域，创建队列时按照消息节点个数乘每个节点大小从动态内存池中申请一片空间。
queueState：队列状态，表明队列控制块是否被使用，有 OS_QUEUE_INUSED 和 OS_QUEUE_UNUSED 两种状态。
queueLen：消息节点个数，表示该消息队列最大可存储多少个消息。
queueSize：每个消息节点大小，表示队列每个消息可存储信息的大小。
queueID：消息 ID，通过它来操作队列。
消息节点按照循环队列的方式访问，队列中的每个节点以数组下标表示，下面的成员与消息节点循环队列有关：
queueHead：循环队列的头部。
queueTail：循环队列的尾部。
readWriteableCnt[OS_QUEUE_WRITE]：消息节点循环队列中可写的消息个数，为 0 表示循环队列为满，等于 queueLen 表示循环队列为空。 readWriteableCnt[OS_QUEUE_READ]：消息节点循环队列中可读的消息个数，为 0 表示循环队列为空，等于 queueLen 表示消息队列为满。 readWriteList[OS_QUEUE_WRITE]：写消息阻塞链表，链接因消息队列满而无法写入时需要挂起的 TASK。
readWriteList[OS_QUEUE_READ]：读消息阻塞链表，链接因消息队列空而无法读取时需要挂起的 TASK。
memList：申请内存块阻塞链表，链接因申请某一静态内存池中的内存块失败而需要挂起的 TASK。
关键算法
在计算机程序设计中，“先入先出”和“先入后出”都是处理输入数据的方法。上篇文章向大家介绍了 FIFO（先入先出）算法，今天给大家讲解 FILO（先入后出）算法。一个先入后出(FILO,First In Last Out)的队列，可以形象地理解为手枪的弹匣，装子弹是“入队列”，射击是“出队列”，最先压入弹匣的子弹是最后射出去的。同理，最先入队列的消息也是在最后处理，这就是 FILO（先入后出）算法的本质。
1.1FIFO 算法之入队列
第一步：队列初始化
下图呈现了一个初始化后的队列：
截取关键函数 LOS_QueueCreate，此函数来源于 liteos_m 内核代码。
queue 指针指向队列的内存，队列分配了 len 个消息，每个消息的大小为 msgSize。与此同时头指针和尾指针的初始化为 0，意味着队列为空，还没有消息入队列。
第二步：第一个消息入队列
各类任务可以作为队列的生产者，队列初始化后，任务可以放置第一个消息，在此选择 FILO 的方式来放置消息。
下图是 FIFO 插入第一个数据后的内存形态：
FILO 的操作包含在 OsQueueBufferOperate 函数中，这次是进入 OS_QUEUE_WRITE_HEAD 的分支处理：
OsQueueBufferOperate 是队列内存的核心操作函数，FILO 算法的本质是往队列的头部添加数据，入队列的操作抽象为 OS_QUEUE_WRITE_HEAD 操作。而本次操作和 FIFO 不一样，插入数据不再移动 tail 这个“尾巴”指针，后续无论是入队列操作还是出队列操作，tail 指针都不会被操作。
第三步：继续生产数据
数据继续生产，第 2 个消息进入队列后继续移动 head 指针，如下图所示：
第三个消息也是重复的移动 head 指针，如下图所示：
第四步：生产数据结束
本次实例以生产者生产四个消息为结束点，最后形态的队列下图所示：
1.2 FIFO 算法之出队列
第一步：取出队列头消息。由于这是先入后出的算法，因此第一个出队列的消息是最后入队列的，也就是队列中标注为“第 4 个”的消息。
消费后的消息空间也是 unused 空间，在此处用其它颜色标注消费后的消息，便于读者理解队列的变化情况。
回顾一下 OsQueueBufferOperate 函数的关键代码，这一次是读的分支：
queueHead 是头指针，它的移动代表着出队列的行为，queueHead 目前指向“第 4 个”消息，往后移动一个，应用得到“第 4 个”消息的返回值。此处可见，最后入队列的消息最先出。
第二步：继续消费
第三个消息被消费的图示：
第二个消息被消费的图示：
第三步：消费完毕
最后一个消息也处理完成，于是 head 指针和 tail 指针均移动到下图的位置。队列为空，任务结束。
这时如果把图重新换个方向来看，那么就很容易了解这个算法的本质。Tail 指针全程没有用到，如果把它去掉，水平方向的队列改为垂直方向。如下图所示，可见该图片为典型的入栈操作。由此可知，OpenHarmony 内核通过头指针的写操作和读操作，把栈的操作兼容到队列中。
总结
本文主要介绍了 OpenHarmony 内核对象队列的算法之 FILO，至此，队列的 2 个算法都已介绍完毕。通过对 FIFO 和 FILO 这 2 个算法的详解，开发者能够更加全面了解 OpenHarmony LiteOS-M 内核队列算法，以便将来在内核开发工作中遇到队列的其他算法，也能够举一反三，迅速掌握。
OpenHarmony开发者官方账号 2021.12.15 加入
OpenHarmony是由开放原子开源基金会（OpenAtom Foundation）孵化及运营的开源项目，目标是面向全场景、全连接、全智能时代，基于开源的方式，搭建一个智能终端设备操作系统的框架和平台，促进万物互联产业的繁荣发展
评论