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:

\begin{displaymath}
newPC = (oldPC \ \& \ {\tt 0xF0000000}) + (JA << {\tt 2})\end{displaymath}

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