Encoder Front Page
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.



                  TCB[TASK_ID].delay   = 0
                  TCB[TASK_ID].address = ENTRY_POINT
                  NUMBER_TASKS++      ; assembly time variable
OS_DELAY        MACRO      DELAY      ; currentTask is a global variable 
                      ; whose value is assigned by the scheduler
                  TCB[currentTask].delay   = DELAY
                  TCB[currentTask].address = Return_Address
                  GOTO OS_Scheduler
ReturnAddress:    ; return address after delay has expired














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.


Text Box: OS_KERNEL       MACRO      ; ISR given control at the OS tick rate
                  save context of currently running task
                  FOR i = 0 TO numberTasks
                    IF TCB[i].delay != 0
                  restore context of interrupted task











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.

                  numberTasks = NUMBER_TASKS    ; save assembly-time 
                                         ; NUMBER_TASKS into a run-time variable used by scheduler and 
     ; kernel
                    FOR currentTask = 0 TO numberTasks
      IF (TCB[currentTask].delay == 0)
                        GOTO TCB[currentTask].address
OS_Scheduler:       ; entry point when task relinquishes control; i.e. next task















4.0 Program Structure and Operation


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

Text Box:      Task0:     LOOP
                  OS_DELAY delayTime#0
     ; ------------------------------
     Task1:     LOOP
                  OS_DELAY delayTime#1
     Task2:     LOOP
                  OS_DELAY delayTime#2
     Main:             OS_CREATE  0, Task0
                                    OS_CREATE  1, Task1
                                    OS_CREATE  2, Task2



























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 106 / 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.


Text Box: Display:   LOOP            
             OS_DELAY 1    
             convert least significant BCD digit to 7 segment
  output digit (selecting least significant display)
             OS_DELAY 1
             convert most significant BCD digit to 7 segment
  output digit (selecting most significant display)









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.