File-System Structure

File-System Structure
File System Implementation

File System Structure
File System Implementation
Directory Implementation
Allocation Methods
Free-Space Management
Efficiency and Performance
Layered File System in OS
File structure
Logical storage unit

Collection of related information
File system resides on secondary storage (disks).

File system organized into layers.
File control block storage structure consisting of
information about a file.
A Typical File Control Block (FCB)
Logical file system

Provides users the view of a contiguous sequence of words,

bytes stored somewhere.
Uses a directory structure, symbolic name
Provides protection and security
OS/user interface
E.g., to create a new file the API provides a call that calls
the logical file system
The file organization module

Knows about files and their logical blocks (say 1,..N)

Files are organized in blocks of 32 bytes to 4K bytes
Translates logical blocks into physical
Knows location of file, file allocation type
Includes a free space manages that tracks unallocated blocks
Basic file system

Issues commands to the device driver (layer of software that

directly controls disk hardware) to read and write physical
blocks on the disk,
Each physical block identified by a disk address (e.g., drive 2,
cylinder 34, track 2, sector 11)
IO control
The lowest level in the file system

Consists of device drivers and interrupt handlers to transfer
information between the memory and the disk
A device driver translates commands such as get me block
111 into hardware specific ISA used by hardware controller.
This is accomplished by writing specific bits into IO registers
Virtual File Systems
All file operations are done on an Open

File Table (OFT)
Contains information about all the
open files
Some OS can have multiple such
tables, e.g., one for each process
and one system-wide table
After opening a file the OS updates
this OFT table and returns an index
to the raw in the table
All future references to the file are
done through the index and not the
symbolic file name
Index is called FCB, file descriptor
(Unix) or file handle (NT)
FCB effectively is another table
containing info about a file for the OS
Directory info generally is copied into
FCB after file opening (compare this
with the PCB)
FCB (is an index into a row in OFT)
Schematic View of Virtual File System
VFS allows the same system call interface (the API) to be

used for different types of file systems.
The API is to the VFS interface, rather than any specific

type of file system.
Directory Implementation
Has a large effect on the file system performance
A) Linear list of file names with pointer to the data blocks.
simplest to program
time-consuming to execute as require a linear search
E.g., to create a new file name we must search the directory to
make sure that no such file exist
When we open the file we must search the linear structure
Many OS implement a software cache for the most
frequently/recently accessed directory information

Allocation Methods
Many files are stored on the same disk;
one main problem is to allocate space on disk to the files
An allocation method refers to how disk blocks are

allocated for files
Three major techniques
1) Contiguous allocation
Allocation for a file is contiguous on disk
2) Linked allocation
Blocks are linked together on disk so can be anywhere
3) Indexed allocation
Blocks are mapped with a table that contains pointers to
disk blocks (similar to page table)
B) Hash Table linear list with hash data structure.
decreases directory search time greatly

collisions situations where two file names hash to the same
location
Major difficulty is its fixed size and dependence of hash function on
the size of the table
Typical solution is to make each hash entry a linked list

Contiguous Allocation
Contiguous Allocation of Disk Space
Each file occupies a set of contiguous blocks on the disk.

Simple only starting location (block #) and length (number of
blocks) are required.
Random access.
Wasteful of space (dynamic storage-allocation problem).
External fragmentation
First fit and best fit strategies to allocate

Files cannot grow.
Extent-Based Systems
Many newer file systems (e.g. Veritas File System) use a
modified contiguous allocation scheme.
Extent-based file systems allocate disk blocks in extents.
Linked Allocation
Each file is a linked list of disk blocks: blocks may be
scattered anywhere on the disk.
block
pointer
An extent is a contiguous block of disks. Extents are

allocated for file allocation. A file consists of one or more
extents.
Linked Allocation (Cont.)
Linked Allocation
Simple need only starting address

Free-space management system no waste of space
No random access
File-Allocation Table (FAT)

File-allocation table (FAT)
disk-space allocation used by
MS-DOS and OS/2. FAT table
on each partition contains map
of linked list
Indexed Allocation
Linked allocation solves external fragmentation but cannot
support direct access (FAT helps in that)
Indexed allocation solves the direct access problem by

Bringing all pointers together into the index block.

Index block is an array of block addresses
To read the k-th block we first find its address in the index block by
looking the k-th pointer
Logical view.
index table
Example of Indexed Allocation
Indexed Allocation Mapping (Cont.)
outer-index
index table
file
Combined Scheme: UNIX inode (4K bytes per

block)
Free-Space Management
Space represented with Bit vector (n blocks)
0 1
n-1
bit[i] =
block[i] free
block[i] occupied
Block number calculation

(number of bits per word) *
(number of 0-value words) +
offset of first 1 bit
Free-Space Management (Cont.)

Bit map requires extra space. Example:
block size = 212 bytes (4 kbytes)
disk size = 230 bytes (1 gigabyte)
n = 230/212 = 218 bits (or 32K bytes)
Free-Space Management (Cont.)
Need to protect:
Pointer to free list
Bit map
Must be kept on disk
Copy in memory and disk may differ (coherence issue).
Cannot allow for block[i] to have a situation where bit[i] =
1 in memory and bit[i] = 0 on disk.
Solution:
Set bit[i] = 1 in disk.
Allocate block[i]
Set bit[i] = 1 in memory
Easy to get contiguous files

Linked list (free list of blocks is linked together)
Cannot get contiguous space easily

No waste of space
File system Efficiency and

Performance
Linked Free Space List on Disk
Efficiency dependent on:

disk allocation and directory algorithms
Performance
Disk/buffer cache separate section of main memory for

frequently used file blocks (regular IO)
Page cache caches pages rather than blocks with VM
techniques (memory-mapped IO)
Dedicating section of memory as virtual disk, or RAM disk.
Various Disk-Caching Locations
Page Cache
A page cache caches pages rather than disk blocks
using virtual memory techniques.
Memory-mapped I/O uses a page cache.
Routine I/O through the file system uses the buffer (disk)
cache.
This leads to the following figure.
I/O Without a Unified Buffer Cache

File-System Structure

Uploaded by

Copyright:

Available Formats

File-System Structure

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

File-System Structure

Uploaded by

Copyright:

Available Formats

File-System Structure

File System Implementation

Layered File System in OS

Logical storage unit

File system resides on secondary storage (disks).

A Typical File Control Block (FCB)

Logical file system

Provides users the view of a contiguous sequence of words,

The file organization module

Knows about files and their logical blocks (say 1,..N)

Basic file system

Issues commands to the device driver (layer of software that

The lowest level in the file system

Virtual File Systems

All file operations are done on an Open

FCB (is an index into a row in OFT)

Schematic View of Virtual File System

VFS allows the same system call interface (the API) to be

The API is to the VFS interface, rather than any specific

An allocation method refers to how disk blocks are

B) Hash Table linear list with hash data structure.

decreases directory search time greatly

Contiguous Allocation of Disk Space

Each file occupies a set of contiguous blocks on the disk.

Files cannot grow.

An extent is a contiguous block of disks. Extents are

Linked Allocation (Cont.)

Simple need only starting address

File-Allocation Table (FAT)

Bringing all pointers together into the index block.

Example of Indexed Allocation

Indexed Allocation Mapping (Cont.)

Combined Scheme: UNIX inode (4K bytes per

Block number calculation

Free-Space Management (Cont.)

Free-Space Management (Cont.)

Easy to get contiguous files

Linked list (free list of blocks is linked together)

Cannot get contiguous space easily

File system Efficiency and

Linked Free Space List on Disk

Efficiency dependent on:

Disk/buffer cache separate section of main memory for

Various Disk-Caching Locations

I/O Without a Unified Buffer Cache

You might also like