《山东大学操作系统试验-6》由会员分享，可在线阅读，更多相关《山东大学操作系统试验-6（28页珍藏版）》请在金锄头文库上搜索。
1、软件学院实验报告软件学院实验报告实验题目：死锁问题实验实验题目：死锁问题实验实验题目：死锁问题实验实验题目：死锁问题实验 在两个城市南北方向之间存在一条铁路，多列火车可以分别从两个城市的车 站排队等待进入车道向对方城市行驶，该铁路在同一时间，只能允许在同一方向 上行车，如果同时有相向的火车行驶将会撞车。请模拟实现两个方向行车，而不 会出现撞车或长时间等待的情况。构造一个管程来解决这个问题。学号：学号：学号：学号： 日期：日期：日期：日期： 2012201220122012 年年年年 5 5 5 5 月月月月 24242424 日日日日 班级：班级：班级：班级： 5 5 5 5 班班班班 Ema
2、ilEmailEmailEmail：实验目的实验目的实验目的实验目的：通过本实验观察死锁产生的现象，考虑解决死锁问题的方法。从而进 一步加深对于死锁问题的理解。掌握解决死锁问题的几种算法的编程和调试技 术。 练习怎样构造管程和条件变量， 利用管程机制来避免死锁和饥俄问题的发生。 硬件环境硬件环境硬件环境硬件环境：IBM 实验室计算机软件环境软件环境软件环境软件环境：eclipsegcc 编译器 Ubuntu-Linux 操作系统 Gnome 桌面实验步骤：实验步骤：实验步骤：实验步骤：1.1.1.1.问题分析问题分析问题分析问题分析 管程-Monitor 管程是一种高级抽象数据类型，它支持在它
3、的函数中隐含互斥操作。结合条 件变量和其他一些低级通信原语， 管程可以解决许多仅用低级原语不能解决的同 步问题。利用管程可以提供一个不会发生死锁或饥饿现象的对象;哲学家就餐问 题和 Java 语言中的 synchronized 对象都是很好的管程的例子. 管程封装了并发进程或线程要互斥执行的函数。为了让这些并发进程或线程 在管程内互斥的执行，进入管程的进/线程必须获取到管程锁或二值信号量 条件变量 Condition Variables 条件变量提供了一种对管程内并发协作进程的 同步机制。如果没有条件变量，管程就不会有很有用。多数同步问题要求在管程 中说明条件变量。条件变量代表了管程中一些并发
4、进程或线程可能要等待的条 件。 一个条件变量管理着管程内的一个等待队列。如果管程内某个进程或线程发 现其执行条件为假， 则该进程或线程就会被条件变量挂入管程内等待该条件的队 列。 如果管程内另外的进程或线程满足了这个条件，则它会通过条件变量再次唤 醒等待该条件的进程或线程，从而避免了 死锁的产生。所以，一个条件变量C 应具有两种操作 C.wait()和 C.signal()。当管程内同时出现唤醒者和被唤醒者时，由于要求管程内的进程或 线 程 必 须 互 斥 执 行 ， 因 此 就 出 现 了 两 种 样 式 的 条 件 变 量 MesaStyle(signal-and-continue):唤醒
5、者进程或线程继续执行，被唤醒者进程或 线 程 等 到 唤 醒 者 进 程 或 线 程 阻 塞 或 离 开 管 程 后 再 执 行 Hoare Style(signal-and-wait):被唤醒者进程或线程立即执行，唤醒者进程或线程 阻塞，直道被唤醒者阻塞或离开管程后再执行。 实验 6 单行道(过桥)问题可以通过管程很好的解决。可以把单行道/桥封装 为一个管程类，桥上通过的车辆是进入管程的进/线程，可以通过创建多个车辆 进/线程并随机产生它们的行进方向，并指定桥上可同时行驶的车辆的个数来模 拟该问题的各种现场随机情况。 一个正确的实验结果应能实现在各种随机现场情 况下车辆进程不会逆向上桥(死锁
6、)，也不会使车少方向上的车辆无机会上桥(饥 饿). 2.2.2.2.算法设计说明如下：算法设计说明如下：算法设计说明如下：算法设计说明如下： 以下是一个单行道管程类及其方法和属性的大致描述： 定义一个单行道管程类： class OneWay public: OneWay(); OneWay(); void Arrive(int direc);/ 车辆准备上单行道，direc 为行车方向 void Cross(int direc);/ 车辆正在单行道上 void Quit(int direc);/ 车辆通过了单行道 private: int rate;/车速 int *maxCars;/最大同向
7、车数 int *numCars;/当前正在通过的车辆数 int *currentDirec;/当前通过的车辆的方向 Condition *OneWayFull;/通过单行道的条件变量 Lock *lock;/单行道管程锁 ; 定义一个进入管程的信号量 Sema 类和锁 Lock 类(可参考实验六的示例程序). 定义一个单行道管程的条件变量类： class Condition public: Condition(Sema *sema1 , Sema *sema2); Condition(); void Wait(Lock *conditionLock,int direc);/过路条件不足时阻塞
8、void Signal( int direc);/唤醒相反方向阻塞车辆 private: Sema* queue1;/ 一个方向阻塞队列 Sema* queue2;/ 另一方向阻塞队列 Lock* lock;/ 进入管程时获取的锁 ;Mesa 型条件变量的 Wait 和 Signal 方法：(也可设计成 Haoro 样式) Condition:Wait( Lock *conditionLock,int direct) 保存当前条件锁； 释放锁； 进入所在方向等待队列睡眠； 被唤醒后重新获取锁； Condition:Signal( Lock *conditionLock) 唤醒相反方向队列等待者
9、 单行道管程的 Arrive 和 Quit 方法： OneWay:Arrive(int direc) 获取管程锁；如果当前方向不是我的方向或者单行道上有车且车辆数大于等于上限数 在条件变量上等待; 单行道上车辆数加 1； 当前方向为我的方向；释放管程锁； OneWay:Quit(int direc) 获取管程锁； 单行道上车辆数减 1； 车辆数为 0 唤醒相反方向队列中的等待者 释放管程锁 主程序 main() 建立单行道管程； 建立多个行车子进程(最好不少于 5 个)，每个随机设定一个行车方向； 每个子进程作： while(1) 单行道管程-Arrive(direc); 单行道管程-Cros
10、s(direc); 单行道管程-Exit(direc); 3.3.3.3.开发调试过程：开发调试过程：开发调试过程：开发调试过程：用 eclipse 新建一个名为 test6 的 c+ project。 新建 source folder 新建名为 dp.c 的 C+语言程序 再建立以下名为 dp.h 的 C+ 语言头文件 build 项目，产生可运行的二进制文件。 对程序进行调试，排除 bug。然后在终端运行程序，如下图： 一五辆车，单向做多一辆车。二五辆车，单向最多两辆车。三五辆车，单向最多三辆车。四五辆车，单向最多四辆车。结论分析与体会：结论分析与体会：结论分析与体会：结论分析与体会： 通
11、过编写此次试验，首先让我更清楚地了解到了死锁现象发生的原因及避 免方法， 加深了对于死锁问题的理解。学会了如何构造管程和条件变量来避免死 锁和饥饿的发生，更加熟练了型号量的使用以及共享内存的创建和使用。附录附录附录附录 A A A A： 本实验全部程序源代码及注释本实验全部程序源代码及注释本实验全部程序源代码及注释本实验全部程序源代码及注释 Dp.hDp.hDp.hDp.h/* dp.h*Created on: 2012-5-24*Author: taburiss*/#include#include#include#include #include#include#include#includ
12、e #include#include#include#include #include#include#include#include #include#include#include#include #include#include#include#include #include#include#include#include #include#include#include#include #include#include#include#include #include#include#include#include /*信号灯控制的共同体*/typedeftypedeftypedef
13、typedef unionunionunionunion semuns intintintint val; Sem_uns;/管程中使的信号量classclassclassclass Sema publicpublicpublicpublic:SemaSemaSemaSema(intintintint id);SemaSemaSemaSema();intintintint downdowndowndown(); /信号量加 1intintintint upupupup(); /信号量减 1privateprivateprivateprivate:intintintint sem_id; /信号
14、量标识符;/管程中使的锁classclassclassclass Lock publicpublicpublicpublic:LockLockLockLock(Sema *lock);LockLockLockLock();voidvoidvoidvoid close_lockclose_lockclose_lockclose_lock();voidvoidvoidvoid open_lockopen_lockopen_lockopen_lock();privateprivateprivateprivate:Sema *sema; /锁使的信号量;classclassclassclass Con
15、dition publicpublicpublicpublic:ConditionConditionConditionCondition(Sema *sema1, Sema *sema2);ConditionConditionConditionCondition();voidvoidvoidvoid WaitWaitWaitWait(Lock *conditionLock, intintintint direct); /过路条件不时阻塞intintintintSignalSignalSignalSignal(intintintint direc);/唤醒相反向阻塞车辆privateprivat
16、eprivateprivate:Sema* sema0; / 个向阻塞队列Sema* sema1; / 另向阻塞队列Lock* lock; / 进管程时获取的锁;classclassclassclass OneWay publicpublicpublicpublic:OneWayOneWayOneWayOneWay(intintintint maxall, intintintint maxcur);OneWayOneWayOneWayOneWay();voidvoidvoidvoid ArriveArriveArriveArrive(intintintint direc);/ 车辆准备上单道,direc 为车向voidvoidvoidvoid CrossCrossCrossCross(intintintint direc);/ 车辆正在单道上voidvoidv
