Understanding Virtual Address, Virtual Memory and Paging

Question

I've been learning these topics and read many articles and books but they all lack some complementary information and confused me even more. So here, I’d like to explain what I know while I am asking my questions. Hopefully, this topic will be useful for many like me. I'd also like to learn validity of my knowledge and corrections if necessary.

Virtual Memory

Some articles say “Virtual Memory is some space of Hard Disk which emulates Physical Memory so that we can have more memory than we actually have.”. Some other articles say “Virtual Memory is the combination of Physical Memory (RAM), a section of hard disk which acts like Physical Memory and Page Tables.” However they are different things and I don’t understand why there are different explanations like that.

Let’s go with the second explanation since it is also how Wikipedia describes Virtual Memory as well. At this point Virtual Address makes sense since we use address at Virtual Memory instead of physical memory directly.

By the way, my Mac says I have 8GB physical memory and 8GB virtual memory. In this case does VM include Physical Memory or it is the amount of space in HD used as memory? Do I have 16GB memory available for my programs?

Question 1:

Intel i5 has 36 bit address bus and this means you can address 64GB memory. Let’s say I installed 4GB RAM to my computer. However, my programs may not be aware of the size of the memory installed as it will be used on many different systems with different sizes of memory. This is where Virtual Memory becomes handy. It abstracts away the actual size of the memory installed.

However, what happens when my programs want to access memory address 0xFFFFFFFFF? I do only have 4GB installed and perhaps some memory space in HD.

I have two theory for this question:

1. Since page tables are maintained by OS, the OS decodes that address and finds out which page that is and checks that page in the page table to see whether they have a physical address associated with it (valid and invalid flags), if yes then goes to physical address the page entry points at in the physical memory + offset defined in the virtual address and brings that value. Otherwise a page fault happens and OS looks for that page in the secondary storage, fetches it and puts it in memory and updates page table.

2. It throws a OutOfMemory type of exception which says I don’t have any memory which the given address can address.

The disadvantage of the first theory is that what happens when a program wants to use 64GB memory? Then we need to have 60GB memory space in HD since we only have 4GB. However, in the screen shot below MAC tells me that there is only 8GB Virtual Memory.

Question 2:

How processes are put in Virtual Memory? I mean does each process has 0x0 - 0xFFFFFFFFF virtual memory space available for them or there is only one Virtual Memory address space where all the process are placed?

If each process assumes that they have all the memory available for them, then the memories look like following:

If there is only one Virtual Memory concept, then it would look like this:

Page Table

So page table is a data structure which sits between physical addresses and virtual addresses. It is an associative array (or like a dictionary) which for each page (key), there is a physical address associated (value).

OS uses MMU (Memory Management Unit) to perform this translation from virtual address to physical address.

Question 3:

Is there one big giant page table which includes all the pages for every process or each process has its own page table?

Paging

Paging is a memory management method. Virtual Memory and Physical memory get divided into pages (which are fixed and same size blocks) by Memory Management Unit. This technique is useful when you swap pages between memory and secondary storage so that you can swap pages between them. Your program for instance requests a data located in an address. However, that address your program is using is a virtual address and MMU translates it using page table. During this, MMU checks page table whether the requested is present in page table and OS gets it from secondary storage if not and updates the page table.

Question 4:

Let’s say a process requests the data from an address which is converted to a physical address which has some data already. How is it known that data does not belong to the requester processes and should be replaced with the one that is in secondary storage?

There is dirty bit for example which is used whether to write that page back to hard disk or not but I don’t think it is what determines the owner process.

Recapitulate

Answer 1

Some people use the term "Virtual memory" as if it were synonymous with the Page File, since the Page File represents the part of your allocated memory that is not "real" memory (i.e. RAM). But most people consider "Virtual Memory" to be the entire abstraction layer that the Operating System gives to programs, which combines the RAM and the Page File.

I'm not sure which of these definitions is favored by Mac OS, though it seems unlikely that your computer would not have any paged memory allocated, so I'm guessing that it probably is adding 8GB of paged memory to your 8GB of actual RAM, for a total of 16GB of available (virtual) memory.

Remember that because the Operating System manages memory allocation and deallocation requests, it is free to do just about whatever it wants. My understanding is that most operating systems have different memory allocation tables for each process, so they could literally give the same virtual memory address to multiple programs, but those memory addresses would map to different actual blocks in memory. So a 64-bit operating system can allocate the maximum amount of 32-bit addresses to multiple 32-bit programs--they're not all limited to the same 32-bit memory addresses.

However, there are limits: the operating system can have limits set to the size that the page file is allowed to grow to. So unless you've deliberately told your Operating System to do so, it will probably not have 64 GB of total Virtual Memory. And even if it did, it can't allocate all 64 GB to every program, so you'd most likely have an OutOfMemory error before the OS allocates a virtual address at 0xFFFFFFFFF to your program. (In fact, I wouldn't be surprised to learn that 0xFFFFFFFFF is actually a reserved error-code location, similar to 0x0.) But since the addresses that your program knows about have no correlation to true memory addresses, there's a possibility that you'd end up being allocated a memory address that your program thinks of as 0xFFFFFFFFF, even if the operating system isn't using anywhere near that much memory.

Is there one big giant page table which includes all the pages for every process or each process has its own page table?

Likely both... and then some.

1. Each process has its private memory table, and the OS will actively prevent your program from accessing a memory address that hasn't been allocated to this table.
2. There's also such a thing as Shared Memory, so two processes which need to use the same information can create an area of shared memory and have addresses in that memory space be accessible by both.
3. The Operating System itself obviously needs to have some way to track how much overall memory is available, which address spaces are free/used, and which virtual memory blocks have been allocated to which locations in RAM or in the page file.

So, supposing a process has been allocated memory at address 0x00000002, when it goes to load the value out of that memory address, the operating system might recognize that this actually maps to the real memory address 0x00000F23, and that is the memory address whose value will actually be fetched into the CPU register. Or, it could realize that it has moved the page containing that address onto the disk somewhere, in which case the operating system will find an empty part of memory and load the page's data from the disk into that memory first. (Again, this memory address doesn't have any correlation with the original memory address that the program requested.)

If there isn't any empty memory to pull the page from, the OS will first have to move some data out of memory and into the page file. It tries to intelligently determine which memory is least likely to be used in the near future. But sometimes you end up with memory constantly getting requested shortly after it gets swapped to the disk, only to replace the next piece of memory that a program was about to request. This "thrashing" is what causes computers with insufficient memory to go really, really slow, since disk accesses are orders of magnitude slower than memory accesses.

Affusion

This was a really nice explanation! Thanks. A quick question, let's say there is not much space for new memory allocations in the physical memory, in this case there should be some pages swapped back to secondary storage. During this process, the pages that are swapped may belong to some other process (I guess). So does OS find that process's page table and update the entries of those pages as invalid as well for the new allocation for some other process? – Recapitulate

@Tarik: Yes, any time data is swapped, the appropriate page tables get updated. And when the data is requested by that other process, it'll get swapped back into memory (most likely a different place than where it was before), and the page table will be updated again. – Affusion

Your specific example (0x2 to 0xF23) suggests that VM maps every byte address, rather than dealing in pages. Clearly, it would be ridiculous to use two 64-bit (really only 48, but still) addresses to map every byte rather than two 36-bit page addresses for every 4kB (or 1MiB) page. I'm also pretty certain that VM addresses this low are forbidden/reserved. – Hexastyle

@Emmet: Yes, thanks for pointing that out. I did sort of glaze over the whole page/offset aspect, which I think your answer was better at explaining. – Affusion

Answer 2

Before I answer your questions (I hope I do), here are a few introductory remarks:

Remarks

The problem here is that “virtual memory” has two senses. “Virtual memory” as a technical term used by low-level programmers has (almost) nothing to do with “virtual memory” as explained to consumers.

In the technical sense, “virtual memory” is a memory management system whereby every process has its own virtual address space, and memory addresses in that address space are mapped to physical memory addresses by the OS kernel with hardware support (uses terms like TLB, multi-level page tables, page faults and walks, etc.). This is the sense of VM that you are interested in (described below).

In the non-technical sense, “virtual memory” is disk space used in lieu of RAM (uses terms like swap, backing store, etc.). This is the sense of VM that you're not particularly interested in, but it seems that you've seen some material that deals primarily with this sense of the term or muddles the two.

Question 1

what happens when my programs want to access memory address 0xFFFFFFFFF? I do only have 4GB

In this case, your “Theory 1” is closer.

VM decouples the addresses that your program “sees” and works with — virtual addresses — from physical addresses. Your 4GiB of memory may be at physical addresses from 0x0 to 0xFFFFFFFF (8 F's), but the address 0xFFFFFFFFF (9 F's) is in the user-space (in canonical layout) of virtual addresses. Provided that 0xFFFFFFFFF is in a block allocated to the process, the CPU and kernel (in concert) will translate the page address 0xFFFFFF000 (assuming a 4k page, we just hack off the lower 12 bits) to a real physical page, which could have (almost) any physical base address. Suppose the physical address of that page is 0xeac000 (a relationship established when the kernel gave you the virtual page 0xFFFFFF000), then the byte at virtual address 0xFFFFFFFFF is at physical address 0x00eacfff.

When you dereference 0xFFFFFFFFF (assuming 4k pages), the kernel “asks” the CPU to access that virtual address, and the CPU chops off the lower 12 bits, and looks up the page in the dTLB (translation lookaside buffers are virtual-to-physical page-mapping caches; there's at least one for data and one for instructions). If there's a hit, the CPU constructs the real physical address and fetches the value. If there's a TLB miss, the CPU raises a page fault, which causes the kernel to consult (or “walk”) the page tables to determine the right physical page, and “returns” that value to the CPU, which caches it in the dTLB (it's highly likely to be reused almost immediately). The kernel then asks the CPU for that address again and this time, it will succeed without triggering a walk.

I admit that this description is pretty crummy (reflecting my own level of knowledge). In particular, the exact way that a particular process is identified in the TLB is not 100% clear to me and at least somewhat hardware-specific. It used to be that every context switch needed a full TLB flush, but more recent Intel CPUs have a 6-bit “PID” field, which means that flushes, while still required sometimes, aren't always required on a context switch. Further crumminess arises from my failure to describe multi-level TLBs, PTEs (page table entries) and address the significance of this on data and instruction caching (although I do know that modern hardware can be seeing if it's at all possible that an address is in some cache level at the same time as the TLB lookup).

Question 2

How processes are put in Virtual Memory? I mean does each process has 0x0 - 0xFFFFFFFFF virtual memory space available for them or there is only one Virtual Memory address space where all the process are placed?

Each process has its own completely distinct virtual memory space. This is (almost) the entire point of VM.

In the olden days, the TLB was not “process aware” in any sense. Every context switch meant that the TLBs had to be flushed completely. Nowadays, TLB entries have a short “process context” (PCID?) field and support selective flushing, so you can kinda/sorta think of it as the PID (or, rather, the PCID: some kind of hash of the PID) being prepended to the virtual page address, so the TLB is more process aware, and only those entries need to be flushed when there's a PCID collision with another process (two processes map to the same PCID).

Question 3

Is there one big giant page table which includes all the pages for every process or each process has its own page table?

This is OS-specific, of course, but my understanding is that Linux has one multi-level set of page tables where the entries (PTEs) are tagged with the PID, rather than there being separate per-process page tables. I think the basic reason for this is that a lot of virtual-to-physical mappings are n:1 rather than 1:1, since them all being 1:1 would largely defeat a major purpose of VM: think about shared readonly pages containing the instructions for libraries like libc, or copy-on-write data pages shared between parent and child after a fork. Duplicating these entries for every process in per-process page tables is less efficient than adding/deleting the process-specific entries to/from a common set of page tables when a process is created/exits.

Where Disk Comes In

Once you have a VM system, it becomes almost trivial to add the ability to retrieve a page from disk when a page fault occurs, and implement “aging” for PTEs so that the least recently used pages can be put on disk. Although this is an important feature on memory-constrained systems, is almost entirely irrelevant to understanding how a VM system actually works.

Hexastyle