DOC PREVIEW
Cal Poly CSC 308 - Requirements Techniques, cont.

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSC 308 Requirements Engineering1Requirements Techniques, cont.• Formal requirements analysis techniques include:– DFD (covered)– ERD (covered)– Finite State Machines– Petri NetsCSC 308 Requirements Engineering2Finite State Machines• A requirements technique for modeling the statesand transitions of a software system• Finite state machines are used in other contexts– automata theory and compilers, for example• More precise than data-flow diagrams– data-flow diagrams specify only the nature of a system’sdata flow (e.g. the what and the where)– finite state machines provide information on how asystem progresses from state to state¤ what is “state”CSC 308 Requirements Engineering3Formal Definition• The definition of a finite state machine (FSM)consists of five parts– a set of states– a set of inputs– a transition function– the initial state– a set of final statesCSC 308 Requirements Engineering4Simple Example• States of a combination lock for a safe– Safe has a dial with three positions (1, 2, & 3)– The dial can be turned in two possible directions¤ At any point six possible motions• Turn left to 1 (1L)• Turn right to 1 (1R)• etc...– Combination is 1L, 3R, 2L– The possible states include the safe being locked andunlocked, sounding the alarm, and the steps along thecombination (e.g. 1L and 3R)CSC 308 Requirements Engineering5Example, cont.• Set of States (Locked, A, B, Unlocked, Alarm)• Set of Inputs (1L, 1R, 2L, 2R, 3L, 3R)• Transition Function (next two slides)• Initial State (Locked)• Final States (Unlocked, Alarm)CSC 308 Requirements Engineering6Example, cont.alarmlocked a b unlocked1L 3R 2LX X Xany other inputinitial statefinal stateXCSC 308 Requirements Engineering7Transition TableInput1L1R2L2R3L3RLockedAAlarmAlarmAlarmAlarmAlarmAAlarmAlarmAlarmAlarmAlarmBBAlarmAlarmAlarmAlarmAlarmUnlockedCSC 308 Requirements Engineering8Finite State Machine Wrap-Up• More advanced examples in other textbooks– The infamous “Elevator Example” is a good one (Schach)• Demonstrates– The specification power of FSMs• Typical Problem– The number of states and transitions grows rapidly inlarge systems– Approach: decompose problem into smaller subsystems• Tool support exists for this and related techniques(e.g. statecharts)CSC 308 Requirements Engineering9Petri Nets• A formal technique suited for specifying theproperties of concurrent or multithreaded systems• Typical concurrency problems– race conditions¤ X accesses Y before Z updates it– deadlock¤ X is waiting on Y which is waiting on X• Petri nets can be used to help avoid ambiguity inspecifications that can lead to this class of problemsin multithreaded systemsCSC 308 Requirements Engineering10Formal Definition of Petri Nets• A Petri net consists of four parts– A set of places– A set of transitions– An input function– An output function• In the subsequent diagrams, the input and outputfunctions are represented by arrowsCSC 308 Requirements Engineering11Petri Net PartsPlaceTransitionTokenCSC 308 Requirements Engineering12Firing a transitionA transition fires when ithas a token at each inputplace; as a result a tokenis placed at each outputplace.CSC 308 Requirements Engineering13Simple Example• A server cannot send anevent to a client until theclient has indicated that it isready to receive one• Approach– Map states into places– Map events into transitions• States– Event waiting– Event received– Event processed– Client Ready• Events– Generate Event– Send Event– Process Event– Notify serverCSC 308 Requirements Engineering14Example, cont.Event Generator Event Waiting Event Received Event ProcessedClient ReadyGenerate EventSend EventProcess EventNotify ServerThree events; one being receivedCSC 308 Requirements Engineering15Example, cont.Event Generator Event Waiting Event Received Event ProcessedClient ReadyGenerate EventSend EventProcess EventNotify ServerAn event gets generatedCSC 308 Requirements Engineering16Example, cont.Event Generator Event Waiting Event Received Event ProcessedClient ReadyGenerate EventSend EventProcess EventNotify ServerAn event gets processed; waiting eventmust wait since “Send Event” cannot fire.CSC 308 Requirements Engineering17Example, cont.Event Generator Event Waiting Event Received Event ProcessedClient ReadyGenerate EventSend EventProcess EventNotify ServerAnother event gets generatedCSC 308 Requirements Engineering18Example, cont.Event Generator Event Waiting Event Received Event ProcessedClient ReadyGenerate EventSend EventProcess EventNotify ServerThe client notifies the serverCSC 308 Requirements Engineering19Example, cont.Event Generator Event Waiting Event Received Event ProcessedClient ReadyGenerate EventSend EventProcess EventNotify ServerAn event is sent...CSC 308 Requirements Engineering20Example, cont.Event Generator Event Waiting Event Received Event ProcessedClient ReadyGenerate EventSend EventProcess EventNotify ServerSecond event is processed...CSC 308 Requirements Engineering21Example, cont.Event Generator Event Waiting Event Received Event ProcessedClient ReadyGenerate EventSend EventProcess EventNotify ServerThe client notifies the serverCSC 308 Requirements Engineering22Example, cont.Event Generator Event Waiting Event Received Event ProcessedClient ReadyGenerate EventSend EventProcess EventNotify ServerFinal event is sent...andeventually processed (ghost token)CSC 308 Requirements Engineering23Final StateEvent Generator Event Waiting Event Received Event ProcessedClient ReadyGenerate EventSend EventProcess EventNotify ServerClient is ready for next eventCSC 308 Requirements Engineering24Petri Net Wrap-Up• Clean notation for specifying concurrent properties• Graphical notation hides underlying formalism– Makes it easier to understand• Tool support and execution engines exists for thistechnique– The latter can help in testing how well a Petri netspecifies a property by running it on test


View Full Document

Cal Poly CSC 308 - Requirements Techniques, cont.

Download Requirements Techniques, cont.
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Requirements Techniques, cont. and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Requirements Techniques, cont. 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?