Harald: Created page with "
= Nut/OS Events =
This paper provides an overview of Nut/OS event handling internals. Basically Nut/OS thread scheduling can be understood as han..."

2017-07-13T07:47:56Z

Created page with "<div id="content"> = Nut/OS Events = <br /> This paper provides an overview of Nut/OS event handling internals. Basically Nut/OS thread scheduling can be understood as han..."

New page

<div id="content">

= Nut/OS Events =

<br />

This paper provides an overview of Nut/OS event handling internals.

Basically Nut/OS thread scheduling can be understood as handling events by moving threads among queues. A thread waiting for an event is blocked by moving it from a global ready-to-run queue to a queue, that is expected to receive this event.

<br />

== Linked Lists of Threads ==

During system initialization, the idle thread is created first, which in turn creates the main application thread. Depending on the Nut/OS components used by the application, the system may create additional threads like the DHCP client or the Ethernet receiver thread. Applications can create more threads by calling

<div class="coding">

<pre> HANDLE NutThreadCreate(u_char * name, void (*fn) (void *), void *arg, size_t stackSize);</pre>

</div>
The first parameter, the thread's name, does not have any other purpose than providing a symbolic name. The second parameter specifies the name of the routine, which will be started as a thread and the third parameter is passed to this routine. Each thread gets its own stack and the size of this stack is specified by the fourth parameter.
When successful, <code>NutThreadCreate</code> returns a handle, in fact a pointer to the <code>NUTTHREADINFO</code> structure of the new thread.

[[File:../../img/nutevents00a.png|713x532px|Thread Structure]]
Each time, when Nut/OS creates a new thread, a <code>NUTTHREADINFO</code> structure is allocated from heap memory and and added in front of a linked list containing all existing threads. The global pointer <code>nutThreadList</code> points to the first entry.

To keep things simple, the following diagrams will show the relevant structure members only. Furthermore, let's assume, that only three threads have been created, the idle thread, the main application thread and an additional thread created by the application. This will result in the following list of threads.

[[File:../../img/nutevents01a.png|923x297px|Events 1]]
The pointer <code>nutThreadList</code> points to a list, which contains all three threads. This list is linked by the structure element <code>td_next</code> (red colored links). The last <code>NUTTHREADINFO</code> structure is always the one of the idle thread.

We notice, that there are more lists. The global pointer <code>runQueue</code> points to the list of all threads, which are ready to run and linked by <code>td_qnxt</code> (blue colored links). In opposite to <code>nutThreadList</code>, new entries are not simply added to the front. This list is always sorted by the value of <code>td_priority</code>. In Nut/OS, low values mean high priority. The idle thread is running at lowest priority 254. Again to keep the follwing diagrams simple, the priority order is the same as the list of all threads. In reality this is usually not the case.

<br />

== Waiting for an Event ==

The <code>runQueue</code> does not always contain all existing threads, but only those which are ready to run. One of its entries must have the state <code>TDS_RUNNING</code> and all remaining entries in this queue are in state <code>TDS_READY</code>. Threads with state <code>TDS_SLEEP</code> will never be part of the <code>runQueue</code>.

If a thread directly or indirectly calls

<div class="coding">

<pre> int NutEventWait(HANDLE * qhp, u_long ms);</pre>

</div>
then the related <code>NUTTHREADINFO</code> structure will be removed from this list of ready-to-run threads.
The first parameter of <code>NutEventWait</code> is a pointer to a pointer to a linked list (HANDLE is defined as a void pointer). This parameter is used in a similar way as <code>runQueue</code>, but instead of listing all ready-to-run threads, it contains a list of threads waiting for a specific event. In our example the thread with the highest priority called

<div class="coding">

<pre> HANDLE eventqueue = 0;
NutEventWait(&eventQueue, 1000);</pre>

</div>
and thus had been removed from <code>runQueue</code> and added to <code>eventQueue</code>.
Internally, <code>NutEventWait</code> executes

<div class="coding">

<pre> NutThreadRemoveQueue(runningThread, &runQueue);
runningThread->td_state = TDS_SLEEP;
NutThreadAddPriQueue(runningThread, (NUTTHREADINFO **) qhp);</pre>

</div>
to remove the currently running thread from the <code>runQueue</code>, change its state from <code>TD_RUNNING</code> to <code>TDS_SLEEP</code> and to add it to the <code>eventQueue</code>.
The second parameter of <code>NutEventWait</code> specifies the maximum time the thread is willing to wait for an event posted to the queue. If this parameter is zero, the thread will wait without time limit. Otherwise it is interpreted as the number of milliseconds to wait and Nut/OS will create a timer in this case.

Like threads, timers are created by allocating a <code>NUTTIMERINFO</code> from heap memory and adding it to a linked list. The global pointer <code>nutTimerList</code> points to the first entry and following entries are linked by the pointer <code>tn_next</code>, which is a member of <code>NUTTIMERINFO</code>.

If a timeout is specified, <code>NutEventWait</code> calls

<div class="coding">

<pre> HANDLE NutTimerStart(u_long ms, void (*callback) (HANDLE, void *), void *arg, u_char flags);</pre>

</div>
which creates the <code>NUTTIMERINFO</code> structure and adds it to <code>nutTimerList</code>. We will discuss the situation in case of a time out later in more detail.
Finally, <code>NutEventWait</code> calls

<div class="coding">

<pre> NutThreadSwitch();</pre>

</div>
which pushes the CPU registers on the stack, changes the state of the thread in front of the <code>runQueue</code> from <code>TD_READY</code> to <code>TD_RUNNING</code> and loads the CPU registers for the stack of this thread.
In this document I will not describe in detail, how Nut/OS switches from one to another thread. In fact, <code>NutEventWait</code> will not return immediately, because the CPU starts execution of the second thread.

[[File:../../img/nutevents02a.png|923x486px|Events 2]]
Let's assume, that our second thread directly or indirectly calls <code>NutEventWait</code> too on the same <code>eventQueue</code>.

<div class="coding">

<pre> NutEventWait(&eventQueue, 1000);</pre>

</div>
Again a timeout value has been given and Nut/OS moves the related <code>NUTTHREADINFO</code> structure from the <code>runQueue</code> to this <code>eventQueue</code>, does the required updates of <code>td_state</code>, creates another timer and finally passes control to the last thread.
[[File:../../img/nutevents03a.png|923x553px|Events 3]]
As described above, the last thread is the idle thread, which will never be removed from the <code>runQueue</code>. It serves as a placeholder during times, when all worker threads are sleeping. It keeps the CPU busy by calling <code>NutThreadYield</code> in an endless loop. As soon as another thread becomes ready to run, the idle thread will lose CPU control. In our case, this may happen as soon as an event is posted to the <code>eventQueue</code>.

<br />

== Posting an Event ==

In order to wake up a thread waiting in an event queue, a thread calls

<div class="coding">

<pre> int NutEventPost(HANDLE volatile *qhp);</pre>

</div>
This will remove the <code>NUTTHREADINFO</code> structure in front of this priority ordered linked list to the <code>runQueue</code>. As we already know, the <code>runQueue</code> is also ordered by priority. If the thread, which called <code>NutEventPost</code>, has a lower priority than the woken up thread, CPU control is passed to the latter.
Alternatively a thread may call

<div class="coding">

<pre> int NutEventBroadcast(HANDLE * qhp);</pre>

</div>
in which moves all threads in the specified queue to the <code>runQueue</code>.
In our given example, only the idle thread is left. When the idle thread is doing nothing except calling <code>NutThreadYield</code> in a loop, who is posting an event while both worker threads are sleeping? Well, there are two special calls, which can be called from within interrupt routines.

<div class="coding">

<pre> int NutEventPostAsync(HANDLE volatile *qhp);
int NutEventBroadcastAsync(HANDLE * qhp);</pre>

</div>
The main difference to <code>NutEventPost</code> and <code>NutEventPostAsync</code> is, that Nut/OS will move the <code>NUTTHREADINFO</code> structures and update the <code>td_state</code> values, but will not switch the CPU control. This is actually done when the idle thread calls <code>NutThreadYield</code>. Nut/OS provides cooperative multithreading, which means, that a thread can rely on not losing CPU control without calling specific system function which may change its state. However, interrupts are preemptive in any case. By delaying the context switch, Nut/OS ensures, that cooperative multithreading is maintained even when interrupts are able to wake up sleeping threads.
So far let's assume, that in our example some kind of smart interrupt routine posts an event to <code>eventQueue</code> by calling

<div class="coding">

<pre> NutEventPostAsync(&eventQueue);</pre>

</div>
and that our high priority thread is back in the <code>runQueue</code>.
[[File:../../img/nutevents04a.png|923x556px|Events 4]]
If an event is posted to the <code>eventQueue</code> before the timer elapses, then the <code>NUTTIMERINFO</code> will be removed from the <code>nutTimerList</code> by a call to

<div class="coding">

<pre> NutTimerStopAsync(td->td_timer);</pre>

</div>
The second thread is still waiting for an event and we assume, that a time out will occur.
<br />

== Event Timeout ==

In detail, <code>NutEventWait</code> calls

<div class="coding">

<pre> td_timer = NutTimerStart(ms, NutEventTimeout, (void *) qhp, TM_ONESHOT);</pre>

</div>
when a timeout value other than zero has been specified. Further details of Nut/OS timer handling are not described in this document, but let's look at least to the parameters. The first one contains the number of milliseconds the thread is willing to wait for an event. The second parameter points to a functions, which will be called when the timer elapses. The third parameter will be passed to this function, it points to the event queue. The last parameter puts the timer in oneshot mode. This means, that it is automatically removed from <code>nutTimerList</code> after the timer elapsed.
Obviously the most interesting parameter is the callback routine

<div class="coding">

<pre> void NutEventTimeout(HANDLE timer, void *arg);</pre>

</div>
This procedure is part of the Nut/OS event handling module and directly called by the timer interrupt routine when a timer elapses. As explained above, a pointer to the related queue is passed to this routine along with the handle of the timer (actually a pointer to <code>NUTTIMERINFO</code>). In our example, the timer handle is the same, that had been previously stored in <code>td_timer</code> and the <code>arg</code> points to <code> eventQueue</code>.
The <code>NutEventTimeout</code> will walk through this queue, searching for the <code>NUTTHREADINFO</code> structure that contains a <code>td_timer</code> with the same timer handle. If it is not found, the routine doesn't care. It simply means, that an event already removed the thread from the queue. Nothing else can be done, because the Nut/OS timer handling will automatically remove oneshot timers.

If it is found, <code>td_timer</code> will be cleared and the <code>NUTTHREADINFO</code> structure will be moved to the <code>runQueue</code>. Remember, that <code>NutEventTimeout</code> is running in interrupt context. So it will not perform any thread switching. As soon as the running thread calls any such function, a thread switch may occur. In our example, this will not happen, because the currently running thread got a higher priority.

[[File:../../img/nutevents01a.png|923x297px|Events 1]]
Later on, CPU control will be (hopefully) passed to the second thread, which then continous to execute <code>NutEventWait</code>. This routine will check whether it had been called with a timeout value and <code>td_timer</code> had been cleared to zero. In this case it returns -1 to inform the caller, that a time out occured. Otherwise zero will be returned.

<br />

== Problem Discussion ==

At the time of this writing, Nut/OS is at version 3.9.2.

<code>Problem 1: </code>Not yet verfied, but it looks like events are sometimes lost when a timeout value has been specified. With most applications this is no real problem, because the timeout will avoid complete blocking of the thread.

<code>Problem 2: </code>Several variables and parameters are marked volatile. However, cooperative multithreading requires a volatile attribute for variables only, if they are modified in interrupt routines.

Harald Kipp<br />
Herne, October 9th, 2004.

<br />

</div>

Documents/NTN-2 Events - Revision history

Harald: Created page with " = Nut/OS Events = This paper provides an overview of Nut/OS event handling internals. Basically Nut/OS thread scheduling can be understood as han..."

Harald: Created page with "
= Nut/OS Events =
This paper provides an overview of Nut/OS event handling internals. Basically Nut/OS thread scheduling can be understood as han..."