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.

Practice

1. What is the main purpose of multi-level paging in operating systems?

easy

A. To break memory addresses into parts and reduce the size of page tables

B. To increase the size of the physical memory

C. To combine multiple processes into one

D. To speed up the CPU clock

Solution

1. Step 1: Understand the problem of large page tables

   Large memory requires large page tables, which consume a lot of memory.

2. Step 2: Role of multi-level paging

   Multi-level paging breaks addresses into parts and uses multiple smaller page tables to save memory.

3. Final Answer:

   To break memory addresses into parts and reduce the size of page tables -> Option A

4. Quick Check:

   Multi-level paging reduces page table size = C [OK]

Hint: Multi-level paging splits addresses to save memory [OK]

Common Mistakes:

• Thinking it increases physical memory
• Confusing with process combining
• Assuming it speeds CPU clock

2. Which of the following correctly describes the structure of multi-level paging?

easy

A. A single large page table containing all entries

B. Multiple page tables arranged in a hierarchy

C. A flat list of physical addresses

D. A queue of page requests

Solution

1. Step 1: Recall the definition of multi-level paging

   Multi-level paging uses several page tables arranged in levels, not just one big table.

2. Step 2: Identify the correct structure

   The hierarchy of page tables allows efficient address translation and memory use.

3. Final Answer:

   Multiple page tables arranged in a hierarchy -> Option B

4. Quick Check:

   Multi-level paging uses hierarchical page tables = A [OK]

Hint: Multi-level paging uses hierarchical tables, not one big table [OK]

Common Mistakes:

• Choosing a single large page table
• Confusing with flat address lists
• Thinking it uses queues

3. Given a 32-bit virtual address split into 3 parts for a 3-level paging system: 10 bits for level 1, 10 bits for level 2, and 12 bits for offset, how many entries does the level 2 page table have?

medium

A. 512 entries

B. 4096 entries

C. 2048 entries

D. 1024 entries

Solution

1. Step 1: Understand the bit allocation for level 2

   Level 2 uses 10 bits, so number of entries = 2^10.

2. Step 2: Calculate 2 to the power of 10

   2^10 = 1024 entries in the level 2 page table.

3. Final Answer:

   1024 entries -> Option D

4. Quick Check:

   2^10 = 1024 entries [OK]

Hint: Number of entries = 2^(bits for that level) [OK]

Common Mistakes:

• Using offset bits instead of level bits
• Calculating 2^12 or 2^20 incorrectly
• Mixing levels' bit counts

4. A system uses 2-level paging with 10 bits for the first level and 10 bits for the second level. If the page size is 4 KB, what is the total virtual address size in bits? Identify the error in this calculation: 10 + 10 + 12 = 34 bits.

medium

A. The page size bits are counted twice; correct size is 10 + 10 + 12 = 32 bits

B. The page size bits should be 12, so total is 10 + 10 + 12 = 34 bits

C. The page size bits are counted twice; correct size is 10 + 10 + 12 = 34 bits

D. The page size bits are counted twice; correct size is 10 + 10 = 22 bits

Solution

1. Step 1: Understand the components of virtual address size

   Virtual address size = bits for level 1 + bits for level 2 + bits for page offset.

2. Step 2: Calculate page offset bits from page size

   Page size 4 KB = 2^12 bytes, so offset bits = 12.

3. Step 3: Sum bits correctly

   10 (level 1) + 10 (level 2) + 12 (offset) = 32 bits.

4. Step 4: Identify the error

   Counting page size bits twice or misunderstanding system architecture causes confusion; usually total virtual address size is 32 bits.

5. Final Answer:

   The page size bits are counted twice; correct size is 10 + 10 + 12 = 32 bits -> Option A

6. Quick Check:

   Page size bits counted once, total 32 bits [OK]

Hint: Add bits once per part; page size bits = log2(page size) [OK]

Common Mistakes:

• Counting page size bits twice
• Assuming page size bits are 10
• Ignoring page size when calculating address size

5. In a 3-level paging system, if the virtual address is 48 bits and the page size is 4 KB, how many bits are used for each page table index if the bits are evenly divided among the three levels?

hard

A. 10 bits for each level

B. 14 bits for each level

C. 12 bits for each level

D. 16 bits for each level

Solution

1. Step 1: Calculate offset bits from page size

   Page size 4 KB = 2^12 bytes, so offset bits = 12.

2. Step 2: Calculate bits left for page table indices

   Total virtual address bits = 48, subtract offset bits: 48 - 12 = 36 bits for page tables.

3. Step 3: Divide bits evenly among 3 levels

   36 bits / 3 levels = 12 bits per level for page table indices.

4. Final Answer:

   12 bits for each level -> Option C

5. Quick Check:

   (48 - 12) / 3 = 12 bits per level [OK]

Hint: Subtract offset bits, then divide remaining bits by levels [OK]

Common Mistakes:

• Not subtracting offset bits first
• Dividing total bits by levels without offset
• Using wrong page size bits