File System Design

By: Rong Fan, Xinya Guo, Shwetha Kotekar

There are three topics we want to cover in File Systems:

The two constraints are performance and robustness.

BUT the faster you make your file system, the less robust it gets. But before we get into that...


A file system is the data structure designed to support the abstraction of the data blocks as an archive and collection of files. In other words, a file system organizes the data blocks into files, directories, and file information. This data structure is unique because it is stored on secondary storage (usually the disk), which is a very slow device.



Data Blocks

An Embarrassingly Simple File System:

RT-11 File System

The following simple file system is very similar to the RT-11 files system (Real Time) (early 1970). In this file system, files are contiguous chunks of data. New files are allocated in any free space that will hold it. The deletion of a file frees up that disk space to be used later.


File 1

File 2

File 3

Unsued Space

sequence of sectors: 0 → n

The directory is a fixed size of 10 sectors.

The directory entries are at the beginning of the file. They contain information about the files in the directory. These entries have three fields:

Directory Entry:

File name \0

Start of file

(starting block number)

Length in bytes

(number of blocks allocated)

Advantages with RT-11:

Disadvantages with RT-11::

FAT (File Allocation Table) File System

(late 1970)




FAT (File Allocation TAble)




(Each sector is 512 Bytes)

The boot sector contains the bootstrapping programs to start the system upon a boot, as we have discussed in prior lectures. In a system with multiple disks, each disk has the boot sector.

The superblock contains all the metadata about the file system, such as the version number, the size of the entire system, the root directory, the pointer to the first data block, and more.

The file allocation table (FAT) contains the FAT structure, which is a map of the data region. It is described in more detail below.

The rest of the disk are the data blocks to store files.

SO: 232 x 212 = 244

FAT vs. the Simple File structure

Directories are Files. Unlike the simple file structure from before, FAT has no directory block. Instead, directories are stored like files as an array of directory entries.

= 16miB/file limit

FAT16: % disk in FAT = 2/4096 = 0.5%

For example, we want to find “FOO.pdf”. For this, we need to know where the first block. The FAT directory entry will give you the first block. The directory entry is found using the root in the superblock.

FAT Table

The FAT table is an array of entries where each entry represents the corresponding data block. Each entry either contains:

For example, suppose a file starts at data block 3. The FAT table entry 3 corresponds to data block 3. In this entry is the number 10, which means if we wanted to continue reading the file, we must go to data block 10. If the FAT table, entry 10 has a 0, data block 10 is the last data block in the file.

Issues with FAT:

Advantages with FAT:

Disadvantages with FAT:


The BSD (Berkeley Software Distribution) is a UNIX operating system. The UNIX file system is similar to the FAT file system but replaces the FAT with two of its own unique elements. The disk is portioned into the following components:




inode table

DATA (8kiB blocks)


Inode, or "Index node," is a block of fixed size that holds metadata about directory files or regular files. Each inode has the following information:

Advantages with UNIX file system:

Api: open a file, create it

lseek ( ..., 10,000,0000,000)

write("abc", 3)

Disadvantages with UNIX file system: