PROBLEMS

1.1Several tasks are submitted to a computer system with two processors, P and P,, work
ing in parallel. The process of submitting tasks can be described in discrete time by
a(t), t 0, 1,2,...where a(t) = 1 if atask is submitted at timne t and a(t) = 0 other
wise (at most one task can be submitted in each time step). Suppose such a process
is specified for the time interval t = 0,1,... ,10 as follows: {1, 1, 1,0, 1, 0, 1, 1, 0, 0, 1}.
When a task is seen by the computer system, the following rule for deciding which
of the two processors to use is applied: Alternate between the two processors, with
the first task going to P. It is assumed that if a task is sent to P,i= 1,2, and
that processor is busy, the task joins a queue of infinite capacity. The processing time
of a task at P alternates between 4 and 1time units (starting with 4), whereas the
processing time at P is always 2 time units.
Let y(t) be the total number of customers having departed from the system at time t,
and z1(t) and z2(t) be the queue lengths at processors P, and , respectively (includ
ing a task in process). If one or more events occur at time t, the values of these variables
are taken to be just after the event occurrence(s).
(a) Draw a timing diagram with t = 0,1,..., 10 showing arrivals and departures
(assume that z1(0) = 2(0) = y(0) = 0).
(b) Construct a table with the values of z1(t), 2(t) and y(t) for all t= 0,1,... , 10.
(c) Suppose we now work in continuous time. Arrivals occur at times 0.1, 0.7, 2.2,
5.2 and 9.9. The processing time at P now alternates between 4.2 and 1.1,
whereas that of P, is fixed at 2.0 time units. Consider an event-driven model
with event set E = fa, d, d2}, where a = arrival, d; = departure from processor
P,i = 1,2. Construct a table with the values of z1(k), z2(k), y(k), t(k), where
Ti (*), T(k), y(k) are the queue lengths and cumulative number of departures
after the kth event occurs, k = 1,2,.. and t(*) is the time instant of the kth
event occurrence. If two events occur at the same time, assume that a departure
always comes before an arrival. Compare the number of updates required in this
model to a time-driven model with a time step of magnitude 0.1 time units.

1.2 Repeat Problem 1.1 with the following two decision rules regarding which processor
to use for every arriving task (if two events occur at the same time, assume that a
departure always comes before an arrival):
(a) Send the task to P as long as it sees a queue length less than or equal to 2,
otherwise send it to Pa
(b) Send the task to the processor with the shortest queue seen. In case of a tie, send
it to P.
1.3 A simple manufacturing process involves two machines MË and M2 and a robot arm
that removes a completed piece from Mand brings it to M2. There is no buffering at

SELECTED REFERENCES | 51

either machine. Thus, if a piece is supplied to M, while the machine is busy, that piece
is rejected. On the other hand, if the robot transports a piece to M, while it is busy,
it waits there until M2 can accept the piece. Note that after the robot arm places a
piece in M2 it still takes some time for it to return to its original position from which
it can pick up a new piece from MË. Thus, M, may occasionally be forced to hold a
completed piece (and not accept any new arrivals) until the robot arm is available.
Let zË and z2 describe the states of M, and M2, respectively, and 3 the state
of the robot arm. Assume that the processing times at M1, M, are 0.5 and 1.5s,
respectively, and that the robot arm requires 0.2 s to transport a piece from M to
M2, and 0.1s to return to its original position at MË. Finally, suppose that arrivals of
pieces are scheduled to arrive at M, at time instants: 0.1, 0.7, 1.1, 1.6, and 2.5s.

(a) Identify all possible values that each of z1 , T2, and Tz can take.
(b) Define an appropriate event set E (with the smallest possible number of elements)
for this system.
(c) For the time interval (0.0, 3.0] s, construct a table with the values of r; (k), z2(k),
r3(k), and t(k), where z1(k), z2(k), z3(k) are the states of M1, M2, and the robot
arm after the kth event occurs, k =1,2,. and t(k) is the time instant of the kth
event occurrence. If two events occur at the same time, assume that a completion
of processing at a machine always comes before the arrival of a new piece.
(d) Identify all time intervals during which M, is forced to wait until the robot arm
removes a completed piece.
 2. Consider a variant of the thermostat of example 3.5. In this variant, there is only one

less than or equal to 20 degrees Celsius, it turns the heater on, and leaves it on for

temperature is less than or equal to 20 degrees.

Lee & Seshia, Introduction to Embedded Systems 73

EXERCISES

(a) Design an FSM that behaves as described, assuming it reacts exactly once
every 30 seconds.
(0) How many possible states does your thermostat have? Is this the smalles

(c) Does this model thermostat have le invariance property?

3. Consider the following state machine:

output: y: {0. I}

whether the following statement is true or false, and give a supporting

aroument.

The output will eventually be a constant 0, or it will eventually be a

constant 1. That is, for some n e N, after the n-th reaction, either the
output will be 0 in every subsequent reaction, or it will be I in every
osequent reaction.
Note th Chapterr 13
le that 13 gives mechanisms for making such statements precise and for

4. How many reachable states does the following state machine have?

3)
n:=n

5. Consider the deterministic finite-state machine in Figure 3.14 that models a simple
traffic light

74 Lee & Seshia, Introduction to Embedded Systems

. DISCRETE DYNAMICS

Figure 3.14: Deterministic finite-state machine for Exercise 5

(a) Formally write down the description of his FSM asa 5-luple:
(States, Inputs, Outputs, update, initialState).

(b) Give an execution trace of this FSM of length 4 assuming the input tick is
present on cach reaction.
(C) NOw consie ee eted into or ot of
the new stop state. Other transitions and the inputs and outputs stay the same.
he ne stop sate is ne hew nta sae. s ne resung stae maane de
of length 4. If it is nondeterministic, draw the computation tree up to depth 4.

6. This problem considers variants of the FSM in Figure 3.11, which models arivabs
of pedestrians at acrosswalk. We assume that the trafic light at the crosswalk is
per second.
Assume futher that in cach reaction, each machine sees as inputs the output pro
duccd by the other machine im he same reacton (his torm of composition, Which
(u) Suppose that instead of Figure 3.I I, we use the following FSM to molel th
arrival of pedestrians:

Lee & Seshia, Introduction to Embedded Systems

EXERCISES

the pedestrian arrives is the traffic light in state red.

(b) Suppose that instead of Figure 3.1 I, we use the following FSM to model the
arrival of pedestrian
Lanlst siek, sigG, sigY : pu
outputs: pedestrian

Here, the initial state is nondeterministically chosen to be one of none or

sitions fromnone io watinn buttheeiestrian is neverallowod to cross That
is, at no time after the pedestrian arrives is the trafic light in state rad.
7. Consider the state machine in Figure 3.15. State whether each of the following is
a behavior lor ns macnne ent is denoled by the
shorthand a and present by the shorthand p.
(a) z = (p. D, B. B. P. ...). y= (0,1, 1,0,0,...
(b) r= (P.p,p.p.p,), y= (0, 1, 1, 0, a,
(c) z = (a,p, 4, p, a, -. .- ), y= (a, 1, a, 0, a, -. .)
(d) r= (P.p.p.p.p, ), y = (0,0, a, a, a, )
76 Lee & Seshia, Introduction to Embedded Systems

. DISCRETE DYNAMICS

(e) a = (p.,p.p.P.p, ), y= (0,a, 0, a, 4, ---)

8. (NOTE: This exercise is rather advanced.) This exercise studies properties of dis

two discrete behaviors in asingle system, the resulting combination is not neces
sarily discrete
(a) Consider a pure signal r: R ’ {present, absent) given by

r(t) present if t is a non-negative integer

absent otherwise

for all t¬R. Show that this signal is diserete

(b) Consider a pure signal y: R ’ {present,absent} given by
ulA) -Jpresent if t=l - 1/n for any positive integer n
| absent otherwise
rall t e R. Show that this signal is discrete.
(c) and y in the previou:
That is, w(t) =present if cither zít) = present or u) = present, and is
absent otherwise. Show that wis not discrete
(d) Consider the example shown in Figure 3.1. ASsume hat eacn o ue
sCret imply
the output countis adiscrete sional.

input: x: pure
output: y: {0, 1}

Figure 3.15: State machine for Exercise 7

 2. The objective of this problem is to understand a timed automaton, and then to mod
ify it as specified.
(a) For the timed automaton shown below, describe the output y. Avoid imprecise
or sloppy notation.

continuous variables: r,sE R

output: yER s(0) :=0
r(o) =1iy:=s) r(0) :=(
r():=0
one
two

a() = s()=
i) = 1 il) =

r(t) = 2 /y:= s(t)

r():=0

(b) Assume there is a new pure input reset, and that when this input is present,
the hybrid system starts over, behaving as if it were starting at time 0 again.
Modify the hybrid system from part (a) to do this.
3. In Exercise 6 of Chapter 2, we considered a DC motor that is controlled by an in
put voltage. Controlling a motor by varying an input voltage., in reality, is often
not practical. It requires analog circuits that are capable of har
handling considerable
power. Instead, it is common to use a fixed voltage, but to turn it on and off period
ically to vary the amount of power delivered to the motor. This technique is called
pulse width modulation (PWM).
Construct a timed automaton that provides the voltage input to the motor model
from Exercise 6. Your hybrid system should assume that the PWM circuit delivers
a 25 kHz square wave with a duty cycle between zero and 100%, inclusive. The
input to your hybrid system should be the duty cycle, and the output should be the
voltage.

102 Lee & Seshia, Introduction to Embedded Systems

4. HYBRID SYSTEMS

4. Consider the following timed automaton:

continuous variable: seR

input: a: pure
|output: b :pure aVs(r) = 1
s{):=0
(s(0) :=0
(s1 s2
s() s(1) =0.5)

s(t) = | /b
s() := 0

Assume that the input signals a and b are discrete continuous-time signals, meaning
that each can be given as a function of form a: R ’ {present, absent}, where at
almost all times t eR, a(t) = absent, Assume that the state machine can take
at most one transition at each distinct time t, and that machine begins executing at
time t = 0.

(a) Sketch the output b if the input a is present only at times

t= 0.75, [Link].3,3.75, 4.5,...
Include at least times from t = 0 to t =5.

(b) Sketch the output bif the input a is present only at times t =0,1, 2,3,
(c) Assuming that the input a can be any discrete signal at all, find a lower bound
on the amount of time between events b. What input signal a (if any) achieves
this lower bound?

5. You have an analog source that produces a pure tone. You can switch the source on
or off by the input event on or off. Construct a timed automaton that provides the on
and off signals as outputs, to be connected to the inputs of the tone generator. Your
system should behave as follows. Upon receiving an input event ring, it should
produce an 80 ms-long sound consisting of three 20 ms-long bursts of the pure tone
separated by two 10 ms intervals of silence. What does your system do if it receives
two ring events that are 50 ms apart?

Lee & Seshia, Introduction to Embedded Systems 103

EXERCISES

6. Automobiles today have the features listed below. Implement each feature as a
timed automaton.

(a) The dome light is turned on as soon as any door is opened. It stays on for 30
seconds after all doors are shut. What sensors are needed?
(b) Once the engine is started, a beeper is sounded and a red light warning is
indicated if there are passengers that have not buckled their seat belt. The
beeper stops sounding after 30 seconds, or as soon the seat belts are buckled,
whichever is sooner. The warning light is on all the time the seat belt is un
buckled. Hint: Assume the sensors provide a warn event when the ignition
is turned on and there is a seat with passenger not buckled in, or if the igni
tion is already on anda passenger sits in a seat without buckling the seatbelt.
Assume further that the sensors provide a no Warn event when a passenger de
parts froma seat, or when the buckle is buckled, or when the ignition is turned
off
 4. HYBRID SYSTEMS

9. Figure 4.16 depicts the intersection of two one-way streets, called Main and Sec
ondary. A light on each street controls its traffic. Each light goes through a cycle
consisting of a red (R), green (G), and yellow (Y) phases. It is a safety requirement
that when one light is in its green or yellow phase, the other is in its red phase. The
yellow phase is always 5 seconds long.
The traffic lights operate as follows. A sensor in the secondary road detects a ve
hicle. While no vehicle is detected, there is a 4 minute-long cycle with the main
light having 3 minutes of green, 5 seconds of yellow, and 55 seconds of red. The
secondary light is red for3 minutes and 5 seconds (while the main light is green
and yellow), green for 50 seconds, then yellow for 5 seconds.
If a vehicle is detected on the secondary road, the traffic light quickly gives a right
of way to the secondary road. When this happens, the main light aborts its green
phase and immediately switches to its 5 second yellow phase. If the vehicle is
detected while the main light is yellow or red, the system continues as if there were
no vehicle.

Design a hybrid system that controls the lights. Let this hybrid system have six
pure outputs, one for each light, named mG, mY, and mR, to designate the main
Secondary

light YR

Main R GY

detector

Figure 4.16: Traffic lights control the intersection of a main street and a secondary
street. A detector senses when a vehicle crosses it. The red phase of one light
must coincide with the green and yellow phases of the other light.

Lee & Seshia, Introduction to Embedded Systems 105

EXERCISES

light being green, yellow, or red, respectively, and sG, sY, and sk, to designate the
secondary light being green, yellow, or red, respectively. These signals should be
generated to turn on a light. You can implicitly assume that when one light is turned
on, whichever has been on is turned off.

10. For the bouncing ball of Example 4.7, let ty be the time when the ball hits the
ground for the n-th time, and let v, =ylt,) be the velocity at that time.
(a) Find a relation between vn+1and v, for n> 1, and then calculate v, in terms
of v1.
(b) Obtain tn in terms of U1 and a. Use this to show that the bouncing ball is a
Zeno system. Hint: The geometric series identity might be useful, where
for |b| < 1,
1
1-b
m=0

(c) Calculate the maximum height reached by the ball after successive bumps.
 12. Show that the trajectory of the AGV of Figure 4.13 while it is in left or right mode
is a circle. What is the radius of this circle, and how long does it take to complete a
circle?

13. Consider Figure 4,.17 depicting a system comprising two tanks containing water.
Each tank is leaking at a constant rate. Water is added at a constant rate to the
system through a hose, which at any point in time is filling either one tank or the
other. It is assumed that the hose can switch between the tanks instantaneously.
For i ¬ {1,2}, let z; denote the volume of water in Tanki and v; >0 denote the
constant flow of water out of Tank i. Let w denote the constant flow of water into the
system. The objective is to keep the water volumes above rË and r2, respectively,
assuming that the water volumes are above rË and r2 initially. This is to be achieved

106 Lee & Seshia, Introduction to Embedded Systems

4. HYBRID SYSTEMS

Figure 4.17: Water tank system.

by a controller that switches the inflow to Tank 1 whenever z1(t) < r1(t) and to
Tank 2 whenever T2(t) <2(t).
The hybrid automaton representing this two-tank system is given in Figure 4.18.
Answer the following questions:
(a) Construct a model of this hybrid automaton in Ptolemy I, LabVIEW, or
Simulink. Use the following parameter values: rË = r2 =0, U = Uz = 0.5,
and w = 0.75. Set the initial state to be (q, (0, 1)). (That is, initial value
T1(0) is 0 and z2(0) is 1.)
Verify that this hybrid automaton is Zeno. What is the reason for this Zeno
behavior? Simulate your model and plot how æ1 and ag vary as a function of
time t, simulating long enough to illustrate the Zeno behavior.
(b) A Zeno system may be regularized by ensuring that the time between tran
sitions is never less than some positive number e. This can be emulated by
inserting extra modes in which the hybrid automaton dwells for time e. Use
regularization to make your model from part (a) non-Zeno. Again, plot z1
and z2 for the same length of time as in the first part. State the value of e that
you used

Include printouts of your plots with your answe.

Lee & Seshia, Introduction to Embedded Systems 107

EXERCISES

a1(0) > r1 Aa2(0) > T2 z1(0) > ri Ac2(0) > r2

a1(t) <i
42

1(t) = w-U1 i1(t) = -U1

t2(t) -U2 t2(t) = w-vg

T2(t) S T2

Figure 4.18: Hybrid automaton representing water tank system.

3. Explain, in your own words, and based on your own experience, all the possible
challenges that one may encounter if one wants to design and build a robot that
can play agame of ping pong with ahuman. Be as specific as you can about
the challenges that you identify. You may search online for results related to this
problem, and include ones that caught your attention. Limit your total answer to
600 words and use only one page.

5. Give an example of a problem that is important to each of these research areas.

Make sure that in each case this problenm is central to the area: Embedded sys
tems, Real-time systems, Reliability, Mechatronics, Control Theory, Multi-agent
systems, and Internet of Things.
3. Consider the situation where you are designing a futuristic traffic light.
(a) Represent each move by an output of the name of the color ("Red," "Orange,"
"Blue," or "Green'"). Draw a state machine that shows the number of states
needed for a traffic light that outputs a signal that carries red, then orange,
then red, and then goes to blue, then red, and repeats this process.
(b) Assume that the light stays in the red and green states for 60 s, and in all
the other states only for 10s. Write an Acumen object class My_Light that
models this functionality. The only required field in this object is a signal
my_choice which can be "R," "0," "B," or "G" depending on the first letter
of the color. Make sure that the object is self-contained and do not assume
any inputs from the outside.
6. Consider the situation where two cars are about to collide, and their speeds and
masses are depicted in Figure 3.2.

m m

Fig. 3.2 Two cars about to collide

(a) Assume a coefficient of restitution of C. Write a formula for wy and wz, the
speeds after impact, measured in the same direction.
(b) If both masses are the same (m = m) and mis static (v2 = 0), by what
fraction does the speed w, increase if the speed vy is increased by 10%? If
the answer is not a simple fraction, you may write a formula.
(C) what fraction does
the sned inerence if the sneed isinereaced bu 10g%9
7. Consider Figure 3.3 indicating the *before collision" (above) and "after collision"
(below) speeds fora collision between two masses (represented as cars).

3.9 Study Problems

before 40O mph. 40 mph

m
m.
m

after 15 mph

m,

Fig. 3.3 Two cars, before and after collision (Source: [Link])

(a) Write down the equation for conservation of momentum. This is the equation
ion
(b) Calculate the coefficient of restitution "in this collision.
(c) Assume that mz = 100. What is the energy lost in this collision?
(d) Assume that m, = 100. How much is m?
8. Consider the diagram in Figure 3.4 depicting the "before" and "after" situation
for a collision between two masses. The first object has mass m and the second
has twice that mass. The second object is static before collision, and both objects
are attached after the collision.

(a) Calculate the coeficient of restitution c in this collision.

(b) Write down the conservation of momentum equation relating "before" and
"after" speeds.
(c) What speed must vy be in order to ave v cqualal toto 1000?
1000
(d) Assume that m : What is the energy lost i the collision of partc

9. Consider the diagram in Figure 3.5. This type of diagram is called astate diagram,
According to this diagram, the initial state is S, because it has an arrow that has
no explicit source, possible transitions are indicated by arrows going between
states (sometimes the same state), and whenever there is a transition the digit
indicated on the arrow is assigned to the variable Output.

52 3 Hybrid Systems

before

2m
m

after

2m 2
m

Fig. 3.4 Two spheres, before and after an inelastic collision (Source: [Link])

S,

Fig. 3.5 Afinite state machine with two states, and initiated at state I

(a) Starting from the initial state, what state is the machine in after it has assigned
to Output the values 0, 0, 1,0 in that order? Write out the state of the machine
after each of these four outputs individualy. Jnnut and that both
(b)
the Otransition if Lpput is less than or equal to 5. and take the I transition if
Input is greater than five. Assume further that the system makes a transition
decisions and actions together, and does so every I s. Describe this situation
using the Acumen language in one model that has Input and Output as
parameters