Why does adding a critical section cause a segmentation fault?

Question

I am trying to play around with the following quicksort algorithm in parallel:

#include <stdio.h>
#include <stdlib.h>
#include<omp.h>
#define MAX_UNFINISHED 1000   /* Maximum number of unsorted sub-arrays */


struct {
   int first;                  /* Low index of unsorted sub-array */
   int last;                   /* High index of unsorted sub-array */
} unfinished[MAX_UNFINISHED];  /* Stack */

int unfinished_index;          /* Index of top of stack */

float *A;                      /* Array of elements to be sorted */
int    n;                      /* Number of elements in A */


void swap (float *x, float *y)
{
   float tmp;

   tmp = *x;
   *x = *y;
   *y = tmp;
}


int partition (int first, int last)
{
   int i, j;
   float x;

  
   x = A[last];
   i = first - 1;


   for (j = first; j < last; j++)
      if (A[j] <= x) {
     i++;
     swap (&A[i], &A[j]);
      }
   swap (&A[i+1], &A[last]); 
   return (i+1);
}


void quicksort (void)
{
   int first;
   int last;
   int my_index;
   int q;    

   while (unfinished_index >= 0) {
      
    #pragma omp critical
    {
      my_index = unfinished_index;
      unfinished_index--;
      first = unfinished[my_index].first;
      last = unfinished[my_index].last;
    }

    while (first < last) {
      q = partition (first, last);

      if ((unfinished_index+1) >= MAX_UNFINISHED) {
        printf ("Stack overflow\n");
        exit (-1);
      }

      #pragma omp critical
      {
        unfinished_index++;
        unfinished[unfinished_index].first = q+1;
        unfinished[unfinished_index].last = last;
        last = q-1;
      }  
    }
  }
}



int verify_sorted (float *A, int n)
{
   int i;
   for (i = 0; i < n-1; i++)   
      if (A[i] > A[i+1]) 
         return 0;

return 1;
}


int main (int argc, char *argv[])
{
   int    i;
   int    seed;             /* Seed component input by user */
   unsigned short xi[3];    /* Random number seed */

   if (argc != 3) {
      printf ("Command-line syntax: %s <n> <seed>\n", argv[0]);
      exit (-1);
   }
   seed = atoi (argv[2]);
   xi[0] = xi[1] = xi[2] = seed;

   n = atoi (argv[1]);
   A = (float *) malloc (n * sizeof(float));


   for (i = 0; i < n; i++)
      A[i] = erand48(xi);

 

   unfinished[0].first = 0;
   unfinished[0].last = n-1;
   unfinished_index = 0; //


   #pragma omp parallel 
   quicksort();



   if (verify_sorted (A, n)) printf ("Elements are sorted\n");
   else printf ("ERROR: Elements are NOT sorted\n");
   return 0;
}

Adding the critical sections in the quicksort() function causes a segmentation fault 11, why is that? From my basic understanding, such an error occurs when the system tries to access memory it doesn't have access to or is non-existent, I can't see where that would happen. Putting a critical section over the entire while() loop fixes it but it would be slow.

Answer 1

Your strategy to parallelize the QuickSort looks overcomplicated and prone to race-conditions, the typically way to parallelize that algorithm is to use OpenMP tasks. You can have a look a the following SO Threads

1.QuickSort;

2.MergeSort.

Adding the critical sections in the quicksort() function causes a segmentation fault 11, why is that?

Your code has several issues namely;

1. There is a race-condition between the read of unfinished_index in while (unfinished_index >= 0) and the updates of that variable by other threads;
2. The segmentation fault 11 happens because threads can access positions out of bounds of the array unfinished, including negative positions.

Even with the critical region multiple threads can execute:

unfinished_index--;

which eventually leads to unfinished_index < 0 and consequently:

  my_index = unfinished_index;
  unfinished_index--;
  first = unfinished[my_index].first; <-- problem
  last = unfinished[my_index].last;   <-- problem

accessing negative position the unfinished array. And the same applies to the upper bound as well. All threads my pass this check:

 if ((unfinished_index+1) >= MAX_UNFINISHED) {
    printf ("Stack overflow\n");
    exit (-1);
  }

and then simply

  #pragma omp critical
  {
    unfinished_index++;
    unfinished[unfinished_index].first = q+1;
    unfinished[unfinished_index].last = last;
    last = q-1;
  } 

increment unfinished_index so much that it can access positions outside of the array boundaries.

To solve those problems you can do the following:

void quicksort (void)
{
   int first;
   int last;
   int my_index;
   int q;    
   int keep_working = 1;
   while (keep_working) {
    #pragma omp critical
    {
      my_index = unfinished_index;
      if(my_index >= 0 && my_index < MAX_UNFINISHED)
        unfinished_index--;
      else
         keep_working = 0;
    }
    if(keep_working){
      first = unfinished[my_index].first;
      last = unfinished[my_index].last; 
      while (first < last && keep_working) 
      {
        q = partition (first, last);
        #pragma omp critical
        {
            unfinished_index++;
        my_index = unfinished_index;
        }
        if (my_index < MAX_UNFINISHED){
            unfinished[my_index].first = q+1;
            unfinished[my_index].last = last;
            last = q-1;
        }
        else
           keep_working = 0;
     } 
   }
  }
}

Bear in mind, however, that the following code works for 2 threads. For more than that you might get sometimes "the array not sorted". I will leave it up to you to fixed. However, I would suggested you to used the Task approach instead, because it is faster, simpler and more updated with more modern OpenMP constructors.