Name: Login ID: Code:

Systems Foundational
Sept 2, 1998

You must answer all questions in the Computer Organization section. You must also answer 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).

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;
}                                  }
                                }

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.
Construct a recursive parser for G; provide pseudocode for recursive functions corresponding to the nonterminals.

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?

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?


James Griffioen
9/11/1998