[Xenomai-help] Scheduler: Strange priority handling with multiple tasks waiting for one semaphore

[Xenomai-help] Scheduler: Strange priority handling with multiple tasks waiting for one semaphore

[M. Koehrer]

[-- Attachment #1.1: Type: text/plain, Size: 1872 bytes --]

Hi everybody,

I see strange effect that I do not understand.
What happens when multiple tasks (with different priority) are waiting for a single semaphore?
Assume the following situation:
Task H (High prio) and Task L (low prio) are waiting both for the same semaphore.
A third task does the rt_sem_v() to grant access.
Now H passes its rt_sem_p() and runs. 
A few statements later H calls rt_sem_v() to grant access to the semaphore protected part.
What happens now? As H is high priority there should be no reschedule, i.e. H continues to run.
What happens now if H wants to enter again via rt_sem_p() (on the same semaphore)?
I expect to allow H again the access as it has a higher priority than L.
However, a small demo application for this use case shows me that this not the case.
The heart of my demo application is the following task code fragment:

void mytask(void *cookie)
{
    int id = (int)cookie;
    int cnt = 0;

    while (!end)
    {
        rt_sem_p(&sem, TM_INFINITE);
        (....)
        rt_sem_v(&sem);
    }

    printf("task %i: cnt %i\n", id, cnt);
}
There are two tasks with different priorities that execute this code.
I expected to have only the higher priority task to be run, however they run alternately.
What is happening here? It looks as if the Xenomai scheduler does not handle the priority 
correctly in this case.
I have enclosed the C code of this application to this mail.

Thanks for any feedback on this.

Regards

Mathias



-- 
Mathias Koehrer
mathias_koehrer@domain.hid


Viel oder wenig? Schnell oder langsam? Unbegrenzt surfen + telefonieren
ohne Zeit- und Volumenbegrenzung? DAS TOP ANGEBOT JETZT bei Arcor: günstig
und schnell mit DSL - das All-Inclusive-Paket für clevere Doppel-Sparer,
nur  39,85 €  inkl. DSL- und ISDN-Grundgebühr!
http://www.arcor.de/rd/emf-dsl-2

[-- Attachment #2: sematest.c.gz --]
[-- Type: application/octetstream, Size: 664 bytes --]

Re: [Xenomai-help] Scheduler: Strange priority handling with multiple tasks waiting for one semaphore

[Dmitry Adamushko]

Hi,

>
> I see strange effect that I do not understand.
> What happens when multiple tasks (with different priority) are waiting for a single semaphore?
> Assume the following situation:
> Task H (High prio) and Task L (low prio) are waiting both for the same semaphore.
> A third task does the rt_sem_v() to grant access.
> Now H passes its rt_sem_p() and runs.
> A few statements later H calls rt_sem_v() to grant access to the semaphore protected part.
> What happens now? As H is high priority there should be no reschedule, i.e. H continues to run.
> What happens now if H wants to enter again via rt_sem_p() (on the same semaphore)?
> I expect to allow H again the access as it has a higher priority than L.
> However, a small demo application for this use case shows me that this not the case.

That's how our semaphores work indeed. It has nothing to do with the scheduler.

First of all, note that a semaphore doesn't support PIP (Priority
Inheritance Protocol). It would be not that straightforward to
implement as a semaphore basically has a few "owners". So we don't
track who "owns" a semaphore at the moment as we do for a mutex.
Hence, "resource stealing" is not possible.

The later works for a mutex. We always know an owner in this case and
can steal a resource in case the owner has been scheduled (1) but
doesn't get a CPU yet (2) and in the mean time (between (1) and (2)) a
high-priority task gets control and asks for a mutex (if (2) is not
met, we would do priority boosting for an owner).

rt_sem_v() just wakes up a waiter. If one is available, it doesn't
increase an internal counter (which tracks how many tasks can get a
semaphore) -> aside of this fact, we don't know who "owns" a
semaphore.

Now when a high priority task asks for it again immediately (here we
are in the situation (1)-(2) I described above), we only know it's
busy - we don't know any "owners" -> can't steal it. That's it.

Maybe you can use a mutex in your program (in case a counter of your
semaphore is 1 anyway) and lock sections are not long, time-wise?


-- 
Best regards,
Dmitry Adamushko

Re: [Xenomai-help] Scheduler: Strange priority handling with multiple tasks waiting for one semaphore

[Jan Kiszka]

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

M. Koehrer wrote:
> Hi everybody,
> 
> I see strange effect that I do not understand.
> What happens when multiple tasks (with different priority) are waiting for a single semaphore?
> Assume the following situation:
> Task H (High prio) and Task L (low prio) are waiting both for the same semaphore.
> A third task does the rt_sem_v() to grant access.
> Now H passes its rt_sem_p() and runs. 
> A few statements later H calls rt_sem_v() to grant access to the semaphore protected part.
> What happens now? As H is high priority there should be no reschedule, i.e. H continues to run.
> What happens now if H wants to enter again via rt_sem_p() (on the same semaphore)?
> I expect to allow H again the access as it has a higher priority than L.
> However, a small demo application for this use case shows me that this not the case.
> The heart of my demo application is the following task code fragment:
> 
> void mytask(void *cookie)
> {
>     int id = (int)cookie;
>     int cnt = 0;
> 
>     while (!end)
>     {
>         rt_sem_p(&sem, TM_INFINITE);
>         (....)
>         rt_sem_v(&sem);

Semaphores of the native skin do not know a 'mutex' mode (because there
are explicit mutexes), so you are most likely using the wrong tool here.

Semaphores have no owner. Once you release a semaphore, you pass the
access to the next highest waiter. And, in contrast to mutexes with
strict ownership, there is no way to get it back even if the new owner
hasn't been started yet.

>     }
> 
>     printf("task %i: cnt %i\n", id, cnt);
> }
> There are two tasks with different priorities that execute this code.
> I expected to have only the higher priority task to be run, however they run alternately.
> What is happening here? It looks as if the Xenomai scheduler does not handle the priority 
> correctly in this case.
> I have enclosed the C code of this application to this mail.
> 
> Thanks for any feedback on this.
> 
> Regards
> 
> Mathias
> 

In short: use mutexes for resource protection, then you will get the
desired behaviour!

Jan



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

Re: [Xenomai-help] Scheduler: Strange priority handling with multiple tasks waiting for one semaphore

[Philippe Gerum]

On Mon, 2007-05-14 at 10:40 +0200, M. Koehrer wrote:
> Hi everybody,
> 
> I see strange effect that I do not understand.
> What happens when multiple tasks (with different priority) are waiting for a single semaphore?
> Assume the following situation:
> Task H (High prio) and Task L (low prio) are waiting both for the same semaphore.
> A third task does the rt_sem_v() to grant access.
> Now H passes its rt_sem_p() and runs. 
> A few statements later H calls rt_sem_v() to grant access to the semaphore protected part.
> What happens now? As H is high priority there should be no reschedule, i.e. H continues to run.
> What happens now if H wants to enter again via rt_sem_p() (on the same semaphore)?
> I expect to allow H again the access as it has a higher priority than L.
> However, a small demo application for this use case shows me that this not the case.
> The heart of my demo application is the following task code fragment:
> 
> void mytask(void *cookie)
> {
>     int id = (int)cookie;
>     int cnt = 0;
> 
>     while (!end)
>     {
>         rt_sem_p(&sem, TM_INFINITE);
>         (....)
>         rt_sem_v(&sem);
>     }
> 
>     printf("task %i: cnt %i\n", id, cnt);
> }
> There are two tasks with different priorities that execute this code.
> I expected to have only the higher priority task to be run, however they run alternately.
> What is happening here? It looks as if the Xenomai scheduler does not handle the priority 
> correctly in this case.

Note: when problems of that sort arises, this is almost _never_ a
scheduler issue; a priority fixed FIFO scheduler is damned stupid piece
of code actually (ok, I know how to be really stupid too, but still, the
argument stands...). Strangenesses, if any, are usually caused by some
synchronization objects implementation that would misbehave blatantly,
so in this case, the culprit would have been the native sema4
implementation, and not the scheduler that just applies the decisions of
the latter.

> I have enclosed the C code of this application to this mail.
> 

T0: H grabs sem
T1: H releases sem, depletes it and wakes up L atomically
T2: H goes sleeping on the depleted sem
T3: L runs
T4: L releases sem, depletes it and wakes up H atomically
T5: H preempts L and runs
goto T1

The point is that semaphores have no ownership, e.g. once H transfers
the sema4 resource to L, it can't steal it back while L is sleeping like
we actually do for mutexes (who do maintain the notion of ownership),
because it just have no mean to know who owns the resource it has
released after returning from the sem_release call. Therefore, L must
run and release the sema4 before H has a chance to get back in control.
If you try with a mutex, you should see another behaviour.

To sum up, I see no issue. Did I miss your point?

> Thanks for any feedback on this.
> 
> Regards
> 
> Mathias
> 
> 
> 
> -- 
> Mathias Koehrer
> mathias_koehrer@domain.hid
> 
> 
> Viel oder wenig? Schnell oder langsam? Unbegrenzt surfen + telefonieren
> ohne Zeit- und Volumenbegrenzung? DAS TOP ANGEBOT JETZT bei Arcor: günstig
> und schnell mit DSL - das All-Inclusive-Paket für clevere Doppel-Sparer,
> nur  39,85 €  inkl. DSL- und ISDN-Grundgebühr!
> http://www.arcor.de/rd/emf-dsl-2
> _______________________________________________ Xenomai-help mailing list Xenomai-help@domain.hid https://mail.gna.org/listinfo/xenomai-help
-- 
Philippe.

Re: [Xenomai-help] Scheduler: Strange priority handling

[M. Koehrer]

HI all,

thanks for all the responses.
Using mutexes instead of semaphores actually solves the issue.
However, the API documentation of rt_sem_create() is a little bit confusing here.
The "mode" parameter of rt_sem_create() may contain "S_PRIO" which 
"makes tasks pend in priority order on the semaphore".
I interpret this that it works actually the very same as with mutexes. However, it
is implemented that sem_v directly triggers a waiting task (even if it is low prio).
As the semaphore has nothing to do with the scheduler, this makes sense.
However, this cannot be found within the API documentation.

Regards

Mathias

-- 
Mathias Koehrer
mathias_koehrer@domain.hid


Viel oder wenig? Schnell oder langsam? Unbegrenzt surfen + telefonieren
ohne Zeit- und Volumenbegrenzung? DAS TOP ANGEBOT JETZT bei Arcor: günstig
und schnell mit DSL - das All-Inclusive-Paket für clevere Doppel-Sparer,
nur  39,85 €  inkl. DSL- und ISDN-Grundgebühr!
http://www.arcor.de/rd/emf-dsl-2

Re: [Xenomai-help] Scheduler: Strange priority handling

[Dmitry Adamushko]

On 14/05/07, M. Koehrer <mathias_koehrer@domain.hid> wrote:
> HI all,
>
> thanks for all the responses.
> Using mutexes instead of semaphores actually solves the issue.
> However, the API documentation of rt_sem_create() is a little bit confusing here.
> The "mode" parameter of rt_sem_create() may contain "S_PRIO" which
> "makes tasks pend in priority order on the semaphore".
> I interpret this that it works actually the very same as with mutexes. However, it
> is implemented that sem_v directly triggers a waiting task (even if it is low prio).

So what's wrong here? It triggers a waiter with the highest priority
amongst _other waiters_ and in your case it's "L" (if I remember
abreviations correctly) - there are no other waiters in your case btw.
Waking up a sleeper really means - a resource is now yours.

How would the system know that your high-priority task which calls
rt_sem_v() / which means - I'm finished with a resource) / will call
rt_sem_p() as the very next step :o)


-- 
Best regards,
Dmitry Adamushko

Re: [Xenomai-help] Scheduler: Strange priority handling

[Philippe Gerum]

On Mon, 2007-05-14 at 13:57 +0200, M. Koehrer wrote:
> HI all,
> 
> thanks for all the responses.
> Using mutexes instead of semaphores actually solves the issue.
> However, the API documentation of rt_sem_create() is a little bit confusing here.
> The "mode" parameter of rt_sem_create() may contain "S_PRIO" which 
> "makes tasks pend in priority order on the semaphore".
> I interpret this that it works actually the very same as with mutexes. 

No, absolutely not. Please reread the detailed explanations. This is
_not_ a matter of priority management wrt sema4, but the ability for the
nucleus to steal the resource depending on the respective priority of
_threads_ that want to consume it. S_PRIO is about setting the sema4
behaviour when it comes to enqueue pending threads for _sleeping_ on a
resource; this has nothing to do with how a running thread might steal a
sema4 resource from another one due to its priority being higher
combined to the fact that the current owner of the resource did not wake
up yet in the meantime.

> However, it
> is implemented that sem_v directly triggers a waiting task (even if it is low prio).
> As the semaphore has nothing to do with the scheduler, this makes sense.
> However, this cannot be found within the API documentation.

The sema4 does have something to do with the scheduler: it calls its
services to operate on the thread runstates. But there is nothing else
to document, aside of "semaphores do work as expected", in this case.

> 
> Regards
> 
> Mathias
> 
-- 
Philippe.