In my previous blog I mentioned my goal of having a simple cooperative multitasking framework for embedded C programs. My objectives were simple:
- Each task function would start fresh each time it is scheduled
- Task local memory would be easy to use and on the heap, not the stack
setjmpis available, a task could yield from inside a subroutine (even though on reschedule, the task will start back at the top)
- If no
setjmpis available, tasks can only yield from their top-level function
- Time is the responsibility of a user task
- Forrester Study: The Total Economic Impact of VMware View
- Protecting Unstructured Data On File Servers, NetApp, EMC and SharePoint
I packaged everything up as a source file that can be included with a project. As I mentioned last time, I decided to get it working under Linux and then port it to some of the microcontrollers I actually have in mind.
Just like I think the maligned
goto statement has its uses, I also am not nearly as offended by the preprocessor as some people seem to be, and I use it liberally to make it easier to use the system (Light Weight Operating System or lwos). The preprocessor is a tool, and like any tool its power for misuse is proportional to its power for usefulness. A chainsaw can make a day's work easier, but it can also cut off a finger (as my friend Cheri almost found out a few weeks ago). So it is with the preprocessor.
For example, the scheduler depends on a table of tasks' functions in priority order. Here's an example made more readable by the preprocessor:
// The task table TASK_TABLE TASK_DEF(TASK_READY,task0) TASK_DEF(TASK_READY,task1) TASK_DEF(TASK_READY,task2) TASK_TABLE_END
Many of the "functions" are also preprocessor defines. This is efficient and is similar to using a C++ inline function. It also allows for things like
task_storage to take a type name, something it couldn't do if it were a real function. Of course, you have to be careful with side effects in macro arguments, but that's the price of a chainsaw. All the macros reside in lwos.h.
task_storage, that's a macro that allows a task to store private data that stays around between invocations. There is a pointer in the task structure that starts out as NULL. Each "call" to
task_storage casts the pointer to the right type. However, on the first call the pointer is NULL and then the macro allocates sufficient space for the data type first. A task can use this as the first line in a task function:
struct locals local=task_storage(struct locals);
The main logic is in
task_init (in lwos.c). The basic flow is very simple (in keeping with the light-weight theme):
- Get the first entry in the task table. If it is ready to run, run it. When it returns, start over.
- Get the next entry in the task table (this implies the first entry was not runnable). If it is ready to run, run it. When it returns, start over at the first entry. If it is not ready, keep repeating this step on subsequent rows in the table.
This is a bit oversimplified, but it all boils down to what makes a task ready. If the first task is always ready, it will always run and nothing else will (such is a cooperative operating system). One other nuance is that a task can release to another task instead of returning to the top of the table.
The task structure for each row of the table is pretty simple:
taskfunc= A function pointer to the task's main function
taskdata= A pointer to task local storage
wait= A pointer to the lock flag (like a semaphore) the task is waiting on
wake= A time value to wake up a waiting task
yieldbuf= Used if
setjmpis available for returning
The naïve answer, then, is that a task is ready to run if its state field is
TASK_READY. If the field is
TASK_WAIT, then either
wake should be non-zero or
wait should be a non-NULL pointer. It is possible to have both, if you are careful to set them both appropriately before waiting, but the current code expects only one type of
wait to be used at a time.
wait pointer is non-NULL, then the scheduler checks to see if it points to a zero. If so, then the task becomes ready. This can manage simple interlocks or counted semaphores. Keep in mind that concurrency management isn't an issue because no task can run until another relinquishes control.
If the wake value is non-zero then the scheduler checks to see if the tick count is greater than or equal to the value. If so, the task wakes up. However, the scheduler never updates the tick count. That job is handled by a user task (usually the highest priority one). So what's a tick? Whatever you want it to be. Your tick updater could bump the count each second, or every millisecond, or once a day. It could even count external events instead of time.
The scheduler sets a few global variables before it runs a task. In particular,
task_num is the current task number and
task_current is a pointer to the current row in the task table. Some of the macros use this for different purposes.
The return value of the function determines what the scheduler does. If the function returns zero, the scheduler goes back to the start of the task table. Remember, if the first task stays ready and yields, then nothing else is ever going to happen because the scheduler will run it again.
Of course, the task could mark itself not ready and then yield. It can also return a non-zero number, which is taken as a task to run next. The actual return value has one added to it so that a yield that is specifically targeted at task 0 actually returns 1 (although you could just as well return 0, which will do the same thing). A return of 2, therefore, targets task 1, and so on. The
yield_to macro takes care of this for you, however, so you simply write
yield_to(1). There is also a
task_yield_next macro to handle the common case of letting "the next task" run.
Next time, I'll talk more about the role of
longjmp before porting the code to the Microchip PIC compiler.