title: pthreads: using multiple threads to calculate successive prime numbers
body: <p>I am trying to get the example code to work such that multiple threads will calculate the sum of successive prime numbers (note that the original author's algorithm for successive prime calculation is very inefficient). So far, running unit tests shows that the output is inconsistent, i.e. it will change slightly each time I run the program. I will post the modified source code in C, along with output for debugging purposes.</p>
  
  <p>Source:</p>
  
  <pre><code>/************************************************************************
   * Code listing from "Advanced Linux Programming," by CodeSourcery LLC  *
   * Copyright(C) 2001 by New Riders Publishing                           *
   * See COPYRIGHT for license information.                               *
   ***********************************************************************/
  
  /*
   * Modified By : Dylan Gleason
   * Class       : CST 352 - Operating Systems
   * Date        : 10/18/2012
   */
  
  #include &lt;pthread.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;stdio.h&gt;
  
  #define DEBUG 0  /* Set to 1 to enable debug statements */
  
  /* global variables to be accessed by each thread */
  int current_sum = 2;
  int primes_to_compute = 0;
  
  /* create mutex for ensuring serial access to global data */
  int thread_flag;
  pthread_cond_t cond;
  pthread_mutex_t lock;
  
  /* print the thread info for debugging purposes */
  void print_thread_info() 
  {
     printf("Current thread ID        : %u\n",(unsigned int*)pthread_self());
     printf("Current sum of primes    : %d\n", current_sum);
     printf("Current prime to compute : %d\n\n", primes_to_compute);
  }
  
  /* initialize the mutex and return an integer value to determine if
     initialization failed or not */
  int initialize_mutex()
  {
     int success = 1;
  
     if(pthread_mutex_init(&amp;lock, NULL) == 0 &amp;&amp;
        pthread_cond_init(&amp;cond, NULL) == 0)
        success = 0;
     thread_flag = 0;
  
     return success;
  }
  
  /* set the value of the wait thread flag to the value which the client
     passes */
  void set_thread_flag(int is_waiting)
  {
     pthread_mutex_lock(&amp;lock);   /* lock mutex */
  
     /* set the wait flag value, and then signal in case the prime
        function is blocked, waiting for flag to become set. However,
        prime function can't actually check flag until the mutex is
        unlocked */
     thread_flag = is_waiting;
     pthread_cond_signal(&amp;cond);   
     pthread_mutex_unlock(&amp;lock); /* unlock mutex */
  }
  
  void in_wait()
  {
     while(!thread_flag)
        pthread_cond_wait(&amp;cond, &amp;lock);
  }
  
  
  /* Compute successive prime numbers(very inefficiently). Return the
     Nth prime number, where N is the value pointed to by *ARG. */
  void* compute_prime(void* arg)
  {   
     while(1)
     {
        pthread_mutex_lock(&amp;lock);
        in_wait();
        pthread_mutex_unlock(&amp;lock);
  
        int sum;
        int factor;
        int is_prime = 1;
  
        set_thread_flag(0);
        pthread_mutex_lock(&amp;lock);
        sum = current_sum;
  
        if(DEBUG)
        {
           printf("First lock\n");
           print_thread_info();
        }
  
        pthread_mutex_unlock(&amp;lock);
        set_thread_flag(1);          /* tell next thread to go! */
  
        /* wait until ready-flag is released from current thread */
        pthread_mutex_lock(&amp;lock);
        in_wait();
        pthread_mutex_unlock(&amp;lock);
  
        /* Test primality by successive division. */
        for(factor = 2; factor &lt; sum; ++factor)
        {  
           if(sum % factor == 0)
           {
              is_prime = 0;
              break;
           }
        }
  
        /* Is this the prime number we're looking for? */
        if(is_prime)
        {
           int number;
  
           set_thread_flag(0);
           pthread_mutex_lock(&amp;lock);
  
           /* only decrement primes_to_compute if is greater than zero! */
           if(primes_to_compute &gt; 0)
           {
              --primes_to_compute;
           }       
           if(DEBUG)
           {
              printf("Second lock\n");
              print_thread_info();
           }
  
           number = primes_to_compute;
           pthread_mutex_unlock(&amp;lock);
           set_thread_flag(1);
  
           pthread_mutex_lock(&amp;lock);
           in_wait();
           pthread_mutex_unlock(&amp;lock);
  
           if(number  == 0)
           {
              set_thread_flag(0);
              pthread_mutex_lock(&amp;lock);
              void* sum =(void*) current_sum;
  
              if(DEBUG)
              {
                 printf("Third lock\n");         
                 print_thread_info();
              }
  
              pthread_mutex_unlock(&amp;lock);
              set_thread_flag(1);
              return sum;
           }
        }
  
        set_thread_flag(0);
        pthread_mutex_lock(&amp;lock);
        ++current_sum;
  
        if(DEBUG)
        {
           printf("Fourth lock\n");
           print_thread_info();
        }
  
        pthread_mutex_unlock(&amp;lock);
        set_thread_flag(1);
     }
  
     return NULL;
  }
  
  int main(int argc, char* argv[])
  {
     int prime;
     pthread_t tid[5];   
  
     /* Check command-line argument count */
     if(argc != 2)
     {
        printf("Error: wrong number of command-line arguments\n");
        printf("Usage: %s &lt;integer&gt;\n", argv[0]);
        exit(1);
     }
  
     /* Check to see if mutex initialized correctly */
     if(initialize_mutex() != 0)
     {
        printf("Mutex initialization failed.\n");
        exit(1);
     }
  
     primes_to_compute = atoi(argv[1]);
     printf("Successive primes to be computed: %d\n\n", primes_to_compute);
  
     /* Execute five different threads to calculate the prime summation */
     int t = 0;
     set_thread_flag(1);
  
     for(t; t &lt; 5; ++t)
        pthread_create(&amp;tid[t], NULL, &amp;compute_prime, NULL);
  
     /* Wait for the prime number thread to complete, then get result. */
     t = 0;
     for(t; t &lt; 5; ++t)
        pthread_join(tid[t],(void*) &amp;prime);
  
     /* Print the largest prime it computed. */
     printf("The %dth prime number is %d.\n", atoi(argv[1]), prime);
  
     return 0;
  }
  </code></pre>
  
  <p>Unit test (executing program five times):</p>
  
  <pre><code>Test successive primes up to 100:
  
  Successive primes to be computed: 100
  The 100th prime number is 547.
  
  Successive primes to be computed: 100
  The 100th prime number is 521.
  
  Successive primes to be computed: 100
  The 100th prime number is 523.
  
  Successive primes to be computed: 100
  The 100th prime number is 499.
  
  Successive primes to be computed: 100
  The 100th prime number is 541.
  </code></pre>
  
  <p>Note that the output of non-threaded version if the number for successive primes to calculate is <code>100</code>, the result will always be <code>541</code>. Clearly I am not able to grok the correct usage of the mutexes above - if someone has more experience in this area I would be very grateful! Also, <strong>please note</strong> that I am not concerned with the efficiency/correctness of the actual prime number algorithm, but rather the algorithm for making sure that the threads execute properly with consistent results.</p>