四系统行为描述（计算）模型计算模型（Computation Model）概述时序程序模型有限状态机（FSM）并发进程模型数据流模型流程图小结计算模型-概述（1）计算模型（computation Model）描述系统的处理行为（过程）的方法 模型作用帮助设计者理解和描述系统行为减少系统缺陷（bug）Most system bugs come from mistakes made describing the desired behavior rather than from mistakes in implementing that behavior.计算模型-概述（2）描述嵌入式系统的模型时序程序模型（sequential program model) 提供一组语句、语句排列的规则说明语句如何以一次一条的方式执行表现为程序伪码状态机模型（State machine model）提供系统状态及状态之间转换的条件和方式常用于以控制为主的系统主要行为包括监视控制输入、设置控制输出来相应计算模型-概述（3）描述嵌入式系统的模型（续）并发进程模型（parallel process model)描述多个进程执行的时序，以及进程之间的通讯过程。

适用于多进程系统数据流（dataflow model）描述过程中数据流动的路径常用于以数据为主的系统主要行为将输入数据流转换为输出数据流面向对象模型（Object-oriented model)将复杂的软件分为简单而确定的片断计算模型-概述（4）模型与语言名词模型描述行为，是概念语言是概念的表达，是模型的实现手段计算模型-概述（5）模型与语言（续）例生活计算模型-概述（6）模型与语言（续）例系统设计计算模型-概述（7）文字语言与图形语言文字语言详细准确图形语言形象直观关系文字语言可以用等效的图形语言表示图形语言可以用等效的文字语言表示计算模型-概述（8）文字语言与图形语言（续） 例比较图形菜谱和文字菜谱计算模型-概述（8）实例系统-简单的电梯控制系统计算模型-概述（9）实例系统-简单的电梯控制系统文字描述"Move the elevator either up or down to reach thetarget floor.Once at the target floor, open the door for at least10 seconds, and keep it open until the target floorchanges.Ensure the door is never open while moving.Don’t change directions unless there are no higherrequests when moving up or no lower requestswhen moving down."计算模型（Computation Model）概述时序程序模型有限状态机（FSM）并发进程模型数据流模型流程图小结时序程序（1）电梯I/OInputs: int floor; bit b1..bN; up1..upN-1;dn2..dnN;Outputs: bit up, down, open;Global variables: int req;时序程序（2）Unit Controlvoid UnitControl(){up = down = 0; open = 1;while (1){while (req== floor);open = 0;if (req> floor) { up = 1;}else {down = 1;}while (req!= floor);open = 1;delay(10);}}时序程序（3）Request Resolvervoid RequestResolver(){while (1)...req= ......}//void main(){Call concurrently:UnitControl() andRequestResolver()}计算模型（Computation Model）概述时序程序模型有限状态机（FSM）并发进程模型数据流模型小结FSM（1）状态图与程序语句Assignment statementFSM（2）状态图与程序语句loop statementFSM（3）状态图与程序语句 branch statementHow about “Switch…case”？FSM（4）有限状态机计算模型FSM定义FSM is a 6-tuple, <S, I, O, F, H, s0>, where:S is a set of states {s0, s1, …, s l},I is a set of inputs {i0, i1, …, i m},O is a set of outputs {o0, o1, …, o n},F is a next-state function (i.e., transitions), mappingstates and inputs to states (S X I ->S),H is an output function, mapping current states tooutputs (S->O), ands0is an initial state.FSM（5）FSM-UnitControlSIdle, GoingUp, GoingDown, OpenDoorIReq, floor, timer_vOUp (u) , down (d), open (o), timer_c(t)FSM（6）FSM-UnitControl(cont.)FIdle->Idle : req=floorGoingUp: req>floorGoingDown: req<floorGoingUp->GoingUp: req>floorOpenDoor: !(req>floor)GoingDown->GoingDown: req<floorOpenDoor: !(req<floor)OpenDoor->OpenDoor: timer<10sIdle: !(timer<10s)FSM（7）FSM-UnitControl(cont.)HIdle: u=0, d=0, t=0, o=1;Goingup: u=1, d=0, t=0, o=0;Goingdown: u=0, d=1, t=0, o=0;OpenDoor:u=0, d=0, t=1, o=1;S0IdleFSM（8）FSM-UnitControl(cont.) chartProgram language?FSM（9）FSM-UnitControl(cont.)C language#define IDLE 0#define GOINGUP 1#define GOINGDN 2#define DOOROPEN 3void UnitControl(){int state = IDLE;while (1) {……}}FSM（10）FSM-UnitControl(cont.)C language (cont.)switch (state) {IDLE: up=0; down=0; open=1; timer_start=0;if (req==floor) {state = IDLE;}if (req> floor) {state = GOINGUP;}I if (req< floor) {state = GOINGDN;}break;GOINGUP: up=1; down=0; open=0; timer_start=0;if (req> floor) {state = GOINGUP;}if (!(req>floor)) {state = DOOROPEN;}break;GOINGDN: up=1; down=0; open=0; timer_start=0;if (req> floor) {state = GOINGDN;}if (!(req>floor)) {state = DOOROPEN;}break;DOOROPEN: up=0; down=0; open=1; timer_start=1;if (timer < 10) {state = DOOROPEN;}if (!(timer<10)){state = IDLE;}break;}FSM（11）FSM-Sequential Programming languagetemplate#define S0 0...#define SN Nvoid StateMachine(){int state = S0; // or whatever is the initial state.while (1) {switch (state) {S0: // Insert S0’s actions here; Insert transitions Ti leaving S0:if (T0’s condition is true ) {state = T0’s next state; // insert T0’s actions here.}if (T1’s condition is true ) {state = T1’s next state; // insert T1’s actions here.}...if (Tm’s condition is true ) {state = Tm’s next state; // insert Tm’s actions here.}break;...SN://Insert SN’s actions here; Insert transitions Ti leaving SN:break;}}FSM（12）How to describe the RequestResolver with FSM?FSM（13）Moore & MealyMoore FSMS -> O: 输出只与但前状态有关例：UnitControlMealyS X I -> O: 输出不仅与当前状态有关还与输入有关例：自动售货机FSM（14）Finite-state machines with datapaths(FSMD)FSMD ,<S, I, O, V, F, H, s0>, where:S is a set of states {s0, s1, …, s l},I is a set of inputs {i0, i1, …, i m},O is a set of outputs {o0, o1, …, o n},V is a set of variables {v0, v1, …, v n},F is a next-state function, mapping states andinputs and variables to states (S X I X V -> S),H is an action function, mapping current states tooutputs and variables (S -> O+V),s0 is an initial state.Moore or Mealy?FSM（15）Hiererarchical/Concurrent state machines (HCFSM) Three stateFSM（16）Hiererarchical/Concurrent state machines (HCFSM)（cont.)hierarchyFSM（17）Hiererarchical/Concurrent state machines (HCFSM)（cont.)ConcurrentFSM（18）Hiererarchical/Concurrent state machines (HCFSM)（cont.) Example-UnitControl with Fire ModeFire -> go down to floor 1 -> open doorWhich states should be added?FSM（19）Hiererarchical/Concurrent state machines (HCFSM)（cont.)UnitControl with Fire Mode -without hierarchyFSM（19）Hiererarchical/Concurrent state machines (HCFSM)（cont.) UnitControl with Fire Mode -hierarchyFSM（20）Hiererarchical/Concurrent state machines (HCFSM)（cont.) Elevator controller -concurrentFSM（20）Program-state machines (PSM)Use of sequential program code to define astate’s actionsIncluding the hierarchy and concurrencyA merger of the HCFSM and sequentialprogram modelsA PSM having only one state is the same asa sequential program..FSM（21）Program-state machines (PSM) Example -UnitControllFSM（22）Hiererarchical/Concurrent state machines (HCFSM)（cont.) Two types of transitions.Transitionimmediately(TI)Transition is taken immediately if its conditionbecomes true, regardless of the status of thesource program-stateTransition-on-completion (TOC)Transition is taken only if the condition is trueAND the source program-state is complete.FSM（23）状态机的使用WhenControl systemRespond to InputFSM（24）状态机的使用HowList all possible states, giving each a descriptive name.Declare all variables ( I, O, V).For each state, list the possible transitions, withassociated conditions, to other states.For each state and/or transition, list the associatedactions.For each state, ensure that exiting transition conditionsare exclusive (no two conditions could be truesimultaneously) and complete (one of the conditions istrue at any time).FSM（23）状态机的使用例分析自动售货机的工作过程，并画出其状态图。