Page Table Structure and Hardware Support:
Different operating systems have different methods for implementing page tables. Most allocate a page table per process. A pointer to page table of each process is maintained with all of the other register values associated with the process and stored in its PCB.
Reloading these register values and defining the correct hardware page table values from the stored process/user page table is part of a context-switch.
The actual implementation of the page table can be accomplished in several different ways. The simplest technique involves defining a dedicated set of registers to be used as the page table. Since every memory access requires going through the page table, these registers need very high-speed logic associated with them to make the address translation efficient. This register technique works reasonably well if the size of page table is relatively small.
Most modern systems allow extremely large page tables i.e. a million entries or more. r;6r such machines, the register implementation of the page table is not feasible primarily due to cost considerations. Instead of registers such machines keep the page table in main memory and use a page table base register (PTBR) to maintain a pointer to the page table. Changing page tables during a context switch requires changing only the value in this register rather than physically loading a large number of registers.
This approach has an inherent problem with the time that is required to access a logical memory address. To access logical address n, access must first be into the page table using the PTBR offset by the logical page number in which n is located. This requires a memory access. This access provides the physical frame number in which the logical page holding n is currently located. Then the memory access to this address occurs. This scheme requires two memory accesses for every logical address generated by the CPU. This doubles the time required to perform a physical memory access when the CPU generates a logical address. Such an increase in the time required to perform a memory access is not tolerable.
The standard solution to this problem is to use content-associative memory (CAM). It is also called content-addressable memory, associative registers or translation look-aside buffers (TLBs). CAM is built from extremely high-speed memory where each cell (these can be thought of as registers) consists of two parts: a key and a value.
When the CAM is presented with an item to match, that item is compared with all the keys simultaneously and if one of the cells keys matches with the item to be matched, its value component is output.
When used as a page table, the CAM is presented with an item to match that represents a logical page number. Each cell in the CAM represents one page table entry where the value part of the cell holds the physical frame number in which the logical page currently resides. This is the value, which is output by the cell. If the logical page number is found in the CAM, its frame number becomes immediately available and is used to access the physical memory. While this type of memory is quite expensive, it is also extremely fast. Typically a CAM used for such purposes contains between 8 and 2048 cells. If the page number is not in the CAM, then a memory reference to the page table (in memory) must be made. When the frame number is obtained from the physical memory then it can be used for the translation and performing the second memory access. This page number and frame number are added to the CAM so, that on the next request it will be in the CAM.
If the CAM is already full, the operating system must select a CAM entry for removal so that the one can be entered. Operating system will use a CAM entry replacement protocol for the basis of this decision. Each context-switch will require that the CAM be flushed to ensure that the next process does not use the translation information left behind by the process just switched out.
Each logical address request generated by the CPU whose translation information is in the CAM at the time of the request is called a CAM hit. The percentage of time that this occurs is called the CAM hit ratio. An 86% hit ratio means that 86% of the time the necessary translation information is in the CAM. For example, if it takes 15 nanoseconds to search the CAM and a memory access requires 100 nanoseconds, then the mapped memory access requires a total of 115 nanoseconds if there is a CAM hit. If there is a CAM miss on the logical address request, then the total time required will be 215 nanoseconds, since two memory accesses are required in addition to the CAM search time. Assume negligible time to add the new entry to the CAM - although in reality this time is not negligible. To find the effective memory access time (its like the average access rime under these conditions) each case must be multiplied by its probability, which gives:
Effective memory access time = (0.86 x 115) + (0.14 x 215) = 98.9 + 30.1 = 129
Thus, the effective memory access time is 129 nanoseconds that represent a 14% slow down approximately,
The hit ratio is related to the number of cells in the CAM. When the number of cells ranges between 16 and 512 a hit ratio of between 80%-98% can be achieved. Intel's 80486 chip uses 32 cells. Following diagram shows the address translation that occurs when using a CAM to speed-up page table look-up.
