山东大学操作系统实验六.docx
- 文档编号:1863561
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:16
- 大小:101.37KB
山东大学操作系统实验六.docx
《山东大学操作系统实验六.docx》由会员分享,可在线阅读,更多相关《山东大学操作系统实验六.docx(16页珍藏版)》请在冰点文库上搜索。
山东大学操作系统实验六
软件学院操作系统实验报告
实验题目:
实验六、死锁问题实验
学号:
201100300124
日期:
2013年05月23日
班级:
5班姓名:
韩俊晓
Email:
hanjunxiao188@
实验目的:
通过本实验观察死锁产生的现象,考虑解决死锁问题的方法。
从而进一步加深对于死锁问题的理解。
掌握解决死锁问题的几种算法的编程和调试技术。
练习怎样构造管程和条件变量,利用管程机制来避免死锁和饥俄问题的发生。
实验要求:
在两个城市南北方向之间存在一条铁路,多列火车可以分别从两个城市的车站排队等待进入车道向对方城市行驶,该铁路在同一时间,只能允许在同一方向上行车,如果同时有相向的火车行驶将会撞车。
请模拟实现两个方向行车,而不会出现撞车或长时间等待的情况。
您能构造一个管程来解决这个问题吗?
硬件环境:
实验室计算机
软件环境:
Ubuntu08.4-Linux操作系统
BASH_VERSION='3.2.33
(1)-release
gccversion4.1.2
gedit2.18.2
OpenOffice2.3
实验步骤:
1.实验说明:
管程-Monitor
管程是一种高级抽象数据类型,它支持在它的函数中隐含互斥操作。
结合条件变量和其他一些低级通信原语,管程可以解决许多仅用低级原语不能解决的同步问题。
利用管程可以提供一个不会发生死锁或饥饿现象的对象;哲学家就餐问题和Java语言中的synchronized对象都是很好的管程的例子.
管程封装了并发进程或线程要互斥执行的函数。
为了让这些并发进程或线程在管程内互斥的执行,进入管程的进/线程必须获取到管程锁或二值信号量
条件变量ConditionVariables
条件变量提供了一种对管程内并发协作进程的同步机制。
如果没有条件变量,管程就不会有很有用。
多数同步问题要求在管程中说明条件变量。
条件变量代表了管程中一些并发进程或线程可能要等待的条件。
一个条件变量管理着管程内的一个等待队列。
如果管程内某个进程或线程发现其执行条件为假,则该进程或线程就会被条件变量挂入管程内等待该条件的队列。
如果管程内另外的进程或线程满足了这个条件,则它会通过条件变量再次唤醒等待该条件的进程或线程,从而避免了死锁的产生。
所以,一个条件变量C应具有两种操作C.wait()和C.signal()。
当管程内同时出现唤醒者和被唤醒者时,由于要求管程内的进程或线程必须互斥执行,因此就出现了两种样式的条件变量:
MesaStyle(signal-and-continue):
唤醒者进程或线程继续执行,被唤醒者进程或线程等到唤醒者进程或线程阻塞或离开管程后再执行。
HoareStyle(signal-and-wait):
被唤醒者进程或线程立即执行,唤醒者进程或线程阻塞,直道被唤醒者阻塞或离开管程后再执行。
实验6单行道(过桥)问题可以通过管程很好的解决。
可以把单行道/桥封装为一个管程类,桥上通过的车辆是进入管程的进/线程,可以通过创建多个车辆进/线程并随机产生它们的行进方向,并指定桥上可同时行驶的车辆的个数来模拟该问题的各种现场随机情况。
一个正确的实验结果应能实现在各种随机现场情况下车辆进程不会逆向上桥(死锁),也不会使车少方向上的车辆无机会上桥(饥饿).
在linux系统中可以利用进程间通信(interprocesscommunication)IPC中的3个对象:
共享内存、信号灯数组、消息队列,来解决协作并发进程间的同步与互斥的问题。
1)共享内存是OS内核为并发进程间交换数据而提供的一块内存区(段)。
如果段的权限设置恰当,每个要访问该段内存的进程都可以把它映射到自己私有的地址空间中。
如果一进程更新了段中数据,那么其他进程立即会看到这一更新。
进程创建的段也可由另一进程读写。
linux中可用命令ipcs-m观察共享内存情况。
$ipcs-m
------SharedMemorySegments--------
keyshmidownerpermsbytesnattchstatus
0x00000000327682student6003932162dest
0x00000000360451student6001966082dest
0x00000000393220student6001966082dest
key共享内存关键值
shmid共享内存标识
owner共享内存所由者(本例为student)
perm共享内存使用权限(本例为student可读可写)
byte共享内存字节数
nattch共享内存使用计数
status共享内存状态上例说明系统当前已由student建立了一些共享内存,每个都有两个进程在共享。
2)信号灯数组是OS内核控制并发进程间共享资源的一种进程同步与互斥机制。
linux中可用命令ipcs-s观察信号灯数组的情况。
$ipcs-s
------SemaphoreArrays--------
keysemidownerpermsnsems
0000000163844apache6001
0x4d00f259294920beagleind6008
0x00000159425995student6441
semid信号灯的标识号
nsems信号灯的个数
其他字段意义同以上共享内存所述。
上例说明当前系统中已经建立多个信号灯。
其中最后一个标号为425996是由student建立的,它的使用权限为644,信号灯数组中信号灯个数为1个。
3)消息队列是OS内核控制并发进程间共享资源的另一种进程同步机制。
linux中可用命令ipcs-q观察消息队列的情况。
$ipcs-q
------MessageQueues--------
keymsqidownerpermsused-bytesmessages
0x000001c80root64481
msgmid消息队列的标识号
used-bytes消息的字节长度
messages消息队列中的消息条数
其他字段意义与以上两种机制所述相同。
上例说明当前系统中有一条建立消息队列,标号为0,为root所建立,使用权限为644,每条消息8个字节,现有一条消息。
4)在权限允许的情况下您可以使用ipcrm命令删除系统当前存在的IPC对象中的任一个对象。
ipcrm-m21482删除标号为21482的共享内存。
ipcrm-s32673删除标号为32673的信号灯数组。
ipcrm-q18465删除标号为18465的消息队列。
5)在linux的proc文件系统中有3个虚拟文件动态记录了由以上ipcs命令显示的当前IPC对象的信息,它们分别是:
/proc/sysvipc/shm共享内存
/proc/sysvipc/sem信号量
/proc/sysvipc/msg消息队列
我们可以利用它们在程序执行时获取有关IPC对象的当前信息。
6)IPC对象有关的系统调用函数原型都声明在以下的头文件中:
#include
#include
创建一段共享内存系统调用语法:
#include
intshmget(key_tkey,intsize,intflags);
key共享内存的键值,可以为IPC_PRIVATE,也可以用整数指定一个
size共享内存字节长度
flags共享内存权限位。
shmget调用成功后,如果key用新整数指定,且flags中设置了IPC_CREAT位,则返回一个新建立的共享内存段标识符。
如果指定的key已存在则返回与key关联的标识符。
不成功返回-1
令一段共享内存附加到调用进程中的系统调用语法:
#include
char*shmat(intshmid,char*shmaddr,intflags)
shmid由shmget创建的共享内存的标识符
shmaddr总为0,表示用调用者指定的指针指向共享段
flags共享内存权限位
shmat调用成功后返回附加的共享内存首地址
令一段共享内存从到调用进程中分离出去的系统调用语法:
#include
intshmdt(char*shmadr);
shmadr进程中指向附加共享内存的指针
shmdt调用成功将递减附加计数,当计数为0,将删除共享内存。
调用不成功返回-1。
创建一个信号灯数组的系统调用有语法:
#include
intsemget(key_tkey,intnsems,intflags);
key信号灯数组的键值,可以为IPC_PRIVATE,也可以用整数指定一个
nsems信号灯数组中信号灯的个数
flags信号灯数组权限位。
如果key用整数指定,应设置IPC_CREAT位。
semget调用成功,如果key用新整数指定,且flags中设置了IPC_CREAT位,则返回一个新建立的信号等数组标识符。
如果指定的整数key已存在则返回与key关联的标识符。
不成功返回-1
操作信号灯数组的系统调用语法:
#include
intsemop(intsemid,structsembuf*semop,unsignednops);
semid由semget创建的信号灯数组的标识符
semop指向sembuf数据结构的指针
nops信号灯数组元素的个数。
semop调用成功返回0,不成功返回-1。
控制信号灯数组的系统调用语法:
#include
intsemctl(intsemid,intsemnum,intcmd,unionsemunarg);
semid由semget创建的信号灯数组的标识符
semnum该信号灯数组中的第几个信号灯
cmd对信号灯发出的控制命令。
例如:
GETVAL返回当前信号灯状态
SETVAL设置信号灯状态
IPC_RMID删除标号为semid的信号灯
arg保存信号灯状态的联合体,信号灯的值是其中一个基本成员
unionsemun{
intval;/*valueforSETVAL*/
......
};
semctl执行不成功返回-1,否则返回指定的cmd的值。
创建消息队列的系统调用语法:
#include
intmsgget(key_tkey,intflags)
key消息队列的键值,可以为IPC_PRIVATE,也可以用整数指定一个
flags消息队列权限位。
msgget调用成功,如果key用新整数指定,且flags中设置了IPC_CREAT位,则返回一个新建立的消息队列标识符。
如果指定的整数key已存在则返回与key关联的标识符。
成功返回-1。
追加一条新消息到消息队列的系统调用语法:
#include
intmsgsnd(intmsqid,structmsgbuf*msgp,size_tmsgsz,intmsgflg);
msqid由消息队列的标识符
msgp消息缓冲区指针。
消息缓冲区结构为:
structmsgbuf{
longmtype;/*消息类型,必须大于0*/
charmtext[1];/*消息数据,长度应于msgsz声明的一致*/
}
msgsz消息数据的长度
msgflg为0表示阻塞方式,设置IPC_NOWAIT表示非阻塞方式
msgsnd调用成功返回0,不成功返回-1。
从到消息队列中读出一条新消息的系统调用语法:
#include
intmsgrcv(intmsqid,structmsgbuf*msgp,size_tmsgsz,longmsgtype,intmsgflg);
msqid由消息队列的标识符
msgp消息缓冲区指针。
消息缓冲区结构为:
structmsgbuf{
longmtype;/*消息类型,必须大于0*/
charmtext[1];/*消息数据,长度应于msgsz声明的一致*/
}
msgsz消息数据的长度
msgtype决定从队列中返回哪条消息:
=0返回消息队列中第一条消息
>0返回消息队列中等于mtype类型的第一条消息。
<0返回mtype<=type绝对值最小值的第一条消息。
msgflg为0表示阻塞方式,设置IPC_NOWAIT表示非阻塞方式
msgrcv调用成功返回0,不成功返回-1。
删除消息队列的系统调用语法:
#include
intmsgctl(intmsqid,intcmd,structmsqid_ds*buf);
msqid由消息队列的标识符
cmd控制命令。
常用的有:
IPC_RMID删除msgid标识的消息队列
IPC_STAT为非破坏性读,从队列中读出一个msgid_ds结构填充缓冲buf
IPC_SET改变队列的UID,GID,访问模式和最大字节数。
msgctl调用成功返回0,不成功返回-1。
3.调试过程:
1)建立以下名为dp.h的头文件:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
/*信号灯控制用的共同体*/
typedefunionsemuns{
intval;
}Sem_uns;
//管程中使用的信号量
classSema{
public:
Sema(intid);
~Sema();
//信号量加1
intdown();
intup();//信号量减1
private:
intsem_id;//信号量标识符
};
//管程中使用的锁
classLock{
public:
Lock(Sema*lock);
~Lock();
voidclose_lock();
voidopen_lock();
private:
Sema*sema;//锁使用的信号量
};
classCondition{
public:
Condition(Sema*sema1,Sema*sema2);
~Condition();
voidWait(Lock*conditionLock,intdirect);//过路条件不足时阻塞
intSignal(intdirec);
//唤醒相反方向阻塞车辆
private:
Sema*queue1;//一个方向阻塞队列
Sema*queue2;//另一方向阻塞队列
Lock*lock;//进入管程时获取的锁
};
classOneWay{
public:
OneWay(intmaxall,intmaxcur);
~OneWay();
voidArrive(intdirec);
//车辆准备上单行道,direc为行车方向
voidCross(intdirec);
//车辆正在单行道上
voidQuit(intdirec);
//车辆通过了单行道
int*eastCount;
int*westCount;
int*eastWait;
int*westWait;
int*sumPassedCars;//已经通过的车辆总数
private:
//建立或获取ipc信号量的一组函数的原型说明
intget_ipc_id(char*proc_file,key_tkey);
intset_sem(key_tsem_key,intsem_val,intsem_flag);
char*set_shm(key_tshm_key,intshm_num,intshm_flag);
intrate;
int*numCars;
int*currentDire;
Condition*condition;
Lock*lock;
};
2)建立dp.cc程序。
参考解法伪代码:
以下是一个单行道管程类及其方法和属性的大致描述:
定义一个单行道管程类:
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)建立以下项目管理文件Makefile
head=dp.h
srcs=dp.cc
objs=dp.o
opts=-w-g-c
all:
dp
dp:
$(objs)
g++$(objs)-odp
dp.o:
$(srcs)$(head)
g++$(opts)$(srcs)
clean:
rmdp*.o
4)输入make命令编译连接生成可执行的程序
$gmake
g++-w-g-cdp.cc
g++dp.o-odp
5)执行程序
./dp
其结果显示如下:
实验总结:
1.实验的过程中在编写代码的时候要仔细认真,定义变量的时候要看明白变量的作用范围
2.实验时实验的步骤要记清楚,这样在执行实验的时候不会出差错
3.要善于将之前学过的知识用在后面的学习中,比如进程的创建这里就可以用到
4.学会分析题意,转化为可实现代码
5.对于编译过程中出现的错误,要有耐心去解决
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 山东大学 操作系统 实验