17
$\begingroup$

Let's say we are working with a system that has 40 physical address bits. The total physical address space (assuming byte-addressable memory) is $2^{40}$ bytes, or 1 TiB. And if virtual addresses are 48 bits in length, that means there are more addresses available to virtual memory than there are locations in physical memory.

This makes sense to me, because the "excess" addresses could refer to hard disk locations as well. However, what I don't understand is how the translation between virtual and physical addresses occurs. I assume there is a mapping stored somewhere which links VAS locations to the physical locations. If there are more virtual address locations than physical locations, how can all of these mappings possibly be stored in memory? At minimum you would need 48 bits to store each virtual address, and then another 40 to store the physical location it maps to. So obviously you cannot just store a 1:1 mapping of each virtual address to its physical counterpart, as mapping every location would take more memory than physical memory itself.

What exactly am I missing here?

$\endgroup$
5
  • $\begingroup$ You can't do that even with a small amount of memory and address space. If you had 16-bit physical addresses and 16-bit virtual addresses you still wouldn't be able to store all of the 1:1 mappings! $\endgroup$
    – user253751
    Dec 4, 2017 at 2:00
  • 2
    $\begingroup$ The problem is more complex even than you are thinking. Computers rarely have TB of memory, so physical memory is WAY less than virtual address space. Worse again: Each process has it's entirely separate virtual address space! $\endgroup$ Dec 4, 2017 at 5:44
  • $\begingroup$ In addition to hard disk locations you just have bits/space to spare to waste. For example you can have large region below stack unmapped to prevent undetected overflows. You can randomize what you load where preventing another class of attacks. Want to denote by a single bit if address belongs to kernel or user - go ahead even though you are wasting half of space. While most textbooks concentrate on paging out aspect of virtual memory there is a lot more to it. $\endgroup$ Dec 4, 2017 at 8:18
  • $\begingroup$ (Also note that addresses may alias, which is sometimes useful, so VA A and address B refer to same PA P even though A != B.) $\endgroup$ Dec 4, 2017 at 8:18
  • $\begingroup$ Short answers: whole pages are mapped, not individual addresses. $\endgroup$
    – user16034
    Nov 23, 2022 at 9:27

2 Answers 2

28
$\begingroup$

The trick to making this work is "paging." When bringing data from a hard disk into physical memory, you don't just bring a few bytes. You bring an entire page. 4k bytes is a very common page size.

If you only need to keep track of pages, not each individual byte, the mapping becomes much cheaper. If you have a 48 bit address space and 4096 byte pages, you only need to track which of the 2^36 pages (roughly 69 billion pages). That's much easier! The record of where all of the pages are found is known as a "page table."

If you actually need 1-256 TiB of memory, then giving up a few gigabytes to store this page table isn't a big deal. In practice however, we'll do things like use multi-level page tables, which lets us be a bit more efficient, keeping pages only for regions of the address space that we are actually using.

$\endgroup$
4
  • 6
    $\begingroup$ A page file is a Windows term for an on-disk physical file containing the contents of physical page frames that were reclaimed for lack of memory, whose contents need to be kept. If I'm not mistaken, the data structure mapping virtual page addresses to physical page addresses should be called a page table. $\endgroup$
    – nanofarad
    Dec 4, 2017 at 0:34
  • $\begingroup$ @hexafraction I think you're right. I've made the change. $\endgroup$
    – Cort Ammon
    Dec 4, 2017 at 0:56
  • 2
    $\begingroup$ When actual memory is large, another way of reducing the memory needed for page tables is to allow for larger pages. x86 has an option to mix 4 KiB pages with 2/4 MiB pages. $\endgroup$ Dec 4, 2017 at 14:44
  • $\begingroup$ @NateEldredge: these terms are not specific to Windows but to OSes in general. $\endgroup$
    – user16034
    Nov 23, 2022 at 9:28
0
$\begingroup$

Your processor typically uses 8 bytes to store the information for 4,096 byte table. So 1 GB of page table could handle 512 GB of address space. Yes, there is a limit where it might be impossible to use all of the theoretically possible address space. But then many processors now have 64 bit of address space (256 billion billion bytes), so it is to be expected that you can't use all of it.

What is often possible is to have used logical address space that is at random places within that 64 bit space; this can be used to prevent attacks from hackers because they cannot know where in that huge logical space your data is. (So for example malloc might return addresses anywhere in the 64 bit space, but only for a total of say 64 GB of data).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.