I’m going through FreeRTOS documents and trying to understand how synchronization works. I’ve read the docs but still have some doubts, so I’ll try to explain what I think and you guys can correct me if I’m wrong.
Say we have two tasks. A low-priority task is running, and suddenly a high-priority task becomes ready to run. In that case, the scheduler will preempt the low-priority and run the high-priority task, that part makes sense to me.
Now let’s bring a shared resource into the picture. Both low and high-priority tasks need it, and low priority task protected with a semaphore. If the low priority task is holding it, the high-priority task will try to take it, fail, and then go into the blocked state. When the low priority task finally releases the resource, the high-priority task should run.
Imagine the low-priority task is still holding the resource, and the high-priority task is already blocked waiting for it. Now, if the medium-priority task becomes ready, it will preempt the low-priority one (since it has higher priority). That means the low-priority task doesn’t get a chance to finish and release the resource, so the high-priority task stays blocked longer. Basically, the high-priority task ends up being delayed by the medium-priority task even though it has the highest priority.
From what I understand, this is what people call priority inversion.
Does my wording sound right here, or am I mixing something up in how FreeRTOS actually handles this?
Your description is correct. This is one of the reasons mutexes are recommended for mutual exclusion solutions - they contain a priority inheritance mechanism. Priority inheritance is one way to combat priority inversion.
With priority inheritance, the low priority task will have it’s priority ‘boosted’ to that of the high priority task as long as the high priority task is waiting for the mutex. This will prevent the medium priority task from interrupting the low priority task (since it’s priority is boosted). The low priority task will be able to complete it’s work and release the mutex. At that point the high priority task will preempt and take the mutex. Scheduling works as normal from there on.
Thanks. So here’s how I understand it. We’ve got three tasks: low, medium, and high priority. The low and high-priority ones both need the same resource, but the medium-priority task doesn’t. I’ve protected that resource with a mutex.
Now let’s say the low-priority task is holding the resource, and the high-priority task tries to grab it. Since it’s already locked, the high-priority task goes into the blocked state. Here’s where it gets interesting: if the medium-priority task becomes ready at this moment, normally it would preempt the low-priority one. But because we’re using a mutex, FreeRTOS will temporarily boost the low-priority task’s priority (priority inheritance). That way, the low-priority task keeps running, finishes its work, and releases the resource. As soon as that happens, the high-priority task can take it and continue.
Yep! A couple things I should have noted better in my initial response.
Priority boosting happens when the higher priority task attempts to acquire the mutex.
The lower priority task has its priority reset (aka boosting stops) when the higher priority task stops waiting for the mutex OR when it releases the mutex.
I’ve been reading about binary semaphores and I get that they can be used in a few different ways. One example I keep seeing is using them to synchronize an ISR with a task.
Suppose I have a global variable that gets incremented inside a timer interrupt, and then I read that variable inside a task.
What kind of problems could happen if I just read the variable in the task without using a semaphore?
The issue with reading a variable that is modified by an ISR is that, if the reading of the variable isn’t “atomic” (done with a single instruction), that it might get part of the value, then the interrupt occurs, the value changed, and then you get the rest of the value. This can give the task a value that never actually existed at one time. This isn’t a problem if the value is read with a single assembly instruction, as the interrupt can break that opertion into two pieces. This sort of issue isn’t helped with a semaphore, but needs a critical section that blocks the interrupt from happening during that period. As an example, FreeRTOS has a configuration flag to tell the system if the tick count can be read atomically, or if it needs a critical section.
Where the semaphore is used, is if the task wants to wait for the interrupt to happen, and the interrupt sets up data for the task, then the task can wait on a semaphore, that the interrupt gives, so the task doesn’t just spin waiting for a flag to be set.
I’m now looking into counting semaphores in FreeRTOS. From what I understand, they’re like binary semaphores but can keep track of more than one available resource.
Suppose I’ve got two UART peripherals and four different tasks, each with different priorities, that all want to use them. My thought is to use a counting semaphore initialized to “2” (since there are two UARTs). Whenever a task wants to use a UART, it would “take” from the semaphore, which decreases the count. If both UARTs are already busy and the count goes down to zero, the task would block until one becomes free. When a task finishes with a UART, it would “give” back to the semaphore, which increases the count, so another task can use it.
From what I understand, if multiple tasks are waiting on the semaphore, the scheduler will decide who gets the UART next based on task priority. So higher-priority tasks won’t get delayed by lower-priority one
That would be a good option if you don’t care which UART you are going to send on. You would still need some flag to indicate if each UARTS was “in use” so you can figure out which one you are going to use.
Counting semaphores seem to be used a lot less that binary semaphores as the use case of multiple “fungable” resources is somewhat less common.
I agree. I have seen very few instances of non binary sempahores in ~30 years of embedded development, and in those few instances, other synchronization mechanisms might have been better models of what was going on.
It is important to remember that the concept of a semaphore was the very first attempt to address concurrency (Dijkstra, early 1960). The original sempahore was a very abstract generic concept. Unfortunately, the term is frequently still used as a placeholder for everything synchronization (as can be seen in the function name set xSemaphoreXxx()), and thus, many newcomers tend to start with semaphores when studying concurrency and need to understand that 99% of all concurrency issues can be solved using muteces and interrupt inhibition (note that using semaphores as signals is not an instance of reentrancy prevention, but instead of establishing control flow in concurrent systems).