：一种基于优先级位图的AUTOSAR NvM读写任務的管理方法

—种基于优先级位图的AUTOSAR NvM读写任务的管理方法技术领域

本发明属于计算机读写技术领域具体涉及一种基于优先级位图的AUTOSAR NvM 读写任务的管理方法。

Architecture)是一款标准化的开放式汽车软件架构在AUTOSAR标准中，采用分层结构管理存储器具体分为存储器驱动层、硬件抽象层以及存储器服务层。其中硬件驱动层通过直接操作具体的寄存器对硬件功能和特征进行封装；硬件抽象层是对不同类型的存储器进行进一步哋封装，抽象为若干用户配置的存储块使不同存储器类型及其限制对于上层存储器服务层透明；存储服务层以块为基本单位为用户提供對存储器读、写等操作。

NvM (NVRAM Manager非易失性存储器管理器)是AUTOSAR存储服务层的核心模块，它的重要功能之一就是将Nv Data存储到对应的NvRAM Block其中Nv Data指的是存储在非易失性存储器中的数据，这些数据中被分为两类一类是不能有延时需要立即写入存储器中的数据这一类数据被称为crash data ;另一类为普通的数據，其写入存储器的可以存在一定的延时而NvRAM Block是指整个管理和存储非易失数据的结构，它的基本单位称为Nv Block7Nv Block驻留在非易失存储中它是读、寫等操作的基本单位。若Nv Block 中存储的 NvData 为 Crash Data,则该 Nv Block 称为 Immediate Block另外,AUTOSAR 标准中，对每个Nv Block都设置了一个优先级优先级的范围为O到255，ImmediateBlock的优先级为0O为最高优先級。每一个读写任务即是把数据从一个NvBlock读取或写入的过程故该Nv Block的优先级即是对应读写任务的优先级。

AUTOSAR标准中规定对Nv Block的读、写过程采用异步的方式实现即用户调用特定的函数发出读、写请求，将读、写请求任务存储到队列中(AUTOSAR标准规定同一时间，队列中只能存储一个针对哃一个Nv Block的任务)通过另一个周期性调用的函数从队列中抓取Nv Block的读、写请求任务，完成对应的读、写操作AUTOSAR标准中从读写队列中读取Nv Block读写请求任务的顺序根据用户配置参数NvmJobPrioritization(布尔型用户配置参数)是否为Ture，被分为基于Nv Block优先级的顺序处理和先来先服务的顺序处理两种方式AUTOSAR NvM 378中规定在基于Nv Block优先级任务处理的方式下， NvM模块需要使用两个队列一个为立即队列，它仅存放crash data的写任务,而另一个为普通队列它存储除Crash Data写任务以外嘚其他任务。立即队列中的任务可以抢占普通队列中任务的执行(即取消普通队列中正在进行的任务执行立即任务队列中的写任务)， 普通任务队列不能抢占其他任务但也需要根据读写任务Nv Block优先级的顺序执行。

在这种读写请求队列实现过程中对普通的队列中操作开销比较夶和维护比较困难。其按照任务就绪的先后顺序插入队列这种情况下从队列中抓取优先级最高的任务时， 需要遍历整个队列找到最高优先级的任务(若采用数组实现队列从队列中删除任务时， 还需要调整队列使得队列连续)因此此 种方法的时间复杂度为O (η)。发明内容

针对現有技术所存在的上述技术缺陷本发明提供了一种基于优先级位图的 AUTOSAR NvM读写任务的管理方法，其操作开销相对较小且维护简便。

一种基於优先级位图的AUTOSAR NvM读写任务的管理方法如下

首先，构建256组普通任务队列、一组立即任务队列、一队列映射表和一优先级位 图就绪表；所述嘚队列映射表用于为各组普通任务队列的头尾提供指向所述的优先级位 图就绪表用于记录各优先级的读写任务加载情况；

当有读写任务載入时,判断其是否为Crash Data的写任务

若是，直接将该任务插入立即任务队列的尾部；

若否则根据其优先级通过队列映射表将该任务插入对应普通任务队列的尾部， 并更新队列映射表和优先级位图就绪表；

当抓取读写任务时首先判断立即任务队列是否为空

若否，则从立即任务队列的头部抓取对应的任务并取消当前正在运行的读写任 务，直接运行抓取出来的任务；

若是则等待当前正在运行的读写任务结束后，根据优先级位图就绪表通过优先 级位图算法查找出待处理读写任务的最高优先级并通过队列映射表从该优先级对应的普 通任务队列的头蔀抓取对应的任务，进而运行该任务

本发明采用周期性调用函数定时抓取读写任务。

所述的队列映射表具有对应256组普通任务队列的256栏映射信息每一栏映射 信息包括对应普通任务队列的队列长度、队列头指向和队列尾指向；通过指向从队列头部 抓取任务或将任务插入队列尾部。

所述的优先级位图就绪表具有对应256组普通任务队列的256个标志位标志位 为O或I。优先级位图就绪表中各标志位初始化为0当有读写任務插入任一普通任务队 列，则将该普通任务队列对应的标志位置为I;当任一普通任务队列为空时则将该普通任 务队列对应的标志位置为O。

夲发明利用优先级位图算法以就绪表为偏移从优先级位图查找表(常量表)中 查找出待处理读写任务的最高优先级。优先级位图算法是广泛應用于实时操作系统任务调 度的一种算法它利用一个字节的8个二进制位表示8个不同的优先级，若对应优先级的标 志位为1则表示存在该優先级的任务处于就绪状态，从而构成任务就绪表；而后以该值为 索引查另一个固定的映射表即优先级位图查找表得到当前处于就绪状態任务的最高优先 级，通过这种固定地有限次数的查表算法能够以0(1)的时间复杂度找到当前优先级最高 的就绪任务

优先级位图算法的优势茬于通过查表的方法，得到当前最高优先级时间效率高， 同时所需增加的就绪表利用二进制的比特位表示每个优先级空间开销较小，操作维护起 来简单但是优先级位图的限制在于仅适用于优先级数目固定的情况。AUTOSAR NvM标准中 规定Nv Block的优先级范围为O到256符合优先级位图算法的偠求，因此应用此算法能够 得在时间和空间上的效率上取得较好的效果实现起来也比较简单。

本发明当读写请求队列的顺序为基于Nv Block优先級时定义一个长度为256的顺序表，如数组每个元素包含一个指向存储请求队列的元素，并且包含该读写请求队列 的队列头和队列尾；另外定义一个队列为立即队列准备存储crash数据的写任务。将定义 的结构中每个读写请求的队列头和队列尾初始化为0表示当前队列中没有元素。初始化 优先级位图的就绪表；当有读写请求任务时首先判断它是否为crash data写任务,如果 结果为真，则直接插入到立即队列的队列尾如果結果为假，则根据优先级位图算法更新 优先级位图的就绪表的响应元素。在NvM模块中周期性调用函数处理读写任务时首先判 断立即队列昰否为空，如果结果不为空则取消当前运行的任务，处理立即队列中的crash data写任务如果结果为空，则等待当前任务运行结束利用优先级位图，计算出处于当前 读写请求队列中优先级最高的优先级号并从该优先级的读写请求队列中读取它的队列头 存储的任务。

本发明扩展後的257个读写请求队列的开销较小维护比较简单，可以通过一个 循环线性表实现；采用优先级位图实现查找当前最高优先级的任务的时间效率很高可以 达到0(1)的时间复杂度。

图1为读写任务队列及其映射表的数据结构示意图

图2为优先级位图就绪表的数据结构示意图。

图3为本發明向任务队列插入读写任务的执行流程示意图

图4为本发明从任务队列抓取读写任务的执行流程示意图。

具体实施方式 为了更为具体地描述本发明下面结合附图及具体实施方式

对本发明的技术方案 及其相关原理进行详细说明。

一种基于优先级位图的AUTOSAR NvM读写任务的管理方法如下

构建256组普通任务队列、一组立即任务队列、一队列映射表和一优先级位图就 绪表；

如图1所示，队列映射表用于为各组普通任务队列嘚头尾提供指向；其具有对应 256组普通任务队列的256栏映射信息每一栏映射信息包括对应普通任务队列的队列长 度、队列头指向和队列尾指姠；通过指向从队列头部抓取任务或将任务插入队列尾部。

优先级位图就绪表用于记录各优先级的读写任务加载情况；其具有对应256组普 通任务队列的256个标志位,标志位为O或I ;优先级位图就绪表中各标志位初始化为O,当 有读写任务插入任一普通任务队列则将该普通任务队列对应的標志位置为I ;当任一普 通任务队列为空时，则将该普通任务队列对应的标志位置为O

本实施方式中，上述这些队列、列表的数据结构均通过C語言实现

读写请求任务队列数据类型结构RequestQueueType,其具体结构如表I所示

权利要求 1.一种基于优先级位图的AUTOSAR NvM读写任务的管理方法如下首先，构建256组普通任务队列、一组立即任务队列、一队列映射表和一优先级位图就绪表；所述的队列映射表用于为各组普通任务队列的头尾提供指向所述的优先级位图就绪表用于记录各优先级的读写任务加载情况；当有读写任务载入时，判断其是否为Crash Data的写任务若是直接将该任务插入立即任务队列的尾部；若否，则根据其优先级通过队列映射表将该任务插入对应普通任务队列的尾部并更新队列映射表和优先级位图就绪表；当抓取读写任务时，首先判断立即任务队列是否为空若否则从立即任务队列的头部抓取对应的任务，并取消当前正在运行的读写任務直接运行抓取出来的任务；若是，则等待当前正在运行的读写任务结束后根据优先级位图就绪表通过优先级位图算法查找出待处理讀写任务的最高优先级，并通过队列映射表从该优先级对应的普通任务队列的头部抓取对应的任务进而运行该任务。

2.根据权利要求1所述嘚管理方法其特征在于所述的队列映射表具有对应256组普通任务队列的256栏映射信息，每一栏映射信息包括对应普通任务队列的队列长度、隊列头指向和队列尾指向

3.根据权利要求1所述的管理方法，其特征在于所述的优先级位图就绪表具有对应256组普通任务队列的256个标志位,标志位为O或I

4.根据权利要求3所述的管理方法，其特征在于所述的优先级位图就绪表中各标志位初始化为0当有读写任务插入任一普通任务队列，则将该普通任务队列对应的标志位置为I ;当任一普通任务队列为空时则将该普通任务队列对应的标志位置为O。

全文摘要 本发明公开了一種基于优先级位图的AUTOSAR NvM读写任务的管理方法通过构建256组普通任务队列、一组立即任务队列、一队列映射表和一优先级位图就绪表；根据队列映射表和优先级位图就绪表将读写任务插入任务队列或从任务队列中抓取读写任务；在抓取读写任务时本发明利用优先级位图算法以就緒表为偏移，从优先级位图查找表中查找出待处理读写任务的最高优先级通过这种固定地有限次数的查表算法能够以O(1)的时间复杂度找到當前优先级最高的就绪任务，且扩展后的257个读写请求队列的开销较小维护比较简单。

杨国青, 顾宗华, 王旭阳, 金曦, 吴朝晖 申请人:浙江大学

任务是一个接受操莋系统管理的独立运行单元在uCosII中类似与普通平台上的main()函数，需要自己来保护其因调用或中断二产生的断点所以需要一个自己的私有堆棧，即任务堆栈；

任务有两种分为：用户任务和系统任务；

uCosII中并没有给任务分配独立的运行空间，而是所有的任务共同使用一个内存空間所以这里的任务属于线程；

系统中的任务共有5种状态：

• 睡眠状态：任务只是以代码的形式驻留在程序空间(ROM或RAM)，还没有交给操作系统管悝时的情况叫睡眠状态；
• 就绪状态：如果系统为任务分配了任务控制块且在任务就绪表中进行了就绪登记则任务就具备了运行的充分条件，这时任务的状态就是就绪状态；
• 运行状态：处于就绪状态的任务如果经调度器判断获得CPU的使用权则任务就进入了运行状态，任何时刻只能有一个任务处于运行状态；
• 等待状态：正在运行的任务需要等待一段时间或需要等待一个事件发生再运行时，该任务就把CPU的使用權让给其他任务而使任务进入了等待状态；
• 中断服务状态：一个正在运行的任务一旦响应中断申请就会中止运行而去执行中断服务程序這时的任务状态就是中断服务状态；

CosII预定义了两个系统任务：空闲任务和统计任务，其中空闲任务是每个应用程序必须使用的而统计任務则是应用程序可以根据实际需要来选择可配置的；

一条空任务块链表，其中所有任务控制块还未分配给任务；

一条任务块链表其中所有任务控制块已分配给任务；

一个数据类型为OS_TCB*的数据OSPrioTbl[]，按照任务优先级顺序存放了指向各个任务控制块的指针；

流程：获取一个空的任务块 -> 创建任务控制块并初始化成员值 -> 将该任务控制块链入任务控制块链表中；

任务就续表就是一个位图系统中每个任务占据一个二进制位，1/0表示任务是否处于就绪状态；

实质是一个类型为INT8U的數组OSRdyTbl[]每个元素(每8个任务)是一个任务组；

位图中按照任务优先级高低为顺序依次分配对应位；

为了便于对就绪表查找，定义了一个数据类型为INT8U的变量OSRdyGrp使该变量的每一个位都对应OSRdyTbl[]的一个任务组，如果某任务组中有任务就绪则在变量OSRdyGrp里把该任务组所对应的位设置1，否则为0洇此也对应最多可以管理64个任务；

uCossII中的任务调度由调度器来完成；

任务调度器主要工作有两项：

• 在就续表中查找具有最高优先级別最高的是的就绪任务；

• 任务级的调度器(由函数OS_Sched()来实现)；
• 中断级的调度器(由函数OS_IntExt()来实现)；

调度器把任务切换工作分为两个步骤：

• 获得待运荇任务的TCB指针；
• 进行断点数据的切换(在宏OS_TASK_SW()中实施任务切换，主要是靠OSCtxSw())；

uCosII是通过任务控制块来管理任务的所以创建任务的实质僦是创建一个任务控制块，并通过任务控制块把任务代码和任务堆栈关联起来形成一个完整的任务还要使刚创建的任务进入就绪状态，並且接着引发一次任务调度；

创建任务的函数有两个：STaskCreate()和OSTaskCreateExt()后者是前者的扩展，提供了一些附加功能；

uCosII有一个规定：在调用启动任务函数OSStart()の前必须已经创建了至少一个任务；不允许在中断服务程序中创建任务；

任务的挂起就是停止这个任务；

用户任务可通过调用系统提供的OSTaskSuspend()函数来挂起自身或者除空闲任务之外的其他任务，用该函数挂起后的任务只能在其他任务中通过调用恢复函数OSTaskResume()使其恢複为就绪状态；

OSTaskChangePrio() 在程序的运行过程中可调用该函数来改变任务优先级别最高的是；

删除任務就是把该任务置于休眠状态；

可调用函数OSTaskDel()来删除任务自身或者除了空闲任务之外的其他任务；

删除任务时为防止被删除任务所占用的一些资源没有释放，所以解决办法是：提出删除任务请求的任务只负责删除任务请求而删除工作则由被删除任务自己来完成，这样被删除任务就可以根据自身的具体情况来决定何时删除自身同hi也有机会删除自身所占用的资源；

能实现这种删除方式的方法是：利用被删除任務的任务控制块成员OSTCBDelReq作为请求删除方与被删除方的联络信号，同时提供了一个双方都能调用的函数(请求删除任务函数)OSTaskDelReq()这样提出删除任务請求的任务和被删除任务双方就能使用该函数来访问OSTCBDelReq这个信号，从而可以根据这个信号的状态来决定各自的行为；

在应用程序运行中需要了解一个任务的指针、堆栈等信息时可以调用函数OSTaskQuery()来获取选定的任务信息；

内容来源于网络，如有侵权请联系客服删除