Synchronization internals - the mutex -

Synchronization internals — the mutex


This two-part series addresses the use and misuse of two of the most essential synchronization primitives in modern embedded systems, the mutex  (this part) and the semaphore (part 2). Mutexes and semaphores are provided by most current RTOSs, although they can be implemented on bare-metal systems as well. Their use is considered a best practice among experienced firmware engineers, because they can make code more intuitive, leading to better maintainability, improved logic flow and higher productivity. If you’ve been using flags, variables and super loops to react to changes and control events in your code, read on to learn how skillful use of mutexes, semaphores and threads can improve your work.

Practically all desktop operating systems and most real-time operating systems (RTOSs) include APIs for manipulating mutexes and semaphores. They’re often referred to as synchronization objects because they can be used to coordinate or protect access to resources (i.e., variables, code sections, functions, hardware) among two or more threads of execution. They are also especially well-suited to manage triggers and signal events in an application. A thread of execution could be an interrupt service routine (ISR) or a traditional background process or task.

If you’re not using a modern RTOS (e.g., FreeRTOS, ChibiOS, MQX, uC/OS-III, ThreadX, QNX, Linux, etc.) in your firmware designs, consider incorporating one just to get access to these two important tools. They’re that useful!

A commonly held misconception is that a mutex is the same as a “binary” semaphore. To put it differently, the oft-quoted but incorrect belief is that a “counting” semaphore with an initial value of 1 is functionally the same as a mutex. The truth is actually quite different, and understanding the differences will enable you to produce programs that integrate better with your RTOS and avoid CPU waste.

Operation Primitives
In general, mutexes are used to protect individual resources. They function much like a lock, and have the concept of an owner. By contrast, semaphores contain a built-in counter and are typically used to coordinate access to one or more resources, or execution among two or more processes. A semaphore isn’t necessarily owned by a single process because it coordinates with two or more such processes. Because of the counter, semaphores are sometimes called counting semaphores . A semaphore which restricts its counter to 0 or 1 is known as a binary semaphore .

As suggested above, mutexes support just two basic operations, lock() and unlock(), which are self-explanatory. Semaphores are a bit more abstract, but similarly support just two major operations – take() (aka increment) and give() (aka decrement). For historical reasons, the semaphore take() operation is sometimes confusingly referred to by the capital letter “P”, and the give() operation by the capital letter “V”. You may see these abbreviations used in flowcharts and functional descriptions. We’ll delve into the meaning of take() and give() later in Part 2 of this series.

Inversion of Control
When dealing with an RTOS, it’s essential to understand that your code is not in charge. That’s right! You’re not in charge – you have no idea of when or if or for how long your code gets to run. The RTOS’s scheduler routine is the one calling the shots, which decides what code to run and when to run it.

Only one task at a time can run in a CPU core, and the scheduler coordinates access to it among multiple processes, or tasks. It allows tasks to temporarily execute for a short period, and then suspend so that other tasks can have a chance to execute. This is called a task switch . Because the scheduler is able to quickly suspend and resume the code of multiple tasks, using a high-speed timer called a system tick , it is able to give the appearance of simultaneous multitasking, something known as pre-emptive multitasking .

This leads to a concept known as inversion of control , which means that the scheduler is in charge of choosing when to suspend and resume your code as other tasks are quickly switched in and out. Using a variety of factors, such as task priority , the scheduler automatically decides what to run next. Mutexes and semaphores give us the ability to (a) conditionally suspend a task, and (b) influence how the scheduler chooses the next task to execute.

Next page >

The Problem of Multithreaded Access
With inversion of control in mind, envision a program with three separate functions that run a simple printf statement to the console (or serial port) within a loop, as in Figure 1 .

Figure 1

Func1 outputs “hello 1”, func2 outputs “hello 2” and func3 outputs “hello 3”, over and over. Now imagine that the RTOS API is used to run each function in their own separate tasks as threads. Because there is no synchronization among the three tasks, the console output will quickly become a jumbled mess — there’s no way of controlling when the scheduler suspends and resumes each task. It might choose to suspend task 1 while it is in the middle of printing “hello 2” for task 2, etc.

But imagine if the three functions were to be re-written to share access to the console? One way to accomplish that would be to create a global variable as a flag, such as console_in_use does in Figure 2 .

Figure 2

With a global flag, each task has the ability to check the flag and, if it’s false, quickly set it to true, output the string, then reset it back to false before looping. This is an improvement, and it seems like it would work but, it isn’t reliable and will still lead to jumbled output. The reason is because there’s nothing to stop the scheduler from randomly suspending one task just after it has checked the flag, but before the flag gets to true. The test and set operation doesn’t happen atomically . In such a situation, task 1 could correctly see that the flag is false and, just as it is ready to embark on the code path that would set the flag to true, it could be suspended by the scheduler and switch to task 2. At that point, task 2 examines the same flag, but because task 1 didn’t get to finish assigning the flag to true, it also appears as false to task 2. Now, both tasks 1 and 2 will think the flag is false, so both will attempt to output their strings to the console, causing another jumbled mess.

The problem is that we need a trustworthy method of examining and setting the flag if it’s false, regardless of how the scheduler chooses to perform its multitasking duties. There is a solution – the trusty mutex!

The Mutex
Remember what we learned about inversion of control, in which the scheduler is in charge of executing tasks and not the other way around? If we strategically place a call to the mutex lock() operation at the right point in each function, we can safely coordinate, or protect, access to the shared resource (the printf function). All we have to do is replace the “if ( ! console_in_use )” block with paired calls to lock() and unlock() the mutex, respectively.

Figure 3 contains C code written for the Freescale MQX RTOS. In it, the new program coalesces the three print functions into a single print_task() routine. The main() function launches the RTOS and the main_task() function, which creates three separate instances of print_task() as threads, using the initial_data parameter to pass a unique pointer to each one.

Figure 3

The print_task() function is able to output its messages perfectly, without interrupting or interleaving text with either of the other two tasks that are also running. This works because the mutex lock function is tightly integrated with the RTOS. It has the useful ability to atomically cause the scheduler to examine the mutex variable to see if it is already locked (or, “owned”) by another task and , if so, to suspend the active task until the lock becomes available. Otherwise, the currently executing task becomes the owner of the mutex and execution is allowed to proceed, normally. The code being protected is the printf() statement, because it lies between the lock and unlock calls. This is also known as a critical section .

How a Mutex Works
Many things in computing are about list-keeping, and mutexes are no different internally. For each mutex, the RTOS maintains a list of task IDs that are all suspended, waiting on a chance to grab the lock (because they’ve called the blocking mutex lock() API function) and resume execution. This is called the wait list . If the wait list is empty, our task can immediately take ownership of the lock, allowing the lock() function to return and execution to continue.

However, if the wait list is not empty, it means that other tasks are already waiting in line. So, our task will be suspended and added to the wait list while the scheduler goes about selecting and running other tasks. Our task will remain suspended until whatever task owns it calls the unlock function. This process is called blocking because, from the point of view of our code, the lock() call on the mutex will not return until the scheduler unblocks our task. This form of blocking turns out to be a very efficient method of avoiding wasted CPU cycles in threaded code, because the scheduler will automatically avoid blocked tasks until they become unblocked. It’s also the reason, however, that mutexes should not be used within ISRs . ISRs must get in and get out, quickly, so they can’t call blocking code. For this and other reasons, it’s important to know when to use a mutex or, as shown in Part 2, a semaphore.

At some point, if our code is written correctly, the specific task that holds the locked mutex will finish its duties with the protected resource and finally call the mutex unlock() function. When that happens, the RTOS will remove one of the suspended task IDs from the wait list and mark it as eligible to resume execution, and the whole process repeats.

To recap, mutexes are great for coordinating multiple accesses to a single shared resource, such as an output port, or an important section of code that shouldn’t be executed by more than one task at a time. The code in Figure 3 showed how a mutex can be used to coordinate access to a critical section of code to safely printf to the console, while taking advantage of the RTOSs ability to suspend waiting tasks so that they don’t waste CPU cycles.

In Part 2, we look at the basic operations and usage of semaphores. 

David Cecil holds degrees in electrical engineering and computer engineering from Georgia Tech, and is Director of Engineering at USA Firmware in Cleveland, OH. He is an advocate for using C++, software patterns and other object-oriented techniques in embedded systems, and can be reached by email at .

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.