Deadlock prevent

Question

Need help how to prevent the deadlock for the code in blow i have written. or any suggestion i need to fix the code in order to get rid of deadlock? also when i run in Linux i got a Segmentation fault (core dumped).

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

int cnt;
int *bites;
int *old_bites;
sem_t *sticks;

void *roger(void *arg) {
    int rog = *(int*)arg;

    for(;;) {
        sem_wait(&(sticks[rog]));             // left
        sem_wait(&(sticks[(rog + 1) % cnt])); // right

        bites[rog]++;

        sem_post(&(sticks[(rog + 1) % cnt])); // right
        sem_post(&(sticks[rog]));             // left
}

pthread_exit(NULL);

return NULL;
}

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

int i;
pthread_t *rogers;
int *pos;
cnt = (int)strtol(argv[1], NULL, 10);

rogers = (pthread_t *)calloc(cnt, sizeof(pthread_t));
pos = (int *)malloc(cnt * sizeof(int));
bites = (int *)calloc(cnt, sizeof(int));
old_bites = (int *)calloc(cnt, sizeof(int));
sticks = (sem_t *)calloc(cnt, sizeof(sem_t));

for(i = 0; i < cnt; i++) {
    sem_init(&(sticks[i]), 0, 1);
}

for(i = 0; i < cnt; i++) {
    pos[i] = i;
    pthread_create(&(rogers[i]), NULL, roger, (void *)&pos[i]);
}

for(;;) {
    bool dead = true;
    usleep(50000);
    for(i = 0; i < cnt; i++) {
        if(bites[i] != old_bites[i]) {
            dead = false;
        }
    }
    if(dead) {
        exit(EXIT_SUCCESS);
    }

    for(i = 0; i < cnt; i++) {
        printf("%8X", bites[i]);
    }
    printf("\n");
    for(i = 0; i < cnt; i++) {
        old_bites[i] = bites[i];
    }
}

for(i = 0; i < cnt; i++) {
    pthread_join(rogers[i], NULL);  
}

for(i = 0; i < cnt; i++) {
    sem_destroy(&(sticks[i]));
}

exit(EXIT_SUCCESS);
}

SegFault and deadlock? Maybe go for the record and add a divide-by-zero? — Martin James, Apr 12 '16 at 17:57
OK, I'll bites. Tell us what you have done so far to debug your app. Which line raises the segfault? — Martin James, Apr 12 '16 at 18:00
https://en.wikipedia.org/wiki/Dining_philosophers_problem#Solutions — user3386109, Apr 12 '16 at 18:01
OP, you need to do some debugging. `gdb` and `valgrind` are incredibly helpful tools, especially where segmentation faults are concerned. More info about that on [this question](http://stackoverflow.com/questions/33047452/definitive-list-of-common-reasons-for-segmentation-faults). Also, @user3386109, my brain immediately registered that link as "bistromath". — CodeMouse92, Apr 12 '16 at 18:28
@JasonMc92 Ahh, that explains the title. OP meant airlock prevent. — user3386109, Apr 12 '16 at 18:38
@user3386109, LOL, let's not confuse the guy. (OP, ignore us, nerd jokes flying here.) — CodeMouse92, Apr 12 '16 at 18:39

score 0 · Answer 1 · answered Apr 12 '16 at 18:56

yes I would expect this to deadlock. I don't know what you're using for cnt, but let's pretend it's 1. In this case, only 1 thread will get created. This thread will sem_wait(&(sticks[0]));. Then in the very next line it will sem_wait(&(sticks[(0+1) % 1 == 0]));. Since the initial value of your semaphores are 1, you can't wait on the same semaphore twice without a sem_post first. Thus, this thread will wait forever for a sem_post that it can't reach because it's sem_waiting.

Now consider the case where cnt > 1 (let's just say cnt == 2 to make it simpler). This will spawn thread0 and thread1 with 0 and 1 passed as arguments to their functions. This situation could happen:

Thread0 executes sem_wait(&(sticks[0]));
Context switch: thread1 executes sem_wait(&(sticks[1]));
thread1 executes sem_wait(&(sticks[(1+1) % 2 == 0])); // this blocks because thread0 has already sem_wait'ed this semaphore to 0
Context switch: thread0 executes sem_wait(&(sticks[(0+1) % 2 == 1])); // this blocks because thread1 has already sem_wait'ed this semaphore to 0

Now you have each thread waiting for a sem_post from the other before you can continue ==> deadlock. I would expect this scenario to scale for increasing values of cnt, although the situations that would lead to deadlocks would become more complex.

Why are you using 2 semaphores to protect a single resource? This theory sounds wrong to me. You lose your atomicity with that approach (correct me if I'm wrong obviously).

Also, you have a race condition with your bites array. The main thread isn't observing synchronization before it reads from it. This may be related to the seg fault.

so i have fixed segFault, and is deadlock program will not end? and continuously print out output? — littlerain, Apr 14 '16 at 00:19
@littlerain From the code provided I expect your worker threads to eventually deadlock. All the printing happens in the main loop, which enters an infinite `for` loop and will exit if `dead` becomes true. This might happen sometimes, it might not. The `pthread_join` and `sem_destroy` loops will never be reached. I think your array of semaphores is a logical error. You should only have one. By using more than one semaphore in this way to protect a single resource (`bites` array) you remove the atomicity that thread synchronization is based on. — yano, Apr 14 '16 at 14:35

Deadlock prevent

1 Answers1