Multi-level paging in Operating Systems - Step-by-Step Execution

Concept Flow - Multi-level paging

Start: Virtual Address

↓

Divide into multiple parts

↓

Use first part to index first-level page table

↓

Get address of second-level page table

↓

Use second part to index second-level page table

↓

Find frame number

↓

Combine frame number with offset

↓

Physical Address

Multi-level paging breaks a virtual address into parts to index multiple page tables step-by-step, reducing memory needed for page tables.

Execution Sample

Operating Systems

Virtual Address = [10 bits][10 bits][12 bits]
Level 1 index = first 10 bits
Level 2 index = next 10 bits
Offset = last 12 bits

This shows how a 32-bit virtual address is split for two-level paging: two indexes and an offset.

Analysis Table

Step	Action	Input	Result	Explanation
1	Receive virtual address	0x12345678	0x12345678	Start with full virtual address
2	Extract Level 1 index	Bits 31-22	0x48	First 10 bits used to index first-level page table
3	Access first-level page table	Index 0x48	Pointer to second-level table at 0x2000	Find second-level page table address
4	Extract Level 2 index	Bits 21-12	0x345	Next 10 bits used to index second-level page table
5	Access second-level page table	Index 0x345	Frame number 0x1A3	Find physical frame number
6	Extract offset	Bits 11-0	0x678	Last 12 bits used as offset in frame
7	Combine frame number and offset	Frame 0x1A3 + offset 0x678	Physical address 0x1A3678	Final physical address computed
8	End	-	-	Address translation complete

💡 Translation ends after combining frame number with offset to get physical address.

State Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
Virtual Address	0x12345678	0x12345678	0x12345678	0x12345678	0x12345678
Level 1 index	N/A	0x48	0x48	0x48	0x48
Level 2 index	N/A	N/A	0x345	0x345	0x345
Offset	N/A	N/A	N/A	0x678	0x678
Physical Address	N/A	N/A	N/A	N/A	0x1A3678

Key Insights - 3 Insights

Why do we split the virtual address into multiple parts instead of using one big page table?

Splitting reduces memory usage by avoiding one huge page table; each smaller table is easier to manage and often sparse, as shown in steps 2 and 4 where indexes access smaller tables.

How do we know which bits to use for each level's index?

The virtual address is divided based on the number of bits needed to index each page table level; for example, 10 bits for each level in steps 2 and 4, matching the size of the page tables.

What happens if a page table entry is missing at any level?

If an entry is missing, the translation fails and causes a page fault; this is not shown in the table but would stop the process before step 7.

Visual Quiz - 3 Questions

Look at the execution table, what is the Level 1 index extracted at step 2?

A 0x678

B 0x345

C 0x48

D 0x1A3

💡 Hint

Check the 'Result' column in row for step 2 in the execution_table.

At which step is the physical frame number found?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Look for 'Frame number' in the 'Result' column in execution_table.

If the offset bits were 14 instead of 12, how would the execution_table change?

A Step 6 would extract 14 bits instead of 12

B Level 1 index would be larger

C Physical address would be smaller

D Level 2 index would be 12 bits

💡 Hint

Check how offset bits are extracted at step 6 in execution_table.

Concept Snapshot

Multi-level paging splits a virtual address into parts.
Each part indexes a page table level.
This reduces memory for page tables.
Final physical address = frame number + offset.
Commonly used in modern OS memory management.

Full Transcript

Multi-level paging is a method to translate virtual addresses to physical addresses by breaking the virtual address into multiple parts. Each part is used to index a level of page tables. For example, a 32-bit virtual address can be split into two 10-bit indexes and a 12-bit offset. The first 10 bits select an entry in the first-level page table, which points to a second-level page table. The next 10 bits select an entry in the second-level page table, which gives the frame number. The last 12 bits are the offset within the frame. Combining the frame number and offset gives the physical address. This method saves memory by avoiding one large page table and instead using smaller tables. The execution table shows each step of this translation process with an example address 0x12345678. Key moments include understanding why splitting is done, how bits are divided, and what happens if entries are missing. The visual quiz tests understanding of indexes and steps in the process.