CS414 Fall 2000 Homework 5 Solutions
Q1) The worst performance affecter in disks are seek latency and rotational latency. The seek latency can be reduced by
-
organ pipe distribution
-
disk scheduling techniques
-
multiple heads
The
rotational latency can be reduced by
-
block placement in disk (interleaving)
-
on-disk cache.
Q2)
AFS has complete ACLs (access control lists) while vanilla unix uses 9 bits to
store a reduced ACL. Although
protection matrices are in general faster they are cumbersome to store (huge
empty spaces).
Unix
uses a restricted ACL, with only 3 groups and 3 types of access (per
file). AFS requires more time to
traverse the ACL, but has more flexibility and more levels of protection. For
definitions of ACL and PM see textbook chapter 19.
Q3)
Mirroring is a fast way, especially if you can have a smart controller (use
RAIDs with full replication). Protects
users from all kinds of failures (disk failure, head hitting the disk surface,
etc).
Writing
data as in LFS gives you redundancy for head hitting the disk surface and
accidental deletions, but does not cover disk crashes.
AFS
and VMS keep copies of the files that you modify. AFS keeps a single copy; VMS keeps a version for each time you
save the file. Protection is the same
as in LSF.
Q4a)
Yes, there is no reason why not. These
are orthogonal issues. After you
located the directory in disk, searching the directory can be done through a
hash table.
Q4b)
The similarity: both write the data out to disk contiguously.
The
difference: LFS updates the disk allocation, moves files around, cleans up
after itself (compaction). Swap space
is used through a swap map, which is fixed for a set of processes. LFS performs all writes on new blocks, while
dirty pages keep getting written back on the same sectors they were mapped to.
Q5a)
This is a highly parameterized answer.
It depends on the traffic that is pumped into the network by the
workstations hooked up to the Ethernet segment. If you have a 666MHz Pentium-II, 2 workstations should be sufficient
to pump more than 100Mbps into the network, if they are just pumping data. Typically, about 100 devices can share
100Mbps, and things flow ok... The
number of requests generated per second by each node, and the latency
(communication time + server processing time) determines the feasibility of the
system.
Q5b)
There are 3 levels of caching. In order
of preference from a user's perspective:
1-
at the client’s memory (no need to go to local disk, or across the network to
server or server's disk)
2-
at the client’s disk (no need to go across the network to server or server's
disk)
3-
at the server’s main memory (no need to go to server's disk)
Since
we assume unlimited network bandwidth, the network latency would be much
smaller than the client’s disk latency.
Hence it does not help to cache the file on client’s disk. 2 and 3 may be switched, if the network has
high-bandwidth and is underutilized.
Q5c)
Yes. A server would have to handle a
diverse mix of requests, and several of them. In this case, scheduling the disk
requests to minimize seek delays is more important. Certain disk scheduling algorithms may not be efficient in this
case.
Q6a)
You can find an example in which each pair of algorithms performs the same. So,
the answer should be no for a particular sequence of requests. In this case,
the student should make this assumption explicitly (that is, consider response
time for a particular sequence of requests).
If one considers AVERAGE response time, the order is: FCFS ->
SSTF -> SCAN -> C-SCAN -> LOOK, just as presented.
The
example in class notes shows why. There
is no real need for a big justification here.
The students should just say why, more or less.
Q6b)
As stated above, you can find an example in which each pair of algorithms
performs the same. FCFS can perform the
same as SSTF, so coming up with a counter example would make this false. For example consider the requests 1, 6, 10,
15 with the head initially on 4. FCFS
moves across 17 tracks, while SSTF moves thorough 25 tracks.
Q7)
The following are some techniques to reduce the latency of RAIDs
-
make blocks larger, so that minimize the average delay
-
make caches in the disks larger, to take advantage of smaller blocks that are
being written to disks (although total is same, parts are smaller)
-
synchronize all disks, so that they return data at the same time; otherwise,
one disk may have to wait for another before data is delivered to user
application.