Paging in Operating Systems

In this tutorial, we will be covering the concept of Paging in the Operating System.

Paging permits the physical address space of a process to be non-contiguous. It is a fixed-size partitioning scheme. In the Paging technique, the secondary memory and main memory are divided into equal fixed-size partitions.

Paging solves the problem of fitting memory chunks of varying sizes onto the backing store and this problem is suffered by many memory management schemes.

Paging helps to avoid external fragmentation and the need for compaction.

Basic Method of Paging

The paging technique divides the physical memory(main memory) into fixed-size blocks that are known as Frames and also divide the logical memory(secondary memory) into blocks of the same size that are known as Pages.

This technique keeps the track of all the free frames.

The Frame has the same size as that of a Page. A frame is basically a place where a (logical) page can be (physically) placed.

Each process is mainly divided into parts where the size of each part is the same as the page size.

There is a possibility that the size of the last part may be less than the page size.

• Pages of a process are brought into the main memory only when there is a requirement otherwise they reside in the secondary storage.

• One page of a process is mainly stored in one of the frames of the memory. Also, the pages can be stored at different locations of the memory but always the main priority is to find contiguous frames.

Let us now cover the concept of translating a logical address into the physical address:

Translation of Logical Address into Physical Address

Before moving on further there are some important points to note:

• The CPU always generates a logical address.

• In order to access the main memory always a physical address is needed.

The logical address generated by CPU always consists of two parts:

1. Page Number(p)

2. Page Offset (d)

where,

Page Number is used to specify the specific page of the process from which the CPU wants to read the data. and it is also used as an index to the page table.

and Page offset is mainly used to specify the specific word on the page that the CPU wants to read.

Now let us understand what is Page Table?

Page Table in OS

The Page table mainly contains the base address of each page in the Physical memory. The base address is then combined with the page offset in order to define the physical memory address which is then sent to the memory unit.

Thus page table mainly provides the corresponding frame number (base address of the frame) where that page is stored in the main memory.

As we have told you above that the frame number is combined with the page offset and forms the required physical address.

So, The physical address consists of two parts:

1. Page offset(d)

2. Frame Number(f)

where,

The Frame number is used to indicate the specific frame where the required page is stored.

and Page Offset indicates the specific word that has to be read from that page.

The Page size (like the frame size) is defined with the help of hardware. It is important to note here that the size of the page is typically the power of 2 that varies between 512 bytes and 16 MB per page and it mainly depends on the architecture of the computer.

If the size of logical address space is 2 raised to the power m and page size is 2 raised to the power n addressing units then the high order m-n bits of logical address designates the page number and the n low-order bits designate the page offset.

The logical address is as follows:

where p indicates the index into the page table, and d indicates the displacement within the page.

The above diagram indicates the translation of the Logical address into the Physical address. The PTBR in the above diagram means page table base register and it basically holds the base address for the page table of the current process.

The PTBR is mainly a processor register and is managed by the operating system. Commonly, each process running on a processor needs its own logical address space.

But there is a problem with this approach and that is with the time required to access a user memory location. Suppose if we want to find the location i, we must first find the index into the page table by using the value in the PTBR offset by the page number for I. And this task requires memory access. It then provides us the frame number which is combined with the page offset in order to produce the actual address. After that, we can then access the desired place in the memory.

With the above scheme, two memory accesses are needed in order to access a byte( one for the page-table entry and one for byte). Thus memory access is slower by a factor of 2 and in most cases, this scheme slowed by a factor of 2.

Translation of look-aside buffer(TLB)

There is the standard solution for the above problem that is to use a special, small, and fast-lookup hardware cache that is commonly known as Translation of look-aside buffer(TLB).

• TLB is associative and high-speed memory.

• Each entry in the TLB mainly consists of two parts: a key(that is the tag) and a value.

• When associative memory is presented with an item, then the item is compared with all keys simultaneously. In case if the item is found then the corresponding value is returned.

• The search with TLB is fast though the hardware is expensive.

• The number of entries in the TLB is small and generally lies in between 64 and 1024.

TLB is used with Page Tables in the following ways:

The TLB contains only a few of the page-table entries. Whenever the logical address is generated by the CPU then its page number is presented to the TLB.

• If the page number is found, then its frame number is immediately available and is used in order to access the memory. The above whole task may take less than 10 percent longer than would if an unmapped memory reference were used.

• In case if the page number is not in the TLB (which is known as TLB miss), then a memory reference to the Page table must be made.

• When the frame number is obtained it can be used to access the memory. Additionally, page number and frame number is added to the TLB so that they will be found quickly on the next reference.

• In case if the TLB is already full of entries then the Operating system must select one for replacement.

• TLB allows some entries to be wired down, which means they cannot be removed from the TLB. Typically TLB entries for the kernel code are wired down.

Paging Hardware With TLB

Advantages of Paging

Given below are some advantages of the Paging technique in the operating system:

• Paging mainly allows to storage of parts of a single process in a non-contiguous fashion.

• With the help of Paging, the problem of external fragmentation is solved.

• Paging is one of the simplest algorithms for memory management.

Disadvantages of Paging

Disadvantages of the Paging technique are as follows:

• In Paging, sometimes the page table consumes more memory.

• Internal fragmentation is caused by this technique.

• There is an increase in time taken to fetch the instruction since now two memory accesses are required.

Paging Hardware

Every address generated by CPU mainly consists of two parts:

1. Page Number(p)

2. Page Offset (d)

where,

Page Number is used as an index into the page table that generally contains the base address of each page in the physical memory.

Page offset is combined with base address in order to define the physical memory address which is then sent to the memory unit.

If the size of logical address space is 2 raised to the power m and page size is 2 raised to the power n addressing units then the high order m-n bits of logical address designates the page number and the n low-order bits designate the page offset.

The logical address is as follows:

where p indicates the index into the page table, and d indicates the displacement within the page. The Page size is usually defined by the hardware. The size of the page is typically the power of 2 that varies between 512 bytes and 16 MB per page.

Now its time to cover an example of Paging:

Paging Example

In order to implement paging, one of the simplest methods is to implement the page table as a set of registers. As the size of registers is limited but the size of the page table is usually large thus page table is kept in the main memory.

There is no External fragmentation caused due to this scheme; Any frame that is free can be allocated to any process that needs it. But the internal fragmentation is still there.

• If any process requires n pages then at least n frames are required.

• The first page of the process is loaded into the first frame that is listed on the free-frame list, and then the frame number is put into the page table.

The frame table is a data structure that keeps the information of which frames are allocated or which frames are available and many more things. This table mainly has one entry for each physical page frame.

The Operating system maintains a copy of the page table for each process in the same way as it maintains the copy of the instruction counter and register contents. Also, this copy is used to translate logical addresses to physical addresses whenever the operating system maps a logical address to a physical address manually.

This copy is also used by the CPU dispatcher in order to define the hardware page table whenever a process is to be allocated to the CPU.