Name
Systems Breadth Exam
Spring 1998
January 22, 1998
You must answer all questions in the Computer Organization
section. You must also answer questions in two of the remaining
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.
- Computer Organization
- (a)
- A combined data/instruction cache has a hit-rate of 90%.
A cache access takes 100 nsec while a memory access takes 800 ns.
What is the effective access time?
- (b)
- The MIPS chip has a jump instruction of the form
| 6-bit opcode (OC) |
26-bit address to jump to (JA) |
Because JA is only 26-bits long, the actual 32-bit address
that is jumped to is calculated as follows:

- i.
- Why is JA shifted left?
- ii.
- Why not fill the 4 high-order bits of the new PC with 0's?
- iii.
- If we write a program that has more than 64 million 4-byte
instructions (i.e., take more than 256 MB of memory to store),
what must the compiler/linker/loader consider before using this
instruction?
- (c)
- Gates and Memory
- i.
- Draw the circuit that implements the following truth table that
has inputs A, B, and C and output O:
| A |
B |
C |
O |
| |
|
|
|
| |
|
1 |
|
| |
1 |
|
|
| |
1 |
1 |
1 |
| 1 |
|
|
|
| 1 |
|
1 |
1 |
| 1 |
1 |
|
1 |
| 1 |
1 |
1 |
1 |
- ii.
- Draw the gates that implement the following units. Describe
their purpose and how they work.
- a.
- an SR latch
- b.
- a clocked D latch
- 2.
- Operating Systems
- (a)
- Synchronization
- i.
- Whether or not a semphore is fair (i.e., free from starvation) depends
on its implementation. Describe two semaphore implementations: one that
is fair, and one that is not fair. Justify your assertion regarding the
fairness of each implementation.
- ii.
- Can deadlock arise in a system that uses a single semaphore to
control access to all of its resources? If yes, demonstrate with a small
example.
- iii.
- Can deadlock arise in a system that uses multiple semaphores to
control access to its resources? If yes, demonstrate with a small
example.
- (b)
- Virtual Memory/Paging
- i.
- Describe the anomolous behavior exhibited by FIFO page-replacement.
- ii.
- Even without understanding the FIFO anomaly, we should have been
able to predict that FIFO would be a poor page-replacement policy.
What principle does a good page-replacement policy exploit? How does
FIFO page-replacement violate this principle?
- 3.
- Programming Languages
- (a)
- What is the meaning of a goto in an Algol-like language (such as
Pascal or C) if the target of the goto is outside the procedure
where the goto statement sits?
(Don't say that it is invalid. In some languages, it is valid. What does it
mean?)
- (b)
- Pascal allows integers to be coerced to floating point numbers.
C allows integers to be coerced to pointers.
Are these coercions safe? Why or why not?
- (c)
- Prolog is not an imperative programming language. Discuss
to what extent Prolog supports the following concepts:
- i.
- variables
- ii.
- procedures
- iii.
- value-mode parameters
- iv.
- labels
- v.
- recursion
- 4.
- Compilers
- (a)
- Define the concepts dynamic scoping and static scoping.
Give an example (a piece of code) illustrating the difference
between dynamic and static scoping.
List some programming languages indicating the type of scoping
assumed by the semantics of the language.
- (b)
- Consider a text file (SourceFile) containing sequences of integer numbers
enclosed in well-matching parenthesis.
For example the following is a correct SourceFile:
(123)(734(78)((4)(0555)))
We can look at this string as a sentence in the language L of correctly
formed numbers embedded in matching brackets.
- i.
- Write a grammar describing the language L.
- ii.
- Find FIRST and FOLLOW sets for the symbols of your grammar.
- iii.
- Is your grammar LL(1)? Justify.
- (c)
- Design and provide pseudo-code for a recursive descent parser for
your grammar.
James Griffioen
1/28/1998