Understand virtual memory and how it differs from physical memory
Objective
Background
Virtual memory?
Virtual memory is an abstraction of physical memory (RAM) by the OS. It gives the process a notion of having an entire contiguous memory address space for itself. This is made possible by using the disk space as well to complement the physical memory. By having an additional layer of memory, it’s possible to allocate the process a larger amount of memory (even greater than the physical memory), share memory between processes and make a process’ memory space unaffected by other processes.
Memory addresses come in groups
Memory in most PCs is byte-addressable, which means that each byte of data has an address in the memory which we can use to access that byte only. When someone says they have a 32 bit system, it means that the memory address their system can use is 32 bits in length. Memory addresses are usually denoted in hexadecimal and hence a 32 bit memory address will be an 8 digit hexadecimal number (each hexadecimal digit is 4 bits).
(Source: chortle.ccsu.edu)
We say that an address in a process’ virtual memory is mapped when it has a corresponding physical memory address. We’ll have to store these mappings somewhere, right? This is what pagetable does. Why not the address table? We’ll see in a minute :)
Every process will have a page table that contains information about memory mappings of that process. For every memory address allocated to the process, it needs to have a entry in the page table of the process. Let’s say a page table entry for an address takes just 8 bits. In a 32 bit system, we have 32 bit memory address space, each address requiring 8 bits in the page table. If we do the calculation, this means that we would need storage of size upto 4 GB (2 to the power 32) for each process, just to store its page tables. Wait, how was the pagetables size calculated?
Contiguous virtual memory addresses are grouped into pages. So, if the page size is 4KB (2 to the power 12), the page table size is drastically reduced to just 1MB (2 to the power 20) compared to 4GB earlier.
Similar to virtual memory pages, RAM addresses are divided into fixed size blocks called page frames. In short, pages are stored in page frames. Pages & page frames are identified by unique numbers. Any page will be allocated a complete page frame in the RAM and hence all memory addresses in a page will be contiguous in physical memory as well. Now, when the physical memory is depleted and the OS needs to allocate memory to a process, it can choose to swap data from a frame to disk. The page table of the process whose data was just swapped is also updated to show the frame is in disk and has information about the location on disk where it was swapped.
How is virtual memory converted to physical memory?
Ok, cool stuff. But, how exactly is a memory address mapped? Does the OS use a hashing algorithm or what?
With virtual memory in place and memory grouped into pages, OS is free to choose any vacant page frame in the physical memory to store a page’s content. Let’s say our process queries for data in its memory location 0x00400004. If the page size is 4KB, dividing memory address by page size gives us the page number as 0x400 with 4 as remainder which is the number of locations from the starting of the page where our memory address resides. We check the process’ page table and find that page number 0x400 is mapped to page frame number 0x10. As our memory address is 4 locations after the first address in the page, we find data in the 4th address after the first in the page frame as well.
Primary goals
- Understand the difference between virtual memory & physical memory
Objective
Understand virtual memory and how it differs from physical memory
Background
Virtual memory?
Virtual memory is an abstraction of physical memory (RAM) by the OS. It gives the process a notion of having an entire contiguous memory address space for itself. This is made possible by using the disk space as well to complement the physical memory. By having an additional layer of memory, it’s possible to allocate the process a larger amount of memory (even greater than the physical memory), share memory between processes and make a process’ memory space unaffected by other processes.
Memory addresses come in groups
Memory in most PCs is byte-addressable, which means that each byte of data has an address in the memory which we can use to access that byte only. When someone says they have a 32 bit system, it means that the memory address their system can use is 32 bits in length. Memory addresses are usually denoted in hexadecimal and hence a 32 bit memory address will be an 8 digit hexadecimal number (each hexadecimal digit is 4 bits).
(Source: chortle.ccsu.edu)
We say that an address in a process’ virtual memory is mapped when it has a corresponding physical memory address. We’ll have to store these mappings somewhere, right? This is what pagetable does. Why not the address table? We’ll see in a minute :)
Every process will have a page table that contains information about memory mappings of that process. For every memory address allocated to the process, it needs to have a entry in the page table of the process. Let’s say a page table entry for an address takes just 8 bits. In a 32 bit system, we have 32 bit memory address space, each address requiring 8 bits in the page table. If we do the calculation, this means that we would need storage of size upto 4 GB (2 to the power 32) for each process, just to store its page tables. Wait, how was the pagetables size calculated?
Contiguous virtual memory addresses are grouped into pages. So, if the page size is 4KB (2 to the power 12), the page table size is drastically reduced to just 1MB (2 to the power 20) compared to 4GB earlier.
Similar to virtual memory pages, RAM addresses are divided into fixed size blocks called page frames. In short, pages are stored in page frames. Pages & page frames are identified by unique numbers. Any page will be allocated a complete page frame in the RAM and hence all memory addresses in a page will be contiguous in physical memory as well. Now, when the physical memory is depleted and the OS needs to allocate memory to a process, it can choose to swap data from a frame to disk. The page table of the process whose data was just swapped is also updated to show the frame is in disk and has information about the location on disk where it was swapped.
How is virtual memory converted to physical memory?
Ok, cool stuff. But, how exactly is a memory address mapped? Does the OS use a hashing algorithm or what?
With virtual memory in place and memory grouped into pages, OS is free to choose any vacant page frame in the physical memory to store a page’s content. Let’s say our process queries for data in its memory location 0x00400004. If the page size is 4KB, dividing memory address by page size gives us the page number as 0x400 with 4 as remainder which is the number of locations from the starting of the page where our memory address resides. We check the process’ page table and find that page number 0x400 is mapped to page frame number 0x10. As our memory address is 4 locations after the first address in the page, we find data in the 4th address after the first in the page frame as well.
Primary goals
- Understand the difference between virtual memory & physical memory
Getting Started
-
You need access to a Linux machine with sudo access.
-
Have g++ compiler to run simple cpp programs.
g++ SampleProgram.cc -o SampleProgram
./SampleProgram
- Understand how to run background process and get its process id.
When you run a program with ‘&’ in the end, it runs as a background job and prints the process id. In the above case, 226285 is the process id.
- You may have to periodically kill these processes you put in the background. Otherwise your system may become slow. If you run
psin the same terminal, you will be able to see the list of all processes. You can then kill the process either usingpkillorkillcommands.
What is procfs?
Procfs is a special filesystem in Linux that presents information about processes and other system information in a hierarchical file-like structure. It provides a more convenient and standardized method for dynamically accessing process data held in the kernel. You’ll see it mounted at /proc in your Linux machine.
You can look at the reference material for more information. To start with, get comfortable with the following command which gives the memory layout of your current process denoted by self.
cat /proc/self/maps
Similarly you can get the memory layout of any process by using
cat /proc/[pid]/maps
Another file in Procfs we’ll be utilizing is /proc/[pid]/pagemap. This allows programs access to page table data.
Tip
On 32-bit machines, addresses are only 32-bits
A hex digit - 0xf = 1111 -> 4 bits
So 8 digits are there in the address - 0x26a7c010
For 64-bit systems, addresses are 64-bits
0x7fdc81399010 -> Check if they have 16 digits. If not, why?.
Proving VM address != Physical Memory address
Ok, the background section argues that virtual memory (VM) address and physical memory (PM) or RAM address aren’t the same. We’ll now learn this by doing.
Let’s see the virtual memory addresses for two different processes and try to analyze it. Two programs which go to sleep after doing simple operations are provided for this purpose - run both
// SimpleProgram.cc
int foo() {
return 5;
}
int main() {
int value = foo();
while(1){};
return 0;
}
// EasyProgram.cc
int main() {
int a = 5;
while(1) {};
return 0;
}
Now, let’s analyse the proc-maps output of both these processes to see if anything stands out. Looking at the first 5 lines of command output:
Both the processes have the exact same memory address region for the first 3 sections and still similar ones for the rest. If you see, the addresses store different files /home/crio/Desktop/experiment/virtual_memory/SimpleProgram & /home/crio/Desktop/experiment/virtual_memory/EasyProgram. Different data in the same address? That can’t be true, right?
This points to the fact that every process has its own virtual memory space which is mapped to a physical memory address.
Not satisfied? Use a program that writes a particular text to a memory address and continuously log the data at that memory address to the console. Start the process. Now, run another instance of the same program writing a different text to the same address.
Does the output of the first process change? What does that mean - processes see virtual memory or physical memory?
(A helper program is provided here for you)
Looking at VM to PM address mapping
We’ll see for ourselves the mapping of the virtual memory address to its physical memory counterpart. This is the actual location in the RAM.
Let’s run the same programs from earlier.
The program that does the magic for us resides here. Go fetch it!
Now, we have to tell the program which process we are looking at (PID) and the virtual memory address for which we’d like to find the physical memory mapping
Long story short, the virtual memory address 00400000 is located inside the physical memory frame number 0x1701b. Let’s face it, the output is quite confusing. We’ll look at what the process is trying to communicate.
Page_size is the number of bytes in a memory page. Entry_size tells us that for each virtual memory page there is an 8-bit entry in /proc/[pid]/pagemap. And VirtualPFN is the page in which virtual memory address 00400000 resides.
Hmm…, wait! How did 00400000 when divided by 4096 become 0x400?
Try yourselves out, I’ll leave this number converter for you
(Hint: Memory addresses are hexadecimal, 4096 is decimal)
So, a virtual memory address of a process will point to a specific physical memory address. But, isn’t this quite expensive in cases like different processes using the same huge file?
Awesome thinking! OS designers had thought of the exact same issue and decided to allow processes to share memory. This way if a particular file is being used by multiple processes, it only has to be loaded once into the physical memory.
Too much talk, now let’s get to work and see this for real. libc.so library is required by all executables in Linux. So, this is a good candidate for us to check if different processes share access to a common file.
We can check the virtual memory address for the libc library in the earlier processes.
For the first the entry with permissions r-xp starts from 7f8e49b4a000 and for the other its from 7f886d502000. We’ll ask our pagemap program to convert these addresses for us.
The output verifies that common files are indeed shared across processes.
In Milestone 1, we saw that both of the processes had the exact same VM mappings. Now that you have memory mapping in your arsenal, can you check the physical memory frames that the address maps to, for each of the processes?
References
Curious Cats
-
We mentioned that memory addresses are grouped as pages. Use the
pagemapprogram to see if consecutive virtual memory addresses belong to the same physical memory page frame -
So, all the contents of a page in virtual memory resides wholly in a page in physical memory. Are consecutive pages in virtual memory consecutive in physical memory as well? Is it necessary to be so in all cases? (Hint: Page size = 4096 which is 1000 in hex implies if 7f886d504000 is in virtual page 0x7f886d504, then 7f886d505000 will be in page 0x7f886d505)
-
We fetched the memory address info from
/proc/[pid]/pagemapfile. What would happen if we try to print out all of its contents? Around how much bytes of data will it have for a 64-bit machine? (Hint: A page table entry is 8 bits) -
Start two processes that read from the same file. Find the virtual memory addresses from the
/proc/[pid]/mapsoutput and see if physical memory mappings for the file are the same. Do these map to the same physical memory after one of the processes writes to the file as well?
Mapping of a particular VM address
We saw in the previous milestone that virtual memory addresses are mapped to a corresponding physical address. That means a particular virtual memory address should always map to a particular physical address, right? No! Ok, then it should be the case at least for the same program, right? Not sure, let’s see.
We’ll check this edge case by seeing if a virtual memory address of the same program maps to the same physical memory frame. Compile and start the program provided here twice.
Feed to our mighty pagemap program, these process ids & the virtual memory address 0x100000000. Fingers crossed!
So, even for two processes of the same program, memory mapping isn't the same.
If you see the program, we’ve used the mmap function to allocate memory equal to the size of a page starting from address 0x100000000 and then wrote some text to that address. Comment out the line that has strcpy function used to write to that address. Try the above exercise again. Is there any difference?
Does a process always use all of its VM addresses?
x86-64 bit processors allow up to 128TB of virtual address space which translates to - every process gets 128TB of virtual memory. Does that mean all of this space is used?
Start the program which writes to a virtual memory address. Feel free to change the address it writes to from 123456 to something random.
// RandomVMAccess.cc
int main()
{
char *p = (char*) 123456; // set as some random value
p[0] = '\n';
}
It would be safe to say that you would have got a segmentation fault. This happens when your process tries to access an illegal memory location. What! I read from a perfectly legal virtual memory address, 123456.
The catch is that your program tried to read from a virtual memory address which literally means that it may not be real. Virtual memory addresses become "legal" only if you allocate it for your process which is done by functions like malloc, mmap etc.
Use our pagemap program to see if you get a physical memory mapping for a random address.
Curious Cats
-
What happens when you assign NULL to a pointer? Which memory address does it point to?
-
Virtual memory pages can be in three states - unmapped, swapped, in physical memory. What was the page table entry for your random memory mapping? How would we know from the page table if an address is swapped or not?
Newfound Superpowers
-
You have now unlocked the answers to the mystery of Virtual Memory vs Physical Memory
-
Memory addresses and memory mapping are now, well, easy!
Now you can
Answer the following, which you might not have been able to before:
-
How are you able to run video games of sizes larger than your computer’s RAM?
-
So, virtual addresses of a process have a corresponding physical memory address. Can two different virtual addresses map to the same physical memory address?
-
Does a particular VM address map to a specific PM address always? What about in case of a specific program?
-
Currently, 64-bit processors allow up to 256TB of virtual address space. Do processes use their entire virtual address space?