Searching with fork in C

问题:

I'm supposed to be getting comfortable with fork, and I saw an exercise that said to use a fork call to search an array indexed from 0 to 15. We're to assume that each process can only do two things...(1) is to check to see if an array is length 1, and (2) compare a single element of an array to the number were searching for. Basically i pass it a number, and its supposed to do a finite number of forks and return the index of that number. Here's my code..

#define MAXINDEX 16

int forkSearch(int a[], int search, int start, int end){
  if(start == end){
    if(*(a + end) == search){
      return end;
    }
  } 
  else{
    pid_t child = fork();
    if(child == 0) return forkSearch(a, search, start, end/2);
    else return forkSearch(a, search, (start + end)/2, end);
  }
}

int main(int argc, char* argv[]){
  int searchArray[MAXINDEX] = {1, 12, 11, 5, 10, 6, 4, 9, 13, 2, 8, 14, 3,\
                               15, 7};
  printf("Should be 1. Index of 12 = %d\n", forkSearch(searchArray,
                                                       12, 0, MAXINDEX));
  return 0;
} 

Everything in the return of this quickly exploding program seems to be either 1, 10, 11, or 13. Why isn't this working like it should.

回答1:

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

That's the wrong end there, it should be (start+end)/2, and the start index of the search in the right half should be (start+end)/2 + 1. Otherwise, if the right half is (start+end)/2 .. end, when end == start+1, the start for the recursive call is the old start value and you have an infinite loop.

Your programme has undefined behaviour because

int forkSearch(int a[], int search, int start, int end){
  if(start == end){
    if(*(a + end) == search){
      return end;
    }
  }

doesn't return a value if start == end, but *(a+end) != search. Add an exit(0); after the inner if to exit the processes that didn't find the target.

int searchArray[MAXINDEX] = {...};

forkSearch(searchArray, 12, 0, MAXINDEX)

will lead to an out-of-bounds access at searchArray[MAXINDEX], also undefined behaviour.