Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #536 > unrolled thread

Priority-Inversion

Back to article view | Back to comp.programming.threads

Contents

  Priority-Inversion Gerald Breuer <Gerald.Breuer@googlemail.com> - 2011-09-05 22:56 +0200
    Re: Priority-Inversion Gerald Breuer <Gerald.Breuer@googlemail.com> - 2011-09-06 03:15 +0200
    Re: Priority-Inversion Marcel Müller <news.5.maazl@spamgourmet.com> - 2011-09-06 08:30 +0200
      Re: Priority-Inversion Gerald Breuer <Gerald.Breuer@googlemail.com> - 2011-09-06 16:36 +0200
        Re: Priority-Inversion Marcel Müller <news.5.maazl@spamgourmet.com> - 2011-09-06 23:47 +0200
          Re: Priority-Inversion Gerald Breuer <Gerald.Breuer@googlemail.com> - 2011-09-07 00:37 +0200
            Re: Priority-Inversion Marcel Müller <news.5.maazl@spamgourmet.com> - 2011-09-07 12:06 +0200
        Re: Priority-Inversion Lewis NH2 <lew.nh2@googlemail.com> - 2011-09-09 09:56 -0700
    Re: Priority-Inversion Hallvard B Furuseth <h.b.furuseth@usit.uio.no> - 2011-09-06 12:34 +0200

#536 — Priority-Inversion

Can anyone tell me a *practical* problem where priority
-inversion through mutexes becomes a real problem?

[toc] | [next] | [standalone]

#537

Am 05.09.2011 22:56, schrieb Gerald Breuer:

> Can anyone tell me a *practical* problem where priority
> -inversion through mutexes becomes a real problem?

Hm, seems to me a problem which may occur mainly in
realtime-systems:
http://research.microsoft.com/en-us/um/people/mbj/mars_pathfinder/mars_pathfinder.html

[toc] | [prev] | [next] | [standalone]

#539

Gerald Breuer wrote:
> Can anyone tell me a *practical* problem where priority
> -inversion through mutexes becomes a real problem?

As soon as you share a resource that is protected by a mutex between 
threads with different priorities, priority inversion comes into play. 
If you need the different priorities of your threads you will also need 
to care about priority inversion. If you do not care about the priority 
inversion the different thread priority are optional too.

So the basic question is whether you need different priorities. This is 
the point where realtime processing comes into play.


Marcel

[toc] | [prev] | [next] | [standalone]

#541

Am 06.09.2011 08:30, schrieb Marcel Müller:

>> Can anyone tell me a *practical* problem where priority
>> -inversion through mutexes becomes a real problem?

> As soon as you share a resource that is protected by a mutex between
> threads with different priorities, priority inversion comes into play.
> If you need the different priorities of your threads you will also need
> to care about priority inversion. If you do not care about the priority
> inversion the different thread priority are optional too.

I aked for a practical problem, not for a explanation what PI is;
I'm aware of the theoretical problem.

[toc] | [prev] | [next] | [standalone]

#543

Gerald Breuer wrote:
> Am 06.09.2011 08:30, schrieb Marcel Müller:
> 
>>> Can anyone tell me a *practical* problem where priority
>>> -inversion through mutexes becomes a real problem?
> 
>> As soon as you share a resource that is protected by a mutex between
>> threads with different priorities, priority inversion comes into play.
>> If you need the different priorities of your threads you will also need
>> to care about priority inversion. If you do not care about the priority
>> inversion the different thread priority are optional too.
> 
> I aked for a practical problem, not for a explanation what PI is;
> I'm aware of the theoretical problem.

This is not only theory. It happens really always.

If you have a thread that feeds the S/G DMA registers of a sound device 
with physical addresses of audio buffers. If you pass the buffers from 
the application thread to the device driver thread using an ordinary 
queue protected by a mutex then the sound get drop outs under system 
load long before the driver runs out of buffers because of the priority 
inversion. The behavior is nearly the same as if the driver thread runs 
at the lower priority of the application thread.

So either you need a lock free queue or you have to raise the priority 
of the application thread before it acquires the mutex.


Marcel

[toc] | [prev] | [next] | [standalone]

#544

Am 06.09.2011 23:47, schrieb Marcel Müller:

>> I aked for a practical problem, not for a explanation what PI is;
>> I'm aware of the theoretical problem.

> This is not only theory. It happens really always.

There might be real examplex but what you told before is pure theory.

> If you have a thread that feeds the S/G DMA registers of a sound device
> with physical addresses of audio buffers. If you pass the buffers from
> the application thread to the device driver thread using an ordinary
> queue protected by a mutex then the sound get drop outs under system
> load long before the driver runs out of buffers because of the priority
> inversion. The behavior is nearly the same as if the driver thread runs
> at the lower priority of the application thread.

In this case every part of the chain that feeds some output must be
a realtime thread. So priority inversion isn't the real problem here.

> So either you need a lock free queue or you have to raise the priority
> of the application thread before it acquires the mutex.

Even with a lockfee queue and a feeding thread that isn't also realtime
you could get dropouts.

[toc] | [prev] | [next] | [standalone]

#546

Gerald Breuer wrote:
>> If you have a thread that feeds the S/G DMA registers of a sound device
>> with physical addresses of audio buffers. If you pass the buffers from
>> the application thread to the device driver thread using an ordinary
>> queue protected by a mutex then the sound get drop outs under system
>> load long before the driver runs out of buffers because of the priority
>> inversion. The behavior is nearly the same as if the driver thread runs
>> at the lower priority of the application thread.
> 
> In this case every part of the chain that feeds some output must be
> a realtime thread.

No, this is neither required nor sufficient.

Not sufficient, because the audio data must come from somewhere and so 
the I/O subsystem has to be taken into account too.

Not required because "realtime" depends on the time axis you are talking 
about. The more buffers you have the less are the realtime requirements. 
In fact you need a response time for each task. This time is different 
at each level. The driver thread has only the buffers of the physical 
device. They are usually quite small because of latency issues. So the 
required response time is in the order of some milliseconds. The 
application thread can prepare as much buffers as he likes. Typically in 
case of an MP3 player in the order of a few seconds. So the required 
response time is in the same order. A pure priority based scheduler is, 
of course, no ideal solution for this scenario. But a common work around 
is to start at normal priority and only if the buffer level reaches some 
low water mark, the priority of the application thread is raised for a 
short time. This ensures the audio stream to be continuous even under 
high system load, but without the risk to get the system unresponsive 
because of a high priority thread that has run into an infinite loop or 
simply insufficient system resources. Some platforms provide other 
schedulers that are not only priority based. E.g. on IBM OS/2 a normal 
priority thread will get some time slices every few seconds even if 
there are continuously some foreground threads ready to run. On this 
platform a sufficiently large ring buffer is enough to keep the sound 
playing with high system load.

> So priority inversion isn't the real problem here.

Believe me, it is. I have fixed such applications, that did not care 
about priority inversion.
Before the fix drop outs happen if you e.g. open a complex website with 
Firefox and keep the system under load (with redraws) by fastly dragging 
the vertical scollbar or resizing the window. After the fix the drop 
outs are gone.

The essential question behind patterns of priority inversion is, whether 
it makes sense to share a resource between threads of different priority.

>> So either you need a lock free queue or you have to raise the priority
>> of the application thread before it acquires the mutex.
> 
> Even with a lockfee queue and a feeding thread that isn't also realtime
> you could get dropouts.

You always could get dropouts, at least if the I/O gets stalled. But it 
more unlikely by some orders of magnitude if you have done your 
programming job right.

Of course, a realtime OS will not use a priority based scheduler to 
ensure the realtime guarantees. This would be not sufficient. In such 
environments you need some committed response times and committed system 
resources that cannot be used by others, regardless of any higher priority.


Another scenario I already have seen is a priority queue with tasks and 
a number of worker threads. The are high priority tasks in the queue and 
low priority tasks. So if a low priority application thread places a low 
priority task into the queue and for this locks the queue, the entire 
queue gets stuck even if a high priority worker is ready for work and 
there are high priority tasks in the queue.


Marcel

[toc] | [prev] | [next] | [standalone]

#555

Hi,

> I aked for a practical problem, not for a explanation what PI is;
> I'm aware of the theoretical problem.

We had a PI problem in our audio driver of our embedded device. The
result: very sporadically the sound stopped working, and the only
remedy was then to reboot the device.

Cheers,
/Lew

[toc] | [prev] | [next] | [standalone]

#540

Gerald Breuer writes:
> Can anyone tell me a *practical* problem where priority
> -inversion through mutexes becomes a real problem?

http://practicalcloudcomputing.com/post/2131110062/how-process-priority-inversion-can-burn-cpu-via

-- 
Hallvard

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web