Details of Disks and Filesystems: File Allocation Table (FAT)

CS 321 2007 Lecture, Dr. Lawlor

(Silberschatz chapter 11 has lots of good detail on the File Allocation Table filesystem.)

Disk Mechanics

Disks are funny things.  Data on a disk is lined up in big rings, called "cylinders".  A 5 1/4" floppy disk might have just 80 cylinders, while a typical hard disk has thousands of cylinders.  The cylinders are underneath a read/write "head", a little magnetic loop used to read and write data on the cylinders.  Nowdays disks usually have one head per side per disk, which is one or two for floppies, but a big ("full-height") hard disk might have a stack of a dozen disks, with two dozen heads. 

While the disk rotates under the heads, the data in a cylinder goes by.  The data is usually divided into "sectors" of 512 to 4096 bytes.  Curious question: if the disk is rotating at a fixed speed, and bits are a fixed length on the disk surface, can't you fit more bits around the circumference of the outer circle?  The answer is yes, and this effect literally causes slower bit rates (slower performance) toward the inside tracks (the end) of a disk--one reason old computers "just seem slower than they used to be"!  Typical rotational speeds nowadays are 7,200 RPM--redline for a car engine.  But realize that's only 120 revolutions per second, or 8 milliseconds per revolution ("rotational latency")--this is slow-ville for a computer.

When the heads move between cylinders, that's a "seek".  Through an amazing amount of genius and effort, they've gotten head seek times down to like five *milliseconds*, which is actually closing in on bullet time!  But of course, five milliseconds is eternity and a day to a computer, so you want to minimize seeks.  This is easier said than done.

FAT Filesystem

So, back to the " File Allocation Table" (FAT) filesystem.  It uses an interesting trick to keep track of the blocks in a file.  The file's blocks are basically kept in a big linked list, with each block in the file pointing to the next block until you hit the last block, which is marked with a "-1" link.

What about seek time and rotational latency?