[En-Nut-Discussion] RTOS Comparison

[Nathan Moore]

I think that the two easiest to fix issues with Nut's thread switching
is how it does
timers and ISR posted events.

If I recall correctly the entire timer list is walked every time the
scheduler is called.
While keeping this list sorted may be difficult, it should be easy
enough to keep
copy of the earliest timer time in a variable that the schduler can
see and short
circuit looking at the timers many times.
In the case of event's with a timer being posted and removed from the timer list
you would have to look at the timer list (like it's done now) to see
that nothing
had actually expired, which is what you have now.
I've got some other timer issues, but this is easiest to fix, I think.

The next issue I have is that you have to walk the entire thread list
looking for
threads that were posted from ISRs.  Having 2 thread posting algorithms is
just asking for trouble, anyway, but it's also slow.
Something I toyed around with a while back was to replace both the ISR and
the application event post routines with a new algorithm.
This would envolve a global posted event stack (just a linked list of threads in
LIFO order).  Every time an even was posted and a thread was waiting the
thread would be taken off the top of the eventqueue ( O(1) operation) pushed
onto this stack ( O(1) operation).  This would be the same in ISRs and in
applications.
NutEventPost( void * event) {
    NutEnterCritical();
    NutPostEventFromISR(event, -1); // The second param is what to put
on the event queue if it is empty
    NutExitCritical();
}
NutEventPostNext( void * event) {
    NutEnterCritical();
    NutPostEventFromISR(event, NULL);
    NutExitCritical();
}
NutPostEventFromISR is just a pop from the event waiting queue and a push
to a stack.

Then, when the scheduler got called this posted event stack (remember, just
a linked list) would swapped out for an empty stack (O(1) operation), and be
reversed (O(N) operation, but it should usually be short).
    NutEnterCritical();
    my_event_list = global_event_list;
    global_event_list = NULL;
    NutExitCritical();
This is the only part that needs to be protected, as the ready queue doesn't
need to worry about ISRs doing anything to them b/c they only touch the
events themselves and the posted stack.
I've written list reversal code before, but don't have it handy and
will probably
screw it up if I try to rewrite it here, but it's not difficult and is
O(ListMembers).
This leaves you with a list sorted by earliest posting.  You can then pop
nodes off of this list and add them to the run queue.  You can speed this up
a little bit for the case where nodes in the event list from which you
are popping
just happen to be priority sorted already by not going back to the top of the
run queue unless the next node is of a higher priority than the next position
in the run queue from the node after the previously inserted node.
Anyway, for any given call to the scheduler the posted event stack should be
short.

NutEventPostBroadcast could be implemented by just swapping out the event
wait queue with an empty queue and add that to the top of the posted event
stack.

Nathan