Paging in Operating System
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.
In Operating Systems, Paging is a storage mechanism used to retrieve processes from the secondary storage into the main memory in the form of pages.
The main idea behind the paging is to divide each process in the form of pages. The main memory will also be divided in the form of frames.
One page of the process is to be stored in one of the frames of the memory. The pages can be stored at the different locations of the memory but the priority is always to find the contiguous frames or holes.
Pages of the process are brought into the main memory only when they are required otherwise they reside in the secondary storage.
Different operating system defines different frame sizes. The sizes of each frame must be equal. Considering the fact that the pages are mapped to the frames in Paging, page size needs to be as same as frame size.
Example
Let us consider the main memory size 16 Kb and Frame size is 1 KB therefore the main memory will be divided into the collection of 16 frames of 1 KB each.
There are 4 processes in the system that is P1, P2, P3 and P4 of 4 KB each. Each process is divided into pages of 1 KB each so that one page can be stored in one frame.
Initially, all the frames are empty therefore pages of the processes will get stored in the contiguous way.
Frames, pages and the mapping between the two is shown in the image below.
Let us consider that, P2 and P4 are moved to waiting state after some time. Now, 8 frames become empty and therefore other pages can be loaded in that empty place. The process P5 of size 8 KB (8 pages) is waiting inside the ready queue.
Given the fact that, we have 8 non contiguous frames available in the memory and paging provides the flexibility of storing the process at the different places. Therefore, we can load the pages of process P5 in the place of P2 and P4.
Memory Management Unit
The purpose of Memory Management Unit (MMU) is to convert the logical address into the physical address. The logical address is the address generated by the CPU for every page while the physical address is the actual address of the frame where each page will be stored.
When a page is to be accessed by the CPU by using the logical address, the operating system needs to obtain the physical address to access that page physically.
The logical address has two parts.
- Page Number
- Offset
Memory management unit of OS needs to convert the page number to the frame number.
Example
Considering the above image, let's say that the CPU demands 10th word of 4th page of process P3. Since the page number 4 of process P1 gets stored at frame number 9 therefore the 10th word of 9th frame will be returned as the physical address.
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:
Page Number(p)
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:
Page offset(d)
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
