详细解锁【并发与死锁】
并发与死锁
死锁的定义:死锁是指多个进程在运行过程中由于争夺资源而造成的一种僵局,若无外力作用,它们都将无法推进下去。此时系统处于一种死锁状态,这些互相等待的进程称之为死锁进程。
联合进程图/敏感区域/可重用资源(一次仅供一个进程安全使用且不因使用而耗尽的)/可消耗资源(可被创建和销毁的资源)
死锁产生的原因 :
- 竞争资源。比如:进程P1持有资源R1,它需要资源R2才能完成运行从而释放资源R1;进程P2持有资源R2,它需要资源R1才能完成运行从而释放资源R2;此时,系统就进入了一种僵局,死锁发生。
- 进程间推进顺序非法。
**系统资源分配图:**由进程集合P、资源集合R和边集合E组成。
P_i -> R_j:表示申请边。进程P_i申请了资源R_j。申请边由进程(圆圈表示)指向资源(矩形框表示)。
R_j -> P_i:表示分配边。资源R_j分配给了进程P_i。分配边由资源(矩形框内的一个点,其表示一个资源)指向进程(圆圈表示)。
如果系统资源分配图中没有环,则一定不存在死锁。如果系统资源分配图中有环,则可能存在死锁。(具体要看每个类型的资源有多少个,若每个类型的资源只有一个则一定存在死锁)
无死锁:P3执行完释放R3;P2得到R3执行完释放R1;P1得到R1执行完释放资源,R2不用看是因为不止一个资源,并不构成冲突
有死锁:P3需要得到R2才会执行从而释放R3;P2需要得到R3才会执行从而释放R2,R1;P1需要得到R1才会执行。P3,P2,P1就这样相互僵持谁也不能执行。
无死锁:P4会执行完释放R2,P3得到R2会执行完释放R1,P1得到R1会执行完释放资源。P2直接执行完释放资源。
死锁的四个必要条件:
- 互斥:至少有一个资源一次只能供一个进程使用,其他进程想使用必须等到其被释放为止。
- 占有并等待:一个进程占有至少一个资源并等待另一个资源,而另一个资源又被其他等待进程所占有。
- 不可抢占:进程持有的资源只能被进程自己释放。
- 循环等待:有一组等待进程 {P0,P1,…,Pn},P0 等待的资源为 P1 占有,P1 等待的资源为 P2 占有,……,Pn-1 等待的资源为 Pn 占有,Pn 等待的资源为 P0 占有,形成一个等待环。
- 注意:所有四个条件必须同时成立才会出现死锁。循环等待条件意味着占有并等待条件,这四个条件并不完全独立。前三个条件其实为第四个条件创造了条件,是必要非充分条件。
- 第四个条件可以通过定义资源类型的线性顺序来预防。相当于对资源进行优先级排序,若一个进程已经分配了R资源,则接下来只能分配排在R之后的资源。正确但低效率。
死锁预防是破除上面四个条件任意之一,死锁避免是允许条件产生,但明智地选择使不会达到死锁点。
进程启动拒绝(通过矩阵)
资源分配拒绝:银行家算法
死锁检测
- 死锁检测算法
- 恢复
- 死锁检测算法
哲学家就餐问题
/* program diningphilosophers */ semaphore fork [5] = {1}; int i; void philosopher (int i) { while (true) { think(); wait (fork[i]); wait (fork [(i+1) mod 5]); eat(); signal(fork [(i+1) mod 5]); signal(fork[i]); } } void main() { parbegin (philosopher (0), philosopher (1), philosopher (2), philosopher (3),philosopher (4)); } /* program diningphilosophers */ semaphore fork[5] = {1}; semaphore room = {4};//本意是只有四个人可以进入,个人认为真的多余 int i; void philosopher (int i) { while (true) { think(); wait (room); wait (fork[i]); wait (fork [(i+1) mod 5]); eat(); signal (fork [(i+1) mod 5]); signal (fork[i]); signal (room); } } void main() { parbegin (philosopher (0), philosopher (1), philosopher (2), philosopher (3),philosopher (4)); }
UNIX并发机制/进程之间的通信机制
- 管道(pipe):环形缓冲区,创建时获得一个固定大小的字节数。允许进程以生产这消费者进行通信。是一种半双工的通信方式,数据只能单向流动,而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。信号量传递有限。
- 命名管道FIFO(named pipe): 半双工通信方式,还允许无亲缘关系进程间的通信。信号量传递有限。
- 消息队列MessageQueue:消息队列是由消息的链表,存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。 具有写权限的进程可以按照一定规则向消息队列中添加新信息;对消息队列有读权限的进程则可以从消息队列中读取信息。
- 共享存储SharedMemory:共享内存就是映射一段能被其他进程所访问的内存,**这段共享内存由一个进程创建,但多个进程都可以访问。不同进程可以及时看到对方进程中对共享内存中数据的更新。共享内存是最快(最有用)**的 IPC 方式,它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制,如信号量,配合使用来实现进程间的同步和通信。(需要考虑互斥)
- 信号量Semaphore:信号量是一个计数器,可以用来控制多个进程对共享资源的访问。它常作为一种锁机制,防止某进程正在访问共享资源时,其他进程也访问该资源。主要作为进程间以及同一进程内不同线程之间的同步手段。
- 套接字Socket:是一种更为一般的进程间通信机制,可用于网络中不同机器之间的进程间通信,应用广泛
- 信号 ( sinal ) : 信号是在软件层次上对中断机制的一种模拟,它是一种比较复杂的通信方式,用于通知接收进程某个事件已经发生,一个进程收到一个信号与处理器收到一个中断请求效果上可以说是一致的。
Linux内核并发机制:除了以上还包括实时信号(支持按优先级/信号能排队/将数值和信号一起发送)
- 原子操作
- 自旋锁:试图获得自旋锁的线程将一直进行尝试(自旋),直到获得该锁。
- 信号量
- 屏障
Solaris线程同步原语
Windows并发机制
Android进程间通信
文章来自于网络,如果侵犯了您的权益,请联系站长删除!