8.5 - Structure of the Page Table (p.373)
Nb. Vanaf dit punt wordt ik lui met samenvatten, want het is de avond voor het tentamen....
Hierachical Paging
- Pages in Pages, omdat anders de page table te groot wordt.
- Forward Mapped Page Table = Een meerdere lagen page table waarbij binaire address omzetting altijd werkt van de outerpage --> inner page --> offset.
Most modern computer systems support logical address spaces of 2^32 to 2^64. With a 2^32 address space and 4K ( 2^12 ) page sizes, this leave 2^20 entries in the page table. At 4 bytes per entry, this amounts to a 4 MB page table, which is too large to reasonably keep in contiguous memory. ( And to swap in and out of memory with each process switch. ) Note that with 4K pages, this would take 1024 pages just to hold the page table! One option is to use a two-tier paging system, i.e. to page the page table. For example, the 20 bits described above could be broken down into two 10-bit page numbers. The first identifies an entry in the outer page table, which identifies where in memory to find one page of an inner page table. The second 10 bits finds a specific entry in that inner page table, which in turn identifies a particular frame in physical memory. ( The remaining 12 bits of the 32 bit logical address are the offset within the 4K frame. )
Hashed Page Tables
- De hash is de virtual page number.
One common data structure for accessing data that is sparsely distributed over a broad range of possible values is with hash tables. Figure 8.16 below illustrates a hashed page table using chain-and-bucket hashing:
Inverted Page Tables
- Een regel in de tabel, is een echte page/frame in het geheugen.
Another approach is to use an inverted page table. Instead of a table listing all of the pages for a particular process, an inverted page table lists all of the pages currently loaded in memory, for all processes. ( I.e. there is one entry per frame instead of one entry per page. ) Access to an inverted page table can be slow, as it may be necessary to search the entire table in order to find the desired page ( or to discover that it is not there. ) Hashing the table can help speedup the search process. Inverted page tables prohibit the normal method of implementing shared memory, which is to map multiple logical pages to a common physical frame. ( Because each frame is now mapped to one and only one process. )