Page Table

Most OS allocate a page table for each process. A pointer to the page table is stored in the PCB of the process. When the dispatcher start a process, it must reload the user registers and define the correct hardware page table from the stored user page-table.

Hardware Page Table

The hardware page table can be implemented in many ways. The simplest form of page table can be build using high speed registers for better efficiency. The CPU dispatcher reloads these register-like other registers and instructions to modify the page-table registers are privileged, so only OS can change the memory map.

Example, DEC PDP-11

The address has 16-bit and page-size is 8 KB.

The use of registers is good for memory with small size such as 256 entries in page table. But, in modern computer the size of entries is 1 million cannot use fast registers.

Memory Page Tables

The page-table is kept in main memory and a page-table base register (PTBR) points to the page table. To change page-table entries, you only need to change the value of PTBR.

To access memory location i, we must index into the page-table, using the value in the PTBR, offset by page number for i. This provides us with a frame number and together with offset value gives us the physical address. Then we can access the memory.

This scheme requires two memory access for a byte, therefore, slowed the memory access by a factor of 2.

1. One memory access for the page-table entry
2. Another memory access for the byte.

The above approach is also slow.

The standard solution is to use a Translation Look-aside Buffer (TLB).

• The TLB is associative, high-speed memory.
• Each entry consist of two parts – a key or a tag and a value.
• When an item is presented, it is compared with all the keys. If a match is found, then the corresponding value is returned.
• Number of entries in TLB is small, usually between 64-1024.

TLB With Memory Page Table

The working of TLB is as follows:

• CPU generates the logical address.
• Its page number is presented to TLB.
• If page is found, obtain frame number
• Access the memory.
• If not page not found, it is called TLB miss, a memory reference to the page table must be made.
• When frame number obtained, use it to access memory.
• Add the page and frame number to the TLB, so next reference we can find it quickly.
• If the TLB is full, then OS must use one entry for replacement (using page replacement algorithm).

Other Features Of TLB

• Some entries are wired down(cannot be replaced). The TLB entries for kernel code are wired down.
• Some TLB store address-space identifiers (ASIDs) in each TLB entry. An ASID uniquely identify process and provide address space protection for that process.
• TLB tries to resolve a virtual page, if ASID of process and a virtual page does not match. It is a TLB miss.
• For several processes, if TLB does not support separate ASIDs, then flush or erase TLB for next executing process.
• Otherwise, TLB will refer to valid virtual addresses of previous process and refer to incorrect physical addresses.

The percentage of time a page is found in the TLB is called a hit ratio.

An 80% hit ratio means pages are found 80% of time. If it takes 20 nanoseconds to search TLB. If it takes 100 nanoseconds to access memory.
then,
It takes 120 nanoseconds for mapped-memory access when page is in TLB.

If the page is not found in TLB which takes 20 nanoseconds
It takes 100 nanoseconds to access the page-table in memory.
It takes 100 nanoseconds to access the byte from memory.

The total of 220 nanoseconds to access memory.

To find the effective memory access time, we weight the case by its probability:

\begin{aligned}
&Effective  \hspace{3px}memory  \hspace{3px}access  \hspace{3px}time = 80/100 * 120 + 20/100 * 220\\\\
&= 96 + 44 = 140  \hspace{3px}nanoseconds.
\end{aligned}

The slowdown is 40% (from 100 to 140 nanoseconds)

For 98% hit ratio,

\begin{aligned}&Effective \hspace{3px} access \hspace{3px} time = 98/100 * 120 + 2/100 * 220 \\\\&= 196 117.6 + 4.4 = 122 nanoseconds\end{aligned}

The increased hit ratio produces only 22 % slowdown.

Memory Protection in Paging

Memory protection in paged environment is accomplished by protection bit with each frame number. These bits are kept in the page-table. One bit can define page to be read-write or read-only.
When the page physical address is being computed, the protection bit is verified to prevent write on a read-only page. If such an attempt is made then it cause a hardware trap.

One additional bit is included with each entry, a valid-invalid bit by operating system. If the bit is set to valid, the page is in the process’s virtual address space. If bit is set to invalid, the page is not in virtual address space, resulting in a trap.

Suppose a 14-bit address space, with page size . The number of pages is

14 - 11 = 3 = \frac{2^{14}}{ 2^{11}}= 2^3= 8 \hspace{3px} pages

If the process is restricted to use only 0 to 10453, then all other addresses are set to invalid. The invalid address inside a page are unused and cause internal fragmentation.

page (10240 addresses) + 213 addresses. But the entire 6th page is considered as valid. This is internal fragmentation.