Paging and Demand Paging

Paging and Demand Paging in Operating Systems

Paging and demand paging are techniques used by modern operating systems to manage memory efficiently, especially in systems that support virtual memory. These techniques help in dealing with memory fragmentation, optimizing memory utilization, and enabling more efficient multitasking by allowing processes to run even when they do not have enough physical memory.

1. Paging

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. In a paging system, the physical memory is divided into fixed-size blocks called pages. Similarly, the logical address space (virtual memory) of a process is divided into fixed-size blocks called page frames. When a process is executed, its pages are loaded into available page frames in physical memory.

Key Concepts in Paging:

• Pages: Fixed-size blocks of virtual memory.
• Page Frames: Fixed-size blocks of physical memory.
• Page Table: A data structure used to map virtual pages to physical page frames. Each process has its own page table, which keeps track of where the pages of that process are stored in physical memory.

In paging, the operating system and the hardware (specifically the Memory Management Unit or MMU) work together to translate the virtual addresses used by a program into physical addresses.

Benefits of Paging:

• Eliminates External Fragmentation: Paging helps eliminate external fragmentation because physical memory is divided into fixed-size pages, which are easier to allocate. Pages do not need to be contiguous in physical memory.
• Simplifies Memory Allocation: Memory can be allocated and freed in small fixed-size chunks (pages), making the memory management simpler.
• Efficient Utilization of Memory: Paging allows the system to use available memory more efficiently by allocating memory pages wherever free frames are available.

How Paging Works:

1. The virtual address generated by the CPU consists of two parts: the page number and the offset (the specific location within the page).

   • For example, for a 32-bit virtual address: the first 20 bits represent the page number, and the last 12 bits represent the offset within the page.

2. The operating system uses a page table to map virtual pages to physical page frames.

   • For example, if a process’s virtual page 3 is mapped to physical frame 5, the page table entry for page 3 will store the number 5.

3. When a program accesses a memory address, the MMU uses the page table to translate the virtual address into the corresponding physical address.

Example:

• Suppose the program accesses address 0x2000. If the page size is 1 KB, this address lies in page 2 (as 0x2000 divided by 1 KB gives 2) with an offset of 0x000 (as 0x2000 modulo 1 KB is 0). The MMU looks up the page table and finds that page 2 is mapped to physical page frame 4. It then adds the offset 0x000 to this physical frame, resulting in the final physical address.

Page Table Example:

Consider a process with 4 virtual pages and 4 physical frames. The page table could look like this:

In this case, virtual page 0 is stored in physical frame 2, virtual page 1 in frame 0, and so on.

2. Demand Paging

Demand Paging is an optimization of the paging technique. It only loads the pages of a process into physical memory when they are actually needed during execution. This is also called lazy loading, as the system doesn't load the entire program into memory at once. Instead, it waits until a page is accessed (or "demanded") by the process.

How Demand Paging Works:

1. Initial Loading: When a process starts, only a small portion of its pages, typically just the ones needed for initial execution, are loaded into physical memory.
2. Page Fault: When a process tries to access a page that is not currently in memory, a page fault occurs. A page fault is an interrupt that triggers the operating system to bring the required page into memory from the disk.
3. Page Replacement: If there is no free space in physical memory, the operating system may need to swap out a page that is currently in memory and write it back to the disk (usually to a swap space or a page file) to make room for the new page.
4. Page Table Update: Once the required page is loaded into memory, the page table is updated to reflect the new mapping between the virtual page and the physical frame.
5. Execution Continues: The process continues executing after the required page is loaded into memory.

Advantages of Demand Paging:

• Reduced Memory Usage: Only the pages that are actually used by a program are loaded into memory, which saves memory.
• Faster Start-Up: Since only a small portion of the program needs to be loaded initially, the program can start faster.
• Efficient Memory Utilization: Demand paging allows the system to allocate memory to more processes than the physical memory size would otherwise allow, because only a portion of each process is in memory at any given time.

Page Faults in Demand Paging:

• When a page fault occurs, the operating system must load the page from secondary storage (usually a hard disk) into physical memory. This process involves the following steps:
  1. The operating system suspends the process that caused the page fault.
  2. It identifies which page needs to be loaded into memory.
  3. It checks if there is space available in memory. If not, it uses a page replacement algorithm (e.g., Least Recently Used (LRU), FIFO) to decide which page to evict.
  4. The requested page is loaded from disk into physical memory.
  5. The page table is updated with the new mapping.
  6. The process is resumed, now with the required page in memory.

Example of Demand Paging:

1. A process starts executing, and the operating system loads just the first few pages into memory.
2. The process accesses an instruction in a page that is not yet in memory. This causes a page fault.
3. The operating system loads the required page from disk into a free frame in memory.
4. The process continues execution.

Page Fault Rate and Performance:

• The performance of demand paging depends on the page fault rate, which is the frequency with which page faults occur.
  • Low page fault rate: If most pages are already in memory, the system performs well.
  • High page fault rate: If a process causes frequent page faults, it can result in performance degradation, as loading pages from disk is much slower than accessing them from memory.

3. Page Replacement Algorithms

When memory is full and a page needs to be brought in from disk, the operating system uses page replacement algorithms to decide which page to swap out of memory. Some common algorithms are:

• Least Recently Used (LRU): The page that hasn’t been used for the longest time is swapped out.
• First-In-First-Out (FIFO): The oldest page (the one that was loaded first) is swapped out.
• Optimal Page Replacement: The page that will not be needed for the longest period of time in the future is swapped out (this is difficult to implement because it requires knowledge of future page accesses).

4. Swapping and Thrashing

• Swapping: In systems that use demand paging, swapping refers to moving pages between physical memory and secondary storage (swap space) as needed.
• Thrashing: Thrashing occurs when the system spends too much time swapping pages in and out of memory, resulting in poor performance. This typically happens when the system is overloaded, and the available physical memory is insufficient to keep the pages needed by the processes.

Conclusion

Paging is a memory management scheme that divides both physical and virtual memory into fixed-size blocks, making memory allocation more flexible and eliminating external fragmentation. Demand paging further optimizes paging by only loading pages into memory when they are needed, thus saving memory and improving performance. While demand paging improves memory utilization, it introduces the potential for page faults and swapping, which can impact performance, particularly when there is high demand for memory or when thrashing occurs.