Name

Systems Foundational 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 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.
What is Pipelining? What stages might comprise a pipeline?
2.
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?
3.
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}

(a)
Why is JA shifted left?
(b)
Why not fill the 4 high-order bits of the new PC with 0's?
(c)
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?
4.
Computer architectures typically include both a jump instruction and a call instruction (the call instruction is sometimes named jump-and-link).
(a)
What is the purpose of the call instruction?
(b)
Do you need both instructions or can you get by with just one? Explain.

Operating Systems
This question has four parts. You must answer all parts.

1.
Describe the two fundamental operators on semaphores and give some example code that uses them to enforce mutual exclusion.
2.
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.
3.
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.
4.
Can deadlock arise in a system that uses multiple semaphores to control access to its resources? If yes, demonstrate with a small example.

Compilers

1.
Define the concepts dynamic scoping and static scoping. Give an example (a piece of code) illustrating the difference between dynamic and static scoping. List three programming languages indicating the type of scoping assumed by the semantics of the language.
2.
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.
(a)
Write a grammar describing the language L.
(b)
Find FIRST and FOLLOW sets for the symbols of your grammar.
(c)
Is your grammar LL(1)? Justify.

Programming Languages

1.
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?)
2.
Why don't languages let you goto into a procedure?

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

Databases

1.
This question asks you to consider the differences between relations in Third Normal Form (3NF) and those in Boyce-Codd Normal Form (BCNF).
(a)
Describe the difference between 3NF and BCNF.
(b)
Since one can always convert a relation in BCNF into several relations in 3NF why would you not always store relations in 3NF?
2.
Consider the following query executed to obtain a summary of orders placed with different departments. The d_id is a unique department identifier, d_name is the department name, and amount is the dollar amount of an order.
        select a.d_name, a.d_id, sum(b.amount)
           from Department a, Order b
           where a.d_id = b.d_id
           group by a.d_id

The user obtained the results and found that all of the sums were correct, but that departments for which there were no orders did not appear in the resulting table.

(a)
Explain why some of the departments in the table Department did not appear.
(b)
Formulate a query, or several queries, which will list all departments in the Department table with the sum of their orders including those with no orders.


James Griffioen
1/28/1998