Paging - CSU360 - Shoolini University

Paging in Operating Systems

1. Paging

Paging is a memory management scheme that avoids the need for contiguous allocation of physical memory. It divides both the virtual address space of a program and the physical memory into fixed-size blocks called "pages" and "frames," respectively.

1.1 Concept of Paging

The main concept behind paging is the abstraction of virtual memory. Every address generated by a program is translated from a virtual address to a physical address by the system. This allows programs to think they have more memory than is physically available and simplifies memory management.

1.2 How Paging Works

Paging involves several key steps:

1.2.1 Page Table

The page table contains entries for each page, with each entry holding the frame number where the corresponding page resides in physical memory. If the page is not in memory, the entry will indicate it is invalid.

1.2.2 Page Fault Handling

When a page fault occurs, the operating system has to:

1.2.3 Translation Lookaside Buffer (TLB)

The TLB enhances the speed of virtual address translation by keeping recent translations stored in a fast-access hardware cache, reducing the frequency of page table lookups.

1.3 Advantages and Disadvantages of Paging

Paging offers several advantages:

However, it also has some disadvantages:


// Example of a page table update function in pseudo-code
void updatePageTable(int virtualPageNumber, int frameNumber, bool isValid) {
    PageTable[virtualPageNumber].frameNumber = frameNumber;
    PageTable[virtualPageNumber].isValid = isValid;
}

2. Paging Formulas

Understanding the mathematics behind paging is crucial for optimizing memory management. Key formulas help calculate the properties of pages, frames, and address translations.

2.1 Basic Definitions

2.2 Address Translation

Address translation converts virtual addresses to physical addresses using the page table. Key components of this process are:

2.2.1 Formulas for Address Translation

The following formulas are used to calculate parts of the address translation:

$$ \text{Page Number} = \frac{\text{Virtual Address}}{\text{Page Size}} $$

$$ \text{Offset} = \text{Virtual Address} \mod \text{Page Size} $$

$$ \text{Physical Address} = (\text{Frame Number} \times \text{Page Size}) + \text{Offset} $$

2.3 Calculating Number of Pages and Frames

The total number of pages and frames required by a system can be calculated as follows:

$$ \text{Number of Pages} = \frac{\text{Total Virtual Memory}}{\text{Page Size}} $$

$$ \text{Number of Frames} = \frac{\text{Total Physical Memory}}{\text{Page Size}} $$

2.4 Memory Utilization and Overhead

The effectiveness of paging is influenced by the overhead for maintaining page tables and the actual utilization of memory:

$$ \text{Page Table Size} = \text{Number of Pages} \times \text{Entry Size} $$

Overhead calculation must consider both the physical space occupied by the page table and the processing time to manage it.

// Example code for calculating number of pages
int calculateNumberOfPages(int totalVirtualMemory, int pageSize) {
    return totalVirtualMemory / pageSize;
}

// Example code for calculating physical address
int calculatePhysicalAddress(int frameNumber, int offset, int pageSize) {
    return (frameNumber * pageSize) + offset;
}