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.

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.

Pros with RT-11

• Simple
• Contiguous access is fast
• File allocation and deletion operations are fast
• No indirection. In other words, no need to store file pointers

Cons with RT-11

• No subdirectories
• Limit on # of files, because directory is of fixed size
• Have to know the size of the file in advance
• Fragmentation can occur
  • External fragmentation – There might be enough total free space, but there is no free contiguous block large enough to accomodate the new file.
  • Internal fragmentation – The file may be modified and be come smaller in size, but the file space allocated may not be decreased accordingly.
• Directory could be corrupt; files may overlap each other

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.

• The boot sector contains the bootstrapping programs to start the system upon initial boot.
• The superblock holds the file system metadata, such as the version, size of the file system, the amount of space used, and the location of the root directory.
• The FAT maps the data region. In other words, it is an array of entries in which each entry represents another data block. Each entry can contain:
  • 0, which means the current block is the end of the file
  • -1, which means the current block is free
  • N, the index of the next block of the file
• In FAT, there are regular files and directories. Regular file data is stored in assigned blocks, while the FAT gives the block numbers of the file. Directories are like files. However, they are stored as an array of directory entries, like the one shown below.

• No external fragmentation at the cost of fast file access.

Problems with FAT

• Internal fragmentation causes performance issues.
• Difficult to move a file from one directory to another.
• lseek is slow.

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: Information for disk booting and OS loading
• Superblock: Metadata on file system
• Bitmap Block: Indicates used or unused blocks. Free blocks = 0 and used blocks = 1. 
• Inode Table: Stores the inodes, see following section for more information.
• Data: The file data itself.

Inodes

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.

Links

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.