CSE 221: Homework 3
Due Tuesday, March 9 at 11:59pm
Answer the following questions. For questions asking for short
answers, there may not necessarily be a "right" answer, although some
answers may be more compelling and/or much easier to justify. But I
am interested in your explanation (the "why") as much as the answer
itself. Also, do not use shorthand: write your answers using complete
When grading homeworks, we will grade one question in detail and
assign full credit for technical answers to the others.
- The Scheduler Activations paper states that deadlock is
potentially an issue when activations perform an upcall:
"One issue we have not yet addressed is that a user-level thread could
be executing in a critical section at the instant when it is blocked
or preempted...[a] possible ill effect ... [is] deadlock (e.g., the
preempted thread could be holding a lock on the user-level thread
ready list; if so, deadlock would occur if the upcall attempted to
place the preempted thread onto the ready list)." (p. 102)
Why is this not a concern with standard kernel threads, i.e., why
do scheduler activations have to worry about this deadlock issue, but
standard kernel threads implementations do not have to?
A reliability-induced synchronous write is a synchronous write
that is issued by the file system to ensure that the file system's
state (as represented by the system's metadata) is not left
inconsistent if the system crashes at an inconvenient time.
- Let f be a new file created in a directory d. The
file system will issue at least three disk operations to complete
this operation. Ignoring any data blocks allocated for the directory
or new file, what are these three disk operations for?
- In Unix FFS, at least two of these writes will be issued
synchronously. Which are they, and what order should they be
performed in? Briefly explain why.
- Consider the Soft Updates solution to this problem. Does it do
any reliability-induced synchronous writes? If so, how does it
differ from FFS? If not, why can it avoid doing so? Explain.
- Consider the same operation in LFS. Does LFS generate any
reliability-induced synchronous writes? Explain.
- Consider the same operation with the Rio file cache. Does Rio
generate any reliability-induced synchronous writes? Explain.
- The FFS, LFS, and Soft Updates file systems introduced new
designs and optimizations to improve upon a previous file system
implementation. Consider the following three changes in underlying
workload and storage technology. For each of the three file systems,
explain whether the improvements they found with their design and
optimizations would still hold under each of these changes. For
instance, would FFS still see similar improvements relative to the old
Unix file system under a read-dominated workload? Would LFS still see
similar performance improvements relative to FFS when latency to
storage decreases by 10x and bandwidth increases by 10x?
- Read-dominated workload (100x reads per write)
- Latency improves by 10x, bandwidth improves by 10x ("SSD")
- Latency degrades by 10x, bandwidth degrades by 10x ("Internet Cloud storage")