Scheduling Operating System for AVR
Note: 15 February 2014. This was developed as a minimal size scheduler for small memory devices with no support for context switching. It is no longer under development but has been successfully used. It requires particular attention to certain coding restrictions.
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 som eof the smallest microcontrollers. 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). It doers not make use of any timing information and could be used in an application that does not use interrupts. The source is included in the library. NARTOS is opensource licenced under GPL v2.
The proposed operating system has probably the smallest footprint of all such operating systems. It has the following features:
NARTOS is written in C with some
avr-gcc assembler included. It does not use any hardware resource
of the microcontroller apart from the stack, and so could be
written completely in assembler to run on most AVR devices. The
minimal nature of the operating system requires strict attention
to certain programming practices, as described below.
Existing RTOS software
This is probably not complete:
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". The high priority task queue is Last-in First-out. 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.
Error conditions: if too many tasks are defined, excess tasks are simply not created. taskSchedule can in principle schedule the wrong task. No checks are made to prevent this. It will cause havoc and mayhem.
With NARTOS it is important to program the tasks that ensures the program preserves the stack integrity, and that it 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. It is simple enough to accomplish if using assembler, but 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:
When using the high priority queue, care must be taken to ensure that the high priority tasks do not take over the processor. For example a task at high priority that enters a loop with only a taskRelinquish call, would block out all other tasks, including those at high priority (since the high priority queue is LIFO). NARTOS is not sophisticated enough to detect such situations. Some protection is provided by only allowing tasks to be rescheduled at high priority, but not relinquished tasks or newly started tasks. Ensure that the flow of task scheduling is well understood in the application.
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.
Example/* Initialise the OS and start the receive task */
inputPacketReceiveID = taskStart((uint16_t)*inputPacketReceive,FALSE);
/* Check for a character received and schedule a task to process it */
uartInput = uart_getc(); /* upper byte has an error code, if any */
if (high(uartInput) != 0) /* nonzero if error or no character received */
processCommandID = taskStart((uint16_t)*processCommand,FALSE);
/* Process a command received, and either send a response or an error message.
Reschedule the receive task and exit the processing task. */
if (lastError == NO_ERROR)
outputPacketSendID = taskStart((uint16_t)*outputPacketSend,FALSE);
outputPacketSendID = taskStart((uint16_t)*processError,FALSE);
First created 19 May 2007
Last Modified 18 October 2014