Comprehensive Study Notes on Operating Systems: File Management

Introduction to File Management

• File management is a critical aspect of Operating Systems (OS) because files serve as the central element to most applications.
• The file system is one of the most vital components of the OS from a user perspective; some users perceive the OS as being exclusively the file system.
• Desirable Properties of File Systems:
    - Long-term existence: Files must persist after processes terminate.
    - Large capacity: Must be capable of storing massive amounts of information.
    - Sharable: Information must be accessible and sharable between different processes.
    - Ease of Access: Information should be stored in a structured way that facilitates easy retrieval.
    - Reliability: The system must guarantee data validity and minimize the risk of lost or destroyed data.
• Basic Functions of a File System:
    - Presenting a logical/abstract view of files to users while hiding physical storage details.
    - Facilitating and optimizing the sharing and usage of physical I/O devices.
    - Providing protection mechanisms for data during transfer or management.
• File Management System Components:
    - It consists of system utility programs running as privileged applications.
    - It is primarily concerned with secondary storage.
    - Standard provided functions include: Create, Delete, Open, Close, Read, and Write.

Data Hierarchy: Fields, Records, Files, and Databases

• File management provides services for users and applications through a structured hierarchy of data.
• Fields:
    - The basic element of data containing a single value (e.g., a name or date).
    - Can be fixed length or variable length.
    - Variable-length fields are separated by demarcation fields.
• Records:
    - A collection of related fields treated as a single unit.
    - Can be fixed or variable length; variable-length records include a length attribute field.
    - Example: An individual Employee record.
• Files:
    - A collection of similar records treated as a single entity.
    - Files are identified by a filename.
    - They represent the smallest unit generally subject to access control restrictions, though controls can occasionally extend to individual fields.
• Databases:
    - A collection of related data with explicit relationships between elements and fields.
    - May encompass one or more files.
    - Databases can be managed by a Database Management System (DBMS) and may exist independently of the OS.

Requirements for General Purpose File Systems

• Users must have the ability to create, delete, read, write, and modify files.
• Users require controlled access to other users' files.
• Users must be able to control what specific types of access (permissions) are allowed on their own files.
• Users should be able to define their own file structures appropriate to their specific needs.
• The system must allow users to move data between files.
• Data backup and restoration capabilities must be provided in case of damage or loss.
• The system should offer a convenient method of access via symbolic names.

File System Software Architecture

• Typical Organization (Top to Bottom):
    1. User Program
    2. Logical I/O
    3. Basic I/O Supervisor
    4. Basic File System
    5. Device Drivers (Disk/Tape)
• Device Drivers:
    - The lowest level of the architecture; part of the OS.
    - Communicates directly with physical peripherals (disk/tape drives).
    - Responsible for starting I/O operations and processing completion requests.
• Basic File System:
    - Operates at the physical I/O level of the OS.
    - Primary interface outside the computer.
    - Deals with the exchange, placement, and buffering of data blocks in memory.
    - Does not understand the content or specific structure of the files.
• Basic I/O Supervisor:
    - Responsible for the initiation and termination of all file I/O.
    - Manages control structures for device I/O, scheduling, and file status.
    - Selects and schedules I/O with specific devices.
• Logical I/O:
    - Enables access to records for users and applications.
    - Provides general-purpose record I/O capability and maintains basic file metadata.
• Access Method:
    - The layer closest to the user.
    - Reflects different possible file structures (Pile, Sequential, etc.).
    - Provides a standard interface between applications and the underlying file system/devices.

File Organization and Performance Criteria

• File organization refers to the logical structure of records, not their physical storage.
• Important Criteria for Selection:
    - Short access time.
    - Ease of updates.
    - Economy of storage.
    - Simple maintenance.
    - Reliability.
• The priority of these concerns shifts based on usage (e.g., a read-only CD vs. a primary hard drive) and criteria may conflict.
• Common File Organizations:
    - The Pile: Data is collected in arrival order with no structure. Access is performed via exhaustive search. Used for accumulating mass data.
    - Sequential File: Uses a fixed format with records of identical length and identical fields. Contains a Key Field for unique identification. Records are stored in key sequence. Excellent for batch operations; poor for individual updates/additions. Updates often require a separate log/transaction file to be periodically merged.
    - Indexed Sequential File: Retains sequential characteristics (key order) but adds an index for random access and an overflow file.
    - Indexed File: Uses multiple indexes for various key fields. May use an exhaustive index (one entry per record). Adding a record requires updating all associated index files.
    - Direct/Hashed File: Allows direct access to any block at a known address. Requires a key field for each record; a hash function determines the storage location. Requires fixed-length records.

B-Trees: Structure and Insertion

• Large sequential index files are inefficient; structured index files like B-Trees provide faster access.
• Tree Structure Logic:
    - The file is broken into sections.
    - Upper levels consist of sequenced pointers to lower-level sections.
    - This can extend to multiple levels.
• Balanced Tree Properties:
    - Searching is only efficient if the tree is balanced (all branches of equal length).
    - B-Trees are self-balancing and are the standard for database and OS index organization.
• B-Tree Characteristics:
    - Consists of nodes and leaves.
    - Each node contains at least one unique key and pointers to child nodes or leaves.
    - Keys in a node are stored in nondecreasing order.
    - Nodes exert a limit on the maximum number of keys.
    - Advantage: B-trees are typically very shallow, reducing the depth of searches.
• B-Tree Order Definitions:
    - Usually defined as the minimum number of keys in a non-root node.
    - Knuth Definition: The maximum number of children ($\text{max keys} + 1$).
• Insertion Process:
    1. Search for the key as in a binary tree.
    2. If the leaf node has room, insert the key.
    3. If no room, split the node around the median key.
    4. Move the median key to the parent node and split the original node into two leaves around it.
    5. If the parent is full, split the parent and continue the process up to the root if necessary.
    - Non-backtracking logic: To avoid working back up, the system can split every full node encountered while searching downward for the insertion point.

Blocks, Records, and Blocking Methods

• Records are the logical unit of access, but Blocks are the unit of I/O for secondary storage.
• Blocking Trade-offs:
    - Larger block size: More records per read (good for locality of reference) but may include unneeded records and requires larger buffers.
• Three Common Blocking Approaches:
    1. Fixed Blocking: Fixed-length records are used, and an integral number of records fit per block. This is the default for sequential files. Unused space at the end of a block causes internal fragmentation.
    2. Variable-length Spanned Blocking: Variable-length records can span multiple blocks. A pointer at the end of a block directs the system to the next block. Highly storage-efficient but difficult to implement; spanning records requires two I/O operations and complicates updates.
    3. Variable-length Unspanned Blocking: Variable-length records are used but cannot span blocks. This results in wasted space in blocks if the next record cannot fit, and no record can be larger than a block size.

Filenames and File Links

• Files are typically accessed by name, and OS should recognize file types (e.g., to prevent printing binary files).
• Type Identification: Historically managed via extensions; UNIX uses the file command to examine the "magic number."
• Hard Links:
    - Additional aliases for a file.
    - Multiple filenames for the exact same physical blocks.
    - Deleting one hard link (rm) does not delete the data until all links are removed.
    - Limited to the same filesystem.
    - Cannot be created for directories to prevent cycles.
• Soft (Symbolic) Links:
    - A pointer to a filename, not the physical data.
    - Distinguishable from the original file.
    - Can point to non-existent files or files on other systems.
    - Limited to the same filesystem.

UNIX File Types

• Regular Files: The most common type; treated as a byte stream with no kernel-level structure support.
• Directories: Binary files containing lists of files. Each entry is a file/inode pair used to associate names with directory locations.
• Character-special Files: Used for hardware/peripheral communication. Devices perform their own buffering (raw character stream).
• Block-special Files: Used for hardware communication; the kernel handles the buffering.
• These are typically found in the /dev directory.

Secondary Storage Management and Allocation

• Allocation Issues:
    - Preallocation: Requires knowing the maximum file size at creation. This often leads to overestimation and wasted space.
    - Portion Size: Can range from allocating the entire file at once to one block at a time. This involves a trade-off between single-file efficiency and overall system efficiency.
• Allocation Methods:
    1. Contiguous Allocation: A single contiguous set of blocks is allocated at creation. The File Allocation Table (FAT) stores the starting block and length. This leads to external fragmentation, eventually requiring compaction.
    2. Chained Allocation: Allocation occurs block-by-block. Each block contains a pointer to the next. No external fragmentation. Optimal for sequential files. However, reading can be inefficient due to constant seeks; consolidation is used to mitigate this.
    3. Indexed Allocation: The FAT contains a block number for an index block. This index block contains separate entries for each portion (block or variable-length) allocated to the file.

Inodes (Index Nodes)

• An Inode is a control structure containing critical metadata for a specific file.
• Each file is controlled by exactly one Inode, though multiple filenames may point to it.
• FreeBSD Inode Contents:
    - Type and access mode.
    - Owner and group identifiers.
    - Creation, last read, and last write timestamps.
    - File size.
    - Sequence of block pointers and total block count.
    - Number of directory entries.
    - Blocksize of data blocks.
    - Kernel/user flags and generation number.
    - Extended attribute information.
• Indirection and File Size:
    - File allocation is dynamic and block-based.
    - The Inode uses direct pointers and multiple levels of indirection to track data blocks.
    - Indirection Example (4KB Block Size, 512 addresses per block):
      - Direct Pointers (12): Accesses up to $12 \times 4\,KB = 48\,KB$.
      - Single Indirect: Accesses up to $512 \times 4\,KB = 2\,MB$.
      - Double Indirect: Accesses up to $512 \times 512 \times 4\,KB = 1\,GB$.
      - Triple Indirect: Accesses up to $512 \times 512 \times 512 \times 4\,KB = 512\,GB$.
    - Indirection allows efficient access to small files without overhead while supporting theoretical maximum file sizes that are extremely large.

Questions & Discussion

• Q: Are there any questions regarding more on file management?
• A: [No response provided in transcript]