C semaphores and a "barrier" between threads

Question

I'm trying to solve a problem our Operating Systems professor showed us from a previous exam to prepare for the next one.

The problem is to have two threads that execute concurrently and may complete in a different amount of time. After a particular thread is completed, it needs to block until the other thread is completed, then they may continue their execution.

It seems conceptually simple to me, but my code isn't working the way I think it should.

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

#define N 10

sem_t t_1_sem;
sem_t t_2_sem;

void *thread(void *vargp);
/* shared by both threads*/
struct {
    int count;
} thread_count;

int main() {
    pthread_t tid, tid1;

    thread_count.count = 0;

    sem_init(&t_1_sem, 0, 1);
    sem_init(&t_2_sem, 0, 1);
    printf("Hello from main thread! tid:%ld pid:%d\n", pthread_self(), getpid());
    pthread_create(&tid, NULL, thread, NULL);
    pthread_create(&tid1, NULL, thread, NULL);

    pthread_join(tid, NULL);
    pthread_join(tid1, NULL);

    exit(0);
}

void *thread(void *vargp) {
    int i, tid;

    int val, val2;
    sem_getvalue(&t_1_sem, &val);
    sem_getvalue(&t_2_sem, &val2);
    printf("initial value::: %d : %d\n", val, val2);


    tid = thread_count.count;
    thread_count.count += 1;

    for(i = 0;i<N;i++){
        printf("%d, %d\n", tid, i);
        fflush(stdout);
        //sleep(0.1);
    }

    // TODO
    // barrier
    sem_getvalue(&t_1_sem, &val);
    sem_getvalue(&t_2_sem, &val2);
    printf("second value::: %d : %d\n", val, val2);
    int sem_val;
    if(tid == 0){
        // free other
        sem_getvalue(&t_1_sem, &sem_val);
        printf("posting to 2, waiting on 1 w/ %d count\n", sem_val);
        sem_post(&t_2_sem);
        // wait on this one
        sem_wait(&t_1_sem);
        printf("done waiting on 1\n");
    } else if(tid == 1){
        sem_getvalue(&t_2_sem, &sem_val);
        printf("posting to 1, waiting on 2 w/ %d count\n", sem_val);
        sem_post(&t_1_sem);
        sem_wait(&t_2_sem);
        printf("done waiting on 2\n");
    }

    sem_getvalue(&t_1_sem, &val);
    sem_getvalue(&t_2_sem, &val2);
    printf("final value::: %d : %d\n", val, val2);
    return NULL;
}

What I'm expecting to see is both of the threads counting til 10, then the two "final value" printf's happening next to each other. However, what I'm seeing is the "final value" prints occurring immediately after the thread finishes counting to 10 - it doesn't seem to wait.

I'm also getting really weird values for the sem_val integer I print in the "posting to N" printf's, e.g.:

Hello from main thread! tid:-1606277344 pid:5479
initial value::: 0 : 0
0, 0
initial value::: 0 : 0
1, 0
0, 1
1, 1
0, 2
1, 2
1, 3
1, 4
1, 5
0, 3
1, 6
0, 4
1, 7
0, 5
1, 8
0, 6
1, 9
0, 7
second value::: 0 : 0
posting to 1, waiting on 2 w/ -1809628646 count
0, 8
done waiting on 2
final value::: 0 : 0
0, 9
second value::: 0 : 0
posting to 2, waiting on 1 w/ -1809628646 count
done waiting on 1
final value::: 0 : 0

Any ideas/hints?

Answer 1

You may want to consult The Little Book of Semaphores. Section 3.5 describes the Barrier pattern and how it is correctly implemented.

I know that doesn't directly answer your question, but it should point you in the right direction.

Answer 2

This doesn't exactly answer your question, but you might want to look at extracting the barrier from the thread - if it was C# you'd make it an object, and I've hardly done any C, but you'd probably have a struct and a couple of functions. This may or may not help a lot in this situation, but it saves writing a barrier from scratch each time you want one. Also, if you first implement a semaphore, you can then write a barrier in terms of semaphores, which simplifies things. (I'm currently doing a subject on concurrent programming in .NET, and one of the things we're doing is writing a set of concurrency utilities - semaphore, mutex, barrier, rendezvous, channel etc. - which we can then plug in to other programs.)

As for the barrier, as James has mentioned already, The Little Book of Semaphores describes a correct implementation

Answer 3

Is this what you want?

0, 0
0, 1  
0, 2
0, 3
0, 4
0, 5
0, 6
0, 7
0, 8
0, 9
1, 0
1, 1
1, 2
1, 3
1, 4
1, 5
1, 6
1, 7
1, 8
1, 9

I am not sure I understand your idea but I suspect you might use the semaphore incorrectly. Below is the code that generate above phenomena. Hopefully ,it has something useful for your problem.

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

#define N 10

sem_t t_1_sem;
sem_t t_2_sem;

void *thread_1(void *vargp);
void *thread_2(void *vargp);
/* shared by both threads*/
struct {
    int count;
} thread_count;

 int main() {
pthread_t tid, tid1;

thread_count.count = 0;

sem_init(&t_1_sem, 0, 1);
sem_init(&t_2_sem, 0, 1);
printf("Hello from main thread! tid:%ld pid:%d\n", pthread_self(), getpid());
pthread_create(&tid, NULL, thread_1, NULL);
pthread_create(&tid1, NULL, thread_2, NULL);

pthread_join(tid, NULL);
pthread_join(tid1, NULL);

exit(0);
}

void *thread_1(void *vargp) {
int i, tid;

int val, val2;
sem_getvalue(&t_1_sem, &val);
printf("enter thread_1\n");
sem_wait(&t_1_sem);
//even thread_1 is sleeping , thread_2 will not be scheduled to run
//as thread_1 is holding the semphore
sleep(1);
tid = thread_count.count;
thread_count.count += 1;

for(i = 0;i<N;i++){
    printf("%d, %d\n", tid, i);
    fflush(stdout);
    //sleep(0.1);
}

    sem_post(&t_1_sem);
    return NULL;
}


void *thread_2(void *vargp) {
int i, tid;

int val, val2;
sem_getvalue(&t_1_sem, &val);

printf("enter thread_2\n");
sem_wait(&t_1_sem);
tid = thread_count.count;
thread_count.count += 1;

for(i = 0;i<N;i++){
    printf("%d, %d\n", tid, i);
    fflush(stdout);
    //sleep(0.1);
}

    sem_post(&t_1_sem);
    return NULL;
}

Answer 4

I just successfully dealt with something like this using pthreads with mutexes and condition variables.

Semaphores are a general inter-thread or inter-process messaging mechanism, which you can incidentally use for thread coordination with some difficulty. Mutexes are specialized binary semaphores aimed squarely at thread coordination, and offer a simplified API to do that.

So if you're not constrained to use semaphores, you might consider mutexes as an easier way to get the job done.

Whichever thread coordination approach you pick, use a search engine to find code samples that solve similar problems, and make sure you understand them. For instance, "pthread semaphore example" and "pthread mutex example" both got lots of interesting hits.

A big hint: make sure you actually need two semaphores. One semaphore or mutex can control an arbitrarily large number of threads.

As a more general pedagogical remark, not aimed at your specific example, threading is one of those places where the notion of KISS really applies. It's very easy to get too fancy and get yourself all tangled up.

Answer 5

this is that what you want:

i'm 0 and waiting for 1 - starting
i'm 1 and waiting for 0 - starting
i'm 1, 0 arrived, lets go
i'm 0, 1 arrived, lets go
i'm 1 and waiting for 0 - stopping
i'm 0 and waiting for 1 - stopping
i'm 0, 1 stopped, go home now
i'm 1, 0 stopped, go home now

and the correct code, found what's wrong of your original code yourself.

#define SEM_INIT_V      0

static sem_t t_0_sem;
static sem_t t_1_sem;

void *thread(void *vargp);
/* shared by both threads*/
struct {
        int count;
} thread_count = {};

int main() {
        pthread_t tid0, tid1;

        thread_count.count = 0;

        sem_init(&t_0_sem, 0, SEM_INIT_V);
        sem_init(&t_1_sem, 0, SEM_INIT_V);
        pthread_create(&tid0, NULL, thread, &thread_count.count);
        thread_count.count++;
        pthread_create(&tid1, NULL, thread, &thread_count.count);

        pthread_join(tid0, NULL);
        pthread_join(tid1, NULL);

        return 0;
}

void *thread(void *vargp) {
        int tid = *(int*)vargp;

        //await to sync 0 & 1
        if (0 == tid) {
                puts("i'm 0 and waiting for 1 - starting");
                sem_post(&t_1_sem);
                sem_wait(&t_0_sem);
                puts("i'm 0, 1 arrived, lets go");
                sleep(8);
        } else {
                puts("i'm 1 and waiting for 0 - starting");
                sem_post(&t_0_sem);
                sem_wait(&t_1_sem);
                puts("i'm 1, 0 arrived, lets go");
                sleep(3);
        }

        if(tid == 0){
                puts("i'm 0 and waiting for 1 - stopping");
                sem_post(&t_1_sem);
                sem_wait(&t_0_sem);
                puts("i'm 0, 1 stopped, go home now");
        } else if(tid == 1){
                puts("i'm 1 and waiting for 0 - stopping");
                sem_post(&t_0_sem);
                sem_wait(&t_1_sem);
                puts("i'm 1, 0 stopped, go home now");
        }

        return NULL;
}

Answer 6

sem_getvalue() is not implemented on osx. http://discussions.apple.com/thread.jspa?messageID=9404131&tstart=0

Answer 7

You are initializing the semaphores with initial value of 1 so the wait will succeed immediately (the posts at end of the operation will simply bump the value to 2).

sem_init(&t_1_sem, 0, 1);
sem_init(&t_2_sem, 0, 1);

Then second problem is that you are generating the tid variable in way which is not a thread safe. Both threads might end with value of zero even if that did not happen in this case.