hallo,
In a project that I’m following I happened to face a problem related to how the priority inheritance is managed in FreeRTOS, or rather how it is dehinerited.
First of all I make a recap of what I understood about priority inheritance management.
Here is Task 1 (green) which normally has low priority, and Task 2 (red) with high priority.
time t1: is running task 1 that takes mutex M1
time t2: task 1 takes mutex M2 too
time t3: task 1 is preempted by task 2
time t4: task 2 wants to take mutex M2, but it is owned by task 1. This causes task 2 to be blocked (waiting for the M2 mutex to be released), and the priority of task 1 to be raised to that of task 2. Task 1 is now running.
time t5: task 1 release M2. This should cause its priority to be lowered by allowing task 2 to run and take the M2 mutex in turn. FreeRTOS doesn’t do this, it keeps task 1 priority high.
time t6: task 1 release M1 (its last mutex owned). This is where FreeRTOS finally lowers the priority of task 1 again. Task 2 can now run and take M2.
time t7: task 2 release M2.
The time between t5 and t6 is given to task 1 when task 2 should get it. Otherwise is partially thwarted the effect of the priority inheritance on the priority inversion issue. Between t5 and t6 there is no reason why task 1 should have priority equal to task 2, leaving the possibility that task 1 delays further task 2.
After this premise, I would like to discuss how FreeRTOS could be modified to implement the priority inheritance protocol in a more correct way.
I read a couple of books and some online articles to learn more about the problem. All the sources I found agree that the priority must be lowered (but maybe better to say ‘recalculated’) when the mutex that made it rise is released.
So, thinking a little bit, I came to the following conclusion:
Having a function that given a mutex returns the highest priority among the processes blocked on that mutex (if any).
To have a function that given a mutex returns the process that owns it (if owned)
The recalculation of the priority should take place in the following cases:
A task releases a mutex. Its priority must be recalculated (it is not always the basepriority).
A task blocked on a mutex expires the timeout. The priority of the task that owns the mutex must be recalculated.
A task blocked on a mutex is deleted. If the task was blocked on a mutex, the priority of the process that owns it must be recalculated.
A task blocked on a mutex is forcibly unblocked (using xTaskAbortDelay()). If the task was blocked on a mutex, the priority of the process that owns it must be recalculated.
I think that’s all, but tell me if I forgot something or made a mistake.
I would be curious to know why on FreeRTOS the priority inheritance has been implemented so and never changed.
If it was a performance problem I think that adding some more fields in the tskTCB and xQUEUE structures (only in case of mutex i.e. configUSE_MUTEXES==1) it would be possible to get the feature without excessive computational cost.
could, the set of changes that I have roughly described above, be considered to be included in the main line of FreeRTOS?
Sure, will definitely look at this again. The FreeRTOS priority inheritance mechanism is described as “simplified”, partly for the reason you say - performance - and partly because a full priority inheritance mechanism requires quite a bit of logic.
In your case is there any way to prevent holding two mutexes at once?
Ok, but is my analysis that I described in the first post reasonable? Does it cover all cases? Can it help you? My hope is that the “quite a bit of logic” you are talking about is the one I described.
I could also try to contribute with some changes, but I would like to have a minimum guarantee that the direction is the correct one, since I have the feeling that this activity is a bit hard for a layman (or at least a non-expert) as I am.
Unfortunately no. I can only mitigate the problem, but not eliminate it completely.
The biggest issue is that to perform the calculation you want, every task needs to keep a list of every Mutex it holds, and every Mutex needs a list of tasks that are requesting it, and FreeRTOS only keeps the second list. Then you have a number of cases where you need to recalculate the priority of a task, and this can then ripple to other task.
Think of the case where.a high priority task, A, blocks on a mutex held by a lower priority task B, which is blocking on a mutex held by a lower priority task C, and we elevate these. Then A times out, and we have to re-evaluate the whole chain again.
A non-expert feeling: creating the first list should not be more difficult than the second. Am I underestimating this?
I tried to make a test: it seems to me that task C is never rised to the priority of task A, but it remains to the basepriority of task B. I believe that also this case is to be fixed. Anyway when the A task times out, the B task remains at the priority of the A task even if there is no more reason for that, while the C task is at the basepriority of task B. So the problem of priority inversion persists on task B and task C (task C blocks B even if it has lower priority).
And you’re right: the priority must be recalculated for each task in the chain. But if both lists you described were available, maybe it would not be so time consuming.
This is an interesting topic and something that we have pondered many times. I like the definition of engineering as being designing for the best compromise - but of course that is subjective. In this case we opted for a simplified priority inheritance scheme as typically FreeRTOS is used on small systems and the existing scheme is already a bit fat. A full scheme would be very involved and consume more RAM as well as take longer to execute. Currently semaphores are built on top of queues (which back in the day allowed us to add the functionality with almost no code size increases) - maybe what we need now is a completely separate semaphore implementation that users can opt to either build into the code or not (just like other optional features such as software timers, stream buffers, etc.). If we were to do that it would be almost exclusively for mutex type semaphores though as we already have task notifications as the preferred alternative to most all other semaphore use cases - there is no priority inheritance with notifications though although applications that require a task to hold more than more mutex at a time are few and far between.
I will say that I have some major use cases for semaphores that would be ill served with direct-to-task notifications. The biggest being driver wait for I/O completion. A task calls the driver function, which starts the I/O and waits on the semaphore. When the completion interrupt comes, it gives the semaphore, unblocking the task level driver. You could get the task ID and save it for the ISR, but then if the calling task uses direct-to-task notiications those provide difficulties for the driver. Maybe the new multi-set event notifications will get around this, but the semaphore seems cleaner.
I agree with @richard-damon. The application that made me raise the problem unfortunately strictly needs mutexes (surely it can’t use direct-to-task notifications) and it’s not possible to rewrite it to own only one mutex at a time, unfortunately in some moments we own more than two.
However I also understand @rtel’s points. One way could be to leave the choice to the users through a define symbol.
Interesting - this use case was one of the reasons direct to task notifications were originally introduced Driver libraries don’t need semaphores, they just capture the handle of the task that initiated a transaction (say sending data on a UART), then notify the task when the transaction is complete. The task can optionally wait (inside the UART send function, so transparent to the task), or carry on and get notified later. That mechanism is very light weight as it doesn’t require any additional RAM. In other models we use direct to task notifications in client/server style architectures whereby the client sends a request to a server via a queue. The request is captured in a structure, one field of which is the sending tasks handle. Then the server sends the reply directly to the task - that use case doesn’t avoid a semaphore but does avoid needing additional queues.
I apologize, but I have the feeling that the discussion is a bit diverting, or I am too profane to grasp every nuance.
I use mutexes to “protect” some data accessed from multiple tasks, or to prevent some functions from having to be re-entrant.
And anyway, the use of notifications in the past gave me more than a bother when I tried to use them to do the mutex work.
@mastupristi, he talk of semaphores/notification is a bit of.a a side track from the mutex topic. Yes, a mutex is the right primitive for protecting data that needs long term access or other resources (data that only needs short term access might be better served with a lighter weight critical section).
@rtel, the problem I have with using Direct-to-Task for this sort of shared device is that it interacts poorly with tasks that want to use it for other task specific operations. If it uses ‘bit-less’ notifications, then the code needs to deal with false wakeup if the task gets notified for some other purpose. And if we use a bit, we need to reserve it in ALL tasks that might use these devices, and those tasks can’t use the notification feature as a counting semaphore or a mailbox.
The new multi-box direct to task feature may relieve many of these issues but this will require the libraries that want to use this feature to have code doing it both ways to handle applications that haven’t enabled that feature yet, or test and generate an error to force it to be enabled if they move to a new version of the library.
I even went a step further and use C++ classes for tasks and device drivers. A task might own 1 or more HW devices and provides a higher level event driven interface to its services. All communication is notification based, inter-task and task local driver ISR signaling. There is no direct driver access by other tasks and I didn’t need any mutex protection of shared (driver) data or hardware. This might not be the ultimate solution for everything but it avoids at least problems with raw locks.
Well, it’s just a different design approach
Just my 2ct
I also use C++, but I don’t make all devices their own task, as that adds a lot of overhead. Interclass communications are typically implemented as member functions, and then inside the class, I may use mutex/semaphores/queue to implement the interaction.
For instance, I will define a class to handle serial ports with a generic base class common to all serial port devices, and a sub-class for a specific type of serial port. The base class defines a number of common formatting functions and a recursive mutex to allow a task to make sure a 'message; all goes out together.
Right, there are more appropriate ways to design an application. As usual - It depends
For the sake of completeness I don’t expose driver (e.g. serial port) interfaces. Instead there is e.g. a CSensor class providing GNSS position, temperature and pressure query interfaces using a UART and 2 I2C controllers internally owned by this task. Hence the drivers are very lean and driver level performance-sensitive/fine-grained locking is avoided.
It was helpful to partition a number of applications this way that we co-designed hardware and software matching the application requirements.
Sure, that’s ideal and not always possible.
@hs2 As you say, it depends. Just to make an example I take a single aspect of our applications: our applications deal with numerical signal processing. Very often the processing parameters (e.g. parameters and/or taps of a filter) are communicated via a protocol. But they must all be applied together (atomically).
Since the copy of a structure (even a big one) is not atomic and I can’t stop the interrupts (I have some processing interrupts that trigger in very few microseconds) the solution should have been to use mutex, so that the task using these parameters doesn’t risk inconsistencies. But these made me raise another problem for being “simplified”.
I had a somewhat similar problem to solve and used 2 records or structs. 1 with the last valid params and the associated result and a shadow/working record for the currently ongoing processing. They (their pointers) were swapped (atomically) on completion.
Not my invention - it’s a commonly used pattern.
Sources of unbounded priority inversions are semaphores/mutexes and critical sections, software queues e.g. FIFOs, where high prio items get queued up behind low prio items and hardware queues (similar to SW FIFOs only in HW e.g. high speed FIFO HW queues as communication channel) .
Possible solutions area:
selectively disable task preemption
priority inheritance protocol
priority ceiling protocol
ceiling priority protocol
For performance/overhead reasons, as Richard already pointed out, only a “basic priority inheritance mechanism” is implemented for FreeRTOS mutexes by default.
The longer version:
And, I agree with Richard, if something like that is implemented it should be configurable.
Here is a nice article about different kinds of mutexes in Linux: (Note that the more complex it gets the more overhead it adds):
Would it make sense to replace priority inheritance by Immediate Ceiling Priority Protocol? I believe it is easier to implement and consume less resources.
Could you explain how it differs and would use less resources than FreeRTOS’s current implementation?
Remember, FreeRTOS is using an INTENTIONALLY simplified of Priority Inheritance to minimize resource usage (like RAM and CPU cycles). In particular, there is no list of all the mutexes a task currently holds/is pending on. Only a count of how many it holds. This makes a lot of the more complicated systems impossible to implement.
With the assumption that few tasks will hold multiple Mutexes as one and only for a short time, the inefficiencies aren’t significant.
Driver libraries don’t need semaphores, they just capture the handle of the task that initiated a transaction (say sending data on a UART), then notify the task when the transaction is complete. The task can optionally wait (inside the UART send function, so transparent to the task), or carry on and get notified later. That mechanism is very light weight as it doesn’t require any additional RAM. In other models we use direct to task notifications in client/server style architectures whereby the client sends a request to a server via a queue. The request is captured in a structure, one field of which is the sending tasks handle. Then the server sends the reply directly to the task - that use case doesn’t avoid a semaphore but does avoid needing additional queues.
