Timing dependencies specify constraints on the relative timing of two or more activities. The most widely used members of this dependency family are prerequisite dependencies (A must complete before B starts) and mutual exclusion dependencies (A and B cannot overlap).
Timing dependencies are used in software systems for two purposes:
To specify implicit resource relationships
To specify cooperation relationships among activities that share some resources
Specify Implicit Resource Relationships Implicit resource relationships arise in situations where parts of a resource flow coordination protocol have been hard-coded inside a set of components. Other parts of the protocol might be missing, and explicit coordination might be needed to manage the missing parts only. One example is a set of components for accessing a database. Each of the components contains all the functionality needed in order to access the database built into its code. The name of the database is also embedded in the components and does not appear in their interface. However, none of the components contains any support for sharing the database with other activities. In applications that require concurrent access of the database by all components, designers need to specify and manage an external mutual exclusion dependency among the components.
|
Relation |
Symmetric relation |
Pictorial example |
|---|---|---|
|
X before Y |
XXX YYY |
|
|
X equal Y |
XXX YYY |
|
|
X meets Y |
XXXYYY |
|
|
X overlaps Y |
XXX YYY |
|
|
X during Y |
X equal Y |
YYYYYY XXX |
|
X starts Y |
X, Y simstart |
XXX YYYYY |
|
X finishes |
Y X, Y simend |
XXX YYYY |
Specify Cooperation Relationships Flow dependencies assume that different users of a resource are independent from one another. In many applications, however, users of a resource are cooperating in application-specific ways. Section 10.3 describes an example of such patterns of cooperation. In those cases designers must specify additional dependencies that describe the cooperation among the users. Some of those dependencies could be other resource dependencies. Other could be timing dependencies.
To derive a useful family of timing dependencies we have used the following approach, based on Allen's (1984) taxonomy of time interval relationships. Allen has enumerated all possible relationships between two time intervals (table 10.4). An occurrence of a software activity can be represented by a time interval: [Begin_time, End_time]. Timing dependencies express constraints among activity occurrences. These constraints can be expressed by equivalent constraints between time intervals. Constraints can either require or forbid that a given time interval relationship hold. By enumerating ''required''and ''forbidden''constraints for each of Allen's time interval relationships, we get a list of potentially interesting elementary timing dependencies (table 10.5). These dependencies can be combined to define additional, composite timing relationships. Finally, the resulting set of dependencies can be organized in a specialization hierarchy, as shown in figure 10.18.
|
Allen's relation |
''Relation required'' dependency |
''Relation forbidden'' dependency |
Comments |
|---|---|---|---|
|
X before Y |
X prerequisite Y |
X prevents Y | |
|
X equal Y |
Can be expressed as a composite pattern: X, Y simstart AND X, Y simend |
||
|
X meets Y |
X meets Y |
Special case of prerequisite |
|
|
X overlaps Y |
X overlaps Y |
X, Y mutex | |
|
X during Y |
X during Y |
X, Y mutex |
During can be expressed as a composite pattern: X overlaps Y AND Y finishes X |
|
X starts Y |
X starts Y | ||
|
X, Y simstart |
X, Y simstart | ||
|
X finishes Y |
X finishes Y | ||
|
X, Y simend |
X, Y simend |
Figure 10.18: Specialization relationships among timing dependencies
The following paragraphs describe each of the dependencies shown in figure 10.18. For each dependency type, we describe:
The timing constraint it specifies
The dependency design dimensions
The principal ways to manage it
Some situations where it might be useful
|
Description |
Mutual exclusion dependencies among a set of activities limit the total number of activities of the set that can be executing at any one time |
|
Design dimensions |
Degree of concurrency (maximum number of concurrently executing activities) |
|
Coordination |
processes See Raynal (1986) |
|
Typical use |
Mutual exclusion dependencies typically arise among competing users who share resources with limited concurrency |
|
Description |
Prerequisite dependencies specify that an activity X must complete execution before another activity Y begins execution |
|
Design dimensions |
See section 10.6.3 |
|
Coordination processes |
See section 10.6.3 |
|
Typical use |
Prerequisites arise in two general situations:
Between producers and consumers of some resource. A resource must be produced before it can be consumed.
As a special way of managing mutual exclusion dependencies. Mutual exclusion relationships can be managed by ensuring that the activities involved occur in a statically defined sequential order. The ordering can be specified by defining appropriate prerequisite relationships.
|
|
Description |
Prevention dependencies specify that the occurrence of an activity X prevents further occurrences of another activity Y |
|
Design dimensions |
In permanent prevention dependencies, an occurrence of X prevents all further occurrences of Y
In temporary prevention dependencies, occurrence of a third activity Z re-enables occurrences of Y
|
|
Coordination |
processes Prevention relationships are closely related to perishable prerequisites (see section 10.6.3). As shown in figure 10.19, every prevention dependency can be mapped to an equivalent perishable prerequisite. |
|
Typical use |
Prevention relationships often arise among competing activities that share some resource, where one of the competing activities X has higher priority, and thus the power to restrict access to (prevent) other competing activities Y |
Figure 10.19: Relationships between prevention and perishable prerequisite dependencies
|
Description |
Overlap dependencies specify that an activity Y can only begin execution if another activity X is already executing |
|
Design dimensions |
None |
|
Coordination processes |
This dependency can be managed in two different ways:
Proactively scheduling Y when X starts execution. This is equivalent to decomposing X overlaps Y to Y starts X with specified delay.
Waiting for X to begin execution before allowing Y to start. This is equivalent to defining a perishable prerequisite (enabled by initiation of X, invalidated by completion of X ) between Y and X.
|
|
Typical use |
Overlap relationships typically imply resource relationships between Y and X. In most cases, during its execution Y produces some resource or state required by X. Overlap dependencies occur most frequently as components of During dependencies. |
|
Description |
During dependencies specify that an activity X can only execute during the execution of another activity Y |
|
Design dimensions |
None |
|
Coordination processes |
This dependency is a composite pattern of the following two dependencies:
X overlaps Y,so X can begin execution only if Y is already executing.
Y finishes X. Termination of Y also terminates X.
It can be managed by composing processes for managing its two component dependencies. |
|
Typical use |
During dependencies imply that X uses some resource or state generated during Y 's execution. For example, a network client can only execute successfully during execution of the system's network driver. |
|
Description |
Starts dependencies specify that an activity Y must start execution whenever X starts execution |
|
Design dimensions |
Minimum or maximum delay between initiation of the two activities |
|
Coordination processes |
Combinations of direct control flow and scheduling can be used to manage this dependency |
|
Typical use |
This dependency is often used to describe application-specific patterns of cooperative resource usage or implicit resource dependencies. For example, when starting a word processor program, the printer driver is often initialized as well, in anticipation to the word processor's need for its services. |
|
Description |
Simultaneity dependencies specify that all activities in a set must start execution at the same time |
|
Design dimensions |
Minimum and maximum tolerances between the actual time each activity in the specified set begins execution |
|
Coordination processes |
Simultaneity dependencies can be transformed into many-to-many prerequisite dependencies and managed as such (see figure 10.20) |
|
Typical use |
Simultaneity dependencies are most often used to describe patterns of cooperative resource or mutual resource dependencies |
Figure 10.20: A simultaneity dependency can be transformed and managed as a composite prerequisite. Before activities X and Y can begin execution, all four prerequisite activites must occur. Then both X and Y can occur together.
Figure 10.21: Termination of the user-interface also requires termination of the database and graphics servers
|
Description |
Finishes dependencies specify that completion of an activity X also causes activity Y to terminate execution |
|
Design dimensions |
Minimum or maximum delay between completion of X and termination of Y |
|
Coordination processes |
Termination of the process that executes Y using machine-specific system primitives |
|
Typical use |
This dependency is most often used to specify application termination relationships (figure 10.21) |
|
Description |
Simultaneous end dependencies specify that all activities in a set must terminate if any of them completes execution |
|
Design dimensions |
Minimum or maximum tolerances between the actual time each member of the specified set terminates |
|
Coordination processes |
Centralized. Each activity in the set sends a signal to a monitor process upon termination. The monitor process terminates all other activities in the set.
Decentralized. Terminating activities generate an event. All participant activities periodically check for that event and terminate themselves if they detect it.
|
|
Typical use Speculative concurrency. |
Multiple worker activities are jointly or independently working on a problem. All of them terminate if at least one of them arrives at a solution. |