山东大学操作系统实验六报告死锁问题

计算机科学与技术学院操作系统实验报告实验题目：死锁问题在两个城市南北方向之间存在一条铁路,多列火车可以分别从两个城市的车站排队等待进入车道向对方城市行驶,该铁路在同一时间,只能允许在同一方向上行车,如果同时有相向的火车行驶将会撞车。请模拟实现两个方向行车,而不会出现撞车或长时间等待的情况。您能构造一个管程来解决这个问题吗?实验目的：通过本实验观察死锁产生的现象,考虑解决死锁问题的方法。从而进一步加深对于死锁问题的理解。掌握解决死锁问题的几种算法的编程和调试技术。练习怎样构造管程和条件变量,利用管程机制来避免死锁和饥俄问题的发生。硬件环境：Inter(R)Core(TM)i5-3210MCPU@2.50GHz内存：4GB硬盘：500G软件环境：XUbuntu－Linux操作系统Gnome桌面2.18.3BASH_VERSION='3.2.33(1)-releasegccversion4.1.2gedit2.18.2OpenOffice2.3实验步骤：1、问题分析:管程-Monitor管程是一种高级抽象数据类型,它支持在它的函数中隐含互斥操作。结合条件变量和其他一些低级通信原语,管程可以解决许多仅用低级原语不能解决的同步问题。利用管程可以提供一个不会发生死锁或饥饿现象的对象;哲学家就餐问题和Java语言中的synchronized对象都是很好的管程的例子.管程封装了并发进程或线程要互斥执行的函数。为了让这些并发进程或线程在管程内互斥的执行,进入管程的进/线程必须获取到管程锁或二值信号量条件变量ConditionVariables条件变量提供了一种对管程内并发协作进程的同步机制。如果没有条件变量,管程就不会有很有用。多数同步问题要求在管程中说明条件变量。条件变量代表了管程中一些并发进程或线程可能要等待的条件。一个条件变量管理着管程内的一个等待队列。如果管程内某个进程或线程发现其执行条件为假,则该进程或线程就会被条件变量挂入管程内等待该条件的队列。如果管程内另外的进程或线程满足了这个条件,则它会通过条件变量再次唤醒等待该条件的进程或线程,从而避免了死锁的产生。所以,一个条件变量C应具有两种操作C.wait()和C.signal()。当管程内同时出现唤醒者和被唤醒者时,由于要求管程内的进程或线程必须互斥执行,因此就出现了两种样式的条件变量:MesaStyle(signal-and-continue):唤醒者进程或线程继续执行,被唤醒者进程或线程等到唤醒者进程或线程阻塞或离开管程后再执行。HoareStyle(signal-and-wait):被唤醒者进程或线程立即执行,唤醒者进程或线程阻塞,直道被唤醒者阻塞或离开管程后再执行。实验6单行道(过桥)问题可以通过管程很好的解决。可以把单行道/桥封装为一个管程类,桥上通过的车辆是进入管程的进/线程,可以通过创建多个车辆进/线程并随机产生它们的行进方向,并指定桥上可同时行驶的车辆的个数来模拟该问题的各种现场随机情况。一个正确的实验结果应能实现在各种随机现场情况下车辆进程不会逆向上桥(死锁),也不会使车少方向上的车辆无机会上桥(饥饿).2、算法设计说明如下：以下是一个单行道管程类及其方法和属性的大致描述:定义一个单行道管程类:classOneWay{public:OneWay();~OneWay();voidArrive(intdirec);//车辆准备上单行道,direc为行车方向voidCross(intdirec);//车辆正在单行道上voidQuit(intdirec);//车辆通过了单行道private:intrate;//车速int*maxCars;//最大同向车数int*numCars;//当前正在通过的车辆数int*currentDirec;//当前通过的车辆的方向Condition*OneWayFull;//通过单行道的条件变量Lock*lock;//单行道管程锁};定义一个进入管程的信号量Sema类和锁Lock类(可参考实验六的示例程序).定义一个单行道管程的条件变量类:classCondition{public:Condition(Sema*sema1,Sema*sema2);~Condition();voidWait(Lock*conditionLock,intdirec);//过路条件不足时阻塞voidSignal(intdirec);//唤醒相反方向阻塞车辆private:Sema*queue1;//一个方向阻塞队列Sema*queue2;//另一方向阻塞队列Lock*lock;//进入管程时获取的锁};Mesa型条件变量的Wait和Signal方法:(也可设计成Haoro样式)Condition::Wait(Lock*conditionLock,intdirect){保存当前条件锁;释放锁;进入所在方向等待队列睡眠;被唤醒后重新获取锁;}Condition::Signal(Lock*conditionLock){唤醒相反方向队列等待者}单行道管程的Arrive和Quit方法:OneWay::Arrive(intdirec){获取管程锁;如果当前方向不是我的方向或者单行道上有车且车辆数大于等于上限数在条件变量上等待;单行道上车辆数加1;当前方向为我的方向;释放管程锁;}OneWay::Quit(intdirec){获取管程锁;单行道上车辆数减1;车辆数为0唤醒相反方向队列中的等待者释放管程锁}主程序main(){建立单行道管程;建立多个行车子进程(最好不少于5个),每个随机设定一个行车方向;每个子进程作:while(1){单行道管程-Arrive(direc);单行道管程-Cross(direc);单行道管程-Exit(direc);}}3、开发调试过程：在1、单行道最多允许一辆车行驶,不同方向同时到达五辆车。$./dp512、单行道最多允许两辆车同向行驶,不同方向同时到达七辆车。./dp72附件：Dp.cc:#includedp.hSema::Sema(intid){sem_id=id;}Sema::~Sema(){}intSema::down(){structsembufbuf;buf.sem_op=-1;buf.sem_num=0;buf.sem_flg=SEM_UNDO;if((semop(sem_id,&buf,1))0){perror(downerror);exit(EXIT_FAILURE);}returnEXIT_SUCCESS;}intSema::up(){Sem_unsarg;structsembufbuf;buf.sem_op=1;buf.sem_num=0;buf.sem_flg=SEM_UNDO;if((semop(sem_id,&buf,1))0){perror(uperror);exit(EXIT_FAILURE);}returnEXIT_SUCCESS;}Lock::Lock(Sema*s){sema=s;}Lock::~Lock(){}//上锁voidLock::close_lock(){sema-down();}//开锁voidLock::open_lock(){sema-up();}//用于哲学家就餐问题的条件变量Condition::Condition(Sema*s0,Sema*s1){sema[0]=s0;sema[1]=s1;}voidCondition::Wait(Lock*lock,intdir){lock-open_lock();sema[dir]-down();lock-close_lock();}voidCondition::Signal(intdir){sema[dir]-up();}intdp::get_ipc_id(char*proc_file,key_tkey){#defineBUFSZ256FILE*pf;inti,j;charline[BUFSZ],colum[BUFSZ];if((pf=fopen(proc_file,r))==NULL){perror(Procfilenotopen);exit(EXIT_FAILURE);}fgets(line,BUFSZ,pf);while(!feof(pf)){i=j=0;fgets(line,BUFSZ,pf);while(line[i]=='')i++;while(line[i]!='')colum[j++]=line[i++];colum[j]='\0';if(atoi(colum)!=key)continue;j=0;while(line[i]=='')i++;while(line[i]!='')colum[j++]=line[i++];colum[j]='\0';i=atoi(colum);fclose(pf);returni;}fclose(pf);return-1;}intdp::set_sem(key_tsem_key,intsem_val,intsem_flg){intsem_id;Sem_unssem_arg;//测试由sem_key标识的信号量是否已经建立if((sem_id=get_ipc_id(/proc/sysvipc/sem,sem_key))0){//semget新建一个信号灯,其标号返回到sem_idif((sem_id=semget(sem_key,1,sem_flg))0){perror(semaphorecreateerror);exit(EXIT_FAILURE);}}//设置信号量的初值sem_arg.val=sem_val;if(semctl(sem_id,0,SETVAL,sem_arg)0){perror(semaphoreseterror);exit(EXIT_FAILURE);}returnsem_id;}char*dp::set_shm(key_tshm_key,intshm_num,intshm_flg){inti,shm_id;char*shm_buf;//测试由shm_key标识的共享内存区是否已经建立if((shm_id=get_ipc_id(/proc/sysvipc/shm,shm_key))0){//shmget新建一个长度为shm_num字节的共享内存if((shm_id=shmget(shm_key,shm_num,shm_flg))0){perror(shareMemoryseterror);exit(EXIT_FAILURE);}//shmat将由shm_id标识的共享内存附加给指针shm_bufif((shm_buf=(char*)shmat(shm_id,0,0))(char*)0){perror(getshareMemoryerror);exit(EXIT_FAILURE);}for(i=0;ishm_num;i++)shm_buf[i]=0;//初始为0}//共享内存区已经建立,将由shm_id标识的共享内存附加给指针shm_bufif((shm_buf=(char*)shmat(shm_id,0,0))(char*)0){perror(getshareMemoryerror);exit(EXIT_FAILURE);}returnshm_buf;}//哲学家就餐问题管程构造函数dp::dp(intr,intmax){intipc_flg=IPC_CREAT|0644;intshm_key=220;intshm_num=5;intsem_key=120;intsem_val=0;intshm_flg=IPC_CREAT|0644;intsem_id;Sema*sema;Sema*sema1;Sema*sema2;rate=r;maxCars=max;//currentDirec=1;numCars=0;//共享内存，保存当前车辆数buff_ptr=(int*)set_shm(shm_key++,shm_num,shm_flg)