摘要: 利用μC/OS嵌入式操作系统的任务调度算法，巧妙地实现了简易的嵌入式数据管理。首先详细描述了μC/OS任务调度算法的原理，在此基础上提出了利用该算法实现嵌入式数据管理的基本思想，最后根据实际应用需要，对该算法进行改进并给出数据管理关键流程的详细实现方法。该方法有效解决了传统方法存在的存储空间碎片问题，且实现简单，可广泛应用于低端嵌入式应用中的数据管理。
引言
随着嵌入式系统的飞速发展，如何在嵌入式系统中实现数据管理也越来越引人关注，常用的方法是采用嵌入式数据库。但是目前常用的嵌入式数据库（如SQLite、Berkeley DB等）均需嵌入式操作系统的支持，且对嵌入式系统的内存、CPU处理速度等有较高要求，只能应用在比较高端的嵌入式系统中[12]。在低端的嵌入式系统中，传统的数据管理方法是对数据存储空间按顺序编号，数据存储与删除均根据编号顺序操作。这种方法在多次删除后会出现很多存储空间碎片，一方面加大了程序查找空闲存储空间的难度，数据管理操作时间长（类似微机系统中硬盘长时间不做磁盘碎片整理会造成程序运行变慢的情况），另一方面可能造成存储空间利用率降低。本文提出了一种利用μC/OS任务调度算法实现的数据管理方法，该方法实现简单，无需嵌入式操作系统的支持，可应用于低端的嵌入式系统中，而且可以有效克服低端嵌入式应用中传统数据管理方法的缺陷。
1 μC/OS任务调度算法
μC/OS是一种占先式的多任务嵌入式操作系统，它可以管理多达64个任务[3]。μC/OS中，每个任务的优先级不一样且是唯一的，优先级最高的任务一旦准备就绪，则拥有CPU所有权并开始投入运行[3]。所以，μC/OS的任务调度算法的基本思想就是，查找当前准备就绪的最高优先级的任务，并进行任务切换。实现上述任务调度算法主要包含两个步骤：确定目前哪几个任务处于就绪态，确定目前处于就绪态的任务中哪个优先级最高。为此，μC/OS提供了两个全局变量OSRdyTbl[]和OSRdyGrp。OSRdyTbl[]数组是任务就绪表，包含 8个字节（共64位），相当于把64个任务分为8组，每组8个任务，这64位数据的0、1状态分别代表64个任务是否处于就绪态（0代表空闲，1代表就绪）；OSRdyGrp为1个字节数据（8位），每一位的0、1状态分别代表OSRdyTbl[]数组的相应字节是否非零（即该组中是否有任务处于就绪态）。通过这两个全局变量的赋值就可实现任务就绪态与空闲态的切换，这是μC/OS实现任务调度的基础[4]。
1.1 使任务进入就绪态
μC/OS通过OSRdyTbl[]和OSRdyGrp某位置“1”，使相应任务进入就绪态，如图1所示[3]。
图1 任务就绪表
假设优先级为12的任务进入就绪状态，12 = 1100b,则OSRdyTbl[1]的第4位置1，且OSRdyGrp的第1位置1（代表第1组有任务处于就绪态），相应的数学表达式为:
OSRdyGrp|=0x02；
OSRdyTbl[1]|=0x10；
则μC/OS在执行任务调度时，通过OSRdyGrp的值即可判断出第1组任务中有任务处于就绪态，然后再通过OSRdyTbl[]数组的第1个字节即可判断出此时优先级为12的任务处于就绪态，则可做任务切换。
从上面的计算可以得到:若OSRdyGrp及OSRdyTbl[]的第n位置1，则应该把OSRdyGrp及OSRdyTbl[]的值与2n相或。为了计算方便，μC/OS中把2n的8个值(n=0~7)先计算好，存在数组OSMapTbl[]中，即：
OSMapTbl[0]=20=0x01（0000 0001）
OSMapTbl[1]=21=0x02（0000 0010）
……
OSMapTbl[7] = 27=0x80（1000 0000）
μC/OS中，优先级数分解为高3位和低3位，高3位代表任务组号，低3位代表任务在所在组中的位置。则任意优先级为prio的任务进入就绪态只需执行以下程序[3]：
OSRdyGrp|=OSMapTbl[prio >> 3];
OSRdyTbl[prio>>3]|=OSMapTbl[prio & 0x07];
1.2 使任务进入空闲态
μC/OS通过任务就绪表OSRdyTbl[prio>>3]（prio代表任务优先级）中相应位清零使相应任务进入空闲态，当OSRdyTbl[prio>>3]中的所有位都为零时，还需将OSRdyGrp的相应位清零，代表全组任务中没有一个任务进入就绪态。
1.3 查找当前处于就绪态的最高优先级任务
μC/OS采用查表法查找当前处于就绪态的最高优先级任务，它预先定义了数组OSUnMapTbl[]作为查找表，如下：
INT8U const OSUnMapTbl[]={
0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
}；
相应的查找程序如下：
High3=OSUnMapTbl[OSRdyGrp];//优先级高3位，即当前处于就绪态的最高优先级的任务的组号
Low3=OSUnMapTbl[OSRdyTbl[High3]];//优先级低3位
prio=(Hign3<<3)+Low3;//获得当前处于就绪态的最高优先级的任务
例如：若OSRdyGrp的值为01101000b，则查得OSUnMapTbl[OSRdyGrp]的值是3，它对应于OSRdyGrp中的第3位置1（即当前处于就绪态的最高优先级任务处于第1组任务中）；若OSRdyTbl[3]的值是11100100b，则查OSUnMapTbl[OSRdyTbl[3]]的值是2，则进入就绪态的最高任务的优先级prio=3×8+2=26。
从上文的计算可看出μC/OS查找当前最高优先级任务所花的时间为常数，与应用程序中建立的任务数无关，这个特性是本文实现新型嵌入式数据管理的关键。
2 利用μC/OS任务调度算法实现嵌入式
数据管理在低端的嵌入式应用中，数据管理的主要功能就是数据存储与数据删除。传统的做法是对数据存储空间按地址顺序编号，数据存储与删除均根据编号操作，每个编号的存储空间还提供了标志位，用于判断该空间是否已被占用。这种方法有一个很大的弊端：多次删除后会出现存储空间碎片，这造成后续操作中查找空闲空间耗时较长，且存储量越大，这个现象越严重，大大降低了数据管理操作的效率。有些程序员为了解决这个弊端对删除操作只提供删除所有记录的功能，不提供单独删除某个记录的功能，但这显然牺牲了产品的易用性。本文利用μC/OS任务调度算法实现嵌入式数据管理，可有效解决以上问题。
2.1 基本思想
利用μC/OS任务调度算法实现嵌入式数据管理的基本思想是：将μC/OS中的“任务优先级”与数据管理的“记录号”对应，将“任务就绪态”与“存储空间空状态”（注意，不是存储空间满状态）对应，将“任务空闲态”与“存储空间满状态”对应，将“使任务进入就绪态”与“数据删除”对应，将“使任务进入空闲态”与“数据存储”对应，将“查找当前处于就绪态的最高优先级任务”与“查找当前空闲存储空间”对应。即在实际应用中，数据存储前先根据μC/OS中的“查找当前处于就绪态的最高优先级任务”的方法查找目前优先级最高的空闲存储空间，获得相应记录号，然后在数据存储后根据μC/OS中的“使任务进入空闲态”的方法使相应记录的存储空间置为“满”状态；数据删除后根据μC/OS中的“使任务进入就绪态”的方法使相应记录的存储空间置为“空”状态。显然，该方法较传统方法有两大优点：查找空闲存储空间的速度远高于传统方法，且查找时间为常数，即查找时间与记录数无关（传统方法的查找时间随记录数递增）；不会出现存储空间碎片，因为本方法按优先级存储数据，删除的存储空间的优先级肯定高于未使用的存储空间，则在后续存储操作中会将其优先用于存储，从而也就避免了存储空间碎片的出现。
2.2 算法的改进
μC/OS的最大任务数为64，这意味着直接采用μC/OS任务调度算法实现的数据管理的最大记录数也仅为64个，这显然不适用于多数应用场合，因此需对算法进行改进。本方法引入“页”的概念，即每64个记录为1页，数据存储前先查找包含空记录的页号，然后在该页中查找空记录。查找包含空记录的页号的方法与查找空记录的方法相同（即都根据μC/OS中的“查找当前处于就绪态的最高优先级任务”的方法查找），因此最大记录数为64记录/页×64页=4096个记录。依此类推，可继续扩大存储记录数。为了理解方便，下文代表记录空闲状态和页内记录号的全局变量定义为OSRdyTbl[64][8]、OSRdyGrp[64]和prio，代表页空闲状态和页号的全局变量定义为OSRdyPage、OSRdyPageTbl[8]和PrioPage，代表记录在整个存储空间的序号定义为RecordNo（则RecordNo = PrioPage×64+prio）。
2.3 嵌入式数据管理主要步骤的实现
2.3.1 数据初始化
在嵌入式系统刚运行时，所有记录应为空状态，因此需将代表记录空闲状态和页空闲状态的全局变量OSRdyTbl[]、OSRdyGrp、OSRdyPageTbl[]和OSRdyPage的所有字节均初始化为0xff（因为“1”代表空闲）。
2.3.2 数据存储
数据存储前先要找到优先级最高的空记录，其流程为先找到含空记录的页号，然后在该页中查找空记录号，最后根据页号和空记录号计算出当前可用于存储且优先级最高的存储空间的序号。详细程序如下：
High3=OSUnMapTbl[OSRdyPageGrp];//高3位
Low3=OSUnMapTbl[OSRdyPageTbl][High3]];//低3位
PrioPage=(High3<<3)+Low3;//先找到含空记录的页号
High3=OSUnMapTbl[OSRdyGrp[PrioPage]];
Low3=OSUnMapTbl[OSRdyTbl[PrioPage][High3]];
prio=(High3<<3)+Low3;//获得页中的空记录号
RecordNo=PrioPage*64+prio;//获得空记录在整个存储空间中的序号
根据以上程序得到序号后，就可以将数据存储到相应存储空间了，存储完成后需将该序号的存储空间设置为“满”状态，具体流程为：先将该页中的记录号置为“满”状态（即清零相应位），然后判断本页中是否所有记录均为“满”，若是则置该页的状态为“满”。详细程序如下：
PrioPage=RecordNo / 64;//页号
prio=RecordNo % 64;//记录号
if ((OSRdyTbl[PrioPage][prio>>3] &=~OSMapTbl[prio & 0x07])==0)
OSRdyGrp[PrioPage] &=~OSMapTbl[prio>>3]; //置页中的记录号为“满”状态
if(OSRdyGrp[PrioPage]==0){//若该页中的所有记录均为“满”则置该页为“满”状态
if ((OSRdyPageTbl[PrioPage>>3] &=~OSMapTbl[PrioPage & 0x07])==0)
OSRdyPage &= ~OSMapTbl[PrioPage>>3];
}
2.3.3 数据删除
数据删除即将存储序号RecordNo对应的页号和记录号的存储状态设置为“空”（则该记录可用于后续的存储），具体流程为：先设置页号为“空”（因为只要该页中任意一个记录为“空”，则页的状态即为“空”），然后设置记录号的状态为“空”，详细程序如下：
PrioPage=RecordNo / 64;//页号
prio=RecordNo % 64;//记录号
OSRdyPage |=OSMapTbl[PrioPage>>3];
OSRdyPageTbl[PrioPage>>3] |=OSMapTbl[PrioPage & 0x07];//设置该页的存储状态为“空”
OSRdyGrp[PrioPage] |=OSMapTbl[prio>>3];
OSRdyTbl[PrioPage][prio>>3] |=OSMapTbl[prio & 0x07];)//设置页中的记录为“空”状态
按以上方法将相应序号的存储空间设置为空状态，则在后续操作中该存储空间可用于存储。
结语
本文利用μC/OS嵌入式操作系统的任务调度 算法并加以改进，巧妙地实现了简易的嵌入式数据管理，与传统方法比较，该方法具备不出现存储空间碎片、数据管理操作效率高等优点，可广泛应用于低端嵌入式应用中的数据管理。该方法已在笔者所开发的SF6电气设备分解产物检测仪及智能抄表终端中应用，运行稳定可靠。
参考文献
[1] 曹艳芸.嵌入式数据库发展状况研究[J].电子产品世界,2010，17(3):1618.
[2] 曹剑青,雷振中.对嵌入式数据库的系统设计及实现[J].中国科技纵横,2010(11).
[3] Labrosse Jean J.嵌入式实时操作系统μC/OSII[M].邵贝贝，等译.北京:北京航空航天大学出版社,2003.
[4] 任哲,潘树林,房红征.嵌入式操作系统基础μC/OSII和Linux[M].北京:北京航空航天大学出版社,2006.
徐艺文(博士研究生、讲师)，主要研究方向为嵌入式系统及其应用。
作者：徐艺文 魏云龙 来源：《单片机与嵌入式系统应用》
