Exercise – Synchronization between threads using `pthread_mutex_t` and `pthread_cond_t`

Question

I have got an assignment for an OS course that consists in the use of mutex and condition variables to synchronize N threads, each involved in the search of a character in a row of a NxN matrix.

The first thread to find the character should "notify" the others that it did, so that the other threads stop looking for it.

I wrote a solution, then tried to improve it further, but I'm not so sure about the improved version.

First version

#include <pthread.h>
#include <printf.h>
#include <unistd.h>
#include <memory.h>

#define N 3

char chars[N][N] = {
    {'d', 'b', 'c'},
    {'a', 'd', 'f'},
    {'d', 'h', 'i'}
};

char to_find = 'd';

struct {
    pthread_mutex_t mutex;
    pthread_cond_t cond;
    ssize_t row;
    ssize_t col;
} pos = {PTHREAD_MUTEX_INITIALIZER, PTHREAD_COND_INITIALIZER, -1, -1};

void *find_char(void *params) ;
pthread_t threads[N];

int main () {
    int rows[N];
    int i;

    for (i = 0; i < N; ++i) rows[i] = i;
    for (i = 0; i < N; ++i) pthread_create(&threads[i], NULL, find_char, &rows[i]);
    pthread_cond_wait(&pos.cond, &pos.mutex);
    printf("character found at position [%ld][%ld]", pos.row, pos.col); fflush(stdout);
    return NULL;
}

void *find_char(void *params) {
    const int row = *((int *) params);

    char buff[BUFSIZ];

    sprintf(buff, "starting search on row %d\n", row);
    write(STDOUT_FILENO, buff, strlen(buff));

    int j;
    for (j = 0; j < N; ++j) {
        if (chars[row][j] == to_find) {
            // if two threads find char at the same time
            // only first one must get to signal main thread
            // and cancel the other threads
            pthread_mutex_lock(&pos.mutex);
            if (pos.row >= 0) {
                pthread_mutex_unlock(&pos.mutex);
                return NULL;
            }

            sprintf(buff, "thread %d found the char\n", row);
            write(STDOUT_FILENO, buff, strlen(buff));

            for (int i = 0; i < N; ++i)
                if (i != row) {
                    sprintf(buff, "cancelling thread %d\n", row);
                    write(STDOUT_FILENO, buff, strlen(buff));

                    pthread_cancel(threads[i]);
                }

            pos.row = row;
            pos.col = j;
            pthread_mutex_unlock(&pos.mutex);

            pthread_cond_signal(&pos.cond);
        }
    }
    return NULL;
}

I used the global threads because I found it easier to worry about one this less while writing my first mutex code.

The second iteration consists of trying to remove that.

Second version

#include <pthread.h>
#include <printf.h>
#include <unistd.h>
#include <memory.h>

#define N 3

char chars[N][N] = {
        {'d', 'b', 'c'},
        {'a', 'd', 'f'},
        {'d', 'h', 'i'}
};

char to_find = 'd';

struct {
    pthread_mutex_t mutex;
    pthread_cond_t cond;
    ssize_t row;
    ssize_t col;
} pos = {PTHREAD_MUTEX_INITIALIZER, PTHREAD_COND_INITIALIZER, -1, -1};

void *find_char(void *params) ;

int main () {
    pthread_t threads[N];
    int rows[N];

    for (int i = 0; i < N; ++i) rows[i] = i;
    for (int i = 0; i < N; ++i) pthread_create(&threads[i], NULL, find_char, &rows[i]);
    pthread_cond_wait(&pos.cond, &pos.mutex);
    for (int i = 0; i < N; ++i) pthread_cancel(threads[i]);
    printf("character found at position [%ld][%ld]", pos.row, pos.col); fflush(stdout);
    return NULL;
}

void *find_char(void *params) {
    const int row = *((int *) params);

    char buff[BUFSIZ];

    sprintf(buff, "starting search on row %d\n", row);
    write(STDOUT_FILENO, buff, strlen(buff));

    int col;
    for (col = 0; col < N; ++col) {
        if (chars[row][col] == to_find) {
            pthread_mutex_lock(&pos.mutex);
            if (pos.row >= 0) {
                pthread_mutex_unlock(&pos.mutex);
                return NULL;
            }

            sprintf(buff, "thread %d found the char\n", row);
            write(STDOUT_FILENO, buff, strlen(buff));

            pos.row = row;
            pos.col = col;
            pthread_cond_signal(&pos.cond);

            pthread_mutex_unlock(&pos.mutex);
        }
    }
    return NULL;
}

The main doubt I have got about this is the following:

What happens if the main thread cancels a thread that has entered the critical section and has locked the mutex?

If a cancel request is issued while a thread has locked the mutex, will it be canceled? Will the mutex stay locked? If yes, what do we usually do to prevent this condition?

---

P.S. Bonus points

I just re-read the code and – whilst I'm learning more on condition variables – I noticed I am using a condition variable in a way that is not exactly what it was intended for. In fact, now that I think about it, I could just use the pos.mutex, swap the pthread_cond_wait with two pthread_mutex_lock calls, swap pthread_cond_signal with a pthread_mutex_unlock call and I'd have the same result, without even declaring the conditional variable.

Why do we even need a condition variable in C? Can't we always use a mutex to replace them?

In particular, what are the differences between the lock/unlock operations on a mutex that's been initialized with PTHREAD_MUTEX_INITIALIZER and locked once, and the wait/signal operations for a condition variable that's been initialized with PTHREAD_COND_INITIALIZER?

Answer 1

Just looking at the second version of the code.

1. Bug

If I remove the lines:

sprintf(buff, "starting search on row %d\n", row);
write(STDOUT_FILENO, buff, strlen(buff));

and re-run the program, I sometimes get the output:

thread 0 found the char
thread 2 found the char
character found at position [2][0]

Two of the threads found the character and updated the pos structure. But this should be impossible because the pos structure is protected by a mutex.

How did this happen? Well, if you read the POSIX specification for pthread_cond_wait, you'll see that it says:

The pthread_cond_timedwait() and pthread_cond_wait() functions shall block on a condition variable. The application shall ensure that these functions are called with mutex locked by the calling thread; otherwise, an error (for PTHREAD_MUTEX_ERRORCHECK and robust mutexes) or undefined behavior (for other mutexes) results.

(My emphasis.) So you are seeing undefined behaviour from the main thread calling pthread_cond_wait without having locked the corresponding mutex. What you need instead is:

pthread_mutex_lock(&pos.mutex);
pthread_cond_wait(&pos.cond, &pos.mutex);
pthread_mutex_unlock(&pos.mutex);

(But with result-checking; see §2.5 below.)

2. Other review points

1. The code doesn't compile without warnings:

   clang -Wall -Wextra cr163538.c
   cr163538.c:34:12: warning: incompatible pointer to integer conversion returning
         'void *' from a function with result type 'int' [-Wint-conversion]
       return NULL;
              ^~~~
   

   main is declared as returning int, so you need to write:

   return 0;
   

   or (more clearly):

   return EXIT_SUCCESS;
   

   Where EXIT_SUCCESS is a constant declared in <stdlib.h>.

2. <printf.h> is not a standard header. The functions printf and sprintf are declared in the standard header <stdio.h>.

3. <memory.h> is not a standard header. The function strlen is declared in the standard header <string.h>.

4. Instead of:

   sprintf(buff, "starting search on row %d\n", row);
   write(STDOUT_FILENO, buff, strlen(buff));
   

   it would be simpler to use standard I/O:

   printf("starting search on row %d\n", row);
   

   It's not clear what you are hoping to gain by the more complicated approach.

5. The code does not check the results of functions that might fail. pthread_create, pthread_cond_wait, pthread_cancel, pthread_mutex_lock, pthread_mutex_unlock and pthread_cond_signal can all fail.

   It is always worth checking the result of a function that might fail: even if you are sure that it can't fail, you might have made a programming error (as in §1 above).

   Result-checking is very repetitive, so it's a good idea to use a macro:

   /* If result is not 0, print error message and exit. */
   static void check(int result, const char *message)
   {
       if (result != 0) {
           char buffer[256];
           strerror_r(result, buffer, sizeof buffer);
           fprintf(stderr, "%s: %s\n", message, buffer);
           exit(EXIT_FAILURE);
       }
   }
   
   /* Check that expr evaluate to 0, otherwise fail. */
   #define CHECK(expr) check(expr, #expr)
   

   and then you can write:

   CHECK(pthread_mutex_lock(&pos.mutex));
   CHECK(pthread_cond_wait(&pos.cond, &pos.mutex));
   CHECK(pthread_mutex_unlock(&pos.mutex));
   

3. Answers to questions

1. What happens if the main thread cancels a thread that has entered the critical section and has locked the mutex?

   The PThreads specification does not say. So you have to assume the worst — maybe the mutex remains locked and cannot be unlocked.

2. Why do we even need a condition variable in C? Can't we always use a mutex to replace them?

   Condition variables can be signalled multiple times, causing multiple waiters to run. Whereas a mutex can only be unlocked once.

3. How can multiple waiters be possible when we have to lock the mutex before to wait anyway?

   Read on in the documentation for pthread_cond_wait and you'll see that it says:

   These functions atomically release mutex and cause the calling thread to block on the condition variable cond.

   So when you call pthread_cond_wait it immediately unlocks the mutex, allowing another thread to lock the mutex and wait on the condition.