进程间通信介绍(二)-信号量

上一篇总结了IPC(Inter-Process Communication)的一些基本概念，本次将继续总结以下内容：死锁，信号量与PV原语以及用PV原语解决若干实例问题。

1.死锁

（1）死锁，是指多个进程之间互相等待对方的资源，而在得到对方资源之前又不释放自己的资源，这样，造成循环等待的一种现象。如果所有进程都在等待一个不可能发生的事，则进程就死锁了。

（2）死锁产生的必要条件：

1）互斥条件：
进程对资源进行排他性使用，即在一段时间内某资源仅为一个进程所占用。

2）请求和保持条件：
的那个进程因请求资源而阻塞时，对已获得的资源保持不放。

3）不可剥夺条件：
进程已获得的资源在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

4）环路等待条件：
各个进程组成封闭的环形链，每个进程都等待下一个进程所占用的资源。

（3）防止死锁的办法

1）资源一次性分配：破坏请求和保持条件
2）可剥夺资源：破坏不可剥夺条件
3）资源有序分配法：破坏循环等待条件

（4）死锁避免

防止死锁的几种策略，会严重地损害系统性能。因此在避免死锁时，要施加较弱的限制，从而获得较满意的系统性能。

由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统能在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。

其中最具有代表性的避免死锁算法是银行家算法。

银行家算法：为了保证资金的安全，银行家规定：

• 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；
• 顾客可分期贷款，但贷款的总数不能超过最大需求量；
• 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；
• 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金。

（5）哲学家就餐问题

• 五个哲学家围在一个圆桌就餐，每个人都必须拿起两只筷子才能用餐
• 哲学家就餐问题解法：
  • 服务生解法：
    哲学家拿筷子之前，先征询服务生。即服务生是一个管理者，统一分配筷子，他判断当前资源是否处于安全状态。若处于安全状态，则服务生允许哲学家拿起筷子。
  • 最多4个哲学家
  • 仅当一个哲学家两边筷子都可用时才允许他拿筷子
  • 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之。

2.信号量与PV原语

信号量和P、V原语有Dijkstra(迪杰斯特拉)提出

（1）信号量

1）信号量值含义

• S>0：S表示可用资源的个数
• S=0：表示无可用资源，无等待进程
• S<0：|S|表示等待队列中进程个数

其中，value保存计数值，queue等待队列

• 互斥：P、V在同一个进程中，一般是用来解决互斥问题的。
• 同步：P、V在不同进程中，一般是用来解决同步问题的。

（2）P原语

当一个进程要申请资源的时候，就需要执行P操作：

1）首先，将信号量的计数值减1；
2）如果减1后的计数值<0，就说明先前的s.value值<=0，即，先前已经没有资源可用了。此时，进程进入等待状态，并将进程的PCB(进程控制块)指针插入等待队列末尾。
3）如果在减1前s.value>0，说明有资源可用，则只需将计数值减1即可，if语句不执行。
4）这是一个原子性操作，不能被中断。

（3）V原语

当一个进程使用完资源后，归还资源，执行V操作：

1）首先，将计数值加1；
2）如果加1后仍<=0，说明加1前s.value<0，即等待队列中有进程处于等待状态。这个时候有进程归还资源，就可以唤醒其中一个资源了；
3）如果加1前s.value>=0，说明等待队列中没有等待进程，P操作仅仅是将计数值加1。if语句不执行。
4）同样是原子性操作，不能被中断。

3.用PV原语解决司机与售票员问题

该问题是同步问题：对同一个信号量，P、V在不同进程中

1）首先，司机对S1执行P操作请求资源(启动车辆)，但是要在售票员关门后才可以启动；
2）所以，售票员关门后，要给司机进程一个信号，对S1信号量执行V操作(释放资源)，使得S1.value加1—>司机进程获得资源—>启动车辆并正常运行；
3）然后，售票员进程售票，售完票到站后—>售票员对S2执行P操作请求开门，但是要在司机停车之后才可以开门；
4）司机到站停车，给售票员一个信号，对S2信号量执行V操作(释放资源)，使得S2.value加1—>售票员获得资源—>开门。

4.用PV原语解决民航售票问题

该问题是互斥问题：对同一个信号量，P、V操作在同一个进程中

1）票数x=1的情况下，有许多进程在进程售票动作，售票之前要对S执行P操作，进入临界区–>使得S.value=0，那么当再有其他售票动作执行P操作，将进入等待队列；
2）那么只有当第一个售票的人，对信号量S执行V操作—>释放资源(这里可以假定是将票退了)，其他的售票动作才会从等待队列进入就绪队列。
3）上述代码即为临界区，x为临界资源。

5.用PV原语解决汽车租赁问题

有一汽车租赁公司有两部敞篷车可以出租，假定同时来了四个顾客都要租敞篷车，那么肯定会有两个人租不到车。

当S.value=1时，将进入临界区