Paging and Page Table

Paging is a memory management technique that divides a virtual memory into fixed-size blocks called pages and the physical memory into fixed-size blocks called frames.

• Each page in virtual memory maps to a frame in physical memory, but the pages do not need to be contiguous. This flexibility helps optimize memory utilization and avoid memory fragmentation.

→ When a process is loaded into memory, its pages are stored in available frames, regardless of their physical location. To access a specific piece of data, the operating system translates the virtual address (containing the page number and offset) into a physical address using the page table.

Page Table

The page table is a critical data structure in the operating system that maps each virtual page to a physical frame.

• It stores the frame number for each page, making it possible to quickly locate any data in physical memory.

• Each running process has its own page table, ensuring that virtual addresses for one process don’t interfere with those of another.

Structure of Page Table

• Frame Number: It gives the frame number in which the current page is.
• Present/Absent Bit: Indicates whether the page is currently loaded in physical memory.
  • 1: The page is in memory.
  • 0: The page is not in memory (causes a page fault).
• Protection Bits: Specify the type of access allowed for the page. Common permissions include:
  • Read (R)
  • Write (W)
  • Execute (X)
• Reference Bit (Access Bit): Indicates whether the page has been accessed recently.
  • Used for page replacement algorithms (e.g., Least Recently Used).
  • 1: Page was accessed.
  • 0: Page was not accessed.
• Caching Bit: Determines whether the page is cacheable or not.
  • 1: Page can be cached.
  • 0: Page bypasses the cache (useful for memory-mapped I/O).
• Dirty Bit: Indicates whether the page has been modified.
  • 1: Page was written to.
  • 0: Page remains unmodified.

Types of Page Tables

• Hierarchical Page Table
• Inverted Page Table
• Shared Page Table

1.) Hierarchical Page Table

A hierarchical page table breaks down the page table into multiple levels to manage large virtual address spaces more efficiently.

• Instead of a single large table, the virtual address is divided into multiple parts, each corresponding to a level in the hierarchy.

2.) Inverted Page Table

It is the global page table which is maintained by the OS for all processes where the number of entries is equal to the number of frames in the main memory.

3.) Shared Page Table

A shared page table allows multiple processes to share the same memory region (e.g., shared libraries or code segments) having a single page table entry point to the same physical frame for all sharing processes.

Handling Page Faults

A page fault occurs when a program tries to access a page that is not currently in physical memory. When this happens, the operating system must load the page from secondary storage (usually the disk) into memory.

Steps for handling a page fault:

1. Check Validity: The operating system checks if the requested page is part of the process’s address space.
2. Locate Page on Disk: The OS finds the page in the secondary storage.
3. Free Up Space in RAM (if needed): If memory is full, the OS uses a page replacement algorithm (like LRU or FIFO) to select a page to remove.
4. Load the Page into RAM: The requested page is loaded into an available frame.
5. Update the Page Table: The page table entry is updated with the new frame number.
6. Restart the Process: The process continues executing from where it left off.

Translation Lookaside Buffer (TLB)

The Translation Lookaside Buffer (TLB) is a specialized cache used to speed up virtual-to-physical address translation. Since accessing the page table in memory can be slow, the TLB stores a small number of recent page-to-frame mappings, allowing faster access to frequently used pages.

When a virtual address is translated:

• The OS first checks the TLB for the page number. If it is found (TLB hit), the frame number is quickly retrieved.

• If the page number is not in the TLB (TLB miss), the OS retrieves the frame number from the page table in memory and updates the TLB with this new mapping.