当前位置:

首页 > 系统应用 > OpenHarmony——内核对象队列之算法详解(下)

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

OpenHarmony——内核对象队列之算法详解(下)前言OpenAtom OpenHarmony(以下简称“OpenHarmony”) LiteOS-M 内核是面向 IoT 领域构建的轻量级物联网操作系统内核,具有小体积、低功耗、高性能的特点。在嵌入

本文目录
    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算法之入队列

    第一步:队列初始化

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

    截取关键函数LOS_QueueCreate,此函数来源于liteos_m内核代码。

    LITE_OS_SEC_TEXT_INIT UINT32 LOS_QueueCreate(CHAR *queueName,
    UINT16 len,
    UINT32 *queueID,
    UINT32 flags,
    UINT16 maxMsgSize)
    {
    LosQueueCB *queueCB = NULL;
    UINT32 intSa ve;
    LOS_DL_LIST *unusedQueue = NULL;
    UINT8 *queue = NULL;
    UINT16 msgSize;
    ...
    queue = (UINT8 )LOS_MemAlloc(m_aucSysMem0, len msgSize);
    ...
    queueCB->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(intSa ve);


    *queueID = queueCB->queueID;


    OsHookCall(LOS_HOOK_TYPE_QUEUE_CREATE, queueCB);


    return LOS_OK;
    }

    queue指针指向队列的内存,队列分配了len个消息,每个消息的大小为msgSize。与此同时头指针和尾指针的初始化为0,意味着队列为空,还没有消息入队列。

    第二步:第一个消息入队列

    各类任务可以作为队列的生产者,队列初始化后,任务可以放置第一个消息,在此选择FILO的方式来放置消息。

    下图是FIFO插入第一个数据后的内存形态:

    FILO的操作包含在OsQueueBufferOperate函数中,这次是进入OS_QUEUE_WRITE_HEAD的分支处理:

    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是队列内存的核心操作函数,FILO算法的本质是往队列的头部添加数据,入队列的操作抽象为OS_QUEUE_WRITE_HEAD操作。而本次操作和FIFO不一样,插入数据不再移动tail这个“尾巴”指针,后续无论是入队列操作还是出队列操作,tail指针都不会被操作。

    第三步:继续生产数据

    数据继续生产,第2个消息进入队列后继续移动head指针,如下图所示:

    第三个消息也是重复的移动head指针,如下图所示:

    第四步:生产数据结束

    本次实例以生产者生产四个消息为结束点,最后形态的队列下图所示:

    1.2 FIFO算法之出队列

    第一步:取出队列头消息。由于这是先入后出的算法,因此第一个出队列的消息是最后入队列的,也就是队列中标注为“第4个”的消息。

    消费后的消息空间也是unused空间,在此处用其它颜色标注消费后的消息,便于读者理解队列的变化情况。

    回顾一下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是头指针,它的移动代表着出队列的行为,queueHead目前指向“第4个”消息,往后移动一个,应用得到“第4个”消息的返回值。此处可见,最后入队列的消息最先出。

    第二步:继续消费

    第三个消息被消费的图示:

    第二个消息被消费的图示:

    第三步:消费完毕

    最后一个消息也处理完成,于是head指针和tail指针均移动到下图的位置。队列为空,任务结束。

    这时如果把图重新换个方向来看,那么就很容易了解这个算法的本质。Tail指针全程没有用到,如果把它去掉,水平方向的队列改为垂直方向。如下图所示,可见该图片为典型的入栈操作。由此可知,OpenHarmony内核通过头指针的写操作和读操作,把栈的操作兼容到队列中。

    总结

    本文着重介绍了OpenHarmony内核对象队列算法中的FILO。至此,队列的两个算法FIFO和FILO就都介绍完了。通过详细解析这两个算法,开发者能更全面地理解OpenHarmony LiteOS-M内核队列算法,从而在未来内核开发工作中遇到其他队列算法时,能够触类旁通,快速掌握。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    系统应用
    相关文章 更多
    龙芯推出行业首款OpenHarmony自助服务产品开源鸿蒙落地深圳
    龙芯推出行业首款OpenHarmony自助服务产品开源鸿蒙落地深圳

    德卡科技以龙芯处理器为核心,联合深开鸿基于KaihongOS推出行业首款OpenHarmony原生自助服务产品,实现从芯片到应用的100%自主可控。该产品采用ArkTS原生开发,方舟运行时保障60fps流畅动效,支持离线运行与分布式协同,已在深圳多家医疗机构落地。

    AO3官网镜像链接一键跳转-手机入口快速访问
    AO3官网镜像链接一键跳转-手机入口快速访问

    AO3官网可通过https://www.ao3cn.cc//直接访问,支持手机和桌面端,页面适配移动端,操作流畅,支持书签、收藏、订阅及作品导出等功能,内容涵盖全球同人创作,分类细致,互动性强。

    AO3中文版官网与使用指南
    AO3中文版官网与使用指南

    AO3中文版官网入口为https://www.ao3cn.cc//,进入后点击右上角“Preferences”选择“中文(简体)”并更新即可切换语言,支持免登录浏览海量原创作品,利用标签系统精准筛选内容,平台无广告干扰且开源透明;注册账号后可发布、收藏、点赞和评论作品,并通过高级搜索功能按字数、时间等条件查找资源,实现高效互动与创作共享。

    AO3主页入口及最新镜像链接合集
    AO3主页入口及最新镜像链接合集

    AO3官方主站入口为https://www.ao3cn.cc//,提供作品发布、隐私设置、个人书架、评论管理等功能;支持多语言与移动端浏览,具备高级搜索和标签评级系统;镜像站点如https://ao3.cubeart.club/和https://xiaozhan.icu/仅作临时备用,不可输入账号密码。

    AO3官网中文入口最新地址公布
    AO3官网中文入口最新地址公布

    AO3官网中文访问入口为https://www.ao3cn.cc/,用户可直接通过主流浏览器访问,支持多语言切换至中文界面,新用户需通过邀请注册,老用户可直接登录,平台汇聚全球同人小说、画作与视频,支持自主上传与标签分类,便于检索与收藏,建议使用官方链接避免镜像站,结合筛选功能与书签快捷访问提升体验。

    AO3中文入口及官方镜像链接
    AO3中文入口及官方镜像链接

    AO3网页版中文入口为https://www.ao3cn.cc/,用户可直接访问官网注册登录,切换中文界面后使用多维度标签筛选、下载作品、互动评论等功能,享受无广告、隐私安全的非盈利创作平台。

    LibreOffice怎么卸载干净?残留配置怎么清理
    LibreOffice怎么卸载干净?残留配置怎么清理

    卸载LibreOffice应先使用系统的应用管理或原安装渠道移除程序,再按需要处理用户配置。模板、个人词典、宏和恢复备份可能保存在配置目录中,清理前先备份;普通文档不属于程序残留,不要为了“卸载干净”一起删除。以下主流程适用于Windows和Debian、Ubuntu仓库版。

    WorkBuddy怎么下载?电脑端和手机端在哪里安装
    WorkBuddy怎么下载?电脑端和手机端在哪里安装

    WorkBuddy 下载方法:电脑端从官网 workbuddy.cn 点「立即下载」获取安装包(Windows 装 exe、Mac 按 M 系列/Intel 芯片选 ARM64/X64 的 dmg),Linux 与麒麟/UOS 在系统应用商店搜索安装;手机端 iOS 在 App Store、Android 在应用市场搜「WorkBuddy」。本文含官网下载页与安装向导真实截图。

    WorkBuddy怎么用版本历史?误删了怎么恢复
    WorkBuddy怎么用版本历史?误删了怎么恢复

    WorkBuddy 的版本历史通过对话回退实现:把鼠标悬停在你发送的消息上,点「回退」并确认,对话和受影响的产物会一起回到这条消息之前;产物还有独立的历史版本,误改可在「变更」视图核对、用「恢复」还原。误删文件优先去系统回收站/废纸篓找,误删任务可在「系统设置 → 数据管理」查看已归档任务。本文含5张真实界面截图与恢复顺序表。

    Yandex引擎入口2026最新登录方式
    Yandex引擎入口2026最新登录方式

    Yandex搜索引擎的官方登录入口是https://www.yondex.net/,该平台支持多语言界面切换、智能语言识别与音译转换,并提供个性化服务及高效检索技术,满足全球用户需求。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。