SRS Home | Front Page | Monthly Issue | Index

Search WWW Search seattlerobotics.org

A Cooperative Multi-Tasking Operating System (picoCMOS)

By J. - L. (John) Girard

 

 

1.0     Introduction

 

Being described is the design and implementation of a tiny Cooperative Multi-tasking Operating System.  The implementation is for the Microchip PICmicroâ midrange micro-controllers such as the PIC16F87x.  The design is general enough that it could be implemented on other processors.

 

picoCMOS greatly facilitates writing applications that contain many tasks that need to run apparently simultaneously such as real-time control for robotics. 

 

 

2.0     Cooperative versus Preemptive Operating Systems

 

In a preemptive scheme the operating system takes control from a running task after an interval of time, called a "time slice", has expired.  In a cooperative scheme, tasks relinquish control voluntarily. 

 

One can easily preemptively interrupt a running task after a time slice using a timer interrupt and return control to it after executing another piece of code.  Refreshing LEDs is often done in the background this way.  In the PICmicroâ midrange micro-controllers, since the interrupt service routine cannot access the stack, the return address of the interrupted task cannot be saved to be given control at a later time after another task has been giving temporary control.  The interrupted (foreground) task can only be given control via a "return" instruction; thus, only the interrupt service routine (background) task can be executed.

 

If a task cooperates on the other hand, it can pass control to the operating system with an explicit return address.

 

 

3.0     picoCMOS Structure

 

picoCMOS consists of a single data structure, the kernel, a scheduler, and two macros in its application programmer interface (API).

 

 

3.1     Task Control Block Data Structure

 

A Task Control Block (TCB), depicted below, holds information relevant to a task; in the case of picoCMOS, that information is one byte to hold the number of OS ticks (see below) to delay and two bytes to store the address to receive control when that delay has expired.  Since every task needs a TCB, an array of them is created.

 

 

 

 

The use of this structure will be considered in the algorithms to follow.

 

 

3.2     picoCMOS API

 

The API consists of two macros:

 

            OS_CREATE_TCB   <task id>  <entry point label>

     OS_DELAY        <number of OS ticks to delay>

 

Two of the most important rules in picoCMOS are:

 

1. The main program must create a TCB for every task that is to run.
2. Every task must have, at the top level (as opposed to in a subordinate level), at least one delay.

 

It is the creation of the TCB that introduces a task to the OS kernel and the scheduler.  The delay is the means by which control is relinquished to the OS.

 

The task id is a cardinal number starting from 0; although not necessary at this point, as the macro could easily generate a unique cardinal, it will be used later as a unique id for inter-task communication.  The entry point is the label where the task is to initially start executing.  The delay is the number of OS ticks (see below) to delay before reacquiring control at the point following the macro invocation.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

    

 

3.3     Kernel and Scheduler

 

The kernel is an interrupt service routine (ISR) that periodically gets control via a timer interrupt.  The frequency of interruption is called the "OS tick rate".  In the case of the PICmicroâ the tick rate can be adjusted, depending on the application, via the timer prescaler (and to some extent preloading the timer).  At each OS tick, the kernel decrements (but not beyond zero) the delay value in every TCB.

 

 

 

 

 

 

 

 

 

 

 

 

The scheduler, which is called in the main program after creating the TCBs, repeatedly scans all the TCBs and gives control to the first task with a delay of zero.  When the scheduled task relinquishes control, the scheduler continues considering the next task in the id sequence.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.0     Program Structure and Operation

 

Shown below is the structure of a typical application program that uses picoCMOS.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

OS_CREATE initializes the TCB with a delay of 0 and the entry point of the task.  The OS_SCHEDULER scans the TCB structure and gives control to the first task with a delay of zero; initially, this is Task0 which executes to its OS_DELAY.  This initial execution can be used to do task initialization.  The invocation of OS_DELAY updates the TCB with a delay value and the return address (following the invocation of OS_DELAY) and control is returned to the scheduler which then continues with the next task.

 

While this is happening, the kernel is decrementing every delay value at the tick rate so that the first task to have its delay decremented to zero will regain control (this time at the instruction following the invocation of OS_DELAY).

 

 

5.0     Testing

 

picoCMOS was initially tested on a PIC16F876 running at 4 MHz using an application that has 6 tasks:  a task that displays a 2 digit counter on a two digit multiplexed pair of 7 segment LEDs, a 2 digit counter, and 4 tasks that simply blink LEDs each at a different rate. 

 

The TMR0 prescaler was set at 32 so that the tick rate was 4 x 10⁶ / 4 / 32 / 256 (clock frequency / cycles per instruction / prescaler / timer modulo) = 122 ticks/sec.  The 7 segment LED multiplexing was done with an OS_DELAY of 1 for each digit; thus, since one digit is on while the other is off the LEDs are refreshed every 1 / 61 of a second (122 / 2).  Shown below is the pseudo-code for the 2-digit display task.

 

 

 

 

 

 

 

 

 

 

    

 

All tasks ran with no apparent illicit interaction.  When the blink rates of the LED blinker tasks were set identically they all appeared to turn on and off simultaneously.  The main program and the tasks were located on different pages to test proper page selection logic.

 

picoCMOS has been recently used to implement a subsumption architecture in a robot that previously used conventional programming of a single task.  The programming complexity was drastically simplified and the robot's behavior was dramatically enhanced.

 

 

6.0     Future Enhancements

 

The first enhancement will likely be inter-task communication using binary semaphores.  Other more general inter-task communication may be added, as it is needed.

 

Presently all tasks have the same priority; if more than one task has its delay set to zero, the first task encountered by the scheduler will get control.  A means of prioritizing the tasks may be useful.

 

 

 

7.0     Links and Downloads

 

The main resource used in the design of picoCMOS was a Microchip document describing the Salvoä RTOS.

 

The application to test picoCMOS, described above, and picoCMOS itself, available as an include file, is available on the author's web site.

 

News of the use of picoCMOS and questions may be directed to J.- L. (John) Girard.