Software Systems
Spring 2008

For today, you should have:

1) read from Tanenbaum and answered questions

2) worked on Homework 5

3) worked on your project

4) read LBoS and done the Dining Savages problem


Outline:

1) file system implementation (questions from Tanenbaum)

2) UNIX inodes 

3) dining savages

4) C notes on mycat and mcopy


For next time you should:

1) work on your project

2) read Rosenblum and Ousterhout (questions below)

   http://wb/ss/handouts/rosenblum90lfs.ps

3) read the next section of LBoS and do the barbershop problem

4) work on Homework 5

Coming up: exam #2 next Monday, progress report next Thursday


UNIX inodes
-----------

Benefit: fixed size per file

Problem: limit on the size of the file

Solution: indirection

"Any programming problem can be solved by adding a level of indirection."

-- Anonymous  (variously attributed to Butler Lampson and David Wheeler)

"Any performance problem can be solved by removing a level of indirection."

-- M. Haertel 

Example:

block size is 1KB, block addresses are 32-bits

1) How many addresses can fit in a block?

2) How many blocks can a single indirection block address?

3) How many blocks can a double indirection block address?

4) How many blocks can a triple indirection block address?

5) What would be the maximum file size on such a system?













Dining savages
--------------

In a previous edition of LBoS, I had the following solution:

# COOK

    emptyPot.wait()
    putServingsInPot(M)
    fullPot.signal()

# SAVAGES

    mutex.wait()
        if servings == 0:
            emptyPot.signal()
            fullPot.wait()
            servings = M
        servings -= 1
    mutex.signal()

    getServingFromPot()
    eat()

The difference is that getServingFromPot() was outside the mutex.

But I got an email that convinced me that there is a problem
here.  What is it?


File system interface
---------------------

What is the primary abstraction created by the file system?

What details of the implementation are generally hidden?

What is the interface to the abstraction (for example, what is the
sequence of operations to read a byte from a file and write a new
byte)?


Most file systems provide interfaces at several layers:

1) user interface: what is the user's model of a file?
   What tools does the user have to interact with files?

   a) Graphical: file = document, click and drag.

   b) command line: file = sequence of bytes; ls, wc, awk, grep, etc.

   In most graphical systems, documents belong to applications.

   In UNIX, many applications can operate on the same file.

2) High-level API

   cat file1 > file2

   print open(filename).read()

3) Middle-level API

   fopen, fscanf, fprintf, fclose

4) Low-level API

   creat, open, read, write, close

5) Really low-level API

   getblk, bread, bwrite

6) Really, really low-level interface

   SCSI
   
7) The hardware interface


The ioloop.c that I gave you demonstrates level 4:

#define FILE_MODE (S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH)
 
int main (int argc, char *argv[])
{
  int i = 0;
  int iterations;
  double x;
  FILE *fp;
  int fd;
  int n;
  char buf[] = "a";
 
  if (argc == 2) {
    iterations = atoi (argv[1]);
  } else {
    printf ("Usage: loop [iterations]\n");
    exit (-1);
  }

  fd = creat ("temp", FILE_MODE);

  for (i=0; i<iterations; i++) {
    n = write (fd, buf, 1);
    if (n != 1) {
      perror ("error");
    }
    n = fsync (fd);
    if (n != 0) {
      perror ("error");
    }
  }
  close (fd);
}

Each time you drop down a level, the number of lines of
code to perform the same task gets multiplied by 5-10.

What do you get in return?

This is an example of a common OS feature, a multi-layer interface.

In general, the higher levels provide

1) more abstraction, more work handled for you

2) more concise code

3) shorter development time

4) fewer errors

In general, the lower levels provide

1) detailed control, power

2) performance.


Power and performance are the sirens that lead
software projects to their doom!

And in some cases you don't even get the performance,
because the abstraction hides an algorithm that's
smarter than you.

Choose the highest level interface that can possibly
solve your problem, and only drop down if there is
no alternative.



Reading questions
-----------------

Again, practice reading technical papers in several passes:

1) First pass, read the abstract, introduction and conclusions.

2) Second pass, read the section headings and understand the
   outline of the paper.

   Decide which sections are most important.  In this case,
   I suggest that we are most interested in the mechanism
   described in Section 4, and less interested in the performance
   evaluation in Section 5.

3) Read the questions below so you know what information to
   look for.

4) Give yourself a fixed amount of time (try 20 minutes) to
   read through the paper without getting bogged down, then
   see if you can answer the questions.

5) If there are questions you can't answer and you think it is
   worth spending more time on them, make a targeted search for
   the answers, or at least identify the relevant sections.


Rosenblum and Ousterhout, "The LFS Storage Manager"

1) What were the technical circumstances, in 1990, that motivated LFS?
   Are these observations still applicable, or has the technology
   changed?





2) In a conventional file systems, which factor dominates file system
   performance, latency or bandwidth?  Why?





3) What is asynchronous I/O and how does it help?





4) What is sequential I/O and how does it help?





5) What workloads is LFS designed to support?  What are the
   relevant characteristics of these workloads?





6) What information is stored in the inode map, and why is
   it necessary?





7) What information is stored in the segment summary blocks,
   and why is is necessary?








8) During segment cleaning, how does LFS identify live blocks?
   Where does it put live blocks?










9) When does data in the file cache get written to disk?  How
much data might be lost in a crash?









Skim Section 5 to see what kind of evaluation they did

10) What kind of workload did Rosenblum and Ousterhout use to
    evaluate the performance of their implementation?