04

File Systems

Chapter 4 • Intermediate

50 min

File Systems

A file system is a method of storing and organizing files on storage devices. It provides a way to store, retrieve, and manage data persistently.

File Concept

What is a File?

A file is a named collection of related information recorded on secondary storage.

File Attributes:

  • Name: Human-readable identifier
  • Type: File type (text, binary, executable)
  • Location: Pointer to file location on device
  • Size: Current file size
  • Protection: Access control information
  • Time, Date, User Identification: Metadata

File Operations

  1. Create: Create a new file
  2. Write: Write data to file
  3. Read: Read data from file
  4. Reposition (Seek): Move file pointer
  5. Delete: Remove file from system
  6. Truncate: Erase file contents but keep attributes
  7. Open: Prepare file for access
  8. Close: Release file resources

File Types

Text Files:

  • Sequence of characters organized into lines
  • Human-readable
  • Examples: .txt, .c, .java

Source Files:

  • Source code in various languages
  • Examples: .c, .cpp, .java, .py

Object Files:

  • Compiled source code
  • Examples: .o, .obj

Executable Files:

  • Ready-to-run programs
  • Examples: .exe, .out

Binary Files:

  • Non-text files
  • Examples: images, videos, databases

File Access Methods

1. Sequential Access

Read/write file sequentially from beginning to end.

Example:

code
read next
write next
reset (to beginning)

Use Cases: Tapes, logs, sequential processing

2. Direct Access (Random Access)

Read/write file at any position directly.

Operations:

  • read n (read block n)
  • write n (write block n)
  • position to n (move to block n)
  • read next
  • write next

Use Cases: Databases, indexed files

3. Indexed Sequential Access

Combines sequential and direct access using an index.

Directory Structure

A directory is a collection of files and subdirectories.

Directory Operations

  1. Search: Find file in directory
  2. Create: Create new file
  3. Delete: Remove file
  4. List: List directory contents
  5. Rename: Change file name
  6. Traverse: Access all files in directory

Directory Organization

1. Single-Level Directory

All files in one directory.

Advantages:

  • Simple
  • Easy to understand

Disadvantages:

  • No organization
  • Name conflicts
  • No grouping

2. Two-Level Directory

Separate directory for each user.

Advantages:

  • Solves name conflicts
  • User isolation

Disadvantages:

  • No grouping
  • No sharing

3. Tree-Structured Directory

Hierarchical directory structure (most common).

Advantages:

  • Natural organization
  • Easy navigation
  • Grouping possible

Path Names:

  • Absolute Path: From root (/usr/bin/file)
  • Relative Path: From current directory (../file)

4. Acyclic-Graph Directory

Allows sharing of files and subdirectories.

Advantages:

  • File sharing
  • Multiple paths to same file

Disadvantages:

  • Complexity in deletion
  • Need reference counting

5. General Graph Directory

Allows cycles (not commonly used).

File System Implementation

Allocation Methods

1. Contiguous Allocation

Each file occupies contiguous blocks on disk.

Advantages:

  • Simple to implement
  • Fast sequential access
  • Direct access possible

Disadvantages:

  • External fragmentation
  • File size must be known in advance
  • Difficult to grow files

Example:

File A: Blocks 2-5

File B: Blocks 6-8

File C: Blocks 9-12

2. Linked Allocation

Each file is a linked list of disk blocks.

Advantages:

  • No external fragmentation
  • File can grow dynamically
  • Simple to implement

Disadvantages:

  • No direct access
  • Pointer overhead
  • Reliability issues (broken links)

Example:

File A: 2 → 5 → 11 → 12

3. Indexed Allocation

Each file has an index block containing pointers to data blocks.

Advantages:

  • Direct access possible
  • No external fragmentation
  • File can grow

Disadvantages:

  • Index block overhead
  • Limited file size (depends on index block size)

Example:

File A Index Block: [2, 5, 11, 12, ...]

Multi-Level Index:

  • Single indirect: Index block points to data blocks
  • Double indirect: Index block points to index blocks
  • Triple indirect: Index block points to double indirect blocks

Free Space Management

1. Bit Vector (Bitmap)

Each block represented by one bit (0 = free, 1 = allocated).

Advantages:

  • Simple
  • Efficient to find free blocks

Disadvantages:

  • Not efficient for large disks

2. Linked List

Free blocks linked together.

Advantages:

  • No waste of space
  • Simple

Disadvantages:

  • Not efficient for finding free blocks

3. Grouping

Store addresses of n free blocks in first free block.

4. Counting

Store address of first free block and count of consecutive free blocks.

Disk Scheduling

Disk scheduling algorithms determine the order in which disk I/O requests are serviced.

Disk Structure

  • Tracks: Concentric circles on disk
  • Sectors: Segments of tracks
  • Cylinders: Same track number across all surfaces
  • Seek Time: Time to move disk arm to desired cylinder
  • Rotational Latency: Time for desired sector to rotate under head
  • Transfer Time: Time to transfer data

Disk Scheduling Algorithms

1. First-Come-First-Served (FCFS)

Service requests in order of arrival.

Example:

Queue: 98, 183, 37, 122, 14, 124, 65, 67

Current position: 53

Total head movement:

= 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640

2. Shortest Seek Time First (SSTF)

Service request closest to current head position.

Example:

Queue: 98, 183, 37, 122, 14, 124, 65, 67

Current position: 53

Total head movement:

53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183

= 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236

Advantages:

  • Better than FCFS
  • Reduces average response time

Disadvantages:

  • Can cause starvation
  • Not optimal

3. SCAN (Elevator Algorithm)

Move head in one direction, service all requests, then reverse direction.

Example:

Queue: 98, 183, 37, 122, 14, 124, 65, 67

Current position: 53, moving right

Path: 53 → 65 → 67 → 98 → 122 → 124 → 183 → (end) → 37 → 14

Total head movement:

12 + 2 + 31 + 24 + 2 + 59 + 146 + 23 = 299

4. C-SCAN (Circular SCAN)

Like SCAN but returns to beginning instead of reversing.

Example:

Queue: 98, 183, 37, 122, 14, 124, 65, 67

Current position: 53, moving right

Path: 53 → 65 → 67 → 98 → 122 → 124 → 183 → (end) → (beginning) → 14 → 37

Total head movement:

12 + 2 + 31 + 24 + 2 + 59 + (183-0) + 14 + 23 = 340

5. LOOK

Like SCAN but reverses direction at last request instead of end of disk.

Example:

Queue: 98, 183, 37, 122, 14, 124, 65, 67

Current position: 53, moving right

Path: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 37 → 14

Total head movement:

12 + 2 + 31 + 24 + 2 + 59 + 146 + 23 = 299

6. C-LOOK

Like C-SCAN but reverses at last request.

GATE CS Important Points

  1. File Allocation: Know contiguous, linked, indexed allocation methods
  2. Directory Structure: Understand tree-structured and acyclic-graph directories
  3. Disk Scheduling: Master FCFS, SSTF, SCAN, C-SCAN, LOOK algorithms
  4. Free Space Management: Understand bit vector and linked list methods
  5. File Access Methods: Know sequential, direct, and indexed sequential access

Practice Tips

  1. Trace Disk Scheduling: Practice calculating head movement for different algorithms
  2. File Allocation: Understand how files are stored using different methods
  3. Directory Traversal: Practice navigating directory structures
  4. Previous Year Questions: Solve GATE file system questions from last 10 years
Previous
Memory Management

Related Tutorials