Homework 10

22C:116, Fall 1999

Due Friday Nov 12, 1999, in class

1. Background Recall the problems on Homework 6 involving a WORM device. The solutions posted outline a reasonable approach to take for constructing a file system on such a device.

   Assume that the failure mode of the system during a write to the WORM device is simple: Blocks of memory on the WORM are written in bit serial fashion, and a failure may occur after writing any bit of a block. The WORM cannot normally be used to write partial blocks.

   Part A: Given that the WORM is used to store a single item, for example, one bank account, propose an atomic update scheme. This should be a generalization of Lamport's stable storage scheme, and it must record the entire history of the changes to the stored item, since each change must be made by writing a new copy of the item.

   Part B: Now, use the ideas from solutions to Homework 6 to generalize your solution above, so that the WORM may be used to store a file system, with atomically updatable files.

2. A Question: What aspect of the atomic transaction problem is solved by 2-phase locking, and what parts must be solved by lower-level mutual exclusion mechanisms, pointer assignment or things like Lamport's stable storage?

3. A Question: What problem is solved by the use of optimistic concurrency control in implementing atomic transactions? (This question was inspired by question 19 on page 506 of the text.)

4. A Question: What is the difference between two phase locking and a two phase commit protocol.