Paging in Operating System (OS) | Core Computer Science

What is Paging?

Paging is a Memory Management technique that helps in retrieving the processes from the secondary memory in the form of pages. It eliminates the need for contagious allocation of memory to the processes. In paging, processes are divided into equal parts called pages, and main memory is also divided into equal parts and each part is called a frame.

Each page gets stored in one of the frames of the main memory whenever required. So, the size of a frame is equal to the size of a page. Pages of a process can be stored in the non-contagious locations in the main memory.

Why do we need Paging?

Let there is a process P1 of size 4 MB and there are two holes of size 2 MB each but are not contiguous. Despite having the total available space equal to 4 MB it is useless and can't be allocated to the process.

Paging helps in allocating memory to a process at different locations in the main memory. It reduces memory wastage and removes external fragmentation.

Conversion of Logical Address into Physical Address

The CPU always generates a Logical Address. But, the Physical Address is needed to access the main memory.

The Logical Address generated by the CPU has two parts:

1. Page Number(p) - It is the number of bits required to represent the pages in the Logical Address Space. It is used as an index in a page table that contains the base address of a page in the physical memory.
2. Page Offset(d) - It denotes the page size or the number of bits required to represent a word on a page. It is combined with the Page Number to get the Physical Address.

The Physical Address also consists of two parts:

1. Frame Number(f) - It is the number of bits required to represent a frame in the Physical Address Space. It is the location of the required page inside the Main Memory.
2. Frame Offset(d) - It is the page size or the number of bits required to represent a word in a frame. It is equal to the Page Offset.

Page Table

The Page Table contains the base address of each page inside the Physical Memory. It is then combined with Page Offset to get the actual address of the required data in the main memory.

The Page Number is used as the index of the Page Table which contains the base address which is the Frame Number. Page offset is then used to retrieve the required data from the main memory.

Example of Paging

If Logical Address = 2 bits, then Logical Address Space = 2² words and vice versa.

If Physical Address = 4 bits, then Physical Address Space = 2⁴ words and vice versa.

Now, consider an example :

Let Page Size = 1 bit, Logical Address = 2 bits, Physical Address= 4 bits.

Frame Size = Page Size = 2¹ = 2 Words. It means every page will contain 2 words.

Number of Pages = Logical Address Space / Page Size =2² / 2¹ = 2

Number of Frames =Physical Address Space/ Frame Size = 2⁴ / 2¹ = 8

Advantages of Paging

• It is one of the easiest Memory Management Algorithms.
• Paging helps in storing a process at non-contagious locations in the main memory.
• Paging removes the problem of External Fragmentation.

Disadvantages of Paging

• It may cause Internal Fragmentation.
• More Memory is consumed by the Page Tables.
• It faces a longer memory lookup time.