Influence of application priority on IPC

[Norman Feske]

Hi Sergey,

> I have a question about influence of application priority on IPC 
> messaging mechanism.

your concern of the interaction of priorities and IPC are spot-on. This
is a topic where the different microkernels differ significantly.
Generally, static priorities should be used with caution. You need to be
aware that a higher-priority thread can starve any lower-priority
activity in the system by a busy loop. The potential problems become
apparent when having more than two parties in the system. In such
scenarios, priority inversion can occur.

> Let's say I have two applications (client and server) which use IPC for 
> communication with each other. In run script I set the priority of 
> client to default value (no priority specified) and the priority of 
> server to -1 (value of prio_levels is equal to 2).

Assigning a lower priority to the server than to the client is a
classical priority inversion problem. The client has a high priority and
wants the server to do some work for him. But because the server has a
low priority, any other thread that has a higher priority than the
server (but possibly a lower priority than the client) can infinitely
delay the execution of the server.

There are two ways to deals with such problems, namely priority
inheritance and priority ceiling.

Priority inheritance means that the server will inherit the (higher)
priority of the client while doing work for the client. So the priority
is not attached to a thread but rather to a specific work topic. Anyone
that contributes to the work gets the high priority regardless of which
processes the execution flows through. As far as I know, NOVA is the
only kernel of the Genode base platforms that properly implements
priority inheritance.

Priority ceiling means that there exists a strict order of priorities
that is consistent with the client-server relationships of processes. A
server always needs to have a priority at least as high as its clients.
Because of the invariant that the server operates at a higher priority
than the client, the service request will make progress in at least any
situation where the client would make progress (because it is scheduled
at least as likely as the client who is currently blocked). The
disadvantage of priority ceiling is that a client can artificially boost
its priority (and cause system load) by using servers.

Priority ceiling can be implemented on L4/Fiasco, OKL4, Fiasco.OC, and
L4ka::Pistachio.

> The question is quite simple: is there any determined dependency between 
> changing the priority of applications and possible collisions of IPC 
> calls? For example, what if both priorities are set to default values or 
> to -1? And if there is a suspect of lost IPC messages, then how this 
> hypothesis can be checked?

Normally, one would expect that priority inversion problems are easy to
detect because some part of the system just freezes. However, on most
kernels that lack priority inheritance (actually all kernels but NOVA),
the bad interaction between IPC and priorities are hard to detect
because of an optimization called time-slice donation. On those kernels,
the client that calls the server lends its remaining time slice to the
server to boost the processing of its IPC request. This way, the flow of
control will typically go from the client through the server and then
back to the client while the client's time slice is active.
Unfortunately, this flow of control ends as soon as the time slice is
over. When a timer interrupt occurs while the request is at the server,
and the kernel schedules an unrelated thread that has a priority higher
then the server, the server will starve. As a consequence, this will
possibly end up in a deadlock situation that is extremely hard to reproduce.

To avoid these situations, the rule of thumb is to always assign an
equal or higher priority to the server than to the client.

Could you elaborate a bit more on the problem where you are using
applying priorities to? Is it possible to turn the scenario into a
composition where the server is always prioritized higher than its clients?

Best regards
Norman

-- 
Dr.-Ing. Norman Feske
Genode Labs

http://www.genode-labs.com · http://genode.org

Genode Labs GmbH · Amtsgericht Dresden · HRB 28424 · Sitz Dresden
Geschäftsführer: Dr.-Ing. Norman Feske, Christian Helmuth