Quality RTOS & Embedded Software

 Real time embedded FreeRTOS RSS feed 
Real time embedded FreeRTOS mailing list 
Quick Start Supported MCUs PDF Books Trace Tools Ecosystem TCP & FAT Training


Transitive priority inheritance

Posted by Korexio on August 13, 2008
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.

[1] Buttazzo, G. C.: hard Real-Time Computing Systems. Springer, 2. Edition, 2004

Dominik Krenner

RE: Transitive priority inheritance

Posted by Richard on August 13, 2008
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.


[ Back to the top ]    [ About FreeRTOS ]    [ Sitemap ]    [ ]

Copyright (C) 2004-2010 Richard Barry. Copyright (C) 2010-2016 Real Time Engineers Ltd.
Any and all data, files, source code, html content and documentation included in the FreeRTOSTM distribution or available on this site are the exclusive property of Real Time Engineers Ltd.. See the files license.txt (included in the distribution) and this copyright notice for more information. FreeRTOSTM and FreeRTOS.orgTM are trade marks of Real Time Engineers Ltd.

Latest News:

FreeRTOS V9.0.0 is now available for download.

Free TCP/IP and file system demos for the RTOS

Sponsored Links

⇓ Now With No Code Size Limit! ⇓
⇑ Free Download Without Registering ⇑

FreeRTOS Partners

ARM Connected RTOS partner for all ARM microcontroller cores

Renesas Electronics Gold Alliance RTOS Partner.jpg

Microchip Premier RTOS Partner

RTOS partner of NXP for all NXP ARM microcontrollers

Atmel RTOS partner supporting ARM Cortex-M3 and AVR32 microcontrollers

STMicro RTOS partner supporting ARM7, ARM Cortex-M3, ARM Cortex-M4 and ARM Cortex-M0

Xilinx Microblaze and Zynq partner

Silicon Labs low power RTOS partner

Altera RTOS partner for Nios II and Cortex-A9 SoC

Freescale Alliance RTOS Member supporting ARM and ColdFire microcontrollers

Infineon ARM Cortex-M microcontrollers

Texas Instruments MCU Developer Network RTOS partner for ARM and MSP430 microcontrollers

Cypress RTOS partner supporting ARM Cortex-M3

Fujitsu RTOS partner supporting ARM Cortex-M3 and FM3

Microsemi (previously Actel) RTOS partner supporting ARM Cortex-M3

Atollic Partner

IAR Partner

Keil ARM Partner

Embedded Artists