week3-HierarchicalStateMachines

山东大学嵌入式课设PPT

Introduction to Embedded Systems

Edward A. Lee & Sanjit A. SeshiaUC Berkeley

Copyright © 2008-11, Edward A. Lee & Sanjit A. Seshia, All rights reserved

Chapter 5: Hierarchical State Machines

山东大学嵌入式课设PPT

The StateCharts paper

Lee & Seshia, UC Berkeley: 2

山东大学嵌入式课设PPT

Recall Synchronous Composition:

Synchronous composition

Lee & Seshia, UC Berkeley: 3

山东大学嵌入式课设PPT

Recall Asynchronous Composition:

Asynchronous composition with interleaving semantics

Lee & Seshia, UC Berkeley: 4

山东大学嵌入式课设PPT

Recall program that does something for 2 seconds, then stopsvolatile uint timerCount = 0; void ISR(void) { … disable interrupts if(timerCount != 0) { timerCount--; } … enable interrupts } int main(void) { // initialization code SysTickIntRegister(&ISR); ... // other init timerCount = 2000; while(timerCount != 0) { ... code to run for 2 seconds } }

Is synchronous composition the right model for this?Is asynchronous composition (with interleaving semantics) the right model for this? Answer: no to both.

Lee & Seshia, UC Berkeley: 5

山东大学嵌入式课设PPT

Position in the program is part of the statevolatile uint timerCount = 0; void ISR(void) { … disable interrupts D if(timerCount != 0) { E timerCount--; } … enable interrupts } int main(void) { // initialization code SysTickIntRegister(&ISR); … // other init timerCount = 2000; A while(timerCount != 0) { B … code to run for 2 seconds } C … whatever comes next }

A key question: Assuming interrupt occurs infinitely often, is position C always reached?

Lee & Seshia, UC Berkeley: 6

山东大学嵌入式课设PPT

State machine modelvolatile uint timerCount = 0; void ISR(void) { … disable interrupts D if(timerCount != 0) { E timerCount--; } … enable interrupts } int main(void) { // initialization code SysTickIntRegister(&ISR); … // other init timerCount = 2000; A while(timerCount != 0) { B … code to run for 2 seconds } C … whatever comes next }

Is asynchronous composition the right thing to do here?Lee & Seshia, UC Berkeley: 7

山东大学嵌入式课设PPT

Asynchronous composition

A

CThis has transitions that will not occur in practice, such as A,D to B,D. Interrupts have priority over application code.

BLee & Seshia, UC Berkeley: 8

山东大学嵌入式课设PPT

Modeling an interrupt controllerFSM model of a single interrupt handler in an interrupt controller:

Lee & Seshia, UC Berkeley: 9

山东大学嵌入式课设PPT

Modeling an interrupt controllerint main(void) { // initialization code SysTickIntRegister(&ISR); … // other init timerCount = 2000; while(timerCount != 0) { … code to run for 2 seconds } }

Note that states can share refinements.volatile uint timerCount = 0; void ISR(void) { … disable interrupts if(timerCount != 0) { timerCount--; } … enable interrupts }

Lee & Seshia, UC Berkeley: 10

山东大学嵌入式课设PPT

Hierarchical State MachinesOR state (being B means being in C or D) Reaction: 1. First, the refinement of the current state (if any) reacts. 2. Then the top-level machine reacts. If both produce outputs, they are required to not conflict. The two steps are part of the same reaction.

refinement

Lee & Seshia, UC Berkeley: 11

山东大学嵌入式课设PPT

Hierarchical

State Machines

simultaneous transitions

Example trace:

Simultaneous transitions can produce multiple outputs. These are required to not conflict.Lee & Seshia, UC Berkeley: 12

山东大学嵌入式课设PPT

Hierarchical State Machines

history transition

Example trace:

A history transition implies that when a state with a refinement is left, it is nonetheless necessary to remember the state of the refinement.Lee & Seshia, UC Berkeley: 13

山东大学嵌入式课设PPT

Flattening the state machine (assuming history transitions):

A history transition implies that when a state with a refinement is left, it is nonetheless necessary to remember the state of the refinement. Hence A,C and A,D.Lee & Seshia, UC Berkeley: 14

山东大学嵌入式课设PPT

Hierarchical State Machines with Reset Transitions A reset transition alwaysinitializes the refinement of the destination state to its initial state.

reset transition

Example trace:

A reset transition implies that when a state with a refinement is left, you can forget the state of the refinement.Lee & Seshia, UC Berkeley: 15

山东大学嵌入式课设PPT

Flattening the state machine (assuming reset transitions):

A reset transition implies that when a state with a refinement is left, it is not necessary to remember the state of the refinement. Hence there are fewer states.Lee & Seshia, UC Berkeley: 16

山东大学嵌入式课设PPT

Preemptive Transitions

A preemptive transition specifies that the guard should be evaluated before the current state refinement reacts, and if it is true, then the current state should not react.

Lee & Seshia, UC Berkeley: 17

山东大学嵌入式课设PPT

Modeling an interrupt controllerint main(void) { // initialization code SysTickIntRegister(&ISR); … // other init timerCount = 2000; while(timerCount != 0) { … code to run for 2 seconds } }

Note that states can share refinements.volatile uint timerCount = 0; void ISR(void) { … disable interrupts if(timerCount != 0) { timerCount--; } … enable interrupts }

Lee & Seshia, UC Berkeley: 18

山东大学嵌入式课设PPT

Simplified interrupt controllerThis abstraction assumes that an interrupt is always handled immediately upon being asserted:

A B

C

int main(void) { // initialization code SysTickIntRegister(&ISR); … // other init timerCount = 2000; while(timerCount != 0) { … code to run for 2 seconds } }

D E

volatile uint timerCount = 0; void ISR(void) { … disable interrupts if(timerCount != 0) { timerCount--; } … enable interrupts }

Lee & Seshia, UC Berkeley: 19

山东大学嵌入式课设PPT

Hierarchical interrupt controllerThis model assumes further that interrupts are disabled in the ISR:A key question: Assuming interrupt occurs infinitely often, is state C always reached?

Lee & Seshia, UC Berkeley: 20

山东大学嵌入式课设PPT

Hierarchical interrupt controllerThis model assumes interrupts are disabled in the ISR:Reset, preemptive transitionHistory transition

Lee & Seshia, UC Berkeley: 21

本文来源：https://www.bwwdw.com/article/7twe.html