Chapter 11: File System Implementation

Chapter 11: File System
Implementation
Chapter 11: File System Implementation
■ File-System Structure
■ File-System Implementation
■ Directory Implementation
■ Allocation Methods
■ Free-Space Management
Operating System Concepts – 7th Edition, Jan 1, 2005 11.2 Silberschatz, Galvin and Gagne ©2005
Objectives
■ To describe the details of implementing local file systems and

directory structures
■ To describe the implementation of remote file systems
■ To discuss block allocation and free-block algorithms and trade-offs
File-System Structure
■ 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
Layered File System
Layered File System (2)
■ I/O controls consists of device drivers and interrupt handlers

■ Basic file system issues generic commands to the appropriate
device driver to read /write physical blocks on the disk.
■ File organization module translates logical block addresses to
physical block addresses for the basic file system to transfer
■ Logical file system manages metadata information.
File system implementation
■ Structures
● Boot control block (per volume): info needed at boot time
● Volume control block (per volume): contain volume/partition
details eg no of blocks in the partition, size of blocks, free block
count,
● Directory structure per file system used to organize files,eg.
inodes (UFS), master file table (NTFS)
● Per-file File Control Block: contains information about the file
eg. permission, owner, size, location
■ In-memory information
● In-memory mount table
● In-memory directory structure cache
● System-wide open-file table
● Per-process open-file table
A Typical File Control Block
In-Memory File System Structures
■ The following figure illustrates the necessary file system structures

provided by the operating systems.
■ Figure 12-3(a) refers to opening a file.
■ Figure 12-3(b) refers to reading a file.
In-Memory File System Structures
Virtual File Systems
■ How does an operating system allow multiple types fo file systems

to ve integrated into thet directory structure?
■ Virtual File Systems (VFS) provide an object-oriented way of

implementing file systems.
■ 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.
Schematic View of Virtual File System
■ File system interface: open(), read(0, write(0
■ VFS interface
● Separates file-system-generic operation from their
implementation
● Provides a mechanism for uniquely representing a file
throughout the network
■ Local file system
Directory Implementation
■ Linear list of file names with pointer to the data blocks.

● simple to program
● time-consuming to execute
■ Hash Table – linear list with hash data structure.

● decreases directory search time
● collisions – situations where two file names hash to the same
location
● fixed size
Allocation Methods
■ An allocation method refers to how disk blocks are allocated for

files:
■ Contiguous allocation
■ Linked allocation
■ Indexed allocation
Contiguous Allocation
■ 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)
■ Files cannot grow
Contiguous Allocation of Disk Space
Extent-Based Systems
■ Many newer file systems (I.e. Veritas File System) use a modified
contiguous allocation scheme
■ Extent-based file systems allocate disk blocks in extents
■ An extent is a contiguous block of disks

● Extents are allocated for file allocation
● A file consists of one or more extents.
Linked Allocation
■ Each file is a linked list of disk blocks: blocks may be scattered

anywhere on the disk.
block = pointer
Linked Allocation (Cont.)
■ Simple – need only starting address

■ Free-space management system – no waste of space
■ No random access
■ Mapping
File-allocation table (FAT) – disk-space allocation used by MS-DOS

and OS/2.
Linked Allocation
File-Allocation Table
Indexed Allocation
■ Brings all pointers together into the index block.

■ Logical view.
index table
Example of Indexed Allocation
Indexed Allocation (Cont.)
■ Need index table
■ Random access
■ Dynamic access without external fragmentation, but have
overhead of index block.
■ Mapping from logical to physical in a file of maximum size of
256K words and block size of 512 words. We need only 1
block for index table.
Indexed Allocation – Mapping (Cont.)
■ Mapping from logical to physical in a file of unbounded
length (block size of 512 words).
■ Linked scheme – Link blocks of index table (no limit on size).
Indexed Allocation – Mapping (Cont.)
outer-index
index table file
Combined Scheme: UNIX (4K bytes per block)
Free-Space Management
■ Bit vector (n blocks)

0 1 2 n-1
…
0 ⇒ block[i] free
bit[i] =



1 ⇒ 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
disk size = 230 bytes (1 gigabyte)
n = 230/212 = 218 bits (or 32K bytes)
■ Easy to get contiguous files
■ Linked list (free list)
● Cannot get contiguous space easily
● No waste of space
■ Grouping
■ Counting
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
 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
Directory Implementation
■ Linear list of file names with pointer to the data blocks

● simple to program
● time-consuming to execute
■ Hash Table – linear list with hash data structure
● decreases directory search time
● collisions – situations where two file names hash to the same
location
● fixed size
Linked Free Space List on Disk
Efficiency and Performance
■ Efficiency dependent on:

● disk allocation and directory algorithms
● types of data kept in file’s directory entry
■ Performance
● disk cache – separate section of main memory for frequently
used blocks
● free-behind and read-ahead – techniques to optimize
sequential access
● improve PC performance by dedicating section of memory as
virtual disk, or RAM disk
End of Chapter 11

Chapter 11: File System Implementation

Uploaded by

Copyright:

Available Formats

Chapter 11: File System Implementation

Uploaded by

Document Information

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

Chapter 11: File System Implementation

Uploaded by

Copyright:

Available Formats

Chapter 11: File System

■ To describe the details of implementing local file systems and

■ I/O controls consists of device drivers and interrupt handlers

■ The following figure illustrates the necessary file system structures

■ Figure 12-3(a) refers to opening a file.

■ Figure 12-3(b) refers to reading a file.

■ How does an operating system allow multiple types fo file systems

■ Virtual File Systems (VFS) provide an object-oriented way of

■ Linear list of file names with pointer to the data blocks.

■ Hash Table – linear list with hash data structure.

■ An allocation method refers to how disk blocks are allocated for

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

■ Simple – only starting location (block #) and length (number

■ Wasteful of space (dynamic storage-allocation problem)

■ Files cannot grow

■ Extent-based file systems allocate disk blocks in extents

■ An extent is a contiguous block of disks

■ Each file is a linked list of disk blocks: blocks may be scattered

■ Simple – need only starting address

File-allocation table (FAT) – disk-space allocation used by MS-DOS

■ Brings all pointers together into the index block.

index table file

■ Bit vector (n blocks)

Block number calculation

(number of bits per word) *

■ Bit map requires extra space

■ Linear list of file names with pointer to the data blocks

■ Efficiency dependent on:

You might also like