Travel & Places


A Scenario-Based Approach to Hierarchical State Machine Design

One of the most crucial and complicated phases of real-time system development lies in the transition from system behavior (generally specified using scenario models) to the behavior of interacting components (typically captured by means of
of 8

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.


  Copyrights IEEE2000. Published in the proceedings of the3rd IEEE International Symposium on Object-OrientedReal-time Distributed Computing (ISORC’2000), NewportBeach, California, March 15 - 17, 2000. Abstract One of the most crucial and complicated phases of real-time system development lies in the transition from systembehavior (generally specified using scenario models) to thebehavior of interacting components (typically captured bymeans of communicating hierarchical finite statemachines). It is commonly accepted that a systematicapproach is required for this transition. In this paper, weoverview such an approach, which we root in a hierarchyof "behavior integration patterns" we have elaborated. The proposed patterns guide the structuring of a component’sbehavior, and help in integrating the behavior associated with new scenarios into the existing hierarchical finitestate machine of a component. One of these patterns is dis-cussed at length here. 1. Introduction Scenario models [1,2,10,11,12,16,18] and communicat-ing hierarchical state machine models [2,9,18,20,22] pro-vide two orthogonal views of real-time systems [18,20,22].The former view describes system behavior as sequencesof responsibilities that need to be executed by componentsin order to achieve overall system objectives, whereas thelatter expresses complete component behavior in terms of states and transitions.One of the most crucial and complex phases of real-timesystem design lies in the transition that is required to gofrom system behavior (defined by means of a set of sce-nario models) to component behaviors (described bymeans of communicating hierarchical state machine mod-els) [20,22]. Several factors ( e.g. , the large number of sce-narios, the concurrency and interactions between scenarios[22,24], the unpredictability of external events, etc .) con-tribute to the complexity of this transition. Furthermore,since most industrial systems generally have a long lifecy-cle, it is very important to build system components thatcan be easily maintained, reused and extended. It is wellaccepted that this latter demand further complicates thestructuring of the behavior of a component. Also, designersmust address nonfunctional requirements, such as perfor-mance and robustness. Thus, when considering all thesedifficult issues, it is generally acknowledged that a system-atic approach is required for the specification of the behav-ior of a component.In the current literature, some papers ( e.g. , [12,13,16]),define methods based on synthesis  algorithms that performautomatic generation of state machines from a set of inter-action diagrams. Such methods, in theory, completely auto-mate the transition between interaction diagrams and statemachines. Their main advantage, beyond automatic gener-ation of state machines, consists in having scenario modelsand state machine models in complete semantic synchrony.However, these algorithms do not consider several impor-tant design issues such as scenario interactions and statemachine structuring; issues, we repeat, directly relevant tocomponent maintainability and reusability. Moreover, noneof the existing methods have yet solved the problem of automatically integrating concurrent scenarios in the gen-eral case.In this paper, we propose a different approach to thespecification of the behavior of a component, one rooted inthe definition of behavior integration  patterns. Let us elab-orate. The use of design  patterns (e.g., [4,5,8,23]) has rapidlyincreased in industry in the last few years. The “patternsapproach” consists in defining a set of solutions that can beapplied by designers when facing specific design problems.Patterns can be classified in terms of their applicationdomain, the aspect of system development that theyaddress, and the level of abstraction at which they can beapplied. With respect to application domains, patterns have beendefined for both general design problems, and for problemsthat are specific to some application domains, such as real- Francis Bordeleau School of Computer Science, Carleton University, Ottawa, Canada Jean-Pierre Corriveau School of Computer Science, Carleton University, Ottawa, Canada Bran Selic ObjecTime Limited,Kanata, A Scenario-Based Approach to Hierarchical State Machine Design  time systems (including concurrent and distributed sys-tems) [14,15,19,23,24], CORBA [19] and avionics [14].With respect to the different facets of system development,patterns have been defined to address enterprise design,process and organization [23], system design [6,8], andsoftware design [5,6,23]. And, finally, with respect to lev-els of abstraction, patterns have been defined at the archi-tectural [21] and structural level [5,8,23], behavioral level(  Ibid  .) and programming level [5,8,14,15,19]. However, to the best of our knowledge, there exists nopatterns that address the difficult problem of integrating aset of possibly concurrent and interacting scenarios into aset of component behaviors. In this paper, we describe oneof the several behavior integration patterns we have identi-fied [2] to help designers define communicating hierarchi-cal state machines from scenario models. Figure 1 gives anoverview of these patterns.Figure 1. Hierarchy of behavior integration patternsWe will focus here on the State Machine Integration pattern.This paper is structured as follows. In section 2, wedescribe the Automatic Teller Machine (ATM) system usedto illustrate. In section 3, we describe our general approachfor hierarchical state machine design. In section 4, wedescribe the State Machine Integration pattern. Finally, insection 5, we summarize and discuss our experience of using the pattern approach decsribed here in an industrialcontext. 2. Example: an ATM system In this presentation, an Automatic Teller Machine(ATM) system is used to illustrate the State Machine Inte-gration  pattern. This ATM system is a conventional onethat allows for withdraw, deposit, bill payment, andaccount update. The ATM system is composed of a set of geographicallydistributed ATMs and a Central Bank System (CBS),which is responsible for maintaining client information andaccounts; and for authorizing and registering all transac-tions. Each ATM is composed of a ATM controller, a cardreader, a user interface (composed of a display window anda keypad), a cash dispenser, an envelop input slot (used fordeposit and bill payments), and a receipt printer. The ATMcontroller is responsible for controlling the execution of allATM scenarios, and for communicating with the CBS. For this paper, we consider the following scenarios: • A start-up scenario that describes the steps required tobring the system to its operational state. These stepsinclude the configuration of each components of theATM system, and the establishment of a communica-tion with the CBS. • An abstract Transaction  scenario that captures thesequence of responsibilities common to all transactions.It includes reading the card information, verifying thePIN (Personal identification Number), getting the usertransaction selection, executing the required transac-tion, printing a receipt, and returning the card. • One scenario for each of the different types of transac-tion offered by the ATM system: withdraw, deposit, billpayment, and account update. Each of these scenariosgives the details of a specific transaction, as well as aset of relevant alternative scenarios. • A shutdown scenario that describes the steps to be car-ried out when closing down the ATM. The shut downsteps includes turning off the different ATM compo-nents, and terminating communication with the CBS. 3. Proposed Approach In order to design the hierarchical state machine of acomplex component, the behavior integration patterns wepropose draw on both the inter-scenario relationships anddetails contained in scenario models such as interactiondiagrams [11]. We remark that, except for Use Case Maps(UCMs) [2,3,17], few notations explicitly  capture inter-sce-nario relationships. For detailed interaction diagrams, weuse Message Sequence Charts [10] (MSCs). However, thepatterns we have developed [2] are not dependent on thesetwo specific notations, but rather on the semantics of sce-narios. Let us elaborate.We claim that the integration of a new scenario   S1 intoan existing hierarchical state machine  f   must depend on thepair-wise relationships existing between S1 and the scenar-ios already handled by  f  . We identify three important typesof inter-scenario relationships: • The  Scenario Interaction  relationship. This type of rela-tionship is the strongest of the three from a semanticviewpoint. It exists between scenarios that interact in aspecific manner ( e.g ., one scenario excludes , waits for  , aborts ,  rendezvous or  joins  another). These specificinteractions, we repeat, can be captured in UCMs. Wesuggest that the exact interaction relationship betweentwo scenarios determines how these scenarios are to beintegrated into a hierarchical state machine [2]. Forexample, if two scenarios are taken to be mutuallyexclusive, then they will be integrated using the  Mutu- Behavior Integration PatternsStructuring Scenario Interactions Scenario Mode- Mutually State    Machine  Scenario Scenario    Waiting TimedPartitioning Integration  ExclusiveScenarios Composition Aborting Place WaitingPlaceoriented  ally Exclusive Scenario  pattern, which suggests how toorganize the relevant hierarchical state machine 1  (usinga choice point  ) (  Ibid  .). This pattern is summarized inFigure 2 below. In this figure, the right-hand side statemachine ( executeOption ) illustrates the part of the hier-archical state machine that ensures mutual exclusionbetween the scenarios that correspond to the differentoptions (each option scenario is encapsulated in an option  composite state), while the left-hand side statemachine ( top ) illustrates the higher level state machinethat leads to the execution of an option. Figure 2. Structure of the scenario option state machine • The  scenario dependency  relationship. A scenariodependency relationship exists between a scenario S1and a scenario S2, if scenario S2 is used in the descrip-tion of S1. Examples of this type of relationship includestubs in UCMs [2,3], and the “uses” and “refines” rela-tionships defined by Jacobson [11]. In the ATM system,such a relationship exists between the abstract Transac-tion  scenario and each of the scenarios that correspond aspecific transaction (i.e. withdraw, deposit, bill pay-ment, and account update). • The  scenario clustering   relationship. This relationship is used to capture the coexistence of two or more sce-narios inside a same conceptual regrouping called a cluster  . This regrouping corresponds to a specific ‘aspect of the system. At this point in time, aspects that we have observed to lead to such regrouping include control, configuration, communication, error recovery, normal operation, etc. For example, the “start-up” and “shutdown” scenarios are both part of the control clus-ter of the ATM system, and the “deposit” and “with-draw” scenarios are both part of the operational cluster.The proposed integration patterns define the behavior of components using a two-step approach. First, we use thedetails of message sequence charts [10] (MSCs) to definestate machines on a per scenario basis. The resulting statemachines are called role state machines  as they describebehavior that must implemented by a component to play aspecific role in a scenario. Second, we consider the inter-scenario relationship information to compose the statemachines obtained in the first step into more complex hier-archical state machines. This approach is summarized inFigure3.Figure 3. From a Set of Scenarios to a Set of Component Behaviors 4. The State Machine Integration Pattern The State Machine Integration Pattern  specificallyaddresses the design of a hierarchical state machine from aset of simpler state machines. That is, the main issue thatneeds to be resolved in this pattern is the one of integratinga set of state machines associated with different scenarios,into a single hierarchical state machine. Our presentationroughly follows the style of Gamma et al.  [8]. 1. In this paper, hierarchical state machines are described using the UML notation [20]. topI chooseOptionpreOptionpostOptionpreOptionStepsCompleted executeOption optionSelectedoptionExecutionCompletedpostOptionidleStepsCompleted ... optionSselectedoption ExecutionCompleted   I executeOption option1 optionNoption3option2[option1] [option2][option3] [option4] Component BehaviorHierarchical State Machines MSC MSC MSC Role InteractionDiagramsState Machines Inter-Scenario Relationships  Motivation New scenarios constantly need to be integrated in exist-ing systems to satisfy new requirements. From our perspec-tive, the integration of a new scenario in a system results inthe integration of a new set of role state machines in thesystem. That is, the component behavior of several compo-nents will need to be modified to handle new sequences of actions, new sequences defined by means of what we callrole state machines [2]. For this reason, state machine inte-gration constitutes a main issue in real-time system design. Problem Integrating a set of new role state machines into anexisting component behavior is a difficult task. Often, thestructure of the hierarchical state machine of a componentis not capable of adapting to the integration of new scenar-ios. That is, if the component behavior is not properlystructured, the integration of a new scenario may require amajor restructuring of the components hierarchical statemachine. The cost of major restructuring is very high bothin terms of time and possible new errors. Indeed, whenrestructuring a state machine, designers must ensure thatthe resulting component behavior can still correctly exe-cute all the scenarios already integrated in the component.Unless a systematic approach is used, major restructuringusually entails major regression testing.We have observed that problems in the structuring of hierarchical state machines often result from a lack of understanding of scenario relationships, or a lack of a sys-tematic approach in expressing those scenario relationshipsin terms of state machine constructs. And thus, the integra-tion of a new state machine by a designer who does nothave a good understanding of the overall system behavioroften results in a components state machine that is difficultto maintain and extend. Conversely, if a components statemachine is properly structured, the impact of integrating anew scenario should be limited to a well-defined subset of the overall hierarchical state machine of that component. Applicability The State Machine Integration pattern can be used forthe design of hierarchical state machines in any type of component that is composed of a set of existing statemachines. Forces • Allow for the design of component behavior from exist-ing state machines. • Structure hierarchical state machines (i.e., componentbehavior) so that the integration of new role statemachines is performed at minimal cost. • Provide a scaleable integration strategy: the cost of maintaining the component and the cost of adding newscenarios (i.e., role state machines) should not increaseexponentially as the size of the component grows. • Promote high cohesion of the scenarios addressed in acomposite state. • Maintain traceability between state machine structureand scenarios [7]. • Increase component behavior maintainability andextensibility by structuring hierarchical state machinesin a way that is consistent with the partitioning of sce-narios over several design iterations. Solution The State Machine Integration pattern defines a compo-nents behavior as a set of integrated simpler statemachines, each of which is associated with a set of scenar-ios. More specifically, the approach taken in this pattern issimilar to the approach used in system structure design,where a system is defined as a set of communicating com-ponents. In the case of system structure, the overall behav-ior of the system is the result of component integration. Inthis pattern, a hierarchical state machine is defined as a setof simpler state machines, where each state machine imple-ments a set of scenarios. In this case, the overall behaviorof a component is the result of state machine integration.The starting point for the application of this pattern is aset of role state machines, each of which being associatedwith a specific scenario 1 , that must be integrated in anexisting components hierarchical state machine. Becausethe control  state machine controls the ability of a compo-nent to perform all other functions, the top level of thecomponents hierarchical state machine is typically takenup by the control  state machine. Then, the other statemachines, like the normal operation  state machine or the configuration  state machine, are integrated in the appropri-ate composite state of the control  state machine. (The StateMachine Integration pattern is completely recursive.) The guiding principle behind this pattern consists inseparating the two important aspects of scenario models:individual scenario description, and inter-scenario relation-ships (discussed above). The structure of a componentshierarchical state machine is then defined so that it reflectsthe relationships between scenarios. Thus, the StateMachine Integration pattern can be described as a foursteps process: 1.Each role state machine is associated with (that is, is an implementa-tion of) a specific scenario. Therefore, there exists a one-to-one rela-tionship between a role state machine and a scenario. In the description of the current pattern, we use the terms role state machine  or scenario  depending on the aspect we want to emphasize.  1.Analyze the relationships between the scenarios that areto be integrated and the ones already implemented inthe system. 2.Determine where , i.e. in which state, in a componentshierarchical state machine, the role state machine asso-ciated with a new scenario must be integrated. Thedecision proceeds from the analysis of the relationshipsbetween the scenario corresponding to a role statemachine to integrate and the scenarios currently han-dled by the existing state machine.3.Having established the state s  in which to integrate therole state machine m  and the relevant inter-scenariorelationships, use these relationships to integrate s  in m .Recall that a specific relationship lead to specific inte-gration strategy (see Figure 1.). The application of sucha strategy produces a new hierarchical state machine inwhich the current role state machine has been inte-grated. 4.Before proceeding to the integration of the next rolestate machine, some testing must be performed, as wellas some possible restructuring. More specifically, it isimperative to verify i) that past and new scenarios of the component are still handled correctly and II) that nounwanted interactions between scenarios have devel-oped. Such a verification is not easy due to the non-deterministic nature of events. As for restructuring, itmay involve grouping a set of states into a compositestate, defining state entry or exit actions, distributingthe set of actions executed on a transition over a set of transition segments, etc. (see [2] for further details). Example We now apply the State Machine Integration pattern tothe design of the ATM controller component. This compo-nent is responsible for controlling all aspects of the ATM. Itcoordinates the work of the different ATM components,and communicates with the CBS to carry out transactions.For the purpose of illustrating the State Machine Inte-gration pattern, we consider the two main control scenar-ios: startup  and shutdown , and the set of transaction scenarios. The integration of other scenarios can be carriedout in a similar manner. The design of the component behavior of the ATM con-troller is conducted in three phases:1.Definition of the control state machine.2.Definition of the operational state machine.3.Integration of the two state machines in a single one. Integration of Control Scenarios First, we integrate the two role state machines associ-ated with the control scenarios: the startup  state machineand the shutdown  state machine. These state machines areillustrated in the top part of Figure4. Both of these statemachines are hierarchical state machines. In the startup state machine, the details of the startup configuration areencapsulated in the configuring  composite state. Similarlyin the shutdown  state machine, the details of the shutdownscenario are encapsulated in the shutdown  composite state.In this case, the integration of the state machines israther simple since the end state of one scenario is the ini-tial state of the other scenario. The result of the integrationof the two state machines is illustrated in the bottom part of Figure4. The resulting state machine is a very general onethat could be used for different types of systems.Figure 4. Integration of Control Scenarios ATM Transactions Second, we build a state machine for the operationalaspect of the ATM controller. This state machine encapsu-lates all the ATM transaction scenarios. In this case, thegeneral transaction scenario is a high-level scenario thatuses the other transaction scenarios for the purpose of spe-cific transactions. For this reason, we establish a “uses”relationship between the general transaction scenario andthe other transaction scenarios. This is reflected at the hier-archical state machine level by the definition of a transac-tion  composite state in the general transaction statemachine. This composite state encapsulates the whole setof transaction scenarios.The general transaction scenario could be described bythe operational  state machine given in Figure5. This statemachine describes the steps that are common to all transac-tions. We observe that this state machine is defined inde- configuringconfigCompletedunconfiguredoperational control shutdownshutdownconfigureconfiguredstartconfiguringconfigCompletedunconfiguredoperational startup configurestart unconfiguredoperational shutdown shutdownshutdownshutdownCompleted configuredshutdownCompleted
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks