死锁
死锁
死锁的条件
死锁的产生需要如下4 个条件：
- 互斥：线程对于需要的资源进行互斥的访问（例如一个线程抢到锁）。
- 持有并等待：线程持有了资源（例如已将持有的锁），同时又在等待其他资源（例
如，需要获得的锁）。 - 非抢占：线程获得的资源（例如锁），不能被抢占。
- 循环等待：线程之间存在一个环路，环路上每个线程都额外持有一个资源，而这
个资源又是下一个线程要申请的。
如果这4 个条件的任何一个没有满足，死锁就不会产生。
破坏互斥：
如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如: SPOOLing技术。操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备。类似于在两者之间加了一个中间层输出进程来进行接收 进程请求。
破坏持有并等待：
可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。
破坏非抢占：
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如:剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用)
破坏循环等待：
可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。
相关算法：
哲学家进餐问题：
筷子是临界资源，一段时间只允许一位哲学家使用。为了表示互斥，用一个信号量表示一只筷子，五个信号量构成信号量数组。
核心思想解决方法：
- 利用原子思想完成。即只有拿起两支筷子的哲学家才可以进餐，否则，一支筷子也不拿。
- 奇数号哲学家先拿他左边的筷子，偶数号哲学家先拿他右边的筷子。这样破坏了同方向环路，一个哲学家拿到一只筷子后，就阻止了他邻座的一个哲学家吃饭。
- 至多允许四位哲学家进餐，将最后一个哲学家停止申请资源，断开环路。
- 哲学家申请资源总是按照资源序号先大后小的顺序，这样0，3号哲学家先右后左，但是4号哲学家先左后右，改变方向，破坏了环路。
银行家算法：
核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
死锁检测：
如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程…
则可以画出系统资源图，依次除去顺利执行的线程，如果最终不能消除所有边，则会发生死锁。
解除死锁：
- 资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
- 撤销进程法（或称终止进程法）：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
- 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。
