Q5Operating System

A file system provides the mechanism for on-line storage and access to both data and programs. It consists of two distinct parts: a collection of files (each storing related data) and a directory structure (organizing and providing information about all the files in the system). File systems are stored permanently on secondary storage (disks).

• Application Programs: User programs that request file operations.
• Logical File System: Manages file metadata (directory structures, file control blocks/inodes). Translates file names to file control block numbers.
• File-Organization Module: Knows about files and their logical and physical blocks. Translates logical block addresses to physical block addresses. Includes free-space management.
• Basic File System: Issues generic commands to the device driver to read and write physical blocks on disk.
• I/O Control: Device drivers and interrupt handlers that transfer data between disk and main memory.
• Devices: Physical disk drives.

• Contiguous Allocation: Each file occupies a set of contiguous disk blocks. Simple directory entry (starting block + length). Supports both sequential and direct access. Suffers from external fragmentation and file growth difficulties. Example: CD-ROM file systems.
• Linked Allocation: Each file is a linked list of disk blocks scattered anywhere on disk. Each block contains a pointer to the next block. The directory contains only the first block pointer. Eliminates external fragmentation; supports dynamic growth. Disadvantage: Only sequential access; pointer overhead; pointer loss causes data loss. FAT (File Allocation Table) stores all links in a separate table — enables direct access. Used in DOS/Windows FAT32.
• Indexed Allocation: Each file has an index block containing all pointers to its data blocks. Directory entry points to the index block. Supports direct access without external fragmentation. For large files: linked index blocks, multilevel index, or combined scheme (like Unix inode). Unix inode: 12 direct pointers + 1 single indirect + 1 double indirect + 1 triple indirect.

A directory maps file names to their file control blocks. Various directory organization structures exist:

• Single-Level Directory: All files in one directory. Simple but requires unique names for all files; not practical for multiple users. Oldest structure.
• Two-Level Directory: Separate User File Directory (UFD) for each user; Master File Directory (MFD) at top level. Solves naming conflict between users. Cannot group files by type/project; limited sharing.
• Tree-Structured Directory: Generalization to arbitrary depth. Sub-directories form a tree rooted at '/' (root). Supports grouping of files by project, type, etc. Absolute path from root; relative path from current directory. Most widely used (UNIX, Windows). Deletion of directory with files requires recursive deletion or only empty directories allowed.
• Acyclic-Graph Directory: Allows sharing of files/directories. Implemented with hard links (directory entry pointing to same inode) and symbolic (soft) links (a file containing path to target). Link count in inode prevents premature deletion. Used in UNIX/Linux.
• General Graph Directory: Allows arbitrary links including cycles. Requires garbage collection for cycle detection and removal of unreachable files. Rarely used in practice.

Example: In Linux (ext4), the file system uses indexed allocation (inodes with direct + indirect block pointers), tree-structured directories with acyclic-graph extension (hard links and symlinks). Windows NTFS uses a Master File Table (MFT) where every file/directory is a record with extents for data allocation.