目录

3. 操作系统 校招复习(持续更新~)

生产者消费者算法

信号量机制

PV 操作

死锁

经典生活例子:独木桥

死锁的概念

什么是死锁?

产生死锁的必要条件

  1. 互斥条件。即某个资源在一段时间内只能由一个进程占有,不能同时被两个或两个以上的进程占有。

    如独木桥就是一种独占资源,两方的人不能同时过桥。

  2. 不可抢占条件。进程所获得的资源在未使用完毕之前,资源申请者不能强行地从资源占有者手中夺取资源,而只能由该资源的占有者进程自行释放。

    如过独木桥的人不能强迫对方后退,也不能非法地将对方推下桥,必须是桥上的人自己过桥后空出桥面(即主动释放占有资源),对方的人才能过桥。

  3. 占有且申请条件。进程至少已经占有一个资源,但又申请新的资源;由于该资源已被另外进程占有,此时该进程阻塞;但是它在等待新资源时,仍继续占用已占有的资源。

    以过独木桥为例,甲乙两人在桥上相遇。甲走过一段桥面(即占有了一些资源),还需要走其余的桥面(申请新的资源);但那部分桥面被乙占有(乙走过一段桥面)。甲过不去,前进不能,又不后退;乙也处于同样的情况。

  4. 循环等待条件。存在一个进程等待序列{P1, P2, …, Pn},其中 P1 等待 P2 所占有的某一些资源,P2 等待 P3 所占有的某一些资源,…,而 Pn 等待 P1 所占有的某一资源,形成一个进程循环等待环。

    就像前面的过独木桥问题,甲等待乙占有的桥面,而乙有等待甲占有的桥面,从而彼此循环等待。

死锁的预防

死锁的预防是保证系统不进入死锁状态的一种策略。它的基本思想是要求进程申请资源时遵循某种协议,从而打破产生死锁的四个必要条件中的一个或几个,保证系统不会进入死锁状态。

  1. 打破互斥条件。即允许进程同时访问某些资源

    有些资源是不允许被同时访问的,如打印机等等,这是由资源本身的属性所决定的。

    所以,这种方法并无实用价值。

  2. 打破不可抢占条件。即允许进程强行从占有者那里夺取某些资源

    就是说,当一个进程已占有了某些资源,它又申请新的资源,但不能立即被满足时,它必须释放所占有的全部资源,以后再申请;它所释放的资源可以分配给其他进程;这就相当于该进程占有的资源被隐蔽地抢占了。

    这种预防死锁的方法实现起来困难,会降低系统性能。

  3. 打破占有且申请条件。可以实行资源预先分配策略

    资源预先分配策略

    即进程运行前一次性地向系统申请它所需要的全部资源。

  4. 打破循环等待条件。实行资源有序分配策略

    资源有序分配策略

    采用这种策略,即把资源事先分类编号,按号分配,使进程在申请、占用资源时不会形成环路。

    所有进程对资源的请求必须严格按资源序号递增的顺序提出;进程占用了小号资源,才能申请大号资源,就不会形成环路,从而预防了死锁。

如何避免?(预防和避免不是一个玩意吗?)

安全序列

银行家算法

死锁的检测与解除

Java面试宝典导读 第8章 第5节 处理调度与死锁

死锁的检测

死锁的恢复(解除)

一旦在死锁检测时发现了死锁,就要消除死锁,使系统从死锁状态中恢复过来。

  1. 资源剥夺法

    挂起某些死锁进程,并抢占它的资源,将这些资源分配给其它的死锁进程。

    应防止被挂起的进程长时间得不到资源时,而处于资源匮乏的状态

  2. 撤销进程法

    强制撤销一个或一部分死锁进程并剥夺这些进程的资源。

    撤销的原则可以按照进程优先级和撤销进程代价的高低进行。

  3. 进程退回法

    让一(多)个进程回退到足以回避死锁的地步,进程回退时自愿释放资源而不是被剥夺。

    要求系统保持进程的历史信息,设置还原点

举例场景?