Paging and Segmentation in Operating Systems

1. Paging (Non-Contiguous Memory Management)

To completely eliminate External Fragmentation without the heavy cost of Compaction, Operating Systems use Paging!

Definition of Paging: Paging is a non-contiguous memory management scheme that permits a process’s physical address space in RAM to be non-contiguous. Whenever a process needs RAM, its pages can be placed into any available free memory frames scattered anywhere across RAM!

3 Core Building Blocks of Paging:

1. Frames (In Physical RAM): Physical Memory (RAM) is divided into fixed-size blocks called Frames.
2. Pages (In Logical Process Memory): Logical Memory (the Process) is divided into blocks of the exact same fixed size called Pages (typically 4 KB each).

   Formula: Page Size = Frame Size (Always equal, e.g., 4 KB)

3. Page Table (The Map): Since a process’s Pages (Page 0, Page 1, Page 2...) are placed in scattered Frames in RAM (e.g., Frame 5, Frame 2, Frame 9), the OS maintains a Page Table for each process that stores the Frame Number where each Page is stored in RAM!

2. How Address Translation Works in Paging

Every Logical Address generated by the CPU is divided into two parts:

1. Page Number (p): Used as an index into the Page Table to look up the corresponding Frame Number (f) in RAM.
2. Page Offset / Displacement (d): Specifies the exact byte position within that page/frame. It remains unchanged and is combined directly with the Frame Number (f) to form the final Physical Address!

Role of TLB (Translation Lookaside Buffer) in Paging:

• Problem: Since the Page Table itself is stored in Main Memory (RAM), reading a single variable requires 2 memory accesses: (1) Access RAM to read the Page Table, and (2) Access RAM to read the actual data byte! This cuts memory speed in half.
• Solution — TLB: A TLB (Translation Lookaside Buffer) is a small, ultra-fast hardware associative cache inside the MMU that caches recently used (Page Number → Frame Number) translations. If a page is found in the TLB (TLB Hit), translation happens instantly without touching RAM!

Advantages & Disadvantages of Paging:

• Advantages:
  • 100% Zero External Fragmentation! Any free frame can be given to any process.
  • Simple memory allocation and easy sharing of common code pages.
• Disadvantages:
  • May suffer from a small amount of Internal Fragmentation in the very last page of a process (on average, half a page = 2 KB).
  • Extra memory overhead required to store Page Tables.

3. Segmentation in Operating Systems

Why Was Segmentation Invented?

Paging divides a program blindly into fixed 4 KB chunks (like cutting a book every 50 lines, even if it cuts a function or array right in the middle!). However, a human programmer does not think of a program as a flat array of bytes—a programmer views a program as a collection of logical modules (Segments) of different sizes:

• main() function
• Subroutines / Methods
• Symbol Table
• Stack
• Global Variables / Arrays

Definition of Segmentation: Segmentation is a non-contiguous memory management scheme that supports the user’s / programmer’s logical view of memory by dividing a program into variable-sized logical units called Segments, where each segment has a name (or Segment Number) and a length!

4. How Address Translation Works in Segmentation

In Segmentation, a Logical Address consists of a two-tuple:

Formula: < Segment Number (s),\ Offset (d) >

To translate this into a 1D Physical Address in RAM, the OS uses a Segment Table. Because segments have different sizes, each entry in the Segment Table stores two values:

1. Segment Base: The starting physical address in RAM where that segment begins.
2. Segment Limit: The length (size) of that segment!

Step-by-Step Translation in Segmentation:

1. The Segment Number (s) indexes into the Segment Table to fetch its Limit and Base.
2. Bounds Check: The hardware checks whether the Offset d is valid: 0 ≤ d < Limit.
   • If d ≥ Limit: The process is trying to access memory outside its segment! Hardware triggers a Trap (Segmentation Fault) to the OS.
   • If d < Limit: Valid! It adds the Segment Base to the Offset (d) to get the Physical Address:

     Formula: Physical Address = Segment Base[s] + Offset (d)

5. Comparison: Paging vs Segmentation

This is a 100% guaranteed 8-mark comparison question in DAVV BCA Operating System exams!

💡 Exam Preparation Tips for DAVV BCA

• Always draw both hardware translation diagrams (Figure 4.7 for Paging and Figure 4.8 for Segmentation) and write the 6-point Comparison Table above!
• Remember the golden difference in Fragmentation:
  • Paging has Internal Fragmentation, but NO External Fragmentation.
  • Segmentation has External Fragmentation, but NO Internal Fragmentation.