File Systems: Structure, Management, and Optimization

1. Non-Volatile Memory

Non-volatile memory retains stored information even when not powered. It is used for secondary storage or long-term persistent storage. Examples include:

• CD
• Hard Disk (similar reading and writing time)
• Solid-State Drive (SSD): No moving mechanical components, no difference for sequential vs. random reading, but a significant difference between reading and writing.
• ROM
• Flash Memory
• Magnetic Tape: Natural sequential reading and writing, suitable for backups.

2. File System

A file is a contiguous logical address space that can be written to, read from, opened, closed, and deleted. It has the following attributes:

• Name
• Unique ID
• Type
• Location
• Size
• Protection
• Date

Information about files is stored in file system structures.

3. Directory

A directory is a collection of nodes containing information about files. It allows for searching, creating, renaming files, and listing a directory. Directories can be organized for:

• Efficiency: Locating a file quickly.
• Naming: Convenient naming for users.
• Grouping: Logical grouping of files.

Directory implementation methods include:

• Linear List: A list of file names with pointers to data blocks. Simple but time-consuming.
• Hash Table: A linear list with a hash data structure. Decreases directory search time but has a fixed size and potential for collisions.

Directory Structures

• Single-Level Directory: A single directory for all users. Easy to implement but has problems with naming, grouping, and sharing.
• Two-Level Directory: Separate directories for each user. Requires path names but allows the same file name for different users. Efficient searching but no grouping capability.
• Tree-Structured Directories: Efficient searching and grouping capability. Requires the concept of a current working directory.

4. Acyclic-Graph Directories

These directories allow for shared subdirectories and files. Aliasing means an object can have different names.

5. File System Mounting

A file system must be mounted before it can be accessed. A mount point, which is a directory, must be prepared. Anything referenced from the mount point before mounting will be hidden after mounting.

6. File Sharing

Sharing files on multi-user systems is desirable. It may be done through a protection scheme. On distributed systems, files may be shared across a network using systems like the Network File System (NFS).

7. Virtual File System (VFS)

VFS provides an object-oriented way of implementing file systems. It allows the same system call interface (the API) to be used for different types of file systems.

8. Allocation Methods

This refers to how disk blocks are allocated for files.

• Contiguous Allocation: Each file occupies contiguous blocks on the disk. Simple, supports random access, but wasteful of space, and files cannot grow easily.
• Extent-Based Allocation: Allocates disk blocks in extents. An extent is a contiguous block of disks. Permits file growth and is a modified form of contiguous allocation.
• Linked Allocation: Each file is a linked list of disk blocks. Simple, no waste of space, but difficult to achieve random access. With FAT (File Allocation Table), allocation chains are stored separately in clusters. Problems include table size, access speed, and reliability.
• Indexed Allocation: Brings all pointers for one file together into an index block. Requires an index table, supports random access, and allows dynamic access without external fragmentation. However, it has the overhead of the index block.

9. NTFS

NTFS uses a database structure. In NTFS, everything is a file, and each file has attributes. The Master File Table (MFT) is a file that contains information about all files, including resident attributes. Non-resident attributes are stored on the disk according to an allocation map. If a file becomes too fragmented and the allocation map cannot fit within the MFT, the allocation map itself becomes non-resident and is moved to the disk, mapped by another allocation map.

10. NTFS vs. FAT

NTFS is suitable for large disks (typically over 500MB). FAT has less memory overhead and is simpler. NTFS features a saved file descriptor, transaction recovery, and uses a B+ tree for directory structure, making it faster for large directories.

11. Free Space Management

• Bit Vector: Uses one bit per block to track free space (n blocks). Requires extra space but makes it easy to find contiguous free space.
• Linked List (Free List): Difficult to get contiguous space but does not waste space.

12. Recovery from a Crash

Consistency checking compares data in the directory structure with data blocks on the disk. System programs can be used to back up data from the disk to another storage device. Lost files or disks can be recovered by restoring data from the backup.

13. Log-Structured File Systems

These file systems record each update to the file system as a transaction. All transactions are written to a log asynchronously. If the file system crashes, all remaining transactions in the log must still be performed. NTFS uses a log-structured file system.