Paging concept and page tables in Operating Systems - Step-by-Step Execution

Concept Flow - Paging concept and page tables

Process wants memory

↓

Divide memory into pages

↓

Divide physical memory into frames

↓

Page table maps pages to frames

↓

CPU uses page table to find frame

↓

Access physical memory frame

↓

Return data to process

The process memory is split into pages, physical memory into frames, and a page table maps pages to frames so the CPU can find data.

Execution Sample

Operating Systems

Virtual Address: 0x1234
Page Size: 1KB (1024 bytes)
Page Number = Virtual Address / Page Size
Offset = Virtual Address % Page Size
Use Page Number to find Frame in Page Table
Physical Address = Frame * Page Size + Offset

This shows how a virtual address is translated to a physical address using page number, offset, and the page table.

Analysis Table

Step	Virtual Address	Page Number	Offset	Frame Number (from Page Table)	Physical Address Calculation	Physical Address
1	0x1234 (4660 decimal)	4 (4660/1024=4)	4660 % 1024 = 564	7	7 * 1024 + 564	7168 + 564 = 7732 (0x1E34)
2	0x0A00 (2560 decimal)	2 (2560/1024=2)	2560 % 1024 = 512	3	3 * 1024 + 512	3072 + 512 = 3584 (0x0E00)
3	0x1FFF (8191 decimal)	7 (8191/1024=7)	8191 % 1024 = 1023	1	1 * 1024 + 1023	1024 + 1023 = 2047 (0x07FF)
4	0x2000 (8192 decimal)	8 (8192/1024=8)	8192 % 1024 = 0	5	5 * 1024 + 0	5120 + 0 = 5120 (0x1400)
5	0x3000 (12288 decimal)	12 (12288/1024=12)	12288 % 1024 = 0	Page not mapped	No frame found	Page fault - no physical address
6	N/A	N/A	N/A	N/A	N/A	Stop - address not mapped

💡 Execution stops when a virtual page is not mapped in the page table, causing a page fault.

State Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
Virtual Address	N/A	0x1234	0x0A00	0x1FFF	0x2000	0x3000	N/A
Page Number	N/A	4	2	7	8	12	N/A
Offset	N/A	564	512	1023	0	0	N/A
Frame Number	N/A	7	3	1	5	N/A	N/A
Physical Address	N/A	7732	3584	2047	5120	Page fault	N/A

Key Insights - 3 Insights

Why does the physical address sometimes not exist?

When the page number is not found in the page table (see step 5 in execution_table), it means the page is not loaded in physical memory, causing a page fault.

How is the offset calculated and why is it important?

Offset is the remainder after dividing the virtual address by page size (see execution_table column 'Offset'). It tells the exact byte inside the frame to access.

Why do we divide the virtual address by page size to get the page number?

Because memory is split into fixed-size pages, dividing gives which page the address belongs to (see execution_table column 'Page Number').

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the physical address calculated?

A 7636 (0x1DBC)

B 2047 (0x07FF)

C 3584 (0x0E00)

D 5120 (0x1400)

💡 Hint

Check the 'Physical Address' column in execution_table row for step 3.

At which step does the page fault occur because the page is not mapped?

A Step 2

B Step 4

C Step 5

D Step 1

💡 Hint

Look for 'Page not mapped' or 'Page fault' in the execution_table rows.

If the page size was doubled, how would the page number for virtual address 0x1234 change?

A It would be half as large

B It would stay the same

C It would double

D It would become zero

💡 Hint

Page number = Virtual Address / Page Size; increasing page size decreases page number.

Concept Snapshot

Paging splits virtual memory into fixed-size pages.
Physical memory is split into frames of the same size.
Page table maps each virtual page to a physical frame.
Virtual address = page number + offset.
CPU uses page table to find frame for a page.
If page not mapped, page fault occurs.

Full Transcript

Paging is a memory management method where virtual memory is divided into pages and physical memory into frames. Each virtual page is mapped to a physical frame using a page table. To find the physical address from a virtual address, the CPU divides the virtual address by the page size to get the page number and offset. It then looks up the frame number for that page in the page table. The physical address is calculated by multiplying the frame number by the page size and adding the offset. If the page is not mapped in the page table, a page fault occurs, stopping the process until the page is loaded. This method helps efficiently use memory and isolate processes.

Practice

1. What is the main purpose of paging in an operating system?

easy

A. To encrypt data in memory

B. To increase the CPU clock speed

C. To manage input/output devices

D. To divide memory into fixed-size blocks called pages

Solution

1. Step 1: Understand the concept of paging

   Paging divides the computer's memory into fixed-size blocks called pages to simplify memory management.

2. Step 2: Identify the main purpose

   The main goal is to break memory into pages, not to affect CPU speed, encryption, or device management.

3. Final Answer:

   To divide memory into fixed-size blocks called pages -> Option D

4. Quick Check:

   Paging = dividing memory into pages [OK]

Hint: Paging means splitting memory into equal blocks [OK]

Common Mistakes:

• Confusing paging with CPU speed improvement
• Thinking paging encrypts memory data
• Mixing paging with device management

2. Which of the following correctly describes a page table?

easy

A. A table that stores the mapping from virtual pages to physical frames

B. A list of all running processes in the system

C. A table that stores CPU instructions

D. A list of input/output devices connected to the system

Solution

1. Step 1: Define the role of a page table

   A page table maps virtual memory pages to physical memory frames, helping the OS locate data.

2. Step 2: Eliminate incorrect options

   Page tables do not list processes, CPU instructions, or devices.

3. Final Answer:

   A table that stores the mapping from virtual pages to physical frames -> Option A

4. Quick Check:

   Page table = virtual to physical mapping [OK]

Hint: Page tables map virtual pages to physical memory [OK]

Common Mistakes:

• Confusing page tables with process lists
• Thinking page tables store CPU instructions
• Mixing page tables with device lists

3. Consider a system with a page size of 4 KB and a virtual address 0x1A3F. Which part of the address identifies the page number?

medium

A. The lower 12 bits

B. The middle 8 bits

C. The higher bits except the lower 12 bits

D. The entire 16 bits

Solution

1. Step 1: Calculate bits for page offset

   Page size is 4 KB = 2^12 bytes, so lower 12 bits represent the offset within a page.

2. Step 2: Identify page number bits

   The page number is given by the higher bits of the address excluding the lower 12 bits (offset).

3. Final Answer:

   The higher bits except the lower 12 bits -> Option C

4. Quick Check:

   Page number = address bits above offset bits [OK]

Hint: Page offset = log2(page size) bits; rest is page number [OK]

Common Mistakes:

• Confusing offset bits with page number bits
• Using entire address as page number
• Selecting wrong bit segments

4. A page table entry is missing for a virtual page, causing a page fault. What is the most likely cause?

medium

A. The CPU clock speed is too low

B. The page is not currently loaded in physical memory

C. The virtual address is invalid

D. The page size is too large

Solution

1. Step 1: Understand what causes a page fault

   A page fault occurs when the page table does not have an entry for the requested virtual page, meaning it is not in physical memory.

2. Step 2: Eliminate unrelated causes

   CPU speed, invalid address, or page size do not directly cause missing page table entries.

3. Final Answer:

   The page is not currently loaded in physical memory -> Option B

4. Quick Check:

   Page fault = missing page in physical memory [OK]

Hint: Page fault means page not in physical memory [OK]

Common Mistakes:

• Blaming CPU speed for page faults
• Assuming invalid address always causes page fault
• Confusing page size with page fault cause

5. In a system with 32-bit virtual addresses and 4 KB page size, how many entries does a single-level page table have?

hard

A. 1,048,576 entries

B. 4,096 entries

C. 65,536 entries

D. 16,384 entries

Solution

1. Step 1: Calculate number of pages

   Page size = 4 KB = 2^12 bytes, virtual address size = 32 bits.

2. Step 2: Calculate entries in page table

   Number of pages = 2^(32 - 12) = 2^20 = 1,048,576 entries.

3. Final Answer:

   1,048,576 entries -> Option A

4. Quick Check:

   Entries = 2^(address bits - offset bits) [OK]

Hint: Entries = 2^(virtual bits - page offset bits) [OK]

Common Mistakes:

• Using page size directly as number of entries
• Confusing total address bits with offset bits
• Calculating entries incorrectly as 2^16 or 2^14