感觉这一块还是有点东西的讲讲我自己的理解互斥关系和同步关系的区别。互斥关系好像也涉及到了顺序问题比如一个进程占领了共享区另外一个进程就必须等待他使用结束比如消费者必须等待占领共享区的其他进程完成才能占领共享区进行消费貌似有一个先后顺序。但是与同步关系最大的不同是这种关系没有指向性。生产消费模型中消费者的消费行为会唤醒生产者而非消费者这是同步关系。消费者释放共享区可以唤醒消费者也可以唤醒生产者。当然这种差异在信号量初始值变成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放映权s2s3依次类推。电影放映前放映人vs1即提供影片1的放映权当没人看影片1以后ps1收回影片1的放映权而后vs2即提供影片2的放映权。同时需要finish来知道某一批人已经完成观影。nN n % 3Case NSwitch 0:Vs1P(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. C1C2C3.感觉越是简单越是凶险啊。第二问就是只执行一次的情况下是只有同步的关系。不需要涉及到互斥访问第三问就是首先已知不为空就不需要p(full)之类的操作其次修改也不会涉及到v(empty)所以需要互斥访问就可以。这里也没有更详细的内容去说明是否要记录修改哪一组之类的。29.种树问题感觉很贴近生活啊不容易。这里题目有一点不清晰植树步骤不是说甲乙丙必须依次按照这个步骤执行植树步骤是说一个空地必须按照挖坑种树填坑浇水的步骤来植树。甲可以专注于挖坑而不用管乙和丙。乙只需专心放树和浇水。甲和乙之间类似生产消费的关系甲生产一个树坑乙消费一个树坑。生产的配额一开始规定是3。同时甲和乙还需要互斥的使用铁锹由于铁锹只有一把相当于甲和乙对于临界区的访问必然是互斥的。乙和丙之间只有同步的关系。所以只需要一对pv就能够实现。另外这里乙拿铁锹和乙种树相对独立但是这个行为必须要放种树后面否则就会死锁。