Paging - operating system tutorial

In contiguous memory allocation we resolved 2 major problems which were space allocation and conversion of logical address into physical address. We also discussed about internal and external fragmentation where we learnt that in contiguous memory allocation external fragmentation was a severe issue so we have to switch to non-contiguous memory allocation. So let's start Paging - operating system tutorial .

What is Paging?

In non-contiguous memory allocation we partition the secondary memory and main memory into several fixed sized partitions. Now we know that in fixed sized partitioning we have to suffer from internal fragmentation. But internal fragmentation is not a severe issue so we can ignore it.
The secondary memory is divided into equal sized partitions also know as pages. 
Same sized partitions are also maintained in main memory but they are called as frames. So if a frame is of 1 KB then a frame is also of size 1KB.
NOTE : If there are 3 contiguous pages in the secondary memory then it is not necessary that these pages will be continuous in the main memory as well. They may or maynot be contiguous and that's the beauty of non-contiguous allocation.

Address Translation

CPU will generate a logical address for secondary memory. But the process has been put into main memory so to access the process in the main memory we need a physical address. But to get physical address in non-contiguous memory allocation is a bit difficult because here the process can be present anywhere in the main memory.
So CPU generates a logical address for accessing the data from secondary memory. Now the logical address can be divided into 2 parts - 'P' which stands for page no. and 'd'  stands for instruction offset. To understand the meaning of 'P' and 'd' let say you have a story of 5000 lines. We have divided the story into 4 pages each page containing 1250 lines. Then I ask you to read the 1000th line in page 3. So here 'P' becomes 3 and 'd' becomes 1000.

But how are we going to know which page has to come first and which has to come last? Now consider the example below:

Now to know the location of each page we can use the base address of the first page and then the last line of the first page will contain a pointer to next page. So it works like a linked list. But there's a drawback with this method which is that the access time in case of linked list is worst if we have to access the nth node.
So we use another method which is called Page table. A page table is a data structure which has the same number of entries as the process is having in the secondary memory. Every Process has an independent page table. Each page entry in the page table contains the base address of each frame corresponding to the page.

Now when a logical address is generated by CPU we will check page number 'P' in the page table from where we get the frame number of that page. Now the instruction offset remains the same so we combine it with the frame number that we have obtained to get Physical Address.

Conclusion
CPu generates a logical address which contain 2 parts page no. 'P' and instruction offset 'd'. With the page no. 'P' we access the page table. We reach the page no. with the help of indexing which is present in page table. When we reach the correct page no. then we will get the frame no. where the page is currently stored in main memory. We combine the frame no. with the instruction offset. Instruction offset remains same. So when we combine the frame no with instruction offset we get the physical address.