EEVblog Electronics Community Forum

Products => Computers => Programming => Topic started by: peter-h on February 04, 2023, 11:03:48 am

Title: The meaning of "priority inversion"
Post by: peter-h on February 04, 2023, 11:03:48 am
I am trying to work out what this fancy term means in the embedded context.

I think it means this:

Let's say you write a replacement for memcpy(). For < 10 bytes you move one at a time (if your CPU supports unaligned data). For < 100 bytes you move 4 at a time and then use single byte transfers to tidy up the ends. For >=100 you use DMA. Now, DMA is obviously not thread-safe, so you mutex around that bit. And if some task with a priority of 0 is calling this to move 1000 bytes, and a task with a priority of 10 calls memcpy() to move some other 1000 bytes, the latter task will get locked out. But only upon making that call to memcpy(), and only with len>=100.

So to guard against this you need to know what is going on, no? There is no obvious other way, short of a complicated solution which looks at the priority of each task wanting that mutex and if the prio=10 one is detected, it stops the DMA, saves its state, sets it up for the new use, then restores its state and restarts it for the prio=0 task. Horrible... and very sensitive to undocumented hardware issues.

This is perhaps another example
https://www.eevblog.com/forum/microcontrollers/anyone-here-familiar-with-lwip/msg4680643/#msg4680643 (https://www.eevblog.com/forum/microcontrollers/anyone-here-familiar-with-lwip/msg4680643/#msg4680643)
which is more subtle but only because TCP/IP is complicated. But it refers to a mutex which "supports priority inversion".
Title: Re: The meaning of "priority inversion"
Post by: DiTBho on February 04, 2023, 11:33:42 am
umm, the term "priority inversion" refers to a specific known problem with a specific class of schedulers.

Title: Re: The meaning of "priority inversion"
Post by: brucehoult on February 04, 2023, 12:05:44 pm
No.

First of all, DMA is a red herring. It's effectively a different (specialised) processor, and so is outside the scope of priority inversion.

The lock is relevant.

Priority inversion is nothing to do with interrupting a low priority task in order to run a high priority one. That is just normal operation.

Interrupting a low priority task that already has a lock in order to give the lock to a high priority task goes directly against what a lock is for. That's going to break things.

Priority inversion is when a high priority task is waiting for a lock that is held by a low priority task, and some intermediate task that doesn't care about that lock becomes runnable and preempts the low priority task, preventing progress towards releasing that lock. The "inversion" is that this medium priority task is getting to run when the high priority task can't.

The normal solution is to temporarily give the task holding a lock the same priority as the highest priority task that is waiting for that lock, so it can finish its work and free up the lock as soon as possible. The medium priority task won't run because it has lower priority than the boosted low priority task that holds the lock. Once the lock is freed the high priority task will run immediately, not the medium priority task (and the low priority task will drop back to low priority).

Yes, I've written production quality schedulers.
Title: Re: The meaning of "priority inversion"
Post by: tggzzz on February 04, 2023, 12:25:29 pm
Quote from: brucehoult on February 04, 2023, 12:05:44 pm
The normal solution is to give the task holding a lock the same priority as the highest priority task that is waiting for that lock, so it can finish its work and free up the lock as soon as possible. The medium priority task won't run because it has lower priority than the boosted low priority task that holds the lock. Once the lock is freed the high priority task will run immediately, not the medium priority task (and the low priority task will drop back to low priority).

I believe Microsoft Windows simply randomly changes priorities, in the hope that the thing will eventually become unjammed.

Given that completely uncontrolled and uncontrollable environment, it may even be the best workaround :(
Title: Re: The meaning of "priority inversion"
Post by: Sherlock Holmes on February 04, 2023, 05:13:22 pm
Quote from: peter-h on February 04, 2023, 11:03:48 am
I am trying to work out what this fancy term means in the embedded context.

I think it means this:

Let's say you write a replacement for memcpy(). For < 10 bytes you move one at a time (if your CPU supports unaligned data). For < 100 bytes you move 4 at a time and then use single byte transfers to tidy up the ends. For >=100 you use DMA. Now, DMA is obviously not thread-safe, so you mutex around that bit. And if some task with a priority of 0 is calling this to move 1000 bytes, and a task with a priority of 10 calls memcpy() to move some other 1000 bytes, the latter task will get locked out. But only upon making that call to memcpy(), and only with len>=100.

So to guard against this you need to know what is going on, no? There is no obvious other way, short of a complicated solution which looks at the priority of each task wanting that mutex and if the prio=10 one is detected, it stops the DMA, saves its state, sets it up for the new use, then restores its state and restarts it for the prio=0 task. Horrible... and very sensitive to undocumented hardware issues.

This is perhaps another example
https://www.eevblog.com/forum/microcontrollers/anyone-here-familiar-with-lwip/msg4680643/#msg4680643 (https://www.eevblog.com/forum/microcontrollers/anyone-here-familiar-with-lwip/msg4680643/#msg4680643)
which is more subtle but only because TCP/IP is complicated. But it refers to a mutex which "supports priority inversion".

As the others say this is all to do with locks and scheduling or lock holders and lock waiters, here's how the Windows OS (https://learn.microsoft.com/en-us/windows/win32/procthread/priority-inversion) handles that.
Title: Re: The meaning of "priority inversion"
Post by: peter-h on February 04, 2023, 05:23:09 pm
Quote
The normal solution is to temporarily give the task holding a lock the same priority as the highest priority task that is waiting for that lock, so it can finish its work and free up the lock as soon as possible. The medium priority task won't run because it has lower priority than the boosted low priority task that holds the lock. Once the lock is freed the high priority task will run immediately, not the medium priority task (and the low priority task will drop back to low priority).

Super explanation - thanks.

So, " a mutex which "supports priority inversion" means that the RTOS will automatically do the above when the lock is set? I wonder if FreeRTOS does this?

I've never written code which cares what pre-empts what. I've used priorities just to better allocate CPU time. If I want to stop RTOS task switching, I stop task switching. Maybe there is a way to stop specific tasks being switched to ?

The DMA example was meant as an example of a job which must be protected with a mutex, or things will break.

This is where LWIP ends up when doing e.g. a socket write with the "lock core" mode set

Code: [Select]

osStatus_t osMutexAcquire (osMutexId_t mutex_id, uint32_t timeout) {
  SemaphoreHandle_t hMutex;
  osStatus_t stat;
  uint32_t rmtx;

  hMutex = (SemaphoreHandle_t)((uint32_t)mutex_id & ~1U);

  rmtx = (uint32_t)mutex_id & 1U;

  stat = osOK;

  if (IS_IRQ()) {
    stat = osErrorISR;
  }
  else if (hMutex == NULL) {
    stat = osErrorParameter;
  }
  else {
    if (rmtx != 0U) {
      if (xSemaphoreTakeRecursive (hMutex, timeout) != pdPASS) {
        if (timeout != 0U) {
          stat = osErrorTimeout;
        } else {
          stat = osErrorResource;
        }
      }
    }
    else {
      if (xSemaphoreTake (hMutex, timeout) != pdPASS) {
        if (timeout != 0U) {
          stat = osErrorTimeout;
        } else {
          stat = osErrorResource;
        }
      }
    }
  }

  return (stat);
}

This
https://www.freertos.org/Real-time-embedded-RTOS-mutexes.html (https://www.freertos.org/Real-time-embedded-RTOS-mutexes.html)
suggests that FreeRTOS does exactly the right thing, as the default behaviour. Learn something every day :)

I can also see that raising the priority in this way is going to break some code...
Title: Re: The meaning of "priority inversion"
Post by: brucehoult on February 04, 2023, 10:49:15 pm
Quote
So, " a mutex which "supports priority inversion" means that the RTOS will automatically do the above when the lock is set? I wonder if FreeRTOS does this?

That would be "supports priority inversion AVOIDANCE". Or MITIGATION. Or something like that.

Quote
This
https://www.freertos.org/Real-time-embedded-RTOS-mutexes.html (http://nhttps://www.freertos.org/Real-time-embedded-RTOS-mutexes.html)
suggests that FreeRTOS does exactly the right thing, as the default behaviour. Learn something every day :)

yup.

Quote
I can also see that raising the priority in this way is going to break some code...

Shouldn't.

Code should always be designed to hold a lock for as short a time as possible.

But however long it takes, if it's ok for the high priority task to take the lock for however long it takes, preventing low and medium priority tasks from executing, it is for sure no worse to temporarily elevate the priority of a low priority task that is doing the same thing.
Title: Re: The meaning of "priority inversion"
Post by: Sherlock Holmes on February 05, 2023, 02:47:21 pm
Quote from: peter-h on February 04, 2023, 05:23:09 pm
Quote
The normal solution is to temporarily give the task holding a lock the same priority as the highest priority task that is waiting for that lock, so it can finish its work and free up the lock as soon as possible. The medium priority task won't run because it has lower priority than the boosted low priority task that holds the lock. Once the lock is freed the high priority task will run immediately, not the medium priority task (and the low priority task will drop back to low priority).

Super explanation - thanks.

So, " a mutex which "supports priority inversion" means that the RTOS will automatically do the above when the lock is set? I wonder if FreeRTOS does this?

I've never written code which cares what pre-empts what. I've used priorities just to better allocate CPU time. If I want to stop RTOS task switching, I stop task switching. Maybe there is a way to stop specific tasks being switched to ?

The DMA example was meant as an example of a job which must be protected with a mutex, or things will break.

This is where LWIP ends up when doing e.g. a socket write with the "lock core" mode set

Code: [Select]

osStatus_t osMutexAcquire (osMutexId_t mutex_id, uint32_t timeout) {
  SemaphoreHandle_t hMutex;
  osStatus_t stat;
  uint32_t rmtx;

  hMutex = (SemaphoreHandle_t)((uint32_t)mutex_id & ~1U);

  rmtx = (uint32_t)mutex_id & 1U;

  stat = osOK;

  if (IS_IRQ()) {
    stat = osErrorISR;
  }
  else if (hMutex == NULL) {
    stat = osErrorParameter;
  }
  else {
    if (rmtx != 0U) {
      if (xSemaphoreTakeRecursive (hMutex, timeout) != pdPASS) {
        if (timeout != 0U) {
          stat = osErrorTimeout;
        } else {
          stat = osErrorResource;
        }
      }
    }
    else {
      if (xSemaphoreTake (hMutex, timeout) != pdPASS) {
        if (timeout != 0U) {
          stat = osErrorTimeout;
        } else {
          stat = osErrorResource;
        }
      }
    }
  }

  return (stat);
}

This
https://www.freertos.org/Real-time-embedded-RTOS-mutexes.html (https://www.freertos.org/Real-time-embedded-RTOS-mutexes.html)
suggests that FreeRTOS does exactly the right thing, as the default behaviour. Learn something every day :)

I can also see that raising the priority in this way is going to break some code...

There are other synchronization mechanisms too, take a look at this overview from the Windows DDK.

https://learn.microsoft.com/en-us/windows-hardware/drivers/kernel/introduction-to-spin-locks (https://learn.microsoft.com/en-us/windows-hardware/drivers/kernel/introduction-to-spin-locks)

If this subject matter is somewhat new to you, I'd recommend getting a copy of Windows Internals, this is a great resource for anyone working with these concepts.

https://learn.microsoft.com/en-us/sysinternals/resources/windows-internals (https://learn.microsoft.com/en-us/sysinternals/resources/windows-internals)

or

https://www.amazon.com/Windows-Kernel-Programming-Pavel-Yosifovich/dp/1977593372/ref=sxin_10_mbs_w_global_sims?content-id=amzn1.sym.f6adc278-60fd-4516-8b02-0dbae28f44f1%3Aamzn1.sym.f6adc278-60fd-4516-8b02-0dbae28f44f1&crid=3MKJLADOE24BT&cv_ct_cx=windows+internals&keywords=windows+internals&pd_rd_i=1977593372&pd_rd_r=7b2f4a22-af5e-4abf-b37c-2b34e9df19d5&pd_rd_w=SRWBv&pd_rd_wg=fzPAS&pf_rd_p=f6adc278-60fd-4516-8b02-0dbae28f44f1&pf_rd_r=9Y56KB4JJD88WNMEJ0GN&qid=1675608796&sprefix=windows+inte%2Caps%2C486&sr=1-2-9e7645f9-2d19-4bff-863e-f6cdbe50f990 (https://www.amazon.com/Windows-Kernel-Programming-Pavel-Yosifovich/dp/1977593372/ref=sxin_10_mbs_w_global_sims?content-id=amzn1.sym.f6adc278-60fd-4516-8b02-0dbae28f44f1%3Aamzn1.sym.f6adc278-60fd-4516-8b02-0dbae28f44f1&crid=3MKJLADOE24BT&cv_ct_cx=windows+internals&keywords=windows+internals&pd_rd_i=1977593372&pd_rd_r=7b2f4a22-af5e-4abf-b37c-2b34e9df19d5&pd_rd_w=SRWBv&pd_rd_wg=fzPAS&pf_rd_p=f6adc278-60fd-4516-8b02-0dbae28f44f1&pf_rd_r=9Y56KB4JJD88WNMEJ0GN&qid=1675608796&sprefix=windows+inte%2Caps%2C486&sr=1-2-9e7645f9-2d19-4bff-863e-f6cdbe50f990)



Title: Re: The meaning of "priority inversion"
Post by: magic on February 05, 2023, 02:54:34 pm
Quote from: brucehoult on February 04, 2023, 10:49:15 pm
Quote
So, " a mutex which "supports priority inversion" means that the RTOS will automatically do the above when the lock is set? I wonder if FreeRTOS does this?
That would be "supports priority inversion AVOIDANCE". Or MITIGATION. Or something like that.
This mechanism is widely known as "priority inheritance".

I.e., a task holding a lock "inherits" the priority of the most important task currently waiting for the lock to be released.
Title: Re: The meaning of "priority inversion"
Post by: SuntUnMorcov on April 14, 2023, 08:01:36 am
Bit late to the party on this one, but the thread isn't that old so I'll add my two cents.

A mutex or synchronisation primitive that implements some protocol to avoid unbounded priority inversion is often said to be "priority inversion aware".  Numerous protocols exist, with differing characteristics and distinct differences in their implementation.

The method these protocols employ to avoid an unbounded priority inversion requires temporarily changing the priority of tasks / threads and the methodology behind them is often generally termed "priority inheritance".

Given the nature of your question, there is a great resource available on the Micro OS-II RTOS (uOS-II RTOS).  Not only does it have a nice general section on real-time embedded system concepts (see section 1.3), it also goes on to describe the implementation of the platform independent functionality of the RTOS literally line-by-line.  In my opinion, it's one of the best resources available to wrap your head around many RTOS concepts.  The resource is called the µC/OS-II User's Manual and you can find a free copy of it on the Farnell website here: https://www.farnell.com/datasheets/1950186.pdf (https://www.farnell.com/datasheets/1950186.pdf)
Title: Re: The meaning of "priority inversion"
Post by: peter-h on April 14, 2023, 10:34:41 am
Yes a nice clear "book" although I am amazed somebody would write 754 pages on how to use an RTOS :)

It probably depends on where one is coming from. For anyone who has done "real time" code, most of it will be obvious.

A nice trap is to have say two devices both on the same SPI

- an ADC with a 100ms conversion time
- a FLASH chip

The FLASH will sometimes be blocked for 100ms ;)

Obvious solutions are

- use different SPI controllers
- break up the 100ms into a multi-state process

None of this is especially complicated. But I know computer science professors like to invent loads of convoluted concepts, like various kinds of heaps which "cannot ever fragment".

The biggest problem I found with the RTOS (I use FreeRTOS) is software which others wrote, e.g. the 1990 printf/scanf Newlib library, which absolutely doesn't care about anything, uses the heap and then sticks mutexes everywhere, but seems widely used inembedded stuff.

Title: Re: The meaning of "priority inversion"
Post by: Siwastaja on April 14, 2023, 05:46:34 pm
Quote from: peter-h on April 14, 2023, 10:34:41 am
A nice trap is to have say two devices both on the same SPI

- an ADC with a 100ms conversion time
- a FLASH chip

The FLASH will sometimes be blocked for 100ms ;)

Solution: use one controlling state machine to access both, either using a fixed schedule, or some sort of fancier request queue system / arbiter.

95% of mutex use is because of poor design and forcing "parallel" "thread" thinking where it does not suit very well.
Title: Re: The meaning of "priority inversion"
Post by: tggzzz on April 14, 2023, 05:58:30 pm
Quote from: Siwastaja on April 14, 2023, 05:46:34 pm
95% of mutex use is because of poor design and forcing "parallel" "thread" thinking where it does not suit very well.

Softies find it difficult to think in terms of anything other than a single program counter. Then they try to force fit everything into that concept.

Hardies are more able to think in terms of events and FSMs.

A standard good starting point is input causes interrupt, ISR creates event and puts it in a FIFO. Forever loop pulls event from FIFO and processes it, optionally putting events in the same FIFO or the FIFO for other FSMs.

The half-sync half-async design pattern and Erlang language are exemplars of that.
Title: Re: The meaning of "priority inversion"
Post by: SiliconWizard on April 14, 2023, 07:26:33 pm
Quote from: tggzzz on February 04, 2023, 12:25:29 pm
Quote from: brucehoult on February 04, 2023, 12:05:44 pm
The normal solution is to give the task holding a lock the same priority as the highest priority task that is waiting for that lock, so it can finish its work and free up the lock as soon as possible. The medium priority task won't run because it has lower priority than the boosted low priority task that holds the lock. Once the lock is freed the high priority task will run immediately, not the medium priority task (and the low priority task will drop back to low priority).

I believe Microsoft Windows simply randomly changes priorities, in the hope that the thing will eventually become unjammed.

Well, however funky this approach may look, it's actually used not just by Windows (if it actually does that), and it's an approach that works.