Memory Management and File System Architecture

1. Demand Paging

In a standard virtual memory system, the operating system does not load an entire program into physical memory (RAM) at once. Instead, it uses Demand Paging—a strategy where pages are loaded into memory only when they are needed (on demand).

How It Works: The Page Fault Mechanism

1. CPU Reference: The CPU tries to access a specific virtual address.
2. Page Table Check: The Hardware (MMU) checks the page table entry for that page. Each entry has a Valid/Invalid (V/I) Bit:
   • Valid (1): The page is already in RAM. The address is translated, and execution continues.
   • Invalid (0): The page is currently on the disk (hard drive/SSD). This triggers a Page Fault interrupt.
3. OS Trap: The operating system takes control to handle the page fault.
4. Disk I/O: The OS finds a free frame in physical RAM and reads the required page from the disk into that frame.
5. Update Page Table: The OS updates the page table entry to point to the new frame and changes the bit from Invalid to Valid.
6. Restart Instruction: The CPU restarts the instruction that caused the fault, and it now executes smoothly.

2. Page Replacement Algorithms

When RAM is completely full and a page fault occurs, the OS must choose an existing page in memory to kick out (swap to disk) to make room for the incoming page. This is handled by Page Replacement Algorithms.

To understand them, let's use a standard reference string (the order of pages requested by the CPU) with 3 available memory frames.

Reference String: 7, 0, 1, 2, 0, 3, 0, 4

A. First-In, First-Out (FIFO)

The simplest algorithm. The page that has been in memory the longest is replaced first (like a queue).

• How it handles the string:
  • 7, 0, 1: Loaded into empty frames → [7], [7, 0], [7, 0, 1] (3 Faults)
  • 2: Replaces 7 (oldest) → [2, 0, 1] (1 Fault)
  • 0: Already in memory → [2, 0, 1] (Hit)
  • 3: Replaces 0 (next oldest) → [2, 3, 1] (1 Fault)
  • 0: Replaces 1 → [2, 3, 0] (1 Fault)
  • 4: Replaces 2 → [4, 3, 0] (1 Fault)
• Total Page Faults: 7
• Downside: It suffers from Belady’s Anomaly—where allocating more physical memory frames can actually result in more page faults.

B. Optimal Page Replacement (OPT / MIN)

Replaces the page that will not be used for the longest period of time in the future. This is an ideal algorithm used purely as a benchmark because the OS cannot accurately predict the future.

• How it handles the string:
  • 7, 0, 1: Loaded → [7, 0, 1] (3 Faults)
  • 2: Replaces 7 (because 7 is never used again, while 0 and 1 are used sooner) → [2, 0, 1] (1 Fault)
  • 0: Hit → [2, 0, 1]
  • 3: Replaces 1 (because 0 is needed next) → [2, 0, 3] (1 Fault)
  • 0: Hit → [2, 0, 3]
  • 4: Replaces 2 or 3 → [4, 0, 3] (1 Fault)
• Total Page Faults: 6 (The absolute minimum possible)

C. Least Recently Used (LRU)

Replaces the page that has not been used for the longest period of time looking backward. It operates on the principle of temporal locality (if you haven't used it recently, you probably won't use it soon).

• How it handles the string:
  • 7, 0, 1: Loaded → [7, 0, 1] (3 Faults)
  • 2: Replaces 7 (least recently used) → [2, 0, 1] (1 Fault)
  • 0: Hit. 0 becomes the most recently used → [2, 0, 1]
  • 3: Replaces 1 (since 2 and 0 were accessed more recently) → [2, 0, 3] (1 Fault)
  • 0: Hit → [2, 0, 3]
  • 4: Replaces 2 → [4, 0, 3] (1 Fault)
• Total Page Faults: 6

3. Thrashing

Thrashing occurs when a system spends more time swapping pages in and out of disk than it does executing actual instructions.

Why Does It Happen?

If the OS increases the degree of multiprogramming (loading more and more processes into RAM simultaneously), the number of frames allocated to each individual process shrinks. When a process does not have enough frames to hold its core working set of pages:

1. It quickly triggers a page fault.
2. It looks for a page to replace, but all its pages are actively in use.
3. It replaces a page that it will need almost immediately.
4. This creates a continuous loop of faulting, swapping out, and swapping back in.

The Consequences

• CPU utilization drops to near zero because all processes are stuck waiting in the queue for the disk I/O to finish.
• The OS mistakenly thinks the CPU is idle because the workload is low, so it tries to launch even more processes, making the problem drastically worse.

How to Prevent Thrashing

• Working-Set Model: The OS tracks how many pages a process actively uses during a specific time window (Δ). If the total demand from all processes exceeds available RAM, the OS suspends one of the processes entirely to free up frames for the others.
• Page-Fault Frequency (PFF): The OS sets an acceptable threshold for page faults. If a process's fault rate is too high, it gets allocated more frames. If its fault rate is incredibly low, the OS takes away some of its frames.

Do you have an upcoming exam on this topic, or are you currently working on implementing one of these page replacement algorithms in code? Let me know where you'd like to dive deeper.

4. File System Structure

A file system is organized in layers to isolate tasks and improve modularity. Each layer uses the features of the layer below it to provide services to the layer above it.

• Application Programs: The user-level software (e.g., a text editor or browser) that initiates file requests.
• Logical File System: Manages metadata and the directory structure. It translates a file path into a file identifier (like an inode number) and handles security, permissions, and file structures.
• File-Organization Module: Translates logical block addresses (e.g., "block 12 of file X") into physical block addresses (e.g., "cylinder 4, track 2, sector 5"). It also manages free space allocation.
• Basic File System: Issues generic commands to the device driver to read and write physical blocks on the disk. It manages memory buffers and caches.
• I/O Control (Device Drivers): Consists of device drivers and interrupt handlers that communicate directly with the hardware controllers. It transfers blocks of data between memory and the disk.
• Devices: The physical storage medium (e.g., SSD, HDD, Magnetic Tape).

5. File System Implementation

To operate, a file system maintains specific data structures both on the physical disk and in main memory (RAM).

On-Disk Structures

• Boot Control Block: Usually the first block of a volume. It contains the information needed to boot the operating system from that volume (e.g., the bootloader).
• Volume Control Block (Superblock): Contains volume details like the total number of blocks, block size, free block count, and pointers to free blocks.
• Directory Structure: Organizes files by mapping names to their respective file identifiers (like inode numbers).
• Per-File Control Block (FCB / Inode): Contains detailed metadata about a specific file, including ownership, permissions, file size, and pointers to the data blocks on disk.

In-Memory Structures

• In-Memory Mount Table: Contains information about each mounted volume.
• In-Memory Directory Cache: Holds directory information for recently accessed paths to speed up navigation.
• System-Wide Open-File Table: Contains a copy of the FCB/inode for every file currently open by any process in the system, along with global information like the file's open count.
• Per-Process Open-File Table: Tracks the files opened by a specific process. It includes pointers to the System-Wide Open-File Table and a local file offset pointer tracking the process's current reading/writing position.

6. File Operations

Operating systems provide system calls to perform essential file manipulations:

• Create: Allocates space on the disk for a new file and adds an entry into the directory structure.
• Open: Before a file is used, a process must open it. The OS copies the file's FCB from disk into the System-Wide Open-File Table and creates an index in the Per-Process Open-File Table (returning a File Descriptor or File Handle to the user).
• Read / Write: Executes data transfers using the current file offset pointer. The pointer is automatically updated after the operation completes.
• Close: Decrements the open counter in the System-Wide Open-File Table. If the counter reaches zero, the file's modified metadata is written back to the disk, and its entry is removed from the in-memory table.
• Delete: Searches the directory for the target file. It removes the directory entry, updates the free space management structures to release the blocks, and deletes the file's FCB.

7. Types of Files

Files are classified based on their content, structure, and behavior:

8. Directory Implementation

Directories must map a text filename to its metadata or FCB pointer. There are two primary schemes:

Linear List

Filenames and block pointers are stored sequentially in a simple array or linked list.

• Pros: Very simple to program and implement.
• Cons: Searching for a file requires a linear search (O(n)), which is highly inefficient for directories containing thousands of files.

Hash Table

A linear list paired with a hash function. The hash function processes the filename to instantly return a pointer to its position in the list.

• Pros: Rapid file lookup and insertion (O(1) average time complexity).
• Cons: Requires handling collisions (when two filenames hash to the same index) and can become complex if the table needs to grow dynamically.

9. Allocation Methods

The allocation method dictates how file blocks are stored on physical disk sectors. The goal is to maximize performance and storage efficiency.

Contiguous Allocation

Each file occupies a consecutive set of blocks on the disk (e.g., blocks 10, 11, 12, 13).

• Pros: Exceptional read/write performance. The disk head rarely has to move far, making it ideal for sequential and direct access.
• Cons: Causes severe external fragmentation as files are created and deleted. It is also difficult to grow an existing file if the blocks directly adjacent to it are already occupied.