Systems Exam: September 1997

This test is closed book. Do all parts of all questions. Do question 1 and any other two questions. If you do more than three questions, you will be graded on question 1 and the best two of the others. When you do a question, answer all parts. Please follow these guidelines:

Machine Organization


(a) How many bits must be allocated to a register field in the instruction format of a machine with 16 general-purpose registers?
(b) Suppose we are designing instructions for a machine with 6-bit op-codes, 16 general-purpose registers, 32-bit memory words, and 32-bit memory addresses. Describe three different addressing modes and their instruction formats that will allow memory-referencing load-word and store-word instructions to access all of memory.

Compilers


(a) Give a precise definition of the FIRST and FOLLOW sets for nonterminals of a context free grammar.
(b) Let G be the following grammar:
e --> e OR t | t
t --> tf | f
f --> p* | p+ | p
p --> (e) | OPERAND
where OR and OPERAND are terminal symbols. Make this grammar LL(1) by removing left recursion and other operations if needed.
(c) Give the FIRST and FOLLOW sets for the nonterminals of this grammar.

Programming Languages

Consider the following program:

 1  program Main(input, output);
 2
 3  var
 4      Size : integer;
 5
 6      procedure Outer(Size : integer);
 7      type
 8          ArrayType = array [1 .. Size] of integer;
 9
10          procedure Inner(Size : integer);
11          var
12              MyArray : ArrayType;
13          begin (* Inner *)
14              MyArray[10] := Size;
15          end; (* Inner *)
16
17      begin (* Outer *)
18          if Size < 10 then
19              Outer(Size*2)
20          else
21              Inner(Size/2);
22      end; (* Outer *)
23
24  begin (* Main *)
25      Outer(2);
26  end.

(a) Although the program is not completely valid in any standard computer language, what language does it appear to be in?
(b) This program violates the rules of that language in only one significant way. What is the violation? Give the line number(s) and describe the problem.
(c) In line 14, which declaration of Size does the compiler use: the one in line 4, line 6, or line 10?
(d) Show what frames (activation records) are on the central stack when execution reaches line 14 for the first time. For each frame, show the values of all parameters and local variables.
(e) What is the length of MyArray when execution reaches line 14 for the first time? (The length will determine if the subscript 10 is valid.)

Operating Systems

File systems

Conventional computers use main memory (RAM) and disk to store file system data. However, a new technology called NVRAM (which stands for Non-volatile RAM) is becoming cheap and is being used in addition to RAM and disks. NVRAM is just like RAM except that: (1) it takes a little more time to access data in NVRAM than RAM. (2) NVRAM does not lose data if the power goes off or if the machine reboots. Unfortunately, NVRAMs are still quite small (tens of MB).

How might you change the file system in an operating system to make use of NVRAM and disk? Be as specific as possible, and justify your suggestions. Many different answers are ``correct'' if you can justify them.

Synchronization and Deadlock

Consider a stop sign at a 4-way intersection:
                   |
                   v

                  4-way
              ->   stop  <-
                  sign

                   ^
                   |

(a) Does the rule ``yield to the car on the right'' prevent deadlock? Why or why not?
(b) What is the difference between deadlock and starvation?

Databases

Assume that we wish to construct a database from data items {A, B, C, D, E, F, G}. A through G are the attributes of our table. The set F of functional dependencies is given by:
    F =B C D --> A
        B C --> E
        A --> F
        F --> G
        C --> D
        A --> G

(a) Find a minimal cover for this set of functional dependencies.
(b) Starting with a table T that contains all the attributes above, form a lossless decomposition of T into two tables that make up a 2NF decomposition. Carefully, list the candidate keys of T and of each decomposition.
c) Continue the decomposition to make the database 3NF. Is your decomposition BCNF? Justify your answer.