Mutual Exclusion guide

The most common problem when writing multithreaded code is the synchronization on the shared resources/services.
ChibiOS/RT offers a rich variety of mechanisms that apparently solve the same problem. I wrote apparently because each mechanism has its pro and cons. This article will introduce the various mechanisms and the explain the right scenarios for each one.

Basics

Some of the concepts mentioned in this article can be found in the following Wikipedia articles:

System Locks

This is the lowest level mechanism, the system is locked by invoking the chSysLock() API and then unlocked by invoking chSysUnlock(). The implementation is architecture dependent but it is guaranteed to, at least, disable the interrupt sources with hardware priority below or equal the kernel level.

Advantages

  • It is the lightest as execution time, often a lock or unlock becomes just a single inlined assembler instruction.
  • It ensures mutual exclusion among threads but also interrupt handling code.
  • The implementation would ensure mutual exclusion even on multicore architectures where multiple hardware threads are present.

Disadvantages

  • Disabling interrupts for a long period of time can deteriorate the overall system response time and/or introduce jitter.

When use System Locks

  • When mutual exclusion with interrupt handlers is required.
  • When the operation within the lock zone is very simple and has finite time.

Example

  ...
  chSysLock();
  /* Protected code */
  chSysUnlock();
  ...

Semaphores

In ChibiOS/RT the counting semaphores are mainly meant as a synchronization mechanism between interrupt handlers and high level code running at thread level. Usually a thread waits on a semaphore that is signaled asynchronously by an interrupt handler. The semaphores can, however, be used for mutual exclusion by initializing the semaphore counter to one.

Advantages

  • The semaphores code is “already there” if you use the I/O queues or mailboxes and you don't want to enable the mutexes too in order to save space.
  • Semaphores are lighter than mutexes because their queues are FIFO ordered and do not have any overhead caused by the priority inheritance algorithm.
  • A semaphore takes less RAM than a mutex (12 vs 16 bytes on 32 bit architectures).

Disadvantages

  • Semaphore queues are FIFO ordered by default, an option exist to make them priority ordered but this can impact I/O performance because semaphores are used in I/O queues.
  • Semaphores do not implement the Priority Inheritance algorithm.

When use Semaphores

  • When you don't need queuing by priority nor the Priority Inheritance algorithm.
  • When RAM/ROM space is scarce.

Example

static Semaphore sem; /* Semaphore declaration */
...
chSemInit(&sem, 1);   /* Semaphore initialization before use */
...
chSemWait(&sem);
/* Protected code */
chSemSignal(&sem);
...

Mutexes

The mutexes are the mechanism intended as the most general solution for Mutual Exclusion.

Advantages

  • Mutexes implement the Priority Inheritance algorithm that is an important tool in reducing jitter and improve overall system response time (it is not a magic solution, just another tool for the system designer).

Disadvantages

  • Heaviest among all the possible choices. The Priority Inheritance method is efficiently implemented but nothing is more efficient than no code at all.

When use Mutexes

  • When you are designing a very complex system with hard realtime requirements and you decide that priority inheritance can help you.

Example

static Mutex mtx; /* Mutex declaration */
...
chMtxInit(&mtx); /* Mutex initialization before use */
...
chMtxLock(&mtx);
/* Protected code */
chMtxUnlock();
...

Priority Boost

Another way to implement mutual exclusion is to boost the thread priority to a level higher than all of the threads competing for a certain resource. This solution effectively implements an Immediate Priority Ceiling algorithm.

Advantages

  • Almost free as code size, you need no semaphores nor mutexes.
  • No RAM overhead.
  • Fast execution, priority change is a quick operation under ChibiOS/RT.
  • The Priority Ceiling protocol can help mitigate potential Priority Inversion problems.

Disadvantages

  • Makes the design more complicated because priorities must be assigned to not just threads but also assigned to the resources to be protected.
  • Locking a resource affects all the threads with lower priority even if not interested to the resource.
  • All the threads that can access the resource must have lower priority than the resource itself.
  • The mechanism is not easy to understand in the code unless it is clearly documented.
  • This method does not work in on multicore architectures where multiple hardware threads are present.
  • Only useful in very simple applications.

Example

/* Priority assigned to the resource, threads must have lower
   priority than this.*/
#define AAA_RESOURCE_PRIORITY NORMALPRIO+10
...
/* Locks the resources AAA.*/
tprio_t aaa_old_prio = chThdSetPriority(AAA_RESOURCE_PRIORITY);
/* Accessing resource AAA */
chThdSetPriority(aaa_old_prio); /* Unlocks AAA.*/
...

Message Passing

Another method is to make a single dedicated thread execute the critical code and make it work as a messages server. The other threads can request the service to the server by sending a properly formatted message and then wait for the answer with the result.
This method is very useful when integrating into the system components not designed to be reentrant or to be executed in a multithreaded environment, for example a 3rd part file system or a networking protocol stack.

Advantages

  • It is possible to encapsulate very complex logic without worry about about concurrent accesses.
  • If the encapsulate code uses a large stack area only the server thread have to allocate enough RAM, the client threads save RAM by just requesting the service to the server.
  • Clean system architecture.
  • This method also implements a form of Priority Ceiling. The ceiling is the priority of the server thread itself.

Disadvantages

  • More complex implementation, a protocol must be created between clients and server.
  • Two context switches are required for each request to the server (but ChibiOS/RT is very efficient at that).
  • Requires a dedicated thread as server.
 
chibios/guides/mutual_exclusion_guide.txt · Last modified: 2011/10/03 20:52 by giovanni
 
Except where otherwise noted, content on this wiki is licensed under the following license:GNU Free Documentation License 1.3