linux下经典同步问题,Linux经典同步问题2-哲学家就餐问题

死锁

死锁是 《操作系统原理》课程中的1个很重要的概念, 它描述的是多个进程因竞争资源而造成的1种僵局 ,若无外力作用 ,这些进程将永远不能再向前推进。产生死锁的原因主要有2点: 1是竞争资源 ; 2是进程推进顺序不当。

1、哲学家就餐问题

一张圆桌上坐着 5 名哲学家，桌子上每两个哲学家之间摆了一根叉子，桌子的中间是一碗米饭，如图所示，并且假如按照下面方式进行编号，那么第i为科学家，它的左手边筷子是i，右手边筷子是(i+1)%5。

一般性描述：在实际的计算机问题中，缺乏餐叉可以类比为缺乏共享资源。一种常用的计算机技术是资源加锁，用来保证在某个时刻，资源只能被一个程序或一段代码访问。当一个程序想要使用的资源已经被另一个程序锁定，它就等待资源解锁。当多个程序涉及到加锁的资源时，在某些情况下就有可能发生死锁。例如，某个程序需要访问两个文件，当两个这样的程序各锁了一个文件，那它们都在等待对方解锁另一个文件，而这永远不会发生。

1、最直观错误的解法1

这里要开5个线程，每个哲学家对应一个线程。最开始想到的办法是：每个哲学家先拿起左叉子，再拿起右叉子。并定义互斥信号量数组chopstick[5] = {1,1,1,1,1}用于对5根叉子的互斥访问

伪代码：

#define N 5//哲学家数目

semaphore chopstick[5] = {1,1,1,1,1}//信号量数组,信号量初始化为1互斥访问每根叉子，对叉子进行互斥量保护

void philosopher(int i)//哲学家编号，从0-4

{

while(ture){

think();//想事情，独立，根本不需要保护

down(&chopstick[i]);//拿左手边筷子

down(&chopstick[(i+1)%N]);//拿右手边筷子

eat();

up(&chopstick[i]);//放回左手边筷子

up(&chopstick[(i+1)%N]);//放回右手边筷子

}

}

通过相当于通过信号量保护共享资源，每个线程需要两份，所以每次需要获取两个信号量。但是上面可能出现死锁，那就是5个哲学家同时拿起左边筷子，那么将没有人可以拿到右边快子，于是产生死锁。

2、信号量机制解决哲学家就餐问题

先来两个结论：

(1)系统中有N个并发进程。 若规定每个进程需要申请2个某类资源， 则当系统提供N+1个同类资源时，无论采用何种方式申请资源， 一定不会发生死锁。分析：N+1个资源被N个进程竞争，由抽屉原理可知，则至少存在一个进程获2个以上的同类资源。这就是前面提到的哲学家就餐问题中5个哲学家提供6支筷子时一定不会发生死锁的原因。

(2)系统中有N个并发进程。 若规定每个进程需要申请R个某类资源， 则当系统提供K＝N*(R-1)+1个同类资源时，无论采用何种方式申请使用，一定不会发生死锁。分析：在最坏的情况下，每个进程都申请到R-1个同类资源， 此时它们均阻塞。 试想若系统再追加一个同类资源， 则N 个进程中必有一个进程获得R个资源，死锁解除。

结合以上分析，哲学家就餐问题可以被抽象描述为：系统中有5个并发进程， 规定每个进程需要申请2个某类资源。 若系统提供5个该类资源， 在保证一定不会产生死锁的前提下，最多允许多少个进程并发执行？假设允许N个进程， 将R=2,K=5带入上述公式， 有N*(2-1)+1=5所以N=4。也就意味着，如果在任何时刻系统最多允许4个进程并发执行， 则一定不会发生死锁。 大多数哲学家就餐问题死锁阻止算法都是基于这个结论。 增加一个信号量，控制最多有4个进程并发执行

#define N 5//哲学家数目

semaphore chopstick[5] = {1,1,1,1,1};//信号量数组,信号量初始化为1互斥访问每根叉子，对叉子进行互斥量保护

semaphore mutex = 4;//控制哲学家数量

void philosopher(int i)//哲学家编号，从0-4

{

while(ture){

think();//想事情，独立，根本不需要保护

down(&mutex);//

down(&chopstick[i]);//拿左手边筷子

down(&chopstick[(i+1)%N]);//拿右手边筷子

eat();

up(&chopstick[i]);//放回左手边筷子

up(&chopstick[(i+1)%N]);//放回右手边筷子

up(&mutex);//

}

}

3、用附加规则解决哲学家进餐问题

对哲学家顺序编号，要求奇数号哲学家先抓左边的叉子，然后再抓他右边的叉子，而偶数号哲学家刚好相反。这样的话就总会有一名哲学家可以顺利获得两支筷子开始进餐。此方法的本质是通过附加规则，让哲学家按照一定的顺序请求临界资源——筷子。这样的话，在资源分配图中就不会出现环路，破坏了死锁生的必要条件之一：“环路等待”条件，从而有效地预防了死锁的产生。

#define N 5

semaphore chopstick[5] = {1,1,1,1,1};

void philosopher(int i){

while(TRUE){

think();

if(i%2==1){//奇数号哲学家

down(&chopstick[i]);//先左边

down(&chopstick[(i+1)%N);//后右边

}else{//偶数号哲学家

down(&chopstick[(i+1)%N]);//先右边

down(&chopstick[i]);//后左边

}

eat();

up(&chopstick[i]);

up(&chopstick[(i+1)%N];

}

4、仅当一个哲学家左右两边的叉子都可用时才允许他抓起叉子

哲学家要么不拿，要么就拿两把叉子。那么哲学家就有三种状态：思考状态不用叉子、饥饿状态在等待左右叉子、吃饭状态正在使用叉子。

#define N 5

#define LEFT (i-1+N)%N;//i左邻居编号

#define RIGHT (i+1)%N;//i右邻居编号

#define THINKING 0 //思考状态

#define HUNGRY 1 //试图拿起叉子

#define EATTING 2 //进餐

int state[N];//记录哲学家状态

semaphore mutex = 1;//临界区，仅仅允许一个进入

semaphore s[N] = {0,0,0,0,0};//每个哲学家一个信号量,初始化为0

void philosopher(i)

{

think(i);

take_forks(i); //吃饭前先等待两只叉子

eatting();

put_forks(i); //放下叉子，查看左右邻居是否两只叉子都空闲，如果空闲提醒邻居拿起叉子

}

void take_forks(i)

{

down(&mutex)

state[i] = HUNGRY; //代表当前哲学家正在等待叉子

test_take_left_right_forks(i); //尝试获取两把叉子

up(&mutex); //离开临界区

down(&s[i]); //如果拿不到叉子就阻塞

}

void test_take_left_right_forks(i)

{

if(state[i] == HUNGRY && state[LEFT] != EATTING && state[RIGTH] != EATTING)

{

state[i] = EATTING; //用EATTING代表当前哲学家能拿到两只叉子

up(&s[i]); //如果能够拿到两只叉子，唤醒当前线程

}

}

void putdown(i)

{

P(mutex)

state[i] = THINKING; //代表当前不需要叉子

test_take_left_right_forks(LEFT);

test_take_left_right_forks(RIGHT);

V(mutex);

}

void thinking(i)

{

P(mutex);

state[i] = THINKING;

V(mutex);

}