Generally, we often use embedded database to realize data management in embedded system. However, the commonly used embedded databases (such as SQLite, Berkeley DB, etc.) need the support of the embedded operating system, and have high requirements for the memory and CPU processing speed of the embedded system. They can only be used in high-end embedded systems. In the low-end embedded system, the traditional data management method is to number the data storage space in order, and the data storage and deletion are operated according to the numbering order. This method will cause a lot of storage space fragments after multiple deletion. On the one hand, it increases the difficulty of finding free storage space for the program, and the data management operation time is long (similar to the case that the hard disk in the microcomputer system does not do disk defragmentation for a long time, which will slow down the program operation). On the other hand, it may reduce the utilization of storage space. This paper presents a method of using μ This method does not need the support of embedded operating system, can be applied to low-end embedded systems, and can effectively overcome the defects of traditional data management methods in low-end embedded applications.

one μ C / OS task scheduling algorithm

μ C / OS is a preemptive multitask embedded operating system, which can manage up to 64 tasks. μ In C / OS, the priority of each task is different and unique. Once the task with the highest priority is ready, it has CPU ownership and starts running. So, μ The basic idea of C / OS task scheduling algorithm is to find the highest priority task currently ready and switch tasks. The implementation of the above task scheduling algorithm mainly includes two steps: determining which tasks are in the ready state and which task has the highest priority. To this end, μ C / OS provides two global variables osrdytbl [] and osrdygrp. Osrdytbl [] array is a task ready table, which contains 8 bytes (64 bits in total), which is equivalent to dividing 64 tasks into 8 groups with 8 tasks in each group. The 0 and 1 states of the 64 bit data represent whether the 64 tasks are ready (0 represents idle and 1 represents ready); Osrdygrp is 1 byte data (8 bits). The 0 and 1 states of each bit respectively represent whether the corresponding byte of osrdytbl [] array is non-zero (i.e. whether there are tasks in the group in ready state). Through the assignment of these two global variables, the task ready state and idle state can be switched, which is μ C / OS is the basis of task scheduling.

1.1 make the task ready

μ The C / OS makes the corresponding task enter the ready state through a position “1” of osrdytbl [] and osrdygrp, as shown in Figure 1.

be based on μ Design of embedded data management in C / OS embedded operating system

Figure 1 task readiness table

Assuming that the task with priority 12 enters the ready state, 12 = 1100B, then the fourth position 1 of osrdytbl [1] and the first position 1 of osrdygrp (representing the first group of tasks in the ready state), the corresponding mathematical expression is:

OSRdyGrp|=0x02;

OSRdyTbl[1]|=0x10;

be μ When C / OS performs task scheduling, it can be judged by the value of osrdygrp that a task in the first group of tasks is in the ready state, and then it can be judged by the first byte of osrdytbl [] array that the task with priority 12 is in the ready state, so task switching can be done.

From the above calculation, it can be obtained that if the nth position of osrdygrp and osrdytbl [] is 1, the values of osrdygrp and osrdytbl [] should be combined with 2n. For the convenience of calculation, μ In C / OS, the 8 values of 2n (n = 0 ~ 7) are calculated first and stored in the array osmaptbl [], that is:

OSMapTbl[0]=20=0x01(0000 0001)

OSMapTbl[1]=21=0x02(0000 0010)

……

OSMapTbl[7] = 27=0x80(1000 0000)

μ In C / OS, the priority level is divided into high 3 bits and low 3 bits. The high 3 bits represent the task group number and the low 3 bits represent the position of the task in the group. Then any task with priority of prio enters the ready state, and only the following procedures need to be executed:

OSRdyGrp|=OSMapTbl[prio 》 3];

OSRdyTbl[prio》3]|=OSMapTbl[prio & 0x07];

1.2 make the task idle

μ C / OS clears the corresponding bit in the task readiness table osrdytbl [prio “3] (prio represents task priority) to make the corresponding task enter the idle state. When all bits in osrdytbl [prio” 3] are zero, it is also necessary to clear the corresponding bit of osrdygrp to represent that no task in the whole group enters the ready state.

1.3 find the highest priority task currently in ready status

μ C / OS uses the look-up table method to find the highest priority task in the ready state. It pre defines the array osunmaptbl [] as the look-up table, as follows:

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

};

The corresponding search procedure is as follows:

High3=OSUnMapTbl[OSRdyGrp];// The priority is 3 digits higher, that is, the group number of the highest priority task currently in ready status

Low3=OSUnMapTbl[OSRdyTbl[High3]];// 3 lower priority bits

Prio = (hign3) + low3; / / obtain the task with the highest priority in the ready status

For example, if the value of osrdygrp is 01101000b, it can be found that the value of osunmaptbl [osrdygrp] is 3, which corresponds to the third position 1 in osrdygrp (that is, the highest priority task currently in ready status is in the first group of tasks); If the value of osrdytbl [3] is 11100100b, check that the value of osunmaptbl [osrdytbl [3] is 2, and the priority of the highest task entering the ready state is prio = 3 × 8+2=26。

As can be seen from the above calculation μ The time * for C / OS to find the current highest priority task is a constant, which is independent of the number of tasks established in the application. This feature is the key to realize the new embedded data management in this paper.

2 utilization μ Implementation of embedded C / OS task scheduling algorithm

Data management in low-end embedded applications, the main function of data management is data storage and data deletion. The traditional method is to number the data storage space according to the address sequence. The data storage and deletion are operated according to the number. Each numbered storage space also provides a flag bit to judge whether the space has been occupied. This method has a big disadvantage: after multiple deletions, there will be storage space fragments, which makes it time-consuming to find free space in subsequent operations, and the larger the storage, the more serious this phenomenon is, which greatly reduces the efficiency of data management operations. In order to solve this problem, some programmers only provide the function of deleting all records, not a single record, but this obviously sacrifices the ease of use of the product. This paper uses μ C / OS task scheduling algorithm realizes embedded data management, which can effectively solve the above problems.

2.1 basic ideas

utilize μ The basic idea of embedded data management based on C / OS task scheduling algorithm is μ The “task priority” in C / OS corresponds to the “record number” of data management, the “task ready state” corresponds to the “storage space empty state” (note that it is not the storage space full state), the “task idle state” corresponds to the “storage space full state”, the “make task ready state” corresponds to the “data deletion”, and the “make task idle state” corresponds to “Data storage” corresponds to “find the highest priority task currently in ready status” and “find the current free storage space”. That is, in practical application, before data storage, according to μ The method of “find the highest priority task currently in ready status” in C / OS finds the free storage space with the highest priority, obtains the corresponding record number, and then stores the data according to the μ The method of “make the task enter idle state” in C / OS makes the storage space of corresponding records set to “full” state; after data deletion, according to μ The method of “putting tasks into ready state” in C / OS makes the storage space of corresponding records set to “empty” state. Obviously, this method has two advantages over traditional methods: the speed of finding free storage space is much higher than traditional methods, and the search time is constant, that is, the search time is independent of the number of records (the search time of traditional methods increases with the number of records) ; there will be no storage space fragments, because this method stores data according to priority. The priority of deleted storage space must be higher than that of unused storage space, so it will be used for storage in priority in subsequent storage operations, so as to avoid the occurrence of storage space fragments.

2.2 algorithm improvement

μ The maximum number of tasks in C / OS is 64, which means direct adoption μ The maximum number of records of data management realized by C / OS task scheduling algorithm is only 64, which is obviously not suitable for most applications, so the algorithm needs to be improved. This method introduces the concept of “page”, that is, every 64 records is 1 page. Before data storage, first find the page number containing empty records, and then find empty records in this page. The method of finding the page number containing empty records is the same as that of finding empty records (that is, both are based on μ The method of “find the highest priority task currently in ready status” in C / OS, so the maximum number of records is 64 records / page × 64 pages = 4096 records. And so on, you can continue to expand the number of stored records. For ease of understanding, the following global variables representing the idle state and the record number in the page are defined as osrdytbl [64] [8], osrdygrp [64] and prio, the global variables representing the page idle state and page number are defined as osrdypage, osrdypagetbl [8] and priopage, and the serial number representing the record in the whole storage space is defined as recordno (then recordno = priopage) × 64+prio)。

2.3 implementation of main steps of embedded data management

2.3.1 data initialization

When the embedded system is just running, all records should be empty. Therefore, all bytes of the global variables osrdytbl [], osrdygrp, osrdypagetbl [], and osrdypage representing the record idle state and page idle state should be initialized to 0xff (because “1” represents idle).

2.3.2 data storage

Before data storage, first find the empty record with the highest priority. The process is to find the page number containing empty records, then find the empty record number in the page, and finally calculate the serial number of the storage space currently available for storage and with the highest priority according to the page number and empty record number. The detailed procedures are as follows:

High3=OSUnMapTbl[OSRdyPageGrp];// High 3 bits

Low3=OSUnMapTbl[OSRdyPageTbl][High3]];// Lower 3 bits

Priopage = (high3) + low3; / / find the page number of the empty record first

High3=OSUnMapTbl[OSRdyGrp[PrioPage]];

Low3=OSUnMapTbl[OSRdyTbl[PrioPage][High3]];

Prio = (high3) + low3; / / obtain the empty record number in the page

RecordNo=PrioPage*64+prio;// Get the sequence number of the empty record in the whole storage space

Leave a Reply

Your email address will not be published. Required fields are marked *