CS111 Lecture 11 Scribe Notes - File System Design

Prepared By: Andrew Eng

What is a file system?

A file system is a data structure that provides an abstraction of a set of files. In other words, a file system is a way in which files are organized.

Examples of File Systems

RT-11 File System 

The following file system, deemed the Paul Eggert File System (c. 1974), is very similar to the RT-11 file system. Files are contiguous chunks of data, and new files are allocated into any free space that will hold it. Note: Graphics are not to scale.

Directory File 1 Unused Space File 2 File 3 Unused Space

The directory is of a fized size, and is an array of directory entries. A directory entry is shown below. An entry of all 0s means the directory is unused.

File Name Start Sector # Length of File

Pros with RT-11

Cons with RT-11

FAT File System (Late 1970s)

The File Accocation Table file system is a common system found in memory devices today. The memory layout is shown below.

Boot Sector Superblock FAT Data
Name File Type Size First Block Number

Problems with FAT

Berkeley Fast File System: A UNIX File System

This file system is one of the many variants of the Unix operating system. The disk space structure is divided into the following:

Boot Sector Superblock Bitmap Block Inode Table Data


Index nodes, or inodes, are data structures that contain a file's metadata, such as size, permissions, owner, links, and timestamps. An inode represents a file or directory, but they do not contain file/directory names. Each file is identified with its own unique inode number. Thus, unique files can have the same name.

Each inode contains a set number of direct block pointers, a few indirect block pointers, and possibly double or triple indirect block pointers. These pointers point to the actual data that the file contains.

One issue with this file system is the existence of holes, which are deallocated addresses filled with 0's. When read, we get 0's. When written, these 0-filled blocks get allocated and hold data. However, some holes may still exist. Holes are quite small, but they still take up memory.

inode hierarchy


A hard link is a pointer to a file's contents. It is identical to the original file; any modifications to the data would be reflected in both the original and linked files. A soft link, or symbolic link, is a pointer to another file, which in turn points to the stored data. Soft links are like shortcuts to files when using Windows. This file only exists to point to a file elsewhere in the system.

Soft and Hard Links