Demand Paging

Demand Paging in Operating Systems

Demand Paging is a memory management scheme used in virtual memory systems where a page of memory is only loaded into physical memory when it is needed, or "on demand". This concept is crucial for systems with virtual memory, as it allows a process to run even if its entire memory requirement cannot fit into physical memory (RAM) at once. It also reduces the amount of memory required for running programs by loading pages only when they are actually used.

How Demand Paging Works

In a system using demand paging, the operating system (OS) loads pages from secondary storage (typically disk or SSD) into RAM only when a page is referenced by a process. This approach avoids the need to load the entire program into memory, reducing memory usage and improving overall system performance.

Basic Steps of Demand Paging

1. Program Execution Starts:

   • A program starts executing, and the OS allocates virtual memory to it. The program's memory is divided into pages.
   • Initially, none of the pages are loaded into physical memory.

2. Page Access:

   • When the program accesses a page (i.e., a specific memory address), the Memory Management Unit (MMU) checks if that page is already in RAM.
   • If the page is not in memory, a page fault occurs.

3. Page Fault Handling:

   • When a page fault occurs, the OS takes control of the situation and loads the required page into physical memory.
   • The OS must also decide which page to swap out from RAM if there’s no space available (if RAM is full), and the chosen page is written back to secondary storage (swap space).
   • The page table is updated to reflect the new mapping between the virtual page and the physical frame.

4. Resuming Execution:

   • Once the page is loaded into physical memory, the program continues execution, and the access to that page is now valid.

5. Page Replacement (If Necessary):

   • If there are not enough free frames in physical memory, the OS will use a page replacement algorithm (like FIFO, LRU, or Optimal) to decide which page should be swapped out to make room for the new page.

Advantages of Demand Paging

1. Efficient Memory Utilization:

   • Demand paging allows the system to only load the pages that are actually needed, which means it doesn't waste memory on pages that the program might never use.
   • It enables programs to run even if they require more memory than is physically available, by relying on secondary storage.

2. Reduced I/O Load:

   • Initially, fewer pages need to be loaded into memory, which reduces the initial memory load and I/O operations compared to loading an entire process into memory all at once.

3. Flexibility:

   • It allows the execution of programs that are larger than the available physical memory. By using swap space, the system can load and unload pages dynamically, allowing large programs to run on machines with limited physical RAM.

4. Faster Start-up:

   • Since only the required pages are loaded on-demand, the system can start executing the program more quickly compared to loading the entire program into memory upfront.

Disadvantages of Demand Paging

1. Page Fault Overhead:

   • Each time a page that is not in memory is accessed, a page fault occurs, and the OS has to spend time swapping pages in and out of memory, which introduces overhead.
   • If a program accesses pages that are not in memory frequently, it can cause significant delays, leading to poor performance.

2. Thrashing:

   • If a system is constantly swapping pages in and out of memory (due to frequent page faults), it leads to a situation called thrashing, where the system spends more time managing memory than executing processes.
   • Thrashing happens when there is insufficient physical memory, and too many processes are competing for limited resources.

3. Disk I/O Latency:

   • Reading pages from disk (secondary storage) is much slower than accessing them from RAM. This can lead to significant performance degradation, especially if the system is performing a lot of page swaps.

4. Complexity:

   • Implementing demand paging requires complex OS algorithms to manage page faults, page replacement, and swapping efficiently. The operating system must also maintain and manage page tables for each process to track which pages are in memory and which are on disk.

Page Fault Handling in Demand Paging

When a page fault occurs (meaning the page is not in memory), the OS must take the following steps to handle it:

1. Identify the Page Fault:

   • The MMU detects that a page is not in memory and triggers an interrupt to the OS, notifying it that a page fault has occurred.

2. Suspend the Process:

   • The process is suspended while the OS handles the page fault. This ensures the program doesn't continue executing while waiting for the required page.

3. Check for Free Frames:

   • The OS checks whether there are any free frames in physical memory to load the page. If a free frame is available, the OS loads the page into that frame.

4. Swap Out a Page (if necessary):

   • If there is no free frame, the OS needs to swap out a page from memory to the disk (swap space). The decision about which page to swap out is made using a page replacement algorithm.
   • The page table is updated to reflect the new mapping of virtual pages to physical memory locations.

5. Load the Required Page:

   • The OS loads the page from secondary storage (swap space) into memory.
   • The page table is updated to reflect the new location of the page in physical memory.

6. Resume Execution:

   • The process is resumed from where it left off, with the page now available in memory.

Page Replacement Algorithms

When a page fault occurs, and there is no available space in physical memory to load the required page, the OS needs to decide which page to swap out. This decision is made using a page replacement algorithm. Some common algorithms are:

1. First-In-First-Out (FIFO):

   • Pages are replaced in the order in which they were brought into memory. The oldest page (the one that has been in memory the longest) is swapped out.

2. Least Recently Used (LRU):

   • The page that has not been used for the longest time is swapped out. This algorithm tries to minimize page faults by removing the pages that are least likely to be used in the future.

3. Optimal Page Replacement:

   • This is an ideal algorithm that replaces the page that will not be used for the longest time in the future. However, this is not practically implementable because it requires knowledge of future memory references.

4. Clock Algorithm:

   • A more efficient approximation of LRU. The clock algorithm uses a circular list of pages and a "clock hand" to keep track of the pages. When a page needs to be replaced, the clock hand checks the "referenced" bit of each page, and the first unreferenced page is swapped out.

Example of Demand Paging

Imagine a program that has 4 pages, but the physical memory can only hold 2 pages at a time. Here's how demand paging would work:

1. Initial Access:

   • Page 1 is accessed. Since it’s not in memory, a page fault occurs, and the OS loads Page 1 into a free frame.

2. Second Access:

   • Page 2 is accessed. Since it’s not in memory, a page fault occurs, and Page 2 is loaded into the other available frame.

3. Third Access:

   • Page 3 is accessed. Since memory is full, the OS must swap out a page. It might use FIFO and swap out Page 1, loading Page 3 into its frame.

4. Fourth Access:

   • Page 4 is accessed. The OS swaps out Page 2 (or whichever page is selected by the page replacement algorithm) and loads Page 4 into memory.

In this example, the program only has 2 pages in memory at any given time, but because of demand paging, it can still access all 4 pages by swapping them in and out of memory as needed.

Conclusion

Demand Paging is an essential technique for efficient memory management, especially in systems with virtual memory. By loading pages only when they are needed, demand paging helps in reducing memory consumption, allows for the execution of larger programs than the available physical memory, and provides an abstraction that makes programming easier. However, it comes with trade-offs, such as the overhead of page faults and potential performance degradation due to thrashing if the system is not carefully managed.