13.2 Associations Involving Competition

13.2.1 Competition in the Domain

For some associations, linking objects involves competition for resources. In the online bookstore, customers do not have to compete with one another to place an order; the store can accept as many orders as it likes.^[1] Similarly, the association between publishers and products is not competitive; there is a seemingly unending supply of new books (about UML?), and any publisher's desire to publish a book can be satisfied.

^[1] We have purposely ignored the problem of limited stock and back ordering. All the mechanisms necessary to build those models are covered in this section.

In contrast, consider how shipping clerks select shipments to pack. The Shipping Clerk statechart diagram shown previously in Figure 12.12 on page 210 works correctly if there is a single shipping clerk. When the clerk finishes one shipment, he looks for another shipment that is waiting to be packed. If he finds one, he selects that shipment and begins packing it.

If there are several shipping clerks, this simple approach will not work. Because shipping clerks operate concurrently, several shipping clerks could try to pack and ship the same shipment at the same time. Specifically, and you can try this scenario yourself, if two clerks finish at the same time (i.e., two Clerk objects transition to state 1 simultaneously, as shown in Figure 12.12), both will see the same shipment in state 1 and start packing that same order. Figure 13.5 is a sequence diagram illustrating this scenario. Absent any control mechanism, there would be a fight between shipping clerks for shipments to pack.^[2]

^[2] Yeah, right.

Figure 13.5. Sequence Diagram Illustrating Contention for the Same Order

Having the shipments select a shipping clerk does not solve the problem. The shipments behave concurrently too, and they could also compete for shipping clerks.

13.2.2 Competition in the Models

We address contention problems of this sort by providing a single control point that serializes competing requests. In the real world, this serialization can be enforced by a variety of mechanisms: a line of customers (a manifestation of a policy requiring that customers be served in order of their arrival) or a person who assigns shipments to shipping clerks based on some other policy, such as the size of the order or the priority status of the associated customer.

In Executable UML, the serialization required to manage competition is accomplished by a single state machine for one of the participants in the competition: an assigner.

Definition: An assigner is a state machine that serves as a single point of control for creating links on competitive associations.

An assigner resolves contention by selecting and assigning objects for the task at hand. Assigners are typically class-based state machines, though as we shall see, in some cases contention can be managed by an instance-based state machine. A class-based state machine has only one instance, thereby providing the crucial single point of control needed for creating instances of competitive associations.

Just as you may build zero or one instance-based state machine for each class, you may build zero or one class-based state machines for each class.

To model the competition for the shipping clerk, for example, there will be two state machines, one that applies for each shipping clerk object, and one that coordinates all shipping clerks. If, at some time, there are six shipping clerks, then there will be seven state machine instances executing, one for each of the six shipping clerks and one for the shipping clerk class. The shipping clerk and shipment assignment is used as an example used below.

13.2.3 An Example

Figure 13.6 shows a fairly common form of assigner. This statechart diagram has two waiting states (states 1 and 2) that correspond to waiting for a shipment ready to be packed, and waiting for an idle shipping clerk. (Executable UML models do not have direct access to the states of the state machines, except in the synchronous create operation.) To know when the two objects are ready, we have added a boolean attribute waitingToBePacked to the Shipment class and a corresponding boolean attribute idle to the Shipping Clerk.

Figure 13.6. Shipping Clerk Assigner

The third state is where the actual association takes place. Only when there is a shipment waiting to be packed and a shipping clerk available to pack it do we enter this third state. According to some policy, the actions select an idle shipping clerk and a shipment waiting to be packed, establish the association, and update the state attributes of the participating classes synchronously so as to avoid reselecting the same object before the idle shipping clerk starts packing.

To understand the operation of the assigner more fully, examine the sequence diagram in Figure 13.7.

Figure 13.7. Sequence Diagram Showing an Assigner Managing Competition

Assume the assigner starts in state 1, Waiting for a Shipment, and that the procedure has already been executed. When a shipment is ready to be packed, it requests a shipping clerk by generating the signal shipmentReadyToPack. The shipment assigner receives this signal and transitions to state 2, Waiting for a Free Clerk.

On arrival in state 2, the assigner executes the procedure. An action determines if there is a free shipping clerk by reading the value of the idle attribute for all clerks. If there is an idle clerk (attribute Clerk.idle true), an action generates a signal clerkFree to itself to cause transition to the third state where the association is made.

Should there be no idle clerks, the assigner waits until it receives an occurrence of clerkFree (the same signal specification), from a shipping clerk recently become idle. This is how the assigner handles both assigning a shipping clerk immediately when one is already idle, and assigning a shipping clerk when one becomes available. Note the similarity to the situation described in Section 12.2.2: Saving Signals in Data: It is the same.

Once the association between the shipping clerk and the shipment is made in state 3, Assigning Clerk to Shipment, the assigner generates a clerkAssigned signal to the selected shipping clerk to go about his business (it could as easily have been the shipment one of the two has to take charge), and the assigner generates a signal to itself to make a transition into state 1: Waiting for a Shipment. The procedure in this state mirrors the behavior of the procedure in state 2: If there is a shipment waitingToBePacked, an action generates a signal to itself to cause transition into the next state, and if not, the state machine waits for a shipment to generate a signal to indicate its readiness to be packed.

The state machine ignores shipmentReady signals while in states 2 and 3, and clerkIdle signals while in states 3 and 1. In both cases, there is a trace of the signal stored as an attribute value in the sending objects, again just as in Section 12.2.2: Saving Signals in Data.

13.2.4 Multi-Instance Contention

Figure 13.8 shows an expanded business with several warehouses, where each warehouse services orders for customers who live nearby.

Figure 13.8. Class Diagram Including Warehouse Associations

Obviously enough, we cannot assign any arbitrary shipping clerk to pack a shipment. Instead, we have to assign a shipment to a shipping clerk who works in the right warehouse.

If we created a single assigner to handle all assignments, we'd have the added burden of checking to see whether any ready shipments were at warehouses with idle clerks. A simpler approach is to have one state machine instance per warehouse that manages the assignment.

In this case, we build the contention handling into the warehouse class. There is one state machine per warehouse and the warehouse state machine selects shipping clerks but only from those shipping clerks assigned to the warehouse. This approach works because the instances of the shipping clerks are partitioned by warehouse, so multiple warehouses cannot compete for the same shipping clerk. The statechart diagram for the warehouse is shown in Figure 13.9.

Figure 13.9. Statechart Diagram for Warehouse Managing Contention

This statechart diagram replaces the single-instance assigner in the previous section. It is almost identical to the Shipping Clerk assigner, except the selection criteria in each state include a "related by" clause to select only shipments and clerks related to the warehouse.

If the warehouse had interesting behavior of its own (pretty unlikely in this example), the contention handling could be moved to an association class between the shipping clerk and the warehouse.

13.2.5 Object Selection and Selection Policies

An assigner and its state procedures realize the selection criteria for the associated objects. There is always a policy at work. It could be as simple as selecting an arbitrary object (the shipment shipping clerk example) or it could be arbitrarily complex. We could, for example, depending on expected quarterly results for the company, choose to ship high-value shipments as soon as possible, or delay them until the beginning of the next quarter. Likewise, we could assign work to clerks in a way that balances the number of shipping jobs processed by each clerk in a shift.

When there is a policy to be followed, the models must have classes and attributes to support the policy; their number and complexity depends entirely on the policy. In all cases, the policy will be localized in the procedure for the state that relates the objects.

The policy supported by an assigner may result in a state machine that is more complex than the three-state form presented so far. Leon Starr's elevator example [1], and the complete online bookstore case study provide additional examples of assigners.