Scheduling Operating System for AVR

A real time operating system (RTOS) allows independent software tasks to be run with different priorities and to gain access to processor resources according to each of their needs. The RTOS manages the amount of time each task gets relative to all other tasks. However a full RTOS with time slicing, preemption, intertask communication and resource locking is beyond the scope of a small microcontroller. Here we examine a possiblility for a scheduling operating system that is very small.

The main motivation for looking to a scheduling operating system was to improve the modularity of application code. A program that executes a set of independent tasks will generally block while waiting for some external event to occur. To avoid this blocking behaviour, a state machine approach can be used, but this can grow to have quite a large number of states. While a state machine is reasonably efficient, the code quickly becomes difficult to read and hard-to-find errors can creep in.

An alternative to a state machine is a scheduling operating system that allows each task to start and run, either to completion or indefinitely, relinquishing control at points in its execution when it is blocked while waiting for an external event. In a comprehensive RTOS the execution of a long task would be regularly interrupted by a timer, and the task would be forced to relinquish control in favour of other tasks waiting for the processor. To achieve this, the RTOS must save the entire state of every task, including all register and stack contents. In a microcontroller environment, the overhead associated with this is undesirable. However ,if the programmer can ensure that tasks voluntarily relinquish control at suitable points in their execution, a reasonable approximation to fair sharing can be achieved.

Here is presented the design of a very basic scheduling operating system that allows the creation, scheduling and deletion of tasks. Because it is not strictly a "real-time" operating system, it is referred to as NARTOS (Not a real-time operating system). The enclosed source file includes a simple example task that toggles an output port. NARTOS is opensource.

NARTOS Characteristics

• One or two level priority scheduling of tasks on a task queue.

• Voluntary relinquishment of control by tasks, and rescheduling by other tasks.

• Creation and deletion of tasks.

• No pre-emption

• No saving of context apart from the program counter.

• No termination of running tasks by other tasks.
  

• Size about 360 bytes of program memory (440 with two priorities) and about 3-4 bytes SRAM per task. This could be reduced further by writing NARTOS in assembler language.
  

Current Status

Existing RTOS software

1. FreeRTOS. Comprehensive and portable. Available for a range of devices. Supports independent tasks and co-routines (reduced footprint tasks sharing basic MCU resources).
   
2. Salvo. Typical applications use 1-2K ROM and 50-100 bytes of RAM. Available for a range of devices.
3. AVRX. Tasking, Semaphores, Timer Management, Message Queues. About 1-1.5K ROM and full register context saving.
4. Uc/OS-II by Micrium Inc.
   
5. CMX-RTX, CMX-Tiny+ by CMX systems.
   
6. Nut-OS. RTOS for an embedded ethernet system EtherNut.
7. Proc by Nilsen Electronikk.
   
8. EmBOS by Segger Microcontroller Systems.
   

NARTOS Design

NARTOS consists of a single ring buffer queue. The size of this queue will need to be kept to a minimum, however it must be long enough to hold a single byte ID for all tasks in the program. The two priority levels are handled by growing the queue in the opposite direction for the high priority entries. High priority tasks are removed from the queue before any low priority entries are removed (as you would expect), so the buffer never becomes "scrambled". It is generally impossible to exceed the buffer capacity (apart from programming errors that may schedule tasks more than once) as the number of tasks started cannot exceed the size of the buffer.

Deletion of a task will free up the table entry for reuse by another task.

The API consists of six calls, of which one is never called from any task or ISR. Three of these are operating system calls that leave the task and re-enter the operating system. These will cause all program context to be lost and must not be called from an ISR. Tasks are all created with low priority, and can only be rescheduled at high priority after a wait. This avoids potential lockout of low priority tasks by a high priority task that relinquishes.

• taskStart will create a new running task.  An entry for the new task start point is made in a table of addresses, and a task ID is returned. This is just an index into the table. The task ID is placed on the queue at low priority. One task at least must be started in the main program, which then must jump into the operating system to execute the tasks on the queues.
  

• taskRelinquish (operating system call) causes the address of the next instruction to be executed, to be placed in the address table and the ID of the task to be placed on the end of the low priority task queue.
  

• taskWait (operating system call) suspends the task indefinitely until an ISR or another task reschedules it.

• taskSchedule will reschedule a waiting task for execution next time the operating system is entered. It can be rescheduled at high priority.
  

• taskExit (operating system call) must be called when the task has completed.

• nartos (operating system call) is only called once at the end of the main program to jump start the task executions. Calling this from anywhere else is likely to totally scramble your application.
  

Programming Practice

With NARTOS it is important to program the tasks in a way to ensure that the program does not have any state variable in a register that needs to be preserved through a relinquish or wait call. This would quite likely be overwritten due to activities of other tasks. This is simple enough to accomplish if using assembler, however with compiled languages it is a different story. It is not easy to determine in general what an optimizing compiler may do to the code. The gcc compiler tends to place local variables into registers. The following practices must be followed ensure that no problems occur:

1. All variables whose values are to be preserved across a relinquish or wait call must be defined as global volatile variables, to force the compiler to store them in SRAM and reload them each time they are accessed.

2. Declare all task prototypes with attribute naked (an AVR specific attribute). This ensures that the compiler does not add any prologue or epilogue which may consist of dangling push and pop instructions. These may blow the stack. The tasks are defined as functions in C but they never return. A task is always an infinite loop or terminates via an operating system call. Another attribute applicable to other processor types and that may work is noreturn.

3. Shared resources would need to be explicitly protected with suitable locks as NARTOS has no inbuilt mechanisms for this.
   

Note that in NARTOS we are manipulating the stack in such a way that API function calls do not behave as a compiler may expect them to do. There is a risk that optimization may make incorrect decisions about the function call.

Needless to say, using NARTOS introduces a number of programming risks and is not appropriate where there are a large number of local variables that would be forced into SRAM by the above constraints. It is definitely not appropriate where strict real-time constraints are necessary. There are other freely available and opensource RTOS packages available, and many good commercial ones.