The operating system performs a lot of work before executing the first instruction. The OS must set up at least two data structures, the page table and the region map. The region map is called different things in different operating systems. Inside the Linux kernel, for example, it is a linked list of memory-region objects and some kind of index (e.g. a red-black tree) that gives you an efficient way of discovering the region a specific virtual addresses belongs to.
Each memory region has a start address, a length, permissions (can the program read/write/execute from the region), and some information about the "type" of the region, including how the region is supposed to be initialized on first use and how the logical information is supposed to be saved if a mapped page needs to be moved to disk.
The first step is that the operating system creates a new page table with every virtual page marked as "invalid." Next the OS reads the header of the executable file. The header describes the region map and also gives the virtual address of the first instruction to be executed. So the OS creates an in-memory region map to match the structure described in the executable header and then tries to execute the first instruction (it does this by using some kind of "return from interrupt" instruction that sets the root of the page table to the page table for the process we want and then changing the program-counter (instruction-pointer) to the virtual address of the first instruction.
So the processor tries to execute the instruction at the given virtual address. But every page in the page-table is marked invalid, so when the processor performs the translation from virtual to physical address the processor will invoke an "invalid page" fault, bringing control back to the operating system. The operating system will look up the virtual address in the region map. Since this was supposed to be the address of the first instruction, then it should be the case that the virtual address is contained in a region that is marked as being executable, and there should be information about where the instructions are located in the original executable file. The OS reads a page-worth of date from the original executable file into some physical page in memory, and then modifies the page table to reflect the new virtual-to-physical mapping. Finally the OS again tries to return-from-interrupt to the instruction address. This time, although there will be TLB misses and cache misses, the translation will give a mapping from virtual to physical address, the processor will eventually try to fetch the required instruction into the L1 cache and execute it.
In all likelihood the instruction will try to access some not-yet valid data location. There will be another "invalid page" fault for the data's virtual address. The OS will look up the data's virtual address in the region map, allocate a physical page, initialize the page, map the page in the page table and then return-from-interrupt a third time. This time the instruction will get fetched and executed, and after another TLB and cache miss for the data access will actually execute without causing another fault. Then we move to the next instruction and start all over again.
Hopefully we have some spatial and/or temporal locality so this process doesn't happen with every instruction.
