Part A: Given that the WORM is used to store a single item, here is an atomic update scheme:
WORM[0] is the first block of the device all bits of the WORM are initially zero to write i: n = address of first free block WORM[n] = [1,i,checksum(i)] to read i: n = address of first free block while N > 0 n = n - 1 [x,i,c] = WORM[n] assert that x = 1 if c = checksum(i) return i endloop raise WORM failure exception to find the first free block: set n to 0; loop [x,i,c] = WORM[n] if x = 0, return n x = x + 1 foreverThis is a generalization of Lamport's stable storage scheme, in that, once the initial value has been written, it will always return the most recently written value that was written successfully. If a write is aborted halfway through, for example, by a power failure, the read algorithm will detect the failure as it checks the checksum and that value will never be returned.
The first bit of each block is used in the code above as a bit vector describing which blocks have been used. Clearly, this bit can be separated out and stored elsewhere, so long as this is the first bit written when writing a new block out.
Searching the bit-vector to find the first free block can be reduced by keeping a count of used blocks in RAM. On startup, we'd initialize this by actually count the blocks, but during normal operation, until the next failure or shutdown, we'd just increment the counter and not need to do any searches.
Part B: The ideas from solutions to Homework 6 can be combined with the above to create a WORM-based file system with atomically updatable files by following the following rules:
Each block stored must begin with the type of the block. Data blocks store the sectors of files. Index block gives the addresses of the sectors of a file. Index blocks contain a field to identify the file as either a data file, a directory, or the root directory.
To make a atomic change to one file or directory, first record all new or updated data sectors, then record a new index sector for that file, and then update the directory for that file. The update of a directory follows the same algorithm, since a directory is itself a kind of file. This update algorithm terminates with the update to the root of the file system.
To make an atomic change to more than one file, first record all new or updated data sectors, then record new index sectors for each file that was changed, and then iterate, as above, working back to wards the index sector for the root. The act of writing a new version of this sector actually commits the transaction.
To read a file, search backward from the first free WORM sector for a valid index sector for the root of the file system. Having found this, the remainder of the file system can be read in the usual way for a disk file. Normally, between writes, the index sector for the file system will be the very last used sector on the WORM, but if there was a failure during an update, there will be other sectors between the end and the valid root. These represent updates that were only partially complete at the time of the failure. Older versions of the data on the WORM can be read by searching back from the current root index sector to find earlier versions of the root.