Determine page table size for virtual memory

Question

Consider a virtual memory system with a 38-bit virtual byte address, 1KB pages and 512 MB of physical memory. What is the total size of the page table for each process on this machine, assuming that the valid, protection, dirty and use bits take a total of 4 bits, and that all the virtual pages are in use? (assume that disk addresses are not stored in the page table.)

Recuperative

2^28 entries because of virtual space size / page size. 4 Bytes per entry (28 bits to address vp numbers, + 4 bits = 32 bits) 2^28 * 4 = 1024 MB, which is larger than the physical memory. Does not make sense, I fail at school. This is my guess, not the real answer. Thanks in advance. – Recuperative

I don't see a requirement for all the page table to be in physical memory anywhere in the question. – Heavyset

Why would the physical memory be given and then state that there are no disk addresses stored in the table? This would imply that you only need to address the 512MB of physical memory.. Unless I'm wrong. Thanks again. – Recuperative

You don't need to store disk addresses in the page table if there's another way to get them. For example, say your swap file itself contains extra mapping of process-id/virtual-address to swap file location. You have to read the disk file anyway, may as well do two reads instead of one. Not an ideal solution but workable in a memory-constrained environment. – Heavyset

And your virtual table won't have 28 bits to address a VP number. The VP number is the key (array index), not the value). It needs only enough bits to refer to all the physical pages you want to use. At most, that's 512M/1024 entries (512K = 19 bits), assuming physical pages are on a 1K boundary. – Heavyset

Ah that makes more sense.. So then you would technically need 3 bytes for the PTE but would you round that to 4? So 2^19 * 4 = 2 MB. That would make a lot more sense – Recuperative

No, not quite, you still need 2^28 page table entries since that's your address space. But each entry takes up less space since it only has to address the 512K entries making up physical memory. Unfortunately, with 2^28 entries, 512M can only give you 2 bits per entry - that's less even than the accounting information let alone the physical addresses. So you should look into having the paging tables themselves being paged (a two-level VM system). – Heavyset

The main problem you have is a huge address space combined with a pitifully small page size :-) You should check the figures again and bear in mind that they may want you to simply calculate the page size regardless of whether it will fit in physical storage. Is there any more to the question than what you have shown? – Heavyset

No that is the entire prompt, which makes it somewhat confusing.. I appreciate your help by the way – Recuperative

We haven't started multi level VM systems, so I don't think that would be the solution.. Maybe the answer is simply not possible? – Recuperative

Answer 1

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 4 bytes (32 bits: only 23 are needed but we can round up for efficiency here), this will allow 8,388,608 pages for the secondary page table.

Since each of those secondary page table pages is 1K long (allowing us to store 256 secondary page table entries at 4 bytes each), we can address a total of 2,147,483,648 virtual pages.

This would allow 8,192 fully-loaded (i.e., using their entire 28-bit address space) processes to run side by side, assuming you have a fair chunk of disk space to store the non-resident pages.

Now obviously the primary paging table (and the VM subsystem, and probably a fair chunk of the rest of the OS) has to stay resident at all times. You cannot be allowed to page out one of the primary pages since you may well need that page in order to bring it back in :-)

But that's a resident cost of only 32M of the 512M for the primary paging table, much better than the (at a minimum, for one fully-loaded process) of 736M.

Heavyset

Thanks for the great response! One thing - unless I'm typing my math wrong, shouldn't 2^28 * 32 = 6,174,015,488 bits = 771,751,936 bytes = 738 MB? And yes, I'm pretty sure minimally you would see a 4KB page size implemented, perhaps even 8 or 16... – Recuperative

Yes, your calculation is correct but that's because you're using a 32-bit page entry whereas mine was 23-bit. In a real system, you would no doubt bump it up to at least 24 bits, and probably 32 as you have done, but that's why the figures are different. Whether you use 23 or 32 bits is up to you since the question only specified that at least 4 bits were required. If I was doing the assignment, I'd present multiple options with the reasons for each. But then I'd probably get marked down for being a smart-a*** :-) – Heavyset

Oops, that was a typo on my part. That is actually the calculation for 2^28 * 23 bits = 6174015488 or 736 MB.. – Recuperative

No worries - you've been incredibly helpful. You seem very knowledgeable on the subject. Thanks, once again! – Recuperative

I am studying for a final in my OS class and this was extremely helpful. Thanks a lot man. SO is the best! – Ingunna

Can someone please explain how we calculated that 8192(2**13) fully loaded process are allowed? – Tubulure

@cheems, total virtual address space is vm = (2,147,483,648 pages x 1024 bytes ) bytes, each process can only access pm = 2^28 bytes. so process number is vm/pm = 8192 – Valais

Answer 2

size of the page table= total no of page table entries*size of the page table entry

STEP 1:FINDING THE NO OF ENTRIES IN PAGE TABLE:

no of page table entries=virtual address space/page size

=2^38/2^10=2^28

so there are 2^28 entries in the page table

STEP2:NO OF FRAMES IN PHYSICAL MEMORY:

no of frames in the physical memory=(512*1024*1024)/(1*1024)=524288=2^19

so we need 19 bits and additional 4 bits for valid, protection, dirty and use bits totally 23 bits=2.875 bytes

size of the page table=(2^28)*2.875=771751936B=736MB

Bostick