This chapter is from the book
This chapter is from the book
This chapter is from the book
3.5 Joint Actions
So far, this chapter has confined itself mainly to discussions of guarded actions that rely on the state of a single object. Joint action frameworks provide a more general setting to attack more general design problems. From a high-level design perspective, joint actions are atomic guarded methods that involve conditions and actions among multiple, otherwise independent participant objects. They can be described abstractly as atomic methods involving two or more objects:
void jointAction(A a, B b) { // Pseudocode
WHEN (canPerformAction(a, b))
performAction(a, b);
}
Problems taking this general, unconstrained form are encountered in distributed protocol development, databases, and concurrent constraint programming. As seen in 3.5.2, even some ordinary-looking design patterns relying on delegation require this kind of treatment when otherwise independent actions in otherwise independent objects must be coordinated.
Unless you have a special-purpose solution, the first order of business in dealing with joint actions is translating vague intentions or declarative specifications into something you can actually program. Considerations include:
Allocating responsibility. Which object has responsibility for executing the action? One of the participants? All of them? A separate coordinator?
Detecting conditions. How can you tell when the participants are in the right state to perform the action? Do you ask them by invoking accessors? Do they tell you whenever they are in the right state? Do they tell you whenever they might be in the right state?
Programming actions. How are actions in multiple objects arranged? Do they need to be atomic? What if one or more of them fails?
Linking conditions to actions. How do you make sure that the actions occur only under the right conditions? Are false alarms acceptable? Do you need to prevent one or more participants from changing state between testing the condition and performing the action? Do the actions need to be performed when the participants enter the appropriate states, or merely whenever the conditions are noticed to hold? Do you need to prevent multiple objects from attempting to perform the action at the same time?
3.5.1 General Solutions
No small set of solutions addresses all issues across all contexts. But the most widely applicable general approach is to create designs in which participants tell one another when they are (or may be) in appropriate states for a joint action, while at the same time preventing themselves from changing state again until the action is performed.
These designs provide efficient solutions to joint action problems. However, they can be fragile and non- extensible, and can lead to high coupling of participants. They are potentially applicable when you can build special subclasses or versions of each of the participant classes to add particular notifications and actions, and when you can prevent or recover from deadlocks that are otherwise intrinsic in many joint action designs.
The main goal is to define notifications and actions within synchronized code that nests correctly across embedded calls, in a style otherwise reminiscent of double-dispatching and the Visitor pattern (see the Design Patterns book). Very often, good solutions rely on exploiting special properties of participants and their interactions. The combination of direct coupling and the need to exploit any available constraints to avoid liveness failures accounts for the high context dependence of many joint action designs. This in turn can lead to classes with so much special-purpose code that they must be marked as final.
3.5.1.1 Structure
For concreteness, the following descriptions are specific to the two-party case (for classes A and B), but can be generalized to more than two. Here, state changes in either participant can lead to notifications to the other. These notifications can in turn lead to coordinated actions in either or both participants.
Designs can take either of two characteristic forms. Flat versions couple participant objects directly:
)
Explicitly coordinated versions route some or all messages and notifications through a third object (a form of Mediator — see the Design Patterns book) that may also play some role in the associated actions. Coordination through third parties is rarely an absolute necessity, but can add flexibility and can be used to initialize objects and connections:
)
3.5.1.2 Classes and methods
The following generic steps can be applied when constructing the corresponding classes and methods:
-
Define versions (often subclasses) of A and B that maintain references to each other, along with any other values and references needed to check their parts in triggering conditions and/or to perform the associated actions. Alternatively, link participants indirectly with the help of a coordinator class.
-
Write one or more methods that perform the main actions. This can be done by choosing one of the classes to house the main action method, which in turn calls secondary helper methods in the other. Alternatively, the main action can be defined in the coordinator class, in turn calling helper methods in A and B.
-
In both classes, write synchronized methods designed to be called when the other object changes state. For example, in class A, write method Bchanged, and in class B, write Achanged. In each, write code to check if the host object is also in the correct state. If the resulting actions involve both participants, they must be performed without losing either synchronization lock.
-
In both classes, arrange that the other's changed method is called upon any change that may trigger the action. When necessary, ensure that the state-change code that leads to the notification is appropriately synchronized, guaranteeing that the entire check-and-act sequence is performed before breaking the locks held on both of the participants at the onset of the change.
-
Ensure that connections and states are initialized before instances of A and B are allowed to receive messages that result in interactions. This can be arranged most easily via a coordinator class.
These steps are almost always somehow simplified or combined by exploiting available situation-dependent constraints. For example, several substeps disappear when notifications and/or actions are always based in only one of the participants. Similarly, if the changed conditions involve simple latching predicates (see 3.4.2), then there is typically no need for synchronization to bridge notifications and actions. And if it is permissible to establish a common lock in the coordinator class and use it for all methods in classes A and B (see 2.4.5), you can remove all other synchronization, and then treat this as a disguised form of a single-object concurrency control problem, using techniques from 3.2- 3.4.
3.5.1.3 Liveness
When all notifications and actions are symmetrical across participants, the above steps normally yield designs that have the potential for deadlock. A sequence starting with an action issuing Achanged can deadlock against one issuing Bchanged. While there is no universal solution, conflict-resolution strategies for addressing deadlock problems include the following approaches. Some of these remedies require extensive reworking and iterative refinement.
Forcing directionality. For example, requiring that all changes occur via one of the participants. This is possible only if you are allowed to change the interfaces of the participants.
Precedence. For example, using resource ordering (see 2.2.6) to avoid conflicting sequences.
Back-offs. For example, ignoring an update obligation if one is already in progress. As illustrated in the example below, update contention can often be simply detected and safely ignored. In other cases, detection may require the use of utility classes supporting time- outs, and semantics may require that a participant retry the update upon failure.
Token passing. For example, enabling action only by a participant that holds a certain resource, controlled via ownership-transfer protocols (see 2.3.4).
Weakening semantics. For example, loosening atomicity guarantees when they turn out not to impact broader functionality (see 3.5.2).
Explicit scheduling. For example, representing and managing activities as tasks, as described in 4.3.4.
3.5.1.4 Example
To illustrate some common techniques, consider a service that automatically transfers money from a savings account to a checking account whenever the checking balance falls below some threshold, but only if the savings account is not overdrawn. This operation can be expressed as a pseudocode joint action:
void autoTransfer(BankAccount checking, // Pseudocode
BankAccount savings,
long threshold,
long maxTransfer) {
WHEN (checking.balance() < threshold &&
savings.balance() >= 0) {
long amount = savings.balance();
if (amount > maxTransfer) amount = maxTransfer;
savings.withdraw(amount);
checking.deposit(amount);
}
}
We'll base a solution on a simple BankAccount class:
class BankAccount {
protected long balance = 0;
public synchronized long balance() {
return balance;
}
public synchronized void deposit(long amount)
throws InsufficientFunds {
if (balance + amount < 0)
throw new InsufficientFunds();
else
balance += amount;
}
public void withdraw(long amount) throws InsufficientFunds {
deposit(-amount);
}
}
Here are some observations that lead to a solution:
There is no compelling reason to add an explicit coordinator class. The required interactions can be defined in special subclasses of BankAccount.
The action can be performed if the checking balance decreases or the savings balance increases. The only operation that causes either one to change is deposit (since withdraw is here defined to call deposit), so versions of this method in each class initiate all transfers.
Only a checking account needs to know about the threshold, and only a savings account needs to know about the maxTransfer amount. (Other reasonable factorings would lead to slightly different implementations.)
On the savings side, the condition check and action code can be rolled together by defining the single method transferOut to return zero if there is nothing to transfer, and otherwise to deduct and return the amount.
On the checking side, a single method tryTransfer can be used to handle both checking-initiated and savings-initiated changes.
Without further care, the resulting code would be deadlock-prone. This problem is intrinsic in symmetrical joint actions in which changes in either object could lead to an action. Here, both a savings account and a checking account can start their deposit sequences at the same time. We need a way to break the cycle that could lead to both being blocked while trying to invoke each other's methods. (Note that deadlock would never occur if we require only that the action take place when checking balances decrease. This would in turn lead to a simpler solution all around.)
For illustration, potential deadlock is addressed here in a common (although of course not universally applicable) fashion, via a simple untimed back-off protocol. The tryTransfer method uses a boolean utility class supporting a testAndSet method that atomically sets its value to true and reports its previous value. (Alternatively, the attempt method of a Mutex could be used here.)
class TSBoolean {
private boolean value = false;
// set to true; return old value
public synchronized boolean testAndSet() {
boolean oldValue = value;
value = true;
return oldValue;
}
public synchronized void clear() {
value = false;
}
}
An instance of this class is used to control entry into the synchronized part of the main checking-side method tryTransfer, which is the potential deadlock point in this design. If another transfer is attempted by a savings account while one is executing (always, in this case, one that is initiated by the checking account), then it is just ignored without deadlocking. This is acceptable here since the executing tryTransfer and transferOut operations are based on the most recently updated savings balance anyway.
All this leads to the following very special subclasses of BankAccount, tuned to work only in their given context. Both classes rely upon an (unshown) initialization process to establish interconnections.
The decision on whether to mark the classes as final is a close call. However, there is just enough latitude for minor variation in the methods and protocols not to preclude knowledgeable subclass authors from, say, modifying the transfer conditions in shouldTry or the amount to transfer in transferOut.
class ATCheckingAccount extends BankAccount {
protected ATSavingsAccount savings;
protected long threshold;
protected TSBoolean transferInProgress = new TSBoolean();
public ATCheckingAccount(long t) { threshold = t; }
// called only upon initialization
synchronized void initSavings(ATSavingsAccount s) {
savings = s;
}
protected boolean shouldTry() { return balance < threshold; }
void tryTransfer() { // called internally or from savings
if (!transferInProgress.testAndSet()) { // if not busy ...
try {
synchronized(this) {
if (shouldTry()) balance += savings.transferOut();
}
}
finally { transferInProgress.clear(); }
}
}
public synchronized void deposit(long amount)
throws InsufficientFunds {
if (balance + amount < 0)
throw new InsufficientFunds();
else {
balance += amount;
tryTransfer();
}
}
}
class ATSavingsAccount extends BankAccount {
protected ATCheckingAccount checking;
protected long maxTransfer;
public ATSavingsAccount(long max) {
maxTransfer = max;
}
// called only upon initialization
synchronized void initChecking(ATCheckingAccount c) {
checking = c;
}
synchronized long transferOut() { // called only from checking
long amount = balance;
if (amount > maxTransfer)
amount = maxTransfer;
if (amount >= 0)
balance -= amount;
return amount;
}
public synchronized void deposit(long amount)
throws InsufficientFunds {
if (balance + amount < 0)
throw new InsufficientFunds();
else {
balance += amount;
checking.tryTransfer();
}
}
}
3.5.2 Decoupling Observers
The best way to avoid the design and implementation issues surrounding full joint-action designs is not to insist that operations spanning multiple independent objects be atomic in the first place. Full atomicity is rarely necessary, and can introduce additional downstream design problems that impede use and reuse of classes.
To illustrate, consider the Observer pattern from the Design Patterns book:
)
In the Observer pattern, Subjects (sometimes called Observables) represent the state of whatever they are modeling (for example a Temperature) and have operations to reveal and change this state. Observers somehow display or otherwise use the state represented by Subjects (for example by drawing different styles of Thermometers). When a Subject's state is changed, it merely informs its Observers that it has changed. Observers are then responsible for probing Subjects to determine the nature of the changes via callbacks checking whether, for example, Subject representations need to be re-displayed on a screen.
)
The Observer pattern is seen in some GUI frameworks, publish-subscribe systems, and constraint-based programs. A version is defined in classes java.util.Observable and java.util.Observer, but they are not as of this writing used in AWT or Swing (see 4.1.4).
It is all too easy to code an Observer design as a synchronized joint action by mistake, without noticing the resulting potential liveness problems. For example, if all methods in both classes are declared as synchronized and Observer.changed can ever be called from outside of the Subject.changeValue method, then it would be possible for these calls to deadlock:
)
This problem could be solved by one of the techniques discussed in 3.5.1. However, it is easier and better just to avoid it. There is no reason to synchronize operations surrounding change notifications unless you really need Observer actions to occur atomically in conjunction with any change in the Subject. In fact, this requirement would defeat most of the reasons for using the Observer pattern in the first place.
Instead, here you can apply our default rules from 1.1.1.1 and release unnecessary locks when making calls from Subjects to Observers, which serves to implement the desired decoupling. This permits scenarios in which a Subject changes state more than once before the change is noticed by an Observer, as well as scenarios in which the Observer doesn't notice any change when invoking getValue. Normally, these semantic weakenings are perfectly acceptable and even desirable.
Here is a sample implementation in which Subject just uses a double as an example of modeled state. It uses the CopyOnWriteArrayList class described in 2.4.4 to maintain its observers list. This avoids any need for locking during traversal, which helps satisfy the design goals. For simplicity of illustration, Observer here is defined as a concrete class (rather than as an interface with multiple implementations) and can deal with only a single Subject.
class Subject {
protected double val = 0.0; // modeled state
protected final CopyOnWriteArrayList observers =
new CopyOnWriteArrayList();
public synchronized double getValue() { return val; }
protected synchronized void setValue(double d) { val = d; }
public void attach(Observer o) { observers.add(o); }
public void detach(Observer o) { observers.remove(o); }
public void changeValue(double newstate) {
setValue(newstate);
for (Iterator it = observers.iterator(); it.hasNext();)
((Observer)(it.next())).changed(this);
}
}
class Observer {
protected double cachedState; // last known state
protected final Subject subj; // only one allowed here
public Observer(Subject s) {
subj = s;
cachedState = s.getValue();
display();
}
public synchronized void changed(Subject s){
if (s != subj) return; // only one subject
double oldState = cachedState;
cachedState = subj.getValue(); // probe
if (oldState != cachedState)
display();
}
protected void display() {
// somehow display subject state; for example just:
System.out.println(cachedState);
}
}
3.5.3 Further Readings
Joint actions serve as a unifying framework for characterizing multiparty actions in the DisCo modeling and specification language:
Jarvinen, Hannu-Matti, Reino Kurki- Suonio, Markku Sakkinnen and Kari Systa. “Object-Oriented Specification of Reactive Systems”, Proceedings, 1990 International Conference on Software Engineering, IEEE, 1990.
They are further pursued in a slightly different context in IP, which also addresses different senses of fairness that may apply to joint action designs. For example, designs for some problems avoid conspiracies among some participants to starve out others. See:
Francez, Nissim, and Ira Forman. Interacting Processes, ACM Press, 1996.
For a wide-ranging survey of other approaches to task coordination among objects and processes, see:
Malone, Thomas, and Kevin Crowston. “The Interdisciplinary Study of Coordination”, ACM Computing Surveys, March 1994.
Joint action frameworks can provide the basis for implementing the internal mechanisms supporting distributed protocols. For some forward-looking presentations and analyses of protocols among concurrent and distributed objects, see:
Rosenschein, Jeffrey, and Gilad Zlotkin. Rules of Encounter: Designing Conventions for Automated Negotiation Among Computers, MIT Press, 1994.
Fagin, Ronald, Joseph Halpern, Yoram Moses, and Moshe Vardi. Reasoning about Knowledge, MIT Press, 1995.
A joint action framework that accommodates failures among participants is described in:
Stroud, Robert, and Avelino Zorzo. “A Distributed Object-Oriented Framework for Dependable Multiparty Interactions”, Proceedings of OOPSLA, ACM, 1999.