What am I getting wrong in this Busy Waiting solution using Strict Alteration with C and Posix threads?

Question

I am supposed to reproduce the Strict Alternation algorithm using C and Posix Threads.

I coded the below solution but the printfs aren't being outputed at all. Sometimes just the my_id is outputed but that's all. What am I doing or understanding wrong?

For example, this was the output of one of the times I ran this code:

Oher output:

Here is the code I did:

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

int count = 0;
int turn = 1;

struct arg_struct {
    int my_id;
    int other;
};

void *runner(void *param) {
    struct arg_struct *args = (struct arg_struct *)param;
    int my_id = args -> my_id;
    int other = args -> other;
    printf("my_id %d\n", my_id);
    printf("other %d\n", other);
    printf("Running p_thread %d\n", my_id);

    while(1) {
        while (turn != my_id) { }

        // critical section
        count = count + my_id;
        printf("Critical section of p_thread %d, count was incremented by %d and is now %d\n", my_id, my_id, count);

        turn = other;

        // not critical section
        printf("Not critical section of p_thread %d\n", my_id);
    }

    pthread_exit(NULL);
}

int main(int argc, char *argv[]) {
    int thr_id1, thr_id2;
    pthread_t p_thread1;
    pthread_t p_thread2;

    struct arg_struct args_p_thread1;
    args_p_thread1.my_id = 1;
    args_p_thread1.other = 2;

    struct arg_struct args_p_thread2;
    args_p_thread2.my_id = 2;
    args_p_thread2.other = 1;

    thr_id1 = pthread_create(&p_thread1, NULL, runner, (void*)&args_p_thread1);
    thr_id2 = pthread_create(&p_thread2, NULL, runner, (void*)&args_p_thread2);

    return 0;
}

Add a "volatile" before int turn. That causes the code to work for me. And add pthread_join(&p_thread1) and for p_thread2 — Samuel Squire, Oct 20 '22 at 09:13
DO NOT add `volatile`. It is neither necessary nor sufficient. You could consider instead adding `_Atomic`. That supposes that you are OK with using a spin lock (which, after all, is what you tried to write), but do be aware that spin locks can be very costly when moderately contended or worse. Also be aware that atomics are an optional feature. — John Bollinger, Oct 20 '22 at 18:11

score 0 · Answer 1 · answered Oct 18 '22 at 18:38

0

The variable you use for your parameters is reused between the threads.

Your global variables are not immediately suitable for sharing between threads, so it’s possible they do not see a new value of turn and get stuck in your inner while loop.

Your main loop exits without waiting for the threads, so they may not get a chance to do much. Your program will exit at the end of the main thread, it will not automatically wait for your other threads.

answered Oct 18 '22 at 18:38

tinman

6,348
1
30
43

3

Given a simple `int turn;` any C compiler is free to turn `while (turn != my_id) { }` into `if (turn != my_id) while( 1 ) { }` and never check `turn` again. So it's not just a question of visibility. – Andrew Henle Oct 18 '22 at 19:13
True, I forgot about the main loop. I added a sleep and now it printed at least once each thread, but then it just keep sleeping but not printing the outputs. Last output: my_id 1; other 2; Running p_thread 1; Critical section of p_thread 1, count was incremented by 1 and is now 1; Not critical section of p_thread 1; my_id 2; other 1; Running p_thread 2; Critical section of p_thread 2, count was incremented by 2 and is now 3; Not critical section of p_thread 2; – A. Sousa Oct 18 '22 at 19:15
I didn't understand the comment about parameters reused between the threads, may you elaborate? Also, now that I have put the sleep, I was able to see at least one output and apparently the threads are sharing the global variables. – A. Sousa Oct 18 '22 at 19:17
In the repl.it it is still like my prev comment, but locally (windows) it worked. Thanks for the help. – A. Sousa Oct 18 '22 at 19:21
@AndrewHenle you’re quite right. I had only thought as far as optimising out the memory access, not taking the the optimisation to its conclusion. – tinman Oct 18 '22 at 19:59

score -1 · Answer 2 · answered Oct 20 '22 at 09:19

-1

This code works for me on Repl.it.

I added volatile and pthread_join

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

int count = 0;
volatile int turn = 1;

struct arg_struct {
    int my_id;
    int other;
};

void *runner(void *param) {
    struct arg_struct *args = (struct arg_struct *)param;
    int my_id = args -> my_id;
    int other = args -> other;
    printf("my_id %d\n", my_id);
    printf("other %d\n", other);
    printf("Running p_thread %d\n", my_id);

    while(1) {
        while (turn != my_id) { }

        // critical section
        count = count + my_id;
        printf("Critical section of p_thread %d, count was incremented by %d and is now %d\n", my_id, my_id, count);

        turn = other;

        // not critical section
        printf("Not critical section of p_thread %d\n", my_id);
    }

    pthread_exit(NULL);
}

int main(int argc, char *argv[]) {
    int thr_id1, thr_id2;
    pthread_t p_thread1;
    pthread_t p_thread2;

    struct arg_struct args_p_thread1;
    args_p_thread1.my_id = 1;
    args_p_thread1.other = 2;

    struct arg_struct args_p_thread2;
    args_p_thread2.my_id = 2;
    args_p_thread2.other = 1;

    thr_id1 = pthread_create(&p_thread1, NULL, runner, (void*)&args_p_thread1);
    thr_id2 = pthread_create(&p_thread2, NULL, runner, (void*)&args_p_thread2);

  int join = 0;
    pthread_join(&p_thread1, &join);
  
  pthread_join(&p_thread2, &join);
  
    return 0;
}

answered Oct 20 '22 at 09:19

Samuel Squire

127
3
13

`volatile` is not an appropriate tool for the job -- nor for *any* synchronization job. Using it may happen to improve the observed behavior of the example code in some implementations, but it does not change the fact that the code contains data races -- not only for `turn`, but also for `count`. Making `turn` atomic, on the other hand, combined with using atomic operations with sequential consistency semantics (the default) would do. – John Bollinger Oct 20 '22 at 18:04
John did you run the code? Did you notice the spin lock at the beginning of the loop? Only one thread can run while turn is set to that thread's turn. It needs to be volatile. Volatile is not used for synchronization in the code. Please re-read the code and notice the spinlock. – Samuel Squire Oct 21 '22 at 04:17
There *is no* spin lock without synchronization of some kind for `turn`. This is the essential problem of the original code. Making `turn` atomic would fix that, resolving the data races not only for `turn` itself but also for `count`. Making `turn` volatile does not, but it is particularly pernicious because it might give the appearance of doing so -- until it fails unexpectedly, or on a different machine. – John Bollinger Oct 21 '22 at 11:59
Only one thread can change turn since there is only two threads. One thread is spinning while the other is in the critical section. The turn cannot be modified by multiple threads simultaneously because one thread is spinning. That's how I understand the code. The volatile means that the turn variable shall be visible to other thread when changed in the critical section. I don't think any more synchronization is needed – Samuel Squire Oct 21 '22 at 12:09
[Why is volatile not considered useful in multithreaded C or C++ programming?](https://stackoverflow.com/questions/2484980/why-is-volatile-not-considered-useful-in-multithreaded-c-or-c-programming/2485177#2485177) – John Bollinger Oct 21 '22 at 12:55

What am I getting wrong in this Busy Waiting solution using Strict Alteration with C and Posix threads?

2 Answers2