Paging in Operating Systems: What it Is & How it Works

Introduction

Paging is a memory management technique in operating systems that enables processes to access more memory than is physically available. The system improves performance and resource utilization and reduces the risk of page faults. This method is also known as swapping in Unix-like systems.

This article explains what paging in operating systems is and how it works.

What Is Paging?

Paging is a memory management method that enables processes to use virtual storage. A process has access to the pages it needs without waiting for them to be loaded into physical memory. The technique stores and retrieves data from a computer's secondary or virtual storage (hard drive, SSD, etc.) to the primary storage (RAM).

When a process tries to access a page that is not in RAM, the OS brings in the page from the virtual memory.

Paging improves the efficiency of memory management. By dividing memory into pages, the operating system moves pages in and out of memory as needed. Keeping only the frequently used pages reduces the number of page faults, which improves system performance and responsiveness.

How Does Paging Work?

Paging enables an OS to transfer data between secondary (virtual) and primary (physical) memory. Both storage types are divided into fixed-size blocks. The blocks in primary memory are frames, while those in secondary storage are pages.

Whenever a program executes, it splits into pages, and the OS automatically stores them in secondary memory.

When the process requests memory, the OS allocates page frames from the primary memory to the process. Next, the OS moves program pages from the secondary memory to the primary memory frames.

The logical pages and physical page frames maintain the relationship using a structure called the page table. The memory management unit (MMU) uses the page table to translate logical addresses (virtual memory) into physical addresses (physical memory).

Use the following command to print the page table in the terminal/command prompt in Linux:

pmap [PID]

For the command to work, find the process ID first using the ps, top, pgrep, or atop command. For instance, if the PID for the running process of choice is 17422, print the table with the following command:

pmap 17422

The pmap command output consists of multiple lines, each with four columns except for the first. The first line shows the process ID (PID) and the name. The remaining lines list the mapped virtual page addresses for the process.

The columns in the output have the following information:

• PID. The process ID.
• Kbytes. The page size in kilobytes.
• Mode. The permissions for the page.
• Mapping. The name of the file or object the page is mapped to.

Paging Glossary

Knowing the associated terminology is essential to understanding the paging process. Below is a list of common terminology when working with paging:

• Pages. Fixed-sized blocks of logical/secondary memory. Pages represent a unit of information transfer between main memory and secondary storage. A page set is a process working set. A working set constantly changes as the process accesses different parts of memory.
• Page table. A data structure that enables the memory management unit (MMU) to translate logical addresses into physical addresses.
• Physical memory. The actual memory available to the computer, usually in the form of RAM. In paging, the physical, or main, memory splits into fixed-size blocks or page frames, each with a unique address. The frames are the same size as the pages used by the process.
• Virtual memory (logical/secondary memory). A hard disk or solid-state drive that serves as an extension of the main memory. It compensates for physical memory shortages by temporarily bringing in data from RAM. The logical memory is divided into the same size blocks, called pages. Each page has a logical address within the virtual memory.
• Memory management unit (MMU). A hardware component that translates logical addresses into physical addresses. The MMU also manages the allocation and deallocation of pages in memory.
• Logical address (virtual address). When a program runs, the CPU generates a logical address for each page. The MMU translates logical into physical addresses.
• Logical address space (virtual address space). A set of logical addresses generated by a running program.
• Physical address. Each frame within a physical memory has a unique physical address. Addresses represent a specific location of a process in actual memory.
• Physical address space. The range of all possible physical addresses a system is able to reference.

Paging Workflow

Paging involves the systematic retrieval and display of segmented information. The paging workflow either ends with a page hit or encounters a page fault.

The workflow follows these steps:

1. A process executes.

2. The OS allocates the process segments into the same-sized pages in the virtual memory. It also creates corresponding page frames in physical memory.

3. The OS creates a page table, which maps the process's logical pages to the physical page frames.

4. Another process requests access to the process frame or page.

5a. The requested page is already in the main memory, and the process continues execution, creating a page hit.

5b. If the requested page is not in the main memory, the system is dealing with the page fault or page miss. The paging process continues to resolve the issue:

6. The memory management unit (MMU) uses the page table to identify the process's correct location (correct page frame) in the physical memory.

7. The page table updates with the correct physical address.

8. The OS brings the page into page frames in the primary memory,

9. The process resumes from the point of interruption, and can now access the page. The page fault resolves.

Paging Techniques

The paging implementation offers multiple methods, and the choice of a specific technique depends on several factors. This includes the OS type, available memory, and the process's requirements.

For example, demand paging is a good choice for operating systems that need to be efficient. On the other hand, anticipatory paging is a better choice for operating systems that need to be responsive.

The text below explains the different paging techniques:

• Demand paging. The most common memory management technique in modern operating systems like Windows, Linux, and macOS. It optimizes memory usage by keeping only the currently used page in memory.
• Anticipatory paging. A more aggressive form of demand paging that preloads the pages near the requested page as soon as possible. The goal is to reduce page faults and latency by predicting which pages not in RAM are likely to be needed soon.
• Prepaging. Prepaging is a less aggressive form of anticipatory paging. The system preloads any pages that might be needed in the near future (but not immediately or soon).
• Free page queue, stealing, and reclamation. These techniques manage memory by keeping track of free frames and reallocating the frames as needed.
  • The free page queue. A list of page frames available for allocation. By ensuring the queue never empties, the process minimizes dealing with page faults. 
  • Page stealing. A process of freeing up page frames. Pages that haven't been referenced recently are removed from memory. The free page frames are then added to the free page queue.
  • Reclaiming. Reclaiming (in conjunction with stealing) frees up page frames no longer in use. However, reclaiming is more aggressive. The OS can even reclaim the pages that are likely to restart soon.
• Pre-cleaning. The process saves the contents of modified pages back to disk, even if those pages are likely to be modified again soon. When a new program runs, the system does not have to wait for the pages to be read from disk, which improves the start-up time.
• Copy-on-write paging. When a process attempts to write to a page that is already in use by another process, the OS creates a copy of the page and gives the process exclusive access to the copy. This ensures that the two processes cannot overwrite each other's data.
• Segmented paging. Combines paging with segmentation by splitting the main memory into variable-sized segments, each with a page table. The segments divide into even smaller, fixed-sized pages. Unlike virtual memory, which employs page-based division, segments handle the mapping of virtual to physical memory addresses.
• Inverted paging. A technique where the page table is in memory, and the physical memory is divided into frames. When a process needs to access a page, it looks up the page table to find the physical frame.

Page Faults

A page fault occurs when a process tries to access a page not present in physical memory. The page is unavailable either because it has not been in use recently or because there is insufficient memory.

Moreover, page faults occur if:

• The page has never been loaded into memory before.
• The page has been removed from memory to make room for another page.
• The page has been modified in memory and needs to be written back to disk.

The best strategy for dealing with page faults depends on several factors, including the OS type, the available memory, and the processes. The OS handles page faults using either a paging method or by terminating the process.

Possible solutions are to do one of the following:

• Terminate the program if the page is not important or if the program is not in a critical section. Different page replacement algorithms determine which page to evict when a page fault occurs. The most common page replacement algorithms include Least Recently Used (LRU), First In, First Out (FIFO), and Optimal.
• Move an unused page to the secondary memory and bring in the page causing the page fault to the primary memory. The goal is to ensure the program is able to continue running. 
• Preload pages that the operating system predicts are going to be needed soon (anticipatory paging or prepaging). This helps reduce page faults but also leads to wasting memory if the preloaded pages are unused.

Thrashing

Thrashing occurs in virtual memory when the page fault rate becomes so high that the system spends more time servicing page faults and not enough time executing user code.

The feedback loop that causes thrashing begins when a process experiences a page fault. The operating system (OS) must then load the requested page from the disk into memory, which is time-consuming.

If the OS receives multiple page faults in a brief period, it spends all the time servicing page faults and none executing user code.

Causes of Thrashing

If thrashing occurs, the system continues to slow down until it becomes unusable. The only way to fix thrashing is to address the underlying causes. Some of the causes include:

• Too many processes. When the operating system runs too many processes, it can't keep up with the demands. This leads to a high page faults rate, as the operating system has to swap pages in and out of memory frequently.
• Too much memory usage. Processes that use a lot of memory prevent the operating system from simultaneously keeping all the pages in memory. This also leads to a high rate of page faults.
• Poor page replacement algorithm. The page replacement algorithm decides which page to evict when a page fault occurs. If the page replacement algorithm is not good, it evicts frequently used pages, which leads to a high rate of page faults.
• A high degree of multiprogramming. When the multiprogramming degree is high, processes run simultaneously in the system. This puts a strain on the operating system and leads to thrashing.
• Lack of frames: If there are not enough frames available in memory, the operating system has to evict pages from memory when new pages arrive.

Different methods to prevent thrashing are:

• Limiting the number of processes.
• Allocating less memory to processes. 
• Using a good page replacement algorithm. 
• Increasing the amount of RAM.
• Closing unused applications
• Replacing memory-heavy programs. 
• Increasing the swap file size.

Advantages of Paging

Paging allows operating systems to use physical memory more efficiently and improves system performance. Key paging advantages are:

• Reducing external fragmentation. Paging allows the operating system to use more memory than possible if all pages are simultaneously resident in memory. The OS moves pages not currently in use onto the disk and then swaps them back in when needed.
• Improving memory usage. Paging improves performance by reducing the time the CPU waits for pages to load from the disk. The operating system keeps the most frequently used pages in memory and only swaps out the pages not used as often.
• Simplifying memory management. Paging streamlines memory management for the operating system. Therefore, the OS only has to keep track of the pages currently in memory rather than the entire address space of each process.
• Efficient swapping. With paging, the operating system does not have to consider fragmentation when swapping out a page. Moreover, the OS chooses the page least likely to be used.
• Supports virtual memory. Virtual memory support means each process has its own address space, even if the physical memory is not large enough to accommodate all the processes.

Disadvantages of Paging

Paging is a very effective way to use physical memory, but it also adds complexity to the OS and causes page faults. While the advantages outweigh the disadvantages, the following list represents key drawbacks:

• Increased overhead. Paging introduces overhead, as the operating system has to track which pages are in memory and which are on disk. Therefore, this overhead reduces performance, especially on systems with slow disks.
• Page faults. Paging can lead to page faults. The faults occur when the operating system needs to load a page from the disk into memory. When they happen frequently, the system slows down.
• Complexity. Paging is a complex and challenging system to implement and debug.
• Internal fragmentation. Paging increases internal fragmentation, as the last page of a process is not fully used, leading to wasted memory.
• Page table overhead: Paging requires page tables, which consume significant memory. Multilevel page tables and variable page sizes (super-pages) mitigate the issue.

Conclusion

After reading this text, you now understand how paging in operating systems works, and the advantages and disadvantages.

Next, learn how to check memory usage in Linux to monitor the system efficiently.