Index

Cooperating Sequential Tasks

  1. Introduction
    1. Arduino
    2. Interrupts
  2. Simple Tasks
  3. Multiple Tasks
  4. Communicating Tasks
  5. Communicating Values
  6. Synchronising Tasks
  7. Buffered Communication
  8. Multiple Senders
  9. Conditional Tasks
  10. Transput
  11. Implementation
    1. Common Data
    2. Tasks
    3. task_builder
    4. task
    5. channel
    6. virtual_machine
    7. set
    8. queue
    9. clock
    10. standard
    11. Adjusting Limits

virtual_machine



The virtual machine is a software defined processor which executes cyclic sequences of actions stored in the code array. Each task has its own virtual program counter stored in the next_act field of its task_record. The virtual program counter is initialised to the value contained in the first_act field of the task_record, which indicates where the details of the first action are stored. After a task executes the last action in the sequence defined when it was created, the virtual program counter is reset to the first action again so that the task loops forever, or until it executes a terminate action.

The main functions of the virtual machine and general task management are activated by calling the run_system function defined in the Tasks component. As can be seen below, this checks to see if there are any tasks waiting for conditions or because they are paused. As a result of which some tasks may be reactivated and add to the back of the active_tasks queue. If the number of queued tasks is greater than zero after this has been done, the identifier of the task at the front of the queue is determined and a pointer to is task_record is passed to the execute function.

void run_system()
{
  if (!empty_set(&waiting_set)) check_waiters();
  if (queued(&active_queue) > 0)
  {
    byte id = peek(&active_queue);
    execute(&tasks[id]);
  }
}


The execute function will perform the actions stored in the code array starting at the position indicated by the tasks virtual program counter. Execution will continue until the task becomes inactive due to pauses, waits, communication or termination. When reading the following description of the execution of individual actions, it is important to remember that the currently executing task will remain at the front of the active_queue until it becomes delayed so that the following task can be executed.

void execute(task_record* t)
{
  t->state = active;
  while (t->state == active) evaluate(t);
}


Each time the evaluate function is called, it executes the next action in the task.

void evaluate(task_record* t)
{
  current_task = t->id;
  act a = (act)code[t->next_act];
  t->next_act = t->next_act + 1;
  switch (a)
  {
    case no_act           :                          break;
    case simple_act       : do_simple_act       (t); break;
    case with_arg_act     : do_with_arg_act     (t); break;
    case wait_act         : do_wait_act         (t); break;
    case wait_with_arg_act: do_wait_with_arg_act(t); break;
    case send_act         : do_send_to_act      (t); break;
    case receive_act      : do_receive_from_act (t); break;
    case transput_act     : do_transput_act     (t); break;
    case pause_act        : do_pause_act        (t); break;
    case loop_act         : do_loop_act         (t); break;
    case terminate_act    : do_terminate_act    (t); break;
    case when_act         : do_when_act         (t); break;
    case repeat_act       : do_repeat_act       (t); break;
  }
  if (a != when_act && a != repeat_act) skip = false;
  if (a != repeat_act && t->repeating)
  {
    t->repeating = false;
    t->next_act  = t->repeat_point;
    delay_task(t);
  } 
}


The global current_task variable must always be set to the identifier of the current task as various other functions including the implementation of set_task_data and get_task_data depend on it.

The evaluate function first determines which action is to be performed by extracting an act value from the code array at the location indicated by the virtual program counter. The virtual program counter is then advanced so that it either points at the beginning of the next action or at the first argument of the current one. The value of the current action code is used to select a functions to handle it. There is one function for each of the actions represented by the act enumeration. Each of these functions must access any required arguments from the code array via the virtual program counter, advance it accordingly, and then perform the require action.

The implementations of individual actions are described below.

Action

void do_simple_act(task_record* t)
{
  action_routine routine = (action_routine)code[t->next_act];
  t->next_act            = t->next_act + 1;
  if (skip) return;
  routine();
}


Where a simple action is specified in a task definition, the task_builder adds the act value simple_act to the code array followed by a pointer to a C++ action_routine, i.e. a void function without any parameters. The execute function will leave the virtual program counter next_act referring to the action_routine, which do_simple_act retrieves before incrementing the virtual_program counter. Having done this, it checks to see if the action should be skipped because the global skip variable is set to true as a result of a preceding when or repeat action. If this is the case, the action _routine is not executed. It is important that any required arguments of an action are retrieved, and that the virtual_program counter is advanced accordingly, before the main part of an action is skipped. This ensures that the virtual program counter always refers to the next action even if the current action is skipped.

The do_with_arg_act is very similar to do_simple_act, but has to retrieve two arguments and advance the virtual program counter twice.

void do_with_arg_act(task_record* t)
{
  action_routine1 routine = (action_routine1)code[t->next_act];
  t->next_act             = t->next_act + 1;
  int             value   = code[t->next_act];
  t->next_act             = t->next_act + 1;
  if (skip) return;
  routine(value);
}


Wait

The implementation of wait actions which cause a task to become delayed until a wait_condition become true is as follows.

void do_wait_act(task_record* t)
{
  wait_condition condition = (wait_condition)code[t->next_act];
  t->next_act              = t->next_act + 1;
  if (skip) return;
  dequeue(&active_queue);
  t->state     = waiting;
  t->condition = condition;
  insert(&waiting_set, t->id);
}


It retrieves the wait_condition from the code array and then checks to see if the wait action is to be skipped. Assuming it is not, it removes the current task from the active_queue and sets it state to waiting. So that the virtual machine can check the status of the task at a later time, the wait_condition is stored in the condition field of the task's task_record, and the task's identifier is added to the waiting_set. The check_waiters function associated with the task component will be called periodically to check the status of all tasks whose identifiers appear in the waiting_set. This evaluates the wait_conditions stored in each waiting task's task_record. If the condition returns true, the task is removed from the waiting_set, placed at the back of the active_queue, and has its state set to active. It will be executed further after the other tasks which precede it in the queue become non-active.

Where a wait action involves a condition with an argument, i.e. a wait_condition1, it will be implemented by the do_wait_with_arg_act function. This is almost identical to the do_wait_act function, but must retrieve both a condition and its argument from the code array. In addition it must store both the condition and the argument value in the task_record of the task concerned.

void do_wait_with_arg_act(task_record* t)
{
  wait_condition1 condition = (wait_condition1)code[t->next_act];
  t->next_act               = t->next_act + 1;
  int value                 = code[t->next_act];
  t->next_act               = t->next_act + 1;
  if (skip) return;
  dequeue(&active_queue);
  t->state              = waiting_with_arg;
  t->condition_with_arg = condition;
  t->wait_data          = value;
  insert(&waiting_set, t->id);
}


Pause

The do_pause_act function implements pause actions.

void do_pause_act(task_record* t)
{
  int duration = code[t->next_act];
  t->next_act  = t->next_act + 1;
  if (skip) return;
  dequeue(&active_queue);
  t->state      = paused;
  t->start_time = clock_time();
  t->pause_time = duration;
  insert(&waiting_set, t->id);
}


It retrieves the duration of the pause, removes the task from the active_queue, and sets its state to paused. It then requests the current time in milliseconds from the clock component and stores it in the start_time field of the task_record of the current task. It also stores the duration in the pause_time field of the task_record and adds the current task's identifier to the waiting_set. The check_waiters function associated with the task component will be called periodically to check the status of all tasks whose identifiers appear in the waiting_set. This uses the time_up function provided by the clock component in conjunction with the start_time and pause_time fields stored in each paused task's task_record. If the time_up returns true given the start_time and the pause_time, the task is removed from the waiting_set, placed at the back of the active_queue, and has its state set to active. It will be executed further after the other tasks which precede it in the queue become non-active.

Loop

The do_loop_act function implements an action that is not specified directly in a task's description. Instead it is added on the end of the code array automatically by the end_task function. Its purpose is to cause the task to loop back to its first action. To achieve this, it sets the virtual program counter, next_act, for the task to the value of first_act in the task_record. This is always set by the task_builder to refer to the first action specified in a task. In addition, the current task is left in an active state, but put to the back of the active_queue by using the delay_task function provided by the task component. This ensures that tasks cannot block other tasks even if they loop forever without getting delayed by waits, pauses or communication. Notice that it is not possible skip this action as the state of the skip variable is not checked.

void do_loop_act(task_record* t)
{
  t->next_act = t->first_act;
  delay_task(t);
}


Terminate

The terminate action is implemented by the do_terminate_act function. All this has to do is to remove the current task from the active_queue and set its state to idle. After this, the task will never be executed again.

void do_terminate_act(task_record* t)
{
  if (skip) return;
  suspend(t->id, idle);
}


When

Conditional actions are specified by using the when action before another action that is only to be executed if some condition returns true. Conditions used by when are defined in C++ using the same function type as the conditions used in wait actions, i.e. wait_condition. After retrieving the condition from the code array and advancing the virtual program counter, do_when_act evaluates the condition and sets the global skip variable to true if the condition evaluates to false. The value of skip, as seen in the descriptions of the implementations of other actions above, is used to conditionally inhibit the execution of the actions immediately following when. Refer to the implementation of the execute function shown at the beginning of this section to see how this is done in detail.

Notice that when actions cannot be skipped as the value of skip is not checked by the do_when_act function, i.e. it does not make any sense to write two or more consecutive when actions in a task definition.

void do_when_act(task_record* t)
{
  wait_condition condition = (wait_condition)code[t->next_act];
  t->next_act = t->next_act + 1;
  skip = !condition();
}


Repeat

Conditionally repeated actions are specified by using the repeat action before another action that is to be executed and repeated if some condition returns true. The implementation of repeat by the do_repeat_act function is very similar to that used for when actions as shown above. As with when actions, if the associated condition evaluates to false, the following action must be skipped. The implementation of this is identical to that used for when actions. However, if the condition evaluates to true, it is necessary to store the virtual program counter value which refers to the repeat action itself and an indication that the virtual machine must loop back to the repeat after the following action has been executed. These values are stored in the repeating and repeat_point fields of the current task's task_record. Refer to the implementation of the execute function shown at the beginning of this section to see how this is done in detail.

Notice that repeat actions cannot be skipped as the value of skip is not checked by the do_repeat_act function, i.e. it does not make any sense to write two or more consecutive repeat actions in a task definition, nor does it make any sense to write a when immediately after a repeat, or to write a repeat immediately after a when action.

void do_repeat_act(task_record* t)
{
  wait_condition condition = (wait_condition)code[t->next_act];
  t->next_act = t->next_act + 1;
  if (condition())
  {
    t->repeating    = true;
    t->repeat_point = t->next_act - 2;
  }
  else skip = true;
}


Communication Actions

The remaining actions whose implementations need to be described all involved communication. Most of the work required to implement communication is performed by functions provided by the channel component. These can determine when a channel is ready to communicate, i.e. at least one sender and all required receivers are ready, and can transfer any data required between the sender's source function and all of the receivers' sink functions. Also provided are functions which to perform the necessary housekeeping operations required to reactivate any tasks delayed waiting for communication. See the description of the channel component for more details.

Send To

The virtual machine's implementation of the send_to action using do_send_to_act is shown below.

void do_send_to_act(task_record* t)
{
  byte channel_id    = code[t->next_act];              t->next_act = t->next_act + 1;
  data_source source = (data_source)code[t->next_act]; t->next_act = t->next_act + 1;
  if (skip) return;
  t->source          = source;
  insert(&channels[channel_id].active_senders, t->id);
  if (channel_ready(&channels[channel_id]))
    send_signal(t, channel_id, source);
  else
    suspend(t->id, sending);
}


The do_send_to_act function first retrieves the channel identifier and data_source function specified by the send_to action. The source is then stored in the source field of the current task's task_record for use later if the send cannot go ahead straight away, i.e. if the specified channel is not ready. To let the channel know that at least one sender is available, the identifier of the current task is inserted into the channel's set of active_senders.

At this point, the channel_ready function provided by the channel component can determine if communication can proceed. If it can, the send_signal function, also provided by the channel component, is given a pointer to the current task's task_record, the channel identifier, and the data_source function so that it can complete the communication and update the channel and all the other tasks involved.

If the channel is not ready, the current task is suspended, i.e. it is removed from the active_tasks set and its state is set to sending, and must await other actions to be taken by receivers using the same channel.

Receive From

To implement the receive_from action, do_receiver_from_act proceeds in a similar fashion to do_send_to_act described above. It retrieves a channel identifier and a data_sink function, which it stores in the current task's task_record in the sink field in case it is needed later if the channel is not ready. It then inserts the identifier of the current task in the indicated channel's set of active_receivers before using the channel_ready function to check if the communication can proceed. If the channel is ready, communication is completed by using the receive_signal function provided by the channel component. If the channel is not ready, the current task is suspended to await communication actions by other tasks using the same channel.

void do_receive_from_act(task_record* t)
{
  byte channel_id = code[t->next_act];             t->next_act = t->next_act + 1;
  data_sink sink  = (data_sink)code[t->next_act];  t->next_act = t->next_act + 1;
  if (skip) return;
  t->sink         = sink;
  insert(&channels[channel_id].active_receivers, t->id);
  if (channel_ready(&channels[channel_id]))
    receive_signal(t, channel_id, sink);
  else
    suspend(t->id, receiving);
}


Transput

The implementation of the transput retrieves an input channel identifier and a data_sink to use for a potential receive operation, and an output channel identifier and a data_source to use for a potential send operation. It then, arbitrarily, checks to see if the input channel is ready with the current task acting as a receiver after inserting the current task's identifier into the input channel's active_receivers set. It also stores the data_sink in the sink field of the task_record in case the communication cannot proceed immediately. The input channel identifier is also stored in the alt_input field of the task_record. This will be used to undo changes made to the input channel if the transput operation eventually results in sending rather than receiving.

If the channel is ready at this stage, the communication completes just as if a simple receive_from action were in progress.

If the channel is not ready for the current task to receive, the do_transput_action adds the current task's identifier to the output channel's active_senders set. The data_source is stored in source field of the task_record, and the output channel identifier is stored in the alt_output field, thus mirroring the previous actions used to set-up for receiving.

If the channel is ready at this stage, the communication completes just as if a simple send_to action were in progress.

If the input channel is not ready to complete a receive and the output channel is not ready to complete a send, the task is suspended until other tasks make one of these actions possible. If the receive happens first then, in addition to the operations needed to complete a receiver_from action, the receive_signal function must also remove any information which was set-up to permit a send. If this is not done, the output channel may, erroneously, become ready to complete a send set-up by a transput action which has already completed a receive. Conversely the input channel may, erroneously, become ready to complete a receive set-up by a transput action which has already completed a send, unless the send_signal function resets the information set-up to permit the receive. The receive_signal and send_signal functions use the alt_input and alt_output fields in the task_record to achieve this.

void do_transput_act(task_record* t)
{
  byte input         = code[t->next_act];              t->next_act = t->next_act + 1;
  data_sink sink     = (data_sink)code[t->next_act];   t->next_act = t->next_act + 1;
  byte output        = code[t->next_act];              t->next_act = t->next_act + 1;
  data_source source = (data_source)code[t->next_act]; t->next_act = t->next_act + 1;
  if (skip) return;
  t->sink            = sink;
  t->alt_input       = input;
  insert(&channels[input].active_receivers, t->id);
  if (channel_ready(&channels[input]))
    receive_signal(t, input, sink);
  else
  {
    t->source     = source;
    t->alt_output = output;
    insert(&channels[output].active_senders, t->id);
    if (channel_ready(&channels[output]))
      send_signal(t, output, source); 
    else
      suspend(t->id, transputting);
  }
}