操作系统（8）---进程的同步与互斥以及信号量机制（万字总结~）（3）：https://developer.aliyun.com/article/1511049
读者、写者问题中有一个潜在的问题：
只要有读进程还在读，进程就要一直阻塞等待，可能"饿死"。因此，这种算法中，读进程是优先的
例如，第一个进程到来后，执行P（rw）操作，使得rw由1变为0，那么写进程的P（rw）操作就会堵塞等待，若此时源源不断有读进程执行读操作，那么写进程就会一直等待。
我们可以再设置一个信号量，用于直线"写优先"
1.若两个读者之间并发运行：
读者1与读者2是并发运行的，即宏观上同时读，但是微观上读者1先执行读操作，再读者2进行读操作，若读者1执行到P(rw)操作后，切换到读者2进程，那么读者2进程会被堵塞再P(w)
直到读者1执行完V(w),读者2才能继续执行，由于这里会跳过if语句，所以读进程是能并发运行的。
2.两个写者进程并发运行：
第一个写进程没有执行完之前，第二个写进程会被堵塞再P（w），直到第一个写进程执行完V（w）之后，第二个写进程才能继续执行，两个写进程是能实现互斥访问的。
3.一个写者和一个读者并发运行：
（1）写者-->读者
写进程在写文件时，w的信号量已经由1变为0，此时读者进程会被堵塞在P（w），直到写进程执行完V（w），读者进程才有可能访问共享文件。实现了"写优先"。
（2）读者1--->写者1--->读者2
1.读者进程在读完文件后w值为1，写者进程能执行P（w），w的值由1变为0，但是写者进程会被堵塞在P（rw）
2.若此时还有读者想要读共享文件，由于w的值为0，所以会被堵塞在P(w)中
3.那么写者1和读者2都会堵塞，当读者读完文件后，count--，因为只有1个读者读文件，所以count--后，count值为0，那么就会执行V（rw）
4.这样就可以唤醒堵塞在P（rw）的写者进程了，实现了"写优先"
（3）写者1-->读者1-->写者2
1.当写者写文件时，执行P（w）和P（rw），那么w=0，rw=0
2.读者在读文件时，就会堵塞在P（w）
3.若写者2也想写进程的话，那么第二个写者进程也会被阻塞在P(w)中。
4.由于读者先对w进行了P操作，所以读者1在等待队列的对头位置，而写者进程2排在后面，所以当写者1执行完V操作后，唤醒的是读者进程。
结论:
在这种算法中，连续进入的多个读者可以同时读文件；写者和其他进程不能同时访问文件；写者不会饥饿，但也并不是真正的“写优先”，而是相对公平的先来先服务原则。有的书上把这种算法称为"读写公平法"。
4.哲学家进餐问题
一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
1.关系分析。系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系
2.整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的关键。
3.信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1}，用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5。
这里设置每个哲学家吃饭前依次拿起左、右两支筷子。
若此时5个哲学家并发地拿起了自己左手边的筷子，每位哲学家循环等待右边的人放下筷子(阻塞)
发生“死锁。
如何避免死锁：
①可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的（剩余的筷子分配给相邻的哲学家即可）。
②要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。
③仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。
（1）若1号哲学家执行P（mutex）操作，使mutex由1变为0，继续执行P（chopstick[i]），此时
若切换为2号哲学家，此时2号哲学家会被堵塞在P（mutex）中，只有等待1号哲学家执行完P（chopstick[（i+1）%5]）后，拿起右边筷子后，才能释放mutex。
（2）若0号哲学家执行完以下操作，就会释放mutex
此时1号哲学家可以通过P（mutex），但是因为0号拿了两支筷子，所以1号哲学家会被堵塞在P(chopstick[i])
而2号哲学家由于1号哲学家已经执行了P（mutex），所以mutex由1变为0，所以2号哲学家又会被阻塞在P（mutex），所以即使2号哲学家左右两边筷子都可以用，但是依然会被堵塞。
因此这种方法并不能保证只有两边的筷子都可用时，才允许哲学家拿起筷子。
（3）0号哲学家拿起左右两边的筷子开始吃饭，此时4号哲学家可以拿起左边的筷子，但是不能拿右边的筷子，即会被阻塞在P(chopstick[(i+1)%5])
因此此时4号右边的筷子不可用，但4号仍然会先拿起左边的筷子
总结：
各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。
哲学家进餐问题的关键在于解决进程死锁。
这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。若遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。
四.管程
1.为什么要引入管程
由于信号量机制存在编写程序困难、易出错的问题，例如：
像这样如果写错了P操作的顺序，按 ①②③执行，就会发生死锁
所以设置了管程，使程序员写程序时不需要关注复杂的PV操作
2.管程的定义和基本特征
管程是一种特殊的软件模块，有这些部分组成：
1.局部于管程的共享数据结构说明;
2.对该数据结构进行操作的一组过程（函数）；
3.对局部于管程的共享数据设置初始值的语句；
4.管程需要有一个名字。
为了用管程实现进程间的互斥和同步，管程需要以下特征：
1.局部于管程的数据只能被局部于管程的过程所访问；
2.一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
3.每次仅允许一个进程在管程内执行某个内部过程。
3.管程的例子
1.用管程解决生产者消费者问题
①生产者只用将函数的参数传入ProducerConsumer.insert();其他互斥同步等问题都由管程解决。
②消费者也可以直接调用函数，从缓存中取出产品，中间的过程只由管程负责。
由编译器负责实现各进程互斥进入管程的过程，生产者进程、消费者进程只需要调用管程中的函数就可以了
1.实现进程互斥
若第一个进程正在调用insert函数，若第二个进程也想调用，编译器就会阻止第二个进程使用该函数。只有第一个进程使用完毕，第二个进程才能使用。
2.实现进程同步
管程中会设置条件变量和等待/唤醒操作，用来解决同步问题，例如：
消费者1想要从缓冲区取产品，但是初始count==0，所以第一个消费者进程会等待在empty这一条件变量的队列中，消费者2进程同理
生产者生产产品后，会将产品放入缓冲区中，并且检查count是否为1，即自己放入的产品是不是缓冲区中的第一个产品，这就意味着可能由消费者进程在等待产品，所以此时会用signal(empty),唤醒在empty条件变量中等待产品的进程，在这里会先唤醒对头进程，也就是消费者1。
若执行消费者进程后，count--，此时count==N-1，那么就说明原本缓冲区是满的，现在消费者取走一个进程，那么生产者就可以继续生产了，就会使用signal(full),唤醒生产者进程。
总结：
引入管程的目的无非就是要更方便地实现进程互斥和同步。
1.需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
2.需要在管程中定义用于访问这些共享数据的“入口”----其实就是一些函数(如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品)
3.只有通过这些特定的“入口”才能访问共享数据
4.管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入(如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。
注意：这种互斥特性是由编译器负责实现的，程序员不用关心
5.可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待(此时，该进程应先释放管程的使用权，也就是让出“入口”)；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
程序员可以用某种特殊的语法定义一个管程(比如:monitor ProducerConsumer…end monitor)之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步/互斥了。即程序设计中封装的思想（将复杂的细节隐藏，对外提供简单易用的接口）。
java中类似管程的机制：
Java 中，如果用关键字 synchronized 来描述一个函数，那么这个函数同一时间段内只能被一个线程调用。
每次只能有一个线程进入insert 函数，如果多个线程同时调用 insert 函数，则后来者需要排队等待。
