实验2 BACI环境下解决死锁问题
【实验目的】
1）理解死锁产生的原因。
2）使用BACI解决“生产者—消费者”问题中的死锁问题。
【条件要求】
1）认真阅读和掌握预备知识。 2）上机操作。
【预备知识】 一、什么是死锁
操作系统中并发执行的进程会不断地申请、使用和释放系统的资源，虽然系统会尽量合理地控制资源的分配，但是由于系统资源的数量是有限的，总会发生若干进程都相互等待对方释放己占用的资源才能继续运行下去的情况，使系统中的一部分进程和资源处于无限期停滞的状态。这种可能发生在一组相互合作或竞争的进程之间的问题，称为死锁。
所谓进程死锁是指各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。即出现了各进程间相互的“永久”阻塞的状态，这一组进程就称为死锁进程。如果没有“外力”的推动，死锁就是永久性的。
二、产生死锁的原因
1）竞争资源：当系统中供多个进程所共享的资源不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁。
2）进程推进顺序非法：进程在运行过程中，请求和释放资源的顺序不当，导致了进程死锁。
三、“生产者—消费者”问题
“生产者—消费者”问题是一个典型的进程协作的例子。问题描述如下：
一个或者多个生产者producers不断地产生数据并将数据data放入一个缓冲区buffer，一个或者多个消费者consumer不断地从缓冲区取出产品消费，每个消费者每次只取一个，只能有一个生产者producer（或者消费者consumer）在某一时刻可以访问缓冲区（对公共缓冲区的访问要互斥）。
具体情况分析如下：
1）一个生产者，一个消费者，一个缓冲区。要求P进程（生产者）不能往“满”的缓
冲区中放产品，设置信号量为“S1”，表示空白缓冲区的数目，S1初值为1；要求C进程（消费者）不能从“空’的缓冲区中取产品，设置信号量“S2”,表示缓冲区中产品的数目，S2初值为0。
算法描述如下：
P： C：
while (true) { while (true) { 生产一个产品; wait(s2); wait(s1) ; 从缓冲区取产品; 送产品到缓冲区; signal(s1); signal(s2); 消费产品; }; };
2）m个生产者，k个消费者，n个缓冲区。要求：只能有一个生产者（或者消费者）在某一时刻可以访问缓冲区（对公共缓冲区的访问要互斥）；假定公用缓冲池中具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。
对“生产者—消费者“问题可描述如下： P： C： while (true) { while (true) {
生产一个产品; wait(full); wait(mutex); wait(empty) ; 从缓冲区取产品; wait(mutex); signal(mutex); 送产品到缓冲区; signal(empty); signal(mutex);
signal(full); 消费产品; }; };
细读上述同步流程可以发现：
1）在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现。 2）对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。
3）在每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁。而两个signal操作的顺序无关紧要。
【实验内容】
1）设包含可执行文件bacc，bainterp的目录名为“balnxxe”，进入该目录。 #cd balnxxe
2）使用Vi编辑一个新文件“exam14a.cm”。 # vi exam14a.cm
其内容如下：
/* hint在这里起到测试生产者消费者是否能互斥访问缓冲区，先加1后减1，如果互斥了，结果仍然为0，不变*/
const int size=10; semaphore s; semaphore n; semaphore e; int hint=0; int pc[size]; int v=0; int w=0; int in=0; int out=0; void produce(){ v=v+1; }
void consume() { int b=0; b=w; }
void append(){ int a=0; hint=hint+1; pc[in]=v; a= pc[in] ; in=in+1; in=in%size;
cout<<\ the data \}
void take(){ hint=hint-1; w=pc[out]; out=out+1; out=out%size;
cout<<\ the data \} void p() { int i=0; while(i<1000){ produce();
wait(e); wait(s); append(); signal(s); signal(n); i=i+1; } } void c() { int i=0; while(i<1000){ wait(n); wait(s); take(); signal(s); signal(e); consume(); i=i+1; } }
void main() {
initialsem(s,1); initialsem(n,0); initialsem(e,10); cobegin{ p(); c(); }
cout<<\}
3）保存退出“exam14a.cm”。
4）使用BACI的bacc编译器编译“exam14a.cm”。 #./bacc exam14a.cm
5）解释执行“exam14a.pco”。 #./bainterp exam14a.pco
记录执行结果。看看hint的结果是不是等于0。并观察生产者和消费者交替执行的过程。 6）执行命令：
#cp exam14a.cm exam14b.cm
7）使用Vi编辑“exam14b.cm”。交换p()函数中wait(e)与wait(s)的顺序。 8）保存退出“exam14b.cm”。
9）使用BACI的bacc编译器编译“exam14b.cm”。 #./bacc exam14b.cm
10）解释执行“exam14b.pco”。 #./bainterp exam14b.pco >pc.txt
11）用Vi查看“pc.txt”的内容。查看hint的结果是否为0，并观察生产者和消费者交替执行的过程。如果发生死锁，试解释原因。
12）执行命令：
#cp exam14a.cm exam14c.cm
13）使用Vi编辑“exam14c.cm”。交换c()函数中wait(n)与wait(s)的顺序。 14）保存退出“exam14c.cm”。
15）使用BACI的bacc编译器编译“exam14c.cm”。 #./bacc exam14c.cm
16）解释执行“exam14c.pco” #./bainterp exam14c.pco >pc.txt
17）用Vi查看“pc.txt”的内容。查看hint的结果是否为0，并观察生产者和消费者交替执行的过程。如果发生死锁，试解释原因。