Building "instant-up" real-time operating systems - Embedded.com

Building “instant-up” real-time operating systems

Getting an operating system running on any new target system is always a challenge that could be made simpler if an embedded system developer had a way of getting a real-time operating system up and running in an “instant.” Such an instant-up operating system (IOS) would need no more than some initial compilation with minimal hardware resources required.

This article describes three IOS environments:

1. The cooperative scheduler;

2. The Protothreads tool set, written by Adam Dunkels, described in detail on Protothreads' website www.sics.se/~adam/pt/, and

3. A blending of Protothreads with a cooperative real-time scheduler.

Many seasoned software developers have often faced this classic situation: the hardware team completes a new board and the software team needs to get something working on it. Likely a boot loader and a batch of test utilities will need to be written quickly. A multitasking operating system would sure be handy for this job, but porting a modern operating system will take time and is possibly overkill. The development schedule is likely several weeks behind and as a result, software is now the “brick wall”–there is no time for anything fancy.

Wouldn't it be nice to have an operating system running in an instant? And to have an operating system that doesn't require complex porting to new hardware? Or one that only needs to be compiled with the new target compiler in order to run?

Recently, while taking a real-time operating systems class at Metro State University in St. Paul, I learned about a cooperative scheduler based on work from Michael J. Pont (author of Patterns for Time-Triggered Embedded Systems ) in which tasks can be created and executed at different priorities. An implementation of this scheduler produces an extremely small cooperative operating system, which is also very easy to port: an instant-up operating system (IOS #1).

About the same time, I was also introduced to Protothreads, written by Adam Dunkels. To quote from the website, “Protothreads are extremely lightweight stackless threads . . . .” They are written in C and “provide linear code execution for event-driven systems.” Protothreads are a collection of C macros that give a simple way to have multiple threads running completely in C.

There are no worries about stack allocations or context switching, since the compiler does the heavy lifting. Protothreads provides a method to create threads that seemingly don't run to completion and give virtual concurrency. Protothreads, of course, don't give true concurrency, but threads can be organized as though they do. And Protothreads is easy to port. Voila! IOS #2.

Discovery of Protothreads got me wondering: what would happen if it were blended with a cooperative scheduler? Would this result in IOS #3, merging the virtual concurrency of Protothreads with the scheduling provided by the cooperative scheduler? I found that porting either of them is easy. Indeed, in the case of the cooperative scheduler, only a regular “tick” or timeout is required.

Cooperative schedulers
A cooperative scheduler works on a very simple concept. Given a tick or other delay mechanism, tasks are scheduled and executed at assigned times. In our example, the scheduler maintains a table of tasks, and, as each tick occurs, the expiration times for each task are decremented. When a task's timer expires, the task is scheduled for execution and the timer is reloaded with the reload value given during task creation.

The task control structure for the example cooperative scheduler is simple. It contains a function pointer to a task and a parameter to be passed to the function when called. It also contains data regarding when the task expiration timer and reload value expire.

typedef struct{  int (*pTask) (void * data);   void * param;  int ready;   int valid;  int expires;   int reload;   int handle;} cooperativeTask_t;   

A tasksConstructor needs to be called first; it simply clears the data for all possible tasks and prepares for new tasks to be created.

cooperative_tasksConstructor ();   

A task is created using the function createTask , which loads the function pointer of the task and the data pointer into the task control structure. An initial expire time and reload value are loaded as well. Note that expire and reload times are based on ticks.

int cooperative_createTask    (int (*pFunction)    (void * data),void * data, int expires,    int reload)   

Some type of timer or interrupt service routine (ISR) is necessary to execute the processTick() function on a regular basis. This step gives developers flexibility to test and simulate their implementation on a desktop. Listing 1 shows how processTick() could be implemented. The processTasks() function simply checks which tasks are scheduled, have expired, executes the tasks' functions, and deletes any task with no programmed reload value. It's even possible to have a task execute one time and be deleted. Listing 2 is an example of how processTasks() might be implemented.

View the full-size image

View the full-size image

To tie everything together, a main loop is required. If the timer tick is not handled in an ISR, a simple main loop can be implemented as shown below. If a tick ISR is used, the main loop would simply have a processTasks() call.

while (1){    usleep (100);     cooperative_processTick ();     cooperative_processTasks ();}   

Task execution is performed outside of ISRs, which means all threads run in the same context minimizing needs for concurrency control mechanisms. As all of the scheduler code is written in ANSI C and the only hardware dependency is the tick, one can quickly see how easy it would be to port this to a new target.

Protothreads
Although an excellent explanation of Protothreads internals can be found on the Protothreads website at www.sics.se/~adam/pt/, minimal information is needed to get up and running quickly.

Protothreads are stackless threads that provide conditional blocking. The conditional blocking is accomplished using what some have called a “dodgy” feature of C: many C compilers, including GNU, allow for a nonconventional switch/case construction; a while loop placed in the middle of the switch.

Listing 3 and 4 shows the breakdown example.

(Source for Listing 3 and 4: www.sics.se/~adam/pt/expansion.html)

Notice how the PT_BEGIN simply maps to the beginning of the switch/case:

#define PT_BEGIN(pt)    switch(pt->lc) { case 0:   

Each time the function or “thread” is called, execution will resume exactly where the thread blocked. The location is determined from the line number at compilation time. See the expansion of PT_WAIT_UNTIL :

#define PT_WAIT_UNIT(pt, c)     pt->lc = __LINE__;case     __LINE__:If (!(c)) return 0   

Finishing up with PT_END closes the switch/case, cleans up, and returns control to the scheduler.

#define PT_END(pt)  } pt->lc =     0; return 2;   

Creation of a thread using Protothreads is simple but requires a few steps as shown in the code example in Listing 5 . Each thread must be declared using the PT_THREAD macro. Each thread must receive a pt struct point as a parameter. Each thread also requires PT_INIT(&pt) to be invoked to configure the context the first time.

A PT_BEGIN(pt) is required at the beginning of the thread and a PT_END(pt) is required at the very end. In the middle of the thread the implementer has a variety of macros to choose from to cause the thread to yield. (The complete application programming interface, examples, more implementation details can all be found on the Protothreads website.)

View the full-size image

Several threads can be created and executed. A simple main program for the example above could be like the one shown in Listing 5 .

The infinite loop in main is continuously executing all of the threads. Each time a thread is reentered from main, code execution will begin from where the thread had previously yielded, just as one would expect. Notice how the data is stored in global variables.

Blending the IOSes
Both the cooperative scheduler and Protothreads can be useful for a variety of jobs, with Protothreads providing virtual concurrency and the cooperative scheduler used to allow task execution to be scheduled.

Listing 6 shows a complete blending of an application using Protothreads and the cooperative scheduler. The task control block in this case (pt ) is defined by Protothreads and still needs to be initialized before use, by invoking the PT_INIT macro. After that, the tasks are created exactly as explained above in the cooperative scheduler.

View the full-size image

The tasks will run just fine using Protothreads alone, but by adding the cooperative scheduler, higher priority threads can be created that execute more often than lower priority. Since scheduling is based and occurs on a tick, a device can even go into sleep mode and conserve battery life.

Concerns
All of this sounds great, but a few things must be kept in mind:

Concern #1: Processing time. For cooperative scheduler based operating systems, it's possible that tasks are scheduled too closely together or attempt to do too many things. If a task doesn't complete or yield the CPU in a timely manner, the system will become indeterministic and possibly unstable. This can be rectified by splitting large tasks into smaller and smaller pieces. A developer must always be aware of how much CPU timer is being used and may have to be creative to properly split the tasks. If this becomes too much of a challenge, a traditional context switching operating system may be the proper answer.

Concern #2: Interrupts also consume CPU time. If the only interrupt running on the system is the operating system's tick, task execution can be pretty deterministic. If many interrupts are firing, timing of the operating system's tick may start to drift. If too many interrupt handlers are being executed, there may not be enough CPU time to process the tasks in a timely manner. For an operating system such as this, it has been suggested that only the operating system's tick interrupt should be allowed and the other interrupt sources should be polled. Not all situations require this interrupt moratorium, but keep it in mind. For example, predictable interrupts such as those generated by a T1 framer would probably not cause a problem. (Random interrupts may be another story.)

Concern #3: Data storage in the threads. In none of the three IOSes is “true” context switching taking place. Each time a task “yields,” it's actually returning to the scheduler. Data stored in local variables will be lost. This can be rectified by creating a storage object for the tasks local data. You could even add a pointer to this storage object in the Protothreads context. For example, note the myData pointer:

struct pt {   lc_t lc;   void *myData; };   

Add Protothreads and stir
Beyond being very useful and powerful when used alone in a variety of tasks, I believe the blending of Protothreads and cooperative scheduling provide the combination of virtual concurrency and task scheduling an IOS environment needs to provide developers with a simple and quick way to get multitasking going on a new target.

Michael Dorin is an independent embedded software developer and is working toward a masters in computer science at Metro State University in St. Paul, MN. He can be reached at .

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.