As hopefully you can see from the previous posting, the mutex is a significantly safer mechanism to use for implementing mutual exclusion around shared resources. Nevertheless, there are still a couple of problems that use of the mutex (in preference to the semaphore) will not solve. These are:
- Circular deadlock
- Non-cooperation
Circular Deadlock
Circular deadlock, often referred to as the “deadly embrace” problem is a condition where two or more tasks develop a circular dependency of mutual exclusion. Simply put, one task is blocked waiting on a mutex owned by another task. That other task is also block waiting on a mutex held by the first task.
So how can this happen? Take as an example a small control system. The system is made up of three tasks, a low priority Control task, a medium priority System Identification (SI) task and a high priority Alarm task. There is an analogue input shared by the Control and the SI tasks, which is protected by a mutex. There is also an analogue output protected by a different mutex.
The Control task waits for mutexes ADC and DAC:
mutex_lock (DAC);
/* critical section */
mutex_unlock (ADC);
mutex_unlock (DAC);
The SI Task waits for mutexes DAC and ADC:
mutex_lock (DAC);
mutex_lock (ADC);
/* critical section */
mutex_unlock (DAC);
mutex_unlock (ADC);
Unfortunately, under certain timing conditions, this can lead to deadlock. In this example the Control task has locked the ADC, but before locking the DAC has been pre-empted by the higher priory SI task. The SI task then locks the DAC and tries to lock the ADC. The SI task is now blocked as the ADC is already owned by the Control task. The Control task now runs and tries to lock the DAC. It is blocked as the DAC is held by the SI task. Neither task can continue until the mutex is unlocked and neither mutex can be unlocked until either task runs – classic deadlock.
For circular deadlock to occur the following conditions must all be true:
- A thread has exclusive use of resources (Mutual exclusion)
- A thread can hold on to a resource(s) whilst waiting for another resource (Hold and wait)
- A circular dependency of thread and resources is set up (Circular waiting)
- A thread never releases a resource until it is completely finished with it (No resource preemption)
These conditions can be addressed in a number of ways. For example, a design policy may stipulate that if a task needs to lock more than one mutex it must either lock all or none.
With the Priority Ceiling Protocol (PCP) method each mutex has a defined priority ceiling, set to that of the highest priority task which uses the mutex. Any task using a mutex executes at its own priority – until a second task attempts to acquire the mutex. At this point it has its priority raised to the ceiling value, preventing suspension and thus eliminating the “hold and wait” condition.
In the deadlock example shown before, the significant point is when the SI task tries to lock the DAC. Before that succeeded and lead to cyclic deadlock. However with a PCP mutex, both the ADC and DAC mutex will have a ceiling priority equal to the SI’s task priority. When the SI task tries to lock the DAC, then the run-time system will detect that the SI’s task priority is not higher than the priority of the locked mutex ADC. The run-time system suspends the SI task without locking the DAC mutex. The control task now inherits the priority of the SI task and resumes execution.
The last, but most important aspect of mutual exclusion covered in these ramblings relies on one founding principle: we have to rely on all tasks to access critical regions using mutual exclusion primitives. Unfortunately this is dependent on the design of the software and cannot be detected by the run-time system. This final problem was addressed by Tony Hoare, called the Monitor.
The monitor is a mechanism not typically supplied by the RTOS, but something the programmer tends to build (a notable exception is Ada95’s protected object mechanism). A monitor simply encapsulates the shared resource and the locking mechanism into a single construct (e.g. a C++ Object that encapsulates the mutex mechanism). Access to the shared resource, then, is through a controlled interface which cannot be bypassed (i.e. the application never explicitly calls the mutex, but calls upon access functions).
Finishing Off…
This goal of these initial postings is to demonstrate that common terms used in the real-time programming community are open to ambiguity and interpretation. Hopefully you should now be clear about the core differences between the Binary Semaphore, General (counting) Semaphore and the Mutex.
The underlying difference between the Semaphores and the Mutex is the Principle of Ownership. Given the principle of ownership a particular implementation of a mutex may support Recursion, Priority inheritance and Death Detection.
ENDNOTE
An aspect of the mutex I haven’t covered here is that many operating systems support the concept of a condition variable. A condition variable allows a task to wait on a synchronization primitive within a critical region. The whole aspect Synchronization Patterns (e.g. semaphore as a signal) within the context of RTOSs will be the subject of my next posting.
Niall has been designing and programming embedded systems for over 30 years. He has worked in different sectors, including aerospace, telecomms, government and banking.
His current interest lie in IoT Security and Agile for Embedded Systems.
- Navigating Memory in C++: A Guide to Using std::uintptr_t for Address Handling - February 22, 2024
- Embedded Expertise: Beyond Fixed-Size Integers; Exploring Fast and Least Types - January 15, 2024
- Disassembling a Cortex-M raw binary file with Ghidra - December 20, 2022
Co-Founder and Director of Feabhas since 1995.
Niall has been designing and programming embedded systems for over 30 years. He has worked in different sectors, including aerospace, telecomms, government and banking.
His current interest lie in IoT Security and Agile for Embedded Systems.
Neil,
You remind me of grad school professor, but you are better. He always taught us the theory without telling us practically where it is used.
Now with this article of yours, I really understand now how things work. Thanks for general concepts.
Cheers,
Venu
Your description of the Priority Ceiling Protocol is incorrect. What you describe is more similar to PCP *Emulation* (also called the Priority Protect Protocol in POSIX).
Real PCP doesn't raises the task's priority to the blocked task's priority (not the ceiling). It uses the ceiling to block a task on a wait/lock operation of a mutex if the locking task has a lower priority than the current priority ceiling (highest ceiling of any currently locked mutex), even if the mutex was available.
It's complex, which is why the version you state is more commonly seen.
A nice lucid explanation about semaphore, mutex concepts with regard to RTOS. I recommend this for novice as well as experts.
Pingback: Mutex Vs Semaphore « Roshan Singh
Amazing articles on mutex, semaphores and deadlocks .. thanks mate !!
i'd recommend this link to a lot of people getting started in this field.
Really nice article. Was looking in many books, but no clear explanations.
Hi,
Good article though. By this article I understand that only the owner of the mutex can release the mutex.
Is there no ownership concept in case of binary semaphore???
Guys... Please clarify me on this.
Thanks.
Hi BB, if you carefully reread the article, you should see that the weakness of the semaphore is that it does not have ownership. Thanks.
Pingback: Multithreading, mutex, semaphore | Agnihotri
Pingback: mutex vs semaphore | technoless
I'm well aware of the common misconception that a mutex is a binary sempahore, and blood can flow if you try to explain otherwise.
Here's my question. What is the point of a counting non binary mutex. A mutex with an initial value of 3 can be used to allow 3 processes into the critical section blocking the fourth and subsequent processes, until one of the first 3 exits the critical section, and releases/unlocks/returns the mutex.
Now I cannot imagine ANY programming scenario where it makes sense for more than 1 process to be in the critical section. It is academically interesting that you can allow multiple processes into the critical section BUT HAS NO USEFUL application.
If this is true, then we only need binary semaphores. Binary semaphores for process synchronisation, and binary mutexes, which are of course restricted binary sempahores for mutual exclusion???
Actually I mean we only need binary mutexes, but still need counting semaphores.
I'm using a counting semaphore in a current project. A task's DoRun() waits on a sempahore. This semaphore is released either from an interrupt handler, or because a task sent it a message. Flags tell the task if it is servicing hardware or processing messages. In particular while servicing the hardware it might send itself messages.
So the semaphore count often reaches 3 or even higher.
However the count of 3 does not mean 3 tasks may run, it means it should loop 3 times through DoRun, processing 1 interrupt and 2 messages.
So we need counting semaphores, and binary mutexes, where the mutex is a semaphore that must be released by the same task that took it.
Hi Francis,
I agree with your position that, ideally, a binary semaphore is not needed in the context of mutual exclusion and resource management.
However, many RTOSs and programmers still use the binary semaphore for signalling ("Semaphore-as-a-Signal" pattern) where the OS doesn't offer alternative/better synchronisation primitives (e.g. event flags or a signalling object).
Check out the blog entry on synchronisation ( https://feabhasblog.wpengine.com/2009/10/task-synchronisation/ ) which discusses this in more detail.
Niall.
Niall, You have me backwards. I say a counting Mutex not needed for mutual exclusion and resource management. Binary mutex all that is needed.
But a counting semaphore is needed for process synchronisation. Anything like event, or messages will be built on top of a semaphore.