0

I'm having trouble with getting my worker threads and facilitator threads to synchronize properly. The problem I'm trying to solve is to find the largest prime number 10 files using up to 10 threads. 1 thread is single-threaded and anything greater than that is multi-threaded.

The problem lies where the worker signals the facilitator that it has found a new prime. The facilitator can ignore it if the number is insignificant, or signal to update all threads my_latest_lgprime if it is important. I keep getting stuck in my brain and in code.

The task must be completed using a facilitator and synchronization.

Here is what I have so far:

Worker:

void* worker(void* args){
     w_pack* package = (w_pack*) args;
     int i, num;
     char text_num[30];
     *(package->fac_prime) = 0;
     for(i = 0; i<package->file_count; i++){
          int count = 1000000; //integers per file
          FILE* f = package->assigned_files[i];
          while(count != 0){
               fscanf(f, "%s", text_num);
               num = atoi(text_num);
               pthread_mutex_lock(&lock2);
               while(update_ready != 0){
                    pthread_cond_wait(&waiter, &lock2);
                    package->my_latest_lgprime = largest_prime;//largest_prime is global
                    update_ready = 0;
               }
               pthread_mutex_unlock(&lock2);
               if(num > (package->my_latest_lgprime+100)){
                    if(isPrime(num)==1){
                         *(package->fac_prime) = num;
                         package->my_latest_lgprime = num;
                         pthread_mutex_lock(&lock);
                         update_check = 1;
                         pthread_mutex_unlock(&lock);
                         pthread_cond_signal(&updater);  
                    }

               }
               count--;
          }
     }

     done++;
     return (void*)package;
}`

Facilitator:

void* facilitator(void* args){
     int i, temp_large;
     f_pack* package = (f_pack*) args;

     while(done != package->threads){
          pthread_mutex_lock(&lock);
          while(update_check == 0)
               pthread_cond_wait(&updater, &lock);
          temp_large = isLargest(package->threads_largest, package->threads);
          if(temp_large > largest_prime){
               pthread_mutex_lock(&lock2);
               update_ready = 1;
               largest_prime = temp_large;
               pthread_mutex_unlock(&lock2);
               pthread_cond_broadcast(&waiter);
               printf("New large prime: %d\n", largest_prime);
          }
          update_check = 0;
          pthread_mutex_unlock(&lock);
     }
}

Here is the worker package

typedef struct worker_package{
     int my_latest_lgprime;
     int file_count;
     int* fac_prime;
     FILE* assigned_files[5];
} w_pack;

Is there an easier way to do this using semaphores?

1 Answer 1

1

I can't really spot a problem with certainty, but just by briefly reading the code it seems the done variable is shared across threads yet it is accessed and modified without synchronization.

In any case, I can suggest a couple of ideas to improve on your solution.

  1. You assign the list of files to each thread at start up. This isn't the most efficient way, since processing each file may take more or less time. It seems to me a better approach would be to have a single list of files, and then each thread picks up the next file in the list.

  2. Do you really need a facilitator task for this? It seems to me each thread can keep track of its own largest prime, and every time it finds a new maximum it can go check a global maximum and update it if necessary. You could also keep a single maximum (w/o a per-thread maximum) but that will require you to lock every time you need to compare.

Here is pseudo-code of how I would write the worker threads:

while (true) {
    lock(file_list_mutex)
    if file list is empty {
        break // we are done!
    }
    file = get_next_file_in_list
    unlock(file_list_mutex)

    max = 0
    foreach number in file {
        if number is prime and number > max {
            lock(max_number_mutex)
            if (number > max_global_number) {
                max_global_number = number
            }
            max = max_global_number
            unlock(max_number_mutex)
        }
    }
}

Before you start the worker threads you need to initialize max_global_number = 0.

The above solution has the benefit that it doesn't abuse locks like in your case, so thread contention is minimized.

5
  • Thanks for the response Miguel. The purpose of the facilitator is so that a thread can skip over numbers that are smaller a prime that another thread may have found. It should make things more efficient, but in my implementation I can't seem to figure out how. As for the file assignment, I'm not really trying to make it more efficient in that aspect, only when the threads are running. In other words, I will start to time the workers after the files are assigned. Dec 10, 2011 at 18:47
  • Hi Trevor. I still don't see a need for a facilitator task. Note that your solution would spend a lot of time waiting for locks or conditions, you do that for every number you look at, even if it is not prime. With 10 threads that will generate a lot of contention. You aren't really making the process more efficient, all the contrary. In my solution the thread works with its own maximum and will only lock once it finds one. And at that point since the lock is taken it will also grab the global maximum, like in your solution. Dec 10, 2011 at 18:58
  • +1 for #2. I don't really see the point of the facilitator either, Trevor. You could just as easily have each worker skip ahead when it goes to post a new prime and finds a higher value already there. For that matter, you could sort the files first and work down. Once the largest prime is found you are done with that file.
    – Duck
    Dec 10, 2011 at 19:03
  • @Duck Those are definitely ways to make this more efficient, but the task here is to use synchronization and a facilitator. I guess I should have made that more clear in the question. If you guys know how to do it with synchronization, using cond variables or semaphores, then that would be great. Dec 10, 2011 at 19:10
  • You haven't said what is wrong with your current implementation. Dec 10, 2011 at 21:13

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.