Lec-7
Lecture Overview
- System models are abstract descriptions of systems whose requirements are being analysed
- Objectives - To explain why the context of a system should be modelled as part of RE process
- To describe
- Behavioural modelling (FSM, Petri-nets)
- Data modelling
- Object modelling(Unified Modelling Language, UML)
Lecture Key points
- A model is an abstract system view. Complementary(互补) types of model provide different system information.
- Context models show the position of a system in its environment with other systems and processes.
- Data flow models may be used to model the data processing in a system.
- State machine models model the system’s behaviour in response to internal or external events
System models
- User requirements must be written in such way that non-technical experts can understand them, e.g., by using natural language
- Detailed system requirements may be expressed in a more technical way
- One widely used technique is document the system specification as a set of system models
- These are graphical represnetations which describe business processes and the system to be developed
- They are an important bridge between the analysis and design processes
System Modelling
- System modelling helps the analyst to understand the functionality of the system and models are used to communicate with customers
- Different models present the system from different perspectives:
- External perspective: showing the system/s context or environment
- Behavioural perspective showing the behaviour of the system
- Structural perspective showing the system or data architecture
- “A Picture Paints a Thousand Words”
System Model advantages
- They can be easier to understand than using a verbose natural language description
- System models can leave out unnecessary details of the system so way may focus on what is important
- A system representation should maintain all the information of a system
- An abstraction deliberately simplifies the system and picks out its most salient characteristics
- Different models can focus on different approaches to abstraction
System Model Weaknesses
- They do not model non-functional system requirements
- They do not usually include information about whether a method is appropriate for a given problem
- They may produce too much documentation
- System models are sometimes too detailed and difficult for users to understand
Model Types
- Data processing model - showing how the data is processed at different stages
- Composition model(组合模型) - showing how entities are composed of other entities
- Architectural model - showing principal sub-systems
- Classification model - showing how entities have common characteristics
- Stimulus/response model(刺激反应模型) - showing the system’s reaction to events
Context Models
- Context models 说明系统边界
- Identifying the boundaries of the system to be developed is not always straightforward
- Social and organisational concerns may affect the decision on where to position system boundaries
- Architectural models show the system and its relationship with other systems
- Example - Architechtural Model of an ATM System
Process Models
- Process Models show the overall process and the processes that are supported by the system
- In process models it is implicit 1 process is completed before another process begins
- Process models are similar to flow charts
- Data flow models may be used to show the processes and flow of information from one process to another
- 数据流模型隐式地表示过程将并行发生(并发处理)
Behavioural Models
- Behavioural models are used to descibe the overall behaviour of system
- Two types of behavioural model
- Data processing models that show how data is processed as it moves through the sysyem
- State machine models that show the systems response to events
- Both of these models are required for a description of the system’s behaviour
Data-Processing Models
- Data flow diagrams are used to model the system’s data processing
- These show the processing steps as data flows through a systme
- IMPORTANT part of many analysis methodes
- Simple and intuitive notation
- Show end-to-end processing of data
- Example: Order Processing Data Flow Diagram
Data Flow Diagrams
- Data Flow Diagrams track and documenthow the data associated with a process is helpful to develop an overall understanding of the system
- Data flow diagrams may also be used in showing the data exchange between a system and other systems in its environment
- 数据流图的优势在于，它们简单而直观，因此可以显示给能够帮助验证分析的用户
- 开发数据流图通常是一个自顶向下的过程
- We begin by evaluating the overall process we wish to model before considering sub-processes
- 数据流图显示了一个功能透视图，其中每个转换表示单个功能或过程，这在需求分析期间特别有用，因为它显示了端到端处理。
DFD Context diagram
Statechart Diagrams
状态图(或状态机模型)显示系统响应外部和内部事件的行为
它们显示了系统对刺激的反应(事件-动作范式)，因此经常被用于建模实时系统
状态图将系统状态显示为节点，事件显示为节点之间的弧线。当事件发生时，系统从一种状态转移到另一种状态
状态图是统一建模语言(UML)不可分割的一部分
初始状态用实心圆表示，并且是可选的(有时系统会在不同的地方开始，因此初始状态应该省略)。
如果需要，也可以使用最终状态;这用一个实心圆和一个环来表示。
我们使用抽象级别，以便能够观察我们想要建模的系统的基本行为。
圆角矩形用于状态。每个状态包含两个组件，状态名称和在该状态中执行的操作的简要描述。
Example - Microwave Oven Model:
Statechearts
- 状态图还允许将模型分解为子模型。
- 在每个状态的“do”之后都包含了对动作的简要描述(“do”是可选的)。
- 可以由描述状态和刺激的表格补充。
- 弧线上的标签可以表示从一种状态移动到下一种状态(事件)的方法。
- 一个保护用来确保系统只有在满足表达式时才从一种状态移动到另一种状态。
- 状态可以包含子图(也称为组合状态)。例如，当我们希望为子系统或子状态建模时，这是有用的。
Actions
- put actions after the event using a /
More hints on state charts
- Often have an Idle state where the process is not active
- All states need some exit
- Use multiple state charts to keep the design simple
- Do NOT need to have a state chart as sub state of other chart
- System can be described by multiple state machines running concurrently
- System can be described by multiple state machines running concurrently
Finite State Machines 有限状态机
- Finite State Machines, also known as Finite State Automata(有限状体自动机)(FSA) are models of the behaviours of a system or a complex object, with a limited number of defined coditions or modes, where mode transitions change with circustance. 转型模式会随环境变化而变化.
- definition
计算从输入字符串的开始状态开始。它会根据转移函数变成新的状态。
- A model of computation consisting of
- states : define behaviour and may produce actions
- start(initial) state
- input alphabet
- transition function & next state
- state transitions are movement from one state to another
- rules or conditions must be met to allow a state transition
- input events are either externally or internally generated, which may possibly trigger rules and lead to state transitions
Lec-8- System Models
Introduction
- system models:
- Mealy machines
- Moore machines
- Petri Nets
- UML diagrams
- 这些模型可以指定系统各部分并分析性能
- 知道模型可以代表什么类型属性
FSMs 的变体
- machines having actions associated with transitions(Mealy machine) or states(Moore machine)
- multiple start states,
- tarnsitions conditioned on no input symbol(a null) or more than one transition for a given symbol and state(非确定性有限状态机)
- one or more states designated as accepting states(recognizer), etc
Mealy and Moore Machines
- Finite state automata are like computers in that they receive input and process the input bt changing states.
- The output of finite automata produce is a yes/no at end of processing
- there are two models of finite automata that produce more output than a yes/no.
Moore Machine
- Basically a Moore machine is just a FSA with two extra atttibutes
- It has TWO alphabets, an input and output alphabet.
- 它有一个与每个状态相关联的输出字母。当机器进入每个状态时，它会写入适当的输出字母。
- Example
机器产生的输出包含一个1，表示在输入字符串中找到的每一个子字符串aab。
Mealy Machine
- Mealy machines are computationally equivalent to Moore machines 与摩尔机器互补
- Mealy machines move the output function from the state to the transition. This turns out to be easier to deal with in practice, making Mealy machines more practical.
- A Mealy machine Produces Output on a Transition
- Transitions are labelled i/o where
- i is a character in the input alphabet
- o is a character in the output alpahbet
- 从某种意义上说，米利机器是完整的，因为输入字母表中的每个字符都有一个离开每个状态的过渡。
- 在米利机器中没有接受状态，因为它不是语言识别器，而是输出生成器。它的输出长度和输入长度相同。
- Transitions are labelled i/o where
Petri Net Models
- 很好的方法是通过图形化构建系统来学习建模。
- The Basics
- Capacity
- Arcs have capacity 1 by default; if other than 1, the capacity is marked on the arc, or else we use multiple arrows to denote the capacity
- Places have infinite capacity by default
- Transitions have no capacity, and cannot store tokens all.
- 弧线只能连接位置和过渡，反之亦然。
Enabled Transitions and Firing
- A transition is enabled when the number of tokens is each of its input palces is at least equal to the arc weight going from the palce to the transition
- An enabled transition may fire at any time!
When Arc have Different Weights
When fired, the tokens in the input places are moved to output places, according to arc weights and place capacities.
This results in a new marking of the net, a state description of all places.
Characteristics:
- non-deterministic thus may be used to model discrete distributed systems
- There have been many variations and extensions of Petri nets to more effectively model a wider variety of systems.
- 由于Petri网具有严格的数学符号，许多关于系统的问题都可以通过研究Petri网的性质来验证。
Semantic Data Models
- Used to describe the logical strucuture of data processed by the system
- Entity-relation-attribute model sets out the entities in the system, the relationships between these entities and the entity attributes
- Widely used in database design. Can redily be implemented using relational databases
- No specific notation provided in the UML but objects and associations can be used
- Class diagrams show some of the same ideas
Data dictionary Entries
- A data dictionaries is a list of all of the names used in the system models.
- Descriptions of the entities, relationships and attributes are also included
- It may be used for name-management so that all names used in a system are consistent and do not clash
- It serves as a store of organisational information so that all data is stored in one location.
- Example
Object Models
- Object models describe the system in terms of object classes
- An object class is an abstraction over a set of objects with common attritubes and the services(opeartions) provided by each object
- Various object models may be produced
- Inheritance models
- Aggregation models (聚合)
- Interaction models
- Natural ways of reflecting the real-world entites manipulated(操纵) by the system
- More abstract entites are more difficult to model using this approach
- Object class identification is recognised as a difficult process requiring a deep understanding of the application domain
- Object classes reflecting domain entities are reusable across systems
The Unified Modelling Languange(UML)
- Devised by developers of widely used object-oriented analysis and design methods
- Has become an effective standard for object-oriented modelling
- The unified modeling language contains many different types of diagram we may use to model systems,
- Use-case diagrams
- Class dagrams
- Sequence diagrams
- Statechart diagrams
- Deployment diagrams
- Etc.
- Notation for UML Class Diagrams:
- object classes are rectangles with the name at the top, attributes in the middle section and operations in the bottom section.
- Relationships between object classes(know as associations) are shown as lines linking objects
- Inheritanceis referred to as generalisation and is shown ‘upwards’ rather than ‘downwards’ in a hierachy
Lec 9 & 10 - Modelling Based on Petri Nets
High-level Petri Nets
- High-level Petri nets are Petri nets extended with
- colour(modelling of attributes)
- time(performance analysis)
- hierarchy(Structuring of models)
- 可以用来严格定义系统
- 常被用于分布式系统喝给系统资源分享
- More than one transition in the Petri Net active at the same time, they are non-deterministic
Example
The Extension with Colour
- Each transition has an (in)formal specification which specifies:
- the number of tokens to be produced
- the values of these tokens
- and(optionally) a precondition.
- The complexity is divided over the network and the values of tokens.
- This result in compact, manageable and natural process description
- Example
The Extension with Time
To analyse performance, we must model durations, delays, etc.
A timed Petri net associates a pair tmin and tmax with each transition(there are other possaible definitions for timed Petri net, but we shall only cosider this one).
The values tmin and tmax, tell us the minimum and maximum time that a transition will take to fire once enabled.
This allows us to model performace properties of the system, although the analysis of such systems may be more difficult
The Extension with Hierarchy
- A hierarchy is a mechanism to structure complex Petri nets comparable to data flow diagrams
- A subnet is a net composed out of places, transitions and other subnets
- This allows us to model a system at different levels of abstraction and can reduce the complexity of the model.
- Example
- Message Triplication
The Classical Petri Net Model
Connection are directed and between a place and a transition, or a transition and a place
Tokens(.) are the dynamic objects
Another(equicalent) notation is to use a solid bar for the transitions:
The state of a Petri net is determined by the distribution of tokens over the places
Transitions with Multiple Inputs and Outputs
Transition t1 has three input places(p1,p2 and p3) and two output places
Place p3 is both an input and an output place of t1
Enabling Condition
- Transitions are the active components and places and tokens are passive componets
- A transition is enabled if each of the input places contains tokens
Firing
An enabled transition may fire
Firing corresponds to consuming tokens from the input place and producing tokens for the output places
Firing is atomic(only one transition fires at a time, even if more than one is enabled)
Example
Creating/Consuming Tokens
A transition without any input can fire at any time and produces tokens in the connected places:
A transition without any out but must be enabled to fire and deletes(or consumes) the incoming token(s):
Non-Determinism in Petri Nets
two transition fight for the same token: conflict
Even if there are two tokens, there is still a conflict.
The next transition to fire(t1 or t2) is arbitrary(non-deterministic)
Modelling
States of a process can be modelled by tokens in places and state transitions leading from one state to another are modelled by transitions.
Toknes can be represent resources
Places represent buffers, channels, geographical locations, conditions or states.
Transitions represent events, transformations or transportations
Modelling a Traffic Light
EGB changed on the Traffic lightModelling Two Traffic lights
An informal specification of a traffic light junction:
- A single traffic light turns from “Red” to “Green” to “Amber” and then back to “Red” (we’ll ignore “red and aamber” for now)
- There are two sets of lights. When one of the traffic lights is “Amber” or “Green”, the other must be “red”
As a first step, we may decide to model the system as a Petri net this allows us to make sure the specification is rigorously defined and reduecs potential ambiguities later.
We can also prove properties about the model if we wish
Example
Two traffic lights
Two Safe Traffic Lights
Two safe and Fair Traffic Lights
Exercise
Prove that the Petri net from the previous slide will never allow two red lights to be shown simltaneously
Arc in Petri Nets
- The number of arcs between two objects specifies the number of tokens to be produced/consumed(we can alternatively represent this by writing a number next to a single arc)
- This can be used to model (dis) assembly processes.
Some definitions
- Current state - The configuration of tokens over the places.
- Reachable state - A state reachable form the current state by firing a sequence of enabled transitions
- Deadlock state - A state where no transition is enabled.
- If we write the places in some fixed order(red, black say),then we can use a tuple:(n,m) to denote the number of tokens in each corresponding place(n tokens “red” and m tokens in “black”)
Exercise: Readers and Writers
- How many states are reachable?
- Are there any deadlock states?
- How to model the situation with 2 writers and 3 readers
- How to model a “bounded mailbox” (buffer size = 4)
The Four Seasons
- We would like to denote the current season {spring, summer, autumn, winter}, the temperature {hot,cold} and the light level{bright, dark}.
- As a first step, let us model the seasons(with a token to represent that it is currently autumn)
