Question-1 Discuss the issues associated with paging and solution of it.
In any paging system, two major issues must be faced:
- The mapping from virtual address to physical address must be fast.
- If the virtual address space is large, the page table will be large.
The mapping from virtual address to physical address must be fast.
- In the absence of paging, to fetch an instruction requires only one memory reference.
- With paging, one more memory reference is required to access the page table.
- 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 two memory references per instruction reduce performance by half.
- Most programs access a small number of pages frequently.
- The solution that has been devised is to equip computers with a small hardware device for mapping virtual addresses to physical addresses without going through the page table.
If the virtual address space is large, the page table will be large.
There are two ways of dealing with very large virtual address spaces.
- Multilevel Page Tables
- The secret to the multilevel page table method is to avoid keeping all the page tables in memory all the time.
- In particular, those that are not needed should not be kept around.
- In Fig. 5-17(b) we see how the two-level page table works.
- On the left we see the top-level page table, with 1024 entries, corresponding to the 10-bit PT1 field.
- When a virtual address is presented to the MMU, it first extracts the PT1 field and uses this value as an index into the top-level page table.
- Each of these 1024 entries in the top-level page table represents 4M because the entire 4-gigabyte (i.e., 32-bit) virtual address space has been chopped into chunks of 4096 bytes.
- The entry located by indexing into the top-level page table yields the address or the page frame number of a second-level page table.
- Entry 0 of the top-level page table points to the page table for the program text, entry 1 points to the page table for the data, and entry 1023 points to the page table for the stack.
- The other (shaded) entries are not used. The PT2 field is now used as an index into the selected second-level page table to find the page frame number for the page itself.
- Inverted Page Tables
- An alternative to ever-increasing levels in a paging hierarchy is known as inverted page tables.
- In this design, there is one entry per page frame in real memory, rather than one entry per page of virtual address space.
- For example, with 64-bit virtual addresses, a 4-KB page size, and 4 GB of RAM, an inverted page table requires only 1,048,576 entries.
- The entry keeps track of which (process, virtual page) is located in the page frame.
- Although inverted page tables save lots of space, at least when the virtual address space is much larger than the physical memory, they have a serious down-side:
virtual-to-physical translation becomes much harder.
- The solution is to make use of the TLB.
- If the TLB can hold all of the heavily used pages, translation can happen just as fast as with regular page tables.
- On a TLB miss, however, the inverted page table has to be searched in software.
- One feasible way to accomplish this search is to have a hash table hashed on the virtual address.
- All the virtual pages currently in memory that have the same hash value are chained together, as shown in Fig. 5-18.
- If the hash table has as many slots as the machine has physical pages, the average chain will be only one entry long, greatly speeding up the mapping.
- Once the page frame number has been found, the new (virtual, physical) pair is entered into the TLB.