When is memory allocation/layout deterministic?

I'm trying to learn about buffer overflow attacks, both on the stack and on the heap. The classic "Smashing the Stack for Fun and Profit" mentions the need to use a sizable NOP sled in a stack-based buffer overflow attack in order to reliably jump into the shellcode placed into the buffer. This seems to be due to the fact that the buffer ends up at a different memory location in each run of the program, and yet there's not too much non-determinism (since adding a NOP sled sizably increases the attacker's chances). However, the addresses of the environment variables passed to the program seem to be the same every time, enabling a much easier local attack in which the attacker places shellcode into an environment variable, and then can jump to that environment variable's location exactly. I'm still in the dark about how this plays out for heap-based buffers and in other situations. Therefore my question:

In which circumstances is memory layout deterministic? How predictable is it even when not entirely deterministic? Finally, how do exploit mitigations like ASLR and PIE affect this?