Paging in OS - Scaler Topics (2024)

Overview

Paging in OS helps in retrieving the processes from the secondary memory into the main memory in the form of pages. It divides a process in the form of pages stored in the secondary memory, and also, the main memory is divided in the form of frames. Each page of the process is allocated to exactly one frame of the memory.The main advantage of Paging is that the pages can be stored at different locations of the memory and not necessarily in a contiguous manner.

What is Paging in Operating System?

Paging is a technique that divides memory into fixed-sized blocks. The main memory is divided into blocks known as Frames and the logical memory is divided into blocks known as Pages. Paging requires extra time for the address conversion, so we use a special hardware cache memory known as TLB.This concept of Paging in OS includes dividing each process in the form of pages of equal size and also, the main memory is divided in the form of frames of fixed size. Now, each page of the process when retrieved into the main memory, is stored in one frame of the memory, and hence, it is also important to have the pages and frames of equal size for mapping and maximum utilization of the memory. Its main advantage is that the pages can be stored at different locations of the memory and not necessarily in a contiguous manner, though priority is always set to firstly find the contiguous frames for allocating the pages.

If a process has n pages in the secondary memory then there must be n frames available in the main memory for mapping.

Example to understand Paging in OS

CASE-1 (Contiguous Allocation of Pages)

As we can see in the above image, we have main memory divided into 16 frames of the size of 1KB each. Also, there are 4 processes available in the secondary (local) memory: P1, P2, P3, and P4 of a size of 4KB each. Clearly, each process needs to be further subdivided into pages of size of 1KB each, so that one page can be easily mapped to one frame of the main memory. This divides each process into 4 pages and the total for 4 processes gives 16 pages of 1KB each. Initially, all the frames were empty and therefore, pages will be allocated here in a contiguous manner.

CASE-2 (Non-Contiguous Allocation of Pages)

Basic Method of Paging in Operating System

As we have already discussed above, the basic method of paging includes dividing the main memory into fixed-size frames and the logical memory into fixed-size pages. Basically, a free-frame list is maintained for each process and according to the availability, the page is allocated to the first free frame from the list. Pages of a process are retrieved into the main memory only when there is a requirement otherwise, they are stored in the secondary (local) memory.

Page Table in Operating System (Address Translation)

There are two types of memory addresses used in the process of paging: Logical and Physical memory addresses and they both are separate. The physical address is the actual address of the frame where each page will be allocated, whereas the logical address is the address created by the CPU for each page in the secondary memory. Now to convert this logical address into a physical address, we need a mechanism known as address translation accomplished by the page table.

The logical address generated by the CPU in the secondary memory consists of two parts:1. Page Number [p] -> It acts as an index of a page of each process and denotes the specific page from which the CPU wants to read & process the data.

2. Page Offset [d] -> It denotes the specific word on the page that the CPU wants to read and process. As we can see in the below image, we have physical address: 4 as frame number and 4 as offset. This clearly shows that from the frame number 4, CPU wants to read and access the data identified as 4.

The physical address in the main memory consists of two parts:1. Frame Number [f] -> It identifies the frame in which the required page will be stored.

2. Frame Offset [d] -> It denotes the specific word on the page that has to be read and processed.

Each process of the secondary memory in OS creates its own page table which is to be stored in the physical (main) memory. Page table in OS mainly provides us with the frame number (base address of the frame) along with the offset which when combined, forms the physical address.The size of the page table is indicated by the page table length register (PTLR).

Note: If the total size of the logical address given is 2 raised to the power m while the given page size is 2 raised to the power n, then the (m-n) bits of the logical address specify the page number and the n bits specify the page offset.

Diagram Illustration (Translation of the Logical Address into the Physical Address)

As we can observe in the above diagram, it shows the translation of the logical address into the physical address. We know that each process has its own page table in the local memory and for that, PTBR (Page Table Base Register) holds the base address for the page table of the current process.

In the above approach, if we need to find the location of some element (say f), then we first have to find the index number of the page in the page table by using the value in the PTBR offset for f. It then provides us with the frame number combined along with the offset to produce the physical address. This physical address will be the desired location in the main memory where element f is present inside a specific frame. Now with this, we need to access memory two times (for page table entry to find the index and for actual element in the main memory) and it is thus, a slower process.

Translation of Look-Aside Buffer(TLB)

Now as we have seen above the problem of slow memory access to find an element byte, there is an alternative solution to this problem, and we can use a fast look-up hardware cache known as Translation of look-aside buffer (TLB). The properties of TLB are as follows:

TLB is associative and high-speed cache memory.
There is a small number of entries present in the TLB at a time (between 64 and 1024 entries).
The hardware cost is expensive though but the searching and memory access through TLB is very fast.
Each entry in the TLB consists of two parts: a key and a value, similar to a map in C++ or Java.
Generally when the associative memory is present along with an item, then the item is compared with all the keys in the TLB. In this case, if the item is found, then the corresponding value is returned which is the frame number address location of the item.

Paging with TLB

TLB is used with the page tables in the following ways:

Whenever the logical address is generated by the CPU, its page number is stored in the TLB as a reference entry.
If the page number is present in the TLB and is found upon searching, then its corresponding frame number is also available for accessing the memory.
If the page number is not found within the TLB entries, then this situation is known as TLB miss. In this case, memory reference to the page table must be made.
There is a point to be noted that the page number and the frame number are always added together in the TLB so that we can easily locate an element within the main memory with fast-speed access time upon reference.
When TLB gets full of the entries inside it, then the operating system selects one of the entries for replacement with the new entry.

Characteristics of Paging in Operating System

External fragmentation happens when a dynamic memory allocation method allocates some memory but leaves a small amount of memory unusable. External fragmentation is not present during the paging process because the pages can be stored at the different locations of the memory and not necessarily in a contiguous manner and hence, memory is not wasted.
All the frames and pages are of equal and fixed size and thus, any frame may be employed to allocate a specific page of the process.
When a process is allocated to a memory block, and if the process is smaller than the amount of memory requested or available, then a free space is created in the given memory block. This is known as internal fragmentation. During paging, internal fragmentation may occur during the allocation of the last page of the process.
Physical memory of a process is not necessarily contiguous but the logical memory for a process is always contiguous.

Advantages of Paging in OS

The advantages of Paging in OS are as follows:

It is a memory management technique as we can store the pages of a single process in a non-contiguous manner as well which saves the memory.
The problem of external fragmentation is solved with the help of the Paging technique.
Allocating the pages within equal and fixed-size frames is easy and simple. Swapping is also easy between the pages and the page frames.

Disadvantages of Paging in OS

The disadvantages of Paging in OS are as follows:

Internal Fragmentation may occur especially during the allocation of the last page of the process.
Page tables that are separate for each process in the secondary memory may consume extra memory.
If we are not using TLB (Translation of look-aside buffer), then the time taken to fetch an instruction and the element byte is high because we need to access the memory two times (for page entry and for actual element within the frame).
Address translation of logical to physical address lengthens the memory cycle times. Also, it needs specialized hardware.
Though memory access time can be improved by using TLB, but again there is a limited size of page entries within the TLB up to 1024.

Example of Paging in OS

There is always a copy of the page table maintained by OS for each process which may be later used to translate the logical address into a physical address.

We know that if a process is divided into n pages, then it requires at least n frames, and also, any free frame can be allocated to any process that needs it.As we can see in the above example, a process is divided into 4 pages in the local memory of 1KB size each. There is a point to be noted that the first page of the process is always loaded into the first frame that is listed on the free-frame list. After that the page table is also maintained alongside which contains the corresponding frame number as the destination address for each page of the process. Here, page 1 is allocated to the frame 2 which must be the first free frame available in the list, and similarly, pages 2,3, and 4 are allocated to frames 5,3, and 8 respectively.

Basically, frame table is a type of data structure that maintains the information of which frames are available and which frames are already allocated and this gives us a free-frame list. In the above image, we can observe that a process has 4 pages but there are 5 frames available in the free-frame list (5,8,2,9, and 11). Clearly, the pages: P1, P2, P3, and P4 will be allocated frames: 5,8,2, and 9 respectively and at the same time, the page table will be maintained consisting of corresponding frame numbers for each page of the process. At the end, the free-frame list will only contain the frame number 11.

Conclusion

Paging in OS helps in retrieving the processes from the secondary memory into the main memory in the form of pages as when required by the users.
Paging divides a process in the form of pages stored in the secondary memory and also, the main memory is divided in the form of frames.
The main advantage of Paging is that the pages can be stored at the different locations of the memory and not necessarily in a contiguous manner which avoids memory wastage.
Address translation is a mechanism that converts a logical address generated by the CPU in the secondary memory into a physical address which is required to access and search an element inside a frame in the main memory.
Page table in OS mainly provides us with the frame number (base address of the frame) along with the offset which when combined, forms the physical address.
TLB (Translation of look-aside buffer) is associative and a high-speed cache memory.
If the page number is not found within the TLB entries, then this situation is known as TLB miss. In this case, a memory reference to the page table must be made.
Paging avoids external fragmentation but internal fragmentation may occur in OS.