Follow our illustrated blog on Embedded Software Architecture

How to build a hybrid solar/wind energy harvester?

Priority inversion

VN:F [1.9.22_1171]
Rating: 0.0/10 (0 votes cast)

I found the inspiration for this article while working on a consultancy job: Priority inversion.

In computer science, priority inversion is a (potential) problematic scenario in scheduling in which a high priority task is indirectly preempted by a medium priority task effectively inverting the relative priorities of the two tasks.

(http://en.wikipedia.org/wiki/Priority_inversion)

To put it more clearly.

  • We have a critical section called ‘CRIT’ in a portion of code.
  • Both low priority task ‘LPT’ and high priority task ‘HPT’ need to access it.
  • Medium priority task ‘MPT’ also needs to do some processing, however it does not access ‘CRIT’.
  1. Suppose LPT is running in CRIT.
  2. Then suddenly, HPT becomes runable. It will be scheduled to run until it reaches CRIT.
  3. But then HPT has to wait until LPT finishes CRIT: the priorities have been inverted temporarily which is normal in the system design, however LPT should free the lock as soon as possible.
  4. But it can even take longer for HPT to be able to continue, if MPT pops up.
  5. MPT preempts LPT, which results in HPT waiting even longer before LPT leaves CRIT: a higher priority task (HPT)  is preempted by a lower priority one (MPT).

There are various methods to ‘solve’ priority inversion. We list a few potential solutions here.

Disable interrupts

Disabling all interrupts during CRIT: no interrupts, no rescheduling. If CRIT is very small, this approach is usable, fast and simple but very crude.

Disable the scheduler

Disabling the scheduler during CRIT: interrupts can still happen, but it is not allowed to schedule another thread. This is also a good simple solution, but like “disabling all interrupts” it defeats (temporarily disables) the real-time priority scheduling.

Change thread priorities

Now the one which triggered my desire to handle this subject for this article. Boost the priority of LPT or HPT to an even higher priority (than HPT originally had) when entering CRIT: When in CRIT, LPT cannot be preempted by HPT or MPT. This might sound like a good idea, but the performance of changing priorities on the fly is not very good in most (RT)OS: It locks the scheduler for a short period but it also needs to do some administration and potentially scan and change the order in the runnable list.

Priority ceiling

A priority ceiling mutex is a lot like the previous. But now the mutex has its own priority which must be higher than the priority of HPT for this to work well: The thread in CRIT will get the priority of the priority ceiling mutex.

Automatic priority boosting

Another feature some (RT)OS provide is priority inheritance. The thread in CRIT will get the priority of the highest priority thread waiting for CRIT. Let us take a look at our example again: Suppose LPT is running in CRIT. Then suddenly, HPT becomes runable. It will be scheduled to run until it reaches CRIT but then it has to wait until LPT finishes CRIT: LPT is now boosted to the priority of HPT. If MPT pops up, MPT can no longer preempt LPT. HPT will resume after LPT leaves CRIT. When HPT finishes, MPT will run. And when MPT finishes, LPT will resume.

Avoid CRIT, no LOCKS

Another possible solution is avoiding locks and critical sections for example by using lock-less queues.

Anyway, do not do the change thread priority thing unless you know what you are doing, and even then, it is usually not the best option.

VN:F [1.9.22_1171]
Rating: 0.0/10 (0 votes cast)
Share

Progress update

Time for another update. The Green4 project is progressing steadily. In the last few months, we have been busy preparing the Green4 prototypes. Test software has been developed which is already very usable, but it is still in a state of flux as we … [Continue reading]

Embedding a Basic interpreter

The green4 stm32 cortex m3 microprocessor we selected is - according to today's standards - a rather small microprocessor in Flash (128KB) and RAM (8KB). why an interpreter The Green4 device is running control software on top of FreeRTOS, with a … [Continue reading]

Green4 charge controller: wiring diagrams part 2

Wiring diagram: wind turbine to dump load In contrast to solar panels, a wind turbine can't be disconnected in case it generates too much power. We need to brake it by attaching a load to it. However, wind power can't always flow through the charge … [Continue reading]

Green4 charge controller: wiring diagrams part 1

charge controller wiring batteries to external device

Introduction Instead of endlessly listing requirements and specifications, we prefer to demonstrate the architecture of our Green4 charge controller by means of wiring diagrams and other illustrations. The Green4 is designed to be a versatile … [Continue reading]

Open source implementations of malloc

On (very) small embedded systems without a full OS (e.g. because there is only a scheduler), one can (and should) usually live without dynamic memory allocation. But sometimes, it is really needed or it is just more convenient. It is possible to … [Continue reading]

DC motor control with the mosfet switch board

Although, there is no such thing as a general purpose mosfet switch board because of the wide variations in application specific load (resistive, capacitive, inductive or mixed) characteristics, we were able to investigate and demonstrate DC motor … [Continue reading]

Object-orientation in C – Part 4

We continue to build on the example in Part 3, but we go another step further. Even more abstraction and information hiding can be achieved by partially mimicking (part of) the COM manner of programming: strictly talking with interfaces. This style … [Continue reading]

Current limiting with PWM

For particular applications, such as our energy harvester or at least the battery charger part of it, the ability to control the current is an essential property. We must emphasize that the presented method will limit the average current; the … [Continue reading]

The embedded hierarchy – Part2

hw hierarchy groups

So how can we represent the embedded hierarchy in software? Before we can answer this question, we must make our goals clear: setting up and defining a new board should be as easy as possible, and code re-use should be optimal. With these … [Continue reading]