Binary semaphores
Let's start with the simplest of them, the binary semaphores. You can think of it as a totem, and only the person who has the totem can do something. Also this person is responsible of giving it back after one is done using it, and the totem will be given to the next person.
Think of a family with 3 people at lunch time with only one microwave. Dad puts its dish to heat while mom and son are waiting for their turn. Mom asks to use it and then the son. Dad's turn is over and the mom starts heating her dish while the son starts complaining, hungry, but dad, who is late for work, just realised his dish is not hot enough and will need to use the microwave again. Mom's dish is heated and she goes to eat it while the son heats his dish and dad complains that he has to wait, because he's late, etc. Son leaves the microwave for dad and goes to eat. He heats his dish again and finally goes to eat too.
We had 3 people (tasks) with different priorities (dad late to work) and only one microwave (resource), thus only one person (task) could use the microwave (resource) at a time and the next person (task) can only use the microwave (resource) when the first person (task) releases it. Basically a FIFO, ignoring the tasks priorities.
A binary semaphore works in a similar way. Several tasks can ask for it ("take") and block (or not) while waiting, but only one task can have it at each time. When the task is done with it, it can either give it back ("Give") or just wait until someone else release the resource again. For the first scenario, you could think of the microwave example, where each task gives back the right to use the resource after it is done with it. A more comprehensive example could be a hardware with several components, all communicating through the same I2C peripheral, and one task responsible to communicate with each component. The communication is comprised of sending commands and receiving answers, so while each task is communicating with its component, no other tasks are allowed to use the I2C comm, until the first task frees the resource. For the second scenario, imagine a not frequent interruption (someone pressing a button): the interruption handler will give one binary semaphore at each key press, for which the task responsible to interpret the action will take it and do whatever it must do and then go to sleep, waiting for the next interruption to give another semaphore.
Care must be taken, though, that the binary semaphores don't allow being given more than once. In case you have an interruption that is too often, thus may occur more than once while the task which takes it is still processing, another mechanism should be used (counting semaphores, for example).
Finally, of course you could relate the binary semaphore to a queue with only one position, in which the value stored doesn't matter, but the fact that the queue is full or empty.
The API functions available for creating a binary semaphore are those below (it is created "empty", which means someone should give it for the first time). Giving or taking uses the same functions for other kinds of semaphores or mutex.
/* Creates a binary semaphore, allocated in the heap Return: the handle for the semaphore or NULL (error) */ SemaphoreHandle_t xSemaphoreCreateBinary( void ); /* Creates a binary semaphore, allocated somewhere in RAM, according to pxSemaphoreBuffer Returns: the handle for the semaphore or NULL if pxSemaphoreBuffer is NULL */ SemaphoreHandle_t xSemaphoreCreateBinaryStatic( StaticSemaphore_t *pxSemaphoreBuffer );
Counting Semaphores
Imagine you the family realized how much time they were wasting while waiting for the microwave to be used and decided to buy another microwave, exactly the same model. Now two people could heat their dishes at the same time!
Counting semaphores are commonly used to manage the use of resources, where the counting value represents the number of free resources. To obtain access to it, a task must successfully take the semaphore, which will decrement the counting value, and then give it back, which will increment it again. Another use of counting semaphores is counting event, when an event handler (interrupt handler, for instance) will give a semaphore every time the event occurs and the task that will process the event takes the semaphore. The counting value would be the difference between the amount of events that occurred and the amount of processed ones, or just the amount of event yet to be processed.
You can relate the counting semaphore to a queue with a length higher than one, where the value stored in each position isn't important, but the amount of data still in the queue.
The API for creating the counting semaphores and getting the count value is as follows. Once again, the take and give API is the same for the other kinds of semaphores and mutex and will be presented later.
Counting semaphores are commonly used to manage the use of resources, where the counting value represents the number of free resources. To obtain access to it, a task must successfully take the semaphore, which will decrement the counting value, and then give it back, which will increment it again. Another use of counting semaphores is counting event, when an event handler (interrupt handler, for instance) will give a semaphore every time the event occurs and the task that will process the event takes the semaphore. The counting value would be the difference between the amount of events that occurred and the amount of processed ones, or just the amount of event yet to be processed.
You can relate the counting semaphore to a queue with a length higher than one, where the value stored in each position isn't important, but the amount of data still in the queue.
The API for creating the counting semaphores and getting the count value is as follows. Once again, the take and give API is the same for the other kinds of semaphores and mutex and will be presented later.
/* Creates a counting semaphore, allowing to specify until how many it can count and the initial
count value, allocated in the heap
Returns: the handle for the semaphore or NULL (error) */
SemaphoreHandle_t xSemaphoreCreateCounting( UBaseType_t uxMaxCount,
UBaseType_t uxInitialCount );
/* Similar to xSemaphoreCreateCounting, but the semaphore is stored somewhere in RAM, according
to pxSemaphoreBuffer
Returns: the handle for the semaphore or NULL if pxSemaphoreBuffer is NULL */
SemaphoreHandle_t xSemaphoreCreateCountingStatic( UBaseType_t uxMaxCount,
UBaseType_t uxInitialCount,
StaticSemaphore_t *pxSemaphoreBuffer );
/* Returns the count value of the specified semaphore */
UBaseType_t uxSemaphoreGetCount( SemaphoreHandle_t xSemaphore );
Mutex
Mutex is a special case of binary semaphores, in the sense that it only has one position available for the resource to be used. The main difference is that now priority matters, which makes it a better choice for simple MUTual EXclusion cases, while the semaphores are better for task synchronisation. In my microwave example, if the family were using Mutexes instead of a binary semaphore, dad would reheat his dish before the son could heat his. Another difference from binary semaphores is that it can't be used inside interruptions.
One important thing is that with Mutexes, the task that took it must give it back. This is specially important when you have two tasks and both use the same two mutexes. Imagine task 1 takes mutex 1 and while it is processing, task 2 takes mutex 2. In order to task 1 finish whatever it is doing, it needs to take mutex 2 before giving mutex 1. In order to task 2 to finish, it needs mutex 1. This is a common design problem called deadlock. Each task is waiting the other to give the mutex and will never come to an agreement (unless the programmer implements some kind of protection). There are a few ways of preventing that:
One important thing is that with Mutexes, the task that took it must give it back. This is specially important when you have two tasks and both use the same two mutexes. Imagine task 1 takes mutex 1 and while it is processing, task 2 takes mutex 2. In order to task 1 finish whatever it is doing, it needs to take mutex 2 before giving mutex 1. In order to task 2 to finish, it needs mutex 1. This is a common design problem called deadlock. Each task is waiting the other to give the mutex and will never come to an agreement (unless the programmer implements some kind of protection). There are a few ways of preventing that:
- Don't allow a task to take two mutexes at once
- Using the timeout occurrence to prevent the task to be blocked forever
- Don't share resources at all
- Using a "Gatekeeper" to manage the access to the resource (basically a "manager" of the resource, so instead of taking the mutex, the tasks would use the services provided by the gatekeeper)
Regarding the priority inheritance in Mutexes, the objective is to make higher priority task wait as little as possible. This is how it works WITHOUT priority inheritance (with a binary semaphore, for instance): imagine a task 1 with priority 1 (low) took a mutex and is executing. During that time, task 2 with priority 10 (high) pauses task 1 execution, since it has a higher priority, and blocks while trying to take the mutex, which resumes task 1. Now task 3 with priority 5 (medium) pauses task 1 execution to do whatever it wants and after a while, blocks, what makes task 1 resume again. Task 1 finally gives the mutex and task 2 finally takes it and resumes its execution. What happened is that task 2 had to wait task 3 to execute, even though its priority is higher. This is called Priority Inversion, since a lower priority task managed to execute before a higher priority task.
To avoid that, FreeRTOS implements a priority inheritance mechanism. This means that when a higher priority task tries to take an already taken mutex, the lower priority task holding it momentarily gets its priority raised to the same priority of the other task. This means when task 2 tries to take the mutex, the mechanism raises task 1 priority to 10, avoiding any interrupts by task 3, which has priority 5 and executing as fast as possible in order to give the mutex and resume task 2. When the mutex is given, the original priority is restored, task 2 executes until for any reason it blocks again and only then task 3 will execute. It is important to remember that this mechanism doesn't prevent the priority inversion, since it has actually already happened (all in all, task 2 is still waiting for a lower priority task to execute), but rather minimises this problem. The ideal scenery would be one where the inversion never occurs in first place.
The API for creating a Mutex and getting the handle to the task holding the mutex. Once again, the take and give API is the same for the other kinds of semaphores and will be presented later.
/* Creates a Mutex stored in the heap Returns: a handle to the mutex or NULL if out of memory */ SemaphoreHandle_t xSemaphoreCreateMutex( void ); /* Creates a Mutex stored somewhere in RAM, according to pxMutexBuffer Returns: a handle to the mutex or NULL if pxMutexBuffer is NULL */ SemaphoreHandle_t xSemaphoreCreateMutexStatic( StaticSemaphore_t *pxMutexBuffer ); /* Gets the handle to the task holding the specified mutex Returns: the handle to the task or NULL if no task holds it or xMutex is not a mutex */ TaskHandle_t xSemaphoreGetMutexHolder( SemaphoreHandle_t xMutex );
Just a small concern regarding the function xSemaphoreGetMutexHolder(): it can only reliably determine if the task calling the function is the mutex holder, since the holder can change between calling the function and getting its return value.
Taking and giving semaphores and common mutexes use the same API function which will be described below. Just remember Mutexes can't be used in interruptions, thus the functions ending in FromISR don't apply
Deleting a Semaphore/Counting Semaphore/Mutex/Recursive Mutex is quite straightforward and uses the same function in all cases.
Ok, this post is already too long. I'll leave the explanation of the demo application to the next one...
Taking and giving semaphores and common mutexes use the same API function which will be described below. Just remember Mutexes can't be used in interruptions, thus the functions ending in FromISR don't apply
/* Gives a binary semaphore or mutex or increments the count in a counting semaphore
Returns pdPASS if successful or pdFAIL if the task calling the function is not the holder */
BaseType_t xSemaphoreGive( SemaphoreHandle_t xSemaphore );
/* Same as before, but to be used in an interrupt (doesn't apply to mutex)
Parameter pxHigherPriorityTaskWoken is optional, but important: it will receive pdTRUE if a task
with higher priority than the interrupted was unblocked and a manual context switch is required
Returns pdTRUE if successful, or errQUEUE_FULL if a semaphore is already available (max count
in counting semaphores reached) */
BaseType_t xSemaphoreGiveFromISR( SemaphoreHandle_t xSemaphore,
BaseType_t *pxHigherPriorityTaskWoken );
/* Takes a binary semaphore or mutex or decrements the count in a counting semaphore
Returns pdPASS if successful or pdFAIL otherwise */
BaseType_t xSemaphoreTake( SemaphoreHandle_t xSemaphore,
TickType_t xTicksToWait ); /* 0 will return the function immediatly and portMAX_DELAY will make the task wait indefinitely */
/* Same as before, but to be used in an interrupt (doesn't apply to mutex)
Parameter pxHigherPriorityTaskWoken is optional and quite unlikely to be necessary. Same logic
as before (xSemaphoreGiveFromISR) applies
Returns pdTRUE if successful or pdFAIL if there wasn't a semaphore/mutex to be taken */
BaseType_t xSemaphoreTakeFromISR( SemaphoreHandle_t xSemaphore,
signed BaseType_t *pxHigherPriorityTaskWoken );
Recursive Mutex
This is a special case of Mutex with which the task that has taken the mutex can take it many more times. Beware that the mutex MUST be given the same amount of times before any other task can take it. Like non recursive Mutexes, this type also implements the priority inheritance, thus it can't be used inside an interruption.
Recursive mutexes are mainly used in recursive functions that require exclusive access to some resource, thus taking the mutex is part of the recursive function code, as must be giving back the mutex.
The API for Recursive Mutex is unique and its functions are not interchangeable with common mutexes.
/* Creates a Recursive Mutex stored in the heap
Returns: Handle for the Recursive mutex or NULL if there is not enough memory left */
SemaphoreHandle_t xSemaphoreCreateRecursiveMutex( void );
/* Creates a Recursive Mutex stored somewhere in RAM, according to pxMutexBuffer
Returns: a handle to the mutex or NULL if pxMutexBuffer is NULL */
SemaphoreHandle_t xSemaphoreCreateRecursiveMutex( StaticSemaphore_t pxMutexBuffer );
/* Gives a Recursive Mutex one time
Returns pdPASS if successful, or pdFAIL if the task calling it wasn't the holder */
BaseType_t xSemaphoreGiveRecursive( SemaphoreHandle_t xMutex );
/* Takes a Recursive Mutex one time
Returns pdPASS if successfully obtained, pdFAIL otherwise */
BaseType_t xSemaphoreTakeRecursive( SemaphoreHandle_t xMutex,
TickType_t xTicksToWait ); /* 0 will return the function immediatly and portMAX_DELAY will make the task wait indefinitely */
Deleting a Semaphore/Counting Semaphore/Mutex/Recursive Mutex is quite straightforward and uses the same function in all cases.
/* Deletes a Semaphore, Counting Semaphore, Mutex or Recursive Mutex */ void vSemaphoreDelete( SemaphoreHandle_t xSemaphore );
Ok, this post is already too long. I'll leave the explanation of the demo application to the next one...
No comments:
Post a Comment