Paging concept and page tables in Operating Systems - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

Paging helps divide a program's memory into fixed-size blocks called pages, allowing efficient and flexible use of physical memory without needing contiguous space.

beginner

Define a page table in the context of paging.

A page table is a data structure used by the operating system to map virtual page numbers to physical frame numbers in memory.

intermediate

Why does paging help prevent external fragmentation?

Because memory is divided into fixed-size pages and frames, any free frame can be used for any page, so memory does not need to be contiguous, avoiding gaps between allocated blocks.

intermediate

What information is typically stored in a page table entry?

Each entry usually contains the frame number where the page is stored, and status bits like valid/invalid, access permissions, and whether the page is in memory or on disk.

intermediate

Explain how a virtual address is translated to a physical address using paging.

The virtual address is split into a page number and an offset. The page number is used to look up the frame number in the page table. The physical address is then the frame number combined with the offset.

What is the size relationship between a page and a frame in paging?

A Pages and frames are the same size

B Pages are larger than frames

C Frames are larger than pages

D Pages and frames can be any size

Pages and frames must be the same size so that any page can fit into any frame.

What does a page table entry NOT typically contain?

A Valid/invalid bit

B Frame number

C Page size

D Access permissions

Page size is fixed and known system-wide, so it is not stored in each page table entry.

Which problem does paging help to solve?

A External fragmentation

B CPU scheduling

C File system organization

D Network communication

Paging eliminates external fragmentation by allowing non-contiguous memory allocation.

In paging, what is the 'offset' part of a virtual address used for?

A To find the page number

B To find the frame number

C To check access permissions

D To find the exact location within a page

The offset specifies the exact byte within the page.

If a page is not currently in physical memory, what does the page table entry indicate?

A The page is corrupted

B The page is invalid or on disk

C The page is locked in memory

D The page is in the CPU cache

The valid/invalid bit shows if the page is in memory or needs to be fetched from disk.

Describe how paging works to translate a virtual address to a physical address.

Think about how the system finds the real memory location from a virtual address.

Explain the role and structure of a page table in memory management.

Consider what information the OS needs to find where a page is stored.

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