How to change the program to use multiple consumer level threads

Question

0.00/5 (No votes)

See more:

I have to problems that I need help solving. 1st problem is to have multiple consumer threads working together to find all the prime numbers in a given range and measure how long the program will take to find all prime numbers using 2, 3, & 4 consumer threads. 2nd problem is to have a 2-item buffer instead of a 1-item buff and measure how long the program will take to find and print all prime numbers using 2, 3, and 4 consumer threads. Here is my code. I have tried searching the web and got nothing. Can you please help. My code is below.

What I have tried:

C++

#include <stdio.h>
#include <pthread.h>
#define MAX 1234568500

pthread_mutex_t the_mutex;
pthread_cond_t condc, condp;
int buffer = 0;

unsigned long long int isPrime(unsigned long long int x)
{
	int i;
	
	for(i=2;i<=x/2;++i)
	{
		if(x % i == 0)
		{
			return -1;
		}
	}
	
	return x;
}

void *producer(void *ptr)
{
	unsigned long long int i;
	for(i=1234567800;i<=MAX;i++)
	{
		pthread_mutex_lock(&the_mutex);
		
		while(buffer!=0)
			pthread_cond_wait(&condp,&the_mutex);
		
		buffer = i;
		pthread_cond_signal(&condc);
		pthread_mutex_unlock(&the_mutex);
	}
	
	pthread_exit(0);
}

void *consumer(void *ptr)
{
	unsigned long long int i;
	for(i=1234567800;i<=MAX;i++)
	{
		pthread_mutex_lock(&the_mutex);
		
		while(buffer==0)
			pthread_cond_wait(&condc,&the_mutex);
		
		if(isPrime(buffer)!=-1)
			printf("%d\n",isPrime(buffer));
			
		buffer = 0;
		pthread_cond_signal(&condp);
		pthread_mutex_unlock(&the_mutex);
	}
	pthread_exit(0);
}

int main(int argc, char **argv)
{
	int num_args = argc - 1
	pthread_t pro,con;
	
	pthread_mutex_init(&the_mutex,0);
	
	pthread_cond_init(&condc,0);
	pthread_cond_init(&condp,0);
	
	pthread_create(&con,0,consumer,0);
	pthread_create(&pro,0,producer,0);
	
	pthread_join(pro,0);
	pthread_join(con,0);
	
	pthread_cond_destroy(&condc);
	pthread_cond_destroy(&condp);
	
	pthread_mutex_destroy(&the_mutex);
	
	return 0;
}

Posted 5-Mar-20 10:46am

Member 14764665

Updated 6-Mar-20 14:14pm

Patrice T

v2

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Rick York · Answer 1 · 2020-03-05T21:22:00

I have been thinking about your first problem for a while and I think I have an algorithm in mind. It has to do with dividing the work between the threads. The thing is, you probably won't see much improvement over a single-threaded version until you get to really big numbers. What ever. You wanted a multi-threaded version so here is one possibility. The first thing to do is what most prime finders do : test the value for divisibility by 2. If it is then it's not a prime number so get that out of the way first because then you eliminate half of the possibilities. Then you always start at 3 and check every odd number after it since the even ones are already ruled out.

Here's where the dividing the work part comes in. Each thread is given a stride value. With one thread the stride is 2. With two threads the stride is 4. This works out to the stride value being twice the number of threads. Correspondingly, the starting point will be :

C

startingPoint = 3 + ( ( threadIndex - 1 ) * 2 );

This translates to the starting points with four threads will be 3 for thread 1, 5 for thread 2, 7 for thread 3, and 9 for thread 4.

With these values, you could write your test function as :

C

typedef unsigned long long  ULL;

int IsPrime( ULL value, int threadIndex, int threadCount )
{
    ULL strideValue = 2 * (ULL) threadCount;
    ULL lastValue = value / 2;                              // stop testing here
    ULL testValue = 3 + ( ( (ULL) threadIndex - 1 ) * 2 );  // start testing here
    while( testValue <= lastValue )
    {
        if( ( value % testValue ) == 0 )
            return 0;                       // nope, we found a factor
        testValue += strideValue;
    }
    return 1;   // yes, it is a prime
}

The next thing to do is figure out how the threads will report their results. There are a wide variety of ways to do this. One would be to have a single result value and a counter that tells you how many threads have reported. The variables would have their access controlled by a mutex. When a thread finishes it acquires the mutex, sets the result value to true only if its result is true (if false then leave it alone) and then increments the counter. If the thread finds it was the last one (counter == number of threads) it sets a signal indicating the test is done. After all this it releases the mutex.

The next step is to start and signal the threads. This part I will leave to you since it appears that you are using the pthread library and I can't help you with that. I know how threads and signals work in general, but not that library.

There are different ways this algorithm can be used, depending on how you want to test. The IsPrime algorithm was written assuming the threads are testing one value. Another way you can do testing like this is to build a list of prime numbers. For this, you would use a generic IsPrime function written for one thread but you would distribute the values to test as is done in this IsPrime function with different start and stride values, depending on the thread count and index. Then you would need an array of results with a counter controlled by a mutex.

Patrice T · Answer 2 · 2020-03-06T14:15:00

Quote:
How to change the program to use multiple consumer level threads

Before resorting to multi-threads, the first thing to do is to make sure that the tested algorithm is optimized.
Your code is a very inefficient 'Trial Division' variant, it happen that just optimizing the code will outperform by far any multi-threaded variation of your code.
See my article to get ideas of how to optimize a Trial Division algorithm: Integer Factorization: Trial Division Algorithm[^]

Your algorithm tells if a number is a prime by finding a factor, returning the factor instead of -1 have much more usages than just telling if prime or not.

How to change the program to use multiple consumer level threads

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0