What steps is needed to access a data block in the Log structured File
System (Sprite) .  Assume we know the inode of the file taht contains
the block and that none of the information we need has been cached?

Please the answer must be a sequence of steps.

I have more questions.
Thank you

Hello Mscat,

The following is based on a review of information at
  http://www.cs.berkeley.edu/projects/sprite/sprite.papers.html
and in particular, the thesis paper titled
  "The Design and Implementation of a Log-structured File System"
by Mendel Rosenblum which is online (postscript format) at
  ftp://ftp.cs.berkeley.edu/ucb/sprite/papers/thesis-Rosenblum.ps

I suggest you download a copy (it is about 1 Mbyte of data) and go to
chapter 4 to follow along. There are a few cases that should be
described based on file size.

[1] Section 4.2 (page 29) indicates a Sprite inode includes the disk
addresses of the first 10 blocks of the file. So, for a small file,
(up to 10 blocks), simply read the inode, look up the disk address,
seek to that address, read the data.

[2] Same section, it indicates that both indirect and double indirect
blocks are used. Assuming indirect blocks, the sequence becomes:
 - read inode
 - locate indirect block containing the requested data block address
 - seek to indirect block / read it
 - locate data block address
 - seek to data block / read it

[3] Assuming double indirect blocks, the sequence becomes:
 - read inode
 - locate double indirect block containing the requested data block address
 - seek to double indirect block / read it
 - locate indirect block containing the requested data block address
 - seek to indirect block / read it
 - locate data block address
 - seek to data block / read it

This information was found using the search phrase
  sprite log file system
however some similar phrases such as
  sprite log file system read operation
or
  sprite log file system read performance
or
  unix double indirect block file system explanation
will locate more information related to Sprite in specific or the use
of indirect / double indirect blocks in Unix.

Don't hesitate to make a clarification request if this answer is
unclear or if you need further details.

  --Maniac

---

Request for Answer Clarification by mscat-ga on 29 Nov 2004 20:31 PST

First, thank you very much for trying to help.  
I am not sure how Google Answers work, but I hope you got paid.

However, I do not think thats what the teacher wants. I knew this answer.
I am studying for a big exam, and the teacher is good but tricky.

Thank you

---

Clarification of Answer by maniac-ga on 30 Nov 2004 08:25 PST

Hello Mscat,

Well, the steps could be explained more like code instead. Something like...

read inode;
if data block is in double indirect area then
  read double indirect block to get indirect block;
if data block is in indirect block then
  read indirect block to get data block address;
read data block;

Or perhaps the following is more steplike...
[1] read inode getting address for subsequent steps, determine if data
block is directly accessible, in indirect, or double indirect block.
[2] if data block is in a double indirect block, read double indirect
block to get indirect block address
[3] if data block is in a indirect block, read indirect block to get
data block address
[4] read data block using data block address (from inode or indirect block)
Only the first and last reads are required on a small file, medium
files require reads at steps 1, 3, and 4, and a large file does all 4
reads.

There are several ways to describe the sequence of operations (or
steps). I don't know your teacher but if the teacher has a preferred
way of representing the steps, I suggest following that style. You may
also want to point out that a real implementation of Sprite will
include caches - the inode / indirect / double indirect blocks may
already be in memory and not require reads from disk.

  --Maniac