Page table entries in Virtual Memory

Question

I have a simple question regarding page table entries. Suppose that we are given a 32 - bit Virtual address with 4 KiB page and a physical memory size of 2^28 bits.

Since the page offset is 12 bits, we would have 2^20 page table entries which would be mapped to 2^16 physical frames. But how is it possible for 2^20 entries to map to 2^16 entries. There would run out of physical frame addresses. Suppose that the process uses the full 2^20 pages, then assuming that the whole RAM consists of memory from only this process, all the 2^16 frames in the RAM would contain this processes memory. Am i right to say that 2^4 of the page table entries would show that it maps to disk ?

Also, if the process uses only one page table, then the remaining 2^20 - 1 page table entries would be invalid ?

Answer 1

There are a lot of assumptions in your question. To being with, you assume the page table entries are 32-bits. They could be 64 or even 128 bits.

You also assume that there are 20 bits available for indicating into page frames. Any real system is going to need some of those bits for control and protection purposes.

But how is it possible for 2^20 entries to map to 2^16 entries. There would run out of physical frame addresses.

That is the whole point of virtual memory system. Assuming you have 2^20 pages mapped to a process but only 2^16 physical pages, then not all of the process's pages are going to be mapped to page frames at the same time.

Am i right to say that 2^4 of the page table entries would show that it maps to disk ?

A rationally designed virtual memory system maintains a copy of all process pages on disk somewhere. The pages get copied from disk into memory ad mapped to the address space as needed.

Answer 2

But how is it possible for 2^20 entries to map to 2^16 entries. There would run out of physical frame addresses.

The important thing to understand about virtual memory is that it's "virtual" - it's an illusion that doesn't actually (physically) exist. This allows the OS to do various tricks, like:

• marking some/lots of virtual pages as "unused/not present" so that RAM isn't wasted when it's not needed (and so that programs get an error when they try to access something that doesn't exist - e.g. SIGSEGV signal).

• move pages between RAM and swap space to pretend that there's more RAM than there actually is. Note that this isn't limited to "swap space on disk" - e.g. it could be memory built into some kind of device (e.g. unused memory in a video card), memory that isn't in the current machine (e.g. using a network to store data in the RAM of a different computer) and it could be RAM in the same computer (e.g. if half the data can be compressed to half it's size, then "compression as swap space" would let you store 4 MiB of data in 3 MiB of RAM).

• pretend RAM was allocated by mapping the same page full of zeros everywhere, and then allocate it later (if and only if the page is written to); so that you can have a large area of zeros (e.g. a program's ".bss" section) that costs almost nothing (until/unless it's written to).

• pretend that a file is mapped/loaded into memory without allocating memory and without loading the file; and then allocating page/s and loading data into them if/when the data is accessed later, and also (to get more free RAM if the OS needs it for other things) freeing the memory if it wasn't modified (knowing that you can just get it from disk again later if it's accessed again later)

• mapping the same pages of RAM into multiple processes. For example, if you have 10 processes that are all executing the same executable file; then the executable file might be stored in RAM once and then mapped into the virtual file system's caches plus mapped into 10 different processes.

• "copy on write" tricks; where the same page of RAM is mapped into lots of processes (so any process can read from the page), and then if a process writes to the page the OS can allocate a new page and make a copy of the old page and replace the original (shared, read only) page with the new (not shared, writeable) copy.

If each virtual address space is 1 MiB, then you could have 100 processes (with 100 virtual address spaces and 1 GiB of total space) where the processes only use (on average) 512 KiB of virtual address space each, so that it looks like a total of 51200 KiB of virtual memory is being used; but the computer might only have 64 KiB of RAM where the remaining 51136 KiB of virtual memory is just trickery.