大纲:
死锁概念及死锁处理方法
银行家算法
死锁检测
进程通信方法:信号、管道、消息队列、共享内存
一、死锁
背景
-
可重用资源:资源不能被删除且任何时刻只能有一个进程使用,进程释放资源后其他进程可重用,可能出现死锁
-
消耗资源:资源创建和销毁,当进程间相互等待接收对方消息时也可能出现死锁
=======》资源分配图:描述资源和进程间分配和占用关系的有向图
-
出现死锁的必要条件:
1)互斥:在一个事件只能由一个进程使用资源
2)持有并等待资源:
3)非抢占:资源只能在进程使用后自愿放弃
4)循环等待:
死锁处理方法
-
死锁预防:确保系统永远不会出现进入死锁状态,将前述的四个必要条件中任意一个条件避免掉,但是这样往往影响很大效率很低
-
死锁避免:在使用前进行判断,只允许不会出现死锁的进程请求资源(有效的)
-
死锁检测和恢复:在检测到运行系统进入死锁状态后,进行恢复:
由应用进程处理死锁,通常OS就忽略死锁的存在
死锁预防:使系统在任何时刻都不满足死锁的必要条件
1)互斥:把互斥的共享资源封装成可同时访问
2)持有并等待:进程请求资源时,要求它不持有任何其他资源(在进程开始时,就一次把所有资源都申请到),但资源利用率太低了
3)非抢占:如进程请求不能立即分配的资源,则释放已占有的资源
4)循环等待:对资源排序,要求进程按顺序请求资源(效率下降
死锁避免:利用额外的先验信息
在分配资源时判断是否会出现死锁,只在不会死锁时分配资源“
1)要求进程声明需要资源的最大数目
2)限定提供于分配的资源数目,确保满足进程的最大需求
3)动态检查资源分配状态,确保不会出现环形等待
银行家算法:一种死锁避免的方法
银行家算法以一银行借贷分配策略为基础,判断并保证系统处于安全状态:
1)客户在第一次申请贷款时,声明所需最大资金量,在满足所有贷款要求并完成项目时及时归还
2)在客户贷款数额不超过银行拥有的最大值时,银行家尽量满足客户需要
===> 银行家:os;资金:资源; 客户:申请资源的线程
- 数据结构:总需求量,剩余空闲量,已分配量,未来需要量
判断安全状态……(接下来需要的比现在剩余的小,就安全
死锁检测:允许系统进入死锁状态
维护系统的资源分配图,定期调用死锁检测算法来搜索图中是否存在死锁
检测方法:
- 方法1: 将资源分配图转成等待图:将资源分配图中的资源都去掉只剩下进程,就变成等待图了,如果等待图中由环,则死锁发生
- 方法2:用Available, allocation ,request三个变量构成一个死锁检测算法(数据结构, 开销很大
死锁恢复:
- 终止所有死锁i进程
- 依据某些原则一次只终止一个进程直到死锁消除:
进程优先级,进程已运行时间及还需运行时间,进程已占用资源,进程完成需要的资源,终止进程数目,进程时交互还是批处理
但是又可能某些个进程会一直被选做受害者,一直得不到执行,由此产生饥饿
二、进程通信
进程通信IPC(inter-process communication):是进程进行通信和同步的机制
- IPC提供两个基本操作:发送操作send(message) 和接受操作receive(message)
- 进程通信流程:在通信进程间建立通信链路,再通过send/receive交换消息
- 进程链路特征:物理链路(如,共享内存,硬件总线),逻辑链路(如,逻辑属性)
- 通信方式有两种:间接通信和直接通信
-
间接通信:依赖OS kernel,进程将信息发送到内核的消息队列上,另一个进程从kernel消息队列中读出来,从而完成依赖于操作系统内核的一个间接通信。此时交互的两个进程的生命周期不必相同
1)每个消息队列都有一个唯一的标识,(在内核中可能维护了多个消息队列,必须得直到要通信的对方是谁
2)只有共享了相同消息队列的进程,才能够通信
3)通信链路可以是单项的,也可以是双向的,
4)消息队列可以与多个进程相关联
-
直接通信:在两个进程之间建立一个共享信道,一个进程从共享信道发数据,另一个进程从共享信道读数据。这两个进程生命周期得相同
1)直接通信的进程必须正确命名对方,send(P,message), receive(Q,message)
2)通信链路必须满足:1自动建立链路 2一条链路恰好对应一对通信进程 3每对进程之间只有一个链接存在
3)链接可以是单向的,可以是双向的
进程通信又分为阻塞通信和非阻塞通信:阻塞通信也称为同步通信,非阻塞通信为异步通信
通信链路缓冲
进程发送的消息在链路上可能有三种缓冲方式:
- 0容量:发送方必须等待接收方(就是没缓存嘛
- 有限容量:通信链路缓冲队列满时,发送方才必须等待
- 无限容量:发送方任何时候都可以发,发送的数据在链路上缓存,接收方任何时候都可以接受。(当然这不太可能
进程通信机制的具体实现——信号和管道,消息队列和共享内存
信号signal:进程间的软件中断通知和处理机制
进程在执行过程中有正常的执行流程,如果发生了意外的事件怎么处理呢?并且每一个进程有不同的处理的时候怎么办?
-
信号的接受处理:
1)捕获catch:执行进程指定的信号处理函数被调用
2)忽略ignore:执行操作系统指定的缺省处理,如进程终止,进程挂起
3)屏蔽mask:禁止进程接受和处理信号。(可能是暂时的,当处理同样类型的信号
-
不足:只适合快速通信,因为这种通信机制仅仅只能传送信号的类型,传送的信息量小
-
信号的实现:
1)进程启动时,注册信号处理函数给os内核,以便有信号发送给os时,os可以知道去执行哪一个处理函数
2)有进程或设备发送信号的时候,os kernel负责把这个信号送给指定的进程,并且启动响应的信号处理函数
3)执行信号处理函数,比如杀掉进程或者忽视进程之类的
管道pipe:进程间基于内存文件的通信机制
两个数据想通信,于是在内存中建了临时文件,就将要通信的数据放到临时文件中,子进程从父进程继承通信描述符,缺省文件描述符(fd)有stdin,stdout,stderr
- 与管道相关的系统调用:
1)读管道:read(fd, buffer,nbytes),scanf()是基于这个实现的!!!!!!库函数scanf()就是基于管道的读实现的!
2)写管道:write(fd, buffer,nbytes),printf()是基于写管道实现的!!!!
3)创建管道:pipe(rgfd):rgfd是2个文件描述符组成的数组,rgfd[0]是读文件描述符,rgfd[1]是写文件描述符,继承父进程的通信描述符,一头读一头写就实现两者的通信了!!!bravo!!!
消息队列:由操作系统维护的以字节序列为基本单位的间接通信机制
(间接通信机制必然是由os维护的,所以标题重点就是:消息队列通信以字节序列为基本单位)
图片不想搞了,方便理解记忆消息队列就是进程们通过消息队列来进行通信,发送方将消息发到消息队列中,而接收方通过消息队列接收消息,其中相同标识的消息组成 按先进先出的顺序组成一个消息队列
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)