2  Memory Management

Virtual Memory

Paging: Translating Logical to Physical Addresses

Context

In paging, the operating system divides:

  • Logical (virtual) memory into fixed-size pages
  • Physical memory (RAM) into same-size frames

Each process has a page table that maps page numbers to frame numbers.

Our goal is:

Given a virtual address, compute the corresponding physical address.

Example Setup

  • Virtual address \(V = 7000\)
  • Page size = 4096 bytes = \(2^{12}\) ⇒ \(k = 12\)
  • Assume the page table maps page 1 to frame 9: \(F(1) = 9\)

Step 1: Manual (Arithmetic) Calculation

To translate a virtual address manually, we need to answer two questions:

  1. Which page is the address in?
  2. Where within that page is the address?

This is done by:

  • Dividing the address by the page size to get the page number
  • Taking the remainder (modulo) to get the offset within the page

Apply this to \(V = 7000\) with page size 4096:

  • Page number \(p = \left\lfloor \frac{7000}{4096} \right\rfloor = 1\)
  • Offset \(d = 7000 \mod 4096 = 2904\)

Now we look up page 1 in the page table:

  • Frame number \(f = F(1) = 9\)

To get the final physical address, we compute the base address of frame 9 and add the offset:

  • Physical address = \(f \cdot 4096 + d = 9 \cdot 4096 + 2904 = 39768\)

Result: 39768

Step 2: Bitwise Calculation (Optimized for Hardware)

For power-of-two page sizes, the address can be efficiently split using bitwise operations:

  • Page number = \(V \gg 12\) (right shift by 12 bits is equivalent to dividing by 4096)
  • Offset = \(V \& (2^{12} - 1) = V \& 0xFFF\) (bit mask keeps the lower 12 bits)
  • Page number 1 maps to frame number \(f = F(1) = 9\)

To compute the frame’s starting address, we use a left shift:

  • \(f \ll 12 = 9 \ll 12 = 36864\), which is equivalent to \(9 \cdot 4096\)

Final physical address:

  • \(\text{Physical Address} = 36864 + 2904 = 39768\)

Same result, now using fast bit operations.

Bit Sequence Visualization

Let’s visualize how the virtual address is split in binary:

  • Virtual address \(V = 7000\)
  • Binary representation (14 bits): 0001 1011 0101 1000

Split into:

  • Page number (upper 2 bits): 00 01 → 1
  • Offset (lower 12 bits): 1011 0101 1000 → 2904

This split works because:

  • The lower 12 bits represent the offset for a 4 KB page
  • The upper bits index into the page table

Why This Works Mathematically

The logic behind using bit shifts and masks instead of division and modulo is based on how numbers are represented in binary.

Decimal Analogy (Base 10)

Consider dividing 1375 by powers of 10:

  • 1375 ÷ 10¹ = 137 (modulo: 5)
  • 1375 ÷ 10² = 13 (modulo: 75)
  • 1375 ÷ 10³ = 1 (modulo: 375)

The rightmost digits are the remainder (modulo); the left are the quotient (division).

Binary Example (Base 2)

Take the binary number 1011₂ (= 11₁₀):

  • 1011 ÷ 2¹ = 101 = 5 (modulo: 1)
  • 1011 ÷ 2² = 10 = 2 (modulo: 11 = 3)
  • 1011 ÷ 2³ = 1 = 1 (modulo: 011 = 3)

In both systems, the rightmost digits/bits represent the offset, and the leftmost represent the page number.

This is why in binary:

  • \(V \gg k\) is equivalent to \(\left\lfloor V / 2^k \right\rfloor\)
  • \(V \& (2^k - 1)\) is equivalent to \(V \mod 2^k\)
  • \(f \ll k\) is equivalent to \(f \cdot 2^k\), which gives the frame base address

These operations are both mathematically correct and hardware-efficient.

Final Formula

\[ \text{Physical Address} = \left( F(V \gg k) \ll k \right) + \left( V \& (2^k - 1) \right) \]

This computes:

  • The page number via right shift
  • The frame number from the page table
  • The frame base via left shift (i.e., multiplying by page size)
  • The final physical address by adding the offset

Additional Example for Practice and Clarity

Let’s now take another address and apply all three methods for reinforcement.

Setup
  • Virtual address \(V = 13,\!452\)
  • Page size = 4096 = \(2^{12}\)
  • Page table:
Page # Frame #
0 3
1 7
2 1
3 6
Manual Calculation
  • Page number: \(13,\!452 \div 4096 = 3\)
  • Offset: \(13,\!452 \mod 4096 = 1164\)
  • Frame number: \(F(3) = 6\)
  • Physical address = \(6 \cdot 4096 + 1164 = 24,\!576 + 1164 = 25,\!740\)
Bitwise Calculation
  • \(V = 13,\!452 = 0b0011\ 0100\ 1001\ 1100\)
  • Page number = \(V \gg 12 = 3\)
  • Offset = \(V \& 0xFFF = 1164\)
  • Frame number = \(F(3) = 6\)
  • Frame base = \(6 \ll 12 = 24,\!576\)
  • Physical address = \(24,\!576 + 1164 = 25,\!740\)

Using the Formula

\[ \text{Physical Address} = (F(V \gg 12) \ll 12) + (V \& 0xFFF) \]

\[ = (6 \ll 12) + 1164 = 24,\!576 + 1164 = 25,\!740 \]

Conclusion

When the page size is a power of two, address translation can be performed using fast bit operations instead of division and modulo. This is possible because of how binary numbers encode positional value. We saw that the lower bits give the offset and the upper bits the page number. Whether done manually, with bit operations, or using the translation formula, all approaches yield the same physical address — and this consistency is what makes paging both robust and efficient.