FOR FREE MATERIALS

Translation Lookaside Buffer (TLB) 

Problem of paging and solution

Why we used paging:

1. To handing large size of processes or virtual address spaces.

2. To increase the degree of multiprogramming to reside more process in main memory.

3. To remove external fragmentation to save memory

So, the starting point of most optimizing techniques is that the page table in memory.

But what are the main disadvantages of paging:

1. Paging has its own memory overhead which is a page table i.e. required extra memory space to load page table in memory and generally page table size is very big.

2. With paging, at least one additional memory reference will be needed, to access the page table.

So, extra memory is required as well as extra memory references are used for the page table in paging.

To decrease the memory space due to the large page tables we can use another technique multi-level page table where we divide page table and load a portion of page table as per requirement.

But in multilevel paging memory reference will increase more and affected memory access time will be increased.

Without paging:

In the absence of paging, a certain instruction makes only one memory reference, to fetch the instruction.

Effective Memory Access Time (EMAT) = m (where m is the time taken to access instruction from main memory)

Single paging

With single paging, one additional memory reference will be needed, to access the page table.

EMAT = m + m (one memory access required for instruction or page and another memory access needed for page table)

Multi-level paging

When we use milt-level paging more than an additional memory reference is needed i.e. for each page table one memory reference is required.

Consider we have 4 multi-level paging.

EAT = m + 4 × m (one memory access is required for page and additional 4 memory access is needed for 4-page table) 

Importance of memory reference

Since execution speed is generally limited by the rate at which the CPU can get instructions and data out of the memory, having to make more than one memory reference per memory reference reduces performance by half. Under these conditions, no one would use paging.

Solution:

Computer designers have known about this problem for years and have come up with a solution. Their solution is based on the locality of reference which says that most of the programs tend to make a large memory of references to a small number of pages and it varies from time to time.

Thus only a fractional of the page table entries are heavily read; rests are barely used at all.

The solution that has been introduced is to equip computers with a small hardware device for mapping virtual addresses to physical addresses without going through the page table. This device, called TLB (Translation Lookaside Buffer) or sometimes an associative memory.

Note: To continue with address translation with TLB follows: Implementation of TLB