I know that array elements are contiguous in virtual memory for sure, but are they in terms of physical memory like this one?
#define N 100*1024*1024
int arr[N];
Please Note, Until now most of you said the answer is NO but again my main question is the one below in bold.
If not, at-least if one element was found in a page then can I suppose the whole page is filled of array elements (in other words they may not be contiguous as one in different pages but contiguous in each single page thus improving performance when reading 1 element we read a full page of nearby element ie 4096 byte instead of reading another page for next elements)?
If yes, what if I tried to allocate a big array where there is no available contiguous physical memory (which can happen a lot I believe)?
If the answer depends on programming language I'm interested in C and C++ and if it depends on the OS I'm interested in linux and it's variants like ubuntu
Each page of virtual memory is mapped identically to a page of physical memory; there is no remapping for units of smaller than a page. This is inherent in the principle of paging. Assuming 4KB pages, the top 20 or 52 bits of a 32- or 64-bit address are looked up in the page tables to identify a physical page, and the low 12 bits are used as an offset into that physical page. So if you have two addresses within the same page of virtual memory (i.e. the virtual addresses differ only in their 12 low bits), then they will be located at the same relative offsets in some single page of physical memory. (Assuming the virtual page is backed by physical memory at all; it could of course be swapped out at any instant.)
For different virtual pages, there is no guarantee at all about how they are mapped to physical memory. They could easily be mapped to entirely different locations of physical memory (or of course one or both could be swapped out).
So if you allocate a very large array in virtual memory, there is no need for a sufficiently large contiguous block of physical memory to be available; the OS can simply map those pages of virtual memory to any arbitrary pages in physical memory. (Or more likely, it will initially leave the pages unmapped, then allocate physical memory for them in smaller chunks as you touch the pages and trigger page faults.)
This applies to all parts of a process's virtual memory: static code and data, stack, memory dynamically allocated with malloc/sbrk/mmap etc.
Linux does have support for huge pages, in which case the same logic applies but the pages are larger (a few MB or GB; the available sizes are fixed by hardware).
Other than very specialized applications like hardware DMA, there isn't normally any reason for an application programmer to care about how physical memory is arranged behind the scenes.