Problem 1

In Sprite LFS, segments are written from back to front. For example, below is a diagram showing a segment that has had one write performed on it.

After one more write, the segment could look like this:

A third write would fill the segment (in this diagram, it would write two data/inode blocks and one summary block) and then start filling a new segment.

1. Consider the roll-forward procedure in crash recovery for Sprite LFS. How does the roll-forward procedure determine when to stop rolling forward? If you can't determine this from the paper, then make an educated guess and justify your guess.
    
   
2. Sprite LFS wrote the segments as outlined above because it allowed the cleaner and the roll-forward procedure to make the assumption that if a segment summary block was safely written to disk (such as the last block in the segment shown above), then all of the blocks described by the segment were also safely written to disk. Unfortunately, this is based on the assumption that a disk controller writes blocks in the sequence they are stored in memory. In order to reduce rotational latency, some controllers start the write transfer depending on the current rotational position of the head. For example, in the first write shown above, the controller could first write out the last three green blocks, and then the segment summary block, and then finally the first three green blocks.

Problem 2

void InsertNode (Node* first, last, new) {
   Node *at = first;
   while (at != NULL && at->key > new->key) at = at->next;
   if (at == NULL) {          // Insert as last node in list
     new->prev = last;
     new->next = NULL;
     if (last == NULL) first = new;
     else last->next = new;
     last = new;
     }
   else {                     // Insert before at
     new->prev = at->prev;
     new->next = at;
     if (at->prev == NULL) first = new;
     else at->prev->next = new;
     at->prev = new;
     }
   }

1. Consider using the Rio cache approach: this routine is used to maintain a data structure that is read after the machine recovers from a crash. How could a machine failure leave this doubly linked-list in an unsafe condition?
    
   
2. Suppose that Rio indeed used such a doubly-linked list. How would you design Rio to deal with the problem? (Note that you have two general choices to consider: either doing something so that the datastructure is not seen in an unsafe condition or doing something to make it consistent).
    
   
3. The Rio paper does not discuss the impact of either the L1 or L2 cache. The existence of such caches complicate building Rio. Explain why, and how one could change Rio to accomodate such hardware caches.
   

Problem 3