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:
- Page Table: A table that stores the mapping between virtual pages and physical frames.
- Page Fault: Occurs when a program accesses a page that is not currently loaded in any of the physical frames in memory.
- Translation Lookaside Buffer (TLB): A cache used to speed up address translation by keeping a small part of the page table.
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:
- Identify the missing page required by the program.
- Select a victim frame if memory is full, possibly using an algorithm like LRU for page replacement.
- Load the requested page into the chosen frame from the disk.
- Update the page table to reflect the changes.
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:
- Efficient Memory Use: Reduces wasted space by eliminating the need for contiguous memory blocks.
- Simplifies Management: Only the page table needs to be managed, rather than individual blocks of memory.
- Supports Virtual Memory: Allows systems to execute programs that require more memory than is physically available.
However, it also has some disadvantages:
- Overhead: Maintaining page tables and handling page faults can consume significant system resources.
- Complexity: Implementing efficient page handling mechanisms (like TLB) adds to the complexity of the operating system.
// 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
- Page: A block of virtual memory, typically ranging from 4KB to 64KB.
- Frame: A block of physical memory, the same size as a page, where pages are loaded.
- Page Size (S): The size of a page or frame, a power of 2, which simplifies address calculations.
2.2 Address Translation
Address translation converts virtual addresses to physical addresses using the page table. Key components of this process are:
- Virtual Address (VA): An address generated by the CPU during program execution.
- Physical Address (PA): The actual address in main memory.
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:
- Page Table Size: The total size of the page table depends on the number of pages and the size of each entry.
- Utilization: The percentage of physical memory actively used by processes.
$$ \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;
}