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
?