Event synchronization

Event synchronization is one of the fundamental mechanisms to synchronize the work between 2 and more threads.
Generally an event  is useful if a  thread(threads) needs to signal another thread(s) that something, concerning the execution of the threads has happened.

 

 

  • Event object state 

Each event is represented by a memory structure called event object. The event object has 2 possible states - signaled and not signaled.
An event object is signaled if the event it was designed to wait for has taken place.The consequence of this state is that all,some or one(depends on the implementation specifics) waiting threads on this event are released.
An event object is not signaled if the event it was designed to wait for has NOT taken place.
All threads that has reached the event structure in their execution path will wait until the event gets signaled.

  • Event object reset type 

Event object could be auto reset or manually reset.
 
Manual reset event - event which state remains signaled until explicitly set to non signaled by a thread.Any number of threads waiting on the event is released while the event is signaled.
 
Auto reset event - event which state remains signaled until one and only one  thread waiting on it is released.It is the system code within the event API that puts the event to non signaled state right after the thread is released.
 
Acorn kernel implementation.
It is worth mentioning that atomic read - modify - write access to RAM is secured by disabling the global interrupt flag provided that  the API function is called in user land. Since it is not a desirable solution, the number of instructions within the atomic block should be kept as small as possible!
 

  • Basic event system

There is a simple event implementation in each version of Acorn kernel. It is based on read- modify-write bit atomicity. Each event  is represented by 1 bit (Fig.1) thus allowing 8 different events within 1 byte. Each event bit corresponds to a particular event context (GUI,io,adc sampling...) different tasks synchronize upon. An event is considered signaled if the corresponding bit is set to 1 and not signaled if it is 0. 

 

 

There are 2 API functions defined for the basic event in kernel.inc file.

_EVENT_WAIT - the thread polls the event bit flag to see if another thread has signaled it. If it is not signaled the thread will wait.It is the released thread that resets the flag to non signaled.
 
_SET_EVENT - a thread sets the event bit to signaled. Multiple threads could signal the event but only one thread could wait on it.

The small memory stamp - 1 bit per event - makes it a perfect choice for the CPU with limited memory range.
The problem is that it is impossible to have more then one thread waiting for the event to become signaled(well, it is possible but there is a contention that may prevent some threads from ever getting hold of the event - no fairness which may lead to starvation) and only 8 different events are available for design definition to the acorn programmer.One could use 2 bytes for the event structure, which will allow 16 different events but this require the API functions refactoring.

  • Extended event system

The contention fairness limitations are overcome with the extended event system in version 1.2.  The implementation is based on the so called Ticket Algorithm.  Each event structure is represented by 2 bytes in memory (Fig. 2)  and fragmented in the following sub elements.

S - signal/not signal flag {0,1}
V - Valid ticket number{0,15}
T - Ticket value to reserve{0,15}
The basic idea is that if a thread wishes to enter event wait loop,it takes the next available ticket(T sub element) and waits until its ticket becomes valid , at which point the thread can wait for the signal flag to be set to 1(signaled). When the thread exits the event wait loop, it validates the next invalid ticket in order, by incrementing the Valid ticket number(V sub element) .Because Ticket’s maximum value is 16(dec) , up to 15(see Danger note!) threads could wait on a single event.What follows is a brief review of the algorithm in AVR assembler (code extraction from _WAIT_EVENT_EX).

;INIT PART
1.    cli
2.    lds r17,@0+1        ;read global ticket which will be mine.
3.         mov temp,r17        ;backup ticket for later use
4.    inc r17
5.    cpi r17,0x0F        ;calculate next available ticket
6.    brlo weevjmp
7.         clr r17        
weevjmp:       
8.    sts @0+1,r17        ;save in global ticket variable which will be the next another task to reserve
9.         sei



;SPINNING PART
;1.wait until your ticket becomes valid
;2.wait until event flag is reised(=1)

10.       sbr temp,$80       ; Set MSB (which is the signal flag) in local ticket
weespin:
11.    lds r17,@0         ;current valid ticket and event signal    
12.    cp r17,temp
13.    breq go_to_exit_code
14.    _YIELD_TASK
15.       rjmp weespin

   

;EXIT PART
;next event signal could be missed(overriden) here if it happens between the read and write part of the event signal flag.

go_to_exit_code:    
16.    andi temp,0x0F       ;reset event flag
17.    inc temp
18.    cpi temp,0x0F        ;calculate next valid ticket number
19.    brlo weeexit
20.       clr temp        
weeexit:    
21.    sts @0,temp      



Code between {1,9} is atomic and is the place where the ticket for the thread that has reached _WAIT_EVENT_EX macro is reserved in a local variable{2,3}. The global ticket is incremented {4,8} and placed back in the global variable.This is the INIT part of the algorithm.

The SPINNING part {10,15} is the place where the thread waits on event signal and its ticket number becoming valid. The CPU is free to serve interrupts which improves real time type of CPU external event reactions.At any later point the thread becomes the first in the “waiting line” if it learns by inspecting the valid number that its ticket equals the  valid number{11,12} in which case it can safely enter the synchronized block after going through the EXIT part.

The EXIT part {16,21} is the place where the event flag is raised and threads ticket number has become valid.The thread goes on to clear the event signal flag(auto -reset type of event) and allow the next waiting on the event thread to execute code by increasing the global valid number{17,21}

Advantage::
1.Contention free.
2.Deadlock free.
3.Fair synchronization - each thread is activated in the order it has arrived to the INIT part.
4.N threads could notify/synchronize N threads 

Disadvantage:
1. Reserves  2 bytes for each event. Could be reduced to 1 byte but requires more calculating instructions.
2. Event signal could be missed if it comes in code interval {13,21}.


Danger:

There is a danger with ticket numbering when more threads are waiting and the event does not come any soon.It is possible for the ticket number to fall back to 0 from 16 and have the other thread from the "old" 0 ticket number still waiting for the event that has not come yet. Then we will have more then one thread with the same number which brakes the synchronization! So the basic solution is to keep the number of threads to synchronize on this event object in your app, lower then maximum possible ticket number.


The file EventExt.inc  (version 1.2 and up)   defines 3 API functions to implement the Ticket Algorithm:

_WAIT_EVENT_EX

_SET_EVENT_EX

_SET_EVENT_AND_WAIT_EX

Event synchronization is at the core of the well-build, rock solid multi-threaded kernel. Better understanding it will eventually lead to a better system design and implementation.

Note: In the context of Acorn kernel, terms task and thread are used interchangeably.