/* ChibiOS/RT - Copyright (C) 2006,2007,2008,2009,2010 Giovanni Di Sirio. This file is part of ChibiOS/RT. ChibiOS/RT is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. ChibiOS/RT is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ /** * @page article_mutual_exclusion 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: * - * Mutual Exclusion * - * Priority Inversion * - Priority Inheritance * - * Priority Ceiling * . *

Mutual exclusion by System Locks

* This is the lowest level mechanism, the system is locked by invoking the * @p chSysLock() API and then unlocked by invoking @p 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 Locks

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

Example

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

Mutual exclusion by 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 as simple mutexes 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

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

Mutual exclusion by 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. * . *

Example

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

Mutual exclusion by 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

* @code * /* 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.*/ * ... * @endcode * *

Mutual exclusion by 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, * as 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 * ChibiOSRT is very efficient at that). * - Requires a dedicated thread as server. * . */