OS-6
一些对课本内容的补充:
死锁和阻塞是必须要完全清楚区分的
课后习题第一题的最后选择,也是这样一件事的阐述
争夺一个资源并不会产生死锁,只有互相抢夺互相所拥有的资源才会产生逻辑死锁
阻塞、饥饿都是多个进程对同一个互斥资源的抢夺,逻辑上不存在互相的锁死
只存在互相的等待行为,等待完了就可以拿到这个资源,逻辑上没有互相锁死的存在
同时也可以通过可以逻辑上该行为可以被自发解决,不会一直僵持下去
饥饿可能阻塞,也可能一直就绪
而死锁是相互的
进程A占有一个资源X后向进程B占用的资源Y索取
进程B占用资源Y的同时向进程A索取资源X,这才是死锁,和阻塞像,但绝对需区分
逻辑上该行为是无法被自发解决的
死锁必然阻塞,阻塞不一定死锁,也可能是饥饿
至于死循环,那个是程序逻辑的问题,和这边没关系
循环等待并不是说那个While()循环,而是课本上P150页上面的图,这个才是循环等待
同时附了一些常见的资源类型,都说了历朝历代考研人才是王道
死锁四个条件内,对于不可剥夺条件、请求与保持条件的一些解释:
这两个是最为类似的,也是最容易搞错的,后面对死锁的预防动作中也是极其容易混淆
不可剥夺指进程所占据资源的不可剥夺性,无法被他人强行夺走
请求并保持条件,是指代拥有一个不可剥夺资源后,再提出对其他资源的请求
注意请求条件实际上是在不可剥夺条件上进一步的强化,所以会感觉类似
附:
互斥使用一般指代的是资源的互斥性,一般是共享资源的互斥访问为主
这里需要和后续的破坏方法相区分开,有一定的不同和相似,易混淆之处
后面的资源图,实际上还是很好用的,主要就是这个充分必要条件,以及必要条件的情况
当然其实个人认为,对于死锁的破解,一定要抓住一个想法:
至少让一个进程能够活动,完成运行
只要完成了这样一个操作,那么死锁自然也就不存在,自然就会被破解
类似的,只让四个哲学家吃饭,那么在这四个哲学家中至少有一个哲学家是正常吃饭的
因此就不可能产生死锁问题
银行家算法也是遵循了这个思想,每次至少让一个可行的进程先运行,而阻塞不可行的
对于这个问题,也是类似的
需要避免的,就是箱子里全都是车轮或者全都是车架导致工人三无法组装的死锁问题
怎么避免?我想这种思路也是很容易看穿的
就是至少让当前箱子里,有那么一整套自行车的零部件
和死锁的处理思想几乎是一模一样,就是让当前至少能够正常完成一个进程
附:
参考代码:
semaphore mutex = 1; // 缓冲区互斥信号量
semaphore empty=N; // 箱子内的空位
semaphore weel=0; // 车轮
semaphore frame=0; // 车架
semaphore weel_empty=N-1; // 剩余车轮空位数名额
semaphore frame_empty=N-2; // 剩余车架空位数名额
工人1活动:
do {
加工一个车架;
P(frame_empty); // 占用缓冲区可放置车架数名额
P(empty); // 占用一个缓冲区空位置
P(mutex);
车架放入箱中;
V(mutex);
V(frame); // 车架数量+1
} while(1)
工人2活动:
do {
加工一个车轮;
P(weel_empty); // 占用缓冲区可放置车轮数名额
P(empty); // 占用一个缓冲区空位置
P(mutex);
车轮放入箱中;
V(mutex);
V(wheel); // 车轮数+1
} while(1)
工人3活动:
do {
P(frame); // 取出一个车架
P(mutex);
箱中取一个车架;
V(mutex);
V(empty); // 空位+1;
V(frame_empty); // 释放一个缓冲区可放置车架数名额;
P(wheel);
P(wheel);
P(mutex);
箱中取两个车轮;
V(mutex);
V(empty);
V(empty);
V(weel_empty); // 释放一个缓冲区可放置车轮数名额;
V(weel_empty); // 释放一个缓冲区可放置车轮数名额;
组装为一辆车;
} while(1)
其实这里引出一个问题,车轮、车架空位名额能否用计数量表示?
答案就是可以,但没什么必要
因为这里是一个工人只生产一种产品,所以即使是独占式的也不会导致其他工人无法工作
但,如果是多个工人生产一个产品,那么就一定要设置计数量,否则就会导致互斥
就会导致实际上只有一个工人在正常工作,别的工人都闲着,而实际上不应该有此逻辑
工人工作又不会是互斥的
但如果再稍微改一下,工人使用箱子是需要互斥的,应该怎么写?
这个就比较有趣,实际上应该在工人造完东西后再去申请这个箱子的使用权
而不是说工人在造东西的时候一直占用箱子,这就会导致各工人间的互斥
而实际需要的是工人之间能够并行工作,仅仅是打开放东西这一步需要互斥而已
算是一个比较有趣的变体,能准确模拟出来工作流程就能写
死锁预防之破坏:
破坏互斥一般不太可能用,也不太可能考,实际上也依旧是互斥的,没有能够破坏
重点:
区分破坏不可剥夺与破坏请求并保持:
破坏不可剥夺的意思是,让其的资源能够被其他进程剥夺
破坏请求并保持的意思是,让其在请求新资源之前,自身没有资源
和上面的条件很像但处理逻辑不一样
破坏不可剥夺,就是在你占用一个不可剥夺资源申请新资源失败的时候,剥夺你的资源
和之前的请求并保持反而仿佛是一个逻辑逆的关系,这一点一定要区分
破坏请求,那么就是让你在每次请求的时候,身上是不附带任何占用资源的
要么,一次性给你全部分配完你所需资源,要么,你每次用完了资源再来申请
哲学家问题中,书上的代码,就是典型的破坏请求并保持
当然也是对“保证当前至少有一个进程畅通无阻”思想的具体体现
附:
不可剥夺条件:这个资源只能被一个所占用,不可剥夺
请求并保持条件:该进行已经保持了一个不可剥夺资源,又申请新的资源
破坏不可剥夺条件:当这个进程占有一个不可剥夺资源又申请新资源失败的时候剥夺资源
破坏请求并保持条件:让这个进程在任何申请资源的时候自己不占用任何资源
所以才会感觉容易混淆
对书上循环破坏的解释:
个人还是倾向于如此理解:避免产生“前一个进程的资源被后一个进程所要求”
就是避免产生一个资源的申请环即可
至于顺序法还是别的方法,均只是实现思想的手段
一般感觉用排除法比较容易选出来,这个比较隐蔽不太容易看出来
如果不是破坏请求、破坏不可剥夺,那么基本就是属于破坏循环
典型的类似于哲学家问题中的,奇偶位哲学家、左右撇子哲学家、最多四个哲学家拿筷子
这一类的解决都是破坏循环
几种易于混淆的地方:
死锁的预防、死锁的避免、死锁的检测以及解除是不同的概念,但选择题极易考
因为非常容易张冠李戴,很容易互相混淆
死锁预防的策略有四个,破坏四个必要条件
死锁的避免是在分配前预演一遍看是否会产生冲突
死锁解除中的三个方法又要和死锁预防中的四个破坏必要性条件相互区分
尤其是特指和死锁预防中的“资源剥夺”“破坏请求相区分”,因为实在是太类似了
此外,再说一个事情:
死锁的预防能够保证不会产生死锁问题
死锁的避免不能保证避免死锁问题,进入了不安全区依旧可能产生死锁问题
并且要注意这个“可能”,因为进程之间是并发的
所以完全有可能把产生死锁的情况给避免了,所以才说是可能,不安全区不一定死锁
死锁的检查,这个不说了,是已经产生死锁问题了,然后再去处理
对于死锁处理表的一些解释:
死锁检测的主要优点就是不延长初始化时间,同时在发生死锁的时候再去处理
其解除死锁的方法基本都是剥夺性的,所以说造成损失较为严重
死锁检测只需要知道某一刻的资源需求即可,即当下到底是怎么样一个死锁状态即可
宽松而言就是不需要得到总的配额等资源状态,而死锁避免的算法是必须要得到的
银行家算法就是这样,可能会导致一些进程的长期被冷落,因为一直没有足够的资源分配
所以才说缺点是进程可能被长时间阻塞
补:
首先还是阐述三件事,死锁预防、死锁避免、死锁检测和解除
死锁预防含破坏四个必要条件,各自又可以分为不同的策略来完成对其的破坏
死锁避免主要依赖于系统安全状态的判断,其中考察又以银行家算法为主
其他算法则没有明确的说明,只能默认为一般而言不安全状态也可能不死锁
后面有对这句话的详细解释存在
死锁检测主要依赖于对某个时刻资源请求的分配检测,对资源分配图进行化简是否死锁
死锁解除中又可以分为三个主要方法,其中每个方法又可以分为多种策略
简单来说考试内基本都是张冠李戴类型,所以各自就需要明确的区分
对题目内的“死锁避免”、“死锁预防”、“死锁检测”、“死锁解除”一定要划起来
对于真题、课后习题中出现的计算题:
其实也是对“至少满足一个进程可以正常进行”思想的贯彻
当所有都占据了k-1个资源,最后一个资源的竞争就会变成单纯的阻塞等待行为
而不会变成互相锁死的争夺行为,简单来说就是要在任何情况都保持一个进程能够运行
任何情况之下
关于银行家算法:
首先就是安全状态一定不会死锁,这个我想是能够理解的,就是能有一个安全通过的序列
再就是,不安全状态不一定会死锁,这个就比较费解,但网上还是有相应资料的
不安全意味着在正常执行的状态下,不可能找到一个能够避免死锁的办法,必然死锁
那么,只要出现“不正常”执行状态,那么就可能避免死锁
银行家算法因为避免了不安全状态,所以一定不会产生任何的死锁,但可能会饥饿
[https://blog.csdn.net/qq_34666857/article/details/104122776]
此外,需要把银行家算法和系统区分开
首先需要把系统看作是一个能够自动避开可能死锁状态的机器
只需要有那么一条路的存在,那么系统一定就会选择这条路,而这不需要银行家算法辅助
没有这样一条路的存在,那么在正常执行过程必然死锁,但“非正常”下可避免死锁
银行家算法仅仅是通过正确分配资源,来避免进入“不安全状态”,让系统一定有路可走
至于系统到底怎么走,这和银行家算法毫无关系,其只决定当前是否给该进程分配资源
同时分配资源的同时要保证能给系统留下一条路,系统怎么走他不会干预
算法本身只是模拟了系统可能走的一些路径,不代表系统最终怎么走,其结果不会被参考
银行家算法只是保证分配资源的时候,必然会给系统留下来一个能通过的路径
通过合理分配资源来实现这一点
关于银行家算法的过程:
首先是算出当前的Need数组,然后是用申请和其比较
然后再和可用比较,如果均通过
那么尝试走下去,可用减少、需求量减少,分配量增加
然后记录当前的可用量
这个可用量和表内的需求量比较,如果对某个通过可行,直接加其对应的分配量
然后反复比较,如果发现某次对于任意都可行,那么直接全部通过,后面随意序列都可
附:
对于课后习题第二十三的一些思索
其实这个就是典型的,写者、读者平衡策略,而答案实际上是写了一大堆
这边透出的核心思想其实还是,保证一个进程但凡有一个还在运行
就要锁死另外一方的资源令其不能访问,也就是设置计数器的方式来解决问题
虽然统考那么多年没考过读者-写者问题
此外,第三十八题,个人留了草稿,后续可以回头看