Virtual Memory

Introduction

In simple and straightforward terms: Modern Operating Systems (OS) controls access to memory. Process demands memory and OS provides. Each process thinks it has a large consecutive space of memory which is called virtual memory.  For a 32 bit system virtual address space is 4G wide. For a 64 bit system virtual address space size is 256TB. Virtual memory brings some very important advantages. Each process can address whole address space available; however, system may not have that much physical memory. Each process has its own private virtual memory space which other process cannot access. Virtual memory concept also lets operating system map files. Finally virtual memory concept sharing similar memory areas between processes.

Paging

Virtual address space is divided into small fixed size consecutive address blocks which are called pages. Usually a page is 4 kilobytes in size. Similarly physical address space is divided into such blocks which are calledframes. Page size and frame size must be equal. Each used page must be mapped to a frame.

Mapping of pages to frames is called address translation. Address translation is done by Memory Management Unit which is resident in CPU. MMU uses page tables to achieve address translation.

Each process has its own page table. CPU has a register to keep page table address and on a context switch this address is changed. Page Table comprises of Page Table Entries for each page in virtual address space. If a page is in physical memory, a page table entry contains frame number which refers to location of the page in physical memory. 

Given a virtual address, some of high-order bits of virtual address represents the page number. This page number is used as an index to page table to find corresponding page table entry. If the page is in physical memory, which is understood by checking valid/invalid bit, page table entry contains frame number. Remaining lower order bits of virtual address is used as offset to frame. By concatenating frame number and offset, physical address is obtained.

                                                                                                     

As mentioned above, virtual address space is much larger than physical address space. As a result there are typically much more pages than physically available frames. Operating system uses page file (pagefile.sys for Windows, swap partition for Linux) to write unused pages to disk to open space for actively used pages. In such cases, some pages may not reside in physical memory and must be loaded from disk to a free frame.

How Paging Works

Mapping of Virtual Memory to Physical Memory

1-      Everything starts when CPU needs to access a certain virtual address.

2-      Page table pointer shows the address of page table. Page number part of virtual address is used as an index to page table. Page table entry at the shown by page number, indicates whether page is in currently in memory.

3-      If page is in memory, which is indicated by a valid value in valid/invalid flag,  page table entry shows frame address. Using frame address and offset part of virtual address, physical address is built. Finally physical address is accessed and content is loaded to a CPU register.

4-       If page is not in memory, which is indicated by an invalid value in valid/invalid flag, a page fault occurs. Page needs to be loaded into physical memory. Operating system loads required page from page file to an available frame. Frame address is written to page table entry and valid/invalid flag is set to indicate that page is in physical memory.  Then CPU tries to access virtual address again.

 

Memory Types

Memory is categorized using two classes First class indicates whether it is private or shared. Second class indicates whether it is file backed or not, namely anonymous.

Private Memory

Refers to type of memory which is specific to a process. However, multiple processes may use the same physical memory areas. If any of the processes attempts to modify the shared physical memory, memory area is copied and modification is done to copied area. This action is called Copy on Write (COW).

COW makes fork operations cheap.  When a process is forked, instead of creating a full copy of the processes memory space, memory space is made copy-on-write. COW also reduces total memory usage of processes that are using same binary files and shared libraries.

If private memory is file backed, modifications are not reflected to backing file.

 

Shared Memory

Shared memory is used by multiple processes and any change made by one process is visible to other processes using the same shared memory. Memory is made shared by using explicit system calls. If shared memory is file backed, modifications are reflected to backing file.

Anonymous Memory

Anonymous memory refers to memory areas that are not file backed. When anonymous memory is allocated, allocation is only made in virtual memory and it is mapped to zero page. Zero page is a special page that is filled with zeroes. No physical allocation is made until a write operation is made. When that memory is read, zeroes from zero page is read. When a modification is done to that memory, copy-on-write is triggered and actual physical allocation is made.

In other words reserved memory is not committed until it is really used. This logic allows reservation of memory space that is more than available.

 

File Backed Memory

File backed memory has the content of the mapped file. If it is shared all processes uses the same physical memory and updates are visible to all processes. If it is private any modification triggers a copy-on-write so that each process has its own private copy.