1 、死锁的概念
是指两个或两个以上的事务在执行过程中，因争夺资源而造成的一种互相等待的现象。若无外力作用，事务都将无法推进下去，解决死锁的最简单问题是不要有等待，任何的等待都转换为回滚，并且事务重新开始，但在线上环境，这可能会导致并发性能下降，甚至任何一个事务都不能进行，而这所带来的问题远比死锁的问题更严重
解决死锁的问题最简单的一种方法是超时，当两个事务互相等待时，当一个等待时间超过设置的某一阈值时，其中一个事务回滚，另一个等待的事务就能继续运行了，在InnoDB存储引擎中，参数innodb_lock_wait_timeout用来设置超时时间
超时机制虽然简单，但是其仅通过超时后对事务进行回滚的方式处理，或者说其是根据FIFO的顺序选择回滚对象，但若超时的事务所占权重比较大，如事务操作更新了很多航，占用了较多的undo log,这是采用FIFO方式，就显得不合适了，因为回滚这个事务的时间相对另一个事务所占用的时间可能会更多
除了超时机制，当前的数据库还采用wait-for graph(等待图)的方式来进行死锁检测，较之超时的解决方案，这是一种更为主动的死锁检测方式。InnoDB存储引擎也是采用这种方式。wait-for graph要求数据库保存以下两种信息
锁的信息链表
事务等待链表
通过上述链表可以构造出一张图。而这个在图中若存在回路，就代表存在死锁，因此资源间相互发生等待，在wait-for graph，事务为图中的节点，而在图中，事务T1指向T2边的定义为
事务T1等待事务T2所占用的资源
事务T1最终等待T2所占用的资源，也就是事务之间在等待相同的资源，而事务T1发生在事务T2的后面
看一个例子，当前事务和锁的状态如图
在Transaction Wait Lists中可以看到共有4个事务t1、t2、t3、t4，故在wati-for graph中应有4个节点。而事务t2对row1占用X锁，事务t1对row2占用s锁.事务t1需要等待t2中row1的资源，因此在wait-for graph中有条从节点t1指向节点t2.事务t2需要等待事务t1、t4锁占勇row2对象，故此存在节点t2到节点 t1 t4的边，同样，存在节点t3到节点t1 t2 t4的边，因此最终wait-for graph为
如图，可以发现回路(t1,t2)因此存在死锁。通过上述介绍，可以发现wait-for graph是一种较为主动的死锁检测机制，在每个事务请求锁并发生等待时都会判断是否存在回路，若存在则有死锁，通常来说，InnoDB存储引擎会选择回滚undo量最小的事务
wait-for graph的死锁检测通常采用深度优先的算法实现，在InnoDB1.2版本之前，都是采用递归方式实现，而1.2版本开始，对wait-for graph死锁检测进行了优化，将递归用非递归的方式实现，从而提高了InnoDB存储引擎的性能
原文：http://www.cnblogs.com/olinux/p/5179356.html