OS Part 9: Virtual Memory 🧿
That Indian Dev 🇮🇳
Virtual memory is a crucial technique used in modern operating systems to enable the execution of processes that are larger than the available physical memory. It creates an illusion of having a vast main memory by utilizing a portion of secondary storage, often referred to as swap space, as an extension of the main memory.
The primary advantage of virtual memory is the ability to run programs that exceed the size of physical memory. Traditionally, all instructions of a program had to reside in physical memory for execution. This limitation constrained the size of programs to the available physical memory. However, in reality, many programs do not require all their instructions simultaneously. By allowing the execution of partially loaded programs, virtual memory provides several benefits:
Overcoming Physical Memory Constraints: Virtual memory removes the constraint of available physical memory for program execution. It enables programs to access and utilize a larger address space than what is physically present.
Multiprogramming: By requiring less physical memory per user program, virtual memory allows for the concurrent execution of more programs. This leads to increased CPU utilization and improved system throughput, as multiple programs can be efficiently executed in parallel.
System and User Benefits: Running programs that are not entirely loaded in memory benefits both the system and the user. The system can allocate resources more flexibly, optimizing memory utilization across various processes. Users can execute larger programs without being limited by physical memory constraints, resulting in enhanced application performance.
Page Fault
A page fault refers to an event that occurs when a process attempts to access a page that is not currently present in the physical memory (RAM). When such an access is made, the hardware raises a page fault exception, triggering the intervention of the operating system. The operating system then takes the necessary actions to bring the required page into memory from secondary storage (such as the hard disk). Page faults are an essential mechanism in virtual memory systems as they enable efficient memory management by dynamically loading pages into physical memory only when they are needed. This approach allows the system to handle programs that exceed the available physical memory capacity and execute them efficiently.
Pager
In virtual memory systems, a pager is responsible for managing individual pages of a process. When a page is demanded by a process or when a page fault occurs, the pager is responsible for copying the required page from secondary storage into the main memory (RAM). Various page replacement algorithms are utilized by the pager to determine which pages should be evicted from memory when necessary. Unlike a swapper, which handles entire processes, a pager operates at the page level and treats a process as a sequence of pages rather than a continuous address space. This distinction is crucial, as a pager focuses on managing individual pages efficiently, optimizing memory utilization, and ensuring that only the required pages are loaded into memory.
Demand Paging
Demand paging is a vital technique used in virtual memory systems to optimize memory usage and improve system performance. It operates on the principle of selectively loading pages into memory only when they are needed, reducing unnecessary disk I/O and minimizing memory wastage. Let's delve into the sequential steps involved in demand paging:
Prediction: When a process is scheduled for execution, the pager attempts to predict which pages will be required based on the program's behaviour and access patterns.
Selective Page Loading: Instead of loading the entire process into memory, the pager brings only those pages that are predicted to be needed. By avoiding the unnecessary loading of pages that won't be accessed during program execution, demand paging conserves memory resources.
Reduced Swap Time and Memory Usage: Selective page loading significantly reduces swap time, as only the necessary pages are transferred between secondary storage and main memory. Additionally, demand paging optimizes physical memory usage by loading pages on demand, rather than bringing the entire process into memory at once.
Valid-Invalid Bit Scheme: Each process's page table employs a valid-invalid bit to indicate whether a page is currently in memory or resides in secondary storage. A valid bit of 1 signifies that the page is both legal and present in memory, while a valid bit of 0 indicates that the page is either not valid (not part of the process's logical address space) or valid but currently in secondary storage.
Handling Access to Invalid Pages: If a process attempts to access a page marked as invalid, a page fault occurs. The paging hardware detects the invalid bit and triggers a trap to the operating system.
Page Fault Handling: To handle a page fault, the operating system follows these steps:
Validity Check: The internal table within the process control block (PCB) is consulted to determine the validity of the memory access reference.
Invalid Reference: If the reference is invalid, the process throws an exception, indicating an invalid memory access.
Valid Reference: If the reference is valid, the pager initiates the swapping process for the required page.
Allocating a Free Frame: A free frame is located from the free-frame list, representing available physical memory.
Disk Operation Scheduling: A disk operation is scheduled to read the desired page from secondary storage into the newly allocated frame in physical memory.
Page Table Modification: After the disk read is complete, the page table entry for the page is updated to indicate its presence in memory (valid bit set to 1).
Resuming Execution: The instruction interrupted by the page fault trap is restarted, allowing the process to access the page as if it had always been in memory.
Demand paging is a fundamental technique in virtual memory management that enables efficient utilization of memory resources. By loading pages on demand and utilizing predictive algorithms, demand paging enhances system performance, allows for the execution of larger programs, and optimizes memory allocation in virtual memory systems.
Pure Demand Paging
In extreme cases, a process can start execution without any pages initially loaded into memory. When the operating system sets the instruction pointer to the first instruction of the process, which is not in memory, a page fault immediately occurs, and the required page is brought into memory. This ensures that pages are brought into memory only when they are needed.
Leveraging Locality of Reference
Demand paging takes advantage of the principle of locality of reference, which states that programs tend to access memory locations near those recently accessed. By bringing pages into memory based on the locality of reference, demand paging minimizes the occurrence of page faults and optimizes memory usage, resulting in improved performance.
Page Replacement Algorithm
During a page fault, which happens when a process attempts to access a page not currently present in a frame, the operating system must bring the required page from the swap space into a free frame. However, in cases where all frames are occupied due to high system utilization, the operating system employs a page replacement algorithm to select a currently allocated page in a frame for eviction, creating space for the new page. This algorithmic decision ensures that the necessary pages are available in the main memory, optimizing memory utilization and enabling efficient execution of processes in virtual memory systems.
Types of Page Replacement Algorithm:
FIFO (First-In-First-Out): The FIFO algorithm allocates frames to pages in the order they arrived in memory, replacing the oldest page when a new page needs to be loaded. While this algorithm is simple to implement, its performance may not always be optimal. The page replaced could be an initialization module that has not been used for a long time or a heavily used page containing important variables, causing frequent page faults. One limitation of FIFO is the presence of Belady's anomaly, where increasing the number of frames can lead to an increase in page faults, contrary to other algorithms.
Optimal Page Replacement: The optimal algorithm replaces the page that will not be referenced in the future or, if not possible, replaces the page that will be referenced farthest in the future. Optimal replacement provides the lowest page fault rate among all algorithms. However, it requires future knowledge of the reference string, which is generally impossible to obtain in real-world scenarios. Implementing optimal page replacement is akin to Shortest Job First (SJF) scheduling, making it difficult to implement practically.
Least Recently Used (LRU): LRU approximates the near future by using the recent past as a basis for page replacement decisions. It replaces the page that has not been used for the longest period. LRU can be implemented using two approaches:
Counters: Each page table entry is associated with a time field, and the page with the smallest time value is replaced.
Stack: A stack of page numbers is maintained, and whenever a page is referenced, it is moved to the top of the stack. The most recently used page is always at the top, while the least recently used page is at the bottom. A doubly linked list can be used to efficiently remove entries from the middle of the stack.
Counting-Based Page Replacement: This approach involves keeping a counter to track the number of references made to each page (reference counting). Two variations of counting-based page replacement are:
Least Frequently Used (LFU): Pages with the smallest reference count are considered less frequently used and are replaced.
Most Frequently Used (MFU): This algorithm assumes that pages with the smallest count were recently brought in and have yet to be used. The page with the smallest count is replaced. However, both LFU and MFU replacements are not commonly used in practice.
Selecting an appropriate page replacement algorithm depends on system requirements, workload characteristics, and available resources. By intelligently replacing pages, these algorithms optimize memory utilization and contribute to overall system efficiency in virtual memory environments.
Belady's Anomaly
Belady's anomaly is a peculiar phenomenon in page replacement algorithms, specifically with the FIFO algorithm. It defies the common expectation that increasing the number of available frames in a virtual memory system would always lead to a decrease in the number of page faults. Surprisingly, in certain cases, adding more frames can increase page faults. This anomaly occurs when the FIFO algorithm evicts pages from the working set, causing frequently accessed pages to be removed and causing more page faults. It highlights the need for more advanced page replacement algorithms, like LRU or optimal, that consider the recent usage history or future references of pages to avoid such counterintuitive behaviour and optimize system performance.
Thrashing
Thrashing is a critical issue that can have a severe impact on the performance of computer systems, especially in the context of virtual memory management. It arises when a process lacks the required number of frames to accommodate its actively used pages, leading to a continuous stream of page faults. As a consequence, the process is caught in a frustrating cycle of replacing pages that are immediately needed again, perpetuating the occurrence of page faults. This detrimental condition diverts a significant amount of system resources to servicing page faults, causing a substantial decline in overall performance. The excessive paging activity overwhelms the system, resulting in slowdowns, increased response times, and decreased throughput. The struggle to allocate frames efficiently and meet process demands exacerbates the problem, making thrashing a formidable obstacle to achieving optimal system operation.
Techniques to Address Thrashing
To combat thrashing and restore system performance, several techniques are commonly employed:
Working Set Model: The working set model is based on the concept of locality, which suggests that if a process is allocated enough frames to accommodate its current locality (the set of pages actively used), it will experience page faults only when it transitions to a new locality. If the allocated frames are insufficient to hold the current locality, the process is bound to thrash. By appropriately allocating frames based on the working set, the system can mitigate thrashing effects.
Page Fault Frequency: Monitoring the page fault frequency is crucial in detecting and managing thrashing. A high page-fault rate indicates that the process needs more frames to operate efficiently. Conversely, if the page-fault rate is too low, it may indicate that the process has an excess of frames. By establishing upper and lower bounds on the desired page fault rate, the system can dynamically adjust frame allocations. If the page-fault rate surpasses the upper limit, the process is allocated additional frames. Conversely, if the rate falls below the lower limit, frames are removed from the process.
In conclusion, virtual memory and its key components, including demand paging, page faults, page replacement algorithms, and the impact of thrashing, play vital roles in optimizing memory utilization and enhancing system performance. Virtual memory enables efficient process execution by creating the illusion of abundant memory and dynamically managing memory resources. Through the implementation of effective page replacement algorithms and the monitoring of page fault rates, system administrators can effectively address performance bottlenecks and prevent thrashing.
With this, we conclude our blog series on operating systems. Throughout this series, we have extensively explored various aspects of operating systems, delving into their functionalities, structures, and fundamental concepts. We trust that this blog series has offered valuable insights into the captivating world of operating systems and their significance in modern computing environments.
