What is paging in OS?

In the world of operating systems, memory management plays a vital role in ensuring efficient utilization of a computer’s resources. One of the key techniques employed in memory management is paging. Paging is a memory management scheme that provides a way to break up physical memory into smaller fixed-sized blocks, known as frames, and logical memory into equally sized blocks called pages.

What is paging?

Paging is a memory management technique that aims to overcome the limitations of contiguous memory allocation. In traditional contiguous allocation, processes needed to be loaded into a continuous block of physical memory. However, this approach led to issues such as external fragmentation, which can waste memory space and hamper system performance. Paging addresses these issues by dividing physical and logical memory into fixed-sized units.

Example

Consider an example where the main memory has a capacity of 16 KB, with individual frames of size 1 KB each. This configuration results in the division of the main memory into a collection of 16 frames, each accommodating 1 KB of data.

In this context, there are four distinct processes: A1, A2, A3, and A4, each occupying 4 KB of memory. To facilitate efficient management, each of these processes is further divided into pages, with each page spanning 1 KB. This design allows the operating system to allocate a single frame for each page.

At the start of these processes, all frames within the memory are unoccupied. Consequently, the operating system has the opportunity to store the pages of these processes contiguously in the available frames.

In this case, think of A2 and A4 as taking a break for a while, leaving eight memory slots empty. This emptiness allows room for other pages to be placed there. Meanwhile, a new task called A5, which needs 8 pages (8 KB) of memory, is ready and waiting for its turn.

In this instance, notice that eight separate frames are free within the memory, and these frames are not connected to each other. Paging provides the advantage of placing a process in various locations across these frames. This flexibility enables us to load the pages of the A5 process.

How paging works

Paging involves two main components that are the page table and the page frame. The page table maintains a mapping between logical page numbers and physical frame numbers. The page frame is a fixed-sized portion of physical memory where a page can be loaded.

When a process needs to access memory, the logical address is divided into a page number and an offset within the page. The page number is used to index the page table, which retrieves the corresponding physical frame number. The offset is then combined with the frame number to form the physical memory address. This process is known as address translation.

Advantages of paging

Paging offers several advantages, including:

• Efficient use of memory: Paging enables more efficient use of memory by allowing processes to use non-contiguous physical memory locations.

• Simpler memory management: Managing memory becomes simpler as there is no need to find a contiguous block of memory for each process.

• Better virtual memory management: Paging is a cornerstone of virtual memory, allowing processes to use more memory than is physically available.

Disadvantages of paging

It also has some disadvantages, including:

• Internal fragmentation: Paging can lead to internal fragmentation, where partially filled pages result in wasted memory space.

• Memory overhead by page tables: Page tables consume additional memory, affecting overall memory utilization.

• Overhead in multi-level paging: Multi-level paging introduces extra memory access overhead for navigating page table hierarchies.

Address translation and page replacement

In the process of address translation, the page number from the logical address is used as an index to the page table, retrieving the corresponding frame number. However, if the requested page is not currently in memory, a situation known as a page fault occurs. Page faults trigger page replacement algorithms, which determine which page in memory should be replaced with the requested page from the secondary storage, such as a hard disk.

Various page replacement algorithms exist, each with its own approach to selecting the victim page for replacement. Common algorithms include the Least Recently Used (LRU), First-In-First-Out (FIFO), and Optimal algorithms.

To know more about page replacement algorithms, click here.

Page tables and multi-level paging

In systems with large amounts of memory, the page table can become quite large, leading to efficiency concerns. To address this, multi-level paging, also known as hierarchical paging, can be implemented. In this approach, the page table is divided into multiple levels, with each level further refining the page-to-frame mapping. This hierarchical structure reduces the memory overhead required for storing the page table, as not all possible mappings need to be represented.

Conclusion

Paging is an important memory management technique that revolutionized how operating systems handle memory allocation. By breaking memory into fixed-sized blocks and introducing the concept of the page table, paging overcomes the limitations of contiguous allocation, reduces fragmentation, and enhances memory utilization.