操作系统课程设计管程的实现生产者消费者问题.docx

资源描述

操作系统课程设计管程的实现生产者消费者问题.docx

《操作系统课程设计管程的实现生产者消费者问题.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计管程的实现生产者消费者问题.docx（34页珍藏版）》请在冰点文库上搜索。

操作系统课程设计管程的实现生产者消费者问题.docx

操作系统课程设计管程的实现生产者消费者问题

操作系统课程设计

2、管程的实现（生产者消费者问题）

1.设计背景：

管程是一种高级抽象数据类型，它支持在它的函数中隐含互斥操作。

结合条件变量和其他一些低级通信原语，管程可以解决许多仅用低级原语不能解决的同步问题。

例如，本实验中利用管程提供一个不会发生死锁的生产者消费者问题就是利用管程的很好的例子。

管程封装了并发进程或线程要互斥执行的函数。

为了让这些并发进程或线程在管程内互斥的执行，管程的实现必须隐含的具有锁或二值信号量。

如果没有条件变量，管程就不会有很有用，条件变量提供了一种对管程内并发协作进程的同步机制。

条件变量代表了管程中一些并发进程或线程可能要等待的条件。

一个条件变量管理着管程内的一个等待队列。

如果管程内某个进程或线程发现其执行条件为假，则该进程或线程就会被条件变量挂入管程内等待该条件的队列。

如果管程内另外的进程或线程满足了这个条件，则它会通过条件变量再次唤醒等待该条件的进程或线程，从而避免了死锁的产生。

所以，一个条件变量C应具有两种操作C.wait（）和C.signal（）。

当管程内同时出现唤醒者和被唤醒者时，由于要求管程内的进程或线程必须互斥执行，因此就出现了两种样式的条件变量：

MesaStyle（signal-and-continue）:

唤醒者进程或线程继续执行，被唤醒者进程或线程等到唤醒者进程或线程阻塞或离开管程后再执行。

HoareStyle（signal-and-wait）:

被唤醒者进程或线程立即执行，唤醒者进程或线程阻塞，直道被唤醒者阻塞或离开管程后再执行。

我们实验所做的就是在原来mesa样式的基础上进行Hoare样式的改进;这种样式也是我们实验中需要实现的样式。

2.设计目标

验证并分析Nachos中Bridge管程是否能够正确的解决单

行桥双向过桥问题。

定义和实现Hoare样式的条件变量Condition_H类

利用Hoare样式的条件变量Condition_H,实现Ring类中

定义的各个方法,使用Ring管程解决生产者/消费者问题。

利用Ring对象的Put操作和Get操作代替信号量来完成同

步操作。

这样就避免了由于不恰当的使用信号量而引起

的死锁和饥饿问题。

利用Hoare样式的条件变量Condition_H,实现Dp管程中

定义的各个方法,使用Ring管程解决哲学家就餐问题。

避免了由于不恰当的使用信号量而引起的死锁和饥饿问

题。

3.设计环境

我们将使用以下的环境和资料学习和实验Nachos系统，展开我们的操作系统设计。

11.实验环境为linux操作系统。

22.Nachos-3.4版系统源代码电子文档及相关编译软件gcc-2.8.1-mips。

33.StudyBook：

讲授Nachos系统的原理和实现的教材。

44.IntroductoryBook：

讲授Nachos系统的实验方法、实验步骤、实验要求的实验指导书。

4.设计说明

1.Hoare样式条件变量

设计算法说明：

对于Hoare样式管程，相比于Mesa样式新增了一个唤醒者等待队列。

在Hoare样式中，唤醒者唤醒被唤醒者后，被唤醒者加入到readytorun队列中，将被唤醒者加入到唤醒者等待队列中，被唤醒者阻塞或者离开时会唤醒唤醒者等待队列中的一个唤醒。

这样我们需要一个新的条件变量，重写它的wait（）和signal（）方法来实现Hoare样式管程。

设计内容和步骤：

<1>在synch.h文件中定义一个新的结构体Condition_H。

结构体Condition_H中包含的私有变量有char*name（条件变量名称）、List*queue（等待在该条件变量的线程）、Lock*lock（管程锁，条件变量共享）、Semaphore*next（指向唤醒者等待队列，条件变量共享）、int*nextCount（记录唤醒者等待队列中线程数量，条件变量共享）；方法有char*getName（）、voidWait（Lock*conditionLock）、voidSignal（Lock*conditionLock）。

<2>在synch.cc文件中定义结构体Condition_H中方法的具体实现。

①在方法Condition_H:

Wait（Lock*conditionLock）中，首先判断队列是否为空，是则把传入的锁赋给条件变量的锁。

调用条件变量的等待队列queue的Append（currentThread）方法，把当前线程放入等待队列中当前线程释放锁。

如果唤醒这等待队列中有线程，则唤醒一个线程，即把它加入readytorun队列中，调用了条件变量next的V方法。

当前线程sleep，放弃资源，在readytorun队列中选取下一个执行的线程，该线程申请锁。

②在方法voidCondition_H:

Signal（Lock*conditionLock）中，如果条件变量的等待队列queue非空则从中移除一个线程，并把该线程放入readytorun等待队列中。

当前线程释放锁，并把当前线程加入唤醒这等待队列中，调用了条件变量next的P方法。

在readytorun队列中选取下一个执行的线程，该线程申请锁。

如果队列为空，则不做。

实验收获：

1.需要注意的一点是，唤醒者等待队列是属于管程的

2.一个常用的规则是，在.h头文件中声明方法头，然后在.cc中将具体的方法实现，这是老师上课强调的一点，在试验中应实践好。

3.实验受到了张洪烈老师的鼓励与帮助，在此表示感谢。

实验过程中，具体实现的每一个思想都会遇到很多问题，有的时候可能只是一个未知的知识点的忽略，受到老师点拨之后问题往往可以迎刃而解。

运行结果分析：

（无）

2.消费者生产者管程

设计算法说明：

生产者—消费者问题是一个著名的进程同步问题。

它描述的是：

有一群生产者进程在生产产品，并将此产品提供给消费者进程去消费。

为使生产者进程和消费者进程能并发执行，在它们之间设置有个缓冲区的缓冲池，生产者进程可将它所生产的产品放入一个缓冲区中，消费者进程可从一个缓冲区取得一个产品消费。

使用管程的思想解决这个问题，我们需要使用两个条件变量和一个管程锁，一个唤醒者等待队列以及一系列控制的参数。

方法包括voidPut（slot*message）;voidGet（slot*message）;intFull（）；intEmpty（）;voidEnter（）;voidExit（）;

设计内容和步骤：

<1>slot结构体的实现。

Slot结构体用于存储生产者存放和消费者所取的数据。

包括两个实例变量：

thread_id和value（int类型）。

<2>ring结构体的实现。

ring结构体即生产者消费者问题的管程类。

包括的实例变量有：

intsize;//缓冲区大小

intin,out;//存放和取数据的位置记录

slot*buffer;//缓冲区（环形）

Condition_H*notfull;//条件变量

Condition_H*notempty;//条件变量

Lock*mutexLock;//管程锁

Semaphore*next;//唤醒这等待队列

包括的方法有：

voidPut（slot*message）;//生产者放数据

voidGet（slot*message）;//消费者取数据

intFull（）;//缓冲区是否满

intEmpty（）;//缓冲区是否空

voidEnter（）;//进入管程

voidExit（）;//出管程

<3>ring结构体中方法的具体实现。

voidPut（slot*message）;判断缓冲区是否为满，满则生产者在在notfull条件变量上等待；不满则放入数据，修改变量in的值，在notempty条件变量上唤醒一个消费者。

voidGet（slot*message）;判断缓冲区是否为空，空则消费者在条件变量notempty上等待；不空则取出一个数据，修改变量out的值，在条件变量notfull上唤醒一个生产者。

voidEnter（）;进程获取锁，进入管程，mutexLock->Acquire（）。

voidExit（）;进程释放锁，出管程，mutexLock->Release（）。

<4>使用管程解决生产者消费者问题。

首先生成ring变量，声明缓冲区大小，生产者消费者数量。

为每一个生产者创建线程，设置优先级，运行Producer（）方法。

为每一个消费者创建线程，设置优先级，运行Consumer（）方法。

Producer（_intwhich）设置一个循环体，循环次数是生产者生产产品的数量，每次生产一个产品。

封装程slot类型变量message，调用管程ring的方法，分别是

ring->Enter（）;

ring->Put（message）;

ring->Exit（）;

Get（slot*message）;设置一个循环体，循环次数是消费者消费产品的数量，每次生消费一个产品。

新建slot类型变量message，调用管程ring的方法，分别是

ring->Enter（）;

ring->Get（message）;

ring->Exit（）;

实验收获：

1.需要注意的一点是，唤醒者等待队列是属于管程的

2.增强了对进程同步与互斥问题的实际编程、调试和分析问题的能力。

4.调试及运行

1、在终端里进入到threads的文件夹目录，在终端里面输入make命令，执行编译和链接

2、输入./nachos运行程序，运行的一次结果为:

ckp@ckp-Lenovo-3000-G430:

~/桌面/nachos-3.4_2_1/code/threads$./nachos

Thread:

生产者AisRun

生产者A开始执行

生产者A进入管程

生产者Aapplymutex

生产者Agetmutex

生产者A生产一个产品，当前产品个数：

1，放入一个：

生产者Areleasemutex

生产者A退出

生产者A进入管程

生产者Aapplymutex

生产者Agetmutex

Thread:

生产者BisRun

生产者B开始执行

生产者B进入管程

生产者Bapplymutex

生产者Bsleep

Thread:

消费者AisRun

消费者A开始执行

消费者A进入

消费者Aapplymutex

消费者Asleep

Thread:

消费者BisRun

消费者B开始执行

消费者B进入

消费者Bapplymutex

消费者Bsleep

Thread:

生产者AisRun

生产者A生产一个产品，当前产品个数：

2，放入一个：

生产者Areleasemutex

wake生产者BfromQ

生产者A退出

生产者A进入管程

生产者Aapplymutex

生产者Agetmutex

生产者A生产一个产品，当前产品个数：

3，放入一个：

生产者Areleasemutex

wake消费者AfromQ

生产者A退出

生产者A进入管程

生产者Aapplymutex

生产者Agetmutex

Thread:

生产者BisRun

生产者Bsleep

Thread:

消费者AisRun

消费者Asleep

Thread:

生产者AisRun

生产者A生产一个产品，当前产品个数：

4，放入一个：

生产者Areleasemutex

wake消费者BfromQ

生产者A退出

生产者A进入管程

生产者Aapplymutex

生产者Agetmutex

缓冲区满!

生产者A->waitQ

生产者Areleasemutex

wake生产者BfromQ

Thread:

消费者BisRun

消费者Bgetmutex

消费者B得到一个产品当前产品个数1产品0;

消费者Bwakeup生产者A

消费者Breleasemutex

wake消费者AfromQ

消费者B唤醒一个进程

消费者Bapplymutex

消费者Bsleep

Thread:

生产者BisRun

生产者Bgetmutex

生产者B生产一个产品，当前产品个数：

1，放入一个：

在等待队列中唤醒一个进程

生产者Breleasemutex

wake消费者BfromQ

Thread:

生产者AisRun

生产者Aapplymutex

生产者Asleep

Thread:

消费者AisRun

消费者Asleep

Thread:

消费者BisRun

消费者Bgetmutex

消费者Bapplymutex

消费者Bsleep

Thread:

生产者BisRun

生产者Breleasemutex

wake生产者AfromQ

生产者B退出

生产者B进入管程

生产者Bapplymutex

生产者Bgetmutex

缓冲区满!

生产者B->waitQ

生产者Breleasemutex

wake消费者AfromQ

Thread:

生产者AisRun

生产者Agetmutex

生产者A生产一个产品，当前产品个数：

5，放入一个：

在等待队列中唤醒一个进程

生产者Areleasemutex

wake消费者BfromQ

生产者A退出

生产者A执行结束

Thread:

消费者AisRun

消费者Agetmutex

消费者A得到一个产品当前产品个数5产品0;

消费者Awakeup生产者B

Thread:

消费者BisRun

消费者Bsleep

Thread:

生产者BisRun

生产者Bapplymutex

生产者Bsleep

Thread:

消费者AisRun

消费者Areleasemutex

wake消费者BfromQ

消费者A唤醒一个进程

消费者Aapplymutex

消费者Agetmutex

消费者Aapplymutex

消费者Agetmutex

唤醒一个进程

消费者Areleasemutex

wake生产者BfromQ

消费者A退出

消费者A进入

消费者Aapplymutex

消费者Agetmutex

消费者A得到一个产品当前产品个数3产品0;

唤醒一个进程

消费者Areleasemutex

Thread:

消费者BisRun

消费者Bgetmutex

消费者Breleasemutex

消费者B退出

消费者B进入

消费者Bapplymutex

消费者Bgetmutex

消费者B得到一个产品当前产品个数4产品0;

消费者Breleasemutex

消费者B退出

消费者B进入

消费者Bapplymutex

消费者Bgetmutex

消费者B得到一个产品当前产品个数1产品0;

消费者Breleasemutex

消费者B退出

消费者B进入

消费者Bapplymutex

消费者Bgetmutex

消费者B得到一个产品当前产品个数5产品0;

Thread:

生产者BisRun

生产者Bsleep

Thread:

消费者AisRun

消费者A退出

消费者A进入

消费者Aapplymutex

消费者Asleep

Thread:

消费者BisRun

消费者Breleasemutex

wake生产者BfromQ

消费者B退出

消费者B进入

消费者Bapplymutex

消费者Bgetmutex

缓冲区空!

消费者B->waitQ

消费者Breleasemutex

wake消费者AfromQ

Thread:

生产者BisRun

生产者Bgetmutex

生产者B生产一个产品，当前产品个数：

2，放入一个：

生产者Bwakeup消费者B

生产者Breleasemutex

生产者B唤醒一个进程

生产者Bapplymutex

生产者Bgetmutex

生产者Bapplymutex

生产者Bgetmutex

生产者Breleasemutex

Thread:

消费者AisRun

消费者Agetmutex

消费者A得到一个产品当前产品个数2产品0;

消费者Areleasemutex

消费者A退出

消费者A进入

消费者Aapplymutex

消费者Agetmutex

缓冲区空!

消费者A->waitQ

消费者Areleasemutex

Thread:

消费者BisRun

消费者Bapplymutex

消费者Bgetmutex

消费者B得到一个产品当前产品个数4产品0;

消费者Breleasemutex

消费者B退出

消费者B执行结束

Thread:

生产者BisRun

生产者B退出

生产者B进入管程

生产者Bapplymutex

生产者Bgetmutex

生产者B生产一个产品，当前产品个数：

3，放入一个：

生产者Bwakeup消费者A

Thread:

消费者AisRun

消费者Aapplymutex

消费者Asleep

Thread:

生产者BisRun

生产者Breleasemutex

wake消费者AfromQ

生产者B唤醒一个进程

生产者Bapplymutex

生产者Bgetmutex

生产者Bapplymutex

生产者Bgetmutex

生产者Breleasemutex

生产者B退出

生产者B进入管程

生产者Bapplymutex

生产者Bgetmutex

生产者B生产一个产品，当前产品个数：

4，放入一个：

生产者Breleasemutex

生产者B退出

生产者B进入管程

生产者Bapplymutex

生产者Bgetmutex

生产者B生产一个产品，当前产品个数：

5，放入一个：

Thread:

消费者AisRun

消费者Asleep

Thread:

生产者BisRun

生产者Breleasemutex

wake消费者AfromQ

生产者B退出

生产者B执行结束

Thread:

消费者AisRun

消费者Agetmutex

消费者A得到一个产品当前产品个数4产品0;

消费者Areleasemutex

消费者A退出

消费者A进入

消费者Aapplymutex

消费者Agetmutex

消费者A得到一个产品当前产品个数5产品0;

消费者Areleasemutex

消费者A退出

消费者A执行结束

Nothreadsreadyorrunnable,andnopendinginterrupts.

Assumingtheprogramcompleted.

Machinehalting!

Ticks:

total1000,idle20,system980,user0

DiskI/O:

reads0,writes0

ConsoleI/O:

reads0,writes0

Paging:

faults0

NetworkI/O:

packetsreceived0,sent0

5.结论分析与体会

实验结果的注释很好的说明了本实验如何运用管程使生产者消费者问题的执行过程,多次验证,当唤醒者唤醒一个线程时,被唤醒者立即执行,唤醒者加入到唤醒者等待队列中,当被唤醒者阻塞或者离开管程时才继续执行.由此看出,本实验符合Hoare样式的条件,满足了实验要求。

内部资料

仅供参考

9JWKffwvG#tYM*Jg&6a*CZ7H$dq8KqqfHVZFedswSyXTy#&QA9wkxFyeQ^!

djs#XuyUP2kNXpR

WXmA&UE9aQ@Gn8GK8!