Determine page table size for virtual memory

Well, if the question is simply "what is the size of the page table?" irrespective of whether it will fit into physical memory, the answer can be calculated thus:

First physical memory. There are 512K pages of physical memory (512M / 1K). This requires 19 bits to represent each page. Add that to the 4 bits of accounting information and you get 23 bits.

Now virtual memory. With a 38-bit address space and a 10-bit (1K) page size, you need 2²⁸ entries in your page table.

Therefore 2²⁸ page table entries at 23 bits each is 6,174,015,488 bits or 736M.

That's the maximum size needed for a single-level VM subsystem for each process.

Now obviously that's not going to work if you only have 512M of physical RAM so you have a couple of options.

1. You can reduce the number of physical pages. For example, only allow half of the memory to be subject to paging, keeping the other half resident at all time. This will save one bit per entry, not really enough to make a difference.

2. Increase the page size, if possible. A 1K page on a 38-bit address space is the reason for the very chunky page tables. For example, I think the '386, with its 32-bit address space, uses 4K pages. That would result in a million page table entries, far less than the 260 million required here.

3. Go multi-level. A bit more advanced but it basically means that the page tables themselves are subject to paging. You have to keep the first level of page tables resident in physical memory but the second level can go in and out as needed. This will greatly reduce the physical requirements but at the cost of speed, since two levels of page faults may occur to get at an actual process page (one for the secondary paging tables then one for the process page).

Let's look a little closer at option 3.

If we allow 32M for the primary paging table and give each entry