Multi-level paging in Operating Systems - Mini Project: Build & Apply

Understanding Multi-level Paging

📖 Scenario: You are learning how modern operating systems manage memory using multi-level paging. This technique helps the system efficiently translate virtual addresses to physical addresses by breaking down the page table into multiple levels.Imagine a large library where books are organized in sections, shelves, and then individual books. Multi-level paging works similarly by dividing the address translation into steps.

🎯 Goal: Build a simple representation of a two-level page table using dictionaries to understand how virtual addresses are translated step-by-step.

📋 What You'll Learn

Create a dictionary representing the first-level page table with exact entries.

Add a variable representing the page size in bytes.

Use a nested dictionary comprehension to build the second-level page tables.

Complete the structure by linking second-level tables to the first-level entries.

💡 Why This Matters

🌍 Real World

Multi-level paging is used in modern operating systems to efficiently manage large virtual memory spaces by breaking down page tables into smaller parts.

💼 Career

Understanding multi-level paging is essential for roles in system programming, operating system development, and computer architecture.

1

Create the first-level page table

Create a dictionary called first_level_page_table with these exact entries: 0: None, 1: None, 2: None, 3: None representing empty second-level page tables.

Operating Systems

# Create the first_level_page_table dictionary with keys 0 to 3 and values None
# Your code here

Hint

Use curly braces to create a dictionary with keys 0, 1, 2, 3 and values set to None.

2

Define the page size

Create a variable called page_size and set it to 4096 representing the size of a page in bytes.

Operating Systems

first_level_page_table = {0: None, 1: None, 2: None, 3: None}
# Define the page_size variable and set it to 4096
# Your code here

Hint

Assign the integer 4096 to the variable named page_size.

3

Create second-level page tables

Use a dictionary comprehension to create a dictionary called second_level_tables where each key is from 0 to 3 and each value is another dictionary with keys 0 to 3 and values set to None.

Operating Systems

first_level_page_table = {0: None, 1: None, 2: None, 3: None}
page_size = 4096
# Create second_level_tables dictionary with nested dictionaries for keys 0 to 3
# Your code here

Hint

Use nested dictionary comprehensions with range(4) for both levels.

4

Link second-level tables to first-level page table

Update the first_level_page_table so that each key from 0 to 3 points to the corresponding dictionary in second_level_tables.

Operating Systems

first_level_page_table = {0: None, 1: None, 2: None, 3: None}
page_size = 4096
second_level_tables = {i: {j: None for j in range(4)} for i in range(4)}
# Link each first_level_page_table entry to the corresponding second_level_tables dictionary
# Your code here

Hint

Use a for loop from 0 to 3 to assign second_level_tables[i] to first_level_page_table[i].

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