当前位置: 动力学知识库 > 问答 > 编程问答 >

c - Binary search with fork()

问题描述:

I'm trying to create a binary search tree using 2 sons. They will return 1 if the element searched has been found or 0 otherwise.

#define m_index 16

#include <stdio.h>

#include <stdlib.h>

#include <unistd.h>

#include <errno.h>

int fork_search(int a[], int search, int start, int end){

if(start == end){

if(*(a + end) == search){

return 1;

}

return 0;

}

else{

pid_t child = fork();

if(child == 0) return fork_search(a, search, start, (start+end)/2);

else{

// creating the second son here

pid_t child2 = fork();

if(child2 == 0) return fork_search(a, search, (start + end)/2+1, end);

}

}

}

int main(int argc, char* argv[]){

int a[m_index] = {1, 12, 11, 5, 10, 6, 4, 9, 13, 2, 8, 14, 3, 15, 7};

printf("%d\n", fork_search(a, 12, 0, m_index-1));

return 0;

}

How can I create a second son to search the upper half? If it's the father I could simply write return fork_search(a, search, (start + end)/2+1, end);, however, I need the second son to do this. Thank you!

网友答案:

You are confused about how fork() works. Also about how binary searches work.

Using fork() to traverse a tree

fork() merely starts a copy of the current process (technically a copy-on-write copy). So it will return success provided the fork succeeds.

In fact, it returns twice on success, once to the child, and once to the parent. From the man page:

On success, the PID of the child process is returned in the parent, and 0 is returned in the child. On failure, -1 is returned in the parent, no child process is created, and errno is set appropriately.

So, first you need to check the fork() did not fail (did not return -1). If it did, you abort your search.

If the fork() returned 0, you are the child, so you can search one limb of your tree. Otherwise you are the parent, in which case you need to do the second fork(), then wait() for both children to complete. And pass the results back with exit() (return will merely lead to each child printing the line to stdout in main()).

Note that this way of traversing a binary tree will produce one process for every node in the tree (or every node in the tree with children). This may in effect be a fork bomb, i.e. you may DoS your own computer. You may therefore want to limit the levels of fork() used (i.e. switch to a conventional search when you are more than n levels deep).

Confusion between a binary search and traversing a tree

The second issue here is that the whole point of a binary search (as opposed to a tree) is that you examine the item half way along the search range, then only search to one side of it, i.e. you do not need to process both sides. This eliminates the need for fork().

Here the contents of the array that you are searching are not in order, so you aren't doing a binary search. You are (in effect) traversing a tree, where the root node is half way along, the next nodes up are half way between the ends and the root nodes, etc.

分享给朋友:
您可能感兴趣的文章:
随机阅读: