Hopeless Wanderer Hopeless Wanderer - 3 months ago 9
C Question

Condition variables program works for 2 threads but not for 3

So I have this program that has 2 threads to increment from 0 to 100 a variable, and it works fine.

#include<stdio.h>
#include<stdlib.h>
#include<semaphore.h>
#include<pthread.h>

int contor;

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

void *incrementare(void *args) {
int id = (int)args;
while(1) {
pthread_mutex_lock(&mutex);
if (contor >= 100) {
pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);
pthread_exit(NULL);
}

while (contor %2 == id) {
pthread_cond_wait(&cond,&mutex);
}

contor++;
printf("Thread %d increment: %d\n",id,contor);


pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);
}
}

int main(void) {
pthread_t th1, th2,th3;

if(pthread_create(&th1, NULL, &incrementare, (void *)0) < 0) {
perror("Error!\n");
exit(1);
}
if(pthread_create(&th2, NULL, &incrementare, (void *)1) < 0) {
perror("Error!\n");
exit(2);
}


pthread_join(th1, NULL);
pthread_join(th2, NULL);

pthread_mutex_destroy(&mutex);
pthread_cond_destroy(&cond);

return 0;
}


The result is something like:

Thread 1 increment: 1
Thread 0 increment: 2
Thread 1 increment: 3
Thread 0 increment: 4
Thread 1 increment: 5
Thread 0 incre.. and so on ,which is nice.


But the problem is when I try with 3 threads, and it no longer works as they then come randomly. I only made 3 changes and I do not know what the issue is.

#include<stdio.h>
#include<stdlib.h>
#include<semaphore.h>
#include<pthread.h>

int contor;

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

void *incrementare(void *args) {
int id = (int)args;
while(1) {
pthread_mutex_lock(&mutex);
if (contor >= 100) {
pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);
pthread_exit(NULL);
}

while (contor %3 == id) {
pthread_cond_wait(&cond,&mutex);
}

contor++;
printf("Thread %d increment: %d\n",id,contor);


pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);
}
}

int main(void) {
pthread_t th1, th2,th3;

if(pthread_create(&th1, NULL, &incrementare, (void *)0) < 0) {
perror("Error!\n");
exit(1);
}
if(pthread_create(&th2, NULL, &incrementare, (void *)1) < 0) {
perror("Error!\n");
exit(2);
}
if(pthread_create(&th3, NULL, &incrementare, (void *)2) < 0) {
perror("Error!\n");
exit(3);
}



pthread_join(th1, NULL);
pthread_join(th2, NULL);
pthread_join(th3, NULL);


pthread_mutex_destroy(&mutex);
pthread_cond_destroy(&cond);

return 0;
}


It should do the same right? Only with 3 now. Why isn't it working? This is how it works

Thread 2 increment: 1
Thread 2 increment: 2
Thread 1 increment: 3
Thread 1 increment: 4
Thread 2 increment: 5
Thread 1 increment: 6

Answer

If you want the threads to guarantee a cycle, you need to make a thread wait until the counter modulo N (thread count) is a specific id, not until it is anything but that specific id. With two ids, if it wasn't one, it must be the other. But with three, there are two cases of breaking, and one case of waiting. The scheduler is freely capable of choosing whichever of those two spare threads it wants to release.

But if you change this:

while (contor %3 == id)

to this:

while (contor %3 != id)

you will enforce that the given thread will only write values that are modulo its id.

However, this isn't enough. You also need to wake all waiters. Before, when you had only two threads, there was always the same waiter: the "other guy" that wasn't the active thread. This a pthread_cond_signal would be directed to a specific target thread (the only one not running) and it naturally was also the next one in line.

With three or more threads, there is the possibility that the single thread potentially awoken by pthread_cond_signal may not be the one that has has a contor modulo N id. In fact, the more threads you have, the more likely this will happen. In that case, the thread goes back to waiting, but no one else waiting is started up again. You do NOT want to leave this to chance. Make sure all the waiters are awoken to ensure the one that is next will get the signal.

Do not address this by just sending another pthread_cond_signal somewhere. Rather, send a broadcast instead: Change this:

pthread_cond_signal(&cond);

to this:

pthread_cond_broadcast(&cond);

This will ensure all actively waiting threads eventually get a crack at looking at contor and the one that matches contor modulo N will get the chance to bump, print, send the next broadcast, and head back to waiting.

Thus, the minimal change to your code would be:

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>      // added for intptr_t
#include<inttypes.h>    // added for printf formatter for intptr_t
#include<pthread.h>

int contor;

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

void *incrementare(void *args) {
    intptr_t id = (intptr_t)args; // proper way to pass an integer via thread param
    while(1) {
        pthread_mutex_lock(&mutex);
        if (contor >= 100) {
            pthread_cond_broadcast(&cond);
            pthread_mutex_unlock(&mutex);
            pthread_exit(NULL);
        }

        while (contor %3 != id) {
        pthread_cond_wait(&cond,&mutex);
        }

        contor++;
        printf("Thread %"PRIdPTR " increment: %d\n",id,contor);


        pthread_cond_broadcast(&cond);
        pthread_mutex_unlock(&mutex);
    }
    return NULL; // should always have well-defined return value
}

int main(void) {
    pthread_t th1, th2,th3;

    if(pthread_create(&th1, NULL, &incrementare, (void *)0) < 0) {
        perror("Error!\n");
        exit(1);
    }
    if(pthread_create(&th2, NULL, &incrementare, (void *)1) < 0) {
        perror("Error!\n");
        exit(2);
    }
    if(pthread_create(&th3, NULL, &incrementare, (void *)2) < 0) {
        perror("Error!\n");
        exit(3);
    }

    pthread_join(th1, NULL);
    pthread_join(th2, NULL);
    pthread_join(th3, NULL);

    pthread_mutex_destroy(&mutex);
    pthread_cond_destroy(&cond);

    return 0;
}

The result is below:

Thread 0 increment: 1
Thread 1 increment: 2
Thread 2 increment: 3
Thread 0 increment: 4
Thread 1 increment: 5
Thread 2 increment: 6
Thread 0 increment: 7
Thread 1 increment: 8
Thread 2 increment: 9
Thread 0 increment: 10
....
Thread 0 increment: 97
Thread 1 increment: 98
Thread 2 increment: 99
Thread 0 increment: 100
Thread 1 increment: 101
Thread 2 increment: 102

See it live

The extra two output are because the code checking the the ceiling-break condition is before the cvar-predicate loop. It should be after, but I leave that for you to address.

Keep in mind, however, that doing this ultimately defeats the purpose of turning multiple threads loose on a task. Ideally you want any thread available to perform work to actually do so. That your work affects just a single global somewhat defeats the real purpose of threading (obviously you would not use threading to count to 100; a single thread in a loop is ideal for that).


Regardless, a condensed version of your program appears below. Change the values of N_THREADS and N_COUNT to see differences in output.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <pthread.h>

#define N_THREADS 7
#define N_COUNT   100

int contor;  // 0

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

void *incrementare(void *args)
{
    intptr_t id = (intptr_t)args;
    pthread_mutex_lock(&mutex);
    while(1)
    {
        while (contor < N_COUNT && contor % N_THREADS != id)
            pthread_cond_wait(&cond, &mutex);

        if (contor == N_COUNT)
            break;

        printf("Thread %"PRIdPTR" increment: %d\n", id, ++contor);
        pthread_cond_broadcast(&cond);
    }
    pthread_mutex_unlock(&mutex);
    return NULL;
}

int main(void)
{
    pthread_t ar[N_THREADS];
    intptr_t id = 0;

    for (int i=0; i<N_THREADS; ++i)
    {
        if(pthread_create(ar+i, NULL, &incrementare, (void *)id++) < 0) {
            perror("Error!\n");
            exit(1);
        }
    }

    for (int i=0; i<N_THREADS; ++i)
        pthread_join(ar[i], NULL);

    return 0;
}