Treffer: State-Based Approach to Resources Management for Task-Based Process System, A

State-Based Approach to Resources Management for Task-Based Process System, A

Mills, Stephen F., Tanik, Murat

University of Alabama at Birmingham. Department of Electrical and Computer Engineering

2018

University of Alabama at Birmingham: UAB Digital Collections

Computer systems -- Reliability, Computer engineering, technical reports

Fachzeitschrift text

application/pdf

English

Technical report (University of Alabama at Birmingham. Department of Electrical and Computer Engineering); 2018-08-ECE-142; Technical report (University of Alabama at Birmingham. Department of Computer Science and Engineering); 2001-12-ECE-013; Technical Report 2018-08-ECE-142 Technical Report 2002-12-ECE-013 A State-Based Approach to Resources Management for Task-Based Process System Stephen F. Mills Murat M. Tanik This technical report is a reissue of a technical report issued December 2002 Department of Electrical and Computer Engineering University of Alabama at Birmingham August 2018 Technical Report 2002-12-ECE-013 A State-Based Approach to Resom·ccs Management for Task-Based Process System Stephen F. Mills Murat M. Tanik TECHNICAL REPORT Department of Electrical and Computer Engineering University of Alabama at Birmingham December 2002 ABSTRACT The maturation of process engineering as a distinct discipline necessitates the development of an engineering framework that support the rigorous engineering of process systems. As is the case for other engineering disciplines, process engineering must have the ability to enforce quality standards during the design and implementation of process systems. A survey of process formalisms from the literature is presented and the task system model, a task-based process formalism that appears to provide a suitable basis for the development of a process engineering framework, is described. Extensions to tills model that are specifically intended to address process system reliability and parallelism are introduced. Issues related to task system determinacy and concurrency are discussed and extensions to the task system model that address these issues are described. Specifically, abstract resources and resource states are introduced as extensions to the task system model that can ensure determinacy and also impose constraints that ensure that the transformation of key resources progresses through the desired sequence of states as the task system executes. It is also demonstrated that these extensions provide a means to potentially improve process system efficiency by maximizing parallelism to the extent that reliability is not compromised. INTRODUCTION The quality of goods or services can be described in terms of quality attributes, measurable characteristics of the goods or services that reflect ";fitness of use" from the perspective of 1 customers and users (Delcambre 1994, Kolarik 1994). The quality of a product or service can be viewed as a function of (Tanik and Ertas 1992, Kolarik 1994): • the cost of the product or service, • the timeliness with which products or services are produced, delivered and repaired following failure and • reliability ofthe product or service in terms of fitness for use and satisfaction of customers and users. Reliability in this context is seen as the ability of a product or service to consistently perfom1 within specified parameters, and is thus regarded to be representative of general customer or user satisfaction with the product or service, provided that satisfaction can be properly parameterized. Several issues that must be addressed in order to ensure the reliability of a process system have been identified. Two important ones are (Coffman and Denning 1973, Armenise et al. 1993): • Execution timeliness, which is related to the ability of the system to execute within time constraints and • determinacy, which is related to the consistency of results produced by the system during repeated executions. Execution timeliness depends, in part, upon the efficiency with which the process system operated. In general, increased timeliness can be achieved through increased parallelism within 2 the process system, which may, in turn, be achieved by maximizing the shared utilization of resources. Nondeterminacy is defined as the inability of a process system to produce consistent results through repeated executions, potentially introduces unreliability in a process system. Nondetenninacy can result from the unrestricted sharing of resources among tasks that modify them during execution. Resources are thus seen to play a major role in determining the reliability, operational cost and timeliness of a process system. PROCESS REPRESENTATION FORMALISMS In order to improve process quality, a means to rigidly analyze the target process system and to evaluate proposed improvements is needed (Yeh et al. 1991, Tanik and Chan 1991). A process modeling formalism provides a rigid syntactic framework for representing and analyzing process. As is the case for software engineering (Sage and Palmer 1990), a notational formalism or a set of such formalisms is viewed as essential to the development of disciplined process engineering activities. However, the development of an adequate formalism does not necessarily result in a usable methodology. Tools and methods, as well as procedures for their application, must generally be developed to provide a semantic layer between the humans that must eventually produce processes engineering artifacts and the underlying syntactic formalisms. Formalisms can thus provide a structured foundation upon which tools and methods can be constructed. 3 The processes for an enterprise are often described only in policy documents, organization chru.is, and product specifications (Delcambre and Tanik 1994). This is a suitable representation scheme for humans who must execute the processes, but does not lend itself to formal analysis, monitoring, or improvement. Ideally, a process modeling formalism should provide a sufficiently powerful syntactic model to support rigorous analysis, simulation and manipulation while facilitating the application of semantics to support process enactment and detailed observation from a number of stakeholder views. The following issues that must be addressed developing process models (Curtis ct al. 1992) also should affect the choice of a process modeling formalism: • Degree of formality: In order to be enacted on a machine, a process formalism must be both precise and objective. In real life, however, processes are likely to be heavily dependent upon the actions of humans, and are thus likely to be somewhat ambiguous and non-deterministic in nature. In many cases the components of a process are purposely defined in an ambiguous manner to allow flexibility for the humans that must execute the process. Transposing such a process description onto a rigid formal framework may result in loss or alteration of information, possibly distorting the resulting process models. • Granularity and precision: The degree of granulru.ity that must be provided varies depending upon the nature of a particuJ ar process component and the level of understanding that has already been attained for that component. The analysis process, for exru.nple, may require an extremely detailed representation scheme for the particular components being analyzed. Once those components are understood, however, it may be desirable to 4 represent them in a more abstract manner to reduce both the computational complexity associated with modeling and the introduction of en·or. A formalism should also provide the capability to combine components represented at different levels of gran:u.Jarity within the same model. • ";Scriptiveness" and fitness: For purposes of assessing and improving processes, several perspectives may be taken by a process model in terms of ";scriptiveness."; Prescriptive models assume that the proper behavior for a process is known in advance and measure the fitness of a particular process being modeled in terms of this assumed proper behavior. This perspective is intuitively appealing in many cases, since the "characteristics" of a process can be encoded as part of the model to serve as goals of process improvement. Evolutionary improvement of processes may be inhibited, however, since subjective determinations as to ";proper behavior" of a process must be made. Descriptive models attempt to determine through observation the nature of the processes currently in place within an enterprise. Once determined, these process characteristics form a process baseline that can be explicitly modified, then reassessed via descriptive modeling. Proscriptive models impose constraints delineating behavi.or that is not allowed. This perspective is somewhat weak in assessing process quality and is usualJy employed in conjunction with either prescriptive or descriptive modeling. A number of specific desirable characteristics for process modeling formalisms have been described in the literature include the following, which were synthesized from (Bandinelli et aJ. 1993, Conradi et al. 1992, Armcnise et al. 1991, Madhavji 1991, Yeh et al. 199lb): 5 • Multiple levels of abstraction: ability to ignore details that are not relevant. • Modularity: support for partitioning into logically independent units with well-defined interfaces. • Decomposability: Capability to produce a hierarchy of reusable "submodels" • Genericity: Ability to specify general solutions for classes of problems, possibly by parameterizing the problem-specific details. This also implies the capability to customize generic process models to meet domain-specific criteria and attributes of the processes being modeled. • Instantiation: Support for binding of process components to humans, computing devices, resources, pre-defined tools. • Varying detail: Support for concurrent existence of formally described parts and incomplete or poorly specified parts of the process system. • Nondeterminism: Capability to allow underspecification or non-specification of the manner in which decisions are made. • Formality: A formal syntactic framework that supports automatic analysis, simulation and enactment of the modeled processes. • ";Human-friendly" representation: Support for a representation scheme that allows models to be presented to human observers in an understandable and intuitive manner so that they can understand and agree upon structure and behavior. There is a general consensus in the literature that this implies a graphic representation scheme. 6 • Multi -perspective: organizational). Support for several perspectives (e.g., functional, behavioral, • Integrated monitoring and measurement: Support for static and dynamic analysis and measurement and mechanisms for monitoring the behavior of modeled processes in order to evaluate performance and to support evolution and customization. • Parallelism: Capabilities to represent and model parallelism and concurrency. • Time constraints: Specifications of time constraints and ability to measure performance of the system against these constraints. • Run-time modifiable: Supp01t for changing the system structure during execution. Process modeling and representation formalisms proposed to date in the literature may be generally categorized in the following ways, based upon the way in which process models are developed and represented within the formalism (Comadi et al. 1992, Delcambre and Tanik 1994): • descriptive, • network~based, • imperative or programmatic or • hybrids of more than one of these categories. It will be seen that the boundaries between these categories are indistinct and that formalisms that fit predominantly in a particular category often have some characteristics of one or both of the other categories. 7 The sections that follow describe what is viewed as a representative sampling of proposed formalisms from each categol'y and discuss common characteristics by category. Descriptive Formalisms Descriptive systems provide a framework for characterizing the key entities and relationships in the process. In particular, rule-based systems (or production systems), a subclass of descriptive systems, provide a great deal of flexibility in that no explicit ordering for activities need be given. This all.ows inherent parallelism which can be exploited during execution of the model. Rules (and thus characteristics of tbe model) are easily modified and can be changed during process simulation or execution without disrupting the behavior of the process model. Descriptive formalism generally do not, however, explicitly represent execution control (Armenise et al. 1991). This characteristic provides flexibility, in that the ordering of task execution can be determined during execution and is not proscribed in advance by the structure of the process model. As a result, however, the structure of a process model based upon a descriptive formalism may not be evident to a human observer. MARVEL (Heineman 1994) is a rule-based system that supports the creation of a process­centered environment for process modeling. A key aspect of MARVEL is support for cooperating agents, processes within a process system that work together to accomplish tasks. This concept provides the capability to define unique agents that provide particular services to other agents, and also to provide a hierarchy of abstraction through the encapsulation of sets of related tasks. In addition, there may be tasks (such as a conference call, for example) that jnherently reqtlire the interaction of independent agents. As pat1 of each MARVEL environment, 8 a data model, a process model, tool envelopes and a coordination model. The data model is object-oriented and is specified through the definition of a class hierarchy. The process model is defined using the MARVEL Strategy Language (MSL), a declarative language that supports the specification of rules that determine process execution. At the heart of the MARVEL system is a database management system that supports concurrent queries from agents that are executing concurrently. Dming execution, queries are used to locate appropriate rules and to determine wbat actions are taken if pre-conditions for a rule are satisfied. Conflicts that arise between agents are resolved using conflict rules, also stored in the MARVEL database. The Adele System (Belkhatir et al. 1993) is a software process modeling f01malism that evolved from a need for software configuration management in a complex software engineering environment. This formalism extends the entity-relationship approach to allow the association of triggers and methods, as well as attributes, with relationships. Views at multiple granularities are provided to support process analysis from an administrative perspective as well as a more detailed engineering perspective. Adele is implemented using a two-level approach. The bottom layer, known as the Adele Configuration Management kernel, combines an object-oriented representation scheme (for entities and relationships) with an activity manager that utilizes triggers. This layer was developed primarily to support software configuration management throughout the engineering lifecycle and includes mechanisms to manage overlapping work environments and to simultaneously provide different contexts to different users (or to the same user) so that only appropriate versions of software o~jects are combined and presented to a user. Support for different contexts allows different methods, triggers and attributes sets to be 9 associated with different instances of the same object type. Objects can thus be used simultaneously by different users and for different purposes. The top layer of the system, referred to as the TEMPO formalism, provides a language that facilitates the development of software process models within the object framework of the Configuration Management kernel. TEMPO provides mechanisms to define roles, which in turn group related object instances within a common context. Programs written using TEMPO are thus specifications of roles and association of common triggers and methods with the objects that share a role. Object-oriented formalisms can also be viewed as a subclass of descriptive systems. An object-oriented approach can be viewed as well con-elated to the way in which humans perceive the world (Opdahl and Sindre 1993). TI1e use of an obj ect-based formalism as a basis for modeling and analysis can provide for the smooth design and implementation of new processes, allowing process engineers to divide and conquer large, complicated problems by describing them as a hierarchy of classes and objects analogous to the real-world entities and relationships they represent (Johnson 1995). An object-oriented approach faci litates evolutionary modification and extension of the initial design, a characteristic that is well matched to the dynamic environments in which most processes are executed. In addition, an object-based approach may facilitate the reuse of process engineering artifacts by promoting modularity and encapsulation, providing a clear description of each object and providing for restricted and controlled abstraction within class hierarchies (Seo and Loucopoulos 1993). However, there are some potential limitations of an object-based representation formalism. The class hierarchies that provide a basis for objects tend to be developed as static entities 10 (Opdahl ao.d Sindre 1993). The dynamics associated with project execution are not therefore explicit in the representation of the processes. As a result, object-based process models may not lead to a clear understanding of process dynamics and may also inhibit validation and verification of the process models. Object-oriented approaches sometimes counter this problem by including the development of an object model, which is concerned with the static structure of the system, a dynamic model, which is concemed with sequencing of interactions, and a functional model, which is concerned with data transformations (Rumbaugh et al. 1991). An additional concern relative to object-oriented approaches is that many of the constraints that govern process execution in the real world are stated or understood by the human participants in declarative terms. Processes and the human tasks associated with them tend to be goal-oriented. Goals and declarative constraints are often difficult to represent using an object-oriented representation framework (Shams-Aliee and Warboys 1995). Like descriptive or rule-based formalisms, object-oriented formalisms generally do not provide a means to explicitly represent execution control, resulting in a model strUcture that is sometimes not obvious to a human observer. Shams-Aliee and Wat;boys (1995) suggest that the limitations of an object-oriented approach may be overcome by adding an abstraction hierarchy above the object layer. This intermediate layer would ";bridge the gap" between goal-oriented process descriptions and an object~oriented representation by supporting the description of roles for the hurmm participants and timing constraints for the tasks associated with the processes. 11 Jolmson (1995) describes an object-oriented approach to process representation and modeling using Thermotalk, an object-oriented language similar to Smalltalk but with extensions to facilitate the design and modeling of thermal systems (such as refrigeration systems and power plants). Thermotalk is intended for use by non-programmers, particularly the systems engineers and mechanical engineers who design and implement thermal systems. The goals in developing and applying Thermotalk were to develop design and modeling tools for the engineering of thermal systems that would help system designers cope with complex solutions and also provide an improved understanding of the problem being solved. By providing an intuitively pleasing representation of the processes at work within thermal systems, it was also hoped that •• Thermotalk models wotud facilitate agreement among the system designers, implementers, customers and eventual users. OBM (Sa and Warboys 1995) is an object-oriented process formalism that was originally developed as a representation and modeling formalism for concurrent systems. Support is provided for abstract objects, which may be used to represent components of a process system that are not well defined. Boxed objects allow components to be grouped and treated as a single component. These two features combine to supp01t multiple views, hierarchical layers of abstraction and varying levels of detail within a process system represented using OBM. OBM is reflexive in the sense that each object can provide mechanisms for self-modification. Such self-modifications can be performed during execution. 12 Network-Based Formalisms Network-based formalisms provide natw·al support for modeling of non-determinism and parallelism and are generally capable of providing a pleasing representation scheme. In most cases they provide a graphical view of the activities to be perfom1ed and clearly indicate sequencing and concurrency. Large models created using these schemes may, however, tend to become unwieldy and difficult to modify. This can cause problems given the dynamic nature of most processes, pru.ticularly if improvements (and hence changes) are desired. Conceptual difficulties sometimes arise when attempting to represent complex relationships among entities in the network without ambiguity (Opdahl and Sindre 1993). Modification of network-based process models during execution may cause disruption (Armenise et al. 1991). Included in the category of network-based formalisms are Petri nets and their extensions, finite-state automata and data flow diagrams. Petr i nets were introduced by Carl Adam Petri as a formal basis for modeling and analyzing the communication among computer system components (Peterson 1981). Since that time, a large body of research has focused on the development of a theoretical framework for Petri nets, as well as the application of Petri nets to the modeling of systems. A Petri net is a directed, bipartite graph consisting of a set of state nodes (sometimes referred to as places) and a set of transition nodes, along with arcs that connect them. The arrival of a token at any of the state nodes causes the node to fire, activating all of the transition nodes to which the state node has arcs. The primary strengths of Petri nets lie in their ability to model concurrency in an asynchronous fashion, their inherent modularity, which easily supp01ts concatenation and other 13 combination operations and the graph-based representation scheme that is generally used to represent Petri nets. The ability to easily combine independent networks in modular fashion without loss of the associated semantics provides a convenient way to represent subsystems and components during system design and analysis activities. Figure 1 depicts an example of a Petri net consisting of three states, one transition and arcs that interconnect them. States and transitions are labeled accordingly and the marker inside State 1 represents a token. The Software Process Analysis, Design and Enactment (SPADE) environment supports process development with a focus on support for the evolutionary lifecycle of the process system (Bandinelli et aL 1993, Di Nitta and Fuggetta 1995). SPADE is based upon extended Petri nets, called ER nets, that allow a predicate assertion and an action, executed if the assertion is tme, to be associated with each transition. The SPADE Language (SLANG) provides a programming interface for developing process models. During execution, each activity within a process results in the creation of an instance of the SLANG interpreter, or process engine, that executes the SLANG code corresponding to the activity. In the context of SPADE, state nodes, referred to as places, providing a storage function (e.g., for software design documents, test plans or specification documents) and transition nodes representing activities performed during execution of a process (e.g., a particular software coding or test activity). Arcs between places and transitions represent relations and tokens on the net represent data or resources. SLANG is fully reflexive, so that source code, such as descriptions of activities represented by places of a net, can be processed as data. Late binding is used so that reflexive processing can be used to modify the behavior of a SPADE net during execution. Hierarchies of SPADE nets can be defmed and 14 refinement is supported. This provides support for multiple views, abstraction layers and varying levels of detail within a model. State 1 State 3 Transition State 2 Fig 1. Example of a Petri net The Role Interaction Net (RIN) formalism is based upon Petri net theory, but also incorporates role theory in order to allow the organizational aspects of the enterprise to be modeled (Singh and Rein 1992). Role theory takes a view of th.e organization as composed of positions, each of which is associated with activities and required interactions with other positions. Each human participant in the organization occupies a position, and the corresponding roles taken by these individuals are the building blocks of the organization. RIN's provide representation mechanisms for representing nondeterministic choices by process participants optional interactions (i.e., interactions that may take place but are not required). Activity­centered and role-centered views are supported. Representation of concurrency is inherent in the structure of a RIN and modification of RlN structure during execution is suppmted. Support for hierarchical decomposition is provided 15 and varying levels of detail can be specified within a system and additional detail specified during execution. Figure 2 illustrates an example of a RJN. By convention, t ime is assumed to move forward down the vertical axis while the individual roles are indicated by vertical colunms. A square containing an ";X" symbol inside a box represents an activity to be executed by a participant having the corresponding role. Connection of boxes in other columns represents distribution of the results of that activity among other process participants corresponding to the indicated roles. In this example, a software developer writes code for a software module and writes a user's guide for this software, which is distributed to a software tester and management. The software tester then writes a test plan for the software, which is djstributed to the software developer and management Software Developer lXI Write Code ~e User's est Plan Fig 2. Example of a RIN 16 Management FUNSOFT Nets (Brockers and Gruhn 1993, Gruhn and Jegelka 1992, Gruhn and Saalmann 1992) are based upon an extension to Petri nets called predicate/transition nets because of the association of a firing rule with each state node. In the context of FUNSOFf nets, conventions similar to those described previously for the SPADE formalism are used, with state nodes, referred to as channels, providing a storage function and transition nodes, referred to as agencies, representing activities petformed during execution of a process. Arcs between channels and agencies are referred to as edges and represent relations between channels and agencies. The refinement of agencies is supported as a means of creating hierarchies of FUNSOFT nets and thus providing multiple views and layers of abstraction. Agency refinement also provides a means to simultaneously represent various levels of detail within the same model. The predicates associated with agencies determine the firing behavior in terms of outputs generated. Predicates also allow the behavior of a FUNSOFT net to be automatically modified in specified ways during execution based upon the firing of an agency. Attributes are associated with edges to indicate whether each edge represents a data flow or a control flow and also to indicate how the corresponding data or control signals behave. Figure 3 illustrates an example of a FUNSOFT net representing a software development activity. By convention, channels are represented as circles, agencies are represented as rectangles and edges are represented as arrows. In this case the activities relate to the coding of software modules and the development of a test plan for the integrated modules. Channels store functional specifications a system specification and a test plan, respectively. 17 RequirementsDocs:SystemSpec CodeModule1 DeslgnDocs:FunclionaiSpec1 0~---· DesignDocs:Functiona!Spec2 CodeModule2 WrlteTestPlan Fig 3. Example of a FUNSOFT net TestDocs:TestPian Dataflow diagrams provide a representation scheme based upon processes, stores, external entities and flows among them (Opdahl and Sindre 1993). The use of dataflow as a basis for a process modeling formalism is based upon the concept that the processing of inputs to create outputs is of central interest when modeling many types of processes. Opdahl and Sindre (1993, 1995) present an enhanced dataflow representation scheme that is intended to address some of the conceptual shortcomings of data flow diagrams. In particular this approach, referred to as DFD, provides a representation and modeling formalism capable of representing the processing and exchange of material goods as well as information. This scheme extend the basic dataflow model to include full decomposability of processes, flows and stores into more detailed dataflow diagrams. This provides a means to model, for example the damage of material goods during shipment or the degradation of material goods during prolonged storage. In addition, decomposability provides an abstraction mechanism that supports a hierarchy of views of a system being modeled. A fourth component, the link, is introduced as a connective among processes, flows and stores. A link between components indicated interaction 18 between those components and may serve as synchronization between them. The resulting extended dataflow model, referred to as DFD, provides a flexible system that naturally models conculTency. No mechanisms are explicitly provided to represent non-determinism. Imperative or Programmatic Formalisms Imperative or programmatic formalisms have the advantage that they are conceptually similar to software programming languages, which are generally well understood and subject to strict syntactic rules. This is a desirable feature when executing models on a machine, but may fail to capture the non-determinism inherent in the execution of a human-intensive, real-world process. In particular, the ordering that is imposed when executing procedural programs may not be well matched to the way in which activities are performed in the real world. The two examples provided below are, in fact, obsolete in the sense that both formalisms have now been extended to incorporate features of the descriptive and network-based formalisms. Developed as part of the ARCADIA project, APPLIA (Taylor et al. 1988) is a programmatic process formalism that is based upon Ada with extensions to support the representation of relations, predicates and triggers. APPLI A programs are executed by an interpreter. While process descriptions are specified in procedural form, mechanisms to define system constraints in rule form are also provided. The IPSE 2.5 project (Robertson 1994) began as an effott to develop a programming language for process representation and has evolved into Processwise, a suite of process support services. The Processwise architecture supports the definition of a set of models for each process system, similar to the set proposed in (Conradi et al. 1992), including a user model, and 19 environment model, an organization model, a product model and an activity model. The activity model, which is the model ultimately executed, is developed using the procedural Process Management Language (PML). The granularity associated with the activity model and the relationship of roles as defined in the user model must be determined dming system development and cannot be changed during execution. Changes to execution sequencing, such as the decision to skip an activity, arc supported during execution. Hybrid Formalisms An evolving understanding of nature of process has provided more insight into strengths and weaknesses of formalisms in the different categories discussed previously. For example: • Network-based formalisms such as Petri nets and data flow diagrams provide natural support for the explicit modeling of nondeterminism and parallelism. This is generally not the case for descriptive formalisms, which do not explicitly represent execution control. Programmatic formalisms in some cases provide explicit mechanisms to specify concurrent execution, but also do not generally provide capabilities to represent nondetermjnism. • Descriptive systems can generally supp01t modification of process models during execution. This is not always the case for network-based formalisms, since execution is potentially disrupted by structural modifications to an executing process systems. Programmatic systems may allow the replacement of certain components during execution, but may also be disrupted by significant modifications during execution. 20 • Programmatic systems allow the structure of a process system to be specified in a procedural fashion that is consistent with the way that system requirements and goals are often developed. Descriptive and network-based systems may have difficulty representing these requirements and goals explicitly. • By definition, programmatic and network-based formalisms are more heavily proscriptive than descriptive systems. As a result, exceptions that occur within a programmatic or network-based process model are often easier to detect and resolve than in descriptive process models. As a result of these differences, many recently proposed formalisms are hybrids, incorporating attributes of different types of formalisms so as to combine their respective strengths (Armenise et al. 1991). EPOS is described as a process support environment that includes an object-oriented process modeling language, an initial process schema and a set of process tools that combine to provide a hybrid expert system for the development of process systems (Jaccheri and Comadi 1993). EPOS employs a object-oriented database and provides a database management language, based upon Prolog, that allows the definitions of constraints and triggers. The object­oriented Software Process Evolutionary Language (SPELL) associated with EPOS is fully reflexive and supports defmitions of class hierarchies with single inheritance. Multiple layers of abstraction are also provided. As is the case for Smalltalk, SPELL uses dynamic binding during execution. A feature called change-oriented versioning provides the capability to track changes to multiple objects as a single logical change to the system. Modifications may be made to the 21 instantiated objects of an executing system, although no protection from side effects of such a change is provided. A TASK-BASED PROCESS FORMALISM In order to improve process quality, a means to rigidly analyze the target process system and to evaluate proposed improvements is needed (Yeh et al. 1991). Delcambre (1994) introduces a process modeling and analysis framework that is based upon the task system model of Coffman and Detming (1973). The task system model was originally developed as a mechanism for representing and analyzing the interaction of concurrent software processes within the context of computer operating systems. The task system model represents the activities of a process or process system as a set of tasks: Within the context of the task system model, no assumptions are made regarding the semantics, granularity or functionality a task or task system. As a result, a single task may represent anything from a number of steps in the design of a software artifact to a single computer instruction, depending upon the specific application. Associated with each task Ti are an initiation event, denoted Tit, and a termination event, denoted Ti'!-. A task system is defined as the pair: c = {'t, RTsponges> RTTowcls• RTwux> RTRaJ!!"; RTBrushes> RTintcrior> RTE.~tcrior> RTwheels} TABLE2 TASKS OF THE CARWASH TASK SYSTEM Task Name Description RTswr Personnel that work at the carwash RTvacuum Vacuum cleaner used to vacuum automobiles RTsoap Soap used to wash automobiles RTwater Hose Water hose used to wash and rinse automobiles RTsponges Sponges used to wash automobiles RTTowels Towels used to dry water from automobiles after washing RTwax Wax applied to automobiles during waxing RTRags Rags used to buff dry wax from automobiles RTarusbes Brushes used to clean wheels on automobiles RT!nterior Automobile interior RT~xterior Automobile Exterior RTwheels Automobile wheels For the purposes of this example, it is assumed that the resource type RTstaff represents a pool of human resources available to perform tasks listed in table 1 as needed. Resource type R T staff thus appears in the input set but not the output set for each task that uses resources of this type. Each of the other resource types is assumed to represent a single instance of the 32 corresponding real-world resource that is used exclusively by a particular task until the task is complete. As a result, each of these resource types that appears in the input set I-r for some task T also appears in the output sets OT. Task descriptions for the tasks of 't include the input set IT, the output set OT and the measurement definition FT for each task T E 't. The input and output sets IT and OT, respectively, for task system Cearwash. can be represented as indicated in Table 3. TABLE3 INPUT AND OUTPUT SETS FOR TASK SYSTEM Ccnrwash Task Name Input Set (IT) Output Set (OT) Vacuum RTstaiD RT Vacuum> RTrmerior RTvacuum RT!nlerior Wash RTsraro RTsoap> RTwntcrHose• RTnxtcrior RTsou>• RTwntorHose> RTE"Xterior Dry RTstaiD RTTowels• RTI!x.tcrior R TTowels> R TExtedor Wax R T Staff> RT Wax• R T Exterior R T Wax> R T Exterior Buff R T Staff• R TRags> R T Exterior RTRags> R.TExlerior Wheels RTs~aro RTn~s> RTwatcrHosc• RTwheels RT Brushes> RT WaterHo.'&> RT Wheels INTERFERENCE AND DETERMINACY Tasks T and T' are said to be noninterfering if either (Coffman and Denning 1973): • T is a successor or predecessor ofT', or In other words, interference can only occur between independent tasks that share resources. In the context of a task system C = ('t, associated with the attributes Zru = {Zx" . , z.u} ofy measured at some discrete instant in time. X The resource state WY can thus be seen to be an element of the set of states that can be assumed by an actual resource y: It is assumed that the definition of attributes and associated values for each resource (during process engineering design) sufficiently captures all prope1ties of the resource that are of interest and allows them to be specified at a sufficient level of quantization. This necessarily 43 includes all characteristics of the resource that are subject to change during execution of the task system and that, by changing, can affect the behavior of tasks within the task system be represented as attributes. From the definition of the state of a task system C = ( -rc, ~ *) e (RT n R.r) u (DT n RT') u (RT n DT') (i.e., T and T' are interfering due to a conflict involving abstract resource arxJ In the case that task T (or T') creates arxi• then T (or T') is the originating task for state e>arx;·o and (arXi, cr., •. J e DT', where k ;?; 0. If k = 0, then Step 4 of the Resource State Determinacy '"Xt• Algorithm adds the precedence relation T 0 , then there also exist states crarXi,1, . , crarxi·k-t and thus there are tasks T1, . , Tk-l e t so that Step 3 of the Resource State Determinacy Algorithm adds to C0 ' the precedence relations T ' originating task for some state cra1· l+l of arx;· Then k :t= l unless T = T', since each state results Xw from the termination of a specific task as discussed previously (i.e., k = T.!. and l = T'.J. are unique events). If k < l (i.e., if event k precedes event lin time), there exist states . , T1.k-l RTsoap> RTwaterHoso> RTsponges> RTTowcls• RTwax> RTRags> RTumsbes> RT)n!erior> RTu.xtenorandRTWheets appear in the output sets for one or more tasks T E •ean,-as~.· Oflhese resource types, only RTwaterHose and RTExtcrior are also shared by other tasks, as indicated in Table 5. Specifically, the resource type RT waterHose appears in the output sets for the tasks Wash and Wheels and the resource type RTExterior appears in the output sets for the tasks Wash, Dry, Wax and Buff. As a result, these are the only two resource types for which interference due to the shared use of resources having these type can occur within CcanvASit· TABLE 4 RESOURCE TYPES THAT ARE REPRESENTED IN DOMAIN SETS RTx E OT, T E 't T: RTx E OT RTvacuwn Vacuum RTsoap Wash R T Waterll0$C Wash, Wheels RTspong-.,. Wash RTTowel3 Dry RTwax Wax RTRags Buff RTBmsltes Wheels RTJnterior Vacuum RTExterior Wash, Dry, Wax, Buff RTWiteels Wheels 56 TABLE 5 SHARJNG OF RESOURCES REPRESENTED IN DOMAIN SETS RTx E OT> T E 't T: Rl'x E 01 T: RTx e I'fu OT RTvacuum Vacuum Vacuum RTsoap Wash Wash RTwatcrHose Wash, Wheels Wash, Wheels R.Tsponges Wash Wash RTTowels Dry Dry RTwux Wax Wax RTRags Buff Buff RT13rusbes Wheels Wheels RT Interior Vacuum Vacuum RTExtcrior Wash, D1y, Wax, Bujf Wash, Dly, Wax, Buff RTwbeels Wheels Wheels As a means to ensure determinacy, abstract resources can be defined to indicate the cases in which the same actual resource will be shared by tasks of 'teanvas11 during execution of task system Ccarwash and the Task System Determinacy Algorithm can then be applied to establish the necessary precedence relations among the interfering tasks. In this case, the abstract resources arwatcrHosol E ARstmnges and ru.·Extoriorl E ARExlcrior can be defined and preallocated to the domain and range sets of the tasks Vacuum, Wash, Dry, Wax, Buff and Wheels. Since none of the other resource type RTx that appear in the output set for some task T also appear in the input or output set for some other task T' E • eanvash• it is not necessary to define abstract resources for other resource types. 57 Table 6 illustrates the allocation of abstract resource arwaterHoscl to tasks Wash, Dry, Wax and Buff and ar&1eriorl to tasks Wash and Wheels, respectively, of task system Cearwash· TABLE 6 TASK DESCRIPTIONS USING ABSTRACT RESOURCES Task Name IT DT OT RT Wash R T Staff• R T Soap> { ar WaterHosel > RTsoap> { arWaterHoscl> RT WatcrHosc> ar Bxtcliotl} RTwatcrHosc> arExteriod} RTnxtcrior RTExterior Dry R T Staff> R T Towels> { arlixtcliorl} R T Towels> R T Exterior { ar Exterior! } RTExterior Wax RTsraff• RTwax• { ar Exterior! } R T Wax> RT Exterior { ar Exterior I } RTExterior Buff RT StaiD RT Rags• { ar Exterior)} R T Rags> R T Exterior { ar&teriorl} RTExterior Wheels RTstaff• RTarushc!> { at·waterHo.~el } RTBrushes> { arWatcrHoscl} RTwaterHose• RT Watcrfloso> RTWlreols RTwheels Application of the Determinate Task System Algoritlun to task system C following the pre-allocation of abstract resources arwaterHosei and arExtcriori results in a determinate task system. It can be observed, however, that, while the resulting precedence relations of cg~ssert ensure detenninacy in all cases, the task execution order may not ensure that the shared resources progress through the desired sequence of states. Figure 7, for example, illustrates a determinate task system: 58 C~rwash = {(Initial, Vacuum), (Initial, Wheels), (Initial, Buff), (Buff, Wax), (Wax, Dry), (Dry, Wash), (Vacuum, Terminal), (Wheels, Terminal), (Wash, Terminal)} that might result from application of the Determinate Task System Algorithm. While this system is determinate, the ordering of tasks that results does not preserve the intent of the process system. Specifically, buffing a car, waxing it, drying it and washing (in this order) it does not provide the intended result, which is a clean car with wax properly applied and removed. Buff Wax Dry Wash Fig. 7 A determinate task system C~vash with undesirable task ordering. 59 It can be observed that definition of the abstract resource arexteriorl serializes the execution of the tasks Wash, Dry, Wax and Bufi The order in which these tasks are executed, however, cannot be ensured by the Determinate Task System Algorithm. The desired order of these tasks can, however, be enforced through the use of resource states. Initially, attributes of Cleanness and Dryness are defined for abstract resource arExtel'iorJ· Values are then defined for these attributes as indicated in Table 7. For each of the tasks T E (Wash, Dry, Wax, Buff), appropriate resource states are defmed and associated with the occurrences of the abstract resource m·Exteriorl as this abstract resource is pre-allocated to the domain and range sets, DT and Rn respectively, for each task T E (Wash, Dry, Wax, Buff). TABLE7 ATTRIBUTES AND VALUE SETS FOR RESOURCE TYPE RT exterior attribute Zx; value set m xi Cleam1css {Dirty, Washed, Waxed} Dryness {Wet, Dry} · Thus, for example, the resource state (Washed, Wet) is associated with the abstract resource in the domain set DDry and the resource state (Washed, Dry) is associated with the abstract resource in the range set Rery for task Dry. This ensures that the exterior of the car has been washed but not yet dJ.ied when execution of task Dry is initiated and also indicates that the exterior of the car ";'ill be washed and dry when execution of task Dry terminates. Note that the wild card symbol"*" is used to indicate that the Dryness of abstract resource arl!xteriorl is irrelevant 60 to the initiation of task Dry. Thus, for example, a wet automobile could still be washed within the context of task system Ccarwash· Note also that, since the order in which tasks Wheels and Wash are executed is inconsequential to the desired result, it is not necessary to define resource states for abstract resource arwaterHosoJ· TABLE8 TASK DESCRJPTIONS WITH RESOURCE STATES SPECIFIED Task Name IT DT OT R,. Wash RTstRir• RTSoap, { atwaterHosol> RTSoap• { arwaterHosel> R T \Vnterffose> arfu:teriortC*, Dry)} RTwaterffose• arBxteriorl(Washed, Wet)} RTExlerio,. RTExterior Dry RTstaff> { arnxteriorl(Washed, Wet)} RTTowels• { al"ExteriortfWashed, Dry)} RTTowels> RTExterior RTExterior Wax RTstnll'• RTwax> { ar Exterior I (W ashcd, Dry)} RTwax> { arnxteriorl (Waxed, Wet)} RTExtcrior RTExterior Buff R T Slam RT R.1gs• {arExteriorl(Waxed, Wet)} RTRags> { arllxteriori (Waxed, Dry)} RThterlor RT Ilxterior Wheels RTstoiD { arwnte.:Hosel} RTBnosbes• { ar WaterRoso I } RTDJUshes> R T WatetHose> R T WaterHose> RTwhcels RTwbctls The Task System Determinacy Algorithm is applied to establish precedence relations in cases where abstract resources are defined but resource states are not needed (e.g., for abstract resource arw.terHosel). In this case, only abstract resources for which resource states have not been assigned are considered by this algorithm. Application of this algorithm results in the addition of the precedence relation (Wash, Wheels). 61 The Resource State Determinacy Algorithm is next applied. For abstract resource ar&teriorl• the originating state is Wash and there is no tetminating state in Ce;.,.wash· Table 9 illustrates the contents of the table states() upon completion of the Resource State Determinacy Algorithm. The precedence relations (Wash, Dry), (Dry, Wax) and (Wax, Buff) are added through application of this algoritfun, so that the resulting task system (with ";dummy" tasks Initial and Terminal added, as before, to create a closed task system) is: C~wash ={(Initial, Vacuwn), (Initial, Wash), (Wash, Wheels), (Wash, Dry), (Dry, Wax), (Wax, Buff), (Vacuwn, Terminal), (Wheels, Terminal), (Buff, Terminal)} TABLE9 ORIGINATING AND TERMINATING TASKS FOR EACH STATE OF arExteriort State crarx.,,k Originating Task Terminating Task (Washed, Wet) Wash Dry (Washed, Dry) Dry Wax (Waxed, Wet) \Vax Buff (Waxed, Dry) Buff I Figure 8 illustrates a precedence graph corresponding to the task system c~:nvash (with ";dummy" tasks Initial and Terminal added, as before, to create a closed task system). This task system, as discussed previously, is determinate for any interpretation of the tasks of-&. It differs from the task system cg,.,wasb that resulted from application of the Determinate Task System Algorithm, for example, in that the task Wash precedes the task Dry in the task system cg,'lr\vash. 62 This revised task ordering results directly from the states specified in the domain and range sets for the tasks of task system C~vash and results in the desired result of a clean, dry, waxed and buffed car as discussed previously. Note that, due to the sharing of abstract resource arwaterHosoL by tasks Wash and Wheels, the Determinate Task System Algorithm creates a precedence relation between. these tasks that did not exist in the original task system Ceanvash· The precedence relations between the tasks Vacuum and Wash and between tasks Vacuum and Wax that were present in the original task system Cearwash (illustrated in precedence graph form in Figure 3) are not necessitated by resource dependencies and are thus not included in task system C~am'llSb . This represents an opportunity for increased concurrency provided that sufficient resources can be made avail.able to the real­world process. Note that the assumption that only one real-world instance of each resource type results in the creation of appropriate precedence relations to ensure determinacy and thus reduces potential concurrency. In the case of resource type RT waterHosa> for example, the assumption that only one real-world water hose exists results in the precedence relation (Wash, Wheels). As indicated graphically in Figure 9, application of the Determinate Task System Algorithm (and subsequently tl1e Resource State Determjnacy Algorithm) following the pre-allocation of two abstract resources of type RTw.c.crHose results in a task system C~nrw"";"; that does not include the precedence relation (Wash, Wheels). This implies that additional ·concurrency can potentially be achieved through the addition of a water hose to the complement of real-world carwasb resources. 63 Wash Dry Wax Buff Fig. 8 A precedence graph representing the determinate task system C~rwasb . Of the resource types that appear in domain sets for the tasks of Ccarwaslv note that only R1\vaterHoso and RTstatl' can be increased to improve concurrency. R TExtcrior> the remaining shared resource type, is limited in quantity due to the characteristics of an automobile, which only has one exterior. 64 Wash Dry Wax Buff Figure 9. Result of adding a second abstract resource of type RT watorHoso· DISCUSSION It can be observed that task system determinacy plays an important role in maximizing concurrency among independent task chains without sacrificing consistency of execution results. In the case that a task system is determinate (or that multiple task systems that execute concurrently are mutually independent), the sequence of transformations appJied to shared resources by executing ta.c:;ks remains consistent for any execution sequence of the task system 65 and for any interpretation (meaning variation in execution times in the context of the task system model) of the constituent tasks. It can also be observed 1bat the Detenninate Task System Algorithm does not preserve the precedence relations that were originally specified for C = ('t,; http://uab.contentdm.oclc.org/cdm/ref/collection/uab_ece/id/140

http://uab.contentdm.oclc.org/cdm/ref/collection/uab_ece/id/140

edsbas.203AB916

BASE