NAME________________________

CSE403 OPEN BOOK TEST Fri. May 22, 1998 8:30-9:20

Six (6) Questions, Equally Weighted.

Write your name at the top of each page. Write your answers in the space provided. Use the back of the same page if necessary.

___________________________________________________________

1. Let S be a function that is executed every p units of time (S is a periodic function with period p.) If S fails to complete within p units of time, a fault handler F is called; F recovers from the timing fault and reenters S where it last left off.

Draw a statechart showing the behavior and interactions between S and F.

2. Suppose that file read and write requests are event classes, designated R and W, respectively. Instances of R and W must occur in sequence and satisfy the constraints: Instances of R must be separated by at least 2 time units from preceding instances of R and W, and at least one R must follow a W before another W event occurs.

Express these constraints in Real-Time Logic (RTL).

NAME _________________________

3. Assume that you are given the algebraic specification for an Unbounded Stack (class handout). Add a Bottom function to this specification. Bottom returns the first or bottom element of the stack.

4. Prove that {qy + r = x } is a loop invariant in the following code fragment. The input x and y are assumed to be positive integers. q and r are non-negative integers. State which axiom or rule that you use in each step of your proof.

q := 0; r := x;

while r >=y do

begin

r := r - y;

q := q + 1;

end;

NAME_________________________

5. The basic input symbols to a system are tick (from a clock), D and U (from a single button mouse), and eol. A valid input sentence consists of a sequence of characters followed by eol, where each character is followed by zero or more ticks. A character is a dot or a dash. A dot is a D followed by zero or one tick followed by a U. A dash is a D and U separated by two or more ticks.

(a) Write a BNF grammar that will generate all valid input sentences.

(b) Show how test cases for an input recognizer can be produced from the grammar for

i) the shortest non-empty sentence

ii) a sentence with either one dot or one dash (your choice)

iii) a sentence in which every rule and alternative is used at least once

For each case, list the rules used, in the order that they are used.

NAME __________________________

6. Describe an example of a multi-threaded Java program that one could write that could deadlock. The example should use the synchronized object features of Java. It is not required that you write a program.