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.

NARTOS Characteristics

The proposed operating system has probably the smallest footprint of all such operating systems. It has the following features:

  • 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.

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.

Note that the term "tasks" used in NARTOS are similar to the concept of "co-routines"  used by some other RTOSs. However they are not strictly the same as a co-routine as defined in Computer Science, since they do not have multiple entry points.

Existing RTOS software

This is probably not complete:

  1. FreeRTOS. Comprehensive and portable. Available for a range of devices. Supports independent tasks and co-routines (reduced footprint tasks sharing basic MCU resources). Modified GPL or commercial licence.

  2. FemtoOS. Suitable for as little as 2KB Flash and 128 byte RAM. GPLv3 or commercial licence.

  3. Salvo. Typical applications use 1-2K ROM and 50-100 bytes of RAM. Available for a range of devices. Proprietary licence but limited demo version available.

  4. AVRX. Tasking, Semaphores, Timer Management, Message Queues. About 1-1.5K ROM and full register context saving. Windows support by author only but gcc support by third parties. GPLv2.

  5. Uc/OS-II by Micrium Inc. Proprietary licence.

  6. CMX-RTX, CMX-Tiny+ by CMX systems. Proprietary licence.

  7. Nut-OS. RTOS for an embedded ethernet system EtherNut. BSD Licence.

  8. Proc by Nilsen Electronikk. Freeware, licence similar to GPLv2.

  9. EmBOS by Segger Microcontroller Systems. Proprietary licence but limited demo version available.

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". 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.

  • uint8_t taskStart(const uint16_t addressPointer, const uint8_t isrCall) 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. The parameter isrCall must be TRUE if called from an ISR, FALSE otherwise. E.g. taskId = taskStart((uint16_t)*address,FALSE);

  • void taskRelinquish(void) (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.

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

  • void taskSchedule(const uint8_t taskId,  const uint8_t isrCall) will reschedule a specified waiting task for execution next time the operating system is entered. It can be rescheduled at high priority.

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

  • void initNartos(void) initialises the OS by clearing the task table and queue pointers. Should be called at the start of the main program and before any tasks are defined.
  • void nartos(void) (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.

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.

Programming Practice

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:

  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 will 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 that is applicable more generally 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 locking.

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 */
int main(void)
{
  initNartos();
  inputPacketReceiveID = taskStart((uint16_t)*inputPacketReceive,FALSE);
  nartos();
}

/* Check for a character received and schedule a task to process it */
void inputPacketReceive(void)
{
    uartInput = uart_getc();        /* upper byte has an error code, if any */
    if (high(uartInput) != 0)       /* nonzero if error or no character received */
    {
        taskRelinquish();
    }
    else
    {
       processCommandID = taskStart((uint16_t)*processCommand,FALSE);
       taskWait();
    }
}

/* Process a command received, and either send a response or an error message.
Reschedule the receive task and exit the processing task. */
void processCommand(void)
{
    ......
  if (lastError == NO_ERROR)
    outputPacketSendID = taskStart((uint16_t)*outputPacketSend,FALSE);
  else
    outputPacketSendID = taskStart((uint16_t)*processError,FALSE);
  taskSchedule(inputPacketReceiveID,FALSE);
  taskExit();
}



First created 19 May 2007

Last Modified 18 October 2014