this is so far a mind experiment combined with an untested patch:

[Assuming priority lists, the following is irrelevant for O(1) sched-queues]

Consider we have some bulk of threads with varying priorities waiting on
a xnsynch object. Typically, they are queued in priority order, the
highest prio thread at the head. When we wake them up all at once via
xnsynch_flush, we iterate from high to low prio threads.

Waking up includes inserting those threads in the ready queue(s), again
the highest prio thread first. On wake up of the first waiting thread we
will only have to skip those threads in the ready queue that have higher
priorities. For the second thread we already have to skip the first one
as well on insert if it isn't of the same priority. One may continue
this workflow...

Suggestion: Wouldn't it be more efficient to iterate the waiter queue in
ascending order? Should come at no costs and save a few cycles once in a

Index: include/nucleus/queue.h
--- include/nucleus/queue.h     (revision 1561)
+++ include/nucleus/queue.h     (working copy)
@@ -242,6 +242,19 @@ static inline xnholder_t *popq (xnqueue_
     return nextholder;
+static inline xnholder_t *lastq (xnqueue_t *qslot)
+    xnholder_t *holder = qslot->head.last;
+    return holder == &qslot->head ? NULL : holder;
+static inline xnholder_t *getlastq (xnqueue_t *qslot)
+    xnholder_t *holder = lastq(qslot);
+    if (holder) removeq(qslot,holder);
+    return holder;
 static inline int countq (xnqueue_t *qslot)
     return qslot->elems;
@@ -437,6 +450,11 @@ static inline xnpholder_t *poppq (xnpque
     return (xnpholder_t *)popq(&pqslot->pqueue,&holder->plink);
+static inline xnpholder_t *getlastpq (xnpqueue_t *pqslot)
+    return (xnpholder_t *)getlastq(&pqslot->pqueue);
 static inline int countpq (xnpqueue_t *pqslot)
     return countq(&pqslot->pqueue);
Index: ksrc/nucleus/synch.c
--- ksrc/nucleus/synch.c        (revision 1561)
+++ ksrc/nucleus/synch.c        (working copy)
@@ -525,7 +525,7 @@ int xnsynch_flush(xnsynch_t *synch, xnfl
        status = emptypq_p(&synch->pendq) ? XNSYNCH_DONE : XNSYNCH_RESCHED;
-       while ((holder = getpq(&synch->pendq)) != NULL) {
+       while ((holder = getlastpq(&synch->pendq)) != NULL) {
                xnthread_t *sleeper = link2thread(holder, plink);
                __setbits(sleeper->status, reason);
                sleeper->wchan = NULL;

Attachment: signature.asc
Description: OpenPGP digital signature

Xenomai-core mailing list

Reply via email to