Question 1 (18 marks)

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

(a) Code fragment C1                                                                  (b) Code fragment C2

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:

1

O1 

2

3

Synchronous

Component

C1

Synchronous

Component

C2

(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.

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.

(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 of the 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 floating point numbers of dimension n is executing on a 32-bit processor. For example, given the two vectors of floating point numbers, [x0 , . . . , xn − 1] and [y0 , . . . , yn − 1], the (scalar) total sum S would be calculated as

n − 1             n − 1

S =       xi +      yi

i=0              i=0

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 floats.

(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:

x/-y

-x/-y

22

x/y

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:

-w/z

-w/-z

22

w/-z

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.

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

-a/-b

-a/-b

22

a/b

D

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.

c/y0

b/y1

(b) System Σ2

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