Demonstration of a Single Context Switch on the MegaAVR MCU View the slideshow demonstrates in seven steps the process of switching from a lower priority task, called TaskA, to a higher priority task, called TaskB. These slides demonstrate the concepts described in the article.

Applications designed for use with a real time operating system (RTOS) are structured as a set of autonomous tasks. The RTOS kernel will switch between tasks as necessary to ensure the task with the highest priority that is able to run is the task given processing time. How such a switch is performed is dependent on the microcontroller architecture.

This article uses source code from FreeRTOS.org (an open source real time kernel) to demonstrate how you can implement a task switch. The source code is explained from the bottom up and the article includes a detailed step-by-step guide to one complete task switch.

The FreeRTOS.org real time kernel has been ported to a number of different architectures. For the example presented in this article, I chose to demonstrate the Atmel MegaAVR port due to the simplicity of the AVR architecture and free availability of the utilized WinAVR (GCC) compiler.

I hope the article will be of interest to those who are new to using an RTOS, interested in creating their own architecture port, or are just interested in RTOS implementation.

Benefits of Multitasking
You can simplify an otherwise complex software application though the use of a multitasking operating system (OS):

• The multitasking and inter-task communications features of the OS allow the complex application to be partitioned into a set of smaller and more manageable programs (or tasks).
• Complex timing and sequencing details can be removed from the application code and become the responsibility of the OS.
• Testability, work breakdown within teams, code reuse, and so on become more manageable.

Multitasking vs. Concurrency
A conventional microcontroller can only execute a single task at a time—but by rapidly switching between tasks an OS can make it appear as if each task is executing concurrently.

Figure 1: Rapidly switching between tasks can make it appear as if each task is executing concurrentlyz

Figure 1 shows the execution pattern of three tasks with respect to time. The task names are color coded and appear on the left. Time moves from left to right, with the colored lines showing which task is executing at any particular time. The upper diagram demonstrates the perceived concurrent execution pattern, and the lower the actual multitasking execution pattern.

Task States
In addition to being suspended involuntarily by the RTOS kernel a task can choose to suspend itself. It will do this if it either wants to delay (sleep) for a fixed period, or wait (block) for a resource to become available or an event to occur.

A blocked or sleeping task is not able to execute, and will not be allocated any processing time.

Scheduling
The scheduling policy is the algorithm used by the OS to decide which task should be executing at any moment in time. The scheduling policy is designed to meet the objectives of the OS—which for an RTOS is to provide a timely response to real world events.

The application designer must assign a priority to each task. The higher the criticality of the task (or the shorter its maximum acceptable response time) the higher its relative priority should be. The scheduling policy of the RTOS is then simply to make sure the highest priority task that is ready to execute (not blocked or sleeping) is the task given processing time.

Example Real Time Execution Profile
This section provides a simplistic example that demonstrates the principles of real time scheduling.

A hypothetical embedded system incorporates a keypad and LCD. A user must receive the visual feedback of each key press within a reasonable period—if the user cannot see that the key press has been accepted within this period the product will at best be awkward to use. If the longest acceptable period is 100ms—any response between 0 and 100ms is acceptable. This functionality could be implemented as an autonomous task with the following structure:

void vKeyHandlerTask( void *pvParameters )
{
   /* Key handling is a continuous process and as such the task
   is implemented using an infinite loop (as most tasks are). */
   for( ;; )
   {
       [Suspend waiting for a key press]
       [Process the key press]
   }
}
Listing 1:  Task that records key strokes

Now assume the software is also performing a control function that relies on a digitally filtered input. The input must be sampled, filtered, and the control cycle executed every 2ms. For correct operation of the filter the temporal regularity of the sample must be accurate to 0.5ms. This functionality could be implemented as an autonomous task with the following structure:

void vControlTask( void *pvParameters )
{
   for( ;; )
   {
       [Suspend waiting for 2ms since the start of the previous
       cycle]
       [Sample the input]
       [Filter the sampled input]
       [Perform control algorithm]
       [Output result]
   }
}
Listing 2:  Sampling the digitally filtered input

The software engineer must assign the control task the highest priority as:

1. The deadline for the control task is stricter than that of the key handling task.
2. The consequence of a missed deadline is greater for the control task than for the key handler task.

Figure 2 demonstrates how these tasks would be scheduled by a real time operating system. The RTOS has itself created a task—the idle task—which will execute only when there are no other tasks able to do so. The idle task is always in a state where it is able to execute.

Referring to Figure 2:

• At the start neither of our two tasks are able to run—vControlTask is waiting for the correct time to start a new control cycle and vKeyHandlerTask is waiting for a key to be pressed. Processing time is given to the idle task.
  
  
• At time t1, a key press occurs. vKeyHandlerTask is now able to execute—it has a higher priority than the idle task so is given processing time.
  
  
• At time t2 vKeyHandlerTask has completed processing the key and updating the LCD. It cannot continue until another key has been pressed so suspends itself and the idle task is again resumed.
  
  
• At time t3 a timer event indicates that it is time to perform the next control cycle. vControlTask can now execute and as the highest priority task is scheduled processing time immediately.
  
  
• Between time t3 and t4, while vControlTask is still executing, a key press occurs. vKeyHandlerTask is now able to execute, but as it has a lower priority than vControlTask it is not scheduled any processing time.
  
  
• At t4 vControlTask completes processing the control cycle and cannot restart until the next timer event—it suspends itself. vKeyHandlerTask is now the task with the highest priority that is able to run so is scheduled processing time in order to process the previous key press.
  
  
• At t5 the key press has been processed, and vKeyHandlerTask suspends itself to wait for the next key event. Again neither of our tasks are able to execute and the idle task is scheduled processing time.
  
  
• Between t5 and t6 a timer event is processed, but no further key presses occur.
  
  
• The next key press occurs at time t6, but before vKeyHandlerTask has completed processing the key a timer event occurs. Now both tasks are able to execute. As vControlTask has the higher priority vKeyHandlerTask is suspended before it has completed processing the key, and vControlTask is scheduled processing time.
  
  
• At t8 vControlTask completes processing the control cycle and suspends itself to wait for the next. vKeyHandlerTask is again the highest priority task that is able to run so is scheduled processing time so the key press processing can be completed.

The FreeRTOS.org kernel measures time using a tick count variable. A timer interrupt (the RTOS tick interrupt) increments the tick count with strict temporal accuracy—allowing time to be measured to a resolution of the chosen timer interrupt frequency. Each time the tick count is incremented the RTOS kernel must check to see if it is now time to unblock or wake a task.

It is possible that a task woken or unblocked during the tick ISR will have a priority higher than that of the interrupted task. If this is the case the tick ISR should return to the newly woken/unblocked task—effectively interrupting one task but returning to another (Figure 3).

Figure 3: A context switch occurring in an interrupt service routine

Referring to the circled numbers in Figure 3:

• At (1) the highest priority task (vControlTask) is blocked waiting for a timer to expire. The next highest priority task (vKeyHandlerTask) is also blocked waiting for a key press event. This leaves the Idle Task as the highest priority task that is able to run.
  
  
• At (2) the RTOS tick interrupt occurs. The microcontroller stops executing the Idle Task and starts executing the tick ISR (3).
  
  
• The tick ISR increments the tick count which (for the sake of this example) makes vControlTask ready to run. vControlTask has a higher priority than the idle task so a context switch is required. A task switch from the Idle Task to vControlTask occurs within the ISR.
  
  
• As the execution context is now that of vControlTask, exiting the ISR (4) returns control to vControlTask, which starts executing (5). The Idle Task remains suspended until it is again the highest priority task that is able to execute.

"Execution Context"—a Definition
As a task executes it utilizes microcontroller registers and accesses RAM and ROM just as any other program. These resources together (the registers, stack, and so on) comprise the task execution context.

A task is a sequential piece of code that does not know when it is going to get suspended (stopped from executing) or resumed (given more processing time) by the RTOS and does not even know when this has happened. Consider the example of a task being suspended immediately before executing an instruction that sums the values contained within two registers.

Figure 4: A sample task context immediately prior to the task being suspended

While the task is suspended other tasks will execute and may modify the register values. Upon resumption the task will not know that the registers have been altered—if it used the modified values the summation would result in an incorrect value.

To prevent this type of error it is essential that upon resumption a task has a context identical to that immediately prior to its suspension. The RTOS kernel is responsible for ensuring this is the case—and does so by saving the context of a task as it is suspended. When the task is resumed its saved context is restored by the RTOS kernel prior to its execution. The process of saving the context of a task being suspended and restoring the context of a task being resumed is called context switching.

The AVR Context
On the AVR microcontroller, the context consists of:

• 32 General Purpose Registers
  The GCC compiler assumes register R1 is set to zero.
  
  
• Status Register
  The value of the status register affects instruction execution, and must be preserved across context switches.
  
  
• Program Counter
  Upon resumption, a task must continue execution from the instruction that was about to be executed immediately prior to its suspension.
  
  
• The Two Stack Pointer Registers.

Figure 5: The execution context on the AVR microcontroller

Writing the Tick ISR—The GCC 'signal' Attribute
The MegaAVR port of FreeRTOS.org generates the periodic tick interrupt from a compare match event on the MegaAVR timer 1 peripheral. GCC allows the tick ISR function to be written in C by using the following syntax.

void SIG_OUTPUT_COMPARE1A( void ) __attribute__ ( ( signal ) );
void SIG_OUTPUT_COMPARE1A( void )
{
   /* ISR C code for RTOS tick. */
   vPortYieldFromTick();
}
Listing 3:  C code for compare match ISR

The '__attribute__ ( ( signal ) )' directive on the function prototype informs the compiler that the function is an ISR and results in two important changes in the compiler output:

1. The 'signal' attribute ensures that every AVR register that gets modified during the ISR is restored to its original value when the ISR exits. This is required as the compiler cannot make any assumptions as to when the interrupt will execute, and therefore cannot optimize which registers require saving and which don't.
   
   
2. The 'signal' attribute also forces a 'return from interrupt' instruction (RETI) to be used in place of the 'return' instruction (RET) that would otherwise be used. The AVR disables interrupts upon entering an ISR and the RETI instruction is required to re-enable them on exiting.

Compiling the ISR results in the following output:

;void SIG_OUTPUT_COMPARE1A( void )
;{
    ; ---------------------------------------
    ; CODE GENERATED BY THE COMPILER TO SAVE
    ; THE REGISTERS THAT GET ALTERED BY THE
    ; APPLICATION CODE DURING THE ISR.
    PUSH    R1
    PUSH    R0
    IN      R0,0x3F
    PUSH    R0
    CLR     R1
    PUSH    R18
    PUSH    R19
    PUSH    R20
    PUSH    R21
    PUSH    R22
    PUSH    R23
    PUSH    R24
    PUSH    R25
    PUSH    R26
    PUSH    R27
    PUSH    R30
    PUSH    R31

    ; ---------------------------------------
    ; CODE GENERATED BY THE COMPILER FROM THE
    ; APPLICATION C CODE.
    ;vTaskIncrementTick();
    CALL       0x0000029B       ;Call subroutine

    ; ---------------------------------------
    ; CODE GENERATED BY THE COMPILER TO
    ; RESTORE THE REGISTERS PREVIOUSLY
    ; SAVED.
    POP    R31
    POP    R30
    POP    R27
    POP    R26
    POP    R25
    POP    R24
    POP    R23
    POP    R22
    POP    R21
    POP    R20
    POP    R19
    POP    R18
    POP    R0
    OUT    0x3F,R0
    POP    R0
    POP    R1
    RETI
;}
Listing 4: Compiler output for Listing 3

Organizing the Context—The GCC 'naked' Attribute
The previous section showed how you can use the 'signal' attribute to write an ISR in C and how this results in part of the execution context being automatically saved (only the microcontroller registers modified by the ISR get saved). Performing a context switch however requires the entire context to be saved.

The application code could explicitly save all the registers on entering the ISR, but doing so would result in some registers being saved twice—once by the compiler generated code and then again by the application code. This is undesirable and can be avoided by using the 'naked' attribute in addition to the 'signal' attribute.

void SIG_OUTPUT_COMPARE1A( void ) __attribute__ ( ( signal, naked ) );
void SIG_OUTPUT_COMPARE1A( void )
{
   /* ISR C code for RTOS tick. */
   vPortYieldFromTick();
}
Listing 5:  Addition of the 'naked' attribute to the compare match ISR

The 'naked' attribute prevents the compiler generating any function entry or exit code. Now, compiling the ISR results in the much simpler output:

;void SIG_OUTPUT_COMPARE1A( void )
;{
   ; ---------------------------------------
   ; NO COMPILER GENERATED CODE HERE TO SAVE
   ; THE REGISTERS THAT GET ALTERED BY THE
   ; ISR.
   ; ---------------------------------------
   ; CODE GENERATED BY THE COMPILER FROM THE
   ; APPLICATION C CODE.
   ;vTaskIncrementTick();
   CALL    0x0000029B    ;Call subroutine

   ; ---------------------------------------
   ; NO COMPILER GENERATED CODE HERE TO RESTORE
   ; THE REGISTERS OR RETURN FROM THE ISR.
   ; ---------------------------------------
;}
Listing 6:  Compiler output from Listing 5

When the 'naked' attribute is used the compiler does not generate any function entry or exit code so this must now be added explicitly. The macros portSAVE_CONTEXT() and portRESTORE_CONTEXT() respectively save and restore the entire execution context.

void SIG_OUTPUT_COMPARE1A( void ) __attribute__ ( ( signal, naked ) );
void SIG_OUTPUT_COMPARE1A( void )
{
   /* Macro that explicitly saves the execution
   context. */
   portSAVE_CONTEXT();

   /* ISR C code for RTOS tick. */
   vPortYieldFromTick();

   /* Macro that explicitly restores the
   execution context. */
   portRESTORE_CONTEXT();

   /* The return from interrupt call must also
   be explicitly added. */
   asm volatile ( "reti" );
}
Listing 7:  The compare match ISR modified to explicitly save/restore the execution context

The 'naked' attribute gives the application code complete control over when and how the AVR context is saved. If the application code saves the entire context on entering the ISR there is no need to save it again before performing a context switch so none of the microcontroller registers get saved twice.

Saving the Context
Each task has its own stack memory area so the context can be saved by simply pushing registers onto the task stack. Saving the AVR context is one place where assembly code is unavoidable.

portSAVE_CONTEXT() is implemented as a macro, the source for which is given below:

#define portSAVE_CONTEXT()			\
asm volatile (			\
"push	r0	\n\t"	\ (1)
"in	r0, __SREG__	\n\t"	\ (2)
"cli		\n\t"	\ (3)
"push	r0	\n\t"	\ (4)
"push	r1	\n\t"	\ (5)
"clr	r1	\n\t"	\ (6)
"push	r2	\n\t"	\ (7)
"push	r3	\n\t"	\
"push	r4	\n\t"	\
"push	r5	\n\t"	\
:
:
:
"push	r30	\n\t"	\
"push	r31	\n\t"	\
"lds	r26, pxCurrentTCB	\n\t"	\ (8)
"lds	r27, pxCurrentTCB + 1	\n\t"	\ (9)
"in	r0, __SP_L__	\n\t"	\ (10)
"st	x+, r0	\n\t"	\ (11)
"in	r0, __SP_H__	\n\t"	\ (12)
"st	x+, r0	\n\t"	\ (13)
);

Listing 8: portSAVE_CONTEXT()

Referring to the numbers in Listing 8:

• Register R0 is saved first (1) as it is used when the status register is saved, and must be saved with its original value.
  
  
• The status register is moved into R0 (2) so it can be saved onto the stack (4).
  
  
• Interrupts are disabled (3). If portSAVE_CONTEXT() was only called from within an ISR there would be no need to explicitly disable interrupts as the AVR will have already done so. As the portSAVE_CONTEXT() macro is also used outside of interrupt service routines (when a task suspends itself) interrupts must be explicitly cleared as early as possible.
  
  
• The code generated by the compiler from the ISR C code assumes R1 is set to zero. The original value of R1 is saved (5) before R1 is cleared (6).
  
  
• Between (7) and (8) all remaining microcontroller registers are saved in numerical order.
  
  
• The stack of the task being suspended now contains a copy of the tasks execution context. The kernel stores the tasks stack pointer so the context can be retrieved and restored when the task is resumed. The x register is loaded with the address to which the stack pointer is to be saved (8 and 9).
  
  
• The stack pointer is saved, first the low byte (10 and 11), then the high nibble (12 and 13).

Restoring the Context
portRESTORE_CONTEXT() is the reverse of portSAVE_CONTEXT().

The context of the task being resumed was previously stored in the tasks stack. The kernel retrieves the stack pointer for the task then POP's the context back into the correct microcontroller registers.

#define portRESTORE_CONTEXT()			\
asm volatile (			\
"lds	r26, pxCurrentTCB	\n\t"	\ (1)
"lds	r27, pxCurrentTCB + 1	\n\t"	\ (2)
"ld	r28, x+	\n\t"	\
"out	__SP_L__, r28	\n\t"	\ (3)
"ld	r29, x+	\n\t"	\
"out	__SP_H__, r29	\n\t"	\ (4)
"pop	r31	\n\t"	\
"pop	r30	\n\t"	\
:
:
:
"pop	r1	\n\t"	\
"pop	r0	\n\t"	\ (5)
"out	__SREG__, r0	\n\t"	\ (6)
"pop	r0	\n\t"	\ (7)
);

Listing 9: portRESTORE_CONTEXT()

Referring to the numbers in Listing 9:

• pxCurrentTCB holds the address from where the tasks stack pointer can be retrieved. This is loaded into the X register (1 and 2).
  
  
• The stack pointer for the task being resumed is loaded into the AVR stack pointer, first the low byte (3), then the high nibble (4).
  
  
• The microcontroller registers are then popped from the stack in reverse numerical order, down to R1.
  
  
• The status register stored on the stack between registers R1 and R0, so is restored (6) before R0 (7).

The Complete FreeRTOS.org ISR
The actual source code used by the FreeRTOS.org MegaAVR port is slightly different to the examples shown in the previous sections. The context is saved from within vPortYieldFromTick() which is itself implemented as a 'naked' function. It is done this way due to the implementation of non-preemptive context switches (where a task blocks itself)—which are not described here.

The FreeRTOS.org implementation of the RTOS tick is therefore (see the comments within the code for further details):

void SIG_OUTPUT_COMPARE1A( void ) __attribute__ ( ( signal, naked ) );
void vPortYieldFromTick( void ) __attribute__ ( ( naked ) );
/*--------------------------------------------------*/

/* Interrupt service routine for the RTOS tick. */
void SIG_OUTPUT_COMPARE1A( void )
{
   /* Call the tick function. */
   vPortYieldFromTick();

   /* Return from the interrupt. If a context
   switch has occurred this will return to a
   different task. */
   asm volatile ( "reti" );
}

/*--------------------------------------------------*/
void vPortYieldFromTick( void )
{
   /* This is a naked function so the context
   is saved. */
   portSAVE_CONTEXT();

   /* Increment the tick count and check to see
   if the new tick value has caused a delay
   period to expire. This function call can
   cause a task to become ready to run. */
   vTaskIncrementTick();

   /* See if a context switch is required.
   Switch to the context of a task made ready
   to run by vTaskIncrementTick() if it has a
   priority higher than the interrupted task. */
   vTaskSwitchContext();

   /* Restore the context. If a context switch
   has occurred this will restore the context of
   the task being resumed. */
   portRESTORE_CONTEXT();

   /* Return from this naked function. */
   asm volatile ( "ret" );
}
Listing 10:  The FreeRTOS.org tick ISR