Tuesday, June 6, 2017

FreeRTOS 9.0.0 - Semaphores and Mutexes

Ok, so we now know what tasks notifications is all about. We know it can be used to pass simple messages, to make a task unblock or can be used as simple binary semaphore. Let's start with the semaphores. What are they? What do they eat? How do they multiply?

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.

/* 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:

  • 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

/* 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...


Friday, June 2, 2017

FreeRTOS 9.0.0 on ArduinoMEGA - Full Demo - Task Notifications

After the Demo Blinky and Demo AVR323 I'm feeling more confident in this port, so let's get serious. Let's make the Full Demo work!

I'll try to follow the same order I used to describe the Full Demo here and get each module to work properly. I'll also use all the files used in AVR323 Demo project to start the Full Demo. To do that, I duplicated the AVR323 project with a different name (FreeRTOS_ArduinoMEGA-Demo_Full) and copied a few source and header files from the FreeRTOS folder.
  • The whole Standard Demo Header files can be copied to the project folder "FreeRTOS_ArduinoMEGA-Demo_Full\FreeRTOS\Demo\Common\include" folder (there was only the partest.h header). 
  • The source files should be copied from the folder "FreeRTOS 9.0.0\FreeRTOS\Demo\Common\Minimal" to the project folder "FreeRTOS_ArduinoMEGA-Demo_Full\FreeRTOS\Demo\Common\Minimal", but not all of them. The list follows:
    • AbortDelay.c
    • BlockQ.c
    • blocktim.c
    • countsem.c
    • death.c
    • dynamic.c
    • EventGroupsDemo.c
    • flop.c
    • GenQTest.c
    • integer.c
    • IntSemTest.c
    • PollQ.c
    • QPeek.c
    • QueueOverwrite.c
    • QueueSet.c
    • QueueSetPolling.c
    • recmutex.c
    • semtest.c
    • TaskNotify.c
    • TimerDemo.c
  • You'll also need to add a few source files that implement the FreeRTOS. Add the following from the folder "FreeRTOSv9.0.0\FreeRTOS\Source" to you project folder "FreeRTOS_ArduinoMEGA-Demo_Full\FreeRTOS\Source" (there was only list.c, queue.c and tasks.c, which are the bare minimum):
    • croutine.c
    • event_groups.c
    • timers.c
  • For the Full Demo, we'll need to use some dynamic allocation, thus change your heap file to the heap_5.c to have the full experience.
Finally, before we start, I suggest you compile the project as it is (essencially the AVR323 project) and correct any problems that may appear. For me, there were two problems:
  • References missing: go to Project > Properties > C/C++ General > Paths and Symbols > Includes > GNU C, add the following workpace paths:
    • /FreeRTOS_ArduinoMEGA-Demo_Full
    • /FreeRTOS_ArduinoMEGA-Demo_Full/FreeRTOS/Source/portable/WinAVR/ATmega2560
    • /FreeRTOS_ArduinoMEGA-Demo_Full/FreeRTOS/Source/include
    • /FreeRTOS_ArduinoMEGA-Demo_Full/FreeRTOS/Demo/Common/include
  • Definitions missing: on FreeRTOSConfig.h:
/* Software timer related configs - Full Demo */
#define configTIMER_TASK_PRIORITY ( configMAX_PRIORITIES - 1 )
#define configTIMER_QUEUE_LENGTH 20

/* The following includes are used in Full DEMO */
#define INCLUDE_eTaskGetState   1

With everything compiling correctly, even though it doesn't do anything different, we can start implementing (or actually just using the implemented algorithms) the Full Demo functions.

Tasks Notifications


Task notification is used to either send simple messages to another specific task or to just unblock the other task. This API can be considered a "lightweight" one position queue (called mailbox), since it is faster and consumes less RAM. To understand how it is used, let's assume we have two tasks, one I'll call Producer and one Consumer. The Producer will send a notification to the Consumer using  xTaskNotify(),  xTaskNotifyGive(),  xTaskNotifyAndQuery() or its interrupt safe equivalents, and will remain blocked until the Consumer receives the notification through  xTaskNotifyWait(),  ulTaskNotifyTake() or some task calls xTaskNotifyStateClear() with the Producer's handle as parameter. If the Consumer was already waiting for a notification, it will be immediately unblocked.

The notification value is a 32-bit value that every task has and that is cleared (set to zero) when the task is created. When sending a notification, the Producer can change the Consumer's notification value, either by overwriting, setting one or more bits or by an increment. The notification can also not be changed, if desired.

A fast and basic reference for the functions related to this API follows. Firstly, the functions used by the Producer (the one who sends the notification).

/* Notify a task
Returns: pdFAIL only if eAction is eSetValueWithoutOverwrite and there was another notification waiting, otherwise, pdPASS */
BaseType_t xTaskNotify( TaskHandle_t xTaskToNotify,
                        uint32_t ulValue, /* Interpretation of this value depends on eAction */
                        eNotifyAction eAction );

/* Notify and increment notification value 
Returns: pdPASS, always */
BaseType_t xTaskNotifyGive( TaskHandle_t xTaskToNotify );

/* Notify and retrieve the previous value
Returns: pdFAIL only if eAction is eSetValueWithoutOverwrite and there was another notification waiting, otherwise, pdPASS */
BaseType_t xTaskNotifyAndQuery( TaskHandle_t xTaskToNotify,
                                uint32_t ulValue, /* Interpretation of this value depends on eAction */
                                eNotifyAction eAction,
                                uint32_t *pulPreviousNotifyValue ); /* Returns the previous notification value from the Consumer */

The eAction is an enumerated type and can take one of the following values:

  • eNoAction - ulValue is not used, the task is just notified;
  • eSetBits - ulValue represents the bits that will be set in the Consumer's notification value (bits not set won't be altered);
  • eIncrement - ulValue is not used, the Consumer's value is incremented by one;
  • eSetValueWithOverwrite - ulValue is written in the Consumer's value;
  • eSetValueWithoutOverwrite - ulValue is only written if no other Producer is waiting for the Consumer to be notified (there is not a notification pending).
Functions used by the Consumer (the one who receives a notification) or other tasks.

/* Waits for a notification and changes the notification value according to xClearCountOnExit
Returns: the notification value before it's altered*/
uint32_t ulTaskNotifyTake( BaseType_t xClearCountOnExit, /* if pdTRUE, the notification value is reset to 0; if pdFALSE, the value is decremented by 1 */
                           TickType_t xTicksToWait ); /* Can wait forever, if set to portMAX_DELAY */

/* Waits for a notification, allowing the notification value to be altered bit by bit
Returns: pdFALSE if timed out, pdTRUE otherwise */
BaseType_t xTaskNotifyWait( uint32_t ulBitsToClearOnEntry, /* Bits to clear in the notification value before the enters the block state waiting for a notification */
                            uint32_t ulBitsToClearOnExit, /* Bits to clear in the notification value after the notification is received and the value is saved */
                            uint32_t *pulNotificationValue, /* Notification value resultant from the notification, before alteration according to ulBitsToClearOnExit */
                            TickType_t xTicksToWait ); /* Can wait forever, if set to portMAX_DELAY */

/* Clears a pending notification, not altering the notification value
Returns: pdPASS if there was a notification pendinge, otherwise pdFAIL */
BaseType_t xTaskNotifyStateClear( TaskHandle_t xTask ); /* xTask can be either the handle of another task that may have a notification pending or NULL, which reflects the task that called the function */


Full Demo's Task Notify


OK, API explained, now let's check what's happening in the DEMO. Basically what it does is create a common task, which will receive the notifications, thus represent the Consumer (check prvNotifiedTask()), and two Producers, one from a software timer (check prvNotifyingTimer()) and one from an interruption (check xNotifyTaskFromISR()). The interruption used is Tick interruption, through the use of the vApplicationTickHook().

The Producer from the interruption will notify the Consumer every 50 ms each time using a different API (vTaskNotifyGiveFromISR(), xTaskNotifyFromISR() and xTaskNotifyAndQueryFromISR()), always incrementing the notification value by one, but will only do that after the Producer from the sotware timer is already running. The Producer from the software timer always notifies the Consumer using the xTaskNotifyGive() and its period varies from 10 to 90 ms.

The Consumer will first raise some single tasks tests (check prvSingleTaskTests()), even before it creates the software timer:

  • Tries to take a notification (xTaskNotifyWait()), even though none has or will be given, in order to check if the timeout works;
  • Gives a notification to itself (xTaskNotifyAndQuery() setting the notification value without overwriting) and takes (xTaskNotifyWait()) it, in order to check if it will be done ASAP, thus no timeout-ing;
  • Checks the no-overwrite function by giving two notifications to itself  with different notification values and eSetValueWithoutOverwrite (xTaskNotify()) - the second should fail - and then taking only once (xTaskNotifyWait()) - the notification value should be equal to the first one given;
  • Same as before, but using overwrite: uses eSetValueWithOverwrite and different values, the value taken should be equal to last given.
  • Checks whether giving a notification with no changes to the value works by using xTaskNotify() with eNoAction and a value for the notification
  • Checks increments on the notification value by giving notifications for a known number of times (xTaskNotify() with eIncrement), then taking once and comparing the values; it tries to take again to ensure there are no more notifications pending;
  • Checks whether each bit of the notification value can be set by setting one bit at a time while giving (xTaskNotify() with eSetBits) and taking (the notification value is cleared before it starts through a xTaskNotifyWait() with all bits set on bits to clear on entry and no timeout) - it should run 32 times, since the notification value is 32 bit wide;
  • Checks if bits will be cleared on the entry and not on the exit by trying to take a notification, even though none was given, using xTaskNotifyWait() with bit0 (0x01) as bits to clear on entry and bit1 (0x02) as bit to clear on exit - as no notification was given, the bits are only cleared on entry.
  • Checks if bits will be cleared on exit by giving one notification, taking once with bit1 (0x02) as bits to clear on exit and trying to take again just to save the previous value.
  • Checks if the previous value is correctly received while notifying a task using xTaskNotifyAndQuery();
  • Finally, takes all notifications that might still exist (shouldn't be any), gives one generic notification and tries to clear the state twice (xTaskNotifyStateClear()), the first time should succeed and the second shouldn't.
Now back to the Consumer: after the tests described, it creates the software timer Producer, which will liberate the interruption Producer, and both will create notifications by incrementing the notification value, which means the value will be the amount of notifications given. So the consumer loop will:
  • Restart the software timer with a random period;
  • Try to take one notification with another random timeout and not clearing the value;
  • Try to take another notification, but this time not blocking but also not clearing the value;
  • Takes another notification, with the same timeout as before, but this time clearing the value;
  • Every 50 cycles, it raises the priority of the Consumer, receives all notifications by blocking until there is one available and reseting the counter (notification value), and restores the original priority (it tests the path where the Consumer is notified from an ISR and becomes the highest priority ready state task, but the pxHigherPriorityTaskWoken parameter is NULL - which it is in the tick hook that sends notifications to this task);
  • Finally, a counter of cycles is incremented.
There is one more function used, which is the Check function (xAreTaskNotificationTasksStillRunning()), responsible to check whether this Task Notify algorithm is still running. This function is called from the "Check Task" (prvCheckTask()), which is responsible to call, every 2.5 seconds, all check functions from all algorithms and warn in case something is going wrong. In the case of this algorithm, the function checks if the current number of cycles from the Consumer is higher than the last time it checked and if the number of times a notification was given is roughly the same of the taken ones. In case something is wrong, pdFAIL is returned.

Check Task


The check task (prvCheckTask()) is declared in main.c and is initialized with a low priority. Because the original code was designed to run in Windows, there was no problems with using printf(). With ArduinoMEGA things are obviously different, so a few changes were made. Instead of printing on the terminal, one LED is used to signalize that some problem occurred. A string (a static char *pcStatusMessage declared in main.c) is still used to signalize which error occurred, but it is treated as an array of chars with a defined size (mainERRORSIZE) and the messages always have this size, they are defined in a special header file (error_messages.h) and they're always transferred to the string using memcpy. Maybe in the future I could dispatch those messages through the serial port. Maybe.




Have fun!