DSP

活锁 Livelock

2019-07-13 19:47发布

【概念】 活锁指的是任务或者执行者没有被阻塞,由于某些条件没有满足,导致一直重复尝试,失败,尝试,失败。 活锁和死锁的区别在于,处于活锁的实体是在不断的改变状态,所谓的“活”, 而处于死锁的实体表现为等待;活锁有可能自行解开,死锁则不能。 活锁可以认为是一种特殊的饥饿。 下面这个例子在有的文章里面认为是活锁。实际上这只是一种饥饿。因为没有体现出“活”的特点。 假设事务T2再不断的重复尝试获取锁R,那么这个就是活锁。 如果事务T1封锁了数据R,事务T2又请求封锁R,于是T2等待。T3也请求封锁R,当T1释放了R上的封锁后,系统首先批准了T3的请求,T2仍然等待。然后T4又请求封锁R,当T3释放了R上的封锁之后,系统又批准了T4的请求......T2可能永远等待。 活锁应该是一系列进程在轮询地等待某个不可能为真的条件为真。活锁的时候进程是不会blocked,这会导致耗尽CPU资源。 【例子】 单一实体的活锁 例如线程从队列中拿出一个任务来执行,如果任务执行失败,那么将任务重新加入队列,继续执行。假设任务总是执行失败,或者某种依赖的条件总是不满足,那么线程一直在繁忙却没有任何结果。 协同导致的活锁 生活中的典型例子: 两个人在窄路相遇,同时向一个方向避让,然后又向另一个方向避让,如此反复。 通信中也有类似的例子,多个用户共享信道(最简单的例子是大家都用对讲机),同一时刻只能有一方发送信息。发送信号的用户会进行冲突检测, 如果发生冲突,就选择避让,然后再发送。 假设避让算法不合理,就导致每次发送,都冲突,避让后再发送,还是冲突。 计算机中的例子:两个线程发生了某些条件的碰撞后重新执行,那么如果再次尝试后依然发生了碰撞,长此下去就有可能发生活锁。 【解决】 解决协同活锁的一种方案是调整重试机制。 比如引入一些随机性。例如如果检测到冲突,那么就暂停随机的一定时间进行重试。这回大大减少碰撞的可能性。 典型的例子是以太网的CSMA/CD检测机制。 另外为了避免可能的死锁,适当加入一定的重试次数也是有效的解决办法。尽管这在业务上会引起一些复杂的逻辑处理。