CSE 221: Homework 3

Winter 2010

Due: Thursday, March 11, 2010 at 9:30am in class

1. [Snoeren] 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 embarrassing time.
   1. 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?
   2. 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.
   3. 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.
   4. Consider the same operation in LFS. Does LFS generate any reliability-induced synchronous writes? Explain.
   5. Consider the same operation with the Rio file cache. Does Rio generate any reliability-induced synchronous writes? Explain.

2. Mach's virtual memory implementation allows users to provide backing store implementations. This is done by associating with each memory object a managing task, which is called an external pager. Mach communicates with the appropriate external pager through the paging_object port. An external pager's code and data is itself in memory that is backed by a memory object. Thus, a page fault could be raised in the servicing of a page fault. This could, in turn, invoke an external pager that itself could page fault. What conditions are needed for such a cascade of page faults to lead to an inability to resolve the page fault? Give two different rules one could impose on the use of external pagers that would ensure that such cascaded page faults will always be resolvable.