感觉这一块还是有点东西的，讲讲我自己的理解

互斥关系和同步关系的区别。

互斥关系好像也涉及到了顺序问题，比如一个进程占领了共享区，另外一个进程就必须等待他使用结束，比如消费者必须等待占领共享区的其他进程完成才能占领共享区进行消费，貌似有一个先后顺序。但是与同步关系最大的不同是，这种关系没有指向性。生产消费模型中，消费者的消费行为会唤醒生产者而非消费者，这是同步关系。消费者释放共享区可以唤醒消费者也可以唤醒生产者。

当然这种差异，在信号量初始值变成1时就不再明显。比如水果问题，当共享区只有一个，生产者和消费者中的任意一方对共享区的占领，必然排斥其他的生产，消费者，并且必然唤醒的是生产消费中的另一方。

当临界区初始大小n不等于1的时候，还会产生另一种很有可能的情景，就是某一个进程在确定可以进行活动以后，在占领临界区之前，被另外一个进程抢先占领临界区并进行活动。这种行为不会对当前进程造成不可活动的后果，更不会导致死锁的发生。

临界区互斥并不是绝对的

假如现在有一个箱子，有两拨人，一拨人往箱子里放东西，一拨人从箱子里拿东西，放东西的人，pempty以后就会放，拿东西的人pfull以后就会拿，每个人只会拿自己看中的那个东西，或者在自己看中的地方放东西，理论上讲，是不需要互斥使用的。但是计算机中，内存是没办法保证2个同时pempty的进程能够和对方规避，避免写在同一个地址，生产者，消费者也无法避免在同一内存地址上读写，这就会造成混乱。所以涉及内存资源区时，一定要上锁。

一个信号量能够引导一个同步关系，2个信号量分别放在两个进程的首位，如果都是p开头，两个进程就能够循环进行，比如经典的生产消费模型。如果其中一个是先p后v，另一个是先v后p，那就是顾客和服务者的关系，比如理发师问题，卷烟问题，银行叫号问题。一方提供某种资源，唤醒对方，然后等待对方使用这种资源。另一方等待对方的唤醒，唤醒以后使用这种资源，然后给出反馈。

02.AB产品问题

答：

A与B的产品，显然是生产消费模型，且题目指明存在互斥区。A与B有无同步？虽然没有明显的消费者，但是他们的信号量的数值是相关的，两个生产者，都会因为对方的生产而获得更多的生产机会，相当于互为生产消费者。从这里我们也可以看出涉及empty和full的量都会有同步的关系，无论是显性的：比如生产者和消费者之间，还是隐性的：比如此题目。

03.买面包问题

答：

这里两个梯队之间并没有非常明确的同步关系，比如某一方的行为会唤醒对方。这里更多的是两个进程内的互斥问题。有点类似两群读者。一个梯队在不停的叫号，一个梯队在不停的取号。如果叫号的行为不互斥，两个人同时叫号，就会叫到一个号。如果取号的行为不互斥，两个人就会取到同一个号，相当于服务了同一个人。当然这种模型不太贴近现实，所以在理发师问题中，两个梯队加上了同步措施。

05.缸中取水

答：

所用模型：这里是生产消费模型，可以认为小和尚是生产者，老和尚是消费者。小和尚将水放到水缸，老和尚消费水。不过比经典的生产消费，这里生产者的生产需要互斥竞争，并且增加了水桶这样一个全局的互斥量。

互斥关系：注意，如果生产消费之间有两个互斥量x，需要先争用同一个互斥量，否则会出现循环等待。例如，如果小和尚先拿了所有的水桶，老和尚先占用了水缸，这时候双方都会等待对方手里的资源，就会死锁，类似选择题22题的情景。

06.依次计算

答：

所用模型：主要是同步的关系，这是一个很长的流程，需要不同进程通过信号量实现同步的配合操作。

07.过桥问题

答：

所用模型：将读者写者模型中，去掉写者，用了两队不同的读者。

评价：计数的操作一定是互斥的，如同叫号取号的操作一样，如果不互斥，那么可能会有很多进程认为自己拿到的号是1，都会索要桥的通行权。互斥的操作，就是通过信号量夹紧。

08.线程互斥

类似双标志法，无论先检查对方标志，还是先设置自己的标志，这种方法都是没办法实现空闲让进，忙则等待的原则的。更别提让权等待了。

09.自行车组装

有点类似水果问题，有多个生产者，不过共享区大小大于1，而且消费者需要拿到两个生产者的产品才能消费。我们可以假设共享区被划分界限，供两个生产者使用，双方互不侵犯界限，这样才不会死锁。一旦一方完全占领共享区，相当于另一方的生产者和消费者互相等待，则会发生死锁。所以我们可以规定，车架最多N-2个，车轮最多N-1个，给对方的生产消费互动留下空间。相比较于经典的生产消费模型，我们可以说对每一对生产者消费者都设置了自己的信号量对。我感觉答案里的empty信号量设置也有点多余。

另外一个很明显的特点是，这里生产消费是不互斥的，可能一个人在放车架，一个人在放车轮，同时一个人在取车架或车轮进行组装。

10.PQR

感觉答案中的mutex有点多余。

11.理发师问题

感觉是一个非常混合版的读者写者模型，我感觉都可以新增一个模型了，可以称之为做叫号服务模型。首先双方存在明显的同步关系。顾客增加会唤醒服务方，而后顾客等待服务。服务方被唤醒以后为顾客提供服务。会有两个信号量对该过程进行同步，如下图所示。另外顾客数量的变化是需要互斥的。同时顾客叫号，服务方取号服务的过程会导致顾客数量的变化，所以这个行为需要和数量的变化用信号量夹紧。如果不夹紧，就可能会发生：服务方已经使顾客数量减一，但是在vbarber之前，有顾客进程加入，并使得n++，导致实际顾客滞留，实际顾客数量大于最大值。

同步关系：在问题中，顾客有n个，每一个顾客和理发师都是上面的流程。我们需要一个count来反映正在等待的顾客的数量。如果这个数量超过n，那么顾客就不应该vcustomer。如何让这个数量真正的反映在等待的顾客的数量呢。我们需要把这个数量和vcustomer以及vbarber夹一下。如果有了一个vcustomer，那么说明，等待的顾客+1。如果有了一个vbarber，那么就说明等待的顾客-1。也就是说这个count能够通过和vcustomer以及vbarber夹紧，能够正确的反映等待的顾客的数量。如果不夹紧，可能理发师使得count减少，但是并没有真正的提供服务，那么实际等待的顾客数量就会大于count。

12.观看录像

类似前文中的过桥问题。不过我感觉这个题是有潜力的，只是没出这么深罢了，比如我们可以规定，放映的顺序是固定的，那么影片1的全部散场后，影片3的观众是不能够观影的，除非影片2的观众数量为0。套用到读者写者问题，相当于有三个读者队列需要按顺序阅读。对于这个问题，我们可以增加一个电影放映人的进程。固定s1为影片1放映权，s2，s3依次类推。电影放映前，放映人vs1，即提供影片1的放映权，当没人看影片1以后ps1，收回影片1的放映权，而后vs2，即提供影片2的放映权。同时需要finish来知道某一批人已经完成观影。

n++

N = n % 3

Case N

Switch 0:

Vs1

P(m1)

If n1 == 0:

P(s1)

V(finish)

V(m1)

else:

v(m1)

p(finish)

switch 1：

类似上文

Switch 2：

类似上文

16.卷烟问题

水果问题的升级版，因为只有一个桌子，相当于，共享区只有一个，所以不需要mutex进行夹紧，但是从编程的角度，最好还是应该加上mutex。同时这里用了一个顾客服务的模型。同时规定了顺序。

17.放数取数

类似水果问题，但是有N个缓冲区，需要mutex夹紧缓冲区。

18.取号叫号

和理发师问题没有本质的区别。只是控制顾客数量的手段从使用n变成了信号量empty。在server的进程中，我们同样需要注意，要把对数量控制的信号量vemtpy放到提供服务的vserver前面。整体如下所示。

20.连续消费

连续消费10次，这里相当于消费者的10次消费行为有一定的原子性，不能够被打断，可以用互斥量夹紧，保证该过程不会被其他的消费者打断，但是可以被其他的生产者打断。

21.信箱通信

挺妙的。首先从自己信箱拿信件的行为就是消费者的行为。然后往对方信箱塞信的行为就是生产者的行为。当A作为消费者的时候，信箱A就是其要获得资源的临界区，这时候不能允许B在信箱中放信。

会不会死锁呢？ 假如A先一步进入临界区，B且B信箱是满的，那么A取信以后，确实是需要等待B，但是此时B无需等待A的任何操作，也就是不满足请求保持的条件，所以不会死锁。B会先从B中取信，这是A就可以送信。或者B将全部信件送完，这时候A一定是有信件可以取出然后送给B，也不会死锁。同理任意一个情景都不会死锁。

23.哲学家进餐

没什么好说的，要么破坏请求保持，让每个哲学家一次拿到两个筷子。要么破坏循环等待，让用餐最大人数小于等于总人数-1.

25.互斥实现

如果通过关中断实现互斥，其原理是让其他的进程无法占用cpu。如果是多核计算机，那么其他的进程一样可以访问该变量。

28. C1，C2，C3.

感觉越是简单越是凶险啊。第二问就是，只执行一次的情况下，是只有同步的关系。不需要涉及到互斥访问

第三问就是，首先已知不为空，就不需要p(full)之类的操作，其次修改，也不会涉及到v(empty)，所以需要互斥访问就可以。这里也没有更详细的内容去说明是否要记录修改哪一组之类的。

29.种树问题

感觉很贴近生活啊，不容易。这里题目有一点不清晰，植树步骤不是说甲乙丙必须依次按照这个步骤执行，植树步骤是说一个空地必须按照挖坑种树填坑浇水的步骤来植树。甲可以专注于挖坑而不用管乙和丙。乙只需专心放树和浇水。甲和乙之间类似生产消费的关系，甲生产一个树坑，乙消费一个树坑。生产的配额一开始规定是3。同时甲和乙还需要互斥的使用铁锹，由于铁锹只有一把，相当于甲和乙对于临界区的访问必然是互斥的。乙和丙之间只有同步的关系。所以只需要一对p，v就能够实现。

另外这里乙拿铁锹和乙种树相对独立，但是这个行为必须要放种树后面，否则就会死锁。