Operating Systems and Architecture
Comprehensive Exam
August 18, 1998
Computer Science Department
University of New Mexico
The test monitor will answer some parts of these questions for you if you
are unsure of what some of these terms mean. The only penalty is that you will
not get any points for the part that was answered for you. You can still answer
the other parts of the question. This can get you started on a question even
if you are not sure of the definitions.
You can do any questions you want. You do not have to do all the parts of
a single question. Instead you can pick the parts you want to answer. Be sure that
it is absolutely clear which questions you are answering.
Do enough questions to total at least 100 points. It is okay to go over 100
points and you can answer as many questions as you wish but all the questions
you answer will be counted in your grade and the total will be normalized to
100 points. We will not take the best 100 points.
- File systems
(15 points) Typical file systems do not operate disks at
their capacity, that is, the disk drives and disk controllers are not transferring
nearly as much data as they are capable of. Why not? What are some possible
solutions to this problem?
- Scheduling
(15 points) Most modern operating systems use multiple levels
of queues for scheduling. Explain in some detail how these systems work and
why they work well.
- Protection
- (5 points) Describe the matrix model of protection.
- (5 points) Describe the access-list method of protection and how it relates
to the matrix model.
- Resource allocation
(15 points) Consider the following statement, "All
resource allocation and optimization decisions involve predicting the future." Explain
what this statement means. Give several examples where it is true. Give any
examples you can think of where it is not true.
- Handling of SCSI and network devices
(20 points) A SCSI controller controls
a bus and an Ethernet controller controls a bus. Compare how these two controllers
will be handled by the operating system. Which parts of the operating system
will be concerned with each one? How will each one be virtualized (if at all)?
Relate this to the differences between a SCSI bus and an Ethernet bus.
- Caches
- (5 points) Contrast the terms "write-through" and "write-back" when
applied to cache line replacement.
- (10 points) Explain how you can implement coherence on a shared bus multiprocessor
system when each processor uses a write-back replacement policy.
- Instruction set architecture
(20 points) One of the most common arguments
in systems is static versus dynamic. In the context of instruction set architecture,
static means scheduling that is done by the compiler (prior to program execution),
dynamic means scheduling that is handled by the hardware (during program execution).
Give a brief characterization of this debate in the context of instruction set
architectures. You should consider register scheduling (static) versus large
caches (dynamic) and multiple, parallel instructions per instruction word (a.k.a.,
VLIW—very large instruction words) versus out of order and speculative execution.
- Networks and operating systems
Modern networks are capable of delivering
data at bandwidths that are comparable to a memory bus. For example, a PCI bus
is capable of delivering memory blocks at a rate of 120 Mbytes/sec and a Myrinet
network is capable of delivering message blocks at a rate of 60 Mbytes/sec.
To avoid a significant loss of bandwidth, it is critical that the networking
system deliver messages directly to the application and avoid making copies
whenever possible.
- (5 points) Given the example of 120 MB/S for the memory bus and 60 MB/S
for the network, what is the effective message bandwidth if every message requires
a memory copy (you should ignore other overheads that might be introduced).
Repeat this calculation assuming that the memory bandwidth is 10 MB/S and the
network bandwidth is 2 MB/S.
- (15 points) Discuss the problems that must be addressed when delivering
messages directly to the memory for an application
