Article (Priority Inversion)

QNX Newsgroups (Archives) qnx.cafe
1

I’ve written an article on priority inversion; anyone care
to critique it? Comments appreciated.

http://www.parse.com/~rk/articles/priority.html

Thanks in advance!

Cheers,
-RK

–
[If replying via email, you’ll need to click on the URL that’s emailed to you
afterwards to forward the email to me – spam filters and all that]
Robert Krten, PDP minicomputer collector http://www.parse.com/~pdp8/

2

In article <c0bm80$6lj$1@inn.qnx.com>, rk@parse.com says…

I’ve written an article on priority inversion; anyone care
to critique it? Comments appreciated.

http://www.parse.com/~rk/articles/priority.html

Thanks in advance!

Cheers,
-RK

Good article, brave enough to tell the truth that the priority
inheritance does not protect against priority inversion. Probably there
is no universal cure for priority inversion suitable for operation system
as a whole, but good design can help to avoid the problem in every
particular case. The priority queueing solution is such an example, but
it is too complicated, IMHO. Thus it might be useful in very particular
case :slight_smile:
BTW, I don’t think the idea with the array is good, especially if it
requires a thread for every element of array. (Well, they are supposed to
be blocked, and what? Currently we have 64 levels, but it was promised to
rise that number drasticly in nearest future). Why can’t it be two-
dimensional list? If some client sends request we just go through list
(in direction of priority levels :slight_smile:) - if there is element with this
priority level, we add request into that list (in directions of queued
requests :slight_smile:); if there is element with lower priority and next element is
with higher priority (so there is no given priority in the list), we
insert new element for given priority into list and add request into this
element (which is list itself :slight_smile:) Huh, I love simplify things :smiley:

Thanks for article.

Cheers,
Eduard.

3

ed1k <nonexisting@invalid.domain> wrote:

In article <c0bm80$6lj$> 1@inn.qnx.com> >, > rk@parse.com > says…
I’ve written an article on priority inversion; anyone care
to critique it? Comments appreciated.

http://www.parse.com/~rk/articles/priority.html

Thanks in advance!

Cheers,
-RK



Good article, brave enough to tell the truth that the priority
inheritance does not protect against priority inversion. Probably there
is no universal cure for priority inversion suitable for operation system
as a whole, but good design can help to avoid the problem in every
particular case. The priority queueing solution is such an example, but
it is too complicated, IMHO. Thus it might be useful in very particular
case > :slight_smile:

Thanks! It was presented as an example, not as a “universal solution”.

BTW, I don’t think the idea with the array is good, especially if it
requires a thread for every element of array. (Well, they are supposed to
be blocked, and what? Currently we have 64 levels, but it was promised to
rise that number drasticly in nearest future). Why can’t it be two-
dimensional list? If some client sends request we just go through list
(in direction of priority levels > :slight_smile:> ) - if there is element with this
priority level, we add request into that list (in directions of queued
requests > :slight_smile:> ); if there is element with lower priority and next element is
with higher priority (so there is no given priority in the list), we
insert new element for given priority into list and add request into this
element (which is list itself > :slight_smile:> ) Huh, I love simplify things > :smiley:

If I understand you correctly, it’s not the size of the array that you
are really complaining about, but rather the number of threads required.
I really don’t see a difference between:

block_array_t *blocks [64];

versus

block_array_t *block_list;

in terms of memory storage – 64 x NULL pointer is 256 bytes. Even if the
number of priorities is raised to 256, that still only comes out to 1k.

The suggestion of using the thread pool to manage the number of threads
is where you will get the savings in the “large number of priority levels”
case… right?

Thanks for article.

NP.

Cheers,
-RK

–
[If replying via email, you’ll need to click on the URL that’s emailed to you
afterwards to forward the email to me – spam filters and all that]
Robert Krten, PDP minicomputer collector http://www.parse.com/~pdp8/

4

In article <c0dcq4$j7f$1@inn.qnx.com>, rk@parse.com says…
[blatantly cut]

If I understand you correctly, it’s not the size of the array that you
are really complaining about, but rather the number of threads required.
I really don’t see a difference between:

block_array_t *blocks [64];

versus

block_array_t *block_list;

in terms of memory storage – 64 x NULL pointer is 256 bytes. Even if the
number of priorities is raised to 256, that still only comes out to 1k.

The suggestion of using the thread pool to manage the number of threads
is where you will get the savings in the “large number of priority levels”
case… right?

Yes, my main concern was about the number of threads… so the idea was
to create the thread with a given priority as soon as there is some job
in queue for this priority, and destroy the thread if queue is empty.
Indeed, it doesn’t matter in which way it’s implemented, as an array or
as a linked list.

As for thread pool, if you mean thread pool as it is currently
implemented in Neutrino, I am not quite understand how to tie up the
priority array and thread pool. But I didn’t spend much time to learn the
problem… buzy time (and mostly quite far from neutrino: asm), sorry.

Eduard.

5

Hi Robert,

I don’t understand the benefit of a priority request queue when we have
thread pools? I understand and agree with the packetization of large
requests, but thread pools seem synonymous to the priority request queue
scheme you speak of. It seems to me that the OS’s thread scheduler is
supplemented with this request queue, and I’m a little slow in uderstanding
why.



Thanks,

Kevin


“Robert Krten” <rk@parse.com> wrote in message
news:c0bm80$6lj$1@inn.qnx.com…

I’ve written an article on priority inversion; anyone care
to critique it? Comments appreciated.

http://www.parse.com/~rk/articles/priority.html

Thanks in advance!

Cheers,
-RK

–
[If replying via email, you’ll need to click on the URL that’s emailed to
you
afterwards to forward the email to me – spam filters and all that]
Robert Krten, PDP minicomputer collector > http://www.parse.com/~pdp8/

6

Ok…I think I see it.



What you are saying is:



"If you rely on thread pools, you have the potential of running out of
threads to service requests.

If you have a fixed number of threads assigned to each level of priority,
then you always have a thread available if it isn’t doing something at its
priority already, if it is, you get queued and sent on your way."



Ok…so this is essentially asynchronous, you could put a flag in your
message that makes in synchronous, such that you get held until your request
is serviced.



The other thing is though…aren’t high priority MsgSend()s given available
threads in thread pools over lower priority MsgSend()s? In other words,
even if you are able to saturate a server with lower priority requests and
temporarily use up all the available threads in a server’s pool, as soon as
one completes, no matter how many lower priority threads are in place, the
higher priority one will get the next available thread, right?



Ahhh…it doesn’t solve the granularity problem your solving with the
priority queued stuff though. You’re essentially reserving threads for
each priority level, which the current QNX thread pool model
lacks…MsgReceive() should have a priority parameter. It would only
unblock if a message of priority n is sent.



Clever stuff RK, as usual. I still haven’t ordered your new book. Hope you
have a copy or two left…



Regards,

Kevin





“Kevin Stallard” <kevin@fffflyingrobbbotsss.com> wrote in message
news:c0usro$cjj$1@inn.qnx.com…

Hi Robert,

I don’t understand the benefit of a priority request queue when we have
thread pools? I understand and agree with the packetization of large
requests, but thread pools seem synonymous to the priority request queue
scheme you speak of. It seems to me that the OS’s thread scheduler is
supplemented with this request queue, and I’m a little slow in
uderstanding
why.



Thanks,

Kevin


“Robert Krten” <> rk@parse.com> > wrote in message
news:c0bm80$6lj$> 1@inn.qnx.com> …
I’ve written an article on priority inversion; anyone care
to critique it? Comments appreciated.

http://www.parse.com/~rk/articles/priority.html

Thanks in advance!

Cheers,
-RK

–
[If replying via email, you’ll need to click on the URL that’s emailed
to
you
afterwards to forward the email to me – spam filters and all that]
Robert Krten, PDP minicomputer collector > http://www.parse.com/~pdp8/