Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm starting to tinker with process forking, just to get a feel for it. I thought I'd write an example where work is distributed among child processes and the results handed back to the parent; this way, it could be run in parallel on several processors.

In my first attempt, I'm forking in a loop, which means that each time through, all the existing processes (the original, children, grandchildren, etc) produce another fork.

This is causing me problems (memory consumption, rapid growth of the number of processes, keeping track of the pipes to hand data back up the chain, etc), and I'm wondering if I've stumbled on an anti-pattern. I could simply fork N children directly from the parent.

I realize that it's common to fork and exec multiple times; for instance, terminal forks a shell, and the shell forks an editor. But is it considered bad practice to fork "recursively" when the children are all of the same type?

share|improve this question
2  
After the fork runs there is a return flag of some sort which can tell you whether you are the parent or the newly born clone. I think it is OK to fork in a loop, as long as only the parent does so. In the movie "The 6th day" they looked inside the eye to figure out if the person was a clone. There is a similar but different way of doing this in C. The important thing is: you must have precise control over who forks and who does not. Otherwise you cannot reason about what is going on in your multi-process code. –  Job Dec 24 '11 at 16:39
5  
A recursive fork is a sort of denial of service aka fork bomb. –  staticx Dec 24 '11 at 20:41
5  
I'm firing a shotgun, and noticed my foot is starting to bleed. Is this dangerous? –  Joey Adams Dec 25 '11 at 4:25
1  
@JoeyAdams - LOL. Well played, sir. –  Nathan Long Dec 25 '11 at 11:34
add comment

2 Answers

up vote 6 down vote accepted

Uncontrolled forking is definitely an anti-pattern. As you have discovered, it is relatively easy to consume all available resources, and then continue to consume them to the point where everything grinds to a complete standstill.

Just ask the Sorcerer's apprentice.

Like any problem involving recursion, you have to clearly understand your terminating condition. If your algorithm potentially never terminates, recursion is completely unsuitable since you have no control of how deep your stack can become.

Of course, some tasks may "discover" other tasks, so it may also never be possible to launch everything directly from the parent process.

One strategy often used to simplify a solution is to create some kind of task manager process, and have it consume a queue of pending tasks. The master task, or any children, can add tasks to the queue as they find them. The task manager then forks as many processes as it needs to in order to process the tasks.

In this way, the task manager can keep a count of the total number of running processes, and only fork a new process if it thinks it necessary and the hardware can cope with it.

There is a risk of blocking with this, of course: some task needs the result of another task before it can continue, yet that other task is in the queue and will never be run because all the currently executing tasks are blocking waiting for tasks that haven't been started yet...

You can fix this by having separate tasks whose job is to consume results, and managing these through a separate task manager. That way, the calculations can never become completely blocked: something is always going to be making progress.

share|improve this answer
add comment

If you want to distribute multiple processes the goal is to minimize proccessing time. You need to define what do you want to minimize. Usually it is a nearest neighbor or a geometry function or 2d function f(x)=y. A recursion isn't such a function but you can look into a gray code for example to traverse a function f(x)=y. It can help you to difference between the left and the right bit.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.