Name: Login ID: Code:

Systems Breadth Exam
Sept 2, 1998

You must answer all questions in the Computer Organization section. You must also answer all the questions in two of the remaining four areas. Do not write any answers on this paper. Only mark your name and code on this paper. Write all your answers on the blank paper provided to you. Only use one side of each sheet of paper. Write your code at the top of each sheet of paper. Do not write your name on your answer sheets.

Computer Organization

1.
Addressing:
Each of the points shown below lists an addressing mode followed by an example instruction using that type of addressing mode. For each point, describe how that type of addressing works and show the contents of register 4 (R4) after the instruction finishes. Assume that R3 contains the value 0x100. Assume that memory location 0x100 contains the value 0x102. Assume that memory 0x102 contains the value 0x100.
(a)
Immediate Addressing: mov $6, R4
(b)
Direct Addressing: mov 0x100, R4
(c)
Register Addressing: mov R3, R4
(d)
Register Indirect Addressing: mov *R3, R4
(e)
Indexed Addressing: mov 2(R3), R4
(f)
Indirect Indexed Addressing: mov *2(R3), R4
2.
Design an instruction format for a computer that wants to support all of the above addressing modes. Assume the opcode will consume 6 bits. Assume there are 16 registers. Assume addresses are 32 bits long. Assume immediates are 16 bits long. Assume all operations have 2 operands (like the move instruction above).
3.
Show the circuit that implements the boolean function (A + B) + (C * A) + (B + C). Simplify the circuit if possible.
4.
Draw the circuit for an SR latch and describe how it works.

Operating Systems

1.
The following question about page-replacement policies has 5 parts. Answer all parts.
(a)
Describe differences between a local and a global page-replacement policy.
(b)
Give a specific example of a local page-replacement policy.
(c)
Give a specific example of a global page-replacement policy.
(d)
Briefly describe a situation where a global policy would be preferable to a local policy.
(e)
Briefly describe a situation where a local policy would be preferable to a global policy.
2.
The following program consists of two processes. Process P1 captures integer coordinates from an input stream. Process P2 displays them 3 at-a-time. Rewrite these two processes using semaphores so that each input coordinate (P1) is used exactly once by process P2.

                     #define BMAX 40
                     int buf[BMAX];

                     void main() {
                        create(P1);
                        create(P2);
                     }

P1() { // 1 at-a-time           P2() { // 3 at-a-time
   int i=0;                        int i=0;
   while (1) {                     while (1) {
      fin >> buf[i];                  fout <<f(buf[i],buf[(i+1)%MBUF],
      i = (i+1)%MBUF;                          buf[(i+2)%MBUF]);
   }                                  i = (i+3)%MBUF;
}                                  }
                                }

3.
What problems would you need to address if you were going to extend a conventional file system to be a distributed file system. Clearly explain each of the problems and suggest solutions.

Compilers

Consider a set of arithmetical expressions with a small set of operators. Specifically, an arithmetical expression for this problem is limited and includes only such tokens as id (identifier), num (number), +, *, as well as ( and ). For example, (num + id ) * (num * num * (id + id)) is a well-formed expression. On the other hand, (num - id)/id, which is usually a good expression, is not included in our considerations.

1.
Design an LL(1) grammar G that generates the language of all well-formed expressions as described above.
2.
Compute FIRST and FOLLOW sets for the nonterminals of your grammar.

3.
Build a LL(1) parse table for G.
4.
Based on the table, parse (id + num) * id.

Note : A grammar that is not LL(1) will only receive partial credit.

Programming Languages

Consider a language that only has parameter passing by value.

1.
Does FORTRAN have this characteristic?
2.
In such a language, how can a programmer get the effect of passing a parameter by reference? (You may need to introduce other features.)
3.
How can a programmer get the effect of passing a parameter by result?
4.
A programmer who is interested in efficiency does not want to pass an array of size 50,000 by value. There are at least 3 alternatives. Describe two and discuss how they compare to passing by value with regard to good programming practice.
5.
Imagine a language like FORTRAN, but without COMMON and without parameters. Is there any way to pass information to procedures?
6.
C does not allow labels to be passed as parameters. What would be the semantics of a goto whose target is a label parameter?
7.
What is the problem with passing a label as a result value from a procedure?

Databases

1.
Given a relation and a set of tuples for that relation, can one determine the functional dependencies for that relation? Explain your answer.
2.
Given that you know the set of functional dependencies for a particular database give, two ways that that information could be used.

3.
Suppose that we have a database consisting of attributes A, B, C, D, E, F with the following functional dependencies:
          E -> D
          C -> A
          C, E -> F
          A -> B
(a)
Find a key for the relation R = ABCDEF.
(b)
How many keys does R have? Show all of them.
(c)
Find a decomposition of R into third normal form that has a lossless join and preserves dependencies. Discuss why your decomposition is lossless and dependency-preserving.
(d)
Suppose that relation R is decomposed into R1 = CDEF and R2 = ABC. What redundancies and anomalies are introduced?

4.
This question asks you to discuss several aspects of transaction serializability.
(a)
Define a serializable set of transactions.
(b)
Why is serializability a desirable property of a set of transactions?
(c)
Discuss how one could enforce serializability in a database.


James Griffioen
9/11/1998