On my hosted vServer with 1024 MB RAM, I got this message about every half hour:
[Mon May 21 15:21:03 2012] [error] (12)Cannot allocate memory: fork: Unable to fork new process
Running “top”, I saw that there was no swap space configured, but in my case 1 GB of RAM should be enough. Only 100 MB of RAM was free at this moment.
Running “top -u www-data”, many apache2 processes appeared, everyone took about 70 MB. MySQL uses about 20 %, which is okay in my case. Because the website has not many visitors, but runs some huge scripts (so the PHP memory limit is at 256 MB), I decided to adjust the prefork values in apache2.conf to about the half of the default values.
After restarting Apache, I had about 350 MB free RAM and the error message disappeared.
A useful command if you want to determine the process which uses the highest amount of memory:
ps aux | sort -nrk 4 | head