Instructions:
There are seven questions on this exam;
answer any six of the following seven questions.
1. Authentication
A credential is a piece of information produced by a trusted authority
and signed with that authority's encryption key.
- A.
-
Describe how credentials are used in Kerberos. How does the recipient of the credential know that it is authentic (i.e., contains
valid information) and intended (i.e., that this copy of the credential was produced
by the authority and not an imposter?
Why does Kerberos use two kinds of credentials?
- B.
-
Web browsers, to support secure communication with a server ("https" connections),
have to present a credential to the server.
How might the browser obtain this credential?
How might the browser obtain its initial keys or credentials?
2. Distributed Time Stamps
Lamport describes an algorithm to logically order events in a distributed
system.
In his algorithm, events
a and b, in processes i and j, have logical time stamps
Ci(a) and Cj(b).
If Ci(a) < Cj(b), we do not know if a -> b or if
a and b are un-ordered. (Note that "->" is the right-arrow Lamport
happened-before operator.)
How would you extend the logical time information sent with each message
to included enough information that you could disambiguate the case
described above?
3. Memory Management
Consider a system that does not contain hardware support for setting
or clearing dirty bits.
- A.
-
Explain the benefits of knowing if a page is dirty or clean.
- B.
-
Describe how setting and clearing dirty bits can be
efficiently emulated by the OS. To make your answer clear,
specify any changes in how the page tables are used and any new data
structures that are needed. Explain what happens on a read and write
to a given page; if some read or write operations act differently
than others, explain each case.
- C.
-
Imagine that you would also like to implement copy-on-write.
Explain copy-on-write and give a specific example of where it is
particularly useful.
- D.
-
Describe how copy-on-write could be incorporated into this system
(i.e., a system with no hardware support for dirty bits).
4. Scheduling
The Solaris operating system is based on Unix System V Release 4
(SVR4). Scheduling in Solaris, as in all SVR4-based schedulers, is
performed at two levels: class-independent routines and class
dependent routines. Class-independent routines are those that are
responsible for dispatching and preempting processes (the low-level
mechanism). Class-dependent routines are those that are responsible
for setting the priority of each of its processes (the high-level
policy).
- A.
- By default, Solaris supports three scheduling
classes (time-sharing, real-time, and system) and a range of
priorities (from 0 to 159, where higher numbers designate higher
priority processes). Each scheduling class gives each of its
processes a priority in a range that is non-overlapping with the
priorities in the other classes; that is, there is a strict ordering
of scheduling classes. Argue for an ordering of scheduling classes
that you believe is the most logical; point out the advantages as well
as any disadvantages of your ordering.
- B.
- The time-sharing class in Solaris is a multi-level feedback queue
scheduler, based on a configurable dispatch table. The dispatch table
has one row for each priority; each row includes the following fields:
- ts_quantum: the length of the time-slice for processes at this
priority
- ts_tqexp: the new priority level when a process
(currently at this priority) consumes its time-slice
- ts_slpret: the new priority when a process (currently at
this priority) returns from sleeping
Given what you know about the goals of multi-level feedback queue
schedulers, hypothesize about the values of these fields:
- Is ts_quantum longer at higher or lower priorities? Why?
- Does ts_tqexp specify a higher or a lower priority than
the current priority? Why?
- Does ts_slpret specify a higher or a lower priority than
the current priority? Why?
- C.
- Assume that the time-sharing scheduler always sets
the priority of a process to ts_slpret when that process wakes
from sleeping. How could a process take advantage of this behavior to
get better performance? Discuss a simple change within the scheduler
that would eliminate, or reduce, this behavior (you may add new fields
to the dispatch table if necessary).
- D.
- Assume that the time-sharing scheduler only changes
the priority of a process when it consumes its time-slice and when it
wakes from sleeping (with your modifications in part C). What types
of processes may suffer? Again, discuss a simple change within the
scheduler that would eliminate, or reduce, this problem (you may add
new fields to the dispatch table if necessary).
5. RAID
Assume you have a RAID-4 system with D+1 disks, with 1 disk used for
redundancy information (the rest for data). Each disk has B blocks of
capacity, and all disks are of identical make, model, and
performance. Unfortunately, one of your data disks fails and will not
work anymore, and you must replace it with a brand new disk. The
system must then carry out the task of updating the new disk so that
the RAID-4 returns to its normal ``working'' status (i.e., all the
data disks have all their data and the parity disk has all its
necessary parity information), a process known as
reconstruction.
- A.
- Describe how the process of reconstruction would work for RAID-4.
How does the process change if a data disk or parity disk fails?
- B.
- During this reconstruction, how many blocks must be
read from the RAID-4 storage system, and how many written?
- C.
- Now assume that we had instead created a storage system with mirroring
instead of RAID-4, with a total of 2D disks for the system. Describe how
reconstruction would work in the mirrored system.
- D.
- Which is faster - reconstruction in RAID-4 or reconstruction in the
mirrored system? Justify your answer.
6. LFS
The classic log-structured file system presents an entirely different
way to manage disk storage. Data is never-overwritten in place;
instead, all data and meta-data are batched and then appended to the
end of an on-disk log.
- A.
- Assume that the log is divided into segments, and that data is batched in a
segment and then written to disk. One key parameter is the selection of the
segment size. Given a modern disk, how would you select the size of the
segment? Be quantitative in your answer.
- B.
- Sometimes, a segment is written to disk before it is full. Describe
two different scenarios where that could occur. Given a modern disk, how would
smaller segments affect the performance of writes? Be quantitative in
your answer.
- C.
- Suppose we modify the LFS, adding mechanisms to
enable in-place block update. That is, given a block to write out, the
file system can now choose whether to append it to the end of the log,
or to overwrite the last live version. Describe how this approach
could improve performance.
7. Networking
Consider the following network (assume links are bidirectional):
5
|---------------------|
| |
| B---------------C
| / \ 3 / \
| 1/ \2 1/ \5
\ / \ / \
A-------D-------E-------F
/ 1 1 2
1/
/
G
- A.
-
Using the Distance Vector/RIP/Bellman-Ford algorithm, generate a routing
table for node A showing each step in the process including route and
distance to each node.
- B.
-
Describe the "counting to infinity" problem in RIP and give an example
using the network above.
- C.
- Describe one method for dealing with the "counting to infinity"
problem in RIP.