6.4.1 Two Basic Concepts

To make our operating system work, we need to simultaneously introduce two basic concepts. First, we introduce preemption as an alternative to the C function call as a way to control execution. Second, we introduce priority-based scheduling as a way for the programmer to control the order in which processes run. We will explain these ideas one at a time as general concepts, then go on in the next sections to see how they are implemented in FreeRTOS.org.

To be able to take full advantage of the timer, we must change our notion of a process. We must, in fact, break the assumptions of our high-level programming language. We will create new routines that allow us to jump from one subroutine to another at any point in the program. That, together with the timer, will allow us to move between functions whenever necessary based upon the system’s timing constraints.

Figure 6.7 shows an example of preemptive execution of an operating system. We want to share the CPU across two processes. The kernel is the part of the operating system that determines what process is running. The kernel is activated periodically by the timer. The length of the timer period is known as the time quantum because it is the smallest increment in which we can control CPU activity. The kernel determines what process will run next and causes that process to run. On the next timer interrupt, the kernel may pick the same process or another process to run.

Figure 6.7 Sequence diagram for preemptive execution.

Note that this use of the timer is very different from our use of the timer in the last section. Before, we used the timer to control loop iterations, with one loop iteration including the execution of several complete processes. Here, the time quantum is in general smaller than the execution time of any of the processes.

How do we switch between processes before the process is done? We can’t rely on C-level mechanisms to do so. We can, however, use assembly language to switch between processes. The timer interrupt causes control to change from the currently executing process to the kernel; assembly language can be used to save and restore registers. We can similarly use assembly language to restore registers not from the process that was interrupted by the timer but to use registers from any process we want. The set of registers that defines a process is known as its context, and switching from one process’s register set to another is known as context switching. The data structure that holds the state of the process is known as the record.

How does the kernel determine what process will run next? We want a mechanism that executes quickly so that we don’t spend all our time in the kernel and starve out the processes that do the useful work. If we assign each task a numerical priority, then the kernel can simply look at the processes and their priorities, see which ones actually want to execute (some may be waiting for data or for some event), and select the highest priority process that is ready to run. This mechanism is both flexible and fast.

6.4.2 Processes and Context

The best way to understand processes and context is to dive into an RTOS implementation. We will use the FreeRTOS.org kernel as an example; in particular, we will use version 7.0.1 for the ARM7 AVR32 platform.

A process is known in FreeRTOS.org as a task.

Let us start with the simplest case, namely steady state: everything has been initialized, the operating system is running, and we are ready for a timer interrupt. Figure 6.8 shows a sequence diagram in FreeRTOS.org. This diagram shows the application tasks, the hardware timer, and all the functions in the kernel that are involved in the context switch:

Figure 6.8 Sequence diagram for a FreeRTOS.org context switch.

Here is the code for vPreemptiveTick() in the file portISR.c:

void vPreemptiveTick( void )

{

  /* Save the context of the current task. */

  portSAVE_CONTEXT();

  /* Increment the tick count - this may wake a task. */

  vTaskIncrementTick();

  /* Find the highest priority task that is ready to run. */

  vTaskSwitchContext();

  /* End the interrupt in the AIC. */

  AT91C_BASE_AIC->AIC_EOICR = AT91C_BASE_PITC->PITC_PIVR;;

  portRESTORE_CONTEXT();

}

The first thing that this routine must do is save the context of the task that was interrupted. To do this, it uses the routine portSAVE_CONTEXT(). vTaskIncrementTick() then performs some housekeeping, such as incrementing the tick count. It then determines which task to run next using the routine vTaskSwitchContext(). After some more housekeeping, it uses portRESTORE_CONTEXT() restores the context of the task that was selected by vTaskSwitchContext(). The action of portRESTORE_CONTEXT() causes control to transfer to that task without using the standard C return mechanism.

The code for portSAVE_CONTEXT(), in the file portmacro.h, is defined as a macro and not as a C function. Let’s look at the assembly code that is actually executed:

  push r0

  in   r0, __SREG__

  cli

  push r0

  push r1

  clr  r1

  push r2

; continue pushing all the registers

  push r31

  ldsr26, pxCurrentTCB

  ldsr27, pxCurrentTCB + 1

  inr0, __SP_L__

  stx+, r0

  inr0, __SP_H__

  stx+, r0

The context includes the 32 general-purpose registers, PC, status register, and stack pointers SPH and SPL. Register r0 is saved first because it is used to save the status register. Compilers assume that r1 is set to 0, so the context switch does so after saving the old value of r1. Most of the routine simply consists of pushing the registers; we have commented out some of those register pushes for clarity. Next, the kernel stores the stack pointer.

Here is the code for vTaskSwitchContext(), which is defined in the file tasks.c (minus some preprocessor directives that include some optional code):

void vTaskSwitchContext( void )

{

  if( uxSchedulerSuspended != ( unsigned portBASE_TYPE ) pdFALSE )

  {

    /* The scheduler is currently suspended - do not allow a context switch. */

    xMissedYield = pdTRUE;

  }

  else

  {

    traceTASK_SWITCHED_OUT();

    taskFIRST_CHECK_FOR_STACK_OVERFLOW();

    taskSECOND_CHECK_FOR_STACK_OVERFLOW();

    /* Find the highest priority queue that contains ready tasks. */

    while( listLIST_IS_EMPTY( &( pxReadyTasksLists[ uxTopReadyPriority ] ) ) )

    {

      configASSERT( uxTopReadyPriority );

      --uxTopReadyPriority;

    }

    /* listGET_OWNER_OF_NEXT_ENTRY walks through the list, so the tasks of the

    same priority get an equal share of the processor time. */

    listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &( pxReadyTasksLists [ uxTopReadyPriority ] ) );

    traceTASK_SWITCHED_IN();

    vWriteTraceToBuffer();

  }

}

This function is relatively straightforward—it walks down the list of tasks to identify the highest-priority task.

As with portSAVE_CONTEXT(), the portRESTORE_CONTEXT() routine is also defined in portmacro.h and is implemented as a macro with embedded assembly language. Here is the underlying assembly code:

  ldsr26, pxCurrentTCB

  ldsr27, pxCurrentTCB + 1

  ld r28, x+

  out__SP_L__, r28

  ld r29, x+

  out__SP_H__, r29

  popr31

; pop the registers

  popr1

  popr0

  out__SREG__, r0

  popr0

This code first loads the address for the new task’s stack pointer, then gets the stack pointer register values, and finally restores the general-purpose and status registers.

6.4.3 Processes and Object-Oriented Design

We need to design systems with processes as components. In this section, we survey the ways we can describe processes in UML and how to use processes as components in object-oriented design.

UML often refers to processes as active objects, that is, objects that have independent threads of control. The class that defines an active object is known as an active class. Figure 6.9 shows an example of a UML active class. It has all the normal characteristics of a class, including a name, attributes, and operations. It also provides a set of signals that can be used to communicate with the process. A signal is an object that is passed between processes for asynchronous communication. We describe signals in more detail in Section 6.6.

Figure 6.9 An active class in UML.

We can mix active objects and normal objects when describing a system. Figure 6.10 shows a simple collaboration diagram in which an object is used as an interface between two processes: p1 uses the w object to manipulate its data before the data is sent to the master process.

Figure 6.10 A collaboration diagram with active and normal objects.