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

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

1、操作系统课程设计2、管程的实现（生产者消费者问题） 1.设计背景： 管程是一种高级抽象数据类型，它支持在它的函数中隐含互斥操作。结合条件变量和其他一些低级通信原语，管程可以解决许多仅用低级原语不能解决的同步问题。例如，本实验中利用管程提供一个不会发生死锁的生产者消费者问题就是利用管程的很好的例子。 管程封装了并发进程或线程要互斥执行的函数。为了让这些并发进程或线程在管程内互斥的执行，管程的实现必须隐含的具有锁或二值信号量。 如果没有条件变量，管程就不会有很有用，条件变量提供了一种对管程内并发协作进程的同步机制。条件变量代表了管程中一些并发进程或线程可能要等待的条件。一个条件变量管理着管程内的一

2、个等待队列。如果管程内某个进程或线程发现其执行条件为假，则该进程或线程就会被条件变量挂入管程内等待该条件的队列。如果管程内另外的进程或线程满足了这个条件，则它会通过条件变量再次唤醒等待该条件的进程或线程，从而避免了死锁的产生。所以，一个条件变量C应具有两种操作C.wait()和C.signal()。 当管程内同时出现唤醒者和被唤醒者时，由于要求管程内的进程或线程必须互斥执行，因此就出现了两种样式的条件变量：Mesa Style(signal-and-continue):唤醒者进程或线程继续执行，被唤醒者进程或线程等到唤醒者进程或线程阻塞或离开管程后再执行。Hoare Style(signal-

3、and-wait):被唤醒者进程或线程立即执行，唤醒者进程或线程阻塞，直道被唤醒者阻塞或离开管程后再执行。我们实验所做的就是在原来mesa样式的基础上进行Hoare样式的改进;这种样式也是我们实验中需要实现的样式。2.设计目标验证并分析Nachos中Bridge管程是否能够正确的解决单行桥双向过桥问题。n 定义和实现Hoare样式的条件变量Condition_H类n 利用Hoare样式的条件变量Condition_H,实现Ring类中定义的各个方法,使用Ring管程解决生产者/消费者问题。利用Ring对象的Put操作和Get操作代替信号量来完成同步操作。这样就避免了由于不恰当的使用信号量而引起

4、的死锁和饥饿问题。n 利用Hoare样式的条件变量Condition_H,实现Dp管程中定义的各个方法,使用Ring管程解决哲学家就餐问题。避免了由于不恰当的使用信号量而引起的死锁和饥饿问题。3.设计环境我们将使用以下的环境和资料学习和实验Nachos系统，展开我们的操作系统设计。0 1.实验环境为linux操作系统。1 2.Nachos-3.4版系统源代码电子文档及相关编译软件gcc-2.8.1-mips。2 3.Study Book ：讲授Nachos系统的原理和实现的教材。3 4.Introductory Book：讲授Nachos系统的实验方法、实验步骤、实验要求的实验指导书。4.设计

5、说明1.Hoare样式条件变量设计算法说明：对于Hoare样式管程，相比于Mesa样式新增了一个唤醒者等待队列。在Hoare样式中，唤醒者唤醒被唤醒者后，被唤醒者加入到readytorun队列中，将被唤醒者加入到唤醒者等待队列中，被唤醒者阻塞或者离开时会唤醒唤醒者等待队列中的一个唤醒。这样我们需要一个新的条件变量，重写它的wait（）和signal（）方法来实现Hoare样式管程。设计内容和步骤：在synch.h文件中定义一个新的结构体Condition_H。结构体Condition_H中包含的私有变量有char* name（条件变量名称）、List* queue（等待在该条件变量的线程）、L

6、ock* lock（管程锁，条件变量共享）、Semaphore *next（指向唤醒者等待队列，条件变量共享）、int *nextCount（记录唤醒者等待队列中线程数量，条件变量共享）；方法有char* getName()、void Wait(Lock *conditionLock)、void Signal(Lock *conditionLock)。在synch.cc文件中定义结构体Condition_H中方法的具体实现。在方法 Condition_H:Wait (Lock *conditionLock) 中，首先判断队列是否为空，是则把传入的锁赋给条件变量的锁。调用条件变量的等待队列que

7、ue的Append(currentThread)方法，把当前线程放入等待队列中当前线程释放锁。如果唤醒这等待队列中有线程，则唤醒一个线程，即把它加入readytorun队列中，调用了条件变量next的V方法。当前线程sleep，放弃资源，在readytorun队列中选取下一个执行的线程，该线程申请锁。在方法void Condition_H:Signa l(Lock *conditionLock)中，如果条件变量的等待队列queue非空则从中移除一个线程，并把该线程放入readytorun等待队列中。当前线程释放锁，并把当前线程加入唤醒这等待队列中，调用了条件变量next的P方法。在readyt

8、orun队列中选取下一个执行的线程，该线程申请锁。如果队列为空，则不做。实验收获：1.需要注意的一点是，唤醒者等待队列是属于管程的2.一个常用的规则是，在.h头文件中声明方法头，然后在.cc中将具体的方法实现，这是老师上课强调的一点，在试验中应实践好。3.实验受到了张洪烈老师的鼓励与帮助，在此表示感谢。实验过程中，具体实现的每一个思想都会遇到很多问题，有的时候可能只是一个未知的知识点的忽略，受到老师点拨之后问题往往可以迎刃而解。运行结果分析：（无）2.消费者生产者管程设计算法说明：生产者消费者问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将此产品提供给消费者进程去消费

9、。为使生产者进程和消费者进程能并发执行，在它们之间设置有个缓冲区的缓冲池，生产者进程可将它所生产的产品放入一个缓冲区中，消费者进程可从一个缓冲区取得一个产品消费。使用管程的思想解决这个问题，我们需要使用两个条件变量和一个管程锁，一个唤醒者等待队列以及一系列控制的参数。方法包括void Put(slot *message); void Get(slot *message);int Full()；int Empty(); void Enter();void Exit();设计内容和步骤： slot结构体的实现。Slot结构体用于存储生产者存放和消费者所取的数据。包括两个实例变量： thread_i

10、d和 value（int类型）。ring结构体的实现。ring结构体即生产者消费者问题的管程类。包括的实例变量有： int size; /缓冲区大小 int in, out; /存放和取数据的位置记录 slot *buffer; /缓冲区（环形） Condition_H *notfull; /条件变量 Condition_H *notempty; /条件变量 Lock *mutexLock; /管程锁 Semaphore *next; /唤醒这等待队列包括的方法有： void Put(slot *message); /生产者放数据void Get(slot *message);/消费者取数据i

11、nt Full(); /缓冲区是否满int Empty(); /缓冲区是否空void Enter(); /进入管程void Exit(); /出管程ring结构体中方法的具体实现。 void Put(slot *message);判断缓冲区是否为满，满则生产者在在notfull条件变量上等待；不满则放入数据，修改变量in的值，在notempty条件变量上唤醒一个消费者。void Get(slot *message); 判断缓冲区是否为空，空则消费者在条件变量notempty上等待；不空则取出一个数据，修改变量out的值，在条件变量notfull上唤醒一个生产者。void Enter();进程获

12、取锁，进入管程，mutexLock-Acquire()。void Exit();进程释放锁，出管程，mutexLock -Release()。使用管程解决生产者消费者问题。首先生成ring变量，声明缓冲区大小，生产者消费者数量。为每一个生产者创建线程，设置优先级，运行Producer（）方法。为每一个消费者创建线程，设置优先级，运行Consumer（）方法。 Producer(_int which)设置一个循环体，循环次数是生产者生产产品的数量，每次生产一个产品。封装程slot类型变量message，调用管程ring的方法，分别是 ring-Enter(); ring-Put(message)

13、; ring-Exit();Get(slot *message); 设置一个循环体，循环次数是消费者消费产品的数量，每次生消费一个产品。新建slot类型变量message，调用管程ring的方法，分别是 ring-Enter(); ring- Get(message); ring-Exit();实验收获：1.需要注意的一点是，唤醒者等待队列是属于管程的2.增强了对进程同步与互斥问题的实际编程、调试和分析问题的能力。4.调试及运行1、在终端里进入到threads的文件夹目录，在终端里面输入make命令，执行编译和链接2、输入./nachos 运行程序，运行的一次结果为:ckpckp-Lenovo

14、-3000-G430:/桌面/nachos-3.4_2_1/code/threads$ ./nachosThread: 生产者A is Run生产者A 开始执行生产者A 进入管程生产者A apply mutex 生产者A get mutex 生产者A 生产一个产品， 当前产品个数： 1， 放入一个： 0 生产者A release mutex 生产者A 退出生产者A 进入管程生产者A apply mutex 生产者A get mutex Thread: 生产者B is Run生产者B 开始执行生产者B 进入管程生产者B apply mutex 生产者B sleepThread: 消费者A is

15、Run消费者A 开始执行消费者A 进入消费者A apply mutex 消费者A sleepThread: 消费者B is Run消费者B 开始执行消费者B 进入消费者B apply mutex 消费者B sleepThread: 生产者A is Run生产者A 生产一个产品， 当前产品个数： 2， 放入一个： 0 生产者A release mutex wake 生产者B from Q生产者A 退出生产者A 进入管程生产者A apply mutex 生产者A get mutex 生产者A 生产一个产品， 当前产品个数： 3， 放入一个： 0 生产者A release mutex wake 消费

16、者A from Q生产者A 退出生产者A 进入管程生产者A apply mutex 生产者A get mutex Thread: 生产者B is Run生产者B sleepThread: 消费者A is Run消费者A sleepThread: 生产者A is Run生产者A 生产一个产品， 当前产品个数： 4， 放入一个： 0 生产者A release mutex wake 消费者B from Q生产者A 退出生产者A 进入管程生产者A apply mutex 生产者A get mutex 缓冲区满!生产者A - waitQ生产者A release mutex wake 生产者B from

17、QThread: 消费者B is Run消费者B get mutex 消费者B 得到一个产品 当前产品个数 1 产品 0 ;消费者B wake up 生产者A消费者B release mutex wake 消费者A from Q消费者B 唤醒一个进程消费者B apply mutex 消费者B sleepThread: 生产者B is Run生产者B get mutex 生产者B 生产一个产品， 当前产品个数： 1， 放入一个： 0 在等待队列中唤醒一个进程生产者B release mutex wake 消费者B from QThread: 生产者A is Run生产者A apply mutex

18、 生产者A sleepThread: 消费者A is Run消费者A sleepThread: 消费者B is Run消费者B get mutex 消费者B apply mutex 消费者B sleepThread: 生产者B is Run生产者B release mutex wake 生产者A from Q生产者B 退出生产者B 进入管程生产者B apply mutex 生产者B get mutex 缓冲区满!生产者B - waitQ生产者B release mutex wake 消费者A from QThread: 生产者A is Run生产者A get mutex 生产者A 生产一个产品

19、， 当前产品个数： 5， 放入一个： 0 在等待队列中唤醒一个进程生产者A release mutex 生产者A release mutex wake 消费者B from Q生产者A 退出生产者A 执行结束Thread: 消费者A is Run消费者A get mutex 消费者A 得到一个产品 当前产品个数 5 产品 0 ;消费者A wake up 生产者BThread: 消费者B is Run消费者B sleepThread: 生产者B is Run生产者B apply mutex 生产者B sleepThread: 消费者A is Run消费者A release mutex wake 消

20、费者B from Q消费者A 唤醒一个进程消费者A apply mutex 消费者A get mutex 消费者A apply mutex 消费者A get mutex 唤醒一个进程消费者A release mutex 消费者A release mutex wake 生产者B from Q消费者A 退出消费者A 进入消费者A apply mutex 消费者A get mutex 消费者A 得到一个产品 当前产品个数 3 产品 0 ;唤醒一个进程消费者A release mutex 消费者A release mutex Thread: 消费者B is Run消费者B get mutex 消费者B

21、 release mutex 消费者B 退出消费者B 进入消费者B apply mutex 消费者B get mutex 消费者B 得到一个产品 当前产品个数 4 产品 0 ;消费者B release mutex 消费者B 退出消费者B 进入消费者B apply mutex 消费者B get mutex 消费者B 得到一个产品 当前产品个数 1 产品 0 ;消费者B release mutex 消费者B 退出消费者B 进入消费者B apply mutex 消费者B get mutex 消费者B 得到一个产品 当前产品个数 5 产品 0 ;Thread: 生产者B is Run生产者B slee

22、pThread: 消费者A is Run消费者A 退出消费者A 进入消费者A apply mutex 消费者A sleepThread: 消费者B is Run消费者B release mutex wake 生产者B from Q消费者B 退出消费者B 进入消费者B apply mutex 消费者B get mutex 缓冲区空!消费者B - waitQ消费者B release mutex wake 消费者A from QThread: 生产者B is Run生产者B get mutex 生产者B 生产一个产品， 当前产品个数： 2， 放入一个： 0 生产者B wake up 消费者B生产者B

23、 release mutex 生产者B 唤醒一个进程生产者B apply mutex 生产者B get mutex 生产者B apply mutex 生产者B get mutex 生产者B release mutex Thread: 消费者A is Run消费者A get mutex 消费者A 得到一个产品 当前产品个数 2 产品 0 ;消费者A release mutex 消费者A 退出消费者A 进入消费者A apply mutex 消费者A get mutex 缓冲区空!消费者A - waitQ消费者A release mutex Thread: 消费者B is Run消费者B apply

24、 mutex 消费者B get mutex 消费者B 得到一个产品 当前产品个数 4 产品 0 ;消费者B release mutex 消费者B 退出消费者B 执行结束Thread: 生产者B is Run生产者B 退出生产者B 进入管程生产者B apply mutex 生产者B get mutex 生产者B 生产一个产品， 当前产品个数： 3， 放入一个： 0 生产者B wake up 消费者AThread: 消费者A is Run消费者A apply mutex 消费者A sleepThread: 生产者B is Run生产者B release mutex wake 消费者A from Q

25、生产者B 唤醒一个进程生产者B apply mutex 生产者B get mutex 生产者B apply mutex 生产者B get mutex 生产者B release mutex 生产者B 退出生产者B 进入管程生产者B apply mutex 生产者B get mutex 生产者B 生产一个产品， 当前产品个数： 4， 放入一个： 0 生产者B release mutex 生产者B 退出生产者B 进入管程生产者B apply mutex 生产者B get mutex 生产者B 生产一个产品， 当前产品个数： 5， 放入一个： 0 Thread: 消费者A is Run消费者A sle

26、epThread: 生产者B is Run生产者B release mutex wake 消费者A from Q生产者B 退出生产者B 执行结束Thread: 消费者A is Run消费者A get mutex 消费者A 得到一个产品 当前产品个数 4 产品 0 ;消费者A release mutex 消费者A 退出消费者A 进入消费者A apply mutex 消费者A get mutex 消费者A 得到一个产品 当前产品个数 5 产品 0 ;消费者A release mutex 消费者A 退出消费者A 执行结束No threads ready or runnable, and no pen

27、ding interrupts.Assuming the program completed.Machine halting!Ticks: total 1000, idle 20, system 980, user 0Disk I/O: reads 0, writes 0Console I/O: reads 0, writes 0Paging: faults 0Network I/O: packets received 0, sent 05.结论分析与体会实验结果的注释很好的说明了本实验如何运用管程使生产者消费者问题的执行过程,多次验证,当唤醒者唤醒一个线程时,被唤醒者立即执行,唤醒者加入到唤醒者等待队列中,当被唤醒者阻塞或者离开管程时才继续执行.由此看出,本实验符合Hoare样式的条件,满足了实验要求。