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.
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