I'm having a hard time understanding the need for PIC executables when virtual memory is being used. From what I gathered each program is assigned an entry in the page table and therefore has the illusion that it has the whole memory at its disposal while the paging mechanism takes care of possible relocations, pagefaults and so on.So if any program has the illusion of owning all possible memory addresses why would one use a PIC?
We don't need it, and until the last year or two, all Linux executables were position-dependent (not PIC). See 32-bit absolute addresses no longer allowed in x86-64 Linux?.
You can still build non-PIE executable with gcc -fno-pie -no-pie, and static ELF executables are always non-PIE with their load address chosen at link time. Typically defaulting to putting the start of the text segment at 401000.
Position-independent ELF executables started out as a hack: an ELF shared object with an entry point. But these days that's widely used and the gcc default on most Linux distros. The load address can be randomized at runtime.
Also note that many OSes support runtime fixups when loading an executable or library at something other than its preferred address.
ELF shared objects on Linux for example can contain relocations for 64-bit absolute addresses, so you can have traditional jump tables (array of code pointers) or statically-initialized arrays of pointers (to data or functions) in code compiled with gcc -fPIC for x86 and x86-64.
Note that gcc -fPIC also enables support for symbol-interposition, so functions can't directly access global variables; they have to load the address from the GOT, unless the symbol has "hidden" ELF visibility. (Or of course if you make it static instead of global).
See https://www.macieira.org/blog/2012/01/sorry-state-of-dynamic-libraries-on-linux/
(Some of the ideas proposed in that blog have been implemented, for example GCC supports -fno-plt.)
The actual cost of just position-independence with -fpie is pretty small. But still non-zero on OSes where position-dependent executables are guaranteed to load in the low 32 bits of virtual address space (e.g. Linux), so you can take advantage of 32-bit absolute addresses for 5-byte mov r32, imm32 instead of 7-byte RIP-relative LEA to put a static address into a register, or [array + reg] to index a static array with its address in a disp32 displacement as part of an addressing mode..