Introduction to Semaphores and Mutexes

Keywords: Embedded systems, ARM, FreeRTOS, Semaphore, Tasks, Mutex

“A Semaphores is a Synchronization technique used to control access to common resources in a multi-threaded Environment”.

“A Semaphores is a resource management technique used to manage access to shared resources in a multi-threaded environment”.

Most of the low power low end embedded systems follows legacy hardware architecture of shared memory where any part of volatile memory can be read/modified/written by any part of embedded software running on the hardware. This is not a big issue until the software gets complex and runs multiple units of independent software tasks accessing shared memory simultaneously e.g. System is performing multi-tasking.

In such systems on the major problem is memory protection and access to a common hardware/software resources (e.g. UART). Though some part of shared memory can be reserved (via some global flag variable) that can be set and released when accessing a resource; The problem in such systems arises when it comes to the memory operation Atomicity.

For Example, consider a UART being managed by a global flag and used by two tasks i.e. Task1 and Task-2 (video bellow). Each time a Task wants to access UART, it first checks whether the flag is set. If the flag is 0, it means its free if not it means UART is being used by another process. In this case, it is quite probable that one task say Task-1 just checks the flag and about to Set the flag (to indicate to other processes that UART is acquired) and a Context Switch occurs leaving the flag unset. The next task (Task-2) selected by Scheduler checks the same flag and finds the UART free ( as flag is not yet Set by the previous task), it sets it and start using UART for long time. Meanwhile again a Context Switch occurs bring back the first task (Task-1) to execute. The Task-1 has already checked the flag (before Context Switch) so it just simply Set the flag (flag is overwritten) and start using UART. Now the string sent by two Tasks mix up that can lead to severe bugs in critical systems.

The following video shows how two freeRTOS tasks trying to write string to same serial Port. As can be seen while the one task has not yet finished writing to serial port, the context switch preempt the first task and runs the second task resulting into mixing of two strings. The exact same things happens in situations of shared memory.

* Task1 Prints: “Message From Task-1: FreeRTOS Task-1 Running...
* Task2 Prints: “Message From Task-2: FreeRTOS Task-2 Running...

Another very common example is the use of a Shared Printer on network. Many computer on network may be accessing printer simultaneously but printer can only be assigned to one computer at a time.

In order to tackle such problem, Dijkestra proposed a significant technique called Semaphore for managing concurrent processes trying to gain access of some common resource.

Semaphores are not only limited to manage only single share resource being accessed by multiple processes, it can also be used to synchronized access to N-number of shared resources in a multi-threaded environment (see Semaphore types).

1. Semaphore Operations:

Semaphore implementation provides accesses to the follow operation.

1.1 Take(): Take() Operation is used to gain access to a resource. If the resource is not available, the Task is Blocked.

1.2 Give(): Give() Operation is used to release an already Taken resource.

2. Semaphore Internal:

Internally semaphore contains:

2.1 : A Variable – N : Indicates remaining resources available to be assigned. Initially this variable is set to the total number of resources available in system. For example if there are three UARTs available in system to be accessed by multiple process then this variable will be initially set to 3. In Semaphore, access to this variable is Thread-Safe and only available via standard Take() and Give() Operations.

2.2 A List: To keep track of of processes that are blocked on the semaphore and waiting for the access. Whenever there is an availability of of resource/resources, task/tasks in the list are unblocked to gain access of the assigned resources.

3. How Semaphore Works:

When ever a process is alloted access (via Take() Operation) to a resource by semaphore, the value of internal variable – N is decremented by 1. Similarly when a process release a resource (via Give() Operation), the internal variable – N is incremented by 1. Once the value of N becomes 0 any further process trying to gain access of a resource via the semaphore will be sent to blocked state and an entry is made to the internal list. Once a resource becomes available, the process in the block list is unblocked and given access.

4. Semaphore Types:

This following two types of Semaphores.

4.1 Binary Semaphore: Binary semaphore can take the value 0 & 1 only (the internal Variable – N value). In other words, binary semaphore can only be used to manage one single resource being accessed by many processes. Binary semaphore are mostly used for Task Synchronization rather than managing access to single resource. The following tutorial shows how binary semaphore can be used for synchronization purpose.

4.2 Counting Semaphore: Counting semaphore can take nonnegative integer as it internal variable – N value. While Binary semaphores are mostly used for task synchronization, Counting Semaphores are used to manage access to n-number of resource being accessed by multiple tasks.

5. Mutex:

Mutexes are similar to binary semaphores in the sense that both are used to protect Individual Resource except in Mutexes a process owns a resource. i.e. Once a process gain access of a resource, no can can make it release the resource until the process itself release it. In semaphore a process once gain access of a resource (Take()) can be released from anywhere while in case of mutexes, only the process that gained access can release the resource even if a high priority task is waiting for the resource. This can lead to the Priority Inversion problem (A higher priority task is waiting for the low priority task to complete) which is out of scope of this tutorial. In FreeRTOS Mutexes include priority inheritance mechanism to minimises the effect of Priority Inversion in some situation but it doesn’t completely solve Priority Inversion problem. Whereas binary semaphores are the better choice for implementing synchronisation (between tasks or between tasks and an interrupt), mutexes are the better choice for implementing simple mutual exclusion (hence ‘MUT’ual ‘EX’clusion).

5.1 Mutex Standard Operations:

Though the standard operation on Mutex are Lock() and UnLock() to gain and release ownership of a resource, FreeRTOS uses the same Take() and Give() APIs as a substitute to Mutex Lock() and UnLock() Operations.

6. FreeRTOS Semaphores, Mutexes APIs:

This following APIs are commonly used for freeRTOS Semaphore and Mutex Operations.

6.1 xSemaphoreCreateBinary():

SemaphoreHandle_t xSemaphoreCreateBinary( void );

This API creates a binary Semaphore and return a handle to it to be used for further references.

Parameter NameDescription
Return ValueIf NULL is returned, then the semaphore cannot be created because there is insufficient heap memory available for FreeRTOS to allocate the semaphore data structures.

If a non-NULL value is returned, the semaphore has been created successfully. The returned value should be stored as the handle to the created semaphore.

6.2 xSemaphoreCreateCounting():

SemaphoreHandle_t xSemaphoreCreateCounting( UBaseType_t uxMaxCount,
                                            UBaseType_t uxInitialCount);

xSemaphoreCreateCounting() creates a Counting Semaphore with uxMaxCount be considered as the total number of resources available and uxInitialCount as the total number of resources CURRENTLY/INTIALLY avialble. The API resturns a Handle to the Counting Semaphore to be used for further references.

Parameter NameDescription
uxMaxCountThe maximum value to which the semaphore will count.
uxInitialCountThe initial count value of the semaphore after it has been created.
Return ValueIf NULL is returned, the semaphore cannot be created because there is insufficient heap memory available for FreeRTOS to allocate the semaphore data structures.

If a non-NULL value is returned, the semaphore has been created successfully. The returned value should be stored as the handle to the created semaphore.

6.3 xSemaphoreTake():

BaseType_t xSemaphoreTake( SemaphoreHandle_t xSemaphore, TickType_t xTicksToWait );

xSemaphoreTake() is used to perform the Take() operation on xSemaphore. If the semaphore is not available, the task is sent back to block state for xTicksToWait time in terms of Ticks.

Parameter Name/ Returned valueDescription
xSemaphoreThe semaphore being taken. A semaphore is referenced by a variable of type SemaphoreHandle_t. It must be explicitly created before it can be used.
xTicksToWaitThe maximum amount of time the task should remain in the Blocked state to wait for the semaphore if it is not already available.

If xTicksToWait is zero, then xSemaphoreTake() will return immediately if the semaphore is not available.

The block time is specified in tick periods, so the absolute time it represents depends on the tick frequency. The macro pdMS_TO_TICKS() can be used to convert a time specified in milliseconds to ticks.

Setting xTicksToWait to portMAX_DELAY will cause the task to wait indefinitely (without a timeout) if INCLUDE_vTaskSuspend is set to 1 in FreeRTOSConfig.h.
Return ValueThere are two possible return values:

1. pdPASS

pdPASS is returned only if the call to xSemaphoreTake() was successful in obtaining the semaphore.

If a block time was specified (xTicksToWait was not zero), then it is possible that the calling task was placed into the Blocked state to wait for the semaphore if it was not immediately available, but the semaphore became available before the block time expired.

2. pdFALSE

The semaphore is not available.

If a block time was specified (xTicksToWait was not zero), then the calling task will have been placed into the Blocked state to wait for the semaphore to become available, but the block time expired before this happened.

6.4 xSemaphoreGive():

BaseType_t xSemaphoreGive(SemaphoreHandle_t xSemaphore);

xSemaphoreGive() releases a previously taken semaphore or Mutex.

Parameter NameDescription
xSemaphoreA handle to the semaphore being released. This is the handle returned when the semaphore was created.
Return ValuepdTRUE if the semaphore was released. pdFALSE if an error occurred.

6.5 xSemaphoreGiveFromISR():

BaseType_t xSemaphoreGiveFromISR( SemaphoreHandle_t xSemaphore, BaseType_t
                                              *pxHigherPriorityTaskWoken );

From Interrupt Service Routine (ISR), Binary and counting semaphores can be given using the xSemaphoreGiveFromISR() function. xSemaphoreGiveFromISR() is the interrupt-safe version of xSemaphoreGive().

Parameter NameDescription
xSemaphoreA handle to the semaphore being released. This is the handle returned when the semaphore was created.
pxHigherPriorityTaskWokenxSemaphoreGiveFromISR() will set *pxHigherPriorityTaskWoken to pdTRUE if giving the semaphore caused a task to unblock, and the unblocked task has a priority higher than the currently running task. If xSemaphoreGiveFromISR() sets this value to pdTRUE then a context switch should be requested before the interrupt is exited.
Return ValuepdTRUE if the semaphore was released. If a semaphore is already available, it cannot be given, and xSemaphoreGiveFromISR() will return pdFAIL.

6.6 xSemaphoreCreateMutex():

SemaphoreHandle_t xSemaphoreCreateMutex( void );

Before a Mutex can be used, it must be created. This API is used to create a Mutex.

Parameter NameDescription
Return ValueIf the mutex type semaphore was created successfully then a handle to the created mutex is returned. If the mutex was not created because the memory required to hold the mutex could not be allocated then NULL is returned.

Note: The same same xSemaphoreTake() and xSemaphoreGive() APIs are used to perform Mutex Lock and UnLock operations.

References:

[1] – FreeRTOS Official Website



95 thoughts on “Introduction to Semaphores and Mutexes”

Leave a Reply

Your email address will not be published. Required fields are marked *