Michael Barr - Programming Embedded Systems in C and C++

Figure 8-3. A context switch

Though we frequently talk about the tasks in a multitasking operating system as completely independent entities, that portrayal is not completely accurate. All of the tasks are working together to solve a larger problem and must occasionally communicate with one another to synchronize their activities. For example, in the printer-sharing device the printer task doesn't have any work to do until new data is supplied to it by one of the computer tasks. So the printer and computer tasks must communicate with one another to coordinate their access to common data buffers. One way to do this is to use a data structure called a mutex.

Mutexes are provided by many operating systems to assist with task synchronization. They are not, however, the only such mechanism available. Others are called semaphores, message queues, and monitors. However, if you have any one of these data structures, it is possible to implement each of the others. In fact, a mutex is itself a special type of semaphore called a binary, or mutual-exclusion, semaphore.

You can think of a mutex as being nothing more than a multitasking-aware binary flag. The meaning associated with a particular mutex must, therefore, be chosen by the software designer and understood by each of the tasks that use it. For example, the data buffer that is shared by the printer and computer task would probably have a mutex associated with it. When this binary flag is set, the shared data buffer is assumed to be in use by one of the tasks. All other tasks must wait until that flag is cleared (and then set again by themselves) before reading or writing any of the data within that buffer.

We say that mutexes are multitasking-aware because the processes of setting and clearing the binary flag are atomic. That is, these operations cannot be interrupted. A task can safely change the state of the mutex without risking that a context switch will occur in the middle of the modification. If a context switch were to occur, the binary flag might be left in an unpredictable state and a deadlock between the tasks could result. The atomicity of the mutex set and clear operations is enforced by the operating system, which disables interrupts before reading or modifying the state of the binary flag.

ADEOS includes a Mutex class. Using this class, the application software can create and destroy mutexes, wait for a mutex to be cleared and then set it, or clear a mutex that was previously set. The last two operations are referred to as taking and releasing a mutex, respectively.

Here is the definition of the Mutex class:

class Mutex {

public:

Mutex();

void take(void);

void release(void);

private:

TaskList waitingList;

enum { Available, Held } state;

};

The process of creating a new Mutex is simple. The following constructor will be executed automatically each time a new mutex object is instantiated:

/**********************************************************************

*

* Method: Mutex()

*

* Description: Create a new mutex.

*

* Notes:

*

* Returns:

*

**********************************************************************/

Mutex::Mutex() {

enterCS(); ////// Critical Section Begin

state = Available;

waitingList.pTop = NULL;

exitCS(); ////// Critical Section End

} /* Mutex() */

All mutexes are created in the Available state and are associated with a linked list of waiting tasks that is initially empty. Of course, once you've created a mutex it is necessary to have some way to change its state, so the next method we'll discuss is take . This routine would typically be called by a task, before it reads or writes a shared resource. When the call to take returns, the calling task's exclusive access to that resource is guaranteed by the operating system. The code for this routine is as follows:

/**********************************************************************

*

* Method: take()

*

* Description: Wait for a mutex to become available, then take it.

*

* Notes:

*

* Returns: None defined.

*

**********************************************************************/

void Mutex::take(void) {

Task * pCallingTask;

enterCS(); ////// Critical Section Begin

if (state == Available) {

//

// The mutex is available. Simply take it and return.

//

state = Held;

waitingList.pTop = NULL;

} else {

//

// The mutex is taken. Add the calling task to the waiting list.

//

pCallingTask = os.pRunningTask;

pCallingTask->state = Waiting;

os.readyList.remove(pCallingTask);

waitingList.insert(pCallingTask);

os.schedule(); // Scheduling Point

// When the mutex is released, the caller begins executing here.

}

exitCS(); ////// Critical Section End

} /* take() */

The neatest thing about the take method is that if the mutex is currently held by another task (that is, the binary flag is already set), the calling task will be suspended until the mutex is released by that other task. This is kind of like telling your spouse that you are going to take a nap and asking him or her to wake you up when dinner is ready. It is even possible for multiple tasks to be waiting for the same mutex. In fact, the waiting list associated with each mutex is ordered by priority, so the highest-priority waiting task will always be awakened first.

The method that comes next is used to release a mutex. Although this method could be called by any task, it is expected that only a task that previously called take would invoke it. Unlike take , this routine will never block. However, one possible result of releasing the mutex could be to wake a task of higher priority. In that case, the releasing task would immediately be forced (by the scheduler) to give up control of the processor, in favor of the higher-priority task.

/**********************************************************************

*

* Method: release()

*

* Description: Release a mutex that is held by the calling task.

*

* Notes:

*

* Returns: None defined.

*

**********************************************************************/

void Mutex::release(void) {

Task * pWaitingTask;

enterCS(); ////// Critical Section Begins

if (state == Held) {

pWaitingTask = waitingList.pTop;

if (pWaitingTask != NULL) {

//

// Wake the first task on the waiting list.

//

waitingList.pTop = pWaitingTask->pNext;

pWaitingTask->state = Ready;