哲学家就餐问题与银行家算法.pptx

哲学家就餐问题与银行家算法/q435201823/article/details/103542909#_1哲学家就餐问题/q435201823/article/details/103542909#_4解题思路/q435201823/article/details/103542909#_32问题解决/q435201823/article/details/103542909#_34方法一/q435201823/article/details/103542909#_55方法二/q435201823/article/details/103542909#_90方法三目 录/q435201823/article/details/103542909#_121银行家算法/q435201823/article/details/103542909#_123安全状态/q435201823/article/details/103542909#_143银行家算法的数据结构/q435201823/article/details/103542909#_150银行家算法/q435201823/article/details/103542909#_160安全性算法/q435201823/article/details/103542909#_179银行家算法实例 哲学家就餐问题该问题描述的是五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替的进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。 解题思路这段伪代码的思路很明确，这个函数代表的是一个哲学家的活动，可以将其创建为五个不同的线程代表五位不同的哲学家。每位哲学家先思考，当某位哲学家饥饿的时候，就拿起他左边的筷子，然后拿起他右边的筷子，然后进餐，然后放下他左右的筷子并进行思考。因为筷子是临界资源，所以当一位哲学家拿起他左右的筷子的时候，就会对他左右的筷子进行加锁，使其他的哲学家不能使用，当该哲学家进餐完毕后，放下了筷子，才对资源解锁，从而使其他的哲学家可以使用。? 这个过程看似没什么问题，但是当你仔细分析之后，你会发现这里面有一个很严重的问题，就是死锁，就是每个线程都等待其他线程释放资源从而被唤醒，从而每个线程陷入了无限等待的状态。在哲学家就餐问题中，一种出现死锁的情况就是，假设一开始每位哲学家都拿起其左边的筷子，然后每位哲学家又都尝试去拿起其右边的筷子，这个时候由于每根筷子都已经被占用，因此每位哲学家都不能拿起其右边的筷子，只能等待筷子被其他哲学家释放。由此五个线程都等待被其他进程唤醒，因此就陷入了死锁。因为是五位哲学家，并且每位哲学家的各自做自己的事情（思考和吃饭），因此可以创建五个线程表示五位哲学家，五个线程相互独立（异步）。并对五位哲学家分别编号为0~4。? 同时，有五根筷子，每根筷子只对其相邻的两位哲学家是共享的，因此这五根筷子可以看做是五种不同的临界资源（不是一种资源有5个，因为每根筷子只能被固定编号的哲学家使用）。并对五根筷子分别编号为0~4，其中第i号哲学家左边的筷子编号为i，则其右边的筷子编号就应该为(i + 1) % 5。? 因为筷子是临界资源，因此当一个线程在使用某根筷子的时候，应该给这根筷子加锁，使其不能被其他进程使用。? 根据以上分析，可以使用pthread_create函数创建五个线程，可以使用pthread_mutex_t chops[5]表示有五根筷子，五个不同的临界资源，并用pthread_mutex_init(&chops[i], NULL);来初始化他们。根据上面的分析，可以得到一个基本的解决方案如下： 问题解决 方法一第一种解决死锁问题的办法就是同时只允许四位哲学家同时拿起同一边的筷子，这样就能保证一定会有一位哲学家能够拿起两根筷子完成进食并释放资源，供其他哲学家使用，从而实现永动，避免了死锁。举个最简单的栗子，假定0~3号哲学家已经拿起了他左边的筷子，然后当4号哲学家企图去拿他左边的筷子的时候，将该哲学家的线程锁住，使其拿不到其左边的筷子，然后其左边的筷子就可以被3号哲学家拿到，然后3号哲学家进餐，释放筷子，然后更多的哲学家拿到筷子并进餐。? 如何才能实现当4号哲学家企图拿起其左边的筷子的时候将该哲学家的线程阻塞？这个时候就要用到该问题的提出者迪杰斯特拉（这货还提出了迪杰斯特拉最短路径算法，著名的银行家算法也是他发明的）提出的信号量机制。因为同时只允许有四位哲学家同时拿起左筷子，因此我们可以设置一个信号量r，使其初始值为4，然后每当一位哲学家企图去拿起他左边的筷子的时候，先对信号量做一次P操作，从而当第五位哲学家企图去拿做筷子的时候