Home > Mutual Exclusion > Exclusion Is Not Always Mutual

Exclusion Is Not Always Mutual

Saturday, June 26, 2010 Leave a comment Go to comments

Most embedded software practitioners – sadly, not all – know that some form of what is normally called “Mutual Exclusion” is necessary when a read-write resource is shared among two or more concurrent activities, particularly (but not necessarily only) when test-and-set operations are involved. The expression “Mutual Exclusion” is so entrenched as a generic concept that I feel obliged to use it as such, but sometimes it is anything but mutual. To illustrate this, some situations are described below, in terms of the types of activities contending for a resource:-

The contending activities are all tasks (threads) in an RTOS-based system

This is the situation about which most has been written. The usual approach is to require each contending task to lock a specified “mutex” before accessing the shared resource, and to release the mutex when it has finished with the resource. Because only one task at a time may lock (or hold) the mutex, a task trying to lock a mutex held by another task is forced to wait until the holding task has released it before proceeding to access the resource. These are the principles but there is more to consider (such as priority inversion) than I intend to get into just now. The point to be made here is that the mutex provides exclusion which is truly mutual. The mutex protocol requires that each and every task needing access to the associated resource lock and release the mutex in an identical manner; the protocol treats the contending tasks as peers in this respect.

There is another, somewhat draconian but much faster way to deal with this situation, and that is to disable scheduling altogether while the shared resource is accessed. This is sometimes provided as an option at application level but it is essential within the RTOS kernel, which must be able to disable scheduling occasionally. How else would it deal, for example, with its own mutex objects, which are themselves shared resources?

At least one of the contending activities is an interrupt service routine (ISR)

This situation can occur in either a single-threaded program or a multi-threaded one. In the latter case, the mutex described above will probably be available but it is useless here. Let me re-state that, because it is important: an RTOS mutex cannot be used to protect a shared resource from an ISR! This is because an ISR must run to completion without blocking and this disallows it from participating in the mutex protocol. Whether we’re using an RTOS or not, we need another mechanism to deal with contending ISRs and that mechanism is simply to ensure that the relevant interrupts are disabled before any non-interrupt code accesses the shared resource. Of course, the original interrupt states (whether enabled or disabled) must be restored afterwards. Likewise, an ISR must disable and restore any higher-level contending interrupts, and so on. This kind of exclusion is asymmetrical, not mutual; once an ISR starts, it will do its worst, so it must be prevented from running whenever it might adversely affect whatever the (normally) interruptible code is trying to do.

Because it is easier (and arguably safer, in some respects), it is common to disable all interrupts, not just the contending ones. If this is done in an RTOS-based system, it also goes a long way towards stopping contention from other tasks, as without an interrupt no involuntary pre-emption can take place. Assuming that no task voluntarily causes itself to be swapped out while dealing with the shared resource, there is no need to implement mutex protection as well. But then again, perhaps that is an assumption too far…

We are contending with the hardware (e.g. a peripheral or an FPGA)

When we access a hardware register, we generally treat it as memory. However, the hardware itself will read and/or write this register too, so again we are dealing with a shared resource. Very often there is nothing special we need to do in our software because the hardware serialises the data for us by deferring its data updates while a bus access is in progress, or by deferring our access with wait states while it completes its own operations, or by some other transparent means. Sometimes, though, we have to poll a “ready” flag or read/write data only in response to an interrupt. Whatever we have to do will be documented, so, as the Great Sage once said, “RTFM”.

Contending tasks may be running on other processors

If single-processor multi-tasking seems like a bag of worms then multi-processor multi-tasking is most prudently viewed as a bag of snakes. Ironically, the more complex kind of multi-processing (the symmetric kind, SMP) is, for most people, the easier to deal with because the operating system which is inevitably present hides all the tricky bits. For mutual exclusion, just use its mutex objects, as before, and all should be well.

Asymmetric systems, in which different processors run specialised software to do different jobs, have been common for some time. They tend to be “home grown”, as the configuration usually depends heavily upon the particular system requirements. If the processors communicate exclusively by message-passing (through high-speed serial links, for example), shared memory is not needed and neither therefore is the mutual exclusion to go with it. Put some multi-port shared memory in there, and your troubles are just beginning! Just like the designers of SMP operating systems, you’ll find yourself exposed to the marvels of atomic test-and-set instructions and spin-locks. Well, OK, maybe it’s not that hard, but it’s a subject for another day, nevertheless.

Important footnote

If you’re using C or C++, don’t forget to make your shared stuff volatile. That’s all shared memory, not just hardware registers!

Categories: Mutual Exclusion
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: