2

複数のスレッドが連続する素数の合計を計算するようにサンプル コードを動作させようとしています (連続する素数の計算に関する元の作成者のアルゴリズムは非常に非効率的であることに注意してください)。これまでのところ、単体テストを実行すると、出力に一貫性がないことがわかります。つまり、プログラムを実行するたびに出力がわずかに変化します。修正した C 言語のソース コードと、デバッグ用の出力を投稿します。

ソース:

/************************************************************************
 * 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 <pthread.h>
#include <stdlib.h>
#include <stdio.h>

#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(&lock, NULL) == 0 &&
      pthread_cond_init(&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(&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(&cond);   
   pthread_mutex_unlock(&lock); /* unlock mutex */
}

void in_wait()
{
   while(!thread_flag)
      pthread_cond_wait(&cond, &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(&lock);
      in_wait();
      pthread_mutex_unlock(&lock);

      int sum;
      int factor;
      int is_prime = 1;

      set_thread_flag(0);
      pthread_mutex_lock(&lock);
      sum = current_sum;

      if(DEBUG)
      {
         printf("First lock\n");
         print_thread_info();
      }

      pthread_mutex_unlock(&lock);
      set_thread_flag(1);          /* tell next thread to go! */

      /* wait until ready-flag is released from current thread */
      pthread_mutex_lock(&lock);
      in_wait();
      pthread_mutex_unlock(&lock);

      /* Test primality by successive division. */
      for(factor = 2; factor < 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(&lock);

         /* only decrement primes_to_compute if is greater than zero! */
         if(primes_to_compute > 0)
         {
            --primes_to_compute;
         }       
         if(DEBUG)
         {
            printf("Second lock\n");
            print_thread_info();
         }

         number = primes_to_compute;
         pthread_mutex_unlock(&lock);
         set_thread_flag(1);

         pthread_mutex_lock(&lock);
         in_wait();
         pthread_mutex_unlock(&lock);

         if(number  == 0)
         {
            set_thread_flag(0);
            pthread_mutex_lock(&lock);
            void* sum =(void*) current_sum;

            if(DEBUG)
            {
               printf("Third lock\n");         
               print_thread_info();
            }

            pthread_mutex_unlock(&lock);
            set_thread_flag(1);
            return sum;
         }
      }

      set_thread_flag(0);
      pthread_mutex_lock(&lock);
      ++current_sum;

      if(DEBUG)
      {
         printf("Fourth lock\n");
         print_thread_info();
      }

      pthread_mutex_unlock(&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 <integer>\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 < 5; ++t)
      pthread_create(&tid[t], NULL, &compute_prime, NULL);

   /* Wait for the prime number thread to complete, then get result. */
   t = 0;
   for(t; t < 5; ++t)
      pthread_join(tid[t],(void*) &prime);

   /* Print the largest prime it computed. */
   printf("The %dth prime number is %d.\n", atoi(argv[1]), prime);

   return 0;
}

単体テスト (プログラムを 5 回実行):

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.

計算する連続する素数の数が である場合、非スレッド バージョンの出力では100、結果は常に になることに注意してください541。明らかに、上記のミューテックスの正しい使用法を理解することはできません-誰かがこの分野でより多くの経験を持っているなら、私は非常に感謝しています! また、実際の素数アルゴリズムの効率/正確性には関心がないことに注意してください。むしろ、スレッドが適切に実行され、一貫した結果が得られるようにするためのアルゴリズムに関心があります。

4

1 に答える 1

1

わかりました、あなたのプログラムを見ると、何が起こっているのかがわかります。

競合状態があり、かなり悪い状態です。あなたがいる番号は、current_sum変数によって決まります。各ループの開始時にアクセスしますが、ループの最後までインクリメントしないでください。同じmutexロック内で同時に設定してからインクリメントする必要があります。そうしないと、2つの異なるスレッドが同じ値をプルでき、それらが同じプライム値をプルすると、そのプライムが2回カウントされます。

お役に立てれば。

于 2012-10-18T22:03:50.147 に答える