1.7 I/o devices and file systems  (Page 6/9)

Even if it is possible to allocate in groups, how do you know when to do it? Be guided by history: if file is already big, it willprobably get bigger.

Crash recovery

Computers can crash at any time, and we want the file system to behave sensibly in the face of crashes. The key idea is calledconsistency:

• The file data and the various control structures (descriptors, bitmaps) must be in agreement.
• Since crashes can occur at any time, not all updates to the disk may be completed.
• We must insure that when the system reboots, it can return its file system to some sensible state.
• The key constraint is that any file system write operation, in progress at the time of the crash, either completely finishes or appears as ifit never happened. This is called atomicity by the database folks.

Insuring consistency requires two things:

• Updates to the file system data structures must be done in the write order (and there is only one right order)!
• The proper steps must be taken at reboot time to bring the system back in to a consistent state.

There are three basic updates that happen when data is written to a file.

1. A block (or blocks) is allocated from the free list (bit map).
2. Data is written to the newly allocated block.
3. The inode is updated to include the new data.

These operations must be done in the above order. If they are not, then it is possible to have a data block included in a file thatmight have garbage (uninitialized data) in the block.

After rebooting, the recovery utility program on Unix, called "fsck", is going to traverse the entire directory structure of thedisk to insure that all free blocks are in the free list.

Recovery after a crash follows these steps:

1. Allocate a temporary bit map, initialized to indicate that all disk blocks are free.
2. Start at the inode for the root directory.
3. Traverse the directory:
   • For each disk data block in the directory file, marks its blocks as "allocated" in the bit map.
   • For each data file in this directory, marks its data blocks as "allocated" in the bit map.
   • For each directory in this directory, perform the "Traverse the directory" stepsabove.

At the completion of the algorithm, you can compare the actual bit map to the temporary one to find blocks that were allocated, butnever made it into a file.

Directories

Motivation

Users need a way of finding the files that they created on disk. One approach is just to have users remember descriptor indexes.

Of course, users want to use text names to refer to files. Special disk structures called directories are used to tell whatdescriptor indices correspond to what names.

A hard concept to understand at the beginning: naming is one of the (if not the) most important issues in systems design.

Approach #1: have a single directory for the whole disk. Use a special area of disk to hold the directory.

• Directory contains pairs.
• If one user uses a name, no-one else can.

Approach #2: have a separate directory for each user (TOPS-10 approach). This is still clumsy: names from different projects getconfused.