Real-Time Operating Systems for DSP, part 5

In part 4, we introduced the concept of mutual exclusion. Mutual exclusion ensures that a shared variable can only be manipulated or modified by one thread at a time. That is, any time one thread is modifying the variable, all other threads are excluded from access. In this article, we look at a variety of methods for achieving mutual exclusion.

Mutual Exclusion via Interrupt Control
One approach to mutual exclusion is proactively to take steps to prevent the task that is accessing a shared resource or otherwise executing in a critical section from being interrupted. Disabling interrupts is one approach. The programmer can disable interrupts prior to entering the critical section, and then enable interrupts after leaving the critical section:

This approach is useful because no clock interrupts occur and the process has exclusive access to the CPU and cannot be interrupted by any other process. The approach is simple and efficient.

There are some significant drawbacks to the approach. Disabling interrupts effectively turns off the preemptive scheduling ability of your system. Doing this may adversely affect system performance. The more time spent in a critical section with interrupts turned off, the greater the degradation in system latency. If the programmer is allowed to disable interrupts at will, he or she may easily forget to enable interrupts after a critical section. This leads to system hangs that may or may not be obvious. This is a very error prone process and, without the right programmer discipline, could lead to significant integration and debug problems. Finally, this approach works for single processor systems but does not work for multiprocessor systems.

RTOSs provide primitives to help a programmer manage critical sections without having to resort to messing with the system interrupts.

Mutual Exclusion with a Simple Semaphore
In its simplest form, a semaphore is just a thread safe flag that is used to signal that a resource is "locked." Most modern instruction sets include instructions that are especially designed to so that they can be used as a simple semaphore. The two most common suitable instructions are test and set instructions and swap instructions. The critical feature is that the flag variable must be both tested and modified as a single, atomic operation.

Note that "semaphore" is often used to mean something more complex than a simple thread-safe flag. That's because the "semaphore" service offered by many operating systems is a special, more complex (to implement at least) form of semaphore (technically a "blocking semaphore") which automatically suspends the waiting process if the requested resource is not busy. I'll discuss how to use blocking semaphores in the next section.

The most primitive technique for synchronizing on a critical section is called busy waiting. In this approach, a task sets and checks a shared variable (a simple semaphore) that acts as a flag to provide synchronization. This approach is also called spinning with the flag variables called spin locks. To signal a resource (use that resource), a task sets the value of a flag and proceeds with execution. To wait for a resource, a task checks the value of the flag. If the flag is set, the task may proceed with using the resource. If the flag is not set, the task will check again.

The disadvantages of busy waits are that the tasks spend processor cycles checking conditions without doing useful work. This approach can also lead to excessive memory traffic. Finally, it can become very difficult to impose queuing disciplines if there is more than one task waiting on a condition. To work properly, the busy wait must test the flag and set it if the resource is available, as a single atomic operation. Modern architectures typically include an instruction designed with this operation in mind.

Test and set instruction
The test and set instruction is atomic by hardware design. This instruction allows a task to access a memory location in the following way:

• If the bit accessed is a 0 then set it to 1 and return 0.
• If the bit is 1 return 1. The pseudocode for this operation is as follows:

The task must test the location for 0 before executing a wait. If the value is 0 then the task may proceed. If it is not a 0, then the task must wait. After completing the operation, the task must reset the location to 0.