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.
- 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.
- 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.
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.
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?
- 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