------------------------------------------------------
Session 23 - April 02, 2003
------------------------------------------------------
AGENDA:
0 Admin
1 Ch 5.3: file system implementation

------------------------------------------------------
0 - ADMIN
------------------------------------------------------
Startout Q: What is an inode?

Due today
* RI #7, covers Ch 5.1-5

Due Friday
* HM #5: Questions 5.3, 5.6, 5.7, 5.10, and 5.14.

------------------------------------------------------
1 - CH 5.3: FILE SYSTEM IMPLEMENTATION
------------------------------------------------------
IMPLEMENTING FILES
* problem associating blocks with the right files
* contiguous allocation
* linked list allocation - fig 5-8 p. 416
* linked list allocation using index fig 5-9 p. 417
* I-nodes fig 5-10 p. 418
- Calculate number of blocks that I-node can support:
  => 10+256+256*256+256*256*256
  => 16843018 blocks
- Assuming 1K blocks 
  => 16843018 blocks * 1 KB/block * 1 MB/1024 KB 
  => 16448.25 MB (aka 16.06 GB)

IMPLEMENTING DIRECTORIES
* directory really just a special file
* what info needed in directories?
  - main function is to map name onto info needed
    to locate data
CP/M
* fig 5-11 p. 419
* all one happy directory

MS-DOS
* fig 5-12 p. 420
* multiple directories

UNIX
* fig 5-13, 5-14 p. 421
* note that "." and ".." handled without special mech.

DISK SPACE MANAGEMENT
Very similar concerns to memory management
* (Which you haven't read yet.  :) )
Block size
* median file size (1984) was ~1K => 32K blocks bad
  12-15K in 1997
* fig 5-15 p. 423
Tracking free blocks
* linked list of free blocks
* bit map

FILE SYSTEM RELIABILITY
When bad things happen to good files.
* equipment error
* human error

Backup
* full backup vs incremental
* media to use: tapes, CDs, hard disks
* mirroring, RAID

File system consistency
* crashes can cause inconsistency
* file system checker program
  - fsck on UNIX
  - 2 checks: blocks and files
  How would you check on block consistency?
  - what are solutions to inconsistency?
  How would you check on file consistency?
  - what are solutions to inconsistency?

FILE SYSTEM PERFORMANCE
block/buffer cache
If block in cache, satisfy read request from there.
  For write requests, just write to cache and mark
  as dirty. Every so often, synchronize cache and disk.
When cache gets full, can use FIFO, 2nd chance, LRU.
* May put likely-to-reuse blocks at end of list, less
  likely ones at front of list.
Often do write-through for directory or I-node updates.

Keep meta-information near the actual data.
* MS-DOS problems
* Locate meta-info near middle of disk
* BSD fast file system
  - keep related blocks near each other, pref. same cyl
COS 421 - Lecture Notes #23		SPRING 2003	
COS421-lect-2003-04-02.doc	Page 1	Printed 02.04.03