操作系统（8）---进程的同步与互斥以及信号量机制（万字总结~）（2）：https://developer.aliyun.com/article/1511030
4.信号量机制实现前驱关系
进程 P1中有句代码S1，P2中有句代码S2，P3中有句代码S3...P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行:
其实每一对前驱关系都是一个进程同步问题(需要保证一前一后的操作),即每一条线都代表一前一后地同步问题。
因此:
1.要为每一对前驱关系各设置一个同步信号量，并且设置为0
2.在“前操作”之后对相应的同步信号量执行V操作
3.在“后操作”之前对相应的同步信号量执行P操作
对应的代码如下：
三.同步与互斥典型案例
1.生产者、消费者问题
系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注:这里的“产品”理解为某种数据)
生产者、消费者共享一个初始为空、大小为n的缓冲区。
对于生产者：
缓冲区没满时，生产者才能继续生产，若缓冲区满时，生产者必须阻塞等待。
消费者从缓冲区取走数据后，若此时有生产者处于阻塞状态，那么消费者进程应该唤醒生产者进程(阻塞态--->就绪态)
注：生产者进程只是回到了就绪态，这并不意味着生产者进程需要立即往缓冲区写数据
对于消费者：
缓冲区空时，消费者必须等待，缓冲区没空时，消费者才能取走数据（消费）
当生产者写入数据，缓冲区不为空，就会唤醒消费者进程（阻塞态--->就绪态）
缓冲区：
缓冲区是临界资源，各进程必须互斥地访问。
假如两个进程并发地往缓冲区写入数据，两个进程挑选了同一块区域写入数据，那么后面进程写入的数据就会覆盖前面进程写入的数据。所以各进程必须互斥访问才不会导致数据覆盖等问题。
PV操作题目分析步骤：
例：系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注:这里的“产品”理解为某种数据)
生产者、消费者共享一个初始为空、大小为n的缓冲区。
1.找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
同步：当缓冲区没满时，生产者才能生产，否则堵塞等待，当缓冲区没空时，消费者才能消费，否则堵塞等待。
互斥：对于临界资源，各进程必须互斥访问。
2.根据各进程的操作流程确定P、V操作的大致顺序
当缓冲区没空（即有产品）之后，可以执行V操作，在在消费者消费之前需要执行P操作。下面的案例同理。（前V后P）
3.设置信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)
semaphore mutex=1; //互斥信号量，实现对缓冲区的互斥访问
semaphore empty=n； //同步信号量，表示空闲缓冲区的数量
semaphore full=0; //同步信号量，表示产品的数量，也即非空缓冲区的数量
代码实现如下：
这里需要注意的是：
实现互斥是在同一进程中进行一对PV操作
实现进程的同步是在其中一个进程执行P操作，另一个进程执行V操作
P表示对临界区上锁（mutex=0），V表示对临界区解锁（mutex=1）
在这里能否改变相邻P、V操作的顺序（重要）：
若此时缓冲区内已经放满产品，即empty=0，full=n。
则生产者进程执行①，使mutex变为0，再执行②，由于已没有空闲缓冲区，因此生产者被阻塞。
由于生产者阻塞，因此切换到消费者进程。消费者进程执行③，由于mutex为0，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。
这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。
同样的，若缓冲区中没有产品，即full=0，empty=n。按③④①的顺序执行就会发生死锁。
因此，实现互斥的P操作一定要在实现同步的P操作之后
V操作不会导致进程阻塞，因此两个V操作顺序可以交换
两个红框执行语句能否放在PV操作间：
逻辑上是可以的，但这会导致临界区代码更长，也就是对临界区上锁的时间更长，这样各进程交替使用临界资源的效率就会下降。
2.多生产者、多消费者问题
这一问题的做题步骤与上一问题是一样的:
例：桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
1.找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
互斥关系：
对缓冲区(盘子)的访问要互斥地进行
同步关系（一前一后）：
1.父亲将苹果放入盘子后，女儿才能取苹果
2.母亲将橘子放入盘子后，儿子才能取橘子
3.只有盘子为空时，父亲或母亲才能放入水果
注：盘子为空”这个事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果
2.根据各进程的操作流程确定P、V操作的大致顺序。
对于互斥关系的P、V操作，只需要在临界区前后进行PV操作即可。
对于同步关系，遵循前V后P这样的关系即可。
3.设置信号量，设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)
互斥关系:mutex=1
同步关系如图：
初始值苹果和橘子都为0，即apple=0，orange=0，而刚开始盘子是空的，父亲和母亲都可以向盘子中放入水果，所以plate=1。
若我们从单个进程行为角度来考虑的话：
如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果
如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果
这样分析会产生冗余的前-后关系，我们应该从事件的角度分析，即从事件的前后关系下手：
盘子变空事件→放入水果事件。
“盘子变空事件”既可由儿子引发，也可由女儿引发;
“放水果事件”既可能是父亲执行，也可能是母亲执行。
这样的话，就可以用一个同步信号量解决问题了。
代码实现如下：
父亲进程：
P（plate）操作用来检查盘子是否为空，V（apple）操作，用于告诉女儿进程，盘子中苹果数量+1
母亲进程：
P（plate）用于检查盘子是否为空，若盘子中有其他水果，该P操作就会阻塞，V（orange）操作用于告诉儿子进程，盘子中橘子数+1
女儿进程：
P（apple）进程用于检查盘子中是否有苹果，V（plate）进程用于告诉父亲母亲进程盘子已经为空。
儿子进程：
P（orange）进程用于检查盘子中是否有橘子，V（plate）进程用于告诉父亲母亲进程盘子已经为空。
再加上加锁解锁的互斥PV操作即可。
可不可以不用互斥信号量,即:
刚开始，儿子、女儿进程即使上处理机运行也会被阻塞。如果刚开始是父亲进程先上处理机运行，则:
父亲 P(plate)，可以将苹果放入盘子
若此时母亲也想放入橘子，即P(plate)，阻塞等待盘子
父亲放入苹果V(apple)，女儿进程被唤醒，其他进程即使运行也都会阻塞，暂时不可能访问临界资源(盘子)，女儿P(apple)，访问盘子，V(plate)后，等待盘子的母亲进程被唤醒，母亲进程访问盘子，即将橘子放到盘子中，plate=0(其他进程暂时都无法进入临界区)
所以，即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象
原因在于:
本题中的缓冲区大小为1，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是1。因此在任何时刻最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。
若将临界资源数=2
父亲 P(plate)，可以访问盘子，母亲 P(plate)，也可以访问盘子→父亲在往盘子里放苹果，同时母亲也可以往盘子里放橘子。于是就出现了两个进程同时访问缓冲区的情况，有可能导致两个进程写入缓冲区的数据相互覆盖的情况。
因此，如果缓冲区大小大于1，就必须专门设置个互斥信号量mutex来保证互斥访问缓冲区。
总结：
在生产者--消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。
3.吸烟者问题:
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复(让三个抽烟者轮流地抽烟)
1.找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
互斥关系：桌子可以抽象为容量为1的缓冲区，要互斥访问
组合一:纸和胶水，这是抽烟者1需要的
组合二:烟草和胶水，这是抽烟者2需要的
组合三：烟草和纸，这是抽烟者3需要的
桌子上只能放其中某一个组合（我们将组合看为一个整体）
同步问题：
桌上有组合一-->第一个抽烟者取走东西
桌上有组合二-->第二个抽烟者取走东西
桌上有组合三-->第三个抽烟者取走东西
发出完成信号-->供应者将下一个组合放到桌上
2.根据各进程的操作流程确定P、V操作的大致顺序
互斥关系：在临界区前P操作，后V操作
同步关系：前V后P
3.设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为
1，同步信号量的初始值要看对应资源的初始值是多少)
发出完成信号--->供应者将下一个组合放到桌上
代码实现如下：
这里设置i=0，供应者在提供完组合后，需要i=(i+1)%3操作，实现三个抽烟者轮流抽烟
供应者代码如下：
供应者将材料放到桌上后V（offer），需要等待吸烟者向他发出完成吸烟的信号P（finish）
注：若一个生产者要生产多种产品(或者说会引发多种前驱事件)，那么各个V操作应该放在各自对应的“事件”发生之后的位置。
吸烟者代码如下：
各个吸烟者从桌子上拿走相应组合之前，需要检查是否为自己需要的材料P（offer），当发现是自己需要的材料，并且卷烟抽掉后，需要向供应者提供完成信号，通知供应者可以放下一个组合的材料了。供给者就可以进行下一轮的供给
这里是否需要设置一个专门的互斥信号量？
与多生产者多消费者问题分析原理一样，缓冲区大小为1，同一时刻，四个同步信号量中至多有一个的值为1，所以可以不用设置一个专门的互斥信号量。
注：若题目改为每次随机让一个吸烟者吸烟，就可以加入random，随机将某一种组合放到桌子上。
3.读者、写者问题
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。
为什么允许多个读进程同时执行读操作？
这里和之前的消费者进程不同，消费者进程会取走数据，读者进程在读数据后并不会将数据清空，并不会改变数据。因此多个读者可同时访问共享数据
当某进程想要向共享文件写数据时，必须等待其他进程对此文件的操作结束后，才能写数据
1.写者进程会改变共享文件的内容，若读进程与写进程并发运行，写者进程在读者进程之前，写入了一些数据，覆盖了之前的内容，那么读者进程读到的将是错误的内容，而不是覆盖之前的内容，这就会导致出错。
2.若两写者进程并发运行，两写进程都往同一块内容写数据，那么后面的写进程写入的数据将覆盖前一个写进程写入的数据。
1.找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
两类进程:写进程、读进程
互斥关系:写进程---写进程、写进程----读进程。读进程与读进程不存在互斥问题。
写进程----读进程互斥访问的代码如下：
读者和写者在访问文件前后都进行“加锁”,“解锁”操作。
但这样会导致读者与读者之间不能同时访问共享文件：
这里可以加入count变量，在读进程加锁之前，检查是否是第一个读进程，若是，就进行加锁操作，若不是，则不进行加锁操作，并将count++，若读完文件，则count--，count--后，若
count==0，表示是最后一个读进程，那么进行解锁即可。
读进程代码如下：
但是这一方法存在一个不足，若两个读进程并发执行，在读进程时count==0，都会进行“加锁”操作。后一进行在进行P操作后，rw值为0，此时前一进程发现rw已经等于1，就会堵塞等待。
出现上述问题的原因在于对count 变量的检查和赋值无法一气呵成，因此可以设置另一个互斥信号量来保证各读进程对count 的访问是互斥的。
读者进程1执行P（mutex）操作，使得mutex从1变为0，此时读者进程2也想要执行P（mutex），但是发现mutex=0，所以就会被阻塞在此P操作，所以可以实现对count的互斥访问。
操作系统（8）---进程的同步与互斥以及信号量机制（万字总结~）（4）：https://developer.aliyun.com/article/1511060
