【考研】操作系统：2014年真题47（同步互斥问题） |
您所在的位置：网站首页 › 同步互斥问题的判断依据 › 【考研】操作系统：2014年真题47（同步互斥问题） |
【考研】操作系统：2014年真题47（同步互斥问题）
|
前言
解决同步互斥问题的思路，源于对王道讲解的总结笔记 同类型题目： 【考研】操作系统：2019年真题43（同步互斥问题）_住在阳光的心里的博客-CSDN博客 【考研】操作系统：2015年真题45（同步互斥问题）_住在阳光的心里的博客-CSDN博客 【考研】操作系统：2009年真题45（同步互斥问题）_住在阳光的心里的博客-CSDN博客 2014年真题47，是生产者-消费者经典问题的变型，可先参考学习生产者-消费者经典问题。 OS知识点汇总（考研用）——第二章：进程管理（下）_左职新手的博客-CSDN博客 一、思路解决同步互斥问题，思路步骤： 1. 分析各进程之间的同步互斥关系； 2. 设置互斥信号量 mutex = 1、同步信号量（一般设可使用的资源数为empty = N）。 3. 最好画出同步互斥关系图，并判断属于哪一种类型，如生产者-消费者问题、读者-写者问题、哲学家进餐问题、吸烟者问题。 二、题目45. 系统中有多个生产者进程和消费者进程，共享用一个可以存 1000 个产品的环形缓冲区（初始为空），当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时， 消费者进程可以取走一件产品， 否则等待。 要求一个消费者进程从缓冲区连续取出 10件产品后，其他消费者进程才可以取产品，请用信号量 P, V（ wait ， signed ）操作实现进程间的互斥和同步，要求写出完整的过程；并指出所用信号量的含义和初值。 解：（1）互斥资源： 一个消费者进程从缓冲区连续取出 10件产品后，其他消费者进程才可取产品，设置互斥信号量 mutex1 = 1; 生产者和消费者对缓冲区的访问进行设置互斥信号量：mutex2 = 1; （2）同步关系：生产者和消费者进程共享用一个可以存 1000 个产品的缓冲区（初始为空），则设同步信号量 empty = 1000，代表有几个空闲缓冲单元; 设同步信号量 full = 0，代表此时缓冲区的产品数; （3）同步互斥关系图如下：（生产者-消费者的变型） （4）伪代码如下： 第一步：设置信号量 semaphore mutex1 = 1; semaphore mutex2 = 1; semaphore empty = 1000; // 有几个空闲缓冲单元 semaphore full = 0;第二步：首先确定是生产者-消费者的问题，列出如下伪代码 producer(){ while(1){ 生产一个产品； 把产品放入缓冲区； } } consumer(){ while(1){ 从缓冲区取出一件产品； 消费这件产品； } }第三步：再设置进程单次互斥访问缓冲区 producer(){ while(1){ 生产一个产品； P(mutex2); 把产品放入缓冲区； V(mutex2); } } consumer(){ while(1){ P(mutex2); 从缓冲区取出一件产品； V(mutex2); 消费这件产品； } }第四步：生产者：放产品前判断缓冲区是否有空位；消费者：取出产品后再腾出空位。 producer(){ while(1){ 生产一个产品； P(empty); // 判断缓冲区是否有空位 P(mutex2); 把产品放入缓冲区； V(mutex2); } } consumer(){ while(1){ P(mutex2); 从缓冲区取出一件产品； V(mutex2); V(empty); // 取出产品后再腾出空位 消费这件产品； } }第五步：在生产者生产一个产品后，此时缓冲区的产品数加一；在消费者使用一个产品后，此时缓冲区的产品数减一； producer(){ while(1){ 生产一个产品； P(empty); // 判断缓冲区是否有空位 P(mutex2); 把产品放入缓冲区； V(mutex2); V(full); // 缓冲区产品数加一 } } consumer(){ while(1){ P(full); // 缓冲区产品数减一 P(mutex2); 从缓冲区取出一件产品； V(mutex2); V(empty); // 取出产品后再腾出空位 消费这件产品； } }第六步：与经典的生产者-消费者问题的不同在于，要求一个消费者进程从缓冲区连续取出 10件产品后，其他消费者进程才可取产品。 所以，用互斥信号mutex1来实现消费者之间的制约, 用 for 循环来实现一个消费者连续取10次后，下一个消费者才可从缓冲区取产品。 producer(){ while(1){ 生产一个产品； P(empty); // 判断缓冲区是否有空位 P(mutex2); 把产品放入缓冲区； V(mutex2); V(full); // 缓冲区产品数加一 } } consumer(){ while(1){ P(mutex1); // 设置互斥信号量，实现一个消费者进程一个周期（10次）内次对缓冲区的控制 for(int i = 0; i < 10; i++){ // 用 for 循环实现连续取 10 次 P(full); // 缓冲区产品数减一 P(mutex2); 从缓冲区取出一件产品； V(mutex2); V(empty); // 取出产品后再腾出空位 消费这件产品； } V(mutex1); } }完整代码如下： semaphore mutex1 = 1; semaphore mutex2 = 1; semaphore empty = 1000; // 有几个空闲缓冲单元 semaphore full = 0; producer(){ while(1){ 生产一个产品； P(empty); // 判断缓冲区是否有空位 P(mutex2); 把产品放入缓冲区； V(mutex2); V(full); // 缓冲区产品数加一 } } consumer(){ while(1){ P(mutex1); // 设置互斥信号量，实现一个消费者进程一个周期（10次）内次对缓冲区的控制 for(int i = 0; i < 10; i++){ // 用 for 循环实现连续取 10 次 P(full); // 缓冲区产品数减一 P(mutex2); 从缓冲区取出一件产品； V(mutex2); V(empty); // 取出产品后再腾出空位 消费这件产品； } V(mutex1); } } 三、进一步理解系统中有多个生产者进程和消费者进程，共享用一个可以存 1000 个产品的环形缓冲区（初始为空）。 环形缓冲区，相当于一个循环队列。可以设置一个大小为1000的循环缓冲区。
在本题里，不用再额外判断循环队列是否“满 / 空”，因为设置了 P(mutex) 和 P(full) 来分别判断缓冲区是否有空位，缓冲区是否有产品。 备注：判断栈、队列为 “ 满 / 空 ” 和其长度。 满空长度栈s->top == maxsize - 1;s->top == -1; 顺序栈：s->top == s->base; 链栈：s->next == NULL s->top + 1;队列(Q.rear + 1) % maxsize == Q.frontQ.front == Q.rear == 0 链队： if(Q.rear == NULL) return 1; (rear - front + maxsize) % maxsize |
【本文地址】
今日新闻 |
推荐新闻 |