做色流网站服务器,项目总结,长治电商平台网站,上海做网站那家公司好学习日期#xff1a;2024.7.10
内容摘要#xff1a;利用信号量机制解决几个经典问题模型 目录
引言
问题模型
生产者-消费者问题#xff08;经典#xff09;
多生产者-多消费者问题
吸烟者问题
读者写者问题#xff08;难点#xff09;
哲学家进餐问题#xff0…学习日期2024.7.10
内容摘要利用信号量机制解决几个经典问题模型 目录
引言
问题模型
生产者-消费者问题经典
多生产者-多消费者问题
吸烟者问题
读者写者问题难点
哲学家进餐问题避免死锁 引言
在《信号量机制》章节中我们已经学习了信号量的概念和用其实现进程同步和互斥的工作原理下面结合实际的模型来看信号量机制如何起效。
PV操作题目分析步骤
1.关系分析。找出题目中描述的各个进程分析它们之间的同步、互斥关系。
2.整理思路。根据各进程的操作流程缺点P、V操作的大致顺序。
3.设置信号量。根据题目条件确定信号量初始值互斥一般为1同步一般看对应资源的初始值
简记口诀
互斥紧邻操作成对PV。紧邻互斥操作在同一进程内完成PV
同步前V后P前后后前。在不同进程内进行操作以保证顺序执行在前一个进程完成后进行V操作在后一个进程开始前进行P操作
问题模型
生产者-消费者问题经典
系统中有一组生产者进程和消费者进程生产者每次生产一个产品放入缓冲区消费者每次从缓冲区中取出一个产品使用“缓冲区”理解为二者共享的仓库“产品”理解为某种数据 缓冲区是一个初始为空大小固定为n双方共享的区域且缓冲区是临界资源各进程必须互斥访问。原因如果不是互斥访问的可能两个生产者进程在同一片区域放入数据导致数据覆盖丢失
首先分析显然
①缓冲区没满的情况下生产者才能生产二者有同步关系。
②缓冲区不空的情况下消费者才能消费二者有同步关系。
③进程对缓冲区的访问必须互斥。
那么设置三个变量一个mutex表示互斥标记一个empty表示空闲区数目一个full表示装入区数目。每次生产者进程行动时P(empty),V(full)消费者行动时则反之
这样就能实现通过PV操作来表示资源的获取与释放。 注意实现互斥是在同一进程中进行一对PV操作在“把产品放入缓冲区/从缓冲区中取出”这一对临界资源的访问行为前后成对进行。
而同步关系是在两进程分开执行在一个进程中执行P另一个执行V。具体理论部分可以参考上一章。
Q能否交换相邻P操作的顺序
不能。假如交换了生产者的前两个P操作的顺序若缓冲区内已经放满产品此时empty0fulln。若生产者先进行P(mutex)声明自己独占了缓冲区然后P(empty)发现缓冲区的empty区不足就会进入阻塞状态。
之后消费者想占用缓冲区释放empty资源时因为生产者已经占用了mutex没有释放因为互斥会导致无法进行V(empty)操作
这样生产者在等待消费者释放empty消费者在等待生产者解除对缓冲区的占用双方会无限等待下去形成死锁。
所以表示互斥的PV部分要成对出现成对执行且实现互斥的P操作一定在实现同步操作的P操作之后。
Q:能否交换相邻V操作的顺序
可以V操作不会导致进程阻塞但是为了方便理解记忆还是让实现互斥的PV操作紧邻互斥行动区为好。
Q能否不依赖互斥标识资源mutex
通常不行但是特殊情况下可以。这个特殊情况就是缓冲区容量为1的情况即empty的初始值为1此时如果一个生产者生产了产品执行P(empty)另一个生产者也想生产产品时因为empty的值已经是0就会发生阻塞从而避免了生产者同时访问的问题。而在生产者执行完互斥操作V(full)之前因为full的值为0消费者进行P(full)时也会阻塞避免了生产者访问时消费者同时访问的问题从而不依赖mutex就能实现互斥访问。 多生产者-多消费者问题
是生产者-消费者问题的变形区别在于增加了若干组生产者和消费者。比如说1号生产者会生产1型商品2号生产者生产2型商品而1号消费者只消费1型商品2消费者只消费2型商品。
所有的生产者和消费者仍旧共享一个缓冲区此处的“多”指的是“多类”而不是“多个”与上一问题的根本区别是有多类生产者和消费者。
关系分析
①首先同生产者-消费者问题的前提一样缓冲区没满才能生产不空才能消费且互斥访问。
②根据不同资源的类型分别PV不同的变量来为每对生产者和消费者确立同步关系。
在分析同步问题的时候不能从单个进程行为的角度来分析而应该从事件角度分析。
不要想着“x号生产者生产了一个x号产品x号消费者......”然后设置四个同步信号量。而是从事件的角度分析把进程的先后顺序概括为事件的先后顺序在这个例子中就是生产产品事件先于消耗产品事件。
生产产品可以是1号生产者也可以是2号生产者它们只需要每次占用一个仓库空间P(empty)然后增加一个对应产品Vproduct_x。同样的消费者也只要每次消耗一个产品P(product_x)然后释放一个空间P(empty)就行了。最后再在互斥操作前后加上mutex的成对PV操作保证互斥根据空间的大小设置empty的初始值就可以解决问题了 吸烟者问题
仍然是生产者-消费者问题的变形。更准确的来说是“可生产多种产品的单生产者-多消费者问题”
假设一个系统有三个抽烟者进程和一个供应者进程每个抽烟者进程不停的卷烟并抽烟这需要三种材料烟草、纸卷和胶水。在三个抽烟者中第一个有烟草第二个有纸卷第三个有胶水。供应者会无限提供三种材料每次将两个材料置于桌面而拥有剩下那个材料的抽烟者就会拿走完成抽烟然后给供应者一个信号告诉他完成了供应者就会放另外两种材料在桌上让三个抽烟者能够轮流抽烟。 首先桌子可以抽象为容量为1互斥访问的缓冲区。为什么放两件东西容量为1呢
我们将供应者供应的两件东西看作是一个组合则他一共供给三个组合第一个消费者需要纸卷胶水定义为组合1第二个消费者需要烟草胶水定义为组合2同理得组合3。
这样问题就抽象为了一个生产者能生产1号2号3号三种产品分别对应三个消费者要进行轮流消费缓冲区容量为1。
关系分析
①桌上有组合x 先于 x号消费者取走东西且缓冲区互斥访问。
②消费者发出完成信号 先于 生产者将下一个组合放到桌上。 Q轮流操作如何实现
如右图所示通过一个if(i0)的选择分支结构和结尾的i(i1)%3实现了让i在012不断循环变化从而轮流执行三个部分的生产每次产生对应的offer。补充如果要随机实现可以用Randomi
而如上图每一个消费者每次消耗一个offer的商品P(offer_x),然后再释放一个finish信号给生产者保证先释放信号然后生产者再生产下一个产品。
之前介绍过因为此时缓冲区的容量为1故不需要互斥信号量mutex也可以实现互斥访问。 读者写者问题难点
在系统中有读者、写者两组并发进程共享一个文件。多个读者可以同时对文件执行读操作但是只允许一个写者往文件中写入信息写者对文件的访问必须互斥也不能边写边读每个写者在工作时都必须独占该共享文件。
与消费者进程不同读者进程在读数据时不会“消耗”数据 所以读者进程可以同时访问共享数据互不影响。
不能边读边写是因为如果允许并发执行读者可能先读了某数据的一部分但剩下的部分被写者覆盖了导致读者所读的数据并不是所期望的。不能同时写的原因同生产者进程互斥原因会相互覆盖。
关系分析
①写者进程和所有进程互斥读者进程之间不互斥。
难点就在于如何在实现写者进程互斥的同时让读者进程不互斥。
我们一步一步来
semaphore rw1writer(){while(1){P(rw); //写之前上锁写文件操作...V(rw); //写完解锁}
}reader(){while(1){P(rw); //读之前上锁读文件操作...V(rw); //读完解锁}
} 先写个最简单的但是显然这样是每个进程都互斥访问共享区不能实现同时读操作。
那么要如何实现“同时读”呢可以设法让后面的读进程跳过P(rw)这一步。
所以逻辑代码变成了这样
semaphore rw1;
int count 0; //记录当前有几个读进程在访问文件writer(){while(1){P(rw); //写之前上锁写文件操作...V(rw); //写完解锁}
}reader(){while(1){
if(count0) //由第一个读进程负责上锁P(rw); //读之前上锁count; 读文件操作...count--;
if(count0)//由最后一个读进程负责解锁V(rw); //读完解锁}
}
我们引入了一个新的变量count用来记录当前访问文件的读进程数当count0时访问文件的读进程是第一个它负责上锁之后访问的读进程因为count0就跳过了P(rw)语句从而可以直接进行读文件操作。同理当最后一个读进程读完时count0最后一个进程进行V(rw)释放资源表示没有读进程还在操作了。
但是这样还是有一个问题因为读进程是并发执行的如果两个读进程同时开始执行当第一个读者进程P(rw)以后还没有来得及count时第二个读进程可能已经通过了conunt的判断语句也进行P(rw),但是此时rw已经为0了这会导致第二个进程阻塞。
显然出现上一问题的原因是我们对count变量的检查和赋值无法一气呵成。无法一气呵成...?我们最初用PV操作就是为了解决进程互斥中软件实现方法无法一气呵成的问题的详见《进程的同步与互斥》所以可以想到再加一组互斥标识保证进程能互斥的访问count。
semaphore rw 1;
semaphore mutex 1;//用于保证对count变量的互斥访问
int count 0; //记录当前有几个读进程在访问文件writer(){while(1){P(rw); //写之前上锁写文件操作...V(rw); //写完解锁}
}reader(){while(1){P(mutex);if(count0) //由第一个读进程负责上锁P(rw); //读之前上锁count; V(mutex); 读文件操作...P(mutex);count--; if(count0)//由最后一个读进程负责解锁V(rw); //读完解锁V(mutex);}
} 我们引入了mutex变量来保证进程能互斥的访问count,此时如果两个读进程同步访问count第一个进程会P(mutex)阻止其它读进程修改count并且在自己修改完count之后其它进程才能进行if判断这样就不会出现上述问题了。两组对于mutex的PV操作能够保证进程对count的互斥访问。
但是还有一个潜在的问题受不了了只要有读进程还在读rw的值就始终是0写进程就会一直阻塞如果一直有源源不断的读进程写进程就会饥饿。在这种算法中读进程是优先的。那么该如何避免写进程饥饿呢就是说怎样能让写进程在想写入的时候在有限的等待时间内就能写入呢
semaphore rw 1;
semaphore mutex 1;//用于保证对count变量的互斥访问
semaphore w 1; //用于实现“写优先”
int count 0; //记录当前有几个读进程在访问文件writer(){while(1){P(w);P(rw); //写之前上锁写文件操作...V(rw); //写完解锁V(w);}
}reader(){while(1){P(w);P(mutex);if(count0) //由第一个读进程负责上锁P(rw); //读之前上锁count; V(mutex);V(w); 读文件操作...P(mutex);count--; if(count0)//由最后一个读进程负责解锁V(rw); //读完解锁V(mutex);}
} 我们又引入了一个新的变量w用于实现写优先。
假如三个进程读者A写者读者B并发执行。
当读者进程A通过了上半部分开始进行读文件操作时释放了w占用了rw。此时写者进程可以进行P(w)操作了但是会被阻塞在P(rw)操作上。当读者进程B开始运行时因为写进程已经进行过P(w)操作了读者B会在P(w)处被阻塞。
这样当读者A的读操作结束时count--后为0读者A会认为自己是最后一个读进程从而释放rw这样写者就可以执行P(rw)实现了写者优先于读者B执行。
此方法并不是真正的“写优先”只是保证了写进程不会饥饿相对公平的实现了先来先服务。
此处的w好比一个提供顺序功能的标记第一个读者最开始先占用然后在读文件之前释放第二个读者如果在写者之后来就会因为写者已经占用了w而不能继续。
小结
读者-写者问题为我们解决复杂的互斥问题提供了思路核心思想在于设置一个计数器count来记录当前正在访问共享文件的读进程数用count的值来判断当前进入的进程是否是第一个/最后一个读进程从而跳过部分P指令实现读进程不互斥。
在对count变量的检查和赋值不能一气呵成时采用mutex变量来确保count部分被互斥访问。
在写进程会饥饿时引入了w变量来确保可以公平的完成先来先服务。 哲学家进餐问题避免死锁
圆桌上坐着5位哲学家每两个哲学家之间摆着一根筷子桌子的中间是火锅哲学家们会思考和干饭。哲学家们在思考时不会影响别人只有想干饭时才会拿起左、右各一根筷子一根一根拿如果筷子已经在他人手上则需要等待。因为火锅很烫哲学家必须需要一双筷子才能进餐进餐完毕后哲学家放下筷子继续思考。 难点这个问题中只有互斥关系没有同步关系但是在这个模型中每个哲学家进程都需要同时持有两个临界资源才能开始吃饭。我们可以想到一个很尴尬的情况那就是每个哲学家都拿了一根筷子大家都没有办法吃饭但是都在等待别人吃饭然后让出筷子这就是死锁。这是临界资源分配不当导致的我们要设法避免这种情况发生。
关系分析
①系统中有5个哲学家进程5位哲学家与左右邻居对其之间的筷子的访问是互斥关系。
②筷子是本模型中的临界资源哲学家想要吃饭需要获取其左右两根筷子。
我们给哲学家和筷子编号为0~4。显然编号为i的哲学家需要编号i和i1的两根筷子来吃饭考虑到边界严谨的表述是i和(i1)%5
我们很容易想到一个简单的写法
这种写法能实现对筷子的互斥访问但是不能避免前面提到的死锁问题。那么该怎么解决呢
①可以要求奇数号哲学家先拿左手的筷子偶数号哲学家先拿右手的筷子。如图所示以0、1为例这样两位就会在一开始争抢1号筷子谁先拿到另一个就在不占用任何筷子的情况下直接进入阻塞态这样就避免了五个人每人占用一根筷子进入阻塞态的死锁。
以代码实现的话在每个哲学家拿筷子之前判断号码的奇偶然后确定P操作的顺序即可。
②保证至少有一个哲学家可以一气呵成的拿到完整的一双筷子。
使用mutex互斥变量保证至少有一个哲学家可以拿到完整的一双筷子。
在拿筷子的部分前后加入了mutex的PV操作。当0号哲学家拿筷子时先P(mutex)之后依次拿起左右的筷子即使在这过程中发生了进程调度别的进程也会因为mutex值已经为0被阻塞不能拿起筷子直到0号哲学家把筷子拿完释放mutex以后别的哲学家才能拿起筷子。这样能够保证至少第一个开始拿筷子的进程会一气呵成的拿到一双筷子避免死锁。
但是这个方法也有一个问题。如图所示当0号哲学家拿完一双筷子开始进餐后4号哲学家开始拿筷子因为此时mutex已经释放4号哲学家顺利执行了P(mutex)且拿起了4号筷子当想拿起0号筷子时发现被占用进入阻塞态。 此时对于2号哲学家来说他左右两侧的筷子都是可以使用的没有被占用但是如果他想进食因为4号哲学家还在占用着mutex并被阻塞所以他在执行P(mutex)时会被阻塞。明明有临界资源可以用但是却不能访问这违背了空闲让进原则这种方法的并发度不够高。
③最多允许四个哲学家同时拿起筷子。
只要最多四个哲学家同时拿起筷子就必然有至少一个哲学家可以拿起一双筷子避免了死锁。
为了解决这个问题我们可以把上个方法中mutex的初始值设置为4。这样在上一情况中4号哲学家依然会被右手的筷子阻塞但2号哲学家不会被mutex阻塞可以正常进食。
同时在极端情况即每个哲学家进程拿起一根筷子就被调度的情况中最后一个进程想要拿起筷子时会因为mutex已经为0在P(mutex)步骤中被阻塞从而在不占用任何筷子的情况下进入阻塞态这样就不会发生死锁。
小结
哲学家进餐问题的关键在于避免死锁每个进程都需要持有两个临界资源因此就有了“死锁”的隐患想避免死锁就要尽量让进程在不占用临界资源的情况下进入阻塞态。 感谢您看到这里如果满意的话麻烦您点个赞支持一下个人主页还有更多内容分享。
个人能力不足如有错漏部分还请指出我会尽快修改。
内容总结自王道计算机考研《操作系统》 和 人民邮电出版社《操作系统导论》
