死锁四要素:
互斥条件: 至少有一个资源不能共享，即一次只能被一个进程/线程占用
占用和等待: 一个进程/线程持有资源A并且等待其他进程释放资源B。
非抢占: 一个进程/线程不能无缘无故从另一个进程/线程抢占资源，只能等待其使用完资源之后自动释放
循环等待: 一组进程/线程形成一种循环等待资源的关系。每个进程/线程都在等待下一个进程/线程所持有的资源。
避免死锁只要破坏上面任何一个条件即可。
哲学家进餐问题描述:
哲学家进餐问题是一个经典的并发编程问题，描述了五位哲学家围坐在圆桌前，每人面前放着一碗意大利面和一只叉子。他们只有在两只叉子都拿到手才能吃意大利面，吃完后才能放下叉子继续思考。问题是如何设计算法，使得哲学家们能够正确地进餐而不发生死锁（每个哲学家都在等待右边的叉子）或饥饿（某些哲学家始终无法拿到叉子）的情况。
方案一: 限制同时吃饭人数避免死锁，对应打破死锁的循环等待这个必要条件。
为什么限制同时吃饭人数可以避免死锁？
根据抽屉原理: K = N * (R) + 1 // K 是资源数， N 进程数，R 是每个进程需要获取的资源数量
资源数量大于需求数量，必然有一个哲学家可以拿到2个筷子进餐。打破死锁必要条件：循环等待(压根不用循环)
哲学家问题 K = 5 ，R = 1 得出 N = 4，即同时允许四个哲学家线程用餐, 至于能否用餐还是看筷子的互斥锁。
主要代码实现:
pthread_mutex_t forks[NUM_PHILOSOPHERS]; //每个叉子资源访问的互斥锁
sem_t *max_philosophers; //限制同时最多哲学家进餐人数
//最多支持NUM_PHILOSOPHERS - 1,个人用餐，抽屉原理可知 最少有一个人手上会拿到两把叉子 max_philosophers = sem_open("max_philosophers", O_CREAT | O_EXCL, 0666, NUM_PHILOSOPHERS - 1);
static void *philosopher(void *arg) {
int i = *(int *)arg; //当前哲学家编号
int leftFork = (i + NUM_PHILOSOPHERS - 1) % NUM_PHILOSOPHERS;
int rightFork = (i + 1) % NUM_PHILOSOPHERS;
while (1)
{
sem_wait(max_philosophers);
printf("Philosopher %d is thinking.\n", i);
pthread_mutex_lock(&forks[leftFork]);
pthread_mutex_lock(&forks[rightFork]);
printf("Philosopher %d is eating.\n", i);
sleep(1);
pthread_mutex_unlock(&forks[leftFork]);
pthread_mutex_unlock(&forks[rightFork]);
sem_post(max_philosophers);
sleep(1);
}
return NULL;
}
方案二: 根据哲学家编码奇偶按照不同顺序获取不同的筷子. 打破互斥和循环条件，抢占和等待条件也占了点边。
主要代码:
#define NUM_PHILOSOPHERS 5
pthread_mutex_t forks[NUM_PHILOSOPHERS]; //叉子的互斥锁
//拿起筷子
void pickup_forks(int leftfork, int rightfork, int philosopher_id) {
pthread_mutex_lock(&forks[leftfork]);
pthread_mutex_lock(&forks[rightfork]);
printf("Philosopher %d is eating.\n", philosopher_id);
}
//放下筷子
void return_forks(int leftfork, int rightfork) {
pthread_mutex_unlock(&forks[leftfork]);
pthread_mutex_unlock(&forks[rightfork]);
}
static void *philosopher(void *arg) {
int i = *(int *)arg;
int leftfork = (i + NUM_PHILOSOPHERS - 1) % NUM_PHILOSOPHERS;
int rightfork = (i + 1) % NUM_PHILOSOPHERS;
while (1)
{
if (i % 2 == 0) {
pickup_forks(leftfork, rightfork, i);
} else {
pickup_forks(rightfork, leftfork, i);
}
sleep(1);
return_forks(leftfork, rightfork);
sleep(1);
}
return NULL;
}
非抢占 条件就不举例了:
因为一旦涉及到非抢占，必然会引入线程优先级的问题，比如A哲学家的线程优先级高但是资源被优先级低的B哲学家线程抢占，那么系统调度会让B释放,让给A。如果A频繁的吃，B 线程哲学家总有一天会被饿死。A 也会被活活撑死。。。
吸烟者问题描述：
三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西:烟草、纸和火柴，供应者有丰富货物提供。 三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。 供应者随机地将两样不同的东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。 当吸烟者完成吸烟后唤醒供应者，供应者再随机地把两样不同的东西放在桌子上，唤醒一个吸烟者。
这里核心问题就是一个: 当前抽烟者手里拿的资源，然后这个资源准备好之后，让供应者释放资源信号。所以互斥的信号量是当前抽烟人手里的资源，而不是另外两种资源。当初看这个问题时候总是会被另外两个资源印象。这个思路是不对的
代理商放资源需要抽烟者线程激活。抽烟者线程也靠代理商当前手里的资源激活，形成互斥。
吸烟者问题 理解之后实现比较简单，代码就不贴了。有兴直接去翻源码即可。
网友评论