LiteOS-M内核队列的关键数据结构及关键算法
一、前言
随着数字经济的发展，作为数字基础设施根技术的操作系统成为数字变革的关键力量，openatom openharmony（以下简称“openharmony”） 以泛智能终端数字为底座支撑着千行百业的产业生态。
构建开源生态，需要让开发者先用起来，本文希望通过分享 openharmony 的 liteos-m 内核对象队列的算法详解，让大家对这一算法有更加清晰的认识。 openharmony 当前分为以下几种系统类型：轻量系统 、小型系统、标准系统。针对不同量级的系统，分别使用了不同形态的内核。在轻量系统上，可以选择 liteos-m；在小型系统和标准系统上，可以选用 liteos-a；在标准系统上，可以选用 linux。 在轻小型系统中，openharmony 所使用的内核为 liteos，在标准系统中使用 linux。liteos-m 在面向 lot 领域构建了一款轻量级物联网操作系统内核，嵌入式从业者如果能更好地掌握内核相关的知识，就能在未来做研发或者定制产品的时候独当一面。 二、关键数据结构
首先关注队列的关键数据结构 losqueuecb，有了这个数据，才能理解队列是如何工作的： typedef struct { uint8 *queue; /**< pointer to a queue handle */ uint16 queuestate; /**< queue state */ uint16 queuelen; /**< queue length */ uint16 queuesize; /**< node size */ uint16 queueid; /**< queueid */ uint16 queuehead; /**< node head */ uint16 queuetail; /**< node tail */ uint16 readwriteablecnt[os_readwrite_len]; /**< count of readable or writable resources, 0:readable, 1:writable */ los_dl_list readwritelist[os_readwrite_len]; /**< pointer to the linked list to be read or written, 0:readlist, 1:writelist */ los_dl_list memlist; /**queuelen = len; queuecb->queuesize = msgsize; queuecb->queue = queue; queuecb->queuestate = os_queue_inused; queuecb->readwriteablecnt[os_queue_read] = 0; queuecb->readwriteablecnt[os_queue_write] = len; queuecb->queuehead = 0; queuecb->queuetail = 0; los_listinit(&queuecb->readwritelist[os_queue_read]); los_listinit(&queuecb->readwritelist[os_queue_write]); los_listinit(&queuecb->memlist); los_intrestore(intsave); *queueid = queuecb->queueid; oshookcall(los_hook_type_queue_create, queuecb); return los_ok;}
数据结构是支撑算法的灵魂，内核对象的队列控制结构 losqueuecb 通过 queue 指针来指向具体队列的内容，队列分配了 queuelen 个消息，每个消息的大小为 queuesize，与此同时头指针和尾指针不约而同初始化为 0。
第二步：第一个消息入队列
生产者通过队列来传递信息，这个生产者可以是形形色色的各个任务，产生一个队列后，任务就迫不及待的需要放置消息，选择 fifo 还是 filo？这一次我们选择了 fifo。
下图是 fifo 插入第一个数据后的内存形态。
openharmony 作为一个开源系统，在下面的代码中很好地体现了这个操作：
static inline void osqueuebufferoperate(losqueuecb *queuecb, uint32 operatetype, void *bufferaddr, uint32 *buffersize){ uint8 *queuenode = null; uint32 msgdatasize; uint16 queueposition; errno_t rc; /* get the queue position */ switch (os_queue_operate_get(operatetype)) { case os_queue_read_head: queueposition = queuecb->queuehead; ((queuecb->queuehead + 1) == queuecb->queuelen) ? (queuecb->queuehead = 0) : (queuecb->queuehead++); break; case os_queue_write_head: (queuecb->queuehead == 0) ? (queuecb->queuehead = (queuecb->queuelen - 1)) : (--queuecb->queuehead); queueposition = queuecb->queuehead; break; case os_queue_write_tail: queueposition = queuecb->queuetail; ((queuecb->queuetail + 1) == queuecb->queuelen) ? (queuecb->queuetail = 0) : (queuecb->queuetail++); break; ...}
osqueuebufferoperate 是队列内存的核心操作函数，fifo 算法本质是往队列的尾处添加数据，代码抽象为 os_queue_write_tail 操作，请注意队列是个循环队列，插入数据后移动 tail 这个“尾巴”指针要尤为小心，在最后一个物理空间用完成后需要移到队列头部，这就是环形队列的“循环大法”。
如何判断最后一个物理空间已经用完？(queuecb->queuetail + 1) == queuecb->queuelen)c 语言语句很好地解释了这个疑问。queuelen 是队列物理空间的边界值，如果下一个消息已经指到这个边界值，那么内核必须让它回到原位，即 queuecb->queuetail = 0，不然可能会出现“内存越界”的问题，可能会造成机毁物亡。因为 openharmony 应用在各个领域，如果是自动化驾驶领域那么造成的后果非常严重。
第三步：继续生产数据
接下来，再来一些图片示例：
第四步：生产数据结束
生产者生产了四个消息后就结束了。
3.2 fifo算法之出队列
第一步：队列第一个消息
如上图所示我们回顾下入队列的步骤，知道了每个消息的入队顺序，于是第一个消息被消费后:
在生产消息过程中我们已经提到 osqueuebufferoperate 这个函数，我们回顾关键代码：
/* get the queue position */switch (os_queue_operate_get(operatetype)) { case os_queue_read_head: queueposition = queuecb->queuehead; ((queuecb->queuehead + 1) == queuecb->queuelen) ? (queuecb->queuehead = 0) : (queuecb->queuehead++); break;
queuehead 就是我们的头指针，它的移动也面临着生产过程相同的问题，在最后一个物理空间用完成后需要移到队列的头部。os_queue_read_head 是出队列的关键处理，解决了 queuehead 头指针如何移动的问题。
第二步：继续消费
第三步：消费完毕
最后一个消息也消失了，head指针和tail指针均移动到下图的位置，此时队列为空。
四、总结
本文主要介绍了 openharmony 内核对象队列的算法之 fifo，在后续的篇章中将给大家介绍内核对象队列另外一种算法——filo。希望通过这篇文章，可以让开发者们对于目前 openharmony liteos-m 内核队列算法有了更全面的概念。
当然队列算法也不远远如此，linux 标准内核有加权队列等更复杂的算法。但是“他山之石，可以攻玉”，技术万变不离其宗，掌握了 fifo 的细节有助于工程师设计其它队列算法，也能够把更多更新的技术带入到 openharmony 社区，繁荣开源生态。
原文标题：openharmony——内核对象队列之算法详解（上）
文章出处：【微信公众号：深开鸿】欢迎添加关注！文章转载请注明出处。
博通新一代GPS芯片定位精度30厘米以内适用城市及密林
华为AOC光线缆的分类及型号
入户皮线光缆的衰耗是怎么回事？
深入浅出学习eTs之电话提示功能实现
风头劲压iPhone 弯曲手机、可穿戴电子产品照亮2013
LiteOS-M内核队列的关键数据结构及关键算法
Neuchips与新思科技合作开展帮助降低进入人工智能领域的门槛
芯片是如何去定义的
魔方网表，使用无代码软件赋能团队
“山寨科技” 该培育还是该扼杀？
2020年4月前苹果App都需使用iOS 13 SDK构建
天禄科技业绩下滑，推进TAC膜国产化研发
STM32低成本WiFi播放电路设计详解
健康码扫码测温一体机及健康码终端解决方案助力秋冬季疫情防控
2020年或将是L3自动驾驶整体发展路线能够确定下来的一年
怎样设计数字电路板可以获得最好的SI和EMC特性
大功率变频装置电压等级必须下降
德赛西威与杰发科技签订合作协议 助推国产汽车电子芯片发展
电源管理芯片商必易微上市，首日开盘大涨26.93%，募资6.5亿元拓展电机驱控芯片等
Visual Studio Code快捷键的使用基于3568开发板vscode的使用
随着数字经济的发展，作为数字基础设施根技术的操作系统成为数字变革的关键力量，openatom openharmony（以下简称“openharmony”） 以泛智能终端数字为底座支撑着千行百业的产业生态。
构建开源生态，需要让开发者先用起来，本文希望通过分享 openharmony 的 liteos-m 内核对象队列的算法详解，让大家对这一算法有更加清晰的认识。 openharmony 当前分为以下几种系统类型：轻量系统 、小型系统、标准系统。针对不同量级的系统，分别使用了不同形态的内核。在轻量系统上，可以选择 liteos-m；在小型系统和标准系统上，可以选用 liteos-a；在标准系统上，可以选用 linux。 在轻小型系统中，openharmony 所使用的内核为 liteos，在标准系统中使用 linux。liteos-m 在面向 lot 领域构建了一款轻量级物联网操作系统内核，嵌入式从业者如果能更好地掌握内核相关的知识，就能在未来做研发或者定制产品的时候独当一面。 二、关键数据结构
首先关注队列的关键数据结构 losqueuecb，有了这个数据，才能理解队列是如何工作的： typedef struct { uint8 *queue; /**< pointer to a queue handle */ uint16 queuestate; /**< queue state */ uint16 queuelen; /**< queue length */ uint16 queuesize; /**< node size */ uint16 queueid; /**< queueid */ uint16 queuehead; /**< node head */ uint16 queuetail; /**< node tail */ uint16 readwriteablecnt[os_readwrite_len]; /**< count of readable or writable resources, 0:readable, 1:writable */ los_dl_list readwritelist[os_readwrite_len]; /**< pointer to the linked list to be read or written, 0:readlist, 1:writelist */ los_dl_list memlist; /**queuelen = len; queuecb->queuesize = msgsize; queuecb->queue = queue; queuecb->queuestate = os_queue_inused; queuecb->readwriteablecnt[os_queue_read] = 0; queuecb->readwriteablecnt[os_queue_write] = len; queuecb->queuehead = 0; queuecb->queuetail = 0; los_listinit(&queuecb->readwritelist[os_queue_read]); los_listinit(&queuecb->readwritelist[os_queue_write]); los_listinit(&queuecb->memlist); los_intrestore(intsave); *queueid = queuecb->queueid; oshookcall(los_hook_type_queue_create, queuecb); return los_ok;}
数据结构是支撑算法的灵魂，内核对象的队列控制结构 losqueuecb 通过 queue 指针来指向具体队列的内容，队列分配了 queuelen 个消息，每个消息的大小为 queuesize，与此同时头指针和尾指针不约而同初始化为 0。
第二步：第一个消息入队列
生产者通过队列来传递信息，这个生产者可以是形形色色的各个任务，产生一个队列后，任务就迫不及待的需要放置消息，选择 fifo 还是 filo？这一次我们选择了 fifo。
下图是 fifo 插入第一个数据后的内存形态。
openharmony 作为一个开源系统，在下面的代码中很好地体现了这个操作：
static inline void osqueuebufferoperate(losqueuecb *queuecb, uint32 operatetype, void *bufferaddr, uint32 *buffersize){ uint8 *queuenode = null; uint32 msgdatasize; uint16 queueposition; errno_t rc; /* get the queue position */ switch (os_queue_operate_get(operatetype)) { case os_queue_read_head: queueposition = queuecb->queuehead; ((queuecb->queuehead + 1) == queuecb->queuelen) ? (queuecb->queuehead = 0) : (queuecb->queuehead++); break; case os_queue_write_head: (queuecb->queuehead == 0) ? (queuecb->queuehead = (queuecb->queuelen - 1)) : (--queuecb->queuehead); queueposition = queuecb->queuehead; break; case os_queue_write_tail: queueposition = queuecb->queuetail; ((queuecb->queuetail + 1) == queuecb->queuelen) ? (queuecb->queuetail = 0) : (queuecb->queuetail++); break; ...}
osqueuebufferoperate 是队列内存的核心操作函数，fifo 算法本质是往队列的尾处添加数据，代码抽象为 os_queue_write_tail 操作，请注意队列是个循环队列，插入数据后移动 tail 这个“尾巴”指针要尤为小心，在最后一个物理空间用完成后需要移到队列头部，这就是环形队列的“循环大法”。
如何判断最后一个物理空间已经用完？(queuecb->queuetail + 1) == queuecb->queuelen)c 语言语句很好地解释了这个疑问。queuelen 是队列物理空间的边界值，如果下一个消息已经指到这个边界值，那么内核必须让它回到原位，即 queuecb->queuetail = 0，不然可能会出现“内存越界”的问题，可能会造成机毁物亡。因为 openharmony 应用在各个领域，如果是自动化驾驶领域那么造成的后果非常严重。
第三步：继续生产数据
接下来，再来一些图片示例：
第四步：生产数据结束
生产者生产了四个消息后就结束了。
3.2 fifo算法之出队列
第一步：队列第一个消息
如上图所示我们回顾下入队列的步骤，知道了每个消息的入队顺序，于是第一个消息被消费后:
在生产消息过程中我们已经提到 osqueuebufferoperate 这个函数，我们回顾关键代码：
/* get the queue position */switch (os_queue_operate_get(operatetype)) { case os_queue_read_head: queueposition = queuecb->queuehead; ((queuecb->queuehead + 1) == queuecb->queuelen) ? (queuecb->queuehead = 0) : (queuecb->queuehead++); break;
queuehead 就是我们的头指针，它的移动也面临着生产过程相同的问题，在最后一个物理空间用完成后需要移到队列的头部。os_queue_read_head 是出队列的关键处理，解决了 queuehead 头指针如何移动的问题。
第二步：继续消费
第三步：消费完毕
最后一个消息也消失了，head指针和tail指针均移动到下图的位置，此时队列为空。
四、总结
本文主要介绍了 openharmony 内核对象队列的算法之 fifo，在后续的篇章中将给大家介绍内核对象队列另外一种算法——filo。希望通过这篇文章，可以让开发者们对于目前 openharmony liteos-m 内核队列算法有了更全面的概念。
当然队列算法也不远远如此，linux 标准内核有加权队列等更复杂的算法。但是“他山之石，可以攻玉”，技术万变不离其宗，掌握了 fifo 的细节有助于工程师设计其它队列算法，也能够把更多更新的技术带入到 openharmony 社区，繁荣开源生态。
原文标题：openharmony——内核对象队列之算法详解（上）
文章出处：【微信公众号：深开鸿】欢迎添加关注！文章转载请注明出处。
博通新一代GPS芯片定位精度30厘米以内适用城市及密林
华为AOC光线缆的分类及型号
入户皮线光缆的衰耗是怎么回事？
深入浅出学习eTs之电话提示功能实现
风头劲压iPhone 弯曲手机、可穿戴电子产品照亮2013
LiteOS-M内核队列的关键数据结构及关键算法
Neuchips与新思科技合作开展帮助降低进入人工智能领域的门槛
芯片是如何去定义的
魔方网表，使用无代码软件赋能团队
“山寨科技” 该培育还是该扼杀？
2020年4月前苹果App都需使用iOS 13 SDK构建
天禄科技业绩下滑，推进TAC膜国产化研发
STM32低成本WiFi播放电路设计详解
健康码扫码测温一体机及健康码终端解决方案助力秋冬季疫情防控
2020年或将是L3自动驾驶整体发展路线能够确定下来的一年
怎样设计数字电路板可以获得最好的SI和EMC特性
大功率变频装置电压等级必须下降
德赛西威与杰发科技签订合作协议 助推国产汽车电子芯片发展
电源管理芯片商必易微上市，首日开盘大涨26.93%，募资6.5亿元拓展电机驱控芯片等
Visual Studio Code快捷键的使用基于3568开发板vscode的使用