Paging

15 min read2,885 words

Paging

Paging is a memory-management technique that allows a process to be stored in non-contiguous locations in physical memory.

Paging divides logical memory into fixed-size blocks called pages and physical memory into fixed-size blocks called frames.

The important idea is:

Process → Pages RAM → Frames

Pages can be placed into any available frames.

1. Why Do We Need Paging?

With contiguous memory allocation, a process needs one large continuous block.

Suppose a process needs 100 MB, but RAM has:

+----------------+ | P1 | +----------------+ | Free 40 MB | +----------------+ | P2 | +----------------+ | Free 30 MB | +----------------+ | P3 | +----------------+ | Free 50 MB | +----------------+

Total free memory:

40 + 30 + 50 = 120 MB

But there is no single 100 MB block.

So the process cannot be allocated contiguously.

Paging solves this problem by dividing the process into smaller pieces.

2. Basic Idea of Paging

Suppose:

Process size = 16 KB Page size = 4 KB

Then:

16 KB / 4 KB = 4 pages

The process becomes:

+--------+ | Page 0 | +--------+ | Page 1 | +--------+ | Page 2 | +--------+ | Page 3 | +--------+

Physical memory is divided into frames:

+---------+ | Frame 0 | +---------+ | Frame 1 | +---------+ | Frame 2 | +---------+ | Frame 3 | +---------+ | Frame 4 | +---------+ | Frame 5 | +---------+ ...

The pages don't have to be placed next to each other.

For example:

Page 0 → Frame 5 Page 1 → Frame 1 Page 2 → Frame 7 Page 3 → Frame 3

3. Page vs Frame

This is one of the most important concepts.

Page

A page is a fixed-size block of logical/virtual memory.

Frame

A frame is a fixed-size block of physical memory (RAM).

Virtual Memory Physical Memory +---------+ +---------+ | Page 0 | ──────────────→ | Frame 5 | +---------+ +---------+ | Page 1 | ──────────────→ | Frame 1 | +---------+ +---------+ | Page 2 | ──────────────→ | Frame 7 | +---------+ +---------+ | Page 3 | ──────────────→ | Frame 3 | +---------+ +---------+

Easy memory trick:

Page = Program's virtual memory

Frame = Physical RAM

4. Page Size and Frame Size

The size of a page is always equal to the size of a frame.

For example:

Page size = 4 KB Frame size = 4 KB

or:

Page size = 8 KB Frame size = 8 KB

Why?

Because one page must fit exactly into one frame.

5. Page Table

How does the OS know where each page is stored?

It uses a page table.

Example:

Page NumberFrame Number
05
11
27
33

The page table maps:

Page → Frame

For example:

Page 0 → Frame 5 Page 1 → Frame 1 Page 2 → Frame 7 Page 3 → Frame 3

6. Complete Paging Structure

CPU | ↓ Logical Address | +------+------+ | | ↓ ↓ Page Number Offset | ↓ Page Table | ↓ Frame Number | +------ Offset | ↓ Physical Address | ↓ RAM

This is the heart of paging.

7. Logical Address

A logical address in paging is divided into two parts:

Logical Address | +----------------+ | | ↓ ↓ Page Number Offset

For example:

Logical address = 13 bits +-----------+--------+ | Page No. | Offset | +-----------+--------+

The page number identifies the page.

The offset identifies the exact location inside that page.

8. What Is an Offset?

Suppose page size is:

4 KB

A page contains:

4096 bytes

Therefore, the offset needs to identify one of:

0 → 4095

Number of bits required:

log₂(4096) = 12 bits

Therefore:

Offset = 12 bits

9. Address Format

Suppose:

Logical address = 16 bits Page size = 4 KB

Since:

4 KB = 4096 bytes = 2¹²

Offset:

12 bits

Therefore page number:

16 - 12 = 4 bits

Address format:

16-bit Logical Address +----------+--------------+ | Page No. | Offset | | 4 bits | 12 bits | +----------+--------------+

Number of pages:

2⁴ = 16 pages

10. Physical Address

The physical address is also divided conceptually into:

Frame Number + Offset

The important point is:

Page Number → Frame Number

The offset remains unchanged.

Example:

Logical address: Page 2 + Offset 100 Page table: Page 2 → Frame 7 Physical address: Frame 7 + Offset 100

11. Address Translation Example

Suppose:

Page size = 100 bytes Logical address = 250

Find:

Page number Offset

Formula:

Page Number = Logical Address / Page Size

Integer division:

250 / 100 = 2

So:

Page Number = 2

Offset:

250 % 100 = 50

Therefore:

Page = 2 Offset = 50

Suppose page table says:

Page 2 → Frame 7

Then physical address:

Frame × Page Size + Offset = 7 × 100 + 50 = 750

Therefore:

Physical address = 750

12. Another Numerical Example

Suppose:

Page size = 1 KB Logical address = 2500

Since:

1 KB = 1024 bytes

Page number:

2500 / 1024 = 2

Offset:

2500 % 1024 = 452

Therefore:

Page number = 2 Offset = 452

Suppose:

Page 2 → Frame 5

Physical address:

5 × 1024 + 452 = 5120 + 452 = 5572

Therefore:

Physical Address = 5572

13. Important Paging Formulas

Page number

Page Number = Logical Address ÷ Page Size

Take the integer part.

Offset

Offset = Logical Address % Page Size

Physical address

Physical Address = Frame Number × Page Size + Offset

These formulas are very important for numerical questions.

14. Number of Pages

Suppose:

Process size = 20 KB Page size = 4 KB

Number of pages:

20 / 4 = 5 pages

Therefore:

P0 P1 P2 P3 P4

15. When Process Size Is Not a Multiple of Page Size

Suppose:

Process size = 18 KB Page size = 4 KB

Then:

18 / 4 = 4.5

So we need:

5 pages

Memory allocated:

5 × 4 = 20 KB

Unused:

20 - 18 = 2 KB

That unused space is internal fragmentation.

Therefore paging can cause some internal fragmentation, especially in the final page.

16. Paging and Fragmentation

Paging eliminates the major problem of external fragmentation associated with contiguous allocation.

Why?

Because pages can be placed in any available frame.

Example:

Free Frames: F1 F4 F8 F10

Pages can use them:

P0 → F8 P1 → F1 P2 → F10 P3 → F4

They don't need to be adjacent.

However:

Paging can still produce internal fragmentation.

Usually the last page of a process may not be completely full.

17. Advantages of Paging

1. Eliminates external fragmentation

A process does not need one continuous memory block.

2. Supports non-contiguous allocation

Pages can be placed anywhere.

3. Supports virtual memory

Paging is fundamental to many virtual-memory systems.

4. Better memory utilization

Free frames can be used independently.

5. Supports process isolation

Different processes can have separate page tables and permissions.

6. Easy allocation

Physical frames can be allocated independently.

18. Disadvantages of Paging

1. Page table overhead

Every process may require a page table.

Large address spaces can require substantial page-table memory.

2. Address translation overhead

The system needs to translate:

Page → Frame

3. Internal fragmentation

The final page may not be completely used.

4. Memory access can become more expensive

Without caching mechanisms, translation may add overhead.

5. Page-table management complexity

Large systems require more sophisticated structures.

19. TLB

To speed up address translation, processors commonly use a:

TLB = Translation Lookaside Buffer

The TLB is a fast cache that stores recent page-to-frame mappings.

Without TLB:

CPU ↓ Page Table ↓ Frame ↓ RAM

With TLB:

CPU ↓ TLB ↓ Found? ├── Yes → Frame └── No → Page Table ↓ Frame

20. TLB Hit

Suppose CPU needs:

Page 5

And TLB already contains:

Page 5 → Frame 10

Then:

TLB → Frame 10

This is a:

TLB hit

It avoids having to look up the page table for that translation.

21. TLB Miss

Suppose CPU needs:

Page 8

But TLB doesn't contain it.

Then:

CPU ↓ TLB ↓ Miss ↓ Page Table ↓ Frame Number

This is a:

TLB miss

The translation can then be placed into the TLB for future use, depending on the hardware/OS design.

22. Page Table Entry

A page table doesn't necessarily contain only a frame number.

A page table entry (PTE) may contain information such as:

+-------------------+ | Frame Number | | Present/Valid | | Read/Write | | User/Supervisor | | Accessed | | Dirty | | Other flags | +-------------------+

Important bits include:

Present/Valid bit

Indicates whether the page is currently mapped/present as required.

Protection bits

Determine whether the page can be:

Read Write Execute

Dirty bit

Indicates whether a page has been modified.

Accessed/Reference bit

Indicates that the page has been accessed.

23. Multi-Level Page Tables

A huge page table can consume a lot of memory.

Instead of having one enormous page table, modern systems can use multi-level page tables.

Conceptually:

Virtual Address | ↓ +-------------+ | Level 1 | +-------------+ | ↓ +-------------+ | Level 2 | +-------------+ | ↓ +-------------+ | Level 3 | +-------------+ | ↓ Frame

Only the portions needed for the address space have to be allocated.

24. Page Table and Process

Each process can have its own virtual address space and page-table mappings.

Example:

Process A Virtual Page 0 → Frame 5 Virtual Page 1 → Frame 8 Process B Virtual Page 0 → Frame 2 Virtual Page 1 → Frame 9

Both processes can have a virtual address such as:

Page 0

but it can map to different physical frames.

This provides process isolation.

25. Shared Pages

Paging can also support shared memory.

For example:

Process A Page 5 ─────┐ ↓ Frame 20 ↑ Process B │ Page 8 ──────┘

Both processes can map a page to the same physical frame.

This can be useful for:

  • Shared libraries
  • Inter-process communication
  • Shared memory
  • Copy-on-write mechanisms

26. Copy-on-Write

Copy-on-write, commonly abbreviated COW, is an important optimization.

Suppose:

Process A | ↓ Shared physical page ↑ | Process B

Initially both can share the same physical page.

If one process tries to modify it:

Process A writes ↓ Page copied ↓ A gets its own copy ↓ B keeps original

This avoids unnecessary copying when the data is only being read.

27. Paging and Virtual Memory

Paging is strongly connected with virtual memory.

Suppose:

Virtual Memory = 16 GB Physical RAM = 4 GB

The entire virtual address space doesn't have to be physically present in RAM at once.

Only currently needed pages may be in RAM.

Virtual Memory +----+----+----+----+----+----+ | P0 | P1 | P2 | P3 | P4 | P5 | +----+----+----+----+----+----+ ↓ selected pages RAM +----+----+----+----+ | P0 | P3 | P5 | ...| +----+----+----+----+

When a required page isn't available, a page fault can occur.

28. Page Fault

A page fault happens when the CPU references a virtual page that is not currently available in the required physical-memory state.

Simplified flow:

CPU requests page ↓ Page table checked ↓ Page present? / \ Yes No | | ↓ ↓ Continue Page Fault ↓ OS handles fault ↓ Find/load required page ↓ Update page table ↓ Retry

Page faults are normal in virtual-memory systems.

However, excessive page faults can cause poor performance.

29. Paging vs Segmentation

PagingSegmentation
Fixed-size pagesVariable-size segments
Physical memory divided into framesMemory divided into logical segments
Page size = frame sizeSegment size can vary
Programmer usually doesn't see pages directlySegments correspond more naturally to logical program units
No external fragmentation in basic pagingCan suffer external fragmentation
Can have internal fragmentationCan have external fragmentation
Uses page tableUses segment table

30. Paging vs Contiguous Allocation

FeatureContiguous AllocationPaging
Process locationContinuousNon-continuous
External fragmentationPossibleEliminated in basic paging
Internal fragmentationPossiblePossible
AllocationMore difficult with scattered holesFrames can be independently allocated
Address translationSimplerPage-table based
Virtual memoryLimited/older approachFundamental technique

31. Complete Paging Example

Suppose:

Logical memory = 16 KB Physical memory = 32 KB Page size = 4 KB

Number of pages

16 / 4 = 4 pages
P0 P1 P2 P3

Number of frames

32 / 4 = 8 frames
F0 F1 F2 F3 F4 F5 F6 F7

Suppose page table:

PageFrame
P0F5
P1F2
P2F7
P3F1

Memory might look like:

Physical RAM F0 → Free F1 → P3 F2 → P1 F3 → Free F4 → Free F5 → P0 F6 → Free F7 → P2

Notice:

P0 → F5 P1 → F2 P2 → F7 P3 → F1

The process is completely non-contiguous.

32. Important Numerical Formula

If:

Logical address = LA Page size = S

Then:

Page number = floor(LA / S) Offset = LA mod S

If:

Page number → Frame number F

then:

Physical address = F × S + Offset

33. Bit Calculation

Suppose:

Logical address = 32 bits Page size = 4 KB

Since:

4 KB = 4096 bytes = 2¹² bytes

Therefore:

Offset = 12 bits

Remaining:

32 - 12 = 20 bits

So:

+--------------------+------------+ | Page Number | Offset | | 20 bits | 12 bits | +--------------------+------------+

Number of virtual pages:

2²⁰ pages

34. Another Bit Example

Suppose:

Logical address = 16 bits Page size = 1 KB

1 KB:

1024 = 2¹⁰

Therefore:

Offset = 10 bits

Page number:

16 - 10 = 6 bits

Number of pages:

2⁶ = 64 pages

So:

+----------+------------+ | Page No. | Offset | | 6 bits | 10 bits | +----------+------------+

35. Why Page Size Matters

Page size affects the system in several ways.

Small pages

Advantages:

  • Less internal fragmentation
  • Finer-grained memory management

Disadvantages:

  • More pages
  • Larger page tables
  • Potentially more translation overhead

Large pages

Advantages:

  • Smaller page tables
  • Can improve translation efficiency in some situations

Disadvantages:

  • More internal fragmentation
  • Less fine-grained memory management

Modern systems can support multiple page sizes for different workloads.

36. Advantages and Disadvantages Summary

Advantages

✓ No external fragmentation ✓ Non-contiguous allocation ✓ Supports virtual memory ✓ Easy frame allocation ✓ Process isolation ✓ Memory sharing ✓ Efficient physical-memory utilization

Disadvantages

✗ Page-table overhead ✗ Internal fragmentation ✗ Address translation overhead ✗ Page faults can be expensive ✗ More complex memory management

🧠 Exam Revision

Definition

Paging is a non-contiguous memory-management technique in which logical memory is divided into fixed-size pages and physical memory is divided into equal-size frames. A page table maps pages to frames.

Remember:

Logical Memory → Pages Physical Memory → Frames Page → Page Table → Frame

Most important concepts:

Paging │ ├── Page ├── Frame ├── Page Table ├── Logical Address │ ├── Page Number │ └── Offset ├── Physical Address │ ├── Frame Number │ └── Offset ├── Address Translation ├── TLB ├── Page Table Entry ├── Multi-Level Page Table ├── Page Fault ├── Virtual Memory ├── Internal Fragmentation └── Copy-on-Write

One-line memory trick:

“Page tells WHERE in virtual memory; frame tells WHERE in RAM; offset tells EXACTLY WHERE inside it.”

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy