Paging concept and page tables in Operating Systems - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the purpose of paging

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

A To divide physical memory into fixed-size blocks called frames and map them to pages in virtual memory

B To increase the size of the CPU cache for faster processing

C To encrypt data stored in memory for security

D To allow direct access to hardware devices without OS intervention

💡 Hint

Think about how memory is managed to avoid fragmentation and simplify allocation.

Paging divides physical memory into fixed-size frames and virtual memory into pages. This allows the OS to map pages to frames flexibly, avoiding fragmentation and simplifying memory management.

📋 Factual

intermediate

Page table entry contents

Which of the following is NOT typically stored in a page table entry?

A Frame number where the page is stored

B Validity bit indicating if the page is in physical memory

C Process ID of the owner process

D Access permissions like read or write

💡 Hint

Consider what information is needed to translate virtual addresses to physical addresses.

Page table entries store the frame number, validity bit, and access permissions. The process ID is managed elsewhere, not in the page table entry.

🔍 Analysis

advanced

Calculating page table size

An operating system uses 32-bit virtual addresses and a page size of 4 KB. How many entries does a single-level page table have?

A 65,536 entries

B 1,048,576 entries

C 262,144 entries

D 4,096 entries

💡 Hint

Calculate the number of pages by dividing the virtual address space by the page size.

Virtual address space is 2^32 bytes. Page size is 4 KB = 2^12 bytes. Number of pages = 2^(32-12) = 2^20 = 1,048,576 entries.

❓ Comparison

advanced

Difference between internal and external fragmentation

Which statement correctly distinguishes internal fragmentation from external fragmentation in memory management?

A External fragmentation occurs only in virtual memory; internal fragmentation occurs only in physical memory.

B External fragmentation happens inside allocated blocks; internal fragmentation is caused by scattered free blocks.

C Internal fragmentation is caused by paging; external fragmentation is caused by segmentation only.

D Internal fragmentation occurs when allocated memory blocks have unused space; external fragmentation is free memory scattered in small blocks.

💡 Hint

Think about wasted space inside allocated blocks versus scattered free space outside allocated blocks.

Internal fragmentation is wasted space inside allocated memory blocks due to fixed block sizes. External fragmentation is free memory scattered in small pieces that can't be used effectively.

❓ Reasoning

expert

Effect of page size on page table size and fragmentation

How does increasing the page size affect the size of the page table and the amount of internal fragmentation?

A Page table size decreases and internal fragmentation increases

B Page table size increases and internal fragmentation decreases

C Both page table size and internal fragmentation increase

D Both page table size and internal fragmentation decrease

💡 Hint

Consider how page size affects the number of pages and leftover space inside pages.

Larger page size means fewer pages, so the page table has fewer entries (smaller size). But larger pages cause more unused space inside pages, increasing internal fragmentation.

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