死锁问题的解决

生产者和消费者死锁问题的解决 ——基于windows环境的实验 一．实验目的： 1．掌握基本的同步互斥算法，理解生产者和消费者模型。 2．了解Windows2000／XP中多线程的并发执行机制，线程间的同步和互斥 3．学习使用Windows2000／XP中基本的同步对象，掌握相应的API。 二．实验要求 2．1创建生产和消费者线程 在Windows2000环境下，创建一个控制台进程，在此进程中创建n个线程来模拟生产者或者消费者。 这些线程的信息由我们在本程序定义的“测试用例文件”中予以指定。该文 件的格式和含义如下： 3 1 P 3 2 P 4 3 C 4 1 4 P 2 5 C 3 1 2 4 ＃ 第一行说明程序中设置几个缓冲区，其余每行分别描述了一个生产者或者消费者线程的信息。每 一行的各字段间用Tab 键隔开。不管是消费者还是生产者，都有一个对应的线程号，即每一行开始字段 那个整数。第二个字段用字母P 或者C 区分是生产者还是消费者。第三个字段表示在进入相应线程后， 在进行生产和消费动作前的休眠时间，以秒计时；这样做的目的是可以通过调整这一列参数，控制开始 进行生产和消费动作的时间。如果是代表生产者，则该行只有三个字段。如果代表消费者，则该行后边 还有若干字段，代表要求消费的产品所对应的生产者的线程号。所以务必确认这些对应的线程号存在并 且该线程代表一个生产者。最后一个符号“＃”，表示文件的结束。 2．2 生产和消费的规则 在按照上述要求创建线程进行相应的读写操作时，还需要符合以下要求 (1)共享缓冲区存在空闲空间时，生产者即可使用共享缓冲区。 (2)从上边的测试数据文件例子可以看出，某一生产者生产一个产品后，可能不止一个消费者，或 者一个消费者多次地请求消费该产品。此时，只有当所有的消费需求都被满足以后，该产品所在的共享 缓冲区才可以被释放，并作为空闲空间允许新的生产者使用。 (3)每个消费者线程的各个消费需求之间存在先后顺序。例如上述测试用例文件包含一行信息“5 C 3 1 2 4”，可知这代表一个消费者线程，该线程请求消费1，2，4 号生产者线程生产的产品。而这种消 费是有严格顺序的，消费1 号线程产品的请求得到满足后才能继续 (4)要求在每个线程发出读写操作申请、开始读写操作和结束读写操作时分别显示一行提示信息。 三．相关基础知识 3．1 生产者和消费者模型 本实验所使用的生产者和消费者模型具有如下特点： (1)本实验的多个缓冲区不是环形循环的，也不要求按顺序访问。生产者可以把产品放到目前某一 个空缓冲区中。 (2)消费者只消费指定生产者的产品。 (3)在测试用例文件中指定了所有的生产和消费的需求，只有当共享缓冲区的数据满足了所有关于 它的消费需求后，此共享缓冲区才可以作为空闲空间允许新的生产者使用。 (4)本实验在为生产者分配缓冲区时各生产者间必须互斥，此后各个生产者的具体生产活动可以并 发。而消费者之间只有在对同一产品进行消费时才需要互斥，同时它们在消费过程结束时需要判断该 消费对象是否已经消费完毕并清除该产品。 3．2 同步对象 Windows 用来实现同步和互斥的实体。在Windows 中，常见的同步对象有：信号量(Semaphore)、 互斥量(Mutex)、临界段(CriticalSection)和事件(Event)等。本程序中用到了前三个。使用这些对象都分 为三个步骤，一是创建或者初始化：接着请求该同步对象，随即进入临界区，这一步对应于互斥量的 上锁；最后释放该同步对象，这对应于互斥量的解锁。这些同步对象在一个线程中创建，在其他线程 中都可以使用，从而实现同步互斥。当然，在进程间使用这些同步对象实现同步的方法是类似的。 四．程序的实现 4．1 程序的结构 程序分为一个主函数、分别用于模拟消费和生产者的两个函数以及三个辅助性的函数。主函数用 于初始化缓冲区和各个同步对象，并完成线程信息的读入和记录，最后根据该组线程记录启动模拟线 程，并等待所有线程的运行结束后退出整个程序。消费者和生产者函数运行于相应线程中完成对缓冲 区的读写动作，根据此处生产消费模型的特点，生产者和消费者线程之间通过同步对象的使用实现了 生产和消费动作的同步与互斥，是本试验的核心所在。另外三个辅助函数被生产者和消费者函数调用， 是上述生产和消费函数中对缓冲区访问功能的一些包装。程序的流程如图1-1 所示 4．2 数据结构 (1)用一个整型数组Buffer_Critical 来代表缓冲区。不管是生产产品还是对已有产品的消费都需要 访问该组缓冲区。 (2)在程序中用一个自定义结构ThreadInfo记录一条线程的信息，即将测试用例文件中的一行信息记 录下来，用于程序创建相应的生产者或者消费者。由于要创建多个线程，所以程序中使用了一个 ThreadInfo结构的数组Thread lnfo。 (3)在实现本程序的消费生产模型时，具体地通过如下同步对象实现互斥：一个互斥量h_mutex，以 实现生产者在查询和保留缓冲区内的下一个空位置时进行互斥。每一个生产者用一个信号量与其消费 者同步，通过设置h _Semaphore[MAXTHREAD_NUM]信号量数组实现，该组信号量用于表示相应产品 已生产。同时用一个表示空缓冲区数目的信号量empty_semaphore进行类似的同步，指示缓冲区中是否 存在空位置，以便开始生产下一个产品。每一个缓冲区用一个同步对象实现该缓冲区上消费者之间的 互斥，这通过设置临界区对象数组PC_Critical[MAX_BUFFER_NUM]实现。 (4)为了实现初始化的线程触发的模拟，还要自己额外定义一些东西。 首先，建立一个线程信息的ThreadInfo类型的数组，用来储存从文件读入信息的。 然后，由于我们并不知道消费者要消费多少个产品，因此我们的ThreadInfo类型必需要有一个数据 结构用来存储这个信息，这里我用了vector去管理消费者的个数。用getline去读入文件每一行的信息， 遇到‘\0’就结束，这样便可以方便的记录消费者对应的产品。 接着，由于我们要求当消费者所有要求的产品都消费完后，一定要释放空间，我们怎样才能知道 呢？通过查询h_Semaphore数组显然是不现实的。这里我用了一个数组： int prdt_time[MAXTHREAD_NUM+1]; //每个生产者线程对应多少个消费者 专门记录每个产品应该被消费多少次，当消费次数为0时，释放空间；这个数组的初始化随同文件 读入完成。 最后，也是最重要的，怎样模拟线程的产生呢？我们知道的是：要按文件提供的延迟来使线程生 成。直接对ThreadInfo类型的数组进行排序，这样消耗很大，于是我自己定义一个节点结构： struct node{ int delay; //延迟 int que_num; //从文件读入的序号,就是对应的thread_info队列的下标 }; 如上代码解析所示，它包含线程的队列号，即ThreadInfo数组的下标，以及该线程的延迟；这个结 构是专门用来为下面的结构服务的： vector Begin_que; //产生线程的次序队列 这是个记录线程产生先后的队列，用sort算法对它的节点排序，延迟小的在队首，就可以实现线程 生成的模拟了。 (5)在结果输出时，还要主要输出流的互斥保护： CRITICAL_SECTION print_mutex; 4．3 代码实现 代码的实现基本是按流程图进行；具体看附件 1（cpp实现），里面对主要过程都加以了注释。 五． 实验结果分析 5．1 下面我们对前面提供的测试数据做一个分析： 3 1 P 3 2 P 4 3 C 4 1 4 P 2 5 C 3 1 2 4 ＃ 程序输出结果： Begin_que的顺序是：线程4－>线程1－>线程5－>线程2－>线程3。线程4等待了2秒，然后在第0 个buffer位置产生一个产品，它的任务完成了，就结束。1号和5号再等待1秒，同时并发，可以看到是1 号比5号先生成，1号在buffer第1个位置产生产品，然后任务完成。5号线程是消费线程，马上消费1号 线程的产品。接着，2号和3号线程等待1秒后同时触发，2号产品生成后，并没有马上结束了，在它结 束之前，其它线程做了这样的操作：5号消费线程消费了2号产品。然后3号线程再次消费1号产品，这 时，1号产品应该被清除，而之前的2号产品也该被清楚。如图，清除了位于buffer第2个位置的2号产品 后，跟着便清楚位于第一个位置的1号产品。然后线程5消费4号产品，此时3号线程任务完成，汇报于 屏幕，这时5号线程把位于第0个位置的不分buffer空间清除，5号线程任务完成。至此，整个模拟完成。 5．2 另一组数据的分析 下面我们对于这样一个测试数据再做一次分析： 3 1 P 5 2 P 4 3 P 2 4 C 3 1 3 2 ＃ 由于我们在一个循环中创建了这四个进程，所以可以近似地认为它们是同时开始运转的。基于这 样的假设，再观察第3 列的时间参数，可以发现，最早动作的应该是3号生产者线程。这时它在3个缓 冲区之一中生产了产品。接下来应该是4 号消费者，其开始请求1 号生产者的产品，由于该产品还不 存在，故本线程被阻塞。接下来是2 号生产者生产产品，而4 号消费者依然处于阻塞状态。等到第5 秒 钟1 号生产者完成生产后，4号消费者被激活，由于此时所要求的1、3、2 号生产者的产品都已就绪， 所以4号消费者即顺次进行3 个产品的消费。由于这里对每一个产品的第一次消费也是对它的最后一次 消费，所以，每消费一个产品后随即释放该产品所占缓冲区空间。至此，模拟程序就成功运行完毕。 我们看一下程序的结果： 通过观察，发现跟分析是一致的，再次证明程序的正确性。 5．3 死锁问题 然而，通过设定消费者对特定的生产者产品的请求顺序，再配合时间参数，可以发现在某种情况 下会出现死锁。让我们再来分析如下一个例子，测试用例文件如下： 2 1 P 2 2 C 1 3 1 4 3 P 4 4 P 3 # 在上述情况下，惟一的消费者2号线程等待了1秒钟之后首先请求3号生产者线程的产品。通过第3 列时间参数可知：在3 号生产者线程(等待4 秒钟)进行生产活动之前生产者线程1号(等待2 秒钟)和4 号(等待3 秒钟)已经完成了生产，此时全部的两个缓冲区已被占用，等待2 号消费者线程取走产品。但 是3 号生产者线程由于得不到空缓冲区而陷入阻塞，而2号线程由于取不到3号线程的产品也处于等待。 这是因为消费者线程对产品请求的次序是生产者线程3、1、4，使得生产者线程1 和4的产品不能被取 走而无法释放缓冲区，从而造成一种死锁状态。 图5.3.1 光标一直闪动，但程序没有往下发展，出现“死锁”。在下面一节，我们将讨论该程序遇到的问 题，以及死锁问题的一种解决方法。 5．4 输入文件格式问题 注意字符之间的空格不是space键，而是Tab键，每一行的结尾不能有任何字符，包括空格符。否 则，读入文件会产生错误，使程序不能正确模拟整个过程。 六．问题以及死锁的一种解决方法 6．1 输出结果时出现乱序。 后来在把输出添加了临界区保护，解决了这个问题。 6．2 当我把模拟线程产生时间加大一些，出现的问题： 部分文字出现重叠。这里前提是已经把输出流用临界区实现互斥，如图 6.2.1。 开始时候，以为是系统在输出时候有问题。然后自己加 2个缓冲的字符数组：buffer和 consum_buf 来看是否能解决问题，发现并没有帮助。 经过多次的细心检查，发现生产者线程函数有一个输出漏了用临界区保护，加上保护后输出的这 部分没有问题了。原来是自己的粗心！ 图 6.2.1 6．3 本实验对于死锁的研究 6.3.1死锁的条件为： 互斥条件； 占有且等待条件； 非抢占（不可剥夺条件）； 循环等待条件。 6.3.2 求助于

书

关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf

本： 根据产生死锁的四个条件，只要使其中之一不能成立，死锁就不会出现。间接的死锁预防方法： (1)破坏互斥条件: (2)破坏占有等待条件: (3)破坏非剥夺条件: 直接的死锁预防方法： (4)破坏循环等待条件: 6.3.3我的决策：消费者做出一点牺牲来解决死锁问题。 观察本实验，可以发现出现死锁的情况为：buffer 一定的情况下，当 buffer 没有空位置时，消费 者线程等待消费的产品不能产生，使得消费与生产产生循环等待。 显然，不能改变“互斥”和“非抢占”的条件，这样会破坏整个模拟的前提。 要不，我们改变 buffer 区域的大小吧。这样子可行，但是却违背了这个实验的初衷；如果真的这 样，倒不如把 buffer看成无限空间，就像课本的“生产者消费者问题”一样去实现算了。 于是，我采用的方法是：基于资源分配的当前状态做动态选择来避免死锁。考虑到每个消费者线 程记录都有一个 vector 保存消费产品（按消费者消费要求顺序），我们能不能当出现死锁的时候，消费 者做出让步，调整一下它的消费习惯，也就是它的所要求的消费顺序。

答案

八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案

是可以的。下面我们来实现 “消费者做出一点牺牲来解决死锁问题”。 首先，消费者怎样发现死锁呢？ 当出现这种情况即可判断为死锁：当 buffer没有空位置时，并且函数WaitForSingleObject等待超 时（等待可设置超时时间大一些，我设置为 10s）。在程序实现： #01…for(iter=deal_dLock[ThreadID].begin();iter!=deal_dLock[ThreadID].end();++iter) #02…{ #03… check_dlock = WaitForSingleObject(h_semaphore[*iter],10000); //等待时间为10s #04… while(check_dlock==WAIT_TIMEOUT &&can_product()==-1) #05… { #06… EnterCriticalSection(&print_mutex); #07… cout<<"\n\nThe no."<