Understanding Paging In Operating System In Detail

Memory management in operating systems involves allocating memory to processes, aiming to optimize usage and minimize fragmentation. Paging in operating system is an algorithmic approach that divides memory into fixed-size pages, eliminating the need for contiguous memory allocation. This strategy facilitates efficient memory management and allocation, enhancing data access speed.

Paging involves transferring data between primary and secondary storage, utilizing fixed-size units called pages to allocate memory to processes. It is a logical approach that improves overall system performance. Let's delve deeper into paging in operating systems.

What is Paging in OS?

Paging in operating system is a static memory allocation method that allows a process's physical address space to be of a non-contiguous type. It's a memory management scheme or storage mechanism that lets the operating system fetch processes from secondary memory in the form of pages and place them in the main memory. The paging hardware and operating system are integrated to implement the paging process.

A page is a logical memory unit in a program. Logical memory is organized into equal-sized pages or equal-sized blocks. A frame is a type of physical memory unit. In the concept of paging, physical memory (main memory) is organized into frames, which are equally sized memory blocks. The memory size of a new process is determined when it arrives. If a process has n pages in local memory, there must be n frames available in the system.

To get maximum utilization of the main memory and minimize external fragmentation, the size of a frame should be the same as the size of a page. Paging is mostly used to store non-contiguous portions of a single process. To make the paging method easier, the operating system decides:

The program's total page count.
Finds a sufficient number of empty page frames to assist.
All pages must be contiguous to be loaded into memory.

Characteristics of Paging in OS

Paging in OS has five key characteristics:

External fragmentation is not present.
By procedure, any frame may be employed.
Only on the last page of a process, internal fragmentation may occur.
A process's physical memory is no longer contiguous.
A process' logical memory is still contiguous.

Example of Paging

Here is an example. Let’s say the main memory size is 64B and the frame size is 4B then, the number of frames would be 64/4 = 16. There are 4 processes. The size of each process is 16B and the page size is also 4B then, the number of pages in each process = 16/4 = 4. These pages may be stored in the main memory frames in a non-contiguous form, depending on their availability.

Paging in OS: Page Table

Paging is a crucial memory management technique used by operating systems to efficiently manage memory allocation and address space. At the heart of paging lies the page table, a fundamental data structure that facilitates the mapping between virtual and physical memory addresses.

If we speak of paging in the operating system, the logical and physical memory addresses are separated. As a result, an address translation mechanism is required to convert the logical address into a physical address. The physical address is the actual address of the frame where each page will be placed, whereas the logical address space is the address created by the CPU for each page.

The CPU generates a logical address that is made up of two parts-

Page Number (p): Determines which page of the process the CPU wishes to read the data from.
Page Offset (d): Defines which word on the page the CPU wants to read.

When the CPU generates a page number, the page table displays the relevant frame number (frame base address) for each page in the main memory.

The required physical address is formed by multiplying the frame number by the page offset. The frame number identifies the frame in which the required page is stored. Page Offset provides the precise word from that page that must be read.

Every new process creates a separate page table (stored in physical memory). A page table entry contains a variety of page-related information. The information contained in the page table item differs from one operating system to another. PTE has the following information:

Frame Number: It is the most crucial piece of information in a page table entry. The frame number identifies the memory frames in the paging in which the page is stored. The size of the frame number is determined by the number of frames in the main memory.

The number of bits for frame = Size of Physical memory/Frame size.

Present/Absent Bit: This is also referred to as the valid/invalid bit. This bit indicates whether or not the page is in the main memory space. This bit is set to 0 if the page is not available in the main memory; otherwise, it is set to 1.
Protection bit: This bit is also known as the 'Read / Write bit.' This bit is about page security. It determines whether or not the user has permission to read and write to the page. This bit is set to 0 if only read operations are allowed and no writing operations are allowed. If both read and write operations are permitted, this bit will be set to 1.
Reference bit: The reference bit indicates whether or not the page was referred to in the previous clock cycle. If the page has recently been referenced, this bit is set to 1, otherwise, it is set to 0.
Caching Enabled/Disabled: The reference bit indicates whether or not the page was referred to in the previous clock cycle. If the page has recently been referenced, this bit is set to 1, otherwise, it is set to 0.
Dirty bit: This bit is also known as the "Modified bit." This bit indicates whether or not the page has been changed. This bit is set to 1 if the page has been updated; otherwise, it is set to 0.

Page Table Types

Following are the two most used Page Table types:

1. Single Level Page Table

Only single-page tables are used in this procedure. Page tables are made up of a linear array of page table entries (PTEs). Each PTE holds information on the page, such as its physical page number and status bits, such as whether the page is valid or not, as well as any other bits.

Every memory reference will have its address translated. The size of the page table might vary greatly depending on the page size. The loading of larger page tables takes longer.

Drawback of Single-Level Page Table: The main downside of this strategy is that managing these big page tables as a single entity is problematic. Because of the additional memory reference for the page table, mapping from virtual to physical address is delayed.

2. Multi-Level Page Table

A multilevel page table is split into two or more levels. Page tables are stored in multi-level tables, which have a tree-like structure.

The level-0 page table's entries are pointers to a level-1 page table.
The level-1 page table's entries are pointers to a level-2 page table.

Actual page information will be stored in the entries of the final level page table.

When paging is implemented on the page table in multilevel paging, the base address of the first-level page entry will be the base address of the second-level page table entry, and the second-level page table entry will be the base address of the third-level page table entry, and so on.

The frame number of actual pages will be displayed in the final level page table item. In multilevel paging, regardless of the level of paging, all the PT will be stored in the main memory and all PT entries carry simply the frame number.

Drawback of Multi-Level Page Table: All of the page tables are kept in memory. As a result, getting the physical address of the page frame needs more than one memory access, one for each level required. Extra memory references to access address translation can slow down a program in memory by a factor of two or more, which is a considerable drawback.

Paging with TLB (Translation Look-aside Buffer)

In a paging system, the virtual memory used by a process is divided into fixed-size blocks called pages. When a process accesses memory, the operating system translates the virtual memory address to a physical memory address using page tables. This translation process typically involves multiple memory accesses, which can introduce latency and reduce performance. Hence, to mitigate this overhead, a Translation Look-aside Buffer (TLB) is employed.

Paging with TLB (Translation Look-aside Buffer) is a memory management technique used in computer operating systems to improve the efficiency of memory access in a paging system. Every table entry is broken into two parts: one is the key, and the other is the value. When an object is introduced to the associative memory, it is compared to all keys at the same time. If there is a match, the value field for that match is returned.

In other words, the TLB is a small, high-speed cache that stores recently used virtual-to-physical address translations. When a process accesses memory, the TLB is consulted first to check if the required translation is already present. If the translation is found in the TLB (a TLB hit), the physical memory address is retrieved directly from the TLB, avoiding the need to access the slower main memory.

If the translation is not found in the TLB (a TLB miss), the operating system retrieves the translation from the page table in main memory and also updates the TLB with the new translation. Subsequent accesses to the same virtual memory address will then benefit from the faster TLB lookup.

By caching frequently used translations, the TLB significantly reduces the number of memory accesses required for address translation, thereby improving overall system performance. However, the size of the TLB is limited due to hardware constraints, so it may not be able to store all possible translations. TLB misses can occur when a translation is not found in the TLB, resulting in additional latency as the translation is fetched from main memory.

Overall, Paging with TLB is an effective strategy for optimizing memory access in paging systems, striking a balance between speed and hardware resources. Despite the high cost of the technology, the search mechanism that is enabled in this way is extremely quick. TLB typically stores a limited amount of entries, usually between 64 and 1024.

Advantages of Paging in OS

Here are some advantages of paging in operating systems:

Simplifies Memory Management: Paging simplifies memory management by breaking up physical memory into fixed-size blocks called pages and logical memory into fixed-size blocks called frames. This simplification makes it easier for the operating system to manage memory allocation and deal with memory fragmentation.
Allows for Efficient Memory Utilization: Paging allows for efficient memory utilization by allocating memory in smaller, fixed-size units (pages). This helps in reducing internal fragmentation, as memory can be allocated in smaller chunks, even if the requested memory size is not an exact multiple of the page size.
Enables Virtual Memory: Paging enables the concept of virtual memory, which allows processes to use more memory than physically available in the system. When physical memory becomes full, pages that are not currently needed can be swapped out to disk storage, freeing up physical memory for other processes. This helps in running larger programs or multiple programs simultaneously without running out of memory.
Facilitates Memory Protection: Paging facilitates memory protection by assigning each page a protection attribute (read-only, read-write, execute-only, etc.). This allows the operating system to enforce memory protection policies, preventing unauthorized access to memory and enhancing system security.
Supports Memory Sharing: Paging supports memory sharing between processes by allowing multiple processes to map the same physical page into their address spaces. This is useful for implementing shared memory communication between processes or for efficiently loading shared libraries into memory.
Improves Overall System Performance: Paging can improve overall system performance by reducing memory fragmentation, enabling efficient memory allocation and deallocation, and allowing for the effective utilization of virtual memory. This leads to better system responsiveness and the ability to handle a larger number of concurrent processes or larger memory-intensive applications.

Disadvantages of Paging in OS

While paging offers several advantages, it also comes with some disadvantages. Here are some of the drawbacks of paging in operating systems:

Increased Overhead: Paging introduces additional overhead in terms of memory management. The operating system needs to maintain data structures such as page tables to keep track of the mapping between logical and physical memory addresses. This overhead can impact system performance, especially in terms of memory access times.
Page Faults: Paging can lead to page faults, which occur when a process attempts to access a page that is not currently in physical memory. When a page fault occurs, the operating system needs to fetch the required page from secondary storage (such as a hard disk) into physical memory, which can result in a delay in process execution.
Fragmentation: Paging can lead to fragmentation of physical memory. External fragmentation occurs when free memory is fragmented into small, non-contiguous blocks, making it difficult to allocate contiguous memory blocks to processes. While paging reduces internal fragmentation, it may still suffer from external fragmentation, especially when pages are swapped in and out of memory frequently.
Increased Disk I/O: Paging involves swapping pages between physical memory and disk storage, which can result in increased disk I/O operations. This increased disk activity can lead to longer process execution times and decreased overall system performance, especially if the disk is a bottleneck in the system.
Limited Page Table Size: The size of the page table used to map logical addresses to physical addresses can become significant, especially in systems with large amounts of memory or large address spaces. Managing and accessing large page tables can consume system resources and introduce additional overhead.
Complexity of Memory Management: Paging introduces complexity to memory management, especially when combined with other chmemory management techniques such as segmentation. Managing page tables, handling page faults, and implementing page replacement algorithms can be complex tasks that require careful design and optimization.

Summing Up

Paging stands as a foundational memory management technique in modern operating systems, offering a balance between efficient memory utilization, virtual memory support, and memory protection. Despite its advantages, paging comes with its fair share of challenges. The overhead introduced by maintaining page tables and handling page faults, coupled with the potential for fragmentation and increased disk I/O operations, can impact system performance.

However, through careful design, optimization, and the implementation of efficient page replacement algorithms, many of these challenges can be mitigated. Paging remains a crucial component in the arsenal of memory management techniques, enabling operating systems to efficiently allocate and manage memory resources, support large address spaces, and facilitate the execution of diverse workloads.

As computing environments continue to evolve and memory requirements grow, paging will continue to play a vital role in shaping the performance and scalability of modern operating systems. With ongoing advancements in hardware and software technologies, the future of paging holds promise for further enhancements in memory management efficiency and system performance, ensuring that operating systems can continue to meet the demands of increasingly complex computing environments.

Frequently Asked Questions

Q1. Describe the paging technique.

Paging is a memory management employed by operating systems to organize memory and assign memory to processes. Processes are allotted memory in terms of pages. Pages are fixed-size blocks of memory used in paging. Paging includes transferring operations in the form of pages from the secondary storage into the primary memory.

Q2. What are the logical pages in paging?

In paging, logical pages are fixed-sized blocks of logical or secondary memory. Logical pages represent a unit of information transfer between main memory and secondary storage. The logical memory is divided into blocks of the same size called pages. When a process is about to run, its pages are loaded from the backup store into any free memory frames. The page table, which is utilized by the memory management unit to convert logical addresses into physical addresses, keeps the mapping between logical pages and physical page frames.

Q3. How does paging contribute to memory protection in a computer system?

Paging contributes to memory protection in a computer system in the following ways:

Protection bits: Through the association of protection bits with each page, paging enables memory protection and these bits identify the protection on the appropriate page and are linked to each item in the page table. The protection bits can be used to control access to pages and prevent unauthorized access to memory.
Valid/Invalid bit: The paging process should be protected by using the concept of insertion of an additional bit called Valid/Invalid bit. This bit is used to indicate whether a page is currently in memory or not. If the bit is set to valid, the page is in memory, and if it is set to invalid, the page is not in memory.
Easy-to-use memory management algorithm: External fragmentation is unnecessary because of the simple-to-use memory management mechanism of paging. It is a sensible idea and enables quicker access to data.

Q4. What is the role of a page table in the paging technique?

The page table serves as a vital data structure in the paging technique of memory management in operating systems. Its primary role is to map virtual memory addresses used by processes to corresponding physical memory addresses, facilitating efficient memory allocation, access control, and translation between logical and physical memory spaces.

Q5. When does a page fault occur, and what does it signify?

A page fault occurs when a process attempts to access a memory page that is not currently loaded in physical memory. It signifies that the required page needs to be fetched from secondary storage (e.g., disk) into physical memory before the process can continue execution.

You might also be interested in reading:

Shreeya Thakur

Sr. Associate Content Writer at Unstop

I am a biotechnologist-turned-content writer and try to add an element of science in my writings wherever possible. Apart from writing, I like to cook, read and travel.