操作系统学习经典的进程同步互斥若干问题

问题模型&＃xff1a;
系统中有一组生产者进程和一组消费者进程&＃xff0c;生产者进程每次生产一个产品放入缓冲区&＃xff0c;消费者进程每次从缓冲区中取出一个产品并使用&＃xff08;产品&＃xff1a;某种数据&＃xff09;。

生产者、消费者共享一个初始为空、大小为 n 的缓冲区。

• 只有缓冲区没满时&＃xff0c;生产者才能把产品放进去&＃xff0c;否则必须等待&＃xff08;同步关系&＃xff09;。
• 只有缓冲区不空时&＃xff0c;消费者才能取出产品&＃xff0c;否则必须等待&＃xff08;同步关系&＃xff09;。
• 缓冲区必须是互斥访问的&＃xff0c;是临界资源&＃xff08;互斥关系&＃xff09;。

要注意各种 P 操作的先后顺序&＃xff08;因为P操作会让进程阻塞&＃xff09;&＃xff0c;否则容易出现“死锁”现象。

• 在这个问题模型中&＃xff0c;要注意的是同步要在互斥前边。

多生产者 - 多消费者

问题模型&＃xff1a;
生产者可以往桌子上放不同的材料&＃xff0c;三个吸烟者需要拿到自己对应的材料&＃xff0c;才可以完成吸烟动作。吸烟完成后&＃xff0c;通知生产者&＃xff0c;生产者才放下一个材料&＃xff0c;三个吸烟者轮流吸烟。

主要的同步、互斥关系&＃xff1a;

• 桌子是一个容量为 1 的缓冲区&＃xff0c;要互斥访问。&＃xff08;互斥关系&＃xff09;
• 桌子上有组合一&＃xff0c;第一个人才可以抽烟。&＃xff08;同步关系&＃xff09;
• 桌子上有组合二&＃xff0c;第二个人才可以抽烟。&＃xff08;同步关系&＃xff09;
• 桌子上有组合三&＃xff0c;第三个人才可以抽烟。&＃xff08;同步关系&＃xff09;
• 每个吸烟者吸烟结束&＃xff0c;供应者才可以将下一个组合放在桌子上。&＃xff08;同步关系&＃xff09;
  
  注意这里边&＃xff0c;互斥的关系&＃xff0c;并没有单独设置一个信号量&＃xff0c;因为4个负责同步的信号量&＃xff0c;同一时刻只会有一个有值。
  • 吸烟者问题为解决“可以生产多个产品的单生产者”问题提供了一个思路。

问题模型&＃xff1a;

• 多个读进程可以同时读&＃xff0c;不会出问题。
• 读写进程一起访问共享文件的话&＃xff0c;会导致读进程读的并不是自己想要的那份&＃xff08;被写进程改了&＃xff09;
• 多个写进程一起写入共享文件&＃xff0c;可能导致数据被覆盖。

综上&＃xff1a;

• 只可以多个读进程一起。
• 写进程执行的时候&＃xff0c;其他的写进程和读进程都不能访问。
• 读进程执行的时候&＃xff0c;写进程不能访问。

关系如下&＃xff1a;

• 写 - 写&＃xff08;互斥&＃xff09;
• 读 - 写&＃xff08;互斥&＃xff09;
  
  读写者模式的精巧之处&＃xff1a;

上边图里对读进程的设计中&＃xff0c;如果没有count变量记录读进程的数量的话&＃xff0c;会导致读进程与读进程之间也是互斥的&＃xff0c;这并不是我们希望的。如果像上图中的设计&＃xff0c;当多个读进程去读共享文件时&＃xff08;有先后顺序&＃xff09;&＃xff0c;只有访问共享文件的进程才会上锁&＃xff0c;其他的读进程都不会进行上锁操作&＃xff0c;因为通过count变量可以知道已经有读进程在读了&＃xff0c;此时去读的话&＃xff0c;并不会和写进程冲突&＃xff0c;可以放心的读。同理&＃xff0c;只有最后一个读完文件的读进程才会执行解锁操作&＃xff0c;因为比它先读完的那些进程不能执行解锁操作&＃xff0c;一旦解锁&＃xff0c;写进程就会开始写入&＃xff0c;就会造成读写冲突。

上边的这种设计存在一个问题&＃xff0c;如上图的左下角所示&＃xff0c;如果两个读进程并发的执行在读count变量时&＃xff0c;都为0&＃xff0c;会导致其中一个上锁&＃xff0c;另一个读进程被阻塞&＃xff0c;这是不可以的。所以再对count变量进行互斥访问&＃xff0c;加一个mutex。

可见&＃xff0c;上边这种方式是“读进程优先”的&＃xff0c;只要有读进程在读&＃xff0c;那写进程就会一直被阻塞&＃xff0c;可能“饿死”。
再加入一个信号量 w&＃xff0c;把写进程的优先级提一提。

引入 信号量w以后&＃xff0c;并发执行的情况。

• 读者1->读者2

  读者1读完以后&＃xff0c;会对mutex和w都执行V操作&＃xff0c;所以读者2可以正常读文件。

• 写者1->写者2

  多了一个互斥信号量&＃xff0c;所以也不会有影响。
  *写者1->读者1

  写者1执行后&＃xff0c;w和rw上锁&＃xff0c;此时如果有读者进程尝试访问&＃xff0c;w信号量会让该读进程阻塞。

• 读者1->写者1->读者2

  读者1在读的时候&＃xff0c;写者1尝试访问&＃xff0c;读者1会被w阻塞&＃xff0c;当读者1执行了 V(w) 以后&＃xff0c;写者1会对w上锁&＃xff0c;然后被rw阻塞&＃xff0c;如果此时&＃xff0c;读者2尝试访问&＃xff0c;因为写者1对w上了锁&＃xff0c;所以读者2会被w阻塞掉。等到读者1执行了V(rw)以后&＃xff08;此时count一定为1&＃xff0c;因为读者2被阻塞着&＃xff09;&＃xff0c;写者1可以对rw上锁&＃xff0c;开始正常的写入。等待写者1操作结束&＃xff0c;对rw和w解锁后&＃xff0c;读者2就可以正常的进行了。
  这就避免了之前&＃xff0c;写进程饥饿的问题。

• 写者1->读者1->写者2

写者1对w和rw上锁后&＃xff0c;开始写文件操作&＃xff0c;此时读者1尝试访问&＃xff0c;被w信号量阻塞&＃xff0c;此时再有写者2尝试访问&＃xff0c;也被w信号量阻塞&＃xff0c;当写者1完成任务&＃xff0c;释放rw和w后&＃xff0c;因为读者1先于写者2上锁排队&＃xff0c;所以w信号量被解锁后&＃xff0c;读者1开始执行&＃xff0c;写者2依然开始被阻塞着。

这种方法相对读者和写者都相对公平。牛逼&＃xff01;

总结&＃xff1a;

• count服务于读进程&＃xff0c;保证读进程不互斥&＃xff0c;mutex用于保证对count的互斥访问。
• w用于解决写进程饥饿。

问题模型&＃xff1a;

• 下面这种方案是不合理的&＃xff0c;会存在死锁现象&＃xff0c;所有的哲学家都等待自己右手边的筷子&＃xff0c;又没有人放下自己手中的筷子。
  两个解决死锁问题的思路&＃xff1a;

1. 限制最多只允许4个哲学家进餐。
2. 要求奇数号的哲学家先拿左手边筷子&＃xff0c;偶数号哲学家先拿右手边筷子。
3. 要求有人拿筷子的时候&＃xff0c;其他人不能拿。&＃xff08;有书上说的是&＃xff0c;当左右筷子都可用时才允许拿起来&＃xff09;

第三种方法&＃xff1a;

情况说明&＃xff1a;

• 0号想吃饭&＃xff0c;拿起左边筷子时&＃xff0c;此时进程切换&＃xff0c;2号想吃饭了&＃xff0c;2号被mutex阻塞&＃xff0c;只能等到0号吃完&＃xff0c;2号采可以拿筷子、吃饭。
• 0号拿起左右筷子&＃xff0c;对mutex解锁后&＃xff0c;0号开始吃饭&＃xff0c;1号此时只能拿起左筷子&＃xff0c;拿右筷子时被阻塞&＃xff0c;如果此时2号也想吃饭&＃xff0c;但它一根筷子也拿不了&＃xff08;即使左右都有筷子可用&＃xff09;&＃xff0c;因为被mutex阻塞了。只能等1号吃完&＃xff0c;它再吃。
• 0号拿起左右筷子&＃xff0c;对mutex解锁后&＃xff0c;0号开始吃饭&＃xff0c;4号想吃饭&＃xff0c;只能拿起左侧的筷子&＃xff0c;拿右筷子时被阻塞
  哲学家进餐问题的关键在于解决进程死锁
  哲学家进餐问题的关键在于解决进程死锁
  哲学家进餐问题的关键在于解决进程死锁