What Is Paging In Operating System?

Unstop
9 min readApr 30, 2022

Table of content:

  • Characteristics of Paging
  • Address Translation
  • Page Table (PT)
  • Paging with TLB
  • Advantages of Paging
  • Disadvantages of Paging

In Operating System, memory management is the responsibility of dividing the memory among the various processes. The fundamental goal of memory management is to make optimal use of memory by minimizing internal and external fragmentation. One such algorithm for memory management techniques is paging.

Paging is a static memory allocation method that allows a process’s physical address space to be of non-contiguous type. It’s a memory management scheme or storage mechanism that lets the operating system fetch processes from secondary storage 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 pages, which are equally 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.

ALSO READ

5 Books That Will Come Handy In Your Coding Journey!

Characteristics of Paging

  • 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’ s logical memory is still contiguous.

Example of Paging

For example, Let’s say the main memory size is 64B and the frame size is 4B then, No of frames = 64/4 = 16.

There are 4 processes. The size of each process is 16B and page size is also 4B then, No 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

Address Translation

In paging, 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 Memory Management Unit (MMU), which is a hardware component, performs the mapping from virtual to a physical address, which is known as the paging technique. The page table base register (PTBR) refers to a process’s page table. A virtual memory processor must have a page table base register that is accessible by the operating system.

The size of the page table is indicated by the page table length register. The page table is used to translate the logical address to the physical address. At runtime, memory address translation occurs. Translating a virtual address to a physical address is required when reading a word from memory.

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

  • Page Number (p)
  • Page Offset (d)

The physical address is separated into two parts.

  • Frame Number (f)
  • Frame Offset (d)

The page number determines which page of the process the CPU wishes to read data from. The Page Offset 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.

ALSO READ

5 Interesting Coding Projects That’ll Make Your Resume Stand Out!

Page Table (PT)

Every new process creates a separate page table. Page table is stored in physical memory.

Page Table Entry

A page table entry contains a variety of page-related information. From operating system to operating system, the information contained in the page table item differs. The frame number is the most crucial piece of information in a page table entry.

PTE has the following information:

  • Frame Number: The frame number identifies the memory frames in paging in which the page is stored. The size of the frame number is determined by the number of frames in the main memory. Number of bits for frame = Size of Physical memory/Frame size.
  • Present/Absent Bit: This bit 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.

The following method may be used to create a page table:

  • In the main memory, a single-level page table is stored.
  • Main Memory stores a multi-level page table.
  • Single or multilevel page tables, associative memory (Register or TLB), and associative memory (Register or TLB).
  • Page table that is inverted.

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.

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, the mapping from virtual to physical address is delayed.

Multi-Level Page Table

Multilevel page table are 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.

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)

To access a byte in paging, the first-page table item must be visited, followed by the bytes.
As a result, two memory accesses will be required. Memory access is slowed by a factor of two as a result. In most cases, this delay would be intolerable.

The above issue can be remedied by employing a fast-searching hardware cache called a translation look-aside buffer. The TLB is a type of associative fast memory.

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.

Despite the high cost of the technology, the searching mechanism that is enabled in this way is extremely quick. TLB typically stores a limited amount of entries, usually between 64 and 1024.

ALSO READ

Acing Hackathons & Coding Competitions In 2022: Ten Programming Languages To Learn

Advantages of Paging

  • Memory management that is effective.
  • Simplicity in partitioning (non-contiguous memory allocation).
  • Allocating memory is simple and inexpensive.
  • Pages are simple to share.
  • No compaction is necessary.
  • no external fragmentation.
  • more efficient swapping.

Disadvantages of Paging

  • Internal fragmentation (only at the last page of the process).
  • Address translation necessitates the use of specialized hardware.
  • The page table is stored in the main memory.
  • Address translation lengthens memory cycle times.
  • Memory reference overhead is caused by multi-level paging.
  • Memory access time is longer.

Paging allows you to save a process in memory in a non-contiguous manner and it is invisible to programmers. Although paging is a storage strategy that allows the operating system to retrieve processes from secondary storage into main memory in the form of pages, it might result in internal fragmentation.

You might also be interested in reading:

  1. 10 Best React Projects Ideas You Must Build in 2022
  2. Difference Between Hardware and Software
  3. 10 Most Important Programming Language for AI
  4. Difference Between JavaScript And jQuery

--

--

Unstop

Unstop (formerly Dare2Compete) enables companies to engage with candidates in the most interactive way to discover, assess, and hire the best talent.