ELEN90066 Embedded System Design

Semester 2, 2020 Exam

November 2020

Question 1 (18 marks)

Consider the following two fragments of C code, C1  and C2  shown in Figure 1:

Figure 1: C code fragments

where the integer-valued inputs i1, i2, i3 can only take the values {0, 1}, x1 and x2 are integer- valued variables, and o1 and o2, are integer-valued outputs that can only take the values {0, 1}.

The two fragments of C code above can be represented as two synchronous components, C1  and C2 , with their block diagrams given below:

Synchronous Component

Synchronous Component

C1                                                                                      C2

Question 1 (continued)

(a)  [4 marks] Draw a Finite State Machine diagram to represent the behaviour of component C1 .

(b)  [4 marks] Draw a Finite State Machine diagram to represent the behaviour of component C2 .

(c)  [6  marks] Construct a Finite State Machine diagram representing the  cascade  composition of

C1  and C2 , where the output of C1  is fed into the input of C2 , i.e., o1  is connected to i3 .  Which states of the composition are unreachable?

(d)  [2  marks] What  does the term  constructive  mean with respect to the composition of Finite State Machines? Why is constructiveness a useful property?

(e)  [2  marks] Write down one safety property of the composed system from part (c) that is true, and one safety property that is violated by the composed system.

Question 2 (20 marks)

(a)  [2 marks] Consider a delay component in an embedded system, Delay, that can be modelled as

an infinitely repeating sequence of two assignment statements in C shown in Figure 2:

Figure 2: Code fragment for Delay

The integer-valued variables in and out can only take the values {0, 1}.  Variables taking such values will be referred to as Boolean variables for the rest of this question.

Draw a Finite State Machine diagram to represent the behaviour of this component.

(b)  [4  marks]  Consider a modified version of the Delay component, called OddDelay, that has a

Boolean input variable in, a Boolean output variable out and two Boolean state variables x and y.

Both of the state variables are initialised to 0, and the C code modified to that shown in Figure 3, where the  !  operator performs Boolean inversion, i.e.,  !0 is  1 and  !1 is 0.

Question 2 (continued)

Figure 3: Code fragment for OddDelay

Describe in words the behaviour of the component OddDelay.  List a possible execution trace of the component when supplied with the sequence of inputs 0,  1,  1,  0,  1,  1  for the first six reactions.

(c)  [4 marks] Describe the component OddDelay from part (b) as an Extended Finite State Machine with two states.

(d)  [4  marks]  Consider a counter component,  Counter, which maintains a non-negative counter using a state variable x.  The initial value of x is 0.  The component has two Boolean input variables inc and dec and operates in the following way:

• when the input inc is 1, the counter state is incremented by 1; and

• when the input dec is 1, the counter state is decremented by 1.

The output of the component is the updated value of x. When both input variables inc and dec are 1, and when dec is 1 with the state x equal to 0, the component does not assign any value to the output, and as such there is no corresponding reaction.

The counter does not expect both input variables inc and dec to be 1 simultaneously, nor does it expect the state to be decremented when the counter value is 0.

Draw a Finite State Machine representing the behaviour of the Counter component.

Question 2 (continued)

(e)  [6  marks] Design a component CounterTest, represented as a non-deterministic Finite State Machine, that supplies inputs to the Counter component from part (d).

The component CounterTest has no inputs, and its outputs are the Boolean variables inc and dec. It should produce all possible combinations ofthe outputs as long as the Counter component is willing to accept these as inputs:  it should never set both inc and dec to 1 simultaneously, and it should ensure that the number of rounds with dec set to 1 never exceeds the number of rounds with inc set to 1.

Question 3 (8 marks)

Suppose that  a  program  to  compute  the  total  sum  of  two  vectors  of 丑oating  point  numbers  of dimension n is executing on a 32-bit processor. For example, given the two vectors of 丑oating point numbers, [x0, . . . , xn-1] and [y0, . . . , yn-1], the (scalar) total sum S would be calculated as

Suppose that the program uses a single for loop that, on each iteration, accesses individual elements of x and y to accumulate this sum.  Further suppose that the vectors x and y are stored contiguously in memory starting with address 0 and that any caches are initially empty.

The processor has a direct mapped cache and the cache can hold two sets, each of which can hold

four 丑oats.

(a)  [2  marks] What is the role of a cache in the memory hierarchy of an embedded system?

(b)  [2  marks] How many cache misses will occur if n = 2?  Show all of your working and list any assumptions you have made (if any).

(c)  [2  marks] How many cache misses will occur if n = 8?  Show all of your working and list any assumptions you have made (if any).

(d)  [2  marks]  Assume  that  the  vectors  x  and  y  are  created  using  the  C  memory  management function malloc().  Give one advantage and one disadvantage of this approach for embedded systems. Explain your answer.

Question 4 (14 marks)

(a)  [2 marks] Consider a system modelled by the following Finite State Machine (FSM), A:

Is the feedback composition is well-formed? Explain your answer.

(b)  [2 marks] Consider a system modelled by the following Finite State Machine (FSM), B:

Is the feedback composition is well-formed? Explain your answer.

(c)  [4  marks]  Consider the  machine A combined with machine B in a feedback composition as shown below to form machine C. Note that the output port of B is drawn on the left and the input port on the right so that the block diagram looks neater.

Question 4 (continued)

Show that feedback composition C is well-formed, and draw the Finite State Machine model for the composite machine.

(d)  [6 marks] Consider the machine D below

Redraw this feedback composition as a non-deterministic state machine so that it is no longer ill-formed.

Give the set theoretic description for the composed machine, that is the 5-tuple:

(States, Inputs, Outputs, update, initialState)

Question 5 (18 marks)

Consider six tasks τ1 ,  ..., τ6  with release times, execution times, and deadlines presented below.

We say task τi  precedes task τj  if the predecessor must complete the execution of τi  before τj  can execute. The precedence relationships between tasks τ1 , ...,τ6  are as the following

• τ1  precedes τ3 ;

• τ1  precedes τ4 ;

• τ2  precedes τ4 ;

• τ2  precedes τ5 ;

• τ3  precedes τ6 ;

• τ4  precedes τ6 ;

• τ5  precedes τ4 .

(a)  [4  marks]  Draw the directed acyclic graph representing the precedence of the tasks where a directed edge marks a precedence.

(b)  [4  marks] Does a scheduling approach based on Latest Deadline First  (LDF) yield a feasible deadline? Explain why if the answer is no, and construct the schedule if the answer is yes.

(c)  [10  marks]  Does  Earliest  Deadline First with Precedence  (EDF*) yield  a feasible schedule? Explain why if the answer is no, and construct the schedule if the answer is yes.

Question 6 (10 marks)

Consider Finite State Machines Σ 1  and Σ2  depicted in Figure 4.  Show that they are bisimilar.

(a) System Σ 1

c/y0

b/y1

(b) System Σ2

Figure 4: Systems Σ 1  and Σ2   (Question 6).

Question 7 (12 marks)

Figure  5 depicts the  area of operation of a robot.   Regions  P1   and  P2   represent  two  regions  of interest,  B  denotes  the  base  station,  D  represents  a  dangerous  region,  and  R1    and  R2   are  two charging stations.  Let logical proposition x ∈ {p1 , p2 , b, d, r1 , r2 } correspond to the robot being in region X ∈ {P1 , P2 , B, D, R1 , R2 }.

Figure 5: Area of operation of the robot of Question 7.

(a)  [3  marks]  What does the LTL formula  φ as defined below mean?   In addition to a natural language translation of the specification you need to interpret the specification.

φ := GFb ∧ GF(p1  ∨ p2 ) ∧ GF(r1 ∨ r2 ) ∧ G¬d

(b)  [5  marks] A specification might be that the robot should visit either  P1  or P2  and recharge between any two visits to the base, in addition to the requirement that it should never be in D and it needs to infinitely often visit the base station.  Let ψ be the corresponding LTL formula to this specification. What is ψ?

(c)  [4  marks] Assume that ψ from part (b) holds for a robot’s behaviour.  Does the robot satisfy GF(r1 ∨ r2 )? Explain.