Concurrency Nonsequential Execution Eventing in NEPO
THIS IS A SKETCH OF AN OPENROBERTA-LAB EXTENSIONS. NOT FOR PUBLIC USE. BUT NOT SECRET.
SEND COMMENTS TO reinhard dot budde at iais dot fraunhofer dot de
This text describes an abstract model of concurrency/nonsequential execution/eventing in NEPO. The main goal is, that the model is as easy as possible to comprehend, even for beginners in programming. But note, that any departure from sequential models is a demanding undertaking.
The idea is, that the model can be implemented for many robot systems supported by the Openroberta lab. We want to avoid to have different models of concurrency/nonsequential execution/eventing for different robots. Notes on implementations are attached.
The source of the occurence of an event is a state change of an actor (e.g. button down, button up, ultrasonic distance < 50cm, color changes to red),
not the state of an actor (which would be button pressed). The occurence of an event triggers the execution of an associated statement list.
Thus an event handler is declared as event(actorIdentifier,stateChangeIdentifier) { statement list }. By its declaration in the program an
event handler is enabled, i.e. if the event occurs, the handler is triggered. State dependant activation/deacivation must be implemented w.t.h.
of a variable. The following example shows a downsampling of the button press event:
event(buttonA,pressed) {
everyFifthTime += 1;
if (everyFifthTime >= 5) {
everyFifthTime = 0;
...stmt list to be executed...
}
}
Notes:
- the pair (actorIdentifier,stateChangeIdentifier) must be unique in a program
- the statement list must NOT contain blocking ("time-consuming") functionality (sleep, drive 20 cm, ...)
- the statement list is executed completely, without interruption
- if during the execution of the statement list the event happens again, the event is ignored (Note: event handler must be SHORT)
- a more rigid behavior would be: if during the execution of the statement list an arbitrary event happens, the event is ignored. This may be easier to comprehend
Events and state are a kind of complementary: events are considered atomic and initiate and terminate a state, which is considered to exist for a non-empty time interval. Events have a subscript e and states s. Except button and bumper most events are not cheap, because they have a condition, that must be computed in software.
button and bumper:
- ups -> presse -> downs -> releasee -> ups
- ups -> clicke -> ups
ultrasonic / infrared: testing distance of x cm.
- distanceGt(x)s -> approach(x)e -> distanceLt(x)s -> goAway(x)e -> distanceGt(x)s
color sensor: testing intensity of light/ambient light as x%.
- dark(x)s -> lighten(x)e -> light(x)s -> darken(x)e -> dark(x)s
color sensor: testing color x (red, green, blue, ..., rgb(r,g,b)).
- differentColored(x)s -> become(x)e -> colored(x)s -> loose(x)e -> differentColored(x)s
rotation sensor: testing x.
- lessDegrees(x)s -> gotDegrees(x)e -> moreDegrees(x)s
- lessRotations(x)s -> gotRotations(x)e -> moreRotations(x)s
- lessDistance(x)s -> gotDistance(x)e -> moreDistance(x)s
timer sensor: testing for elapsed x msec.
- before(x)s -> elapse(x)e -> after(x)s
pins: x is the number of the pin.
- down(x)s -> rise(x)e -> up(x)s -> fall(x)e -> down(x)s
Tasks are threads of control. They are declared as name { statement list }. The names must be unique in the program. start is a reserved name.
The start task exists always and is executed when the program is started on a robot system.
A task can be started by the run expression rc = run(taskName). The statement terminates immediately (it is NOT blocking). Now both the starting
task/event handler and the started task are ready to execute. The starting task/event handler remains executing.
Notes:
- a task already executing cannot be started. This is indicated by the return code
falseof the run expression. - running tasks can be interrupted ONLY at the beginning (or during) statements that are blocking. Thus we use a kind of cooperative scheduling.
- we use a idle task, which is running, if no other task can run. This task sleeps a (very) short time and triggers then the scheduler (see below).
-
At any point in time there exists a non-empty set of tasks, which are ready to execute. One of the tasks is running.
-
if this tasks hits a blocking statement, the scheduler assigns a wake-up time to the task or a condition for awaking the task. If the running task is the idle task, a (very) short wake-up delay is assigned.
-
if the task terminates because its statement list is exhausted, the task is removed from the set of tasks.
-
in both cases the scheduler gets control.
-
if the scheduler gets control and an (hardware triggered) event occured (this is the "cheap" case), the event's statement list is executed. The scheduler becomes active again after that statement list terminates.
-
this process is repeated until all these kind of events have been processed. Note, that this can freeze the execution of tasks forever.
-
now the awake-conditions are checked. This includes reading sensor values and comes with some cost. If a condition is true (now), the corresponding task is selected and gets control. For fairness a round-robin mechanism is used to avoid starvation of a task.
-
due to the cooperative scheduling it is possible, that event pairs get lost (e.g. a rise and fall of a pin occured, because the scheduler didn't get control during the time span in which the pin was in state down. This is inevitable.
-
if no hardware event has to be processed, the task with the shortest wake-up time is selected. If this time points into the future, the scheduler sleeps until that time. Note, that the sleep time of the scheduler cannot be greater than the sleep interval of the idle task.
-
Otherwise the selected task gets control.
-
if the scheduler awakes again, the whole event checking process is re-executed.
-
due to a processor overload it may happen, that a task starts running an arbitrary time span after its wake-up time. This is inevitable.
- Calliope supports cooperative scheduling with its fibres. It should be possible to use this. Hardware related events are available. Probably low effort.
- leJos supports hardware related events. Using threads for tasks is possible, but expensive and because of Javas memory model demanding, if we want to avoid subtle synchronisation errors.
- ev3dev doesn't support hardware related events. A kind of event loop thread is needed to trigger events and schedule tasks. Probably medium effort. Python3 has a nice threading library, python2 support is weaker.
- nao like ev3dev
- c4ev3 needs probably high effort.
- arduino variants have no builtin support for events/tasks. But because we have complete control over the generated system, implementing the model has probably medium effort.
Detailed prototyping is needed for each robot to avoid pitfalls as "implementation in this context seems to be impossible"
- it is possible, to use very general conditions to trigger event occurences, i.e. any boolean expression. This add costs, but not more than checking a condition as
ultrasonic distance < x cm. - for prototyping it makes sense, to set up an IDE for C++ programming of the Calliope. This system supports most of the requiured functionality.
- to set this productive, we probably need a third toolbox with event blocks to avoid irritation for users.
- the code generation process may follow these lines:
- statement list for event handlers and tasks are packaged into a void function (~an instance of a class with a
run():voidmethod) - trigger expressions of events are packaged into a boolean function (~an instance of a class with an
eval():booleanmethod) - the scheduler looks a bit like the scheduler used for the stack machine scheduler used in the simulation
- statement list for event handlers and tasks are packaged into a void function (~an instance of a class with a
- the implementation of the simple "OS" must be open source and easily to inspect and to understand
Home | Community | Installation | Team 