Prerequisite: Multithreading (computer architecture) - Wikipedia, Lock (computer science) - Wikipedia, Condition variable

Abstract: As we all know lock can prevent multip threads access the same data at the same time. Once a thread gets the lock it can access the data. However, in some situations, we need to wait until some conditions become true to be able to continue. To implement this demand we can use condition variable like this below.

pthread_mutex_lock(&m); // m is mutex
while(done==0){
    pthread_cond_wait(m,cond); // cond is condition variable
}
// modify data in here
pthread_mutex_unlock(&m);

When a thread executes the pthread_cond_wait function, the thread will release mutex m and enter a sleep state. When the other thread wakes it up by signaling or broadcasting, it will require the lock before continuing. However, what if the lock holder didn’t release the lock when invoking the signal or broadcast method? This situation is called spurious wakeup. In this article, we will talk about the formation of spurious wakeup and how to overcome it.

Code example: We use the classical producer/consumer example to analyze.

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

pthread_mutex_t mutex;
pthread_cond_t cond;

int buffer[100];

int loops = 5;
int length = 0;

void *producer(void *arg) {
    int i,j;
    for (i = 0; i < loops; i++) {
    pthread_mutex_lock(&mutex);
    buffer[length++] = i;
    printf("producer length %d\n", length);
    pthread_cond_signal(&cond);
    pthread_mutex_unlock(&mutex);
    }
}

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
    pthread_mutex_lock(&mutex);
    while(length == 0) {
        printf(" consumer waiting...\n");
        pthread_cond_wait(&cond, &mutex);
    }
    int item = buffer[--length];
    printf("Consumer %d\n", item);
    pthread_mutex_unlock(&mutex);
    }
}

int main(int argc, char *argv[])
{

    pthread_mutex_init(&mutex, 0);
    pthread_cond_init(&cond, 0);

    pthread_t pThread, cThread;
    pthread_create(&pThread, 0, producer, 0);
    pthread_create(&cThread, 0, consumer, 0);
    pthread_join(pThread, NULL);
    pthread_join(cThread, NULL);

    pthread_mutex_destroy(&mutex);
    pthread_cond_destroy(&cond);
    return 0;
}

In the example above, we create two threads. One thread produces an element to array buffer every time, the other consumes an element every time.

We can notice that when the producer thread sends a signal the lock didn’t release yet.

What will happen in this situation?

When the producer thread singling and consumer thread receive the signal, the consumer thread will enter the waiting queue of the lock.

In respect of producer thread, you wakeup a thread knowing they may not be processed immediately, because the lock is still in your hand. This phenomenon is called spurious wakeup.

The behavior will waste some time to context switch in one core CPU. The consumer thread has to check the lock release or not regularly.

In our example, when the lock is released in the producer thread, it can’t guarantee the consumer thread gets the lock because both the producer and consumer thread enter the waiting queue(the producer thread enters the waiting queue in the next loop) for the lock. The lock will be assigned randomly.

The timing of lock is released

Obviously, the timing of the lock being released is not the best time.

Before we want to research when is the best time, we should know what if we forget to wakeup the other thread.

You can try to comment out this line: pthread_cond_signal(&cond);

You will find after printing “consumer waiting” and producing five times, the process is blocked due to consumer thread didn’t be waked up. (Note: not every time is such a situation because producer may execute first even we create consumer first.) So we know producer thread is created first, then enter waiting process releases the mutex and never get back due to not be waked up. At this time, if we see process status using ps -x, we can see that the process status is Sl+ which means it’s a multi-threaded process and interruptible sleep (waiting for an event to complete).

If we singling the consumer thread only in the first-time loop like the code below, we can see the program run normally.

    for (i = 0; i < loops; i++)
    {
        pthread_mutex_lock(&mutex);
        buffer[length++] = i;
        printf("producer length %d\n", length);
        if(i==0){
            pthread_cond_signal(&cond);
        }
        pthread_mutex_unlock(&mutex);
    }

So we can know even consumer thread is signaled the first time loop, it will enter the waiting queue and get the lock at last. Although the behavior is waste of time, it works.

To improve efficiency, we should delay the time of wakeup the other thread as possible and avoid spurious wakeup. The former is hard to implement in a real-world situation, so we talk about the latter in this article.

Can we unlock mutex before broadcast/signal ? Not in all cases. In our example, we can change the order between releasing the lock and sending a signal like this. … printf(“producer length %d\n”, length); pthread_mutex_unlock(&mutex); pthread_cond_signal(&cond); … If we haven’t loop in the producer thread, the consumer thread will get the lock and execute immediately.

However, consider a situation you need to access a counter variable and confirm it’s zero to send a signal. You cannot change the order between releasing the lock and sending a signal. Code example:

lock(m);
counter--;
if(counter==0){
  signal(&con)
}
unlock(m)

In the case above, you cannot move if clause outside the lock scope, because the counter may change after unlocking.

That’s all. Thanks for reading.