Micro-seizuated multi-tasking real time kernel design ※
Servers: ■ Beijing University of Aeronautics and Astronautics Zheng Yuquan
Abstract: Introduction to the design and implementation of the top-imaging multitasking microconuclear - Microstar in the introduction of event-driven concepts; the new concept of event-based priority is proposed.
Keywords: Event Drive Priority Task Management Message Signal Synchronization
There are many excellent embedded real-time operating systems (RTOS) on the market, but there are not many RTOS kernels in the medium and low-end microcontroller (MCU). Under the high-end machine, powerful embedded real-time operating system is highly functional, and the performance is very likely to decrease significantly when transplanted to the low-end. A very important reason is that most of its functionality is not required for medium and low systems, but it has become a cumbersome of restrictive performance. Compared with the high-end machine, on the one hand, the addressing capacity is limited, the processing speed is slow, and under the same real-time performance requirements, the requirements for the code efficiency of the kernel are more stringent; on the other hand, the medium and low-end machine is completed The task is relatively simple, reducing the functional requirements of the kernel, such as memory management. From the commonality of the embedded system, most cases the user program and the system kernel are closely combined. The runtime memory capacity consumption, the number of tasks, execution time and results can be expected, which can be further reduced to The functional needs of the kernel.
The view of the event is believed that the task should be passively responding to various events that occur in the outside, rather than actively go to "query", and waste processor time. Methods using event-driven programming not only improves operational efficiency, but also reduces the coupling between event processing, making the program process very clear, which can greatly improve the development efficiency.
fully consider the hardware characteristics of the medium and low-end microcontrollers and the demand for embedded system software, introduce the concept of "event-driven", and the author developed a miniature seizure multitasking RTOS kernel - Microstar. Dynamic creation, delete, sleep, hang, and recovery, providing messages, and signals (Signal) communication schemes, perfect timer services and full-featured task synchronization functions libraries. It is limited to the space, focusing on several different design ideas and difficulties.
1 scheduling strategy
1.1 Event-based priority
The scheduling strategy is the key to the real-time performance of the kernel. Good dispatching strategy, it is necessary to reflect the priority differences from the events that the events handled on real-time requirements, but also guarantee certain fairness, avoiding low priority tasks less than executable. Extreme situation. There are two commonly used scheduling strategies: one is the Round Robin scheduling, such as RTX51; the other is the priority scheduling of priority, such as μC / OS.
According to the time of time rotation, it can guarantee fairness, but the difference in priority is to be reflected in the use of the occupancy time of the processor. If each task does not actively discard the execution, the high priority task can get more processor time than the low priority task; but in the embedded system, an event requires real-time processing, and does not mean that the processing needs more Long time, but often requires to respond as soon as possible. Therefore, it is not too good to use the time turbulence.
If the priority of the task is strict, it can greatly enhance the real-time system of the system, but it is fair. If the high priority task is a unwalaled dead cycle, the low priority task is unable to obtain an executive opportunity.
A good way is the combination of the two, that is, the priority of the task can be scheduled, or the time chip to generate new task scheduling, such as VxWorks; but implementation is more complicated, not necessarily suitable for medium and low-grade MCU. To this end, based on the fact that "event-based priority" is proposed. An task often handles multiple events, and each event is the same as the real-time requirements. Under the general RTOS, the priority of the task is determined by the highest real-time requirements in these events. Therefore, high priority tasks are processed when processing events with high real-time requirements, it is entirely possible to hinder the low priority task handle events with certain real-time requirements.
In some cases, the processing of the same event can be divided into foreground processing and background processing: the time required for the front desk processing is short, and the real-time requirements have a long time, and the time is long, and there is not much requirements for real-time .
If the real-time requirements of the real-time, the priority scheduling strategy is dynamically adjusted according to the different requirements of the event processing, according to the pre-rear stage stage of the event processing, the priority scheduling policy can be used to play a real time. Advantages, it can also ensure fairness within a certain limit. In this case, the priority of the task is no longer a constant, but dynamically depending on the event and processing phase being processed, this is the so-called "event-based priority".
1.2 Implementation in MicroStar
The priority of the mission in Microstar is determined by static priority and dynamic priority. Static priority is equivalent to priority in other RTOs; dynamic priority is an event-based priority-by the kernel, the event is dynamically adjusted by the task being processed and waiting for processing. Static priority rating is limited to 0 to 15, and the same task is not allowed to create a static priority. The dynamic priority level is currently only 0 (also known as emergency grade), 1 (also known as normal level). The actual priority level of the task can be calculated by the following formula:
Priority Level = Dynamic Priority Rating × 16 Static Priority Level.
The larger the priority rating, the lower the priority. It can be seen that dynamic priority determines.
How to achieve priority dynamic adjustment? First, briefly introduce four status of mission in macRostar:
Sleep (Dormant) - Task into dormancy due to call sleep functions, hang functions or waiting for kernel synchronization objects;
Waiting - Task into the waiting state due to waiting for a message or signal (do not confuse the "beacon";
Running - The task is using the resource of the processor, called the run state.
These states are implemented with a flag. One state of the 16 static priority corresponding tasks just can be identified with a 16-bit binary number. The sleep state is indicated by Os_SLPState. From the high position, the nth bit is 0 indicates the task of the static priority to N. The waiting state is designed for messages and signals based on "event-driven" concept, with OS_RDYHSTATE and OS_RDYSTATE two 16-bit variables. Only when the nth bit of OS_RDYHSTATE and OS_RDYSTATE is 0, the task of static priority is N is waiting. If the task is in a non-destentive state, it means that the task has been processed or events to process (which can be deemed to handle this "virtual event"), at this time, there is a dynamic priority concept. If the nth bit in OS_RDYHSTATE is 1, the dynamic priority of the task of the static priority is n is urgent; if the OS_RDYHSTATE N bit is 0, the dynamic priority of the task of static priority is N is a normal level. . After the event of real-time processing, the kernel simply puts the status of OS_RDYHSTATE, enhances the dynamic priority of the task; after the current event is processed, if there is no real time requires higher events waiting to be processed, simply use the OS_RDYHSTATE to clear 0 To reduce the dynamic priority of the task. Thereby, the dynamic adjustable of the priority can be achieved. Only when the task is neither in sleep state, the task is scheduled. 2 task management
2.1 Task Control Block
Multi-tasking system uses task control block (TCB) to record the various properties of the task. In these properties, the most important thing is the top address of the task stack stack. When Context Switch, all register status of the task being stopped, the address of the next code must be put into the stack protection, so this attribute is required. If you allow the priority of the task to be modified, the priority attribute is also required. Therefore, simplify the task control block as follows:
Typedef struct {
UINT_16 MSG [2]; / * Message Receive Area * /
INT * SP; / * Stack Stack Top Pointer * /
Uchar priority; / * Static priority * /
Uchar reserved; / * reserved * /
} TCB, * PTCB;
TCB OS_TCBS [User_Task_num 1];
/ * User task number is up to 15 * /
Msg is used to store messages sent to the task, and two 16-bit binary can store 32 messages. SP points to the top of the task stack. Priority Record the static priority of the task. The array OS_TCBS is used to record the information of all the tasks of the system, and the subscript corresponds to the ID number of the task, that is, the control block of the task of the ID number N is OS_TCBS [N].
2.2 Creation of the task
The OS_CREATASK function is used to create a task:
Void Os_CreateTask
TaskProc Task, // Task Function Pointer
Uchar taski, // Task ID number
Uchar priority, // priority
INT * PSTACK, // Task Stack Opened Address
Void * param // entry parameters for task functions
);
TypeDef void (* TaskProc) (Void * param);
When you create a task, the kernel should do the following works: 1 Initialize the task control block; 2 Initialize the task stack, so that the situation when the task is steal; 3 Set the task status as a state. This function is dependent on the processor, and Fig. 1 is a general description.
In the interrupt program, before the high priority task deprived the low priority task, the kernel sets the register state of the breakpoint to the stack protection, which is the register image area. The address of the task exit function OS_EXIT is first in the stack for the task function MyTask, so that the MyTask function is returned to OS_EXIT, thereby implementing the automatic deletion of the task. 2.3 Task Switching
Like task creation, task switching code is related to hardware. On the PC, the code and steps are as follows:
Void Interrupt Os_SCHEDULE () ............ (1)
{
IF (OS_Nlayers) Return;
OS_NLAYERS ; ............ (2)
_Dx = (int) OS_PCURTCB;
/ * OS_PCURTCB point to the control block of the current task * /
* (int *) (_ DX 4) = _sp;
* (int *) (_ dx 6) = _ss; ............ (3)
Os_getreadytask (); ............ (4)
_Dx = (int) OS_PCURTCB;
_SP = * (int *) (_ DX 4);
_Dx = * (int *) (_ DX 6);
_Ss = _dx; ............ (5)
Os_nlayers --- ;? ............ (6)
UNLOCK_INT ();
} .......... (7)
(1) Use the C language Interrupt keyword to enable each register into the stack protection. (2) Lock the scheduler and does not allow reward. (3) Save the current task's stack top address (consisting of stack segment register SS and stack pointer register SP) in OS_PCURTCB-> SP (under the PC, the SP in the TCB is defined as a far pointer type). (4) Select the highest-priority ready task (method is similar to μC / OS) and point OS_PCURTCB to the control block of the new task. (5) The stack register points to the top address of the new task. (6) Unlock the scheduler. (7) Each register out of the stack, restoring the situation when the last interrupted is interrupted.
3 messages and signals
In order to facilitate event-driven programming, Microstar draws on Windows "Message, Event Drive" concept, and expands. In MicroStar, events can not only trigger messages, signals, but also have priority by event triggered, because different events are different on the real-time requirements for processing. The kernel is based on the message, the priority of the signal dynamically adjusts the dynamic priority of the task.
3.1 message
The message is a very friendly communication method. Consider the memory capacity and demand of the medium and low-grade microcontrollers, the message is simplified into a value of 0 to 31. With a fixed bit map storage format, the 32 values are mapped to the MSG domain of the task control block, which greatly reduces the storage space. The MSG domain can be regarded as a 32-bit binary variable, and the first bit is 1, indicating a message having a value I, so the access of the message is simply by simple "," or "operation. The priority of the message is fixed, the greater the value, the lower the priority. In the system range, the message priority is divided into two levels: emergency level (value 0 ~ 15) and normal level (value 16 ~ 31). When there is an emergency message to the task, the kernel will improve the dynamic priority of the task, thereby increasing the real-time performance of the message processing. When the task has no urgent news to process, the kernel reduces its dynamic priority. The core code of sending messages is as follows: / * const uint_16 os_masktable [16] = {0x8000, 0x4000, ....., 0x0008, 0x0004, 0x0002, 0x0001 * /
IF (MSG & 0xF0) {/ * Ordinary Message * /
PTCB-> msg [1] | = os_masktable [msg & 0x0f];
/ * Ordinary grade message exists in MSG [1] * /
OS_RDYSTATE | = OS_MASKTABLE [PTCB-> Priority];
}
Else {/ * Emergency grade message * /
PTCB-> MSG [0] | = os_masktable [msg];
/ * Emergency grade message exists in MSG [0] * /
OS_RDYHSTATE | = OS_MASKTABLE [PTCB-> Priority];
/ * Enhance dynamic priority * /
}
Different from the message queue of the advanced first out (FIFO), the kernel always takes out the highest priority message to hand over the task. Message Receive Function OS_GETMESSAGE design idea is as follows: If there is no urgent message in the message receiving area, the dynamic priority of the task is reduced; if there is a message in the message receiving area, the highest priority message is taken out; if there is no message, the task is turned to Waiting. Considering that sometimes you don't want the task to enter the waiting state, Microstar also provides a non-blocking OS_PEEKMESAGE message reception function.
3.2 Letter
In embedded system programming, the logo is often used to implement communication between the front and back programs or different tasks. MicroStar also provides a similar task-signal-signal (Signal). It avoids the user program to be wasted due to continuous query flag, and supports "with", "or" operation between the signals. Popular, the signal is a sign bit, used to identify an event of an event. Like the news, the signal also has an emergency level and the general level. Unlike the message, the signal is completely created and maintained by the user program, the kernel only helps the user program waiting for the signal to avoid low efficiency logo queries. It is better to use it intuitively, but the execution efficiency is high. It is very simple to achieve, please refer to the source code.
4 timer
The timer has a lot of uses in the embedded system, such as the timing refresh of the LED, the timeout check in serial port communications. Demand for timers is divided into two categories, one is periodic repeat time, such as re-refreshing the LED every 10 ms; the other is only a time time for timing. Timed time is used as a unit of system clock beat (Tick, also translated as a tita). The time interval between the two system timing interrupts is a beat. The timer structure is as follows:
Typedef struct {
UINT_16 ELAPSE; / * Time-long value * /
UINT_16 Backtime; / * Timed time long backup value * /
MSG Timerid; / * Timer ID Number * /
UCHAR TASKID; / * Id * / TimerProc LPTIMERFUNC; / * Timer Call for Timer * /
} Timer, * ptimer;
Timer os_timers [user_timer_num]; / * Up to 16 * /
Periodic timing and one-time timing are distinguished by Timerid. If the timeID is 64, it is time-time; if TimerID is not more than 32, it is periodic timing. Use the OS_TIMERS array to record timer information, indicate the status of the timer with 16-bit OS_TIMERSTATE. If the nth bit of the binary number of OS_TIMERSTATE is 1, then OS_TIMERS [N] is idle available.
The periodic timer, the time, the kernel, the illegal time, the ket, and the TimerID is sent to the task in a message, and the impact on the dynamic priority of the task is the same as normal messages. Therefore, in order to obtain a timer having a good real-time, simply set the TimerID between 0 to 15. Related to one-time timing is a function of sleep functions and limited time waits for synchronization objects. After the task uses these two functions, after entering the sleep state, the kernel returns to the ready state and automatically releases the timer resources. The core code for system timing processing is as follows:
IF (! (- ptimer-> ELAPSE)) {/ * ELAPSE is reduced to zero indication time to * /
IF (ptimer-> lptimerfunc) (* ptimer-> lptimerfunc) (ptimer->
Taskid, Ptimer-> Timerid;
Switch (PTimer-> Timerid & 0xF0) {
Case Sleep_id: / * One-time time * /
OS_SLPSTATE | = Taskmask; / * End sleep * /
OS_TIMERSTATE | = Timermask; / * Release Timer * /
Break;
Case 0x00: / * Send an emergency timer message * /
PTCB-> msg [0] | = os_masktable [ptimer-> timerid];
OS_RDYHSTATE | = OS_MASKTABLE [PTCB-> Priority] ;;
Break;
Case 0x10::: / * Send a normal level timer message * /
PTCB-> msg [1] | = os_masktable [ptimer-> Timerid & 0x0f];
OS_RDYSTATE | = OS_MASKTABLE [PTCB-> Priority] ;;
}
}
5
The premier multitasking, the low priority task can be interrupted by the high priority task. When accessing a shared variable or resource in a regular manner, we will appear. For example, a task calls Printf ("12345") attempts to output "12345" on the output device, but execution is interrupted by high priority tasks; and high priority tasks also call Printf ("67890") attempt to output "67890" The final output result may be "1267890345". This is the task synchronization problem in the multi-task environment.
There are two ways to synchronize, one for user synchronization, does not need to be deal with the kernel, has the advantages of fast speed, but only the code is shorter, the other is the kernel synchronization mode, need to be implemented by the kernel The speed is relatively slow, but it protects the code for execution time.
5.1 User Synchronization Mode
Synchronization under user mode is implemented by critical segment (Critical Section). The key code section refers to such a small code. It must be interrupted by the access to some shared resources when executed, and does not allow code to interrupt to access the resource. The easiest thing is to implement the off / open interrupt, the advantage is that the speed is extremely fast, the disadvantage is to bring the interrupt delay, only the code segment for performing a short period of time. Another simple solution is to achieve the lock / unlock scheduler, that is, the kernel is prohibited during the critical code segment execution task switching. With this method, it will not bring interrupt delay, but it brings a scheduling delay. In Microstar, add 1 to the OS_NLayers to lock the scheduler, minus 1 can be unlocked. However, it is not appropriate to directly use the unlock scheduler to leave the critical code segment. If interrupt occurs in the critical code segment, the higher priority task has occurred. However, since the scheduler is locked, the task switch cannot be performed when the interrupt program exits to enable high priority tasks. So we hope that it is best to unlock once the scheduler will switch to high priority tasks soon. To this end, the minimum bit of variable OS_FLAG is specifically used as a flag, and any system functions that can make the task ready to affect the flag, such as OS_POSTMESSAGE, OS_NITITY. When you exit the critical code segment, you can determine whether you need to schedule task schedules. The code when leaving the critical code segment is as follows: IF ((os_flag & 0x01) && (! (- s_nlayers)) {--OS_SCHEDULE ();}
5.2 kernel synchronization object
If you want to protect the code for longer execution time, you should use the kernel synchronization object to synchronize. Common kernel synchronization objects have events (Event), beacons (Semaphore, also known as semaphore) and mutex. Event objects are used to notify events or operations have been completed, which uses a boolean value to indicate that the event is in a notification or not notified. The beacon object is used to count the resource. It records the current number of resources available. When using 1 to initialize the number of available resources of the beacon object, the beacon object is actually a mutually exclusive object. MicroStar provides two synchronous objects, support query, limited time or unlimited, and wait for operation. The structure of the kernel synchronization object is as follows:
Typedef struct {
UINT_16 Waiter; / * Waiting list * /
Uchar num; / * Number of resources or event status * /
UCHAR TYPE; / * Synchronous Object Type * /
} Object, * pObject, * hobject, * hevent, * hsemaphore;
When a task enters the sleep state due to a synchronization object, its static priority bit is stored in the Waiter domain. If the static priority is the task waiting for a synchronization object, the nth position in the Waiter binary number is lame. When Type is Event_Object, the event object is indicated. At this time, NUM is an event state, 1 means a notification state, 0 indicates that the state is notified; the beacon object is indicated, and the corresponding NUM is the number of available resources.
]
6 Example of use and use
In Microstar, each functional module is separated, so it can be severely reduced. Migrating MicroStar is relatively easy, just rewrite the task creation and scheduling functions related to hardware. Microstar1.0's PC full version code is about 10KB, which is 1.4KB written for 96 single-chip assembly language. Examples of presentation included in this article are compiled under TC2.0, which can be run directly on the PC. The first example launched three user tasks: 1 WatchTask task displays a running table that is 10ms in the center of the screen. 2 KeyTask task reads a keyboard every 200 ms, and press the "Q" key system to exit execution. 3 MicroStar task displays Microstar related information, updates a frame every 1.5s. demo and kernel source code see this magazine website (www.dpj.com.cn).
Conclusion
This paper proposes this concept based on incident, making the task priority arrangement more reasonable. The design and implementation of microtanigna-microStar is introduced. The provision of the two communication methods of messages and signals make it good for event-driven programming. More complete timer services and complete task synchronous functions provide more and more flexible choices to users. Limited functions reduce the time spent on the technology to master compared to other real-time operating systems. Plus lower memory consumption, generally, Microstar is more suitable for running on medium and low-end MCU platforms.
1 [United States] Jeffrey Ricter. Windows Core Programming. Wang Jianhua and other translations. Beijing: Machinery Industry Press, 2000
2 TANENBAUM A S. Modern operating system. Chen Xiangqun and other translations. Beijing: Machinery Industry Press, 1999
3 Labrosse Jean J. μC / OS-II- Real-time embedded operating system public code public code. Shao Beibei translated. Beijing: China Electric Press, 2001
