How to create multiple processes by using fork() to keep splitting the array and get the index of the given number

Question

// arr[0] = 1, arr[1] = 2, arr[2] = 3, arr[3] = 4, arr[4] = 5, arr[5] = 6, arr[6] =7, arr[7] = 8.
// count = 8  which is the length of the array in this case
// value = 6 which is the value that is being searched

int get_first(int arr[], int count)
{
   int half = count / 2;
   int *firstHalf = malloc(half * sizeof(int));
   memcpy(firstHalf, arr, half * sizeof(int));
   return firstHalf;
}

int get_second(int arr[], int count)
{
    int half = count / 2;
    int *secondHalf = malloc(half * sizeof(int));
    memcpy(secondHalf, arr + half, half * sizeof(int));
    return secondHalf;
}

pid_t  pid;
pid = fork();
if (pid == 0) 
  {
      int half = count / 2; 
      int *result = get_first(arr, count);

      while (sizeof(result) != 1)
      {
          half = half / 2 ;
          int *result = get_first(result, half);
      }
      if (result[0] == value[0])
      {
          return the index of value
      }
  }

else 
  {
      int half = count / 2; 
      int *result1 = get_second(arr, count);  

      while (sizeof(result1) != 1)
      {
          half = half / 2 ;
          int *result1 = get_second(result1, half);
      }
      if (result1[0] == value[0])
      {
          return the index of value
      }
  }

I am new to c and I am really not good at fork(). I need to write a program that uses multiple processes to keep splitting an array into two equal parts. When the array only has a single element, the process will compare the single element to the integer being searched for.

For example, to split an array 5, 6, 7, 8. P1 creates two children, P2 which is assigned to search 5, 6, and P3 which is assigned to search 7, 8. P2 creates two children, P4 which is assigned to search 5, and P5 which is assigned to search 6. P3 creates two children P6 which is assigned to search 7, and P7 which is assigned to search 8.

I wrote two functions to split the array and they are both working fine. The first function gets the first part of the array and the second function gets the second part of the array (I did not write the indexing part because I have not got to there yet). But I am struggling with the fork(). I think the way I am using fork() does not help me to get the right answer, because it does not get to every element in the array.

My question is how to change the fork() in order to allow it to compare every element in the array with the value that I am searching for. Can someone help me to fix it? Thanks in advance.

Answer 1

When fork() returns it returns (on success) in two processes (the calling process and its new child process). Both starts with same code (the first command after fork()). The child process gets an exact copy of the memory in its current state. Thus, although all variables have now its own "incarnation" in their process they have the identical values like just before the fork() in the parent process.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>

/* the type of array elements: */
typedef int Value;

/** fills the sample array with values.
 *
 * For this sample, it's simply filled with conscutive values.
 *
 * @param n the size of array
 * @param arr the array
 */
void fillArray(size_t n, Value *arr)
{
  Value value; /* aux. to provide value to set */
  size_t i; /* loop index */
  value = 0;
  for (i = 0; i < n; ++i) arr[i] = value++;
}

/** searches for value in two processes concurrently.
 *
 * @param n the size of array
 * @param arr the array
 * @param pivot the value to search for
 */
void search(size_t n, Value *arr, Value pivot)
{
  size_t n_2 = n / 2;
  if (!n) return; /* nothing to do */
  printf("search %d...\n", (int)pivot); /* assumes (int)pivot makes sense */
  if (n_2 >= 1) {
    pid_t pid;
    pid = fork();
    if (pid < 0) {
      fprintf(stderr, "ERROR: fork failed!\n");
      return;
    }
    if (pid == 0) { /* in child process */
      size_t i;
      for (i = n_2; i < n; ++i) {
        if (arr[i] == pivot) break;
      }
      if (i < n) { /* element at i is a hit */
        printf("Hit %d (found in child)\n", (int)i);
      }
    } else { /* in parent process */
      size_t i;
      for (i = 0; i < n_2; ++i) {
        if (arr[i] == pivot) break;
      }
      if (i < n_2) { /* element at i is a hit */
        printf("Hit %d (found in parent)\n", (int)i);
      }
      /* terminate child process */
      exit(0); /* funny things happen if this were not here */
    }
  } else { /* special case: only 1 element in array */
    if (arr[0] == pivot) {
      printf("Hit 0 (found)\n");
    }
  }
}

int main(int argc, char **argv)
{
  /* should become input: */
  size_t n; /* the size of array */
  Value *arr; /* the array */
  /* get number of values */
  n = 10;
  /* allocate space for array */
  arr = (Value*)malloc(n * sizeof (Value));
  /* fill array */
  fillArray(n, arr);
  /* make some sample searches */
  search(n, arr, (Value)3);
  search(n, arr, (Value)7);
  /* clean-up */
  free(arr);
  /* done */
  return 0;
}

I tried this with gcc on cygwin. (Cygwin seems to support fork() on Windows - for my surprise.)

Output:

$ gcc --version
gcc (GCC) 5.4.0
Copyright (C) 2015 Free Software Foundation, Inc.
    
$ gcc -o forkSearch forkSearch.c 
    
$ ./forkSearch
search 3...
Hit 3 (found in parent)
search 7...
Hit 7 (found in child)

Live Demo on coliru

What I didn't solve in this sample is (IMHO) the actual challenge: how to pass the found value from child to parent process (in case).