Question

Virtual Memory. When processes are allowed to grow larger than memory, page tables also grow very large. How could we organize page tables and TLB to keep access times as quick as possible for codes with good locality? For example, assume physical memory is 512K, each page is 1K, and a TLB of size 128. If we assume most processes are 256K or less, then we could allocate a fixed-size page table with 256 entries. Now in the unexpected case, where the page table grows larger than 256 entries, how should we organize it? What implications does your design have on average access time and on the maximum virtual memory size of a program?

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

The solution used on x86 is to have "sparse" page tables, that is there isn't a full table to contain a mapping for each page. Rather a two level mechanism is used:

The virtual memory is 4 GB large. A single page has size 4 KB. Using a one level approach would thus require a table of 4 GB / 4 KB = 1024 * 1024 entries. If an entry consumed 4 bytes, then every process would need 4 MB just to store its table.

Using a two level approach we have a page directory with 1024 entries, each of size 4 bytes (making it fit perfectly into a single 4 KB page). Thus each entry in that directory manages 4 GB / 1024 = 4 MB. If (and only if) there should be a mapping of some pages of virtual memory to physical memory in that 4 MB range, then the entry points to an instance of another structure, a page table. That contains 1024 entries, too, so each one manages 4 MB / 1024 = 4 KB exactly one page.

If there's a process that just needs a single page to operate, then using the single level approach we need 4 MB to store its virtual memory configuration. Using the two level mechanism described above, we need 4 KB for the page directory and 4 KB for the page table containing the mapping for that single page. Thus only 8 KB are used to store the virtual memory configuration.

If the process needs additional memory at runtime, and if that memory is at a (virtual) address not within the 4 MB range managed by its page table, then a second page table needs to be provided, increasing the memory used to store the mappings by another 4 KB.

Using this two level approach slightly increases access times for pages not in the TLB, because the memory management unit needs to access two memory locations (the page directory, and afterwards the respective page table) to be able to compute the physical address.

The TLB is unaffected by this: It stores mappings of single pages. How these mappings have been established isn't relevant to its operation.

Let's apply this to the example configuration you gave above: A singe page has 1 KB size. Most processes, as you said, will have 256 KB or less memory. But we want to be able to have processes using more virtual memory.

If we choose to have the last level handle a full 256 KB, then we have 256 KB / 1 KB = 256 entries. Assuming a 32 bit architecture, this in turn means we can have each entry with size of 4 byte (to hold an address). 256 entries * 4 Byte = 1 KB and thus a full page. Nice.

To be able to handle more virtual memory than 256 KB we add another layer. Because it's easy, we let this level use tables with 256 entries (a 4 byte), too, to make such a table exactly fit into a page.

This gives us a virtual memory of 256 * 256 KB (roughly 65 MB). An virtual address in that system would then be 26 bit long:

DDDDDDDDTTTTTTTTPPPPPPPPPP

D := Index to page directory, highest level.
     8 bit to be able to index 256 entries.
T := Index to page table, lower level.
     8 bit to be able to index 256 entries.
P := Offset inside page.
     10 bit to be able to address 1024 bytes.

A process using less than 256 KB needs then 2 KB to manage its memory configuration. Each additional 256 KB of virtual memory needed add another 1 KB of configuration memory.

Assuming the TLB can hold 128 entries (your question is a bit unclear here) it would need 128 * (16 + X - 10) bit, where X is the number of bits used to address physical memory. (Though this depends on the actual implemenation. I was thinking about16 bit per entry to store the indices of the paging structures + the upper bits of the physical address, not counting the 10 bits offset)

Kindly revert for any queries

Thanks.