Paging - aryanjoshi0823/5143-Operating-System GitHub Wiki

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. Instead, it divides both logical and physical memory into fixed-size blocks, which simplifies memory allocation, reduces fragmentation, and supports virtual memory. Below is a comprehensive exploration of paging, including its components, processes, advantages, and more.

1. Basic Concepts of Paging

Logical and Physical Memory

  • Logical Memory: The memory space as seen by the process, which is divided into fixed-size blocks called pages.
  • Physical Memory: The actual hardware memory, which is divided into fixed-size blocks called frames.

Pages and Frames

  • A page is a block of logical memory of fixed size (e.g., 4 KB).
  • A frame is a block of physical memory of the same fixed size.
  • Logical pages are mapped onto physical frames through a translation process.

Page Table

  • A page table is a data structure maintained by the operating system to map each logical page to its corresponding physical frame.
  • Each entry in the page table contains:
    • Frame Number: Indicates the frame in which the page is stored.
    • Control Bits: Metadata such as valid/invalid bits, read/write permissions, etc.

2. Address Translation in Paging

Structure of Logical Address

A logical address is split into two parts:

  1. Page Number (p): Identifies the page in the page table.
  2. Page Offset (d): Specifies the exact byte within the page.

Translation Process

The CPU generates a logical address that is converted into a physical address using the page table:

  1. Extract the page number (p) from the logical address.
  2. Look up the page number in the page table to find the corresponding frame number (f).
  3. Combine the frame number (f) with the offset (d) to generate the physical address.

Physical Address Formula:

{Physical Address} = (Frame Number x Page Size) + Page Offset

Example

  • Logical Address: 5230 bytes
  • Page Size: 1024 bytes
    • Page Number: [5230 / 1024] = 5
    • Page Offset: 5230 mod 1024 = 1102
  • Page Table Entry for Page 5: Frame 12
    • Physical Address: (12 x 1024) + 1102 = 13334

3. Types of Paging Techniques

  • Demand Paging
  • Multi-Level Paging
  • Inverted Paging

4. Real-Life Example of Paging

Consider a process with a logical address space of 16 MB and a page size of 4 KB:

  • Number of Pages: logical address space / page size = 16 mb/ 4kb = 4096
  • Page Table Entries: The page table will have 4096 entries.
  • Physical Address: If the page table maps Page 1 to Frame 100, the logical address for Page 1, Offset 300 translates to Physical Address (100 x 4kb) + 300 = 409,900