We have completed the review of the basic communication and synchronization policy. For more flexibility, it is useful to define a few mechanisms that will allow interrupting the normal processing in some cases.
Because these facilities are add-ons intended for convenience, rather than a part of the basic concurrency model, they are available not as language constructs but as library features. We will assume a class CONCURRENCY, which classes needing these special mechanisms can inherit. A similar approach has already been used twice in this book:
The ABCL/1 concurrent language introduced the notion of "express message" for when we want to let a supplier object serve a certain VIP client immediately, even though the supplier may be busy with another client.
In some approaches an express message will just interrupt the normal message, get serviced, and then let the normal message be resumed. But this is unacceptable, as we saw earlier in this chapter ("Concurrent accesses to an object", page 952) when we found out that at most one execution should be active on any object at any given time: the express message, like any exported feature, needs an initial state satisfying the invariant; but who knows in what state the interrupted routine will be when it is forced to yield to the express message? And who knows what state the express message will produce as a result? All this opens the way to what the discussion of static binding called "one of the worst events that could occur during the execution of a software system": producing an inconsistent object. As we saw then: "if such a situation can arise, we can no longer hope to predict what execution will do".
This does not mean, however, that we should reject the notion of express message altogether. We may indeed need to interrupt a client --- either because we have something more important to do with the object it has reserved, or because it is overextending its welcome to retain it. But such an interruption is not a polite request to step aside for a while. It is murder, at least attempted murder. To take our rival's place we shoot at it, so that it will die unless it can recover in the hospital. In software terms, the interrupting client must cause an exception in its rival, which will either retry (the hospital) or fail.
Such behavior, however, assumes that the challenger is somehow stronger than the holder. If not, the one that will get an exception is the challenger.
The almost inescapable metaphor suggests that instead of the "express message" terminology we talk about the attempt to snatch a shared object from its current holder as a duel (the result, in an earlier era, of trying to snatch away someone's legitimate spouse). An object has executed the instruction
where b is separate. After possibly waiting for the object of its desires, b, to become free, and for separate precondition clauses to hold, it has captured b, becoming its current holder. The execution of r on b has started on behalf of the holder, but is not finished. Another separate object, the challenger, executes
where c, also separate, is attached to the same object as the holder's b. Normally, the challenger will wait until the call to r is over. What if the challenger is impatient?
Through procedures in class CONCURRENCY we can provide the necessary flexibility. On the holder's side we have yield, which means: "I am willing to release my hold if someone more worthy comes along". Most holders, of course, are not so accommodating: unless it makes an explicit call to yield, a holder will retain its hold. To return to this default behavior, you may use the procedure retain.
On the challenger's side we can use two kinds of request to get special treatment:
To return to the default behavior of waiting for the holder to finish, use wait_turn.
A call to one of these CONCURRENCY procedures will retain its effect until another supersedes it. Note that the two sets of facilities are not exclusive; for example a challenger could use both insist to request special treatment and yield to accept being interrupted by another. A priority scheme can be added, so that challengers will only defer to others with higher priorities, but we can ignore this refinement here.
The following table shows the result of a duel --- a conflict between a holder and a challenger --- in all possible cases. The default options and behavior, in the absence of any call to CONCURRENCY procedures, are underlined.
------------------------------------------------------------------ Challenger → wait_turn(fig) demand insist ↓ Holder retain Challenger waits Exception in Challenger waits challenger yield Challenger waits Exception in Exception in holder; holder; challenger gets challenger gets object. object. ------------------------------------------------------------------
As you will remember, every kind of exception has a code, accessible through class EXCEPTIONS. To distinguish an exception caused by one of the situations appearing in the above table, EXCEPTIONS provides the boolean query is_concurrency_interrupt.
Here is an example using duels. Assume a certain controller object has started off a number of partner objects, and then proceeds with its own work, which needs a certain resource shared. But the other objects may need access to the shared resource, and the controller is willing to interrupt its current task to let any of them proceed; when the partner is done, the controller resumes the last interrupted task.
This general description covers for example the case of an operating system kernel (the controller) which starts off input-output processors (the partners), but does not wait for an I/O operation to complete, since I/O is typically several orders of magnitude slower than computation. When an I/O operation terminates, its processor can interrupt the kernel to request attention. This is the traditional interrupt-driven scheme for handling I/O --- and the problem which gave the original impetus, many years ago, to the study of concurrency.
The general scheme may be called the Secretary-Receptionist Algorithm by analogy with what you find in many organizations: a receptionist sits near the entrance to greet, register and direct visitors, but this is not a full-time job; the receptionist is also entrusted with some other work, usually secretarial. When a visitor shows up, the receptionist interrupts his work, takes care of the visitor, and then goes back to the interrupted task.
Restarting a task after it has been started and interrupted may require some cleanup; this is why the following procedure passes to operate the value of interrupted, which will enable it to find out whether the current task has already been attempted. The first argument of operate, here next, identifies the task to perform. The procedure is assumed to be part of a class that inherits from both CONCURRENCY (for yield and retain) and EXCEPTIONS (for is_concurrency_interrupt). Procedure operate could take a long time to execute, and so is the interruptible part.
execute_interruptibly is -- Perform own set of actions, but take interrupts -- (the Secretary-Receptionist Algorithm). local done, next: INTEGER; interrupted: BOOLEAN do from done := 0 until termination_criterion loop if interrupted then process_interruption (shared); interrupted := False else next := done + 1; yield; operate (next, shared, interrupted); -- This is the interruptible part. retain; done := next end end rescue if is_concurrency_interrupt then interrupted := True; retry end end
Some of the steps performed by the controller may actually have been requested by one of the interrupting partners. In an I/O interrupt, for example, the I/O processor will signal the end of an operation and (in the input case) the availability of the data just read. The interrupting partner may use the object shared to deposit that information; to interrupt the controller, it will execute
insist; interrupt (shared); wait_turn -- Request controller's attention, interrupting it if necessary. -- Deposit any needed information into the object shared.
This is the reason why process_interruption, like operate, uses shared as argument: it may have to analyze the shared object to detect information passed by the interrupting partner. This will enable it, if necessary, to set up one of its upcoming tasks, to be executed on behalf of that partner. Note that process_interruption, unlike operate, is not interruptible; any other partner that becomes ready while it is executing will have to wait (otherwise some partner requests might get lost). So process_interruption should only perform simple operations --- registering information for future processing. If that is not possible, you may use a slightly different scheme in which process_interruption relies on a separate object other than shared.
We have one more precaution to take. Although partner's requests can be processed later (through calls to operate in upcoming steps), it is essential that none of these requests can be lost. With the scheme as given, after a partner could execute an interrupt, another one could do the same, overriding the information deposited by the first, before the controller has had the time to register that information by executing process_interruption. This is not acceptable. To avoid this, it suffices to add to the generating class of shared a boolean attribute deposited with the associated setting and resetting procedures. Then interrupt will have the precondition not shared.deposited, so as to wait until the previous partner has been registered, and will execute shared.set_deposited before returning; process_interruption will execute shared.set_not_deposited before exiting.
The partners are initialized by "business card" calls of the form createI> partner.make (shared, ...) which pass them a reference to shared to be retained for future needs.
Procedure execute_interruptibly has been spelled out in full, with the application-specific elements represented by calls to routines operate, process_interruption, termination_criterion that are assumed to be separate. This prepares for the procedure's possible inclusion into a coucurrency library.
With the presentation of the duel mechanism we have finished defining the set of necessary concurrency tools.The rest of this chapter provides an extensive set of examples, from diverse application areas, illustrating the use of these tools. After the examples you will find: