Chapter 4 – File Management System

Complete Study Guide & Exam Preparation

Covers: File concepts · FMS roles · Disk structure · Allocation methods · FAT / NTFS / EXT2-3-4 ·
Permissions · Exam questions

1. What is a File?

A file is a structured set of data representing an external object as seen by a program. It is characterized
by:
• Its type (e.g., text, binary, executable)
• Its name
• Its path (location in the directory tree)
Key note: The definition of a file is independent of the storage medium used.

File Types
Type Description Readable?

ASCII 8-bit character file (text, config, scripts) Yes – directly

Binary Executable code, raw data (images, videos) No – needs interpreter

2. File Management System (FMS)

A file system is the method and data structure used by an OS to control how data is stored and retrieved
from storage media (HDD, SSD, USB).

Roles / Functions of the FMS

• File Manipulation: Create, delete, read, write, rename files
• Space Allocation: Allocate and manage space on secondary storage
• File Localization: Locate files via paths and directories
• File Security & Control: Manage access rights, permissions, ownership
• Backup: Copy files to non-volatile storage
• Abstraction: Give users a logical view (root → dirs → files)

3. File Organization

3.1 Logical Level

Users see files organized in a hierarchical tree of directories. Directories are treated as special files,
allowing unified processing. The tree is recursive – any directory can contain files and sub-directories.
 3.2 Physical Level
At the physical level, data is stored in blocks – the smallest unit a storage device can handle. The FMS
maps file names to the blocks that make up each file.

3.3 File Structure Types

Type Description Example

Without structure Just a sequence of bytes; OS does not interpret content Unix files

Fixed-length records Records of equal size, like database tables Old databases

Tree of records Variable-length records with keys for fast search Indexed DBs

4. File Metadata (Fundamental Information)

Metadata is the information the OS needs to manage and describe a file:

• File name
• Address of the first block on disk
• Access rights / permissions
• Date of creation
• Date and time of last modification
• File size
• Owner (and owner group in Unix/Linux)
• File type (simple, symbolic link, directory, device)
• Number of blocks used
• Pointer to content (inode pointer)

5. Hard Disk & Cache Memory

HDD components: platters (rotating disks), tracks (concentric rings), sectors (512 bytes each), clusters
(groups of sectors), cylinders (same track on all platters).
Key fact: HDD access is ~1,000,000 times slower than RAM. To minimize disk I/O, the OS uses cache
memory (buffering reads/writes).

Disk Scheduling Algorithms (to minimize head movement)

Algorithm Strategy Total Movement (example: start=14, requests=17,18,4,11,2,12)

FIFO Serve requests in arrival order 44 tracks

SSTF (Shortest Seek Time First)

Serve nearest request first 26 tracks

SCAN/LOOK Sweep in one direction, then reverse 20 tracks (LOOK)

Cache Block States

• Locked: Access reserved to one process
• Valid: Data in the block is valid
• To write ('dirty'): Data must be written to disk before block is reused
 • Active: Kernel is currently reading/writing the block
• Waiting: A process is waiting for the block to be freed
Cache Pros: Reduces disk traffic, protects against concurrent writes. Cons: Data loss risk on system
crash; copy overhead for every I/O.

6. Disk Space Allocation Methods

Method How it works Benefits Disadvantages

Contiguous File occupies consecutive blocks. • Easy to implement • Hard to find free contiguous space
Allocation Defined by start block + length. • Simple addressing • Must know file size upfront
• Limited seek time • External fragmentation

Chained Blocks Blocks anywhere on disk; each block holds a• No

pointer
external
to thefragmentation
next. • Pointer wastes space
(Linked List) (Used in FAT) • No need to know file size in advance
• Sequential access only
• No direct access

Indexed An index block stores all pointers to file blocks.

• Direct access possible • Index block wastes space if file is small
Allocation (Used in EXT2/3) • No external fragmentation
7. The Different File Systems

Common file systems:

• FAT (File Allocation Table): Microsoft – DOS/Windows – USB drives
• NTFS (New Technology File System): Microsoft – Windows NT onwards
• Ext2 / Ext3 / Ext4 (Extended): Linux/Unix
• TMPFS (Temporary File System): Embedded systems, RAM-based
• VMFS (Virtual Machine FS): Virtualization tools (VMware)
• NFS (Network File System): Linux network sharing

7.1 FAT – File Allocation Table

Designed by Microsoft in 1977. Uses a linked list (chained allocation). Files are tracked via a table (the
FAT) stored at the start of the partition.

FAT Structure
Boot sector → FAT table → (optional FAT copy) → Root directory → Clusters (data)

FAT Versions Compared

Version Bits Max File Size Max Volume Notes

FAT12 12 < 16 MB < 32 MB Floppy disks (2,847 clusters for 1.44 MB)

FAT16 16 4 GB 4 GB (cluster 64 KB) MS-DOS, Win 95/98; max 65,536 clusters

FAT32 28/32 4 GB (2^32-1) 16 TB (cluster 64 KB) Better space use; root dir unrestricted

FAT Clusters & Fragmentation

• A cluster = n sectors (512 bytes each), where n is a power of 2.
• Every file occupies a whole number of clusters → internal fragmentation.
• Example: 8-sector cluster = 4,096 bytes. A 1-byte file wastes 4,095 bytes.
• FAT table formula: FAT size = (partition size / cluster size) × entry size

FAT Directory Entry (32 bytes)

Each entry contains: filename (8.3 format), extension, attributes (READ_ONLY, HIDDEN, SYSTEM,
DIRECTORY, ARCHIVE, VOLUME_ID), last modification date/time, first cluster number, file size.

FAT Pros & Cons

Pros: Simple, widely compatible, known by many OSes.
Cons: File size limited to 4 GB; prone to fragmentation (especially FAT16); not suitable for large partitions;
no built-in permissions.

7.2 NTFS – New Technology File System

Developed by Microsoft, native to Windows NT (1993). Successor to FAT. Designed for multi-user
environments with security, reliability, and large volumes.

Key features:
• MFT – Master File Table: One entry (1 KB) per file. All metadata stored as attributes. Size never
decreases.
• ACL – Access Control List: Fine-grained permissions per file/directory for users/groups.
• Journaling ($LogFile): Logs operations for crash recovery and consistency.
 • Large volume support: Up to 256 TB volume; 16 TB max file size.
• Compression/Encryption: Per-file compression (LZ77) and encryption (AES/DES).
• MFT Mirror ($MFTMirr): Backup of first 4 MFT entries for fault recovery.

NTFS Structure
$Boot → MFT zone (buffer) → File/directory space → $MFTMirr copy

NTFS MFT Metadata Files

• $MFT (0) – MFT itself
• $MFTMirr (1) – MFT mirror
• $LogFile (2) – Journal
• $Volume (3) – Volume info
• $AttrDef (4) – Attribute definitions
• \ (5) – Root directory
• $Bitmap (6) – Cluster allocation map
• $Boot (7) – Boot sector
• $BadClus (8) – Bad cluster list
• $Secure (9) – Security settings
• User files start at entry 16+

NTFS vs FAT32 Summary

Feature FAT32 NTFS

Max file size 4 GB 16 TB

Max volume 2 TB 256 TB

Permissions None ACL

Journaling No Yes ($LogFile)

Encryption No Yes (EFS)

Compression No Yes (LZ77)

Fragmentation High Lower (but possible)

Startup speed Slower (large FAT) Faster

 7.3 EXT2 / EXT3 / EXT4 – Extended File System
The extended file system family is the standard for Linux. First created in April 1992; ext was the first
Linux-specific FS.

Version Year Max File Max Volume Key Addition

EXT2 1993 2 TB 32 TB First Linux FS; no journaling

EXT3 2001 2 TB 32 TB Added journaling (crash recovery)

EXT4 2008 16 TB 1 EB Extents, delayed allocation, huge files

EXT2/3 Disk Structure

Boot sector → [Block Group 0] → [Block Group 1] → ... → [Block Group N]
Each block group contains:
• Super-Block – global FS info (block size, count, inode count)
• Group Descriptors – info about the group
• Block Bitmap – 1 bit per block: 0=free, 1=allocated
• Inode Bitmap – 1 bit per inode: 0=free, 1=allocated
• Inode Table – array of inodes for files in this group
• Data Blocks – actual file content

EXT2/3 Inodes (Index Nodes)

Each file is described by an inode containing metadata and 15 block pointers:

Pointer Type Entries Blocks Accessible Max file size contribution (1 KB blocks)

Direct (0-11) 12 12 blocks 12 KB

Single Indirect (12) 1 → 256 256 blocks 256 KB

Double Indirect (13) 1 → 256 → 256 256^2 = 65,536 blocks ~64 MB

Triple Indirect (14) 1 → 256 → 256 → 256

256^3 = 16,777,216 blocks ~16 GB
2 3
Total max file size (EXT2): 12 + 256 + 256 + 256 = 16,843,020 KB ≈ 16 GB

EXT3 Journaling
Journaling records all FS operations before they happen. If a crash occurs, the journal is replayed to
restore consistency. EXT2 can be converted to EXT3 without reformatting.
Benefits: Consistency, crash recovery (fault tolerance), file integrity.

8. Permissions & Access Control

8.1 NTFS Permissions (ACL)

NTFS uses Access Control Lists (ACL) – a list of entries specifying which users or groups can perform
which operations on a file/directory.
Permission levels: Browse · Read · Write · Read & Execute · Modify · Full Control

8.2 Unix/Linux Permissions

Unix uses a 3-category model: Owner (u), Group (g), Others (o). Each has Read (r=4), Write (w=2),
Execute (x=1) rights. EXT2/3 support POSIX permissions + ACL.
9. Solved Exam Example – EXT2 Inode Calculation

Given: Block size = 1 KB (1024 bytes). Inode has 12 direct + 1 single indirect + 1 double indirect + 1 triple
indirect pointer. Each pointer = 4 bytes.
Pointers per indirect block = 1024 / 4 = 256

Q a) Maximum file size?

= (12 × 1 KB) + (256 × 1 KB) + (2562 × 1 KB) + (2563 × 1 KB)
= 12 + 256 + 65,536 + 16,777,216 KB
= 16,843,020 KB ≈ 16 GB

Q b) Blocks needed for a 100,000-byte file?

Data blocks = ceil(100,000 / 1,024) = 98 data blocks
• 12 via direct pointers → remaining = 86 blocks
• 86 blocks via single indirect → needs 1 indirect block
Total = 98 data + 1 indirect = 99 blocks

Q c) Fragmentation type and wasted space?

Type: Internal fragmentation (fixed-size blocks).

Wasted space in last data block:

• 97 full blocks = 97 × 1024 = 99,328 bytes used
• Remaining data = 100,000 − 99,328 = 672 bytes
• Last block allocated = 1,024 bytes → Wasted = 1,024 − 672 = 352 bytes

Wasted space in indirect pointer block:

• 256 pointer slots × 4 bytes = 1,024 bytes allocated
• Only 86 pointers used = 86 × 4 = 344 bytes
• Wasted = (256 − 86) × 4 = 170 × 4 = 680 bytes

Total internal fragmentation = 352 + 680 = 1,032 bytes

10. Likely Exam Questions & Answers

Q1: What is a file system? What is its role?

A file system is the method and data structure used by an OS to control how data is stored and
retrieved from storage media. Its role includes: providing an abstract view of data, organizing files in
directories, creating/deleting files and directories, allocating space, localizing files, ensuring security,
and backing up data.

Q2: What is the difference between contiguous, chained, and indexed allocation?
Contiguous: files occupy consecutive blocks (simple addressing, but fragmentation). Chained: blocks
anywhere on disk, linked by pointers (no fragmentation, sequential access only). Indexed: an index
block holds all pointers to file blocks (direct access, wasted space if file is small).

Q3: What is a FAT? How does it work?

FAT (File Allocation Table) is a linked-list table stored at the start of the partition. Each entry
corresponds to a cluster. An entry contains the number of the next cluster in the chain. Special values
indicate end-of-file or free clusters.
Q4: What are the limitations of FAT32?
Max file size: 4 GB (2^32 - 1 bytes). No built-in permissions/security. Prone to fragmentation. Not
suitable for very large partitions. Max volume: 2 TB.

Q5: What is NTFS? How does it differ from FAT?

NTFS is Microsoft's advanced file system (Windows NT onwards). Key differences: supports up to 16
TB files and 256 TB volumes; uses ACL for fine-grained permissions; has journaling for crash recovery;
stores all metadata in the MFT; supports compression and encryption. FAT has none of these features.

Q6: What is the MFT in NTFS?

The Master File Table is the core of NTFS. It contains one 1 KB entry per file (including system files).
All file attributes (name, timestamps, permissions, data) are stored within or referenced from the MFT
entry. The MFT never shrinks in size.

Q7: What is journaling? Which file systems use it?

Journaling records all file system operations in a log (journal) before applying them. If a crash occurs,
the system can replay the journal to restore consistency. EXT3, EXT4, and NTFS all use journaling.
EXT2 does not.

Q8: What is an inode in EXT2/3?

An inode (index node) is a data structure that stores all metadata about a file except its name. It
contains: access rights, dates, owner, file size, block count, file type, and 15 block pointers (12 direct, 1
single indirect, 1 double indirect, 1 triple indirect).

Q9: What is internal fragmentation? Give an example.

Internal fragmentation occurs when a file is allocated more space than it actually needs, due to
fixed-size blocks/clusters. Example: a 1-byte file in a 4 KB cluster wastes 4,095 bytes.

Q10: What is the disk scheduling algorithm SSTF? Compare with FIFO.
SSTF (Shortest Seek Time First) serves the request closest to the current head position. It minimizes
total head movement compared to FIFO (which serves in arrival order). Example: with start=14 and
requests 17,18,4,11,2,12: FIFO = 44 tracks, SSTF = 26 tracks, LOOK = 20 tracks.

Q11: Calculate the FAT size for a 512 GB FAT32 volume with 4 KB clusters.
Number of entries = 512 GB / 4 KB = 2^9 × 2^30 / 2^12 = 2^27 entries. FAT entry size = 4 bytes (32
bits). FAT size = 2^27 × 4 = 2^29 bytes = 512 MB. (Course slide uses slightly different rounding: ≈ 4
GB with 2^6 byte entry – check your notes.)

Q12: What are the three types of file structure?

a) Without structure: just a byte sequence (Unix approach). b) Fixed-length records: equal-size records
like DB tables. c) Tree of variable-length records: each record has a key for fast searching.

Q13: What is the difference between EXT2 and EXT3?

EXT3 adds journaling to EXT2. An EXT2 volume can be converted to EXT3 without reformatting. Both
support 2 TB max file size and 32 TB max volume. EXT3 uses a journal ($LogFile equivalent) for crash
recovery and consistency.

Q14: What are the components of a hard disk?

 Platters (rotating magnetic disks), tracks (concentric rings on a platter), sectors (smallest physical unit,
512 bytes), clusters (groups of sectors), cylinders (same track across all platters), read/write heads
(one per side).

Q15: What is the Linux directory hierarchy (FHS)?

/bin (user binaries), /boot (bootloader), /dev (devices), /etc (config), /home (user dirs), /lib (libraries),
/mnt (temp mounts), /opt (optional packages), /proc (process info), /root (root home), /sbin (system
binaries), /tmp (temp files), /usr (multi-user apps), /var (variable files).
11. Quick Reference – File Systems Comparison

Property FAT32 NTFS EXT2 EXT3 EXT4

Developer Microsoft Microsoft Rémy Card S. Tweedie Mingming Cao

Year 1996 1993 1993 2001 2008

Max file 4 GB 16 TB 2 TB 2 TB 16 TB

Max volume 2 TB 256 TB 32 TB 32 TB 1 EB

Journaling No Yes No Yes Yes

Permissions None ACL UNIX+ACL UNIX+ACL POSIX

Encryption No Yes (AES) No No No

Compression No Yes (LZ77) No No No

Allocation Linked list B-tree Bitmap+table Bitmap+table Extent+bitmap

OS Any Windows Linux/BSD Linux/BSD Linux

Good luck on your exam! Remember: understand the concepts, not just memorize the facts.