File systems, disk scheduling and protection notes — Unit 5

A Hard Disk is a massive array of physical blocks. The OS abstracts this raw hardware into a logical, user-friendly concept: The File System.

⇒1.1 The File Concept

A file is a named collection of related information recorded on secondary storage. Files have attributes (Name, Identifier, Type, Size, Creation Time) stored in a directory structure.

⇒1.2 Access Methods

• Sequential Access: Information is processed in order, one record after the other (like a cassette tape). Used by editors and compilers.
• Direct (Random) Access: The file is viewed as a numbered sequence of blocks. The program can read/write any block in any order instantly (like a CD). Essential for databases.

A directory is a symbol table that translates file names into their directory entries (which contain the physical disk addresses).

⇒2.1 Evolution of Directories

• Single-Level: One massive directory for all users and all files. Terrible naming conflicts.
• Two-Level: A Master File Directory (MFD) points to User File Directories (UFD). Solves naming conflicts between users, but users still can't group their own files.
• Tree-Structured: The modern standard. An absolute root directory (`/` or `C:\`) with unlimited nested subdirectories. Files are accessed via absolute or relative paths.
• Acyclic Graph: Allows directories to share subdirectories and files using Links (Shortcuts/Symlinks), removing the strict tree hierarchy.

How does the OS allocate physical disk blocks to a logical file?

⇒3.1 Contiguous Allocation

A file occupies a set of contiguous blocks on the disk. The directory entry only needs to store the `Start Block` and `Length`.

• Pros: Extremely fast read performance. The disk read head doesn't need to move much. Excellent for Direct Access.
• Cons: Suffers from severe External Fragmentation. It is also difficult to expand the file later if the adjacent blocks are taken.

Files are a linked list of disk blocks. The blocks can be scattered anywhere on the disk.

The directory entry contains a pointer to the first block and the last block. Each physical block contains data AND a pointer (disk address) to the next block.

• Pros: Solves external fragmentation completely. Files can grow indefinitely.
• Cons: Terrible for Direct Access (to read block 50, you must sequentially read blocks 1 through 49 to follow the pointers). Pointers waste disk space. Reliability is low (if one pointer is corrupted, the rest of the file is lost forever).

FAT (File Allocation Table): A variation used by MS-DOS/Windows where all the pointers are moved out of the blocks and stored in a centralized table at the beginning of the disk, protecting them and allowing faster traversal.

Brings all the pointers together into one location: the Index Block.

Each file has its own Index Block, which is an array of disk-block addresses. The $i^{th}$ entry in the index block points to the $i^{th}$ block of the file.

• Pros: Supports fast Direct Access (look up the index array, instantly get the physical block address). No external fragmentation.
• Cons: Wasted space overhead. A file of only 2 blocks still requires an entire index block to hold just 2 pointers.

Unix/Linux uses a highly optimized version of this called Inodes.

Traditional Hard Disk Drives (HDDs) are mechanical. They consist of spinning magnetic platters and a moving read/write arm.

⇒6.1 Physical Components

Platters are divided into circular Tracks. A track is further divided into Sectors (usually 512 bytes). The set of identical tracks on all vertical platters forms a Cylinder.

⇒6.2 Disk Access Time

Reading from a disk is agonizingly slow because of mechanical movement. Access time = Seek Time + Rotational Latency + Transfer Time.

• Seek Time: The time it takes to move the mechanical arm to the correct Cylinder. (The slowest part).
• Rotational Latency: The time waiting for the spinning platter to rotate the correct Sector under the read head.

Disk scheduling algorithms aim strictly to minimize Seek Time.

The OS maintains a queue of requests for I/O to blocks on various cylinders. The goal is to service these requests with the minimum total head movement.

⇒7.1 FCFS (First-Come, First-Served)

Services requests in the exact order they arrived.
Performance: Fair, but generally provides the worst total head movement. The arm swings wildly back and forth across the disk.

⇒7.2 SSTF (Shortest Seek Time First)

Selects the pending request closest to the current head position.
Performance: Substantially better than FCFS.
Flaw: Causes Starvation. If requests keep arriving near the current head position, requests far away at the edge of the disk will never be serviced.

⇒8.1 SCAN (The Elevator Algorithm)

The disk arm starts at one end of the disk and moves toward the other end, servicing requests as it goes. When it reaches the physical end, it reverses direction and services requests on the way back.

Flaw: Unfair wait times. When the head reverses direction at the edge, it immediately services requests near the edge again, while requests at the far end wait a long time.

⇒8.2 C-SCAN (Circular SCAN)

Provides a more uniform wait time. The head sweeps from 0 to the maximum cylinder, servicing requests. When it hits the maximum cylinder, it immediately returns to cylinder 0 without servicing any requests on the return trip, and starts sweeping up again.

SCAN and C-SCAN force the disk arm to travel to the absolute physical extremes of the disk (e.g., cylinder 0 and cylinder 199), even if there are no pending requests out there.

⇒9.1 LOOK

The smart version of SCAN. The arm only sweeps as far as the furthest pending request in that direction. Once there are no more requests ahead of it, it reverses direction immediately.

⇒9.2 C-LOOK

The smart version of C-SCAN. The arm sweeps up to the furthest request, then jumps back to the lowest pending request (instead of physically jumping to cylinder 0).

A modern OS must protect resources from unauthorized access and defend against malicious attacks.

⇒10.1 Protection vs. Security

• Protection: An internal mechanism controlling access to OS resources. Ensuring Process A cannot read Process B's memory. Controlled by Access Matrix models.
• Security: Defense of the system against external and internal attacks. Requires authentication, encryption, and threat detection.

Protection is conceptually modeled as a matrix.
- Rows represent Domains (Users or Processes).
- Columns represent Objects (Files, Printers).
- Cells represent Access Rights (Read, Write, Execute).

⇒11.1 Implementation

A true matrix is sparse and wastes memory. It is implemented in two ways:

• Access Control Lists (ACL): Attached to the Object (Column-based). The file stores a list of users and their rights. (e.g., File1 says: UserA can Read, UserB can Write). Used by Windows/Linux.
• Capability Lists: Attached to the Domain (Row-based). The user holds a ring of keys (capabilities). To access an object, the user presents the appropriate key to the OS.

The OS is the primary target for malicious software.

⇒12.1 Types of Program Threats

• Trojan Horse: A program that appears legitimate but performs malicious acts covertly.
• Trap Door (Backdoor): A secret entry point left by the developer to bypass security checks.
• Logic Bomb: Malicious code that triggers only when a specific condition is met (e.g., a specific date, or an employee being fired).
• Virus: A self-replicating fragment of code that embeds itself into legitimate host files.
• Worm: A standalone program that exploits network vulnerabilities to replicate across multiple computers without user intervention.

To secure file systems and network communications, the OS implements cryptography.

• Symmetric Encryption: The same key is used to encrypt and decrypt data (e.g., AES). Extremely fast. Used to encrypt entire hard drives.
• Asymmetric Encryption: Uses a Public Key (to encrypt) and a Private Key (to decrypt). (e.g., RSA). Very slow. Used for secure authentication (SSH keys) and secure web traffic (HTTPS).
• Hashing: A one-way mathematical function (e.g., SHA-256). Used by the OS to store user passwords securely. The OS never stores your password, only the hash.

Unit 5 concludes the OS syllabus with file management and security.

⇒14.1 University Exam Checklist

• Compare Contiguous, Linked, and Indexed file allocation methods.
• What is a Directory? Explain the Tree-structured directory system.
• Solve a numerical problem calculating total head movement for a given queue of disk cylinder requests using FCFS, SSTF, SCAN, C-SCAN, and C-LOOK algorithms.
• Why is SSTF generally preferred over FCFS, and what is its major flaw?
• Explain the difference between an Access Control List (ACL) and a Capability List.
• Define Trojan Horse, Virus, and Worm.