Organizing Business Knowledge The Mit Process Handbook [Electronic resources] نسخه متنی

Section 10.7 describes how this generic model can be specialized to manage different special cases of flow dependencies.

In the most general case, flow dependencies exist between a number of resource producers and a number of consumers (figure 10.4). Dependencies are connected to activities through resource producer and consumer ports. Producer and consumer ports are abstract ports (see section 10.6.3). That is, they are composite ports that contain implementation-specific groupings of low-level interface ports that logically participate in the production and consumption of a given resource.

Figure 10.4: Generic model of resource .ow dependencies

We assume that by default, a flow dependency between a set of activities implies a stream of resource flows over the lifetime of an application execution. Coordination processes for managing flow dependencies are designed with this assumption in mind. Situations where resources are produced or consumed only once during the lifetime of an application execution are represented by special types of dependencies.

Our objectives in this section are the following:

Introduce a set of dependency design dimensions that define a flow dependency design space. These dimensions represent the interaction requirements that are significant in choosing a coordination process. Every point in this design space defines a different special case of a flow dependency.

Introduce a set of coordination design dimensions that define a coordination process design space. Every point in this design space will be an alternative implementation of a flow dependency managing process.

Specify how each dependency type restricts the range of possible coordination processes for managing it.

Both design spaces are based on a generic model for decomposing flow dependencies into lower-level dependencies, shown in figure 10.4. Managing a flow dependency implies managing all lower-level dependencies. This model extends the ideas introduced in (Malone 1994) and attempts to capture the different considerations that must be addressed whenever resources are exchanged or shared among different activities.

The generic model for managing flow dependencies focuses on the relationships between producers and users of resources. It assumes that different consumers (producers) are independent from one another and compete for access to resources (consumers).

In the following sections we will first introduce dependency and coordination processes design spaces for each of the lower-level dependencies. The design space for generalized flow dependencies will then be defined by the product of the component dependencies design spaces.

10.6.1 Usability Dependencies

Types of Usability Dependencies Usability dependencies state the simple fact that resource users should be able to properly use produced resources. This is a very general requirement that encompasses compatibility issues such as:

Data type compatibility

Format compatibility

Database schema compatibility

Device driver compatibility

The exact meaning and range of usability considerations varies with each kind of resource. Section 10.7, which describes specializations of flow dependencies for a variety of different resources, also discusses in more detail the meaning of usability dependencies for each of them.

Figure 10.5: Framework for managing usability dependencies

Managing Usability Dependencies One interesting observation resulting from this work is that regardless of the particular usability issue being managed, coordination alternatives for managing usability dependencies can be classified by the following two design dimensions (figure 10.5): (1) who is responsible for ensuring usability and (2) are the usability requirements fixed?

who is responsible for ensuring usability? The following alternatives are possible:

Designer is responsible (no run-time coordination is necessary). Components are specially selected at design time so as to be compatible with one another. This is often achieved by developing applications using standardized components. Examples of standardized component families include OLE objects, OpenDoc components, Visual Basic VBXs, and so on (Adler 1995). The advantages of this approach include run-time effciency and reliability. On the other hand, it limits the choice of components for a particular functional requirement to those explicitly designed for the particular standardized environment.

Producers are responsible for ensuring usability. This implies that the producer knows the format expected by the users, and is able to generate or convert its resources to the user format.

Consumers are responsible for ensuring usability. This requires the consumer to recognize the format of resources it receives, and to be able to convert the format to its own format, if necessary.

Third party ensures usability between producers and consumers. The third party must know and be able to handle both formats.

Both producers and consumers convert to and from an interchange format. The advantage of this approach is that it does not require prior knowledge of the formats produced and expected by producers and users. This is particularly desirable if producers and users are dynamically changing, and each of them is using a different native format. The disadvantage is that two conversions take place, which might be ineffcient if conversions are computationally costly. Producers and users must agree on the interchange format.

ARE USABILITY REQUIREMENTS FIXED? Coordination processes can be further classified depending on whether the producer and consumer formats are fixed and known at design-time, or whether they are negotiated at run-time. In the latter case, the management of usability dependencies might introduce additional flow dependencies to the system that have to be managed in turn.

10.6.2 Accessibility Dependencies

Types of Accessibility Dependencies Accessibility dependencies specify that a resource must be accessible to a user before it can be used. Since users are software activities, accessibility specifies more accurately that a resource must be accessible to the process that executes a user activity before it can be used. Important parameters in specifying accessibility dependencies are the number of producers, the number of users, and the resource kind.

Managing Accessibility Dependencies There are two broad alternatives for making resources accessible to their users (figure 10.6):

Place producers and users ''close together.''

Transport resources from producers to users.

Figure 10.6: Framework for managing accessibility dependencies

Depending on the type of resource being transferred, either or both alternatives might be needed. Placing producer and user activities ''close''to one another generally decreases the cost of transporting the resource. Combinations of placing activities and transporting resources should be considered in situations where the cost of placing the activities is lower than the corresponding gain in the cost of transporting the resource. A discussion of the two alternatives follows.

PLACE PRODUCERS AND USERS ''CLOSE TOGETHER'' This can be done either at design-time, or at run-time:

Place activities at design-time. The ways to manage this step is in decreasing order of effciency:

Package activities together in the same sequential code block. In this case transport of data resources becomes trivial through the use of local variables. However, such a packaging is subject to a large number of restrictions (all activities must be in source code form; they must be written in the same language and must be assigned to the same processor and executable; data resource must be transportable through local variables) and is not always possible.

Package activities in the same executable. Transport of data resources can be done cheaply through global variables.

Assign activities to the same processor. Transport of data resources can be done through shared memory.

Assign activities to neighboring processors. Transport of data resources will require network communication, but this is still potentially cheaper than if producer and users were randomly assigned.

Move activities at run-time. Producers can be moved close to users, and vice versa. In the simplest case, this would imply assigning the producer to the processor where user activities are assigned. In more complicated cases, this step might require physically transferring an activity's code to the target machine.

TRANSPORT RESOURCE FROM PRODUCERS TO USERS This step depends on the kind of resource that is flowing. It is discussed in more detail in section 10.7.

Figure 10.7: Prerequisite dependency

10.6.3 Prerequisite Dependencies

Types of Prerequisite Dependencies A fundamental requirement in every resource flow is that a resource must be produced before it can be used. This is captured by including a prerequisite dependency in the decomposition of every flow dependency.

Prerequisites are relationships between two sets of activities (figure 10.7). In the following discussion we will refer to set A as the precedent set and to set B as the consequent set. As is the case with flow dependencies, prerequisite dependencies in our vocabulary have stream semantics: they assume that precedent and consequent activities might execute multiple times over the lifetime of an application execution. Prerequisite dependencies thus specify constraints on the allowed execution interleavings of precedent and consequent activities.

Prerequisite dependencies occur very frequently in software architectures. They are the most frequently used member of the dependency family we call timing dependencies. Timing dependencies express constraints in the timing of control flow into a set of activities. They are discussed in section 10.8.

Prerequisite dependencies form a family of related sequencing constraints. The most useful members of the prerequisite family are the following:

Persistent prerequisites specify that a single occurrence of activity A is an adequate prerequisite for an infinite number of occurrences of activity B. This requirement arises often in system initialization processes: an initialization activity must be executed once before any number of system use activities can take place.

Perishable prerequisites are a special case of permanent prerequisites. They specify that a single occurrence of activity A is an adequate prerequisite for an indefinite number of occurrences of activity B. However, occurrence of a third activity C invalidates the effect of activity A, which must then be repeated (figure 10.8). Examples of this dependency arise in situations where resources (communication channels, files) are opened and periodically closed. If no activity C is connected to their invalidation port, perishable prerequisite dependencies become identical to persistent prerequisites.

Cumulative prerequisites permit occurrences of activity A and activity B to be interleaved as long as the number of occurrences of activity B is always smaller than or equal to the number of completed occurrences of activity A. This prerequisite arises in asynchronous resource flows with buffering.

Transient prerequisites specify that at least one new occurrence of activity A must precede each new occurrence of activity B. Transient prerequisites satisfy the definition of cumulative prerequisites and can be thought of as a special case of that dependency type. Perishable prerequisites reduce to transient prerequisites (figure 10.8), when B and C are the same activity.

Figure 10.8: Perishable prerequisites

Lockstep prerequisites specify that exactly one occurrence of activity A must precede each occurrence of activity B. They occur in resource flows without buffering, where it must be ensured that every produced element is used before the next one can be produced. Lockstep prerequisites are a special case of transient prerequisites.

The preceding variations of prerequisite relationships can be organized in a specialization hierarchy, as shown in figure 10.9. The implication of prerequisite specialization relationships is that coordination processes for managing a prerequisite relationship can also be used to manage any of its parent relationships in the specialization structure. For example, in order to manage a cumulative prerequisite, in addition to using processes specifically designed for this type of prerequisite, designers can also consider using coordination processes for transient or lockstep prerequisites.

Figure 10.9: Specialization relationships among different prerequisite dependency types

Prerequisite dependencies can be further classified according to:

Number of precedent activities

Number of consequent activities

Relationship (and/or) among the precedent activities

In And-prerequisites, all activities in the precedent set must occur before activities in the consequent set can begin execution. By contrast, in Or-prerequisites, occurrence of at least one activity in the precedent set satisfies the prerequisite requirement.

Managing Prerequisite Dependencies There are four generic processes for managing prerequisite dependencies (figure 10.10): producer push, consumer pull, peer synchronization, and controlled hierarchy.

Figure 10.10: Generic processes for managing prerequisite dependencies

PRODUCER PUSH This process decomposes into a control flow dependency (section 10.7.1). The alternatives for managing it are the same as those of managing the corresponding control flow dependency.

Producer push processes manage lockstep prerequisites. Consequents are invoked once each time the precedents complete execution.

CONSUMER PULL This process family decomposes into a synchronous call pattern of control flow dependencies. The alternatives for managing it are the same as those of managing the corresponding pattern of control flows.

Consumer pull processes manage lockstep prerequisites. Precedents are invoked once before each consequent. Consumer pull organizations can also be used to manage persistent and perishable dependencies: before starting itself, each consequent checks whether the prerequisite condition is valid, and invokes the precedent activities if it is not.

PEER SYNCHRONIZATION Peer synchronization processes can be used to manage all kinds of prerequisites. Figure 10.11 shows their generic form for each kind of one-to-one prerequisite. All processes can be generalized to handle many-to-many prerequisites.

Figure 10.11: Generic processes for managing prerequisite dependencies using peer event synchronization

Peer synchronization processes rely on the generation and detection of shared events in the system. Events can be classified as follows (figure 10.12):

Figure 10.12: Taxonomy and examples of event types

Memoryless events. Such events are only capable of recording binary states (occurred/did not occur). They can be used for managing permanent, perishable, transient, and lockstep prerequisites. Memoryless events can be further distinguished into persistent and transient.

Persistent event protocols keep a record of whether the event has occurred or not. Therefore the detection of the event need not take place at the time of event generation. Transient event protocols do not keep a record of whether an event has occurred. Events are either detected at the time they are generated, or go unnoticed. This requires some extra coordination to make sure that event detection activities have been started before event generation takes place.

Cumulative events. Cumulative events are capable of remembering how many times they have occurred. They are used in the management of cumulative prerequisites. Apart from being resetted, cumulative events can be incremented and decremented.

CONTROLLED HIERARCHY There are three variations on this process:

Third party synchronously calls precedent, then calls consequent.

Third party asynchronously calls precedent, then schedules consequent after suffcient delay.

Third party schedules both precedent and consequent with suffcient relative delay.

Controlled hierarchy processes can be used to manage lockstep prerequisites. Permanent prerequisites can also be managed by this approach by placing the prerequisite code before any other code in the system (e.g., in an initialization module or at the top of the main program). Figure 10.13 summarizes the design dimensions of prerequisite dependencies and coordination processes.

Figure 10.13: Framework for managing prerequisite dependencies

10.6.4 Sharing Dependencies

Types of Sharing Dependencies Sharing arises when more than one activity requires access to the same resource. Sharing dependencies can be specialized using the three dimensions of the resource-in-use framework of section 10.5.4. For each different combination of resource-in-use parameters (e.g., indivisible, consumable, concurrent), a different specialization of sharing dependency can be defined.

Sharing dependencies arise in one-to-many, many-to-one, and many-to-many flow dependencies in two distinct situations:

Resource sharing

User sharing

RESOURCE SHARING Resource sharing considerations arise in one-to-many flow dependencies because more than one activity uses the same resource. Resource users are assumed to be independent. Therefore the sharing coordination requirements depend solely on the sharing properties of the resource. The different possibilities are as follows:

Divisible resources. Resources can be divided among the users.

Consumable resources. The total number of users must be restricted.

Nonconcurrent resources. The number of concurrent users must be restricted.

CONSUMER SHARING Consumer sharing dependencies arise in many-to-one flow dependencies because more than one producers produce for the same consumer activity, viewed as a ''resource.''Consumer ''resources''can be characterized using the resource-in-use framework. The different dimensions are as follows:

Divisibility. Consumer activities either occur or do not occur. Therefore they are considered indivisible resources.

Consumability. Consumability of a consumer activity means that it can occur a limited number of times or, equivalently, that it can accept a limited number of produced resources. This implies the need for coordination in order to select which resources will be accepted. Modeling consumer activities as consumable resources enables many-to-one flow dependencies to be used for modeling race conditions.

Concurrency. Concurrency determines whether multiple instances of a consumer activity can be active at the same time. Some consumer activities are nonconcurrent (e.g., non-reentrant procedures). In that case coordination should be installed to restrict simultaneous execution of more than one activity instances.

Many-to-many flow dependencies contain a combination of both resource-and consumer-sharing dependencies.

Managing Sharing Dependencies The problem of resource sharing has been studied extensively by researchers in various areas and there exists a huge literature of related algorithms and techniques. Our purpose in this section is to take an architectural look at resource sharing techniques, showing how their interfaces can be abstracted to a small number of generic processes, and how they relate to the other components of a resource flow management process in a small, well-defined number of ways.

There are three general techniques for coordinating resource sharing requirements (figure 10.14):

Divide resource

Restrict access to resource

Replicate resource

Figure 10.14: Framework for managing sharing dependencies

DIVIDE RESOURCE This technique applies to divisible resources. It can be represented by a process that uses the entire resource and produces a set of new subresources (figure 10.15). Subresources are considered independent resources and can then flow to each user with no further coordination.

Figure 10.15: Sharing of divisible resources in a .ow dependency

There are two different ways a resource divide can be combined with the rest of a flow coordination process:

Divide resource before transportation (figure 10.15a). This is the most common case. The entire resource is divided at the site of production, and the generated sub-resources are independently transported to their users.

Divide resource after transportation (figure 10.15b). The resource is first transported at each site and a new subresource is extracted locally. Examples of such resources are circulating tokens in which successive users write or reserve data areas.

RESTRICT ACCESS TO RESOURCE This very general technique applies to both consumable and nonconcurrent resources. In both cases the function of the coordination process is to restrict the flow of control into activities accessing the resource (figure 10.16). More specifically:

For consumable resources, the process restricts the total number of resource accesses.

For nonconcurrent resources, the process limits the total number of concurrent resource accesses. The most common case is when only one concurrent access can be allowed. Then resource sharing becomes equal to a mutual exclusion dependency (Raynal 1986).

Figure 10.16: Sharing by restricting access to resource

From an architectural perspective, there are three different ways an access restriction process can be integrated with the rest of a flow coordination process:

Restrict consumer activity execution (figure 10.16a). This method is used when a resource is accessible to all consumers (e.g., a fixed hardware resource), or when each consumer is using a local protocol to restrict access.

Restrict resource accessibility (figure 10.16b). This method prevents the resource from being transported to consumers until they are allowed to use it. It has effciency advantages in situations where resource transportation is costly (e.g., for large files), and only a subset of the candidate consumers is allowed to use the resource.

Restrict resource production (figure 10.16c). This alternative should be considered when managing user-sharing dependencies. In situations where only a subset of the produced resources is ever used, it might be more effcient to not produce unless usage has been guaranteed.

REPLICATE RESOURCE Resource replication is a technique that jointly manages accessibility and resource sharing dependencies. Its more general architectural form is similar to that of a resource division process. However, it applies to indivisible resources.

COMBINATIONS OF DIVISION AND RESTRICTION The previous techniques can be combined to handle more complex resource sharing requirements. For example, in order to share a resource that is nonconcurrent and finitely divisible among a potentially infinite number of users a combination of division and access restriction can be used. Whenever an access is desired, extraction of a new subresource is first attempted. If that fails, time sharing is used. This algorithm, for example, manages the sharing of finite capacity buffered input/output channels among a potentially infinite number of user processes.

10.6.5 Putting It All Together — Flow Dependencies

The design dimensions of generalized resource dependencies are the sum of the design dimensions of their component dependencies (figure 10.17). For each combination of dimension values, a different special case of resource flow can be defined. The following is a discussion of the different dimensions and the alternative flow dependencies they can be used to define.

Figure 10.17: First two levels of design dimensions for flow dependencies

Resource Kind The most important design dimension is the kind of resource. Section 10.7 will describe how resource dependencies are specialized according to this dimension.

Prerequisite Relationship Another important dimension is the kind of prerequisite requirement. According to this dimension, resource relationships are classified as follows:

Persistent flows. In these situations one or more resources are produced once, and can then be used an infinite amount of times. In software systems, they arise often to describe the use of calculated constants, and system resources (printers, network channels, etc.) that are set up once and then used an indefinite amount of times.

Perishable flows. This more refined special case of permanent dependencies describes situations where produced resources can be used an indefinite amount of times until they become invalidated. File caching provides an example application where this type of flow describes the underlying interdependency. Cached file blocks are transferred (produced) once from disk and can then be read an arbitrary number of times until some other process modifies their corresponding disk block. Then the cached file blocks become invalidated and have to be refreshed from disk before they can be read again.

Cumulative flows. In these situations every resource produced can only be used once. Producers and users can proceed asynchronously, but at no time can the number of user accesses exceed the number of produced resources. Reading and writing a pipe channel by two separate processes is an example of this type of flow.

Transient flows. In these situations a stream of resources is produced, but the use of each resource is optional. Thus new resources in the stream can overwrite previous ones, possibly before they have been used. One example application where transient flows describe the underlying interdependency is a log file that is periodically being updated and can be printed by a user at will. Not all versions of the file need to be printed. Therefore new updates can overwrite the previous contents of the file without the need for additional coordination.

Lockstep flows. These situations occur where there must exist tight synchronization between producers and users of resources. All resources produced must be used and no resource can be produced until all previous resources have been used by all designated users. Stream data flows using nonbuffered (indivisible) carriers are examples of lockstep flows.

MANAGING PREREQUISITE COORDINATION PROCESSES The coordination process selected to manage a prerequisite dependency at the heart of a resource flow has a profound influence on the overall organization of the interacting activities. Corresponding to the four generic classes of prerequisite coordination processes, we have an equivalent taxonomy of flow organizations:

Producer push. In push organizations, also called eager flows, resource users explicitly receive control from producers every time a new resource has been produced. Only lockstep flows can be implemented in this manner.

If control is transferred to users using synchronous calls, this organization reduces to what is commonly called client/server architecture. The resource producers act as clients and resource users act as servers.

Consumer pull. In pull organizations, also called lazy flows, resource producers are invoked by users whenever the latter require a new resource. Only lockstep and permanent flows can be implemented in this manner.

Pull organizations of flow dependencies also reduce to client/server architectures. Resource users act as the clients and resource producers act as the servers. Note, however, that the direction of the client/server relationship is the inverse of the direction of the flow relationship.

Peer synchronization. In peer organizations producers and users are executed by separate threads of control and synchronize themselves through events. This is a more loose organization, appropriate for managing all kinds of flows. It is particularly suitable for organizing cumulative and transient flows. It might not be as effcient for managing lockstep flows, where tight synchronization is required. Examples of flow processes that are organized in this manner include pipe channel flows, shared memory flows with separate semaphore synchronization, tuple space flows, and so on. Ada's rendezvous interprocess communication paradigm (DoD 1983) is one well-known specialization of peer organizations. Other researchers have used the term implicit invocation architectures to characterize such organizations (Garlan 1988).

Controlled hierarchy. Such organizations typically result in systems with centralized control, where a main program explicitly controls the sequence of flow participants.

Number of Producers and Users—Sharing Dimensions

One-to-one dependencies. These are the simplest kinds of dependencies. The defining dimensions are the kind of resource and the kind of prerequisite relationship. There are no sharing considerations.

One-to-many dependencies. In one-to-many dependencies, resource sharing becomes an issue. Different dependency types can be defined for each combination of resource sharing dimensions of each of the users. Some interesting special cases are:

One-to-all dependencies. Each resource flows to all users

One-to-one-of-many dependencies. Each resource flows to one of the users. This can be managed in an application-independent way (e.g., first come–first served), or in an application-specific way. In the latter case, user consumer ports usually provide additional pieces of information, such as user priorities.

Many-to-one dependencies. In many-to-one dependencies, user sharing issues have to be addressed. Users might not be willing to receive all resources produced, or they might not be able to receive them concurrently.

Situations where users are not willing to receive all resources produced are often referred to as race conditions. In our framework, race conditions are modeled as many-to-one dependencies where the user activity acts as a consumable ''resource.''General ways of managing consumable resources can be used to manage the dependency.

Many-to-many dependencies. These dependencies are the most complex family because they can specialized according to both resource-and user-sharing dimensions. Some interesting special cases include:

Each-to-all. Every resource produced flows to all users

Each-to-one. Every resource produced flows to one user only

Each-from-one. Each user receives one resource only

All-from-one. Only one of the resources produced flows to (all) users

The design alternatives for managing resource dependencies are the product of the different alternatives for managing each component dependency. In principle, each of the component dependencies can be managed by independent coordination processes. In practice, however, there often exist opportunities to increase effciency by managing patterns of dependencies using joint coordination processes. This gives rise to additional design alternatives that designers should be aware of. We have already encountered the opportunity to use joint coordination processes for managing accessibility and sharing (restrict resource transportation, replicate resource). In the following sections we will encounter more opportunities for joint dependency management.