When calling pthread_cond_signal on program with 4 threads, the same thread gets the mutex

Question

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

pthread_t node[4];
pthread_mutex_t token;
pthread_cond_t cond;
int id=0;

void *func(int n)
   {
        int count = 0;
        while (count < 10){
                 pthread_mutex_lock(&token);
                while (id != n){
                        printf("Whoops not my turn, id=%d\n",n);
                        pthread_cond_wait(&cond, &token);}
                //if (id == n){
                        count += 1;
                        printf ("My turn! id= %d\n",n);
                        printf("count %d\n", count);
                        if (id == 3){
                                id = 0;}
                        else{
                                id += 1;}
                        //}else{
                        //      printf("Not my turn! id=%d\n",n);}
                        //      pthread_mutex_unlock(&token);
                        //      sleep(2);}
                        pthread_mutex_unlock(&token);
                        pthread_cond_signal(&cond);}
                        printf ("ID=%d has finished\n",n);

        return(NULL);
   }

int main()
   {
   int i;
   pthread_mutex_init(&token,NULL);
        pthread_cond_init(&cond,NULL);
   for(i=0;i<4;i++)
      pthread_create(&node[i],NULL,(void *)func,(void *)i);

   for(i=0;i<4;i++)
      pthread_join(node[i],NULL);

   pthread_mutex_destroy(&token);

   return 0;
   }

This is my code, it is a C program using threads. I don't think it's purpose needs to be known here, but I will give an example of the problem I have.

Say thread with id 1 (defined by n in func) gets the mutex, and returns "My turn! id=1". When mutex_unlock and cond_signal are called, the next thread to get the mutex will actually be thread with id 1 again, and it will print "Whoops not my turn, id=1". And only then will thread with id 2 get the mutex, and print "My turn! id=2", but when thread with id = 2 will get the mutex after that. Here is my program output:

Whoops not my turn, id=1
Whoops not my turn, id=2
Whoops not my turn, id=3
My turn! id= 0
count 1
Whoops not my turn, id=0
My turn! id= 1
count 1
Whoops not my turn, id=1
My turn! id= 2
count 1
Whoops not my turn, id=2
My turn! id= 3
count 1
Whoops not my turn, id=3
My turn! id= 0
count 2
Whoops not my turn, id=0
My turn! id= 1
count 2
Whoops not my turn, id=1
My turn! id= 2
count 2
Whoops not my turn, id=2
My turn! id= 3
count 2
Whoops not my turn, id=3
My turn! id= 0
count 3
Whoops not my turn, id=0
My turn! id= 1
count 3
Whoops not my turn, id=1
My turn! id= 2
count 3
Whoops not my turn, id=2
My turn! id= 3
count 3
Whoops not my turn, id=3
My turn! id= 0
count 4
Whoops not my turn, id=0
My turn! id= 1
count 4
Whoops not my turn, id=1
My turn! id= 2
count 4
Whoops not my turn, id=2
My turn! id= 3
count 4
Whoops not my turn, id=3
My turn! id= 0
count 5
Whoops not my turn, id=0
My turn! id= 1
count 5
Whoops not my turn, id=1
My turn! id= 2
count 5
Whoops not my turn, id=2
My turn! id= 3
count 5
Whoops not my turn, id=3
My turn! id= 0
count 6
Whoops not my turn, id=0
My turn! id= 1
count 6
Whoops not my turn, id=1
My turn! id= 2
count 6
Whoops not my turn, id=2
My turn! id= 3
count 6
Whoops not my turn, id=3
My turn! id= 0
count 7
Whoops not my turn, id=0
My turn! id= 1
count 7
Whoops not my turn, id=1
My turn! id= 2
count 7
Whoops not my turn, id=2
My turn! id= 3
count 7
Whoops not my turn, id=3
My turn! id= 0
count 8
Whoops not my turn, id=0
My turn! id= 1
count 8
Whoops not my turn, id=1
My turn! id= 2
count 8
Whoops not my turn, id=2
My turn! id= 3
count 8
Whoops not my turn, id=3
My turn! id= 0
count 9
Whoops not my turn, id=0
My turn! id= 1
count 9
Whoops not my turn, id=1
My turn! id= 2
count 9
Whoops not my turn, id=2
My turn! id= 3
count 9
Whoops not my turn, id=3
My turn! id= 0
count 10
ID=0 has finished
My turn! id= 1
count 10
ID=1 has finished
My turn! id= 2
count 10
ID=2 has finished
My turn! id= 3
count 10
ID=3 has finished

As you can see, after each success, and the thread prints "My turn!", it will get the mutex after that and cause an "Whoops not my turn!". I don't understand why this happens as I call pthread_cond_signal, which should signal another thread to wake up before the current thread can reobtain the mutex. Please help me find this solution as I think there is something important I am missing. If my explanation is lacking, please feel free to ask me for more information. Thank you very much for your time!

Answer 1

In the case of Linux, and possibly posix systems in general, there's no guarantee for the order that mutex lock requests get serviced. When the mutex is unlocked, the OS doesn't force a context switch, so the currently running thread continues its loop and locks the mutex again. I don't know if you can change thread priority via the pthread interface, but if this is possible, you could just bump the priority of thread "(n)%4", and when thread "(n)%4" runs, it would set its priority back to normal and set thread "(n+1)%4" to higher priority.

In the case of Windows using its native mutex, apparently the order of lock requests is tracked in a queue or the equivalent, so when the currently running thread loops back to the lock request, Windows will switch to the first thread in a queue of lock requests for the mutex. I don't know if this is documented, but I've confirmed that it works this way. I don't know if pthreads mutex in Windows will work in this manner.

A possible alternative would be one mutex per thread, but I don't know if this would cause any issues depending on the OS. Using one semaphore per thread should work

Side note, if using a condition variable, you can get a spurious wakeup, and will need to handle that situation.

https://en.wikipedia.org/wiki/Spurious_wakeup

However, if using native Windows synchronization types like mutex, semaphore, ..., spurious wakeups will not happen.

For some OS, like Linux, these issues are enough of a problem that some of the high end multi-processing / multi-threading applications install a kernel level driver in order to implement kernel time spin locks to avoid these issues.

https://en.wikipedia.org/wiki/Spinlock

Answer 2

@rcgldr already gave a very good explanation on the timing involved. If you want to increase your odds of giving another thread a chance, try adding a call to pthread_yield, which should give the scheduler the opportunity to pick a different thread, though that won't be a guarantee, either.