When is memory allocation/layout deterministic?

I'm trying to learn about buffer overflow attacks, both on the stack and on the heap. However, I'm confused about when it's possible to determine the address of the buffer.

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. However, it's not completely random, since it is possible to guess the address of the buffer by increasing the chances using a NOP sled.

In contrast, the environment variables passed to the program are placed in the same addresses 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 (e.g. those allocated by malloc) and in other situations. Therefore:

1. In which circumstances is memory layout deterministic?


2. How predictable is it even when not entirely deterministic? Finally, how do exploit mitigations like ASLR and PIE affect this?