Transitive priority inheritance

Hello developers! In my bachelor-thesis I’m analyzing the priority inversion phenomenon. As platform I choose an AVR ATmega128 and the FreeRTOS. I used V4.4.0 and implemented a priority inheritance mechanism as part of my thesis myself. When V4.5.0 came out, I discovered that the implementation provided by FreeRTOS V4.5.0 seems to be buggy. I found two problems (the problems are also discussed in [1]): #1) Falling back to original priority. In V4.5.0, a task giving back a mutex always falls back to it’s original priority. This is can be problematic. Consider the following scenario: Three Tasks T1, T2 and T3 with priorities P1 < P2 < P3 use two mutexes S1 and S2. t1: T1 takes S1 and S2. t2: T2 wants to take S2, is blocked and sets P1 = P2. t3: T3 wants to take S1, is blocked and sets P1 = P3. t4: T1 releases S1 and falls back to its original priority, although it still blocks T2. Therefore, it should fall back to P2. #2) Transitive priority inheritance. In V4.5.0, a task trying to take a mutex only increases the priority of the task holding the mutex. If the task is also blocked, it does not increase the priority of the task that is ready. Consider the following scenario: Three Tasks T1, T2 and T3 with priorities P1 < P2 < P3 use two mutexes S1 and S2. t1: T1 takes S1. t2: T2 takes S2. t3: T2 wants to take S1, is blocked and sets P1 = P2. t4: T3 wants to take S2, is blocked and sets P2 = P3. The priority of T1 is unchanged, although T3 is indirectly blocked by T1 through T2. Therefor only the priority of task T1 should be changed. My implementation solves problem #1 by keeping track of all mutexes a task owns and enumerating the correct next priority for a task if a mutex is released. Problem #2 is solved by keeping track of which mutex blocks a task so that the priority of the task can be raised. My question: My current implementation is neither written according to the FreeRTOS coding style nor tested with the current version. I’m willing to integrate it into the current version with accordance to the coding style if i know that there is someone out there who’s intersted in it, so please give me some feedback. PS: I can also provide source examples if needed. References: [1] Buttazzo, G. C.: hard Real-Time Computing Systems. Springer, 2. Edition, 2004 Greetings, Dominik Krenner

Transitive priority inheritance

Hi Dominik – thanks for your interesting post. You are right of course in that FreeRTOS.org assumes a simple usage scenario where only one semaphore is taken at a time (FreeRTOS.org is intended for small systems, but its scope is increasing all the time).  This should definitely be documented on the pages that include information on the priority inheritance scheme, as should the usage scenarios you highlight. I would be interested in seeing your code, in particular how much RAM and processing overhead is incurred.  This will impact the best route, improved code or improved documentation.  Please don’t send it to the SourceForge email address as this will strip out binary attachments, instead use r [d_o_t] barry at freertos.org. My personal bias is that priority inheritance is a very bad thing if you have a small hard real time system – it was added because people asked for it.  Best to design your system so that priority inheritance is never used if at all possible. Regards.