Deadlock, starvation, priority inversion

nobody wrote on Saturday, April 29, 2006:


I was wondering if anyone can tell me what FreeRTOS does for handling the situations like deadlock, starvation, priority inversion or race conditions.


nobody wrote on Sunday, April 30, 2006:

If you design deadlock into your application, then it will deadlock.  If you design your application so that a task will starve then it will starve.  If you design priority inversion into you app then this will happen also.  FreeRTOS will do what you ask it to do and (hopefully) behave in a deterministic way when doing so.  It does not change your design.

jwestmoreland wrote on Sunday, April 30, 2006:

I’m not sure who the author is of this response; but these are legit. questions.

Nobody - have you bothered to read “MicroC OS II: The Real Time Kernel (With CD-ROM) (Hardcover)
by Jean J. Labrosse” by any chance?  It’s a good book and explains this stuff pretty well.

I imagine that FreeRTOS performs well in all of these areas - Richard has done a good job.

The proof’s in the pudding, right?

John W.

anonymous wrote on Sunday, April 30, 2006:

Here is my understanding of these issues:


Deadlock prevention is a matter of system design. The best a scheduler can do is deadlock detection, which has proven to be a very costly feature. Databases often do it, but I don’t know of any kernels that do.


There are many causes of starvation - most are a matter of system design when you have a purely preemptive scheduler (no time slicing). One of the causes is priority inversion, which can be addressed if priorities can be adjusted dynamically.

Priority Inversion

The common way to address priority inversion (on a binary semaphore, say) is to raise the priority
of the task holding the semaphore to be above that of all waiting tasks. It is costly, but often practical, if done outside the kernel. FreeRTOS does not do it, but it can be done by building your own binary semaphore mechanism. At the same time you can put in recursion protection (same task trying to lock the same semaphore recursively).

uCOS has a form of inversion protection in later versions. If I recall correctly, tasks generally have statically assigned fixed priorities. However there is a special mechanism in which a task taking a semaphore gets its priority boosted to some preset level until it releases the semaphore. The choice of the preset level is a matter of system design. (Or maybe I am confusing uCOS with some other small kernel).

I prefer the FreeRTOS dynamic priorities and building some of the higher level kernel features on top of it. This allows customizing the kernel to a scale appropriate for the embedded application.


rtel wrote on Monday, May 01, 2006:

Just to add what Glen has already said:

Regarding starvation, the scheduling policy of FreeRTOS is that of a traditional priority based preemptive kernel.  The kernel ‘promises’ that the highest priority task that is able to run is the task given processing time - and if more than one such task exists then these tasks will share processing time (timeslice).  The application design takes advantage of this known, deterministic behaviour, with tasks created and priorities set to ensure that your tasks get the processing time required.  If a task is being starved of processing time then either:

+ A higher priority task is legitimately using the processor, and as it is a higher priority task this is what should happen and under no circumstances should the kernel intervene otherwise it will break its ‘promise’.

+ A higher priority task is wasting processing time, in which case the application design needs modification.

+ An erroneous situation has occurred that is causing the higher priority task to thrash - in which case there is a problem anyway.

Regarding priority inversion, I have considered adding a priority inheritance mechanism in using a conditional compilation constant, but don’t like using too many conditional compilations as it lowers the readability of the code.

Adding a priority inversion mechanism would be straight forward but cost a little RAM (8 bytes per queue on a 32bit architecture?) and processing time.  When a task takes a semaphore (implemented using a queue, hence 8bytes per queue) the owner of the semaphore is stored in the semaphore structure.  Then when another task attempts to take the semaphore it checks the priority of the current owner, and raises its priority if necessary.  When releasing a semaphore you need to then check and reset the task priority if necessary.  So you can see I (think) this would be very simple, however…

…IMHO priority inheritance is not necessary in *most* small embedded systems, for which FreeRTOS is targeted.  In larger systems resource management can become problematic and a priority inheritance system may be warranted more.  In smaller systems I would prefer for a single task to manage a resource where ever possible.  For example, in the PC demo all tasks write to the display which is therefore a shared resource.  There is a display management task which is the only task allowed to access the display.  If any other task wants to write out a string, it sends the display management task a pointer to the string and the display management task has exclusive rights to write it out.  Of coarse this type of scheme is not always suitable but there are ways and means normally and my preference is for the kernel not to interfere or make assumptions.

Priority inheritance itself is only a partial solution and its triggering may be symptomatic of a design issue lurking in the code.  The high priority task still has to wait for the low priority task to finish with the resource and release it, albeit much sooner than if its priority had not been raised.