OpenHarmony——内核对象队列之算法详解(下)

08/09 16:16
阅读数 6.2K

OpenHarmony——内核对象队列之算法详解(下)

前言

OpenAtom OpenHarmony(以下简称“OpenHarmony”) LiteOS-M 内核是面向 IoT 领域构建的轻量级物联网操作系统内核,具有小体积、低功耗、高性能的特点。在嵌入式领域的开发工作中,无论是自研还是移植系统,均绕不开内核,开发者只有掌握内核的相关知识,才能更好地深耕物联网产品领域。OpenHarmony LiteOS-M内核对象队列的算法包括FIFO和FILO,在上一期发布的《OpenHarmony-内核对象队列之算法详解(上)》文章中,我分享了OpenHarmonyLiteOS-M内核对象队列的FIFO的算法,今天给大家介绍另外一种算法——FILO算法。

关键数据结构

首先关注队列的关键数据结构LosQueueCB,有了这个数据,才能理解队列是如何工作的:

 

typedef struct {
 UINT8 queue; /< 消息队列内存区域的指针/
 UINT16 queueState; /*< 消息队列状态 /
 UINT16 queueLen; /*< 消息队列状态个数 /
 UINT16 queueSize; /*< 每个消息节点大小 /
 UINT16 queueID; /*< 消息身份 /
 UINT16 queueHead; /*< 消息队列的头部/
 UINT16 queueTail; /*< 消息队列的尾部 /
 UINT16 readWriteableCnt[OS_READWRITE_LEN]; /*< 消息节点循环队列中读或写的消息个数/
 LOS_DL_LIST readWriteList[OS_READWRITE_LEN]; /*< 读或写消息阻塞链表/
 LOS_DL_LIST memList; /*< Pointer to the memory linked list /
 }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算法之入队列

第一步:队列初始化

下图呈现了一个初始化后的队列:   </