the vault

File System Implementations

Overview

The disk structure is generally a 1-D array of logical block, where the logical block is referred to as the smallest accessible unit (with different sizes, depending on the requirement). The logical block is then mapped into disk sectors, with different layouts dependent on the hardware.

UserOS-FSStorage

Disk Organisation

The disk is organised with a Master Boot Record (MBR) at sector 0 with partition table, which is followed by one or more partitions.

Master Boot Record

The MBR holds the information on how the disc’s sectors (A.K.A. “blocks”) are divided into partitions, each partition notionally containing a file system. The MBR also contains executable code to function as a loader for the installed operating system—usually by passing control over to the loader’s second stage, or in conjunction with each partition’s volume boot record (VBR). This MBR code is usually referred to as a boot loader (from Wikipedia)

The file system contains:

  • OS Boot-Up information
  • Partition details
  • Directory structure
  • Files information
  • Actual file data
MBRPartitionPartitionPartitionOS Boot BlockPartition DetailsDirectory StructureFiles InfoFile DataSimple Boot CodePartition Table

File Block Allocation

A file is made up of logical blocks.

Internal fragmentation

When the file size is not a multiple of logical blocks, it might have internal fragmentation.

Thus, a good file implementation needs to

  • keep track of logical blocks
  • allow efficient access
  • utilise disk space effectively.
contiguousfile1file2STARTLENGTH0244linked-listfile1file2STARTEND27411indexedfile1INDEX BLOCK10012346420701234642070123464207012347-0-65-012346420701234642076789109-1-11-11-1Linked List v2 ## Contiguous

General idea

Allocate consecutive disk blocks to files

Simple to keep track

The blocks are in order, so it is easy to keep track where all the blocks are.

Fast access

The system only needs to seek first block.

External fragmentation

File size needs to be specified in advance

Linked List

General Idea

Keeps a linked list of disk blocks, where each disk block stores the current file data and the next disk block number. The file information stores the first and last disk block number.

Solves fragmentation

Slow random access, since not index

Part of disk block is used for pointre

Less reliable

File Allocation Table

This optimisation stores the linked list pointers as a table in memory.

Faster random access

Linked list traversal in memory.

Keeps tracks of all disk blocks in partition

Huge when large, consuming memory space.

Indexed

General idea

Each file has an index block, with an array of disk block addresses.

Lesser memory overhead

Only index block of opened file in memory

Fast direct access

Limited maximum file size

Number of blocks limited to number of block entries

Index block overhead

Variations

Linked scheme

Keeps a linked list of index blocks

Multilevel index

Multilevel block allocation (similar to multi-level paging)

Combined

Combination of direct indexing and multi-level index scheme

Free Space Management

Motivation

When performing file allocation, there is a need to know which disk block is free.

Free space management is important to maintain free space information.

The two operations considered are:

  • allocation: removing free disk block from free space list
  • free: add free disk block to free space list
10111110BitmapLinked List

Bitmap

Provide a good set of manipulations

Need to keep in memory for efficiency reasons

Linked List

Easy to locate free block

Only first pointer needed in memory

High overhead

Directory Structure

The directory structure is in-charge-of:

  • keeping track of the files in a directory
  • map file name to file information

File needs to be opened before use.

Directory needs to recursively search the directories along path to arrive at information.

Data Structure

Linear List

General idea

Locates a file using a linear search

Inefficient for large directories and/or deep-tree traversal

Hash Table

General idea

Stores a hash table of size N.

Fast lookup

Hash table has limited size

Depends on good hash function

File Information

Two common approaches to store

  • store everything in directory entry
  • store only file name and pointers to some data structure

File System in Action

This refers to the runtime information instead of the static information.

Create

To create a file,

  • the full pathname is used to locate parent directory
  • the filename has to be searched to avoid duplicates

Then, if the file can be created,

  • use free space list to find free disk block

Then, add an entry to parent directory with the relevant file information.

Graph View