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:

- (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