哲学家问题

哲学家问题

有五个哲学家绕着圆桌坐，每个哲学家面前有一盘面，两人之间有一支筷子，这样每个哲学家左右各有一支筷子。哲学家有2个状态，思考或者拿起筷子吃饭。如果哲学家拿到一只筷子，不能吃饭，直到拿到2只才能吃饭，并且一次只能拿起身边的一支筷子。一旦拿起便不会放下筷子直到把饭吃完，此时才把这双筷子放回原处。如果，很不幸地，每个哲学家拿起他或她左边的筷子，那么就没有人可以吃到饭了。
哲学家进餐问题是一个多线程运用的经典例子，涉及到线程同步/互斥，临界区访问问题以及死锁问题。

可能导致的死锁问题:

如果5个哲学家都去拿他左边的筷子, 再拿右边的筷子, 会导致每个人都在等待筷子, 导致死锁问题.

解决办法1:

最多允许4个哲学家吃饭, 第5个人想要拿筷子, 要阻塞直到有1个哲学家吃完, 释放筷子.
那怎么让第5个线程想要拿筷子前, 阻塞住?

用信号量机制, 信号量初始化为4, 每个线程拿筷子前调用sem_wait(), 吃完后, 调用sem_post(), 这样在第5个线程要拿筷子时, 就会阻塞, 直到有一个线程吃完后才会解除阻塞, 从而避免了死锁.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

#define NUM 4
/**
 * 最多允许4个哲学家吃饭, 第5个想吃要阻塞直到有1个哲学家吃完
 */
pthread_mutex_t chops[5];
sem_t max_philosopher_num;

void think(int i) {
    printf("I am thinking %d\n", i);
    sleep(rand() % 3);
}

void hungry(int i) {
    printf("I am hungry %d\n", i);
    sleep(rand() % 3);
}

void eat(int i) {
    printf("I am eating %d\n", i);
    sleep(rand() % 3);
}

void *philosopher(void *arg) {
    int i = (int) arg;
    think(i);
    hungry(i);

    sem_wait(&max_philosopher_num);
    pthread_mutex_lock(&chops[i]);
    pthread_mutex_lock(&chops[(i + 1) % 5]);

    eat(i);

    pthread_mutex_unlock(&chops[i]);
    pthread_mutex_unlock(&chops[(i + 1) % 5]);
    sem_post(&max_philosopher_num);

    return NULL;
}

int main() {
    pthread_t tid[5];
    srand(time(NULL));

    for (int i = 0; i < 5; ++i) {
        pthread_mutex_init(&chops[i], NULL);
    }
    sem_init(&max_philosopher_num, 0, NUM);

    for (int i = 0; i < 5; ++i) {
        pthread_create(&tid[i], NULL, philosopher, (void *) i);
    }

    for (int i = 0; i < 5; ++i) {
        pthread_join(tid[i], NULL);
    }
    for (int i = 0; i < 5; ++i) {
        pthread_mutex_destroy(&chops[i]);
    }

    sem_destroy(&max_philosopher_num);
    return 0;
}

解决办法2:

如果想给某个哲学家筷子，就将他需要的所有筷子都给他，然后让他进餐，否则就一个都不给他。从而避免了死锁。
怎么实现呢?
搞一个全局互斥量, 然后在某个线程拿筷子前, 先去拿到这个全局互斥量, 然后在拿他所需要的2个筷子, 因为别的线程没有抢到这个互斥量, 所以不能拿筷子, 而在这个互斥量这里阻塞.
所以这个拿到互斥量的线程可以拿到所有的筷子进餐, 在进餐结束后释放这个互斥量即可.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>

/**
 * 如果想给某个哲学家筷子，就将他需要的所有资源都给他，然后让他进餐，否则就一个都不给他。
 */

pthread_mutex_t mutex, chops[5];

void think(int i) {
    printf("I am thinking %d\n", i);
    sleep(rand() % 3);
}

void hungry(int i) {
    printf("I am hungry %d\n", i);
    sleep(rand() % 3);
}

void eat(int i) {
    printf("I am eating %d\n", i);
    sleep(rand() % 3);
}

void *philosopher(void *arg) {
    int i = (int)arg;

    think(i);
    hungry(i);

    pthread_mutex_lock(&mutex); // 阻止其他线程拿筷子
    pthread_mutex_lock(&chops[i]);
    pthread_mutex_lock(&chops[(i + 1) % 5]);
    pthread_mutex_unlock(&mutex);

    eat(i);

    pthread_mutex_unlock(&chops[i]);
    pthread_mutex_unlock(&chops[(i + 1) % 5]);
    return NULL;
}

int main() {
    pthread_t tid[5];
    srand(time(NULL));

    pthread_mutex_init(&mutex, NULL);
    for (int i = 0; i < 5; ++i) {
        pthread_mutex_init(&chops[i], NULL);
    }

    for (int i = 0; i < 5; ++i) {
        pthread_create(&tid[i], NULL, philosopher, (void *)i);
    }

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

    pthread_mutex_destroy(&mutex);
    for (int i = 0; i < 5; ++i) {
        pthread_mutex_destroy(&chops[i]);
    }

    return 0;
}

解决办法3:

让奇数号哲学家先去拿他左边的筷子, 然后再拿他右边的筷子, 偶数号哲学家相反, 这样可以保证至少有一个哲学家可以拿到2个筷子进餐然后再释放2个筷子.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

pthread_mutex_t chops[5];

void think(int i) {
    printf("I am thinking %d\n", i);
    sleep(rand() % 3);
}

void hungry(int i) {
    printf("I am hungry %d\n", i);
    sleep(rand() % 3);
}

void eat(int i) {
    printf("I am eating %d\n", i);
    sleep(rand() % 3);
}

void *philosopher(void *arg) {
    int i = (int)arg;

    think(i);
    hungry(i);

    if (i % 2 == 0) {
        pthread_mutex_lock(&chops[(i + 1) % 5]);
        pthread_mutex_lock(&chops[i]);
        eat(i);
        pthread_mutex_unlock(&chops[i]);
        pthread_mutex_unlock(&chops[(i + 1) % 5]);
    } else {
        pthread_mutex_lock(&chops[i]);
        pthread_mutex_lock(&chops[(i + 1) % 5]);
        eat(i);
        pthread_mutex_unlock(&chops[i]);
        pthread_mutex_unlock(&chops[(i + 1) % 5]);
    }

    return NULL;
}

int main() {
    pthread_t tid[5];
    srand(time(NULL));

    for (int i = 0; i < 5; ++i) {
        pthread_mutex_init(&chops[i], NULL);
    }

    for (int i = 0; i < 5; ++i) {
        pthread_create(&tid[i], NULL, philosopher, (void *)i);
    }

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

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

    return 0;
}

这篇确实有点水…下篇绝对不水 !