HIERARCHICAL PAGE TABLE

Issue: When the physical address space for the page table cannot be allocated contiguously in main memory.

Solution: Split the page table into smaller pieces and then allocate it.

·        Divide a large virtual address space into many small pages, which can be independently swapped into and out of frames in physical memory.
·        To do so, need to keep a data structure (the page table) for each process mapping page numbers to frame numbers.
·        The simplest method is to put these into an array: the ith entry in the array gives the frame number in which the ith page is stored.
·        4MB of contiguous space per process is a lot. Moreover, if the process is only using a small part of its address space, we will only need to access a small part of the page table.
·        Just as with the address space, we can solve these problems by paging the page table itself. For convenience, we can make the pages of the page table (POPTs) the same size as the pages of the process's address space. This allows us to use the same set of frames to store either process data or POPTs.
·        In our example, each POPT holds 2^12 bytes / 4 bytes per entry = 2^10 entries. Since there are 2^20 total entries in the page table, there must be 2^10 POPTs.
·        Just like we needed a page table when we split up the address space into pages, we will need a second level page table to tell us where the POPTs are stored. In our example, this table must contain 2^10 entries (one for each POPT), each of which is 4 bytes (it contains a 20 bit frame pointer and additional VDRWX bits). Thus the total size of the top-level page table is 2^10 entries * 2^2 bytes per entry = 2^12 bytes = 4kb. This fits in one page, so there is no reason to split it further.
·        With different numbers, we could have a very large top-level page table. If so, we could repeat this process by paging the top-level page.
Finding data with hierarchical paging
·        To look up an address in a hierarchical paging scheme, we use the first 10 bits to index into the top level page table.
·        This tells us which POPT to use.
·        The next 10 bits tell us which entry on that POPT points to the data page we are interested in.

·        The remaining 12 bits gives us the offset into that page.

No comments:

Post a Comment