没有合适的资源?快使用搜索试试~ 我知道了~
实现生产者消费者问题和实现银行家算法的课程设计.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 5 浏览量
2022-05-06
11:22:25
上传
评论
收藏 262KB DOC 举报
温馨提示
试读
29页
实现生产者消费者问题和实现银行家算法的课程设计.doc
资源推荐
资源详情
资源评论
操作系统课程设计
操作系统课程设计
题目一:实现生产者消费者问题
题目二:实现银行家算法
指导老师: ******
班 级: ****** 班
学 号: ******
姓 名: ******
2007 年 12 月 12 日
目 录
第一部分:实现生产者与消费者问题
0
操作系统课程设计
一、题目:实现生产者与消费者问题
此问题是经典的进程同步互斥问题,问题描述参见教材第 36 页和第 46 页,
要求编程实现,生产者放入产品的和消费者取走产品的速度可以调节。
1、课程设计目的:
在我们所学的《操作系统》这门课程中,关于经典进程的同步问题进行了
一定的描述和探讨,介绍了几个经典的算法,需要我们在实践中学会熟练运用。
在生产者与消费者问题中,需要我们了解进程同步的概念,理解信号量机制的
原理,掌握运用信号量解决进程同步问题的方法,进而学会运用进程的同步与
互斥解决生产者与消费者的冲突问题。
2、课程设计要求:
生产者与消费者问题可以算作是经典进程同步问题的典型代表。该课程设
计要求运用基于单缓冲区和多缓冲区的生产者与消费者问题的多种实现机制,其
中利用了数据结构中的循环队列和堆栈来模拟实现是一种比较容易实现的方法。
这种思想能够帮助我们更好的理解所学内容,并加以锻炼我们的动手实践能力,
实现它内在具有的超强的参考价值和实践意义。
该课程设计通过了解进程间的两种制约关系,从而理解信号量机制;通过
对实例的分析和讨论,理解信号量机制实现进程的同步及互斥的方法;通过对
经典进程同步问题的剖析,初步掌握运用信号量解决进程同步问题的方法。
二、设计内容
在同一个进程地址空间内执行的两个线程。生产者线程生产物品,然后将
物品放置在一个空缓冲区中供消费者线程消费。消费者线程从缓冲区中获得物
品,然后释放缓冲区。当生产者线程生产物品时,如果没有空缓冲区可用,那
么生产者线程必须等待消费者线程释放出一个空缓冲区。当消费者线程消费物
品时,如果没有满的缓冲区,那么消费者线程将被阻塞,直到新的物品被生产
出来,我的具体做法也是如此,建立缓冲区,生产者生产的产品放入,消费者
从中取产品,如果没有产品,则等待。
三、开发环境
1
操作系统课程设计
此程序的设计在 Windows XP 操作系统下,基于 Microsoft Visual C+
+6.00 环境下的一个关于实现生产者与消费者问题的程序。用 C 语言实现编程。
四、分析设计
1、设计原理
进程同步是指几个进程相互合作,一个进程到达某个点后,除非另一个进
程已经完成某些操作,否则就不得不停下来,等待这些操作的结束,这就是进
程同步的概念。
生产者-消费者问题是一个经典的进程同步问题,该问题最早由 Dijkstra 提
出,用以演示他提出的信号量机制。本作业要求设计在同一个进程地址空间内
执行的两个线程。生产者线程生产物品,然后将物品放置在一个空缓冲区中供
消费者线程消费。消费者线程从缓冲区中获得物品,然后释放缓冲区。当生产
者线程生产物品时,如果没有空缓冲区可用,那么生产者线程必须等待消费者
线程释放出一个空缓冲区。当消费者线程消费物品时,如果没有满的缓冲区,
那么消费者线程将被阻塞,直到新的物品被生产出来。
生产者—消费者问题是一种同步问题的抽象描述。计算机系统中的每个进
程都可以消费或生产某类资源,当系统中某一进程使用某一资源时,可以看作
是消耗,且该进程称为消费者。而当某个进程释放资源时,则它就相当一个生
产者。
通过一个有界缓冲区把生产者和消费者联系起来。假定生产者和消费者是相
互等效的,只要缓冲区未满,生产者就可以将产品送入缓冲区,类似地,只要
缓冲区未空,消费者就可以从缓冲区中去走物品并消费它。生产者和消费者的
同步关系将禁止生产者向满的缓冲区输送产品,也禁止消费者从空的缓冲区中
提取物品。
在生产者—消费者问题中,信号灯具有两种功能。首先,它是跟踪资源的生
产和消费的计数器;其次,它是协调资源的生产者和消费者之间的同步器。消
费者通过再一指派给它的信号灯上做 P 操作来表示消耗资源,而生产者通过在
同一信号灯上做 V 操作来表示生产资源。再这种信号灯的实施中,计数在每次
P 操作后减 1,而在每次 V 操作中加 1。个这一计数器的初始值是可利用的资源
数目。当资源是不可利用时,将申请资源的进程放置在等待队列中。如果有一
个资源释放,在等待队列中的第一个进程被唤醒并得到资源的控制权。
为解决这一类生产者——消费者问题,设置了两个同步信号灯,一个说明空
缓冲区的数目,用 empty 表示,其初值为有界缓冲区的大小 n,另一个说明缓
2
操作系统课程设计
冲区的数目,用 full 表示,其初制值为 0。由于有界缓冲区是一个零界资源,
必须互斥使用,所以另外还需设置一个互斥信号灯 mutex,起初值为 1。
假定在生产者和消费者之间的公用缓冲区中,具有 n 个缓冲区,这时可以利
用互斥信号量 mutex 实现诸进程对缓冲池的互斥使用;利用信号量 empty 和
full 分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费
者互相等效果,只要缓冲池未满,生产者便可以将消息送入缓冲池;只要缓冲
池未空,消费者便可以从缓冲池中取走一个消息。
在生 产 者 ---消 费 者问 题 中应 注意 : 首先 , 在每 个程序 中用于 互斥的
wait(mutex)和 signal(mutex)必须成对出现;其次,对资源信号量 empty
和 full 的 wait 和 signal 操作,同样需要成对地出现,但它们分别处于不同的
程序中。
生产者与消费者进程共享一个大小固定的缓冲区。其中,一个或多个生产
者生产数据,并将生产的数据存入缓冲区,并有一个或多个消费者从缓冲区中
取数据。
假设缓冲区的大小为 n(存储单元的个数),它可以被生产者和消费者循
环使用。分别设置两个指针 in 和 out,指向生产者将存放数据的存储单元和消
费者将取出数据的存储单元,如图,指针 in 和 out 初始化指向缓冲区的第一个
存储单元。生产者从第一个存储单元开始存放数据,一次存放一条数据一条数
据且 in 指针向后移一个位置,当 in 指针指向第 n 个存储单元,下一次将指向
第一个存储单元,如此循环反复使用缓冲区。消费者从缓冲区中逐条取走数据,
一次取一条数据,相应的存储单元变为“空”,可以被生产者再次使用。每次取
走一条数据,out 指针向后移一个存储单元位置。试想,如果不控制生产者与
消费者,将会产生什么结果?
1 2 3 4 5 6 7 8 n
…………
In out
1 2 3 4 5 6 7 8 n
…………
In out
其中,in 表示存数据位置,out 表示取数据位置
: :被占用单元 :空存储单元
3
操作系统课程设计
图:生产者/消费者循环使用缓冲区
首先,生产者和消费者可能同时进入缓冲区,甚至可能同时读/写一个存储
单元,将导致执行结果不确定。这显然是不允许的。所以,必须使生产者和消
费者互斥进入缓冲区。即某时刻只允许一个实体(生产者或消费者)访问缓冲
区,生产者互斥消费者和其他任何生产者。
其次,生产者不能向满的缓冲区写数据,消费者也不能在空缓冲区中取数
据,即生产者与消费者必须同步。当生产者产生出数据,需要将其存入缓冲区
之前,首先检查缓冲区中是否有“空”存储单元,若缓冲区存储单元全部用完,
则生产者必须阻塞等待,直到消费者取走一个存储单元的数据,唤醒它。若缓
冲区内有“空”存储单元,生产者需要判断此时是否有别的生产者或消费者正在
使用缓冲区,若是有,则阻塞等待,否则,获得缓冲区的使用权,将数据存入
缓冲区,释放缓冲区的使用权。消费者取数据之前,首先检查缓冲区中是否存
在装有数据的存储单元,若缓冲区为“空”,则阻塞等待,否则,判断缓冲区是
否正在被使用,若正被使用,若正被使用,则阻塞等待,否则,获得缓冲区的
使用权,进入缓冲区取数据,释放缓冲区的使用权。其执行流程如图所示,伪
代码如图所示。
2、涉及的数据结构
① 用资源向量 Available。这是一个含有 m 个元素的数组,其中的每一个元
素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源
的 数 目 , 其 数 值 随 该 类 资 源 的 分 配 和 回 收 而 动 态 地 改 变 。 如 果
Available[j]=K,则表示系统中县有 RJ 类资源 K 个。
② 需求矩阵 MAX。这是一个 N*M 的矩阵,它定义了系统中 N 个进程中的每
一个进程对 M 类资源的最大需求。如果 MAX[i,j]=K,则表示进程 I 需要 RJ 类
资源的最大数目为 K。
③ 矩阵 Allocation。这也是一个 N*M 的矩阵,它定义了系统中每一类资源
当前已分配给每一进程的资源数。如果 Allocation[i,j]=K,则表示进程 i 当前
已分得 RJ 类资源的数目为 K。
④ 矩阵 Need。这也是一个 N*M 的矩阵,用以表示每一个进程尚需的各类资
源数。如果 Need[i,j]=K,则表示进程 I 还需要 RJ 类资源 K 个,方能完成其任
务。
上述三个矩阵间存在下述关系:
Need[i,j]=MAX[i,j]-Allocation[i,j]
4
剩余28页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 79
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功