TiROS Documentation

Mutual Exclusion (Mutex)

TiROS supports mutual exclusion (Mutex) mechanisms to provide tasks with synchronized access to shared resources.

In an embedded system, mutexes have to be used with care. Mutexes are subject to priority inversion and deadlock. Real-time operating systems implement algorithms to deal with these problems. All implementations are not alike. The system designer must be cognizant of the limitations of the alorithms and the limitations of a particular implementations. TiROS supports two algorithms to deal with mutexes: Cascaded priority inheritance with delayed fallback and Immediate Priority Ceiling Protocol. The following sections are provided so that the system designer can have a good understanding of mutexes, their implementations in TiROS, and the associated limitations:

  1. What is a Mutex?
  2. Mutexes vs. Critical Sections.
  3. Pitfalls of mutexes.
  4. Priority Inheritance Protocol.
  5. Priority Ceiling Protocol.
  6. Rules for using mutexes in TiROS.
The TiROS API for management of mutexes is provided in the Mutexes section of the API description.

What is a Mutex?

Mutexes are used by a task to provide exclusive access to a shared resource. Mutexes can be used in systems where multiple tasks/threads/processes compete to use the same resources. It is illustrated below: 
    void task1(void) {
             char *ch;
             ch = malloc(100);  // Allocate 100 bytes.
                                // malloc on most embedded systems
                                // is not thread-safe (re-entrant).
                                // It may be possible that task1 is
                                // preempted in the middle of the
                                // malloc and task2 runs and invokes
                                // malloc,
                                // resulting in memory inconsistencies.
             do_stuff(ch);
             free(ch);          // free releases memory. free and
                                // malloc work together. So they both
                                // have to be protected from
                                // concurrent access.
    }

    void task2(void) {
             char *ch2;
             ch2 = malloc(50);
             do_other_stuff(ch2);         
             free(ch2);
    }
The example uses malloc as a shared resource, but it is applicable for any shared resource, such as serial ports, shared data, etc. In a system with concurrent tasks, these shared resources should be protected from concurrent use. To protect a shared resource, a mutex is associated with it. To use the shared resource, a task locks the mutex. If another task find the mutex locked, it has to wait for the mutex to be unlocked. Then it can lock the mutex and use the shared resource.

Using mutexes, the code would be replaced with: 

    mutex mem_mutex;           // Also do appropriate initialization
                               // at startup
    void task1(void) {
             char *ch;
             lock(mem_mutex);  // locking memory allocation routine
             ch = malloc(100);
             unlock(mem_mutex);  // unlocking

             do_stuff(ch);

             lock(mem_mutex);   //locking
             free(ch);          // Free should also be protected.
             unlock(mem_mutex); //unlocking
    }

    void task2(void) {
             char *ch2;
             lock(mem_mutex);   // If mem_mutex is already locked,
                                // then this task will wait here
                                // until it is unlocked. 
             ch2 = malloc(50);
             unlock(mem_mutex);

             do_other_stuff(ch2);         

             lock(mem_mutex);
             free(ch2);
             unlock(mem_mutex);
    }

Mutexes can be implemented in many ways (In the simplest case, it could be a global interrupt disable and enable). All implementations are not alike. To design reliable systems, the user of a real-time operating system should have a knowledge of the limitations of the operating system mutex implementation.

The following sections explain the different types of mutex implementations and their limitations. Figures showing task scheduling with mutexes are used to illustrate mutex properties. The legend for the illustrations is given below.

Legend for mutex diagrams

Mutexes vs. Critical Sections

The simplest implementation of a mutex would be to disable global interrupts on mutex lock and restore it on unlock. Simple and fast as it is, it has the undesirable effect of blocking high priority tasks that do not need to be blocked and increasing interrupt response latency. The figure below illustrates this.

Scenario 1: Mutex implementation with interrupt enable/disable

  1. Low priority task, J2 is running at time, t0.
  2. At time t1, J2 acquires a lock on mutex, M.
  3. At time t2, higher priority task, J1, ought to be waking up for execution. However, since the implementation disables interrupts, it stays blocked.
  4. At time t3, an interrupt is delivered. However, since interrupts are disabled, the interrupt is not serviced at this time.
  5. At time t4, J2 gives up its lock on the mutex and the interrupt state is reenabled. At this time, the interrupt service routine can run.
  6. Finally, at time t5, when the ISR is done, higher priority task, J1 can run.
This implementation has the undesirable effect of blocking higher priority tasks and also interrupt routines. In some situations, where the mutex is held for very short periods of time, this may be suitable.In TiROS, this can be achieved using Critical Sections.

For the rest of the discussion, we will restrict ourselves to mutex implementations that do not block interrupts or other high priority tasks. A better mutex implementation of the previous scenario will look as shown in the next figure.

The non-trivial Mutex implementation of Scenario 1.

  1. Low priority task, J2 is running at time, t0.
  2. At time t1, J2 acquires a lock on mutex, M.
  3. At time t2, higher priority task, J1, wakes up and runs.
  4. At time t3, J1, tries to lock M, but is blocked because M has already been blocked by J2.
  5. At time t4, an interrupt is delivered. The ISR runs.
  6. At time t5, the ISR is complete and J2 resumes.
  7. At time t6, J2 releases the lock on M. J1 can now lock M and continue.
  8. At time t7, J1 releases the lock on M.
  9. At time t8, J1 yields control (or goes to sleep) and J2 is free to run.
Note that interrupts are not delayed by the task holding the lock.

Pitfalls of mutexes

Priority Inversion

Consider a system with three tasks: J0, J1, J2. The priorities for these tasks are P0, P1, P2, where P0 > P1 > P2. J2 is the lowest priority task. Consider the following situation:

Scenario 2: Priority Inversion.

  1. At time t1, low priority task, J2 acquires mutex, M.
  2. At time t2, high priority task, J0, wakes up and runs.
  3. At time t3, J0 tries to lock M but has to wait because it has already been locked by J2..
  4. At time t4, medium priority task, J1,starts running a long computation. The low-priority task, J2, cannot complete because J1 is running. Since J2, cannot finish and unlock the mutex, high-priority task J0, is indirectly blocked.
  5. At time t5, J1, goes to sleep and low priority task J2 is able to run.
  6. At time t6, J2, gives up the lock, this enables J0 to acquire the lock and J0 runs.
Effectively, the high-priority task, J0, is blocked by medium-priority task J1. This condition is called priority-inversion. This is not desirable in a real-time system because the priority-inversion may be unbounded. There are two primary techniques to solve priority-inversion.

Deadlock

A deadlock is a condition where two or more tasks are waiting on each other to finish. None of the tasks can advance. Consider this simple scenario illustrated in the figure below:

Scenario 3: Deadlock.

  1. At time t1, low priority task, J1 acquires mutex, M1.
  2. At time t2, high priority task, J0, wakes up and runs.
  3. At time t3, J0 locks mutex M2.
  4. At time t4, J0 tries to lock mutex M1 but has to wait because it has already been locked by J1.
  5. At time t5, J0 tries to lock mutex M2 that is already locked by J1. Now, task J0 is waiting on J1 and J1 is waiting on J0. Neither task can progress. They are deadlocked.
In a simple system, deadlocks can be avoided by careful design rules (Example: a given set of mutexes should always be acquired in the same time sequence by any task). In a complex system where many library functions internally use mutexes, this can be more difficult. The Priority Ceiling Protocol can prevent deadlocks.

Priority Inheritance Protocol

The priority inheritance protocol prevents priority inversion by temporarily raising the priority of the task holding the mutex. Its priority is raised to the priority of the task that is waiting on the mutex, if that is greater. The priority inheritance prevents Priority Inversion as follows.

Priority Inheritance prevents the priority inversion in Scenario 2.

  1. At time t1, low priority task, J2 acquires mutex, M.
  2. At time t2, high priority task, J0, wakes up and runs.
  3. At time t3, J0 tries to lock M but has to wait because it has already been locked by J2. Since high priority task J0 is now waiting on J2, the priority of J2 is temporarily raised to that of J0.
  4. At time t4, medium priority task, J1, wakes up. However, it cannot run because J2 is running with the priority of J0 which is higher than that of J1. J1 is kept waiting.
  5. At time t5, J2 releases its lock on the mutex. Its priority reverts back to its original priority. Now that J2 has released its lock, J0 which has been waiting for this can acquire the lock. J0 runs because it is the highest priority task that is now "runnable".
  6. At time t6, J0, gives up the lock. Now, medium priority task, J1, which has been waiting can run its long computation.

In a situation with multiple mutexes, this can become more complicated. Most real-time operating systems do not implement the full priority inheritance protocol but instead implement an approximation to it. We describe some of the practical implementations of priority inheritance used in embedded real-time operating systems.

Simple priority inheritance (no support for multiple mutexes)

The previous example showed a mutex implementation that works well in a simple case. But consider the following case, where multiple mutexes are involved.

Scenario 4: Simple PIP is insufficient for multiple mutexes.

  1. At time t1, low priority task, J3 acquires mutex, M1.
  2. At time t2, J2 wakes and runs.
  3. At time t3, J2 locks mutex M2.
  4. At time t4, J2 attempts to lock mutex, M1. J2 is blocked. J3 starts running with the priority of J2.
  5. At time t5, J0 wakes and runs.
  6. At time t6, J0 attempts to lock mutex M2. M2 is already locked by J2. J0 is blocked and the priority of J2 is raised to that of J0. However since J2 is already blocked on another mutex M1, this has no effect. J3 continues to run at the priority of J2.
  7. At time t7, J1 wakes up and runs, preempting J2. Now J0 is effectively blocked by J1 which is running a long computation.
This is problematic because J1 can run for an arbitrarily long period of time, leading to unbounded priority inversion. In this case, it is not sufficient to raise the priority of J2. As J2 is blocked on yet another mutex, M1, we have to follow the chain of mutexes and raise the priority of J3, which is the owner of mutex M1. This is what is done by the full priority inheritance protocol.

Full cascaded priority inheritance protocol

As opposed to the previous scenarion, the full priority inheritance protocol has to operate correctly on a chain of blocked tasks, each waiting on a mutex held by a previous task in the chain. The previous scenario (Scenario 4) is repeated, this time using the full cascased priority inheritance protocol. It is illustrated in the following figure.

Scenario 4: Full PIP: Priority is transitive across locks.

The priority inheritance protocol is simple to describe but complicated to implement in full. Conditions such as nested mutexes, and arbitrary arrival of high-priority tasks have to be considered. In practice, very few operating systems implement the full priority inheritance protocol for the following reasons: For the full PIP, the effective priority of a task is always recomputed in the following case: This is described in Scenario 5 below.

Scenario 5: Relinquishing priority with full PIP.

  1. At time t1, low priority task, J3 acquires mutex, M1.
  2. At time t2, J2 wakes and runs.
  3. At time t3, J2 attempts to lock mutex M1, but is blocked. The priority of J3 is raised to that of J2.
  4. At time t4, J3 has locked mutex M2.
  5. At time t5, J1 wakes and runs, thus preempting J3.
  6. At time t6, J1 attempts to lock mutex M2 which is locked by J3. It is blocked. This raises the priority of J3 to that of J1.
  7. At time t7, J0 wakes, preempts J3.
  8. At time t8, J0 blocks on M2. The priority of J3 is now raised to that of J0.
  9. At time t9, J3 releases the lock on M2. Its priority is decreased to that of J2, because J2 is still waiting for mutex M1 which is still locked by J3. Now J0 can finish its lock on M2.
  10. At time t10, J0 releases its lock on M2.
  11. At time t11, J0 goes to sleep. The next highest priority task is J1 which is now also allowed to complete its lock on M2.
  12. At time t12, J1 releases M2.
  13. At time t13, J1 goes to sleep. Now J3 continues running at the priority of J2.
  14. At time t14, J3 releases its lock. Its priority is lowered to its original priority. Now J2 is the highest priority runnable task. J2 is now allowed to complete its lock on M1.
  15. At time t15, J2 releases M1.

Cascaded priority inheritance with delayed fallback

This is an approximation to the full priority inheritance protocol. The difference between this approximate algorithm and the full algorithm is the effect upon the effective priority of a task when a lock is released.

The effective priority is only lowered when there are no more mutexes held by the task. This modified algorithm is much simpler to implement than the full protocol. It requires much less state, memory, and overhead. In practice, most systems that implement priority inheritance implement the modified algorithm. The behavior of the modified algorithm with Scenario 5 is described below.

Scenario 5: Cascaded priority inheritance with delayed fallback.

  1. At times t0-t8, the behavior is the same as that of the full PIP.
  2. At time t9, J3 releases the lock on M2. In this approximate algorithm, its priority is not immediately decreased. Note, that now there are two tasks with the same priority (J3 and J0). Depending on the specifics of the task scheduler for the operating sytem, either one of these tasks may continue running. It may be preferable to have task J0 continue because it is at a higher priority task than J3. On the other hand, swithching a task involves a context-switch overhead. Either implementation is correct because mutexes are assumed to hold a resource for only short periods of time. And in any case, there is no unbounded priority inversion. For this case, we choose J0 as the task to continue.

  3. At time t10, J0 releases the lock on M2.
  4. At time t11, J0 goes to sleep. The highest priority task is J3, which has the effective priority of J0. J3 runs.
  5. At time t12, J3 releases its lock on M1. It reverts back to its original priority. The highest priority task is now J1 which allowed to complete its lock on M2.
  6. At time t13, J1 releases its lock on M2.
  7. At time t14, J1 sleeps. This enables J2 to run and complete its lock on M1.
  8. At time t15, J2 releses its lock on M1.
  9. At time t16, J2 goes to sleep. This allows J3 to run.

Priority Ceiling Protocol

In the priority ceiling protocol, a mutex is associated with a ceiling priority. Only tasks whose priority is lower than the ceiling protocol, are allowed to use the mutex. It works like PIP, in that a task blocked by the mutex raises the owner of the mutex to its priority. This priority cannot go above the ceiling set for the mutex because by definition, tasks with a higher priority are not permitted to use the mutex and thus cannot block on it. The Priority Ceiling Protocol can prevent deadlock. The disadvantage of using the PCP protocol is that task priorities must be known ahead of time. Tasks are not allowed to dynamically change their priorities (except as part of the protocol).

Original Priority Ceiling Protocol

The original priority ceiling protocol is specified as follows:
  1. Every task has a static priority.
  2. Every mutex has a priority ceiling. A task is not allowed to lock a task whose ceiling priority is lower than its effective priority. Correspondingly, the priority ceiling of a mutex should be greater than or equal to that of any task that might use it.
  3. A task is only allowed to lock a mutex if its priority is higher than all priority ceilings of all active mutexes in the system. This sounds complex but in a system where every task has a unique priority, the scheduler automatically takes care of this (if a task holding a mutex cannot block on other primitives as in TiROS).
  4. When a high priority task blocks on a mutex, the task owning the mutex is raised to the priority of the high-priority task. This is exactly as is in the Priority Inheritance Protocol. However, there is a maximum priority level which is the priority ceiling of the mutex.

Scenario 6: Original Priority Ceiling Protocol

  1. There are two mutexes M1, and M2. The highest priority task that will ever access M1 is J0. Thus the ceiling priority of M1 is greater than or equal to the priority of J0. The highest priority task that will access M2 is J2. The ceiling priority of M2 is greater than or equal to the priority of J2.
  2. At time t1, low priority task, J3 acquires mutex, M1.
  3. At time t2, J2 wakes and runs.
  4. At time t3, J2 attempts to lock mutex M2, but is blocked. Note that J2 is blocked even though mutex M2 is available. This blockage happens by the application of Rule 3) above. The priority of J2 is not higher than the priority ceilings of other active mutexes (i.e., M1). Since J2 is blocked by J3, J3 resumes with the priority of J2.
  5. At time t4, J1 wakes and runs.
  6. At time t5, J0 wakes and runs.
  7. At time t6, J0 attempts to lock mutex M1, but is blocked. M1 is already locked by J3. The priority of J3 is raised to that of J0.
  8. At time t7, J3 releases the lock on M1. It is restored to its original priority. J0 can now run and complete the lock on M1.
  9. At time t8, J0 releases its lock on M1.
  10. At time t9, J0 goes to sleep. This allows J1 to run.
  11. At time t10, J1 goes to sleep allowing J2 to run. J2 can now complete its lock on M2.
  12. At time t11, J2 releases the lock on M2.

Immediate Priority Ceiling Protocol

The Immediate Priority Ceiling Protocol (also called Priority Protect Protocol in POSIX, Priority Ceiling Emulation Protocol in Real-Time Java) is a modification to the original PCP protocol. This is the algorithm that is typically implemented in operating systems that support the priority ceiling protocol. It is simpler to implement and provides higher performance than the original protocol. It is specified as follows:
  1. Every task has a static priority (Similar to OPCP).
  2. Every mutex has a priority ceiling. A task is not allowed to lock a mutex whose ceiling priority is lower than its effective priority. (Similar to OPCP).
  3. When a task locks a mutex, its priority is immediately raised to the priority ceiling (Differs from OPCP).
To illustrate the differences from OPCP, we will re-enact Scenario 6 using IPCP.

Scenario 6: Immediate Priority Ceiling Protocol

  1. The ceiling priority of M1 is greater than or equal to the priority of J0. The ceiling priority of M2 is greater than or equal to the priority of J2.
  2. At time t1, low priority task, J3 acquires mutex, M1. The priority of J3 is raised to the priority ceiling (greather than that of J0).
  3. At time t2, J2 wakes but cannot run.
  4. At time t3, J1 wakes but cannot run.
  5. At time t4, J0 wakes but cannot run..
  6. At time t5, J3 unlocks M1. Its original priority is restored and J0 now runs.
  7. At time t6, J0 locks M1 and runs at the priority ceiling of M1.
  8. At time t7, J0 releases its lock on M1 and its original priority is restored.
  9. At time t8, J0 goes to sleep. This allows J1 to run.
  10. At time t9, J1 goes to sleep allowing J2 to run.
  11. At time t10, J2 locks M2 and runs at the priority ceiling of M2.
  12. At time t11, J2 unlocks M2 and its original priority is restored.
Note also that IPCP uses fewer task-switches. This translates to reduced overhead.

Deadlock Prevention using PCP

The Priority Ceiling Protocol has an important property that is extremely valuable in building reliable embedded systems. It can eliminate deadlock!

Consider the scenario that was presented earlier to illustrate Deadlock. Now, lets apply IPCP (OPCP would work just as well) to this scenario.

Deadlock prevention using IPCP

  1. In this example, M1 and M2 have the same ceiling priority. They both have a priority greater than or equal to the priority of J0.
  2. At time t1, low-priority task J1 has locked mutex M1. The priority of J1 is thus raised to the priority ceiling.
  3. At time t2, task J0 wakes. However, it cannot run because J1 is running, which has higher or equal priority as J1.
  4. At time t3, task J1 locks mutex M2.
  5. At time t4, task J1 releases mutex M2.
  6. At time t5, task J1 releases mutex M1. It then reverts to its original priority. Since the priority of J0 is now greater than that of J1, task J0 is now allowed to run. It can then proceed to lock and unlock M1, M2 without obstruction.
This scenario is similar to that shown earlier (Deadlock), but with PCP applied. It shows how deadlock can be prevented.

Rules for using mutexes in TiROS

  1. To deal with priority inversion, TiROS provides an option of using Cascaded priority inheritance with delayed fallback or Immediate Priority Ceiling Protocol. One and only one of these algorithms can be used at a time.
  2. A mutex cannot be used from an interrupt service routine. Mutex locks and unlocks have to occur in pairs. To enforce priority protocols, a mutex has to be owned by a task. If a global resource also has to be used from an interrupt handler, consider using Critical Sections. Also see Usage with Interrupt Service Routines.
  3. A task acquiring multiple mutexes must release them in the reverse order.
  4. A task that is holding a mutex is not allowed to perform a blocking-wait on other types of synchronization primitives (locks) such as Counting semaphores, Message Queues, and Event Flags. Non-blocking operations are permitted. Blocking on additional mutexes is also permitted. This is because the priority protocols are not transitive across different types of locks. There is no concept of an owner with counting semaphores or message queues. Priority protocols only operate on owned locks, i.e., mutexes. In the default configuration, explicit sleeping is also disallowed while holding a mutex. However, using the TIROS_ALLOW_SLEEP_W_MUTEX configuration directive, this can be bypassed. This can cause undesirable blocking but it is assumed that the user has an explicit reason for doing this. So use this with care.
  5. All tasks should have unique priorities.
  6. Mutexes should have unique ceiling priorities that do not correspond to any task priorities.
TiROS User Manual: Last Updated on Fri Jul 20 10:52:24 2007