Simple Multi-Task Tower Builders: Tasks, Resources

The previous example consisted of a single task that builds a single tower. What if we want to have multiple tasks each building their own tower? The first problem is if two tasks need to use the same block to build their towers. Clearly this is not going to be possible. However, assuming the blocks needed for each tower are disjoint, we must ensure that the tasks do not attempt to control the one arm at the same time. Unless we allow each task to finish its tower before starting another tower building task, which is not multi-tasking, we must fairly alternate the use of the arm between the tasks.

The arm can be thought of as a resource. A tower building task T needs to have exclusive use of the resource whenever it needs to move a block. It can then release the resource when the block move is completed, or is abandoned because that move is no longer the next thing that must be done in task T, due to outside interference. For example, the move of a block B1 to lie on top of another block B2 will be abandoned if outside interference:

• has covered B2,
• moved B2 so it is no longer the top block of a partly built tower,
• covered B1 with a block,
• helped by moving B1 to be on top of B2.

In traditional programming exclusive use of a resource is often accomplished by using locks. In TeleoR, exclusive access to one or more resources is achieved in a more declarative fashion by simply specifying which procedures may be called to start a resource sharing task, and which procedures must be given exclusive access to the resources they need before a call to the procedure in some task T can proceed. The resources will be released immediately T terminates the call to the procedure, for whatever reason. The management of the resource sharing is done using a combination of extra code generated for such resource using procedures, and by the multi-tasking TeleoR evaluator. The result is round-robin fair allocation of resources between tasks, with no task starved of the resources it needs.

As an example, we use the program in the file
qulog/examples/towers/oneArmTowerBuilders.qlg
which is almost identical to the above program.

The first change is to decide which TeleoR procedures can be called to start a task in a multi-tasking context. The procedures so declared are the only ones that can be used as the top-level procedure call of a task. These declarations are used by the TeleoR compiler to generate possible call tree information related to resource use.

In this example we simply change the declaration of make_tower to

The only other change we need to make is to decide the granularity of the interleaving of the use of the arm resource by tasks. We do this by declaring certain procedures as atomic_tel. There is one major constraint on our choice of the atomic procedures - the resource use constraint. Every procedure P that has a robotic action rule, i.e. a rule with one of the actions:

must either be declared an atomic_tel procedure, or in the call graph of the program procedures every path beginning at makeTower must pass through an atomic_tel procedure before it reaches a procedure with robotic action rules.

The maximum interleaving will be achieved by declaring as atomic_tel only those procedures that contain at least one robotic action rule and are the first such procedures on some path of the program call graph starting at makeTower.

Figure 3 shows the call graph of the tower building program. We could satisfy the resource use constraint by declaring makeTower to be atomic_tel. The first task to be launched will acquire the arm resource and will release it only when its tower is completed and makeTower fires its first rule. There will be no interleaving. For maximum interleaving we should declare move_to_block and move_to_table as atomic_tel procedures. Both procedures contain robotic action rules and in the call graph no path from either procedure back to makeTower has procedure with a robotic action rule.

In this example that is all the programmer needs to do. Now we can have multiple tasks running, each building a different tower, with reasonably fair interleaving of their use of the robot arm with every tower eventually built providing there is no persistent outside interference that repeatedly takes apart built towers before all have been built.

It should be noted that the first rule of each atomic procedure has to have the null action as the robotic action. This signals the evaluator that the task can give up the resource even if no parent procedure chooses a different rule when the goal of the atomic task has been achieved.

In this case we have only one resource and so we can think of the atomic tasks as having to grab all resources. In the next example we have multiple resources and tasks might only want to grab a subset of resources. This can lead to tasks running in parallel if they use non-overlapping resource.

The task evaluator maintains a set of running tasks and a queue of waiting tasks together with what resources they are using or want to use. When the task evaluator re-evaluates tasks it first considers the running tasks. If the call stack changes only inside the outermost atomic call (and the first rule is not fired) then the task will continue to run. Otherwise it is added to the end of the wait queue.

Once the running tasks have been processed it considers the waiting tasks in queue order. If the re-evaluation of the first task leads to a call on a atomic procedure and its resources are not being used it becomes a running task. If not it maintains its position in the wait queue possibly waiting on a new set of resources.

The evaluator continues through the remainder of the wait queue and a waiting task T will become running it the required resources do not overlap with any running task, or waiting task that is earlier on the wait queue than T. The second of these requirements provides a degree of fairness.

If you run this program using the simulator you will see that the tasks take turns building their towers. However, if you add extra blocks on top of two of the towers, you will notice that instead of the arm alternating the removing of the extra blocks from each tower, all the extra blocks are first removed from one tower before any is removed from the other. This is because unpile is called from within move_to_table, which is declared to be atomic.

For this reason we have also included
qulog/examples/towers/oneArmTowerBuildersIterUnpile.qlg
that uses an iterative version of unpile and so is not mutually recursive with move_to_table. It therefore produces better interleaving of the tasks when unpiling. In making this change we also added two more rules to makeTower while removing two rules from move_to_block and one from move_to_table. In this program the definition of unpile is

In this version, apart from being iterative, we also use or_while. The reason for this is, when the rule fires, TopBlock will be instantiated to the current top block above Block. When this block is picked up as part of the move to table then, without the or_while the rule will refire with a different instantiation of TopBlock. This will cause the atomic move_to_table to become waiting. Another task will become running, putting this block down. With the or_while the task will complete the block move and only then give up control to another task. If you run this program and a variant with the or_while deleted you will notice by carefully observing the task colours on the arm that this is indeed the case.

Note that, semantically, or_while is different from using a disjunction. Consider the two rules

and where g_or_w(X) is the disjunction of g and w. Now consider a case where the first rule is fired with the instantiation X = v making g(X) true. In order for the second to have the same semantics we would need to call g(X) before w(X). Now imagine that w(v) becomes true and at the same time g(v) becomes false. The first rule will continue but the second rule might, instead, refire if X = v is not the first instantion found that makes w(X) true.