philosophers_deadlock

Philosophers’ Deadlock

Recently, I learnt about the Philosophers’ Deadlock problem in operating systems courses.

Here is the original code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// philosophers_deadlock.c
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

#define NUM_PHILOSOPHERS 5

pthread_mutex_t forks[NUM_PHILOSOPHERS];

void* philosopher(void* num) {
    int id = *(int*)num;

    int left_fork = id;
    int right_fork = (id + 1) % NUM_PHILOSOPHERS;

    while (1) {
        printf("Philosopher %d is thinking.\n", id);
        usleep(10000);  // Sleep for 0.01 seconds

        pthread_mutex_lock(&forks[left_fork]);
        printf("Philosopher %d picked up left fork.\n", id);
        pthread_mutex_lock(&forks[right_fork]);
        printf("Philosopher %d picked up right fork and starts eating.\n", id);

        usleep(10000);  // Sleep for 0.01 seconds

        pthread_mutex_unlock(&forks[right_fork]);
        printf("Philosopher %d put down right fork.\n", id);
        pthread_mutex_unlock(&forks[left_fork]);
        printf("Philosopher %d put down left fork.\n", id);
    }

    return NULL;
}

int main() {
    pthread_t philosophers[NUM_PHILOSOPHERS];
    int philosopher_numbers[NUM_PHILOSOPHERS];

    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_mutex_init(&forks[i], NULL);
        philosopher_numbers[i] = i;
    }

    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_create(&philosophers[i], NULL, philosopher, &philosopher_numbers[i]);
    }

    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_join(philosophers[i], NULL);
    }

    for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
        pthread_mutex_destroy(&forks[i]);
    }

    return 0;
}

It looks not bad, but it has a problem: deadlock.

When all philosophers pick up their left forks, they will wait for the right forks, which are held by their neighbors. This leads to a deadlock situation where no philosopher can eat.

To solve this problem, I have two solutions:

Solution 1: Change the order of picking up forks

In this solution, I will change the order of picking up forks. The odd-numbered philosophers will pick up the right fork first, and then the left fork. The even-numbered philosophers will pick up the left fork first, and then the right fork.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// philosophers_deadlock_mutex.c
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

#define NUM_PHILOSOPHERS 5

pthread_mutex_t forks[NUM_PHILOSOPHERS];

void *philosopher(void *num)
{
    int id = *(int *)num;

    // int left_fork = id;
    // int right_fork = (id + 1) % NUM_PHILOSOPHERS;
    int left_fork, right_fork;
    if (id % 2 == 0)
    {
        // 偶数id的哲学家先拿左边的叉子
        left_fork = id;
        right_fork = (id + 1) % NUM_PHILOSOPHERS;
    }
    else
    {
        // 奇数id的哲学家先拿右边的叉子
        left_fork = (id + 1) % NUM_PHILOSOPHERS;
        right_fork = id;
    }

    while (1)
    {
        printf("Philosopher %d is thinking.\n", id);
        usleep(10000); // Sleep for 0.01 seconds

        pthread_mutex_lock(&forks[left_fork]);
        printf("Philosopher %d picked up left fork.\n", id);
        pthread_mutex_lock(&forks[right_fork]);
        printf("Philosopher %d picked up right fork and starts eating.\n", id);

        usleep(10000); // Sleep for 0.01 seconds

        pthread_mutex_unlock(&forks[right_fork]);
        printf("Philosopher %d put down right fork.\n", id);
        pthread_mutex_unlock(&forks[left_fork]);
        printf("Philosopher %d put down left fork.\n", id);
    }

    return NULL;
}

int main()
{
    pthread_t philosophers[NUM_PHILOSOPHERS];
    int philosopher_numbers[NUM_PHILOSOPHERS];

    for (int i = 0; i < NUM_PHILOSOPHERS; i++)
    {
        pthread_mutex_init(&forks[i], NULL);
        philosopher_numbers[i] = i;
    }

    for (int i = 0; i < NUM_PHILOSOPHERS; i++)
    {
        pthread_create(&philosophers[i], NULL, philosopher, &philosopher_numbers[i]);
    }

    for (int i = 0; i < NUM_PHILOSOPHERS; i++)
    {
        pthread_join(philosophers[i], NULL);
    }

    for (int i = 0; i < NUM_PHILOSOPHERS; i++)
    {
        pthread_mutex_destroy(&forks[i]);
    }

    return 0;
}

This solution works because it prevents the circular wait condition that leads to deadlock. By ensuring that odd-numbered philosophers pick up the right fork first, we break the cycle of dependencies.

Solution 2: Use condition variables

In this solution, I will use pthread_cond_t to implement a condition variable. Each philosopher will wait for the condition variable to be signaled before picking up the left fork and right fork at the same time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// philosophers_deadlock_cond.c
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdbool.h>

#define NUM_PHILOSOPHERS 5

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond[NUM_PHILOSOPHERS];
bool fork_available[NUM_PHILOSOPHERS] = {true, true, true, true, true};

void *philosopher(void *num)
{
    int id = *(int *)num;

    int left_fork = id;
    int right_fork = (id + 1) % NUM_PHILOSOPHERS;

    while (1)
    {
        printf("Philosopher %d is thinking.\n", id);
        usleep(10000); // Sleep for 0.01 seconds

        pthread_mutex_lock(&mutex);

        // wait two forks to be available
        while (!fork_available[left_fork] || !fork_available[right_fork])
        {
            pthread_cond_wait(&cond[id], &mutex);
        }

        // pick up forks
        fork_available[left_fork] = false;
        fork_available[right_fork] = false;

        printf("Philosopher %d picked up left fork %d and right fork %d and starts eating.\n", id, left_fork, right_fork);

        pthread_mutex_unlock(&mutex);

        usleep(10000); // eat for 0.01 seconds

        pthread_mutex_lock(&mutex);

        // put down forks
        fork_available[left_fork] = true;
        fork_available[right_fork] = true;
        printf("Philosopher %d put down left fork %d and right fork %d.\n", id, left_fork, right_fork);

        // signal other philosophers waiting for forks
        pthread_cond_signal(&cond[left_fork]);
        pthread_cond_signal(&cond[right_fork]);

        pthread_mutex_unlock(&mutex);
    }

    return NULL;
}

int main()
{
    pthread_t philosophers[NUM_PHILOSOPHERS];
    int philosopher_numbers[NUM_PHILOSOPHERS];

    for (int i = 0; i < NUM_PHILOSOPHERS; i++)
    {
        pthread_cond_init(&cond[i], NULL);
        philosopher_numbers[i] = i;
    }

    for (int i = 0; i < NUM_PHILOSOPHERS; i++)
    {
        pthread_create(&philosophers[i], NULL, philosopher, &philosopher_numbers[i]);
    }

    for (int i = 0; i < NUM_PHILOSOPHERS; i++)
    {
        pthread_join(philosophers[i], NULL);
    }

    for (int i = 0; i < NUM_PHILOSOPHERS; i++)
    {
        pthread_cond_destroy(&cond[i]);
    }
    pthread_mutex_destroy(&mutex);

    return 0;
}

Initially, all forks are available. When a philosopher wants to eat, they check if both forks are available. If not, they wait on the condition variable until they are signaled. After eating, they put down the forks and signal other philosophers waiting for those forks.

This solution also works because it prevents the circular wait condition by allowing philosophers to wait for both forks to be available before proceeding. It also allows for more flexibility in the order of picking up forks, as philosophers can pick them up in any order as long as they wait for both to be available.

Conclusion

Both solutions effectively solve the deadlock problem in the Philosophers’ Deadlock problem. The first solution is simpler and easier to understand, while the second solution is more flexible and allows for more complex scenarios.