YueOS 重构日志 (0) - 任务与进程
任务与进程 任务 任务是在构建应用时逻辑上进行划分的最小单位。任务按照性质被划分为重要任务、次要任务与系统任务。 重要任务 指对时间敏感的任务。(亦可理解为原叙述中的"为完成某个该任务而进行的系统设计") 次要任务 指对时间不敏感的任务。(亦可理解为原叙述中的"为完成重要任务而执行的辅助任务") 系统任务 系统为维持自身功能正常而必须进行的任务。 进程 因为 STM32 多为单核心,因此只使用进程进行描述。在每个进程可以完成逻辑上的一个或多个任务,但注意进程是系统调度中的最小单位。 进程管理器系列 API 职能:完成进程的创建/删除,启动/停止,信息收集与管理;调度器系列 API 职能:对进程进行调度。 在语法上有一个明显区别:即进程管理器必须指定目标对象;调度器不需要指定对象。 与任务一一对应,处理重要任务的进程被称为重要进程,处理次要任务的进程被称为次要进程,处理系统任务的进程被称为系统进程。 进程的调度行为 重要进程的调度由任务管理器生成的静态调度表进行规划,属于硬实时调度。 次要进程的调度由优先级决定,属...
基于异或实现的单方向双链表
基于异或实现的单方向双链表 背景 在某些应用中需要使用分配在栈上的不定长内存数组。而我常用的泛型双链表是弱定义的,在开发专用模块时使用很方便;但在上述使用情景时,使用会变得很繁杂,另外储存一个单位需要额外的两个单位。 空间利用率实在有些难以恭维,于是便有了这个小模块的诞生。在简单应用中,一般是对某不定长的单位组进行保存,即压栈/出栈,入列/出列。 双向链表与异或 链表需要进行保存自身的入口,即链表元素的地址。 另外,每个元素都会保存前驱(Before)和后继(After)节点。这就是上文提到的额外的两个存储单位。 为了压缩空间,很容易想到对 B 和 A 进行融合,显然与和或都会造成信息的损失,于是使用异或(总之就是取反,懒得解释了)。 异或的性质 a ⊙ a ⊙ b = b 。 于是,我们有一个链表,首结点 B = NULL 、尾结点 A = NULL 。以从头至尾举例: 首结点的 A ⊙ B = A ,故获得了后继结点。 对于后继结点,首结点是已知的,换言之,前驱 A 已知。于是 B ⊙ A ⊙ B = A 。 循环上述步骤。 这种链表既可以从头至尾也可以从尾...
YueOS 开发日志 (1) - 内存管理
内存管理 内存管理的目标 建立合理的机制,将内存快速、高效(使用率)及安全的分配给需要的申请者。 内存申请行为的分类 对于内存申请行为有如下几种可能: 编译时确定 如果程序在设计时就能确定某种数据结构需要实例化的数量,应该优先使用全局变量。这样可以利用编译器来进行内存空间检查。 如一辆脉轮小车底盘的电机速度环 PID 。 运行时确定 某种数据结构在编译时无法确定所有信息(如通信缓冲区大小或打开文件的数量)。这种情况下可以考虑使用堆内存。 长时间持有 某些应用中,一旦申请内存,就几乎不会释放或是在可预见的时间段内都不会将其释放,这种情况称为长时间持有。 应按具体情况选择全局变量或是堆内存申请。 短时间持有 对于某些事件,可以明确估计出该事件的处理器的响应时间,从而估算出某内存空间的使用时间,这种情况被称为短时间持有的内存申请。 若该事件频率较低且所需内存空间较小,则可考虑使用池内存 若频率较高或所需内存空间较大,则可考虑使用堆内存或全局变量。 内存管理的数据结构 内存堆 内存堆是一块连续的大容量内存空间。当用户申请内存时,将从内存堆上划分出...
YueOS 重构日志 - 内存管理
内存管理 每个进程可支配的全部内存空间有下述几个部分构成: 全局堆 系统初始化时,由系统维护的堆空间。 全局池 系统初始化时,由系统维护的内存池。 进程堆 在进程初始化时,由用户手动指定指定的堆空间。(可留空) 进程栈 在进程初始化时,由用户手动指定指定的栈空间。 全局堆 全局堆中的内存块是尽可能紧密排布的,使用时需要对链表进行逐块搜索,这使得其申请与释放较为复杂。 为了解决这一问题而提出了全局池。 全局池 全局池是一系列提前划分好的内存块,当进程申请时,可以快速的分配这些块给进程使用。 但是,内存块分配的多了会占用大量空间,分配少了会使进程无法获得资源。且其无法根本上解除对内存资源的争抢问题,因为其入口仍然是单一的,于是在此基础上提出了进程堆。 进程堆 进程堆是由该进程独享的堆空间,永远不会出现资源竞争。进程堆可以不分配,有些进程是不需要堆的,因此硬性要求堆的分配是不合理的。但若某个进程有着频繁的空间申请行为时,应该为这个进程分配专有的进程堆。 但要注意的是,进程堆并不是一个静态堆,其本身可以 由 GC 进行管理。 进程栈 额… 应该不用解释了吧。...
YueOS 开发日志 (5) - 内核篇:调度器的具体实现
调度器的具体实现 调度器将是整个系统中最核心的功能。调度器操作的实例对象为任务,向上拓展为进程间同步模块。可以说调度器封装设计的优秀与否将成为影响整个系统性能关键。 整个时间轴由无数个任务片构成,两个重要/次要任务之间的缝隙被调度任务填充。因此必须尽可能减小调度任务的长度。 本系统的核心需求依然是将重要任务之外的时间合理高效利用,并不强调实时性,因此不适用 Round-Robin(RR) 方法。 被调度任务的排序算法 关于任务的排序方法,对于 cortex-M 系列同时运行任务最多也就十余个。此时,对于时间复杂度 O(n) 与 O(log(n)) 无明显差距。因此,不使用 AVL 及红黑树类的排序方法,仅使用其退化的最简单模型 —— 有序链表。 定义:按某种方式排序的任务链表称为任务链。 就绪任务链:按照执行顺序排序的待执行任务。 包含重要任务链(静态调度表)与次要任务链(优先度表)。 延时任务链:按照恢复时间顺序排序的被阻塞任务。 挂起任务链:按照时间顺序排序的被挂起任务链。(其实就是无序的🤐。。。凑个定义好处理,嘿嘿嘿嘿) 调度的排序特点 考虑所有发生当...
YueOS 开发日志 (4) - 内核篇:任务的具体实现
任务的具体实现 任务的数据结构是一切的基础。 任务管理器 调度器可调度的任务都需要先使用任务管理器向内核注册。注册后的任务,任务管理器自身会维护一个链表,该链表保存着全部任务。 任务注册 任务注册时,用户需要使用结构 ‘Task_InitConfig_t’ 提供任务的基础信息。 12345678910111213typedef struct { /* 不允许为空 */ Task_Handle_t entryPoint; // 任务的入口点 Kernal_TaskType_e type; // 任务类型,即前文中的四种,用户只关心重要和次要任务即可 uint8_t priority; // 任务的优先级,被次要任务使用 uint32_t* stackAddr; // 堆栈起始地址(最大栈顶) 栈底需要 8 byte 对齐 uint32_t stackSize; // 单位: byte 推荐 4 的倍数 /* 可选 */ void* argv; // 在入口点传入的参数 const ch...
YueOS 开发日志 (6) - 内核篇:时钟与阻塞
时钟与阻塞 硬件时钟 我们使用的硬件为内核计数器。 SysTick: The RCC feeds the external clock of the Cortex System Timer (SysTick) with the AHB clock (HCLK) divided by 8. The SysTick can work either with this clock or with the Cortex clock (HCLK), configurable in the SysTick control and status register. [STM32F4xx Reference manual(RM0090Rev20)] When enabled, the timer counts down from the value in SYST_CVR. When the counter reaches zero, it reloads the value in SYST_RVR on the next clock edge. It then decrements ...
YueOS 开发日志 (3) - 内核篇:OS API
操作系统函数的调用接口 约定:非特权级称为用户态,特权级称为内核态。且为了安全性保证,系统初始化之后一定是使用 PSP 的用户态。 OS API 的调用 由于种种原因,用户很多时候无法执行 OS API。因此在用户态下试图访问某些系统功能,就需要使用 SVC 来向内核提出申请,并在 SVC_Handler 中实现要求。 嗯,挺好的。但是,理想很丰满,现实很骨感。这里有些细节需要考虑。 如何完成 SVC 到系统具体服务的映射? 如何实现一个统一、易于阅读且简洁优雅的 SVC 封装?(不会有人想挨个手撸汇编吧?写几行性能关键语句就得了) 如何保证 OS API 调用是可靠的?用户在中断中调用 SVC 那不炸了吗? SVC 调用下的 OS API 当发起 SVC 请求时,一共存在 256 个被内核忽略的立即数。简单的方式是为每一个 SVC 服务分配一个立即数,但这略麻烦,我懒。 所以使用指针传递的方式。由 ARM ABI 约定易知,应该使用 R0-R3 完成实参传递且使用 R0 传回返回值,同时使用 R12 传递实调函数。 我们使用 0 号 SVC 服务作为内核调用入口,余下...
YueOS 开发日志 (2) - 内核篇:任务与调度
任务与调度 尽可能梳理成分类讨论了,笔者自己的思考过程耦合性有亿点点高。 任务的分类 任务划分结构可以被嵌套表示为 异常任务(中断任务) 词如其意。在内核 Handler Mode 处理的任务被称为异常任务。 线程任务 与上文类似的,在内核 Thread Mode 处理的任务被称为线程任务。线程任务按重要程度又可划分为 重要任务 次要任务 内核任务 重要程度划分的定义参见前文。 综上,调度策略的分析中一共存在四种任务: 异常任务 重要任务 次要任务 内核任务 后三者被合称为线程任务。 上下文切换 从逻辑上看,在某一时刻时内核处理的任务发生了改变的动作被称为任务的上下文切换。 从动作上看,在某一时刻时内核的堆栈指针被手动修改称为任务的上下文切换。 在任一时刻,可能发生的上下文切换无非以下两种情况 主动切换 即当前任务主动触发上下文切换。 被动切换 即当前任务因操作系统内核/处理器内核调度而被动发生上下文切换。 调度策略 由顶向下划出大纲后,当然是自底向上具体分析。 约定 0: 在宏观上来看,所有需要执行的任务一定都是可以在其超时...
