Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Torsten Kröger]

Hi everyone,

to summarize my discussion form yesterday:

1. I would like to implement 'real' synchronous message passing using
the posix skin. 'Real' synchronous message passing shall mean that a
receiver _always_ inherits the priority of the sender. Right now, I
think this is not possible. Please let me know, if anyone knows a
possibility.
 
2. 'Real' synchronous message passing could be realized with the native
skin, because here a sender RT_TASK is able to change the priority of a
blocked receiver RT_TASK before sending a message to it. Is this
correct? If yes, I might consider changing the skin.

3. Is there a possibility of using the native skin and the posix skin at
the same time?

4. I guess, it more a philosophical question: wouldn't another concept
of send/receive/reply-messaging lead to a general avoidance of priority
inversion? This is surely not an easy point regarding its
implementation, but when looking at long-term aims of the Xenomai
project, this might be a point, which worth to discuss about -
especially when heading for distributed systems, where
send/receive/reply-messaging is one of the key methodologies for
real-time systems.


Any reply posting is highly appreciated again :-)
 

Best regards,
Torsten

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Gilles Chanteperdrix]

On 8/10/07, Torsten Kröger <t.kroeger@domain.hid> wrote:
> Hi everyone,
>
> to summarize my discussion form yesterday:
>
> 1. I would like to implement 'real' synchronous message passing using
> the posix skin. 'Real' synchronous message passing shall mean that a
> receiver _always_ inherits the priority of the sender. Right now, I
> think this is not possible. Please let me know, if anyone knows a
> possibility.

We could add a new flag to posix message queues attributes to have
such a priority inheritance. Of course, this would be a non portable
extension.


-- 
                                               Gilles Chanteperdrix

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 842 bytes --]

Torsten Kröger wrote:
> 3. Is there a possibility of using the native skin and the posix skin at
> the same time?

Yes: Write your message passing protocol as an RTDM protocol device.
That way you would have the socket API as interface (for all skins!) and
could even fiddle with priority as you like. We went this way for our
TiMS (Tiny Message Passing Service) in the RACK framework [1]. It's
fairly specialised due to its roots and its applications domain, but the
general idea is surely transferable.

Note that we do _not_ play with the receiver priorities, we rather
prefer a stable _static_ system configuration. That's better for hard
RT, and prio-inheriting MPI generally doesn't help about worst-case
latencies anyway (given a non-broken static prio design).

Jan

[1] http://developer.berlios.de/projects/rack


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Gilles Chanteperdrix]

On 8/10/07, Jan Kiszka <jan.kiszka@domain.hid> wrote:
> Torsten Kröger wrote:
> > 3. Is there a possibility of using the native skin and the posix skin at
> > the same time?
>
> Yes: Write your message passing protocol as an RTDM protocol device.
> That way you would have the socket API as interface (for all skins!) and
> could even fiddle with priority as you like. We went this way for our
> TiMS (Tiny Message Passing Service) in the RACK framework [1]. It's
> fairly specialised due to its roots and its applications domain, but the
> general idea is surely transferable.

It is even possible to use the native skin and the posix skin at the
same time without resorting to RTDM. We try as much as possible to
allow one skin services to be called by a thread belonging to the
other skin. You have to look at each service documentation to know
from what context it can be called.
Posix message queues services, for example, may be called from thread
created by any skin.

-- 
                                               Gilles Chanteperdrix

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Herman Bruyninckx]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2669 bytes --]

On Fri, 10 Aug 2007, Torsten Kröger wrote:

> to summarize my discussion form yesterday:
>
> 1. I would like to implement 'real' synchronous message passing using
> the posix skin. 'Real' synchronous message passing shall mean that a
> receiver _always_ inherits the priority of the sender. Right now, I
> think this is not possible. Please let me know, if anyone knows a
> possibility.
>
> 2. 'Real' synchronous message passing could be realized with the native
> skin, because here a sender RT_TASK is able to change the priority of a
> blocked receiver RT_TASK before sending a message to it. Is this
> correct? If yes, I might consider changing the skin.
>
> 3. Is there a possibility of using the native skin and the posix skin at
> the same time?
>
> 4. I guess, it more a philosophical question: wouldn't another concept
> of send/receive/reply-messaging lead to a general avoidance of priority
> inversion? This is surely not an easy point regarding its
> implementation, but when looking at long-term aims of the Xenomai
> project, this might be a point, which worth to discuss about -
> especially when heading for distributed systems, where
> send/receive/reply-messaging is one of the key methodologies for
> real-time systems.
>
>
> Any reply posting is highly appreciated again :-)

One simple answer: if your distributed system relies on priority inversion
"solutions" and "real" synchronous message passing the way you describe,
it's a bad design!

And don't expect your RTOS to solve that bad design by adding more and more
"features", especially "priority inversion" features... Priority inversion
efficiency and determinism simply don't scale with increased distribution.

As soon as you want to use message passing in a distributed environment,
design your system such that it is _robust_ against priority inversions. if
it is not, your system will not survive future extensions, ports to newer
hardware etc.

What you want to achieve (I think) with "real" synchronous message passing
is that the receiver handles a message as soon as the sender has sent it,
right? Well, if your specification involves _really_ this form of coupling
between sender and receiver, the _only_ good solution is to serialize them
both in the same thread... Taking this discussion a bit further, this
synchronous message passing issue is key to the longlasting discussion
between micro-kerels and monolithic kernels: the former can be more
_robust_ in a distributed way but in practice don't achieve the
_efficiency_ of the monolithic kernel.

Herman

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Torsten Kröger]

>One simple answer: if your distributed system relies on priority
inversion
>"solutions" and "real" synchronous message passing the way you
describe,
>it's a bad design!
>
>And don't expect your RTOS to solve that bad design by adding more and
more
>"features", especially "priority inversion" features... Priority
inversion
>efficiency and determinism simply don't scale with increased
distribution.
>
>As soon as you want to use message passing in a distributed
environment,
>design your system such that it is _robust_ against priority
inversions. if
>it is not, your system will not survive future extensions, ports to
newer
>hardware etc.
>
>What you want to achieve (I think) with "real" synchronous message
passing
>is that the receiver handles a message as soon as the sender has sent
it,
>right? Well, if your specification involves _really_ this form of
coupling
>between sender and receiver, the _only_ good solution is to serialize
them
>both in the same thread... Taking this discussion a bit further, this
>synchronous message passing issue is key to the longlasting discussion
>between micro-kerels and monolithic kernels: the former can be more
>_robust_ in a distributed way but in practice don't achieve the
>_efficiency_ of the monolithic kernel.

I think we have different opinions on this :-)

Thanks to Herman, Jan, Philippe, and Gilles for their recent answers. I
know that this posting is quite long, but I hope you can find time and
interest to read it.

I'm not suggesting to add more and more features, I just think that
there might be the possibility of an important improvement in the
Xenomai send/receive/reply-messaging principle. May be I'm wrong, I have
never designed an operating system, I am no expert in this field but
from the user's point of view I would like to try to explain it like
this:

It’s the task of the scheduler that the task with the highest priority
gets scheduled as soon as the task needs the CPU. If this is not
possible, because one or more other tasks with lower priorities are
working in critical sections, which are also supposed to be used by the
highest-priority task, the priority inheritance protocol rules [1]. But
when looking at synchronous message passing, we have a different
situation. We don’t have critical sections here. A receiver (server)
works for a sender (client) from the reception of a message
('rt_task_receive') on until it calls 'rt_task_reply', i.e. the section
from 'rt_task_receive' to 'rt_task_reply' is not the same as a section
protected by a mutex or a semaphore. Everything a receiver does within
this section, is done on behalf of the client and should be done with
the priority of the client except there are other higher-priority
clients waiting for the receiver.

In the following I would like to explain, (i) the way it is implemented
right now and (ii) the way I would expect synchronous message passing to
work. Again, I don't want to 'play' with priorities or to add more and
more features, I would just like to make a (perhaps important)
suggestion or to understand, why my opinion on this is wrong. 

Suppose T1, T2, T3, T4, and T5 are five tasks in ascending order of
priority. T3 is 'receive' blocked ('rt_task_receive').

------------
(i)
"A receiving task only inherits the priority a sender, if its _current
priority_ is lower than the one of the sender. This inheritance rules
until 'rt_task_reply' has been called by the receiver."

Example 1:
If task T3 is 'receive' blocked, and T4 'sends' a message to T3, the
priority of T4 will be assigned to T3 until T3 calls 'rt_task_reply'. If
T5 should also send a message to T3, while T3 is still between
'rt_task_receive' and 'rt_task_reply' (for the message from T4), the
message of T5 will be queued and the priority of T3 will be raised to
the one of T5. After T3 has called 'rt_task_reply' for the message of
T4, it remains at the priority of T5, receives the message from T5,
works on it, replies it, and then its priority is set back to its basic
one. We don't have priority inversion here.

Example 2:
Another situation would be that T1 sends a message to T3, which would
then remain at its basic priority, even if T2 changes its state to ready
while T3 is processing the message for T1. As result, T2 would not be
scheduled, and we have priority inversion here. Exactly this priority
inversion problem can be avoided.

------------
(ii)
"A receiving task inherits the highest priority of all tasks that have
sent a message to it. This inheritance rules until 'rt_task_reply' has
been called by the receiver."

Example 1:
Same behavior as above.

Example 2:
If T1 sends a message to T3, T3 inherits the priority of T1 until T3
calls 'rt_task_reply'. If T2 gets ready while T3 works on the message
from T1, T2 would be scheduled, and we don't have the priority inversion
problem anymore. If T2 would then get pre-empted by T5 for example, and
if T5 should also send a message to T3, T3's priority would raise to the
one of T5 of course - i.e. the same way as in (i) and the
highest-priority task is always privileged.
------------

I do understand that when we work with static priorities, the developer
is able to prevent this situation by assigned appropriate priorities to
all tasks. But therefore, he needs to know the entire system and the
dependencies between _all_ tasks. In small systems, this is indeed
possible, of course, but in large systems with many tasks, the
probability of miss-configuring the system increases rapidly, and in
very big systems real-time capability cannot be guaranteed when using
synchronous message passing. This problem becomes even bigger, when
looking at distributed systems, of course.

The only disadvantage I see is that we always have to perform a
rescheduling in (ii), when a task receives a message sent from another
task with another priority. In (i) we only perform a rescheduling when a
higher-priority task sends a message to a receiver. As result the
efficiency _slightly_ decreases when low priority tasks communicate with
high-priority tasks via synchronous message passing, but 

- the system is still deterministic, and
- we don't have priority inversions anymore(!)

In the following I would kindly like to answer on some of the recent
postings on this objective. Again, please don't hesitate to tell me,
that I'm wrong.

>Jan Kiszka wrote:
>Note that we do _not_ play with the receiver priorities, we rather
>prefer a stable _static_ system configuration. That's better for hard
>RT, and prio-inheriting MPI generally doesn't help about worst-case
>latencies anyway (given a non-broken static prio design).

The worst-case latencies should be the same in both cases, (i) and (ii).
If a middle-priority task receives a message from a low-priority task
and gets immediately after its message reception interrupted by a
high-priority task, the receiver inherits the high priority, but first
it has to work on the low-priority message. Hence, the maximum
predictable delay is the execution time for the section between
'rt_task_receive' and 'rt_task_reply' of the receiver task while working
for the low priority task. The result should be the same for (i) and
(ii).

>Herman Bruyninckx wrote:
>One simple answer: if your distributed system relies on priority
inversion
>"solutions" and "real" synchronous message passing the way you
describe,
>it's a bad design!

That's exactly, what I want to do - synchronous message passing in a
distributed environment. When doing distributed communication, the
scheduler should be involved at each communication partner. If a
low-priority client on node A sends a message to a server task on node
B, the scheduler of node B should know the priority of the client on
node A, such that the message can be assigned correctly to the
corresponding receiver queue, and that therewith the receiver can be
scheduled correctly. I think, this is the same discussion as above: if
the developer knows the entire system and assigns all priorities to
_all_ tasks on _all_ nodes correctly, the system is real-time capable.
But with an increasing number of nodes and tasks the risk of priority
inversions increases immensely. And, what is more important for me: the
system is _inflexible_. When adding new tasks, you always have to care
for a non-broken static priority design of the _entire_ system.

>Herman Bruyninckx wrote:
>And don't expect your RTOS to solve that bad design by adding more and
more
>"features", especially "priority inversion" features... Priority
inversion
>efficiency and determinism simply don't scale with increased
distribution.

This ties in with the former paragraph. It should be the task of a
distributed real-time system, that (a) the highest-priority task on a
node gets scheduled (without priority inversion) and (b) that a message
of a task with a specified priority is handled with the same priority on
its remote node (the communication medium has to be real-time capable
too - of course). If this is given, one can always calculate the
worst-case execution time of the highest-priority thread. And if the
behavior of the highest priority task is known, one can calculate the
worst-case time for the task with the second-highest priority etc. As
result, we obtain a deterministic system.
 
>Herman Bruyninckx wrote:
>As soon as you want to use message passing in a distributed
environment,
>design your system such that it is _robust_ against priority
inversions. if
>it is not, your system will not survive future extensions, ports to
newer
>hardware etc.

I totally agree! That's my major reason for writing this posting :-)

>Herman Bruyninckx wrote:
>What you want to achieve (I think) with "real" synchronous message
passing
>is that the receiver handles a message as soon as the sender has sent
it,
>right? Well, if your specification involves _really_ this form of
coupling
>between sender and receiver, the _only_ good solution is to serialize
them
>both in the same thread...

I hope, I could describe my idea of "real" synchronous message passing
above. I want the receiver to work on the next message in the receive
queue, while having the priority of the highest priority among all
sender priorities. This can be right after the sending (but not
necessarily). Serializing both in the same thread would be a quite
inflexible design, I think. The real-time capable distribution of
services would become almost impossible this way.

>Herman Bruyninckx wrote:
> Taking this discussion a bit further, this
>synchronous message passing issue is key to the longlasting discussion
>between micro-kerels and monolithic kernels: the former can be more
>_robust_ in a distributed way but in practice don't achieve the
>_efficiency_ of the monolithic kernel.

That's correct. But I think the way synchronous message passing works is
an issue of the kernel - in both cases, monolithic and micro. And the
principles should be the same in both cases. But, of course, I don't
want to start a discussion about this (quite philosophical) question of
operating system architectures here :-) 

------------------
Summary

I suggested a slight change the inheritance of priorities during
synchronous message passing operations that prevents from priority
inversion problems during such communication operations. 

Besides an ongoing discussion, I hope that this subject will end like
this:

1. The approach above is correct and leads to an improvement.

or

2. I am wrong in my opinion.

Before I close, I would like to acknowledge the work of all Xenomai
developers. I don't want to criticize, but to encourage further
developments in this important open source field. And I am really
grateful for this interesting discussion.


Best regards from Braunschweig again,
Torsten

 
[1] Sha, Rajkumar, and Lehoczky. "Priority Inheritance Protocols: An
Approach to Real-Time Synchronization", IEEE Transactions on Computers,
Vol. 39, No. 9, 1990 

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 15330 bytes --]

Torsten Kröger wrote:
>> One simple answer: if your distributed system relies on priority
> inversion
>> "solutions" and "real" synchronous message passing the way you
> describe,
>> it's a bad design!
>>
>> And don't expect your RTOS to solve that bad design by adding more and
> more
>> "features", especially "priority inversion" features... Priority
> inversion
>> efficiency and determinism simply don't scale with increased
> distribution.
>> As soon as you want to use message passing in a distributed
> environment,
>> design your system such that it is _robust_ against priority
> inversions. if
>> it is not, your system will not survive future extensions, ports to
> newer
>> hardware etc.
>>
>> What you want to achieve (I think) with "real" synchronous message
> passing
>> is that the receiver handles a message as soon as the sender has sent
> it,
>> right? Well, if your specification involves _really_ this form of
> coupling
>> between sender and receiver, the _only_ good solution is to serialize
> them
>> both in the same thread... Taking this discussion a bit further, this
>> synchronous message passing issue is key to the longlasting discussion
>> between micro-kerels and monolithic kernels: the former can be more
>> _robust_ in a distributed way but in practice don't achieve the
>> _efficiency_ of the monolithic kernel.
> 
> I think we have different opinions on this :-)
> 
> Thanks to Herman, Jan, Philippe, and Gilles for their recent answers. I
> know that this posting is quite long, but I hope you can find time and
> interest to read it.
> 
> I'm not suggesting to add more and more features, I just think that
> there might be the possibility of an important improvement in the
> Xenomai send/receive/reply-messaging principle. May be I'm wrong, I have
> never designed an operating system, I am no expert in this field but
> from the user's point of view I would like to try to explain it like
> this:
> 
> It’s the task of the scheduler that the task with the highest priority
> gets scheduled as soon as the task needs the CPU. If this is not
> possible, because one or more other tasks with lower priorities are
> working in critical sections, which are also supposed to be used by the
> highest-priority task, the priority inheritance protocol rules [1]. But
> when looking at synchronous message passing, we have a different
> situation. We don’t have critical sections here. A receiver (server)
> works for a sender (client) from the reception of a message
> ('rt_task_receive') on until it calls 'rt_task_reply', i.e. the section
> from 'rt_task_receive' to 'rt_task_reply' is not the same as a section
> protected by a mutex or a semaphore. Everything a receiver does within
> this section, is done on behalf of the client and should be done with
> the priority of the client except there are other higher-priority
> clients waiting for the receiver.
> 
> In the following I would like to explain, (i) the way it is implemented
> right now and (ii) the way I would expect synchronous message passing to
> work. Again, I don't want to 'play' with priorities or to add more and
> more features, I would just like to make a (perhaps important)
> suggestion or to understand, why my opinion on this is wrong. 
> 
> Suppose T1, T2, T3, T4, and T5 are five tasks in ascending order of
> priority. T3 is 'receive' blocked ('rt_task_receive').
> 
> ------------
> (i)
> "A receiving task only inherits the priority a sender, if its _current
> priority_ is lower than the one of the sender. This inheritance rules
> until 'rt_task_reply' has been called by the receiver."
> 
> Example 1:
> If task T3 is 'receive' blocked, and T4 'sends' a message to T3, the
> priority of T4 will be assigned to T3 until T3 calls 'rt_task_reply'. If
> T5 should also send a message to T3, while T3 is still between
> 'rt_task_receive' and 'rt_task_reply' (for the message from T4), the
> message of T5 will be queued and the priority of T3 will be raised to
> the one of T5. After T3 has called 'rt_task_reply' for the message of
> T4, it remains at the priority of T5, receives the message from T5,
> works on it, replies it, and then its priority is set back to its basic
> one. We don't have priority inversion here.
> 
> Example 2:
> Another situation would be that T1 sends a message to T3, which would
> then remain at its basic priority, even if T2 changes its state to ready
> while T3 is processing the message for T1. As result, T2 would not be
> scheduled, and we have priority inversion here. Exactly this priority
> inversion problem can be avoided.
> 
> ------------
> (ii)
> "A receiving task inherits the highest priority of all tasks that have
> sent a message to it. This inheritance rules until 'rt_task_reply' has
> been called by the receiver."
> 
> Example 1:
> Same behavior as above.
> 
> Example 2:
> If T1 sends a message to T3, T3 inherits the priority of T1 until T3
> calls 'rt_task_reply'. If T2 gets ready while T3 works on the message
> from T1, T2 would be scheduled, and we don't have the priority inversion
> problem anymore. If T2 would then get pre-empted by T5 for example, and
> if T5 should also send a message to T3, T3's priority would raise to the
> one of T5 of course - i.e. the same way as in (i) and the
> highest-priority task is always privileged.
> ------------
> 
> I do understand that when we work with static priorities, the developer
> is able to prevent this situation by assigned appropriate priorities to
> all tasks. But therefore, he needs to know the entire system and the
> dependencies between _all_ tasks. In small systems, this is indeed
> possible, of course, but in large systems with many tasks, the
> probability of miss-configuring the system increases rapidly, and in
> very big systems real-time capability cannot be guaranteed when using
> synchronous message passing. This problem becomes even bigger, when
> looking at distributed systems, of course.

Well, relying on OS services to solve design issues of larger system is
/fairly/ risky. All this dynamic scheduling, prio-inheriting, etc.
doesn't come for free. So you can't simply rely on something like "hey,
it worked for 10 threads, now I'm adding 10 more, so it can be at worst
half as fast". You _do_ have to reconsider your whole (RT-)system unless
you want to live with increasing uncertainties (soft RT...). And if the
system is getting too large, use tools. OK, granted, Xenomai yet doesn't
provide such tools nor at least models to feed 3rd-party software. Yet
another nice area to work on. :)

> 
> The only disadvantage I see is that we always have to perform a
> rescheduling in (ii), when a task receives a message sent from another
> task with another priority. In (i) we only perform a rescheduling when a
> higher-priority task sends a message to a receiver. As result the
> efficiency _slightly_ decreases when low priority tasks communicate with
> high-priority tasks via synchronous message passing, but 
> 
> - the system is still deterministic, and
> - we don't have priority inversions anymore(!)
> 
> In the following I would kindly like to answer on some of the recent
> postings on this objective. Again, please don't hesitate to tell me,
> that I'm wrong.
> 
>> Jan Kiszka wrote:
>> Note that we do _not_ play with the receiver priorities, we rather
>> prefer a stable _static_ system configuration. That's better for hard
>> RT, and prio-inheriting MPI generally doesn't help about worst-case
>> latencies anyway (given a non-broken static prio design).
> 
> The worst-case latencies should be the same in both cases, (i) and (ii).
> If a middle-priority task receives a message from a low-priority task
> and gets immediately after its message reception interrupted by a
> high-priority task, the receiver inherits the high priority, but first
> it has to work on the low-priority message. Hence, the maximum
> predictable delay is the execution time for the section between
> 'rt_task_receive' and 'rt_task_reply' of the receiver task while working
> for the low priority task. The result should be the same for (i) and
> (ii).

My point is that worst-case is not much different if the receiver gets
the required static priority right from the beginning. You just add the
management overhead in the dynamic case (which is noticeable if message
handling is short).


BTW, did you already asked yourself why your receiver has to handle
messages of different priority with the same thread? If there is
actually something important aside unimportant stuff to transmit from A
to B, you may as well let B provide two endpoints with two threads: one
to handle to important messages and the other the rest. Please don't
tell me too quickly, you need far too many classification levels for
this. Check it thoroughly first! Too many priorities are a good sign for
indeterministic and inefficient system design.

Note that this pattern can have a nice advantage: lower worst-case
latency. As you can now let the two threads of B synchronise on the
_real_ critical section, ie. where shared data is handled, and not where
whole messages get parsed etc., that section often gets shorter! (A
reason why microkernel-like server design doesn't scale that well.)

> 
>> Herman Bruyninckx wrote:
>> One simple answer: if your distributed system relies on priority
> inversion
>> "solutions" and "real" synchronous message passing the way you
> describe,
>> it's a bad design!
> 
> That's exactly, what I want to do - synchronous message passing in a
> distributed environment. When doing distributed communication, the
> scheduler should be involved at each communication partner. If a
> low-priority client on node A sends a message to a server task on node
> B, the scheduler of node B should know the priority of the client on
> node A, such that the message can be assigned correctly to the
> corresponding receiver queue, and that therewith the receiver can be
> scheduled correctly. I think, this is the same discussion as above: if
> the developer knows the entire system and assigns all priorities to
> _all_ tasks on _all_ nodes correctly, the system is real-time capable.
> But with an increasing number of nodes and tasks the risk of priority
> inversions increases immensely. And, what is more important for me: the
> system is _inflexible_. When adding new tasks, you always have to care
> for a non-broken static priority design of the _entire_ system.
> 
>> Herman Bruyninckx wrote:
>> And don't expect your RTOS to solve that bad design by adding more and
> more
>> "features", especially "priority inversion" features... Priority
> inversion
>> efficiency and determinism simply don't scale with increased
> distribution.
> 
> This ties in with the former paragraph. It should be the task of a
> distributed real-time system, that (a) the highest-priority task on a
> node gets scheduled (without priority inversion) and (b) that a message
> of a task with a specified priority is handled with the same priority on
> its remote node (the communication medium has to be real-time capable
> too - of course). If this is given, one can always calculate the
> worst-case execution time of the highest-priority thread. And if the
> behavior of the highest priority task is known, one can calculate the
> worst-case time for the task with the second-highest priority etc. As
> result, we obtain a deterministic system.
>  
>> Herman Bruyninckx wrote:
>> As soon as you want to use message passing in a distributed
> environment,
>> design your system such that it is _robust_ against priority
> inversions. if
>> it is not, your system will not survive future extensions, ports to
> newer
>> hardware etc.
> 
> I totally agree! That's my major reason for writing this posting :-)
> 
>> Herman Bruyninckx wrote:
>> What you want to achieve (I think) with "real" synchronous message
> passing
>> is that the receiver handles a message as soon as the sender has sent
> it,
>> right? Well, if your specification involves _really_ this form of
> coupling
>> between sender and receiver, the _only_ good solution is to serialize
> them
>> both in the same thread...
> 
> I hope, I could describe my idea of "real" synchronous message passing
> above. I want the receiver to work on the next message in the receive
> queue, while having the priority of the highest priority among all
> sender priorities. This can be right after the sending (but not
> necessarily). Serializing both in the same thread would be a quite
> inflexible design, I think. The real-time capable distribution of
> services would become almost impossible this way.
> 
>> Herman Bruyninckx wrote:
>> Taking this discussion a bit further, this
>> synchronous message passing issue is key to the longlasting discussion
>> between micro-kerels and monolithic kernels: the former can be more
>> _robust_ in a distributed way but in practice don't achieve the
>> _efficiency_ of the monolithic kernel.
> 
> That's correct. But I think the way synchronous message passing works is
> an issue of the kernel - in both cases, monolithic and micro. And the
> principles should be the same in both cases. But, of course, I don't
> want to start a discussion about this (quite philosophical) question of
> operating system architectures here :-) 
> 
> ------------------
> Summary
> 
> I suggested a slight change the inheritance of priorities during
> synchronous message passing operations that prevents from priority
> inversion problems during such communication operations. 
> 
> Besides an ongoing discussion, I hope that this subject will end like
> this:
> 
> 1. The approach above is correct and leads to an improvement.
> 
> or
> 
> 2. I am wrong in my opinion.

Though I would personally avoid designing systems like you want to, I
would also refrain from calling your opinion wrong. There can be valid
scenarios for many patterns (e.g. if existing software dictates the
design :-/). So let's get back to the Xenomai aspect of this thread:

> 
> Before I close, I would like to acknowledge the work of all Xenomai
> developers. I don't want to criticize, but to encourage further
> developments in this important open source field. And I am really
> grateful for this interesting discussion.

If you are seriously interested in prio-inheritance for the native
message passing API, the best you can do is to work actively on a patch
proposal. This would

 - demonstrate how unintrusive this addition could be (preferably, PI
   will be optional and use existing low-level services), while being
   so useful for certain scenarios

 - accelerate the testing cycle (_you_ have the scenario at hand)

 - raise the chances that Xenomai gains this feature soon (core
   developers are generally busy with many things)

Posting patches early will allow you gain concrete feedback on the
design. And we will not sit there and watch you pulling hairs while
you're stuck. But hacking some Xenomai skin is also no black magic,
given the well defined nucleus API. Give it a try!

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Torsten Kröger]

Hello Jan,

thanks for your immediate answer on my posting. The reason for this
posting is that I spent some more time on thinking about RTOS
architectures, and I got some deeper insights, which I would like to
communicate with the aim that it will be a help for further advances of
Xenomai.

My conclusion is still that another kind of priority inheritance for the
synchronous message passing principle of Xenomai could be very relevant
for some application designs, but I totally agree, the loss of
efficiency must be kept as low as possible - if possible the loss should
be zero, of course.

I know that this posting is quite long again, and I don't expect anybody
to answer extensively. If it is too much, take it as inspiriting
discussion of a "freaking RTOS-user"... ;-) ;-) But again, please tell,
if some of the discussion statements are wrong.

I found a paper, which discusses the subjects of our recent mailings:

U. Steinberg, J. Wolter, and H. Haertig. Fast component interaction for
real-time systems. Proceedings of the 17th Euromicro Conference on
Real-Time Systems, pages: 89-97, 2005.

The paper can be downloaded at

http://os.inf.tu-dresden.de/papers_ps/steinberg_ecrts2005.pdf.

The authors of the paper propose a mechanism for the fast interaction of
interdependent components in real-time systems. Although it treats
L4-micro-kernel architectures, the basic subject of discussion is the
same and it can be transferred to Xenomai. Here a short segment of the
work:

>From "Fast component interaction for real-time systems":
>
>"[...] Most real-time kernels that focus on minimality use a simple
fixed->priority scheduling algorithm, which on one hand does not provide
temporal >isolation and on the other hand is prone to priority-inversion
problems >when component interaction creates a dependency between two
schedulable >entities. In this paper we introduce a reservation-based
approach to >provide temporal isolation. We discuss the problems related
to component >interaction, such as priority inversion and correct
accounting of consumed >time, and demonstrate how our mechanism can be
used to implement priority >inheritance and stack-based priority
ceiling. [...] the basic message->passing mechanisms must be designed
such that well-known methods to avoid >priority inversion, namely
priority inheritance and stackbased priority >ceiling, are supported
without sacrificing performance. [...]"
>

As far as I understood the Xenomai kernel, I conclude that the last part
of this citation has not been realized in the Xenomai kernel. Whether
the approach can be transferred to Xenomai is not clear to me; Again, I
don't understand myself as an operating system developer/specialist. At
first glance I'd say the suggested principle could be embedded in the
Xenomai kernel, but after reading the paper more precisely I understood
that a possible implementation would be anything but easy work for me.
If this should really become interesting for the Xenomai project, I
guess that someone with _big_ kernel experiences has to implement a
solution for this. The approach of the paper is to use a donation scheme
in combination with message passing; two different kinds of context are
necessary, which then finally results in efficient communication without
priority inversion and miss-accounting.

>Jan Kiszka wrote:
>My point is that worst-case is not much different if the receiver gets
>the required static priority right from the beginning. You just add the
>management overhead in the dynamic case (which is noticeable if message
>handling is short).
>
>
>BTW, did you already asked yourself why your receiver has to handle
>messages of different priority with the same thread? If there is
>actually something important aside unimportant stuff to transmit from A
>to B, you may as well let B provide two endpoints with two threads: one
>to handle to important messages and the other the rest. Please don't
>tell me too quickly, you need far too many classification levels for
>this. Check it thoroughly first! Too many priorities are a good sign
for
>indeterministic and inefficient system design.
>
>Note that this pattern can have a nice advantage: lower worst-case
>latency. As you can now let the two threads of B synchronise on the
>_real_ critical section, ie. where shared data is handled, and not
where
>whole messages get parsed etc., that section often gets shorter! (A
>reason why microkernel-like server design doesn't scale that well.)

You are absolutely right, and the issue of worst-case latency has to be
observed by the system developer in all use cases. I think this
advantage of low worst-case latency is _extremely important_, but there
are also cases, in which this could lead to disadvantages (e.g.
_inflexibility_). A good latency is not the only attribute of a good
system. I think a system development engineer should be able to decide
freely, which system architecture and which overall system attributes he
aspires for his application; it should not be dictated by the system but
by the application. And therefore the (efficient) avoidance of priority
inversions when doing synchronous message passing seems to be _very
relevant_. Of course, I agree that if this problem cannot be solved
really efficiently, it will be much better to leave the
send/receive/reply-principle as it is in order keep the latencies low.

In the following paragraphs I would like to point out these statements.

A simple sample situation, where it is indispensable that a high
priority task receives messages from other high-priority tasks as well
as from other low-priority ones, could be the following one:

Suppose a digital I/O card, of which some ports are important and
require hard real-time capabilities, while soft-real-time behavior is
sufficient for some other ports. If a task is the only one in the entire
system that has access to the hardware registers via the RTDM (device
flag 'RTDM_EXCLUSIVE' set), and if the hardware registers contain
important and unimportant I/O bits, the task, which has access to the
registers, needs to fulfill real-time conditions, but it must
furthermore enable low-priority tasks to access the unimportant bits.

To solve this, many design possibilities arise. I think it really
depends on the individual application and it cannot be generalized,
since low latencies are always _really desirable_, but not for any
price. I'm not speaking about soft real-time here - worst-case execution
times have to be predictable in any case! To clarify this I present a
further discussion on example for transferring information from a
high-priority task H to a low-priority one L or vice versa (as in your
example above). Three basic options arise:
 
-------------
1. The information is located in a shared-memory area of H and L. This
area is protected by a mutex for example, such that the PIP would rule.
When calculating the worst-case latency for H, we can calculate the
maximum time, L needs within the critical section (L would inherit the
priority of H regarding the PIP). During L is in the critical section it
has several basic possibilities to get the data, e.g.:

a. It can send the data directly to another low-priority task by using
pipes, message queues, or synchronous message passing.
 
b. It can copy data into another area of shared memory (which might be
shared with another other low-priority task).

c. It can copy the data into its own address space.

Each of these three exemplary possibilities has its advantages and
disadvantages. Option c would definitely deliver the lowest worst-case
execution time (and therewith the lowest worst-case latency for H), but
in each case we are able to determine the maximum execution times until
L releases the mutex for the memory area shared with H. Depending on our
preferences and architectural goals, we can not say whether one of these
alternatives is worse than another one. Sure, option (a) would probably
have the greatest worst-case latency, but this must _not necessarily_
mean to be a bad design. 

2. The high-priority task sends the information cyclically to the
low-priority task (á la publish/subscribe). This way the information can
be led to many clients very efficiently.

3. L requests data from H (e.g. via synchronous message passing). If we
only consider the common case of data exchange, the worst-case latency
would not be higher than in (1a). And regarding _transparency_ and
_flexibility_ this might the favorite solution.
-------------

Depending on individual requirements, each alternative should be
possible. Regarding my understanding for the implementation of Xenomai,
the realization of option (3) is currently not possible when real-time
conditions have to be upheld.

Again, I don't want to criticize any part of the Xenomai
implementations. Application programmers just have to be aware of using
synchronous message passing, because its behavior - in particular its
priority inversion behavior - is RTOS-implementation dependent. For me
this was not self-evident before.

I think it should be a general aim of any RTOS with
send/receive/reply-messaging API, that this behavior becomes
generalized, because this matter is an unforeseeable source of errors.
Besides, portability would be further simplified. In my concrete case it
means that I have to port an application to Xenomai, which uses the
posix skin and consists of several tasks that strongly use synchronous
message passing for intercommunication. This brings me to the conclusion
that I cannot implement an _efficient_ solution as long as the priority
inheritance behavior during synchronous message passing operations of
any skin remains as it is.

>Jan Kiszka wrote:
>If you are seriously interested in prio-inheritance for the native
>message passing API, the best you can do is to work actively on a patch
>proposal. This would
>
> - demonstrate how unintrusive this addition could be (preferably, PI
>   will be optional and use existing low-level services), while being
>   so useful for certain scenarios
>
> - accelerate the testing cycle (_you_ have the scenario at hand)
>
> - raise the chances that Xenomai gains this feature soon (core
>   developers are generally busy with many things)
>
>Posting patches early will allow you gain concrete feedback on the
>design. And we will not sit there and watch you pulling hairs while
>you're stuck. But hacking some Xenomai skin is also no black magic,
>given the well defined nucleus API. Give it a try!

I am seriously interested in priority inheritance for the message
passing API, but I don't consider myself as an expert in this field and
nor as an operating system developer. My employer/my client does not
give me time for such kind of system engineering, hence I will remain as
a user - all I can do is to tell about my desires and experiences.

Ok, now I'm coming to the end. I hope this posting was a bit interesting
for any reader and that someone goes for further words on this...

...any comment and further discussion is highly appreciated again! :-)


Torsten

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 1957 bytes --]

Hi Torsten,

<snippin a lot, sorry>

Torsten Kröger wrote:
>> Jan Kiszka wrote:
>> If you are seriously interested in prio-inheritance for the native
>> message passing API, the best you can do is to work actively on a patch
>> proposal. This would
>>
>> - demonstrate how unintrusive this addition could be (preferably, PI
>>   will be optional and use existing low-level services), while being
>>   so useful for certain scenarios
>>
>> - accelerate the testing cycle (_you_ have the scenario at hand)
>>
>> - raise the chances that Xenomai gains this feature soon (core
>>   developers are generally busy with many things)
>>
>> Posting patches early will allow you gain concrete feedback on the
>> design. And we will not sit there and watch you pulling hairs while
>> you're stuck. But hacking some Xenomai skin is also no black magic,
>> given the well defined nucleus API. Give it a try!
> 
> I am seriously interested in priority inheritance for the message
> passing API, but I don't consider myself as an expert in this field and
> nor as an operating system developer. My employer/my client does not
> give me time for such kind of system engineering, hence I will remain as
> a user - all I can do is to tell about my desires and experiences.

As I said, it doesn't take experts here, just someone to start and
collect the pieces (which might include asking for expert knowledge here
and there).

And someone being able to write such long and detailed essays - for me
even too long to read completely yet - should as well be able to play a
bit with code. Or motivate some talented student of yours (I know they
can be rare). ;)

> 
> Ok, now I'm coming to the end. I hope this posting was a bit interesting
> for any reader and that someone goes for further words on this...
> 
> ...any comment and further discussion is highly appreciated again! :-)
> 

Better let some code speak now...

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Torsten Kröger]

Jan Kiszka wrote:
>
>As I said, it doesn't take experts here, just someone to start and
>collect the pieces (which might include asking for expert knowledge
here
>and there).
>
>And someone being able to write such long and detailed essays - for me
>even too long to read completely yet - should as well be able to play a
>bit with code. Or motivate some talented student of yours (I know they
>can be rare). ;)
>

The reason for my long postings is that I just wanted the developers to
understand my concerns - and to see that it is a serious problem of the
Xenomai RTOS.

I cannot imagine that adding new task context data structures and
changing algorithms for CPU time counting (important for RR scheduling)
is an easy or small thing.


Best,
Torsten

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 1182 bytes --]

Torsten Kröger wrote:
> Jan Kiszka wrote:
>> As I said, it doesn't take experts here, just someone to start and
>> collect the pieces (which might include asking for expert knowledge
> here
>> and there).
>>
>> And someone being able to write such long and detailed essays - for me
>> even too long to read completely yet - should as well be able to play a
>> bit with code. Or motivate some talented student of yours (I know they
>> can be rare). ;)
>>
> 
> The reason for my long postings is that I just wanted the developers to
> understand my concerns - and to see that it is a serious problem of the
> Xenomai RTOS.

As pointed out: How "serious" this is heavily depends on the application
design.

> I cannot imagine that adding new task context data structures and
> changing algorithms for CPU time counting (important for RR scheduling)
> is an easy or small thing.

Well, you picked an even more complicated approach to solve your
problem. So far we were only talking about PI for message passing based
on existing infrastructure, using clear semantics. Let's make smaller
steps and see how far it takes us to solve your requirements.

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters ofthreads in other processes

[Philippe Gerum]

On Thu, 2007-08-09 at 15:06 +0200, Torsten Kröger wrote:
> >> this is my first email to this list, and I would like to start with a
> >> question. I use the posix skin of Xenomai 2.3.1, and I have several
> >> processes running, each consisting of several threads. Is there a
> >> possibility for a thread A1 running in process A to change the
> >> scheduling parameters, in particular the priority, of a thread B1
> >> running in process B?
> >>
> >> Regarding the posix specification I cannot find this functionality
> there
> >> and so I guess there is no way doing it with
> "pthread_setschedparam()".
> >> But is there another possibility?
> >
> >No, the only way you could do that is by using an IPC to pass the
> >request from a process to another. You could use message queues for
> >that.
> >
> 
> Thanks for this immediate answer. I just read some parts of the posix
> specification, and if I'm not mistaking posix message queues do not
> inherit thread priorities. They only sort messages in (message-)priority
> order. I guess you mean synchronous message passing provided by
> rt_task_send(), rt_task_receive(), and rt_task_reply() in the native
> API. This would of course be an alternative. But therefore I would have
> to port many code to the native API. Would then be possible to let one
> RT_TASK change the prioriy of any other RT_TASK by simply calling
> rt_task_set_priority()? 
> 
> Regarding send/receive/reply messaging with the native API, I am not
> sure if I detected a mistake in the implementation (file
> ksrc/skins/native/task.c). When a sender RT_TASK sends a message to a
> receiver RT_TASK, then the priority is only inherited, if the receiver's
> priority is lower than the one of the sender. For my understanding, the
> priority should be inherited in any case.
> 
> >From the reception of a message till the call of rt_task_reply() the
> receiver RT_TASK works for the sender and should get its priority.
> Otherwise we would have a priority inversion at this point, because any
> RT_TASK with a priority between the sender and receiver priority would
> now be blocked by the receiver (which works for the lower prioritized
> sender at its old priority).
> 

You are supposed to pick the right base priority for the server in the
first place so this case never arises. Any other behaviour than the
strict priority inheritance protocol would be broken by design because a
server might sleep while processing a request and requests might pile up
(try with two senders having different priorities, highest priority
first, and server entering a blocked state in the middle of its
processing for the first request).

> 
> Many many thanks in advance for your help,
> Torsten
> 
> 
> _______________________________________________
> Xenomai-help mailing list
> Xenomai-help@domain.hid
> https://mail.gna.org/listinfo/xenomai-help
-- 
Philippe.

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Torsten Kröger]

>>
>> Regarding send/receive/reply messaging with the native API, I am not
>> sure if I detected a mistake in the implementation (file
>> ksrc/skins/native/task.c). When a sender RT_TASK sends a message to a
>> receiver RT_TASK, then the priority is only inherited, if the
receiver's
>> priority is lower than the one of the sender. For my understanding,
the
>> priority should be inherited in any case.
>>
>> >From the reception of a message till the call of rt_task_reply() the
>> receiver RT_TASK works for the sender and should get its priority.
>> Otherwise we would have a priority inversion at this point, because
any
>> RT_TASK with a priority between the sender and receiver priority
would
>> now be blocked by the receiver (which works for the lower prioritized
>> sender at its old priority).
>>
>
>You are supposed to pick the right base priority for the server in the
>first place so this case never arises. Any other behaviour than the
>strict priority inheritance protocol would be broken by design because
a
>server might sleep while processing a request and requests might pile
up

I totally agree at first glance. When regarding the concepts based on
the work of Sha, Rajkumar, and Lehoczky ("Priority Inheritance
Protocols: An Approach to Real-Time Synchronization", IEEE Transactions
on Computers, Vol. 39, No. 9, 1990) you are generally right (I guess,
because I'm no expert). But in the particular case of "Synchronous
Message Passing" (send/receive/reply-messaging), I think the "QNX-way"
would make much more sense regarding real-time capabilities: Receivers
(servers) always inherit the priority of the senders (client), no matter
if the receiver's priority is lower or higher than the sender one's. A
description can be found here:

http://www.qnx.com/developers/docs/momentics621_docs/neutrino/sys_arch/k
ernel.html#NTOIPC

The major advantage is that priority inversion problems are completely
avoided here. As also described in the text above, are two rules, which
have to be observed:

1. You are not allowed to have two threads sending each other.
2. Threads must be arranged in a hierarchy, where send calls only go up.

When using the Xenomai native send/receive/reply calls, the system is
not real-time capable in general. The user always has to care for the
whole system, which really gets sophisticated in systems with a huge
number of threads/processes.

>(try with two senders having different priorities, highest priority
>first, and server entering a blocked state in the middle of its
>processing for the first request).

Regarding this example, I cannot see the problem. We won't have a
deadlock in both cases. Xenomai send/receive/reply messaging would work,
but here priority inversion might happen, if there is any other with a
priority between the sender with the low priority and the basis priority
of the receiver. 'Common' Synchronous Message Passing would work exactly
the same way. If the receiver thread blocks during the processing of the
first message from the high-priority sender thread, the second
low-priority thread might be scheduled and could send the second
message. But in this second case, the receiver remains in the high
priority until it calls the reply-function. When it then receives the
second message, the receiver inherits the low priority of the second
sender thread. But in this case, priority inversion problems cannot
arise.

Please let me know, if I'm mistaking. I'm not really a specialist in
this field. All I have experienced is that the basic flow chart of
send/receive/reply-messaging looks really simple - but its robust
real-time capable implementation is quite sophisticated.

Actually my aim is to develop 'common' real-time capable Synchronous
Message Passing for the posix skin of Xenomai, but right know my
conclusion is the following: its realization is not possible, except
_all_ threads are part of one and only one process. But this seems
really not to be practical and hence I'm looking for other solutions.
 
Any comments on this are really appreciated again.


Best regards from Braunschweig,
Torsten 

[Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Torsten Kröger]

Hello everybody,

this is my first email to this list, and I would like to start with a
question. I use the posix skin of Xenomai 2.3.1, and I have several
processes running, each consisting of several threads. Is there a
possibility for a thread A1 running in process A to change the
scheduling parameters, in particular the priority, of a thread B1
running in process B?

Regarding the posix specification I cannot find this functionality there
and so I guess there is no way doing it with "pthread_setschedparam()".
But is there another possibility?  

Any kind of feedback will be appreciated.


Best regards from Braunschweig,
Torsten

Re: [Xenomai-help] POSIX Skin: Changing scheduling parameters of threads in other processes

[Gilles Chanteperdrix]

Torsten Kröger wrote:
 > Hello everybody,
 > 
 > this is my first email to this list, and I would like to start with a
 > question. I use the posix skin of Xenomai 2.3.1, and I have several
 > processes running, each consisting of several threads. Is there a
 > possibility for a thread A1 running in process A to change the
 > scheduling parameters, in particular the priority, of a thread B1
 > running in process B?
 > 
 > Regarding the posix specification I cannot find this functionality there
 > and so I guess there is no way doing it with "pthread_setschedparam()".
 > But is there another possibility?  

No, the only way you could do that is by using an IPC to pass the
request from a process to another. You could use message queues for
that.

-- 


					    Gilles Chanteperdrix.