问题标签 [livelock]

我了解什么是活锁，但我想知道是否有人有一个很好的基于代码的示例？并且基于代码，我并不是指“两个人试图在走廊里互相超越”。如果我再读一遍，我会失去午餐。

Summary:

It seems to me that:

1. wrapping fields representing a logical state into a single immutable consumable object
2. updating the object's authoritative reference with a call to Interlocked.CompareExchange<T>
3. and handling update failures appropriately

provides a kind of concurrency that renders the "lock" construct not only unnecessary, but a truly misleading construct that dodges certain realities about concurrency and introduces a host of new problems as a result.

Problem Discussion:

First, let's consider the main problems with using a lock:

1. Locks cause a performance hit, and must be used in tandem for reading and writing.
2. Locks block thread execution, hindering concurrency and risking deadlocks.

Consider the ridiculous behavior inspired by the "lock". When the need arises to update a logical set of resources concurrently, we "lock" the set of resources, and we do so via a loosely associated, but dedicated locking object, which otherwise serves no purpose (red flag #1).

We then use the "lock" pattern to mark-off a region of code where a logically consistent state change on a SET of data fields occurs, and yet we shoot ourselves in the foot by mixing the fields with unrelated fields in the same object, while leaving them all mutable and then forcing ourselves into a corner (red flag #2) where we have to also use locks when reading these various fields, so we don't catch them in an inconsistent state.

Clearly, there's a serious problem with that design. It's somewhat unstable, because it requires careful management of the lock objects (locking order, nested locks, coordination among threads, blocking/waiting on a resource in use by another thread that's waiting for you to do something, etc.), which depends on the context. We also hear people talk about how avoiding deadlock is "hard", when it's actually very straightforward: don't steal the shoes of a person you plan on asking to run a race for you!

Solution:

Stop using "lock" altogether. Properly roll your fields into an incorruptible/immutable object representing a consistent state or schema. Perhaps it's simply a pair of dictionaries for converting to and from display-names and internal-identifiers, or maybe it's a head node of a queue containing a value and a link to the next object; whatever it is, wrap it into it's own object and seal it for consistency.

Recognize write or update failure as a possibility, detect it when it occurs, and make a contextually informed decision to retry immediately (or later) or do something else instead of blocking indefinitely.

While blocking seems like a simple way to queue a task that seems like it must be done, not all threads are so dedicated and self-serving that they can afford to do such a thing at the risk of compromising the entire system. Not only is it lazy to serialize things with a "lock", but as a side affect of trying to pretend a write shouldn't fail, you block/freeze your thread, so it sets there unresponsive and useless, forsaking all other responsibilities in its stubborn wait to accomplish what it set out to do some time earlier, ignorant of the fact that assisting others is sometimes necessary for fulfilling it's own responsibilities.

Race conditions are normal when independent, spontaneous actions are occurring simultaneously, but unlike uncontrolled Ethernet collisions, as programmers we have total control over our "system" (i.e. deterministic digital hardware) and its inputs (no matter how random, and how random can a zero or one really be?) and outputs, and the memory that stores our system's state, so livelock should be a non-issue; furthermore, we have atomic operations with memory barriers that resolve the fact that there may be many processors operating concurrently.

To summarize:

1. Grab the current state object, consume its data, and construct a new state.
2. Realize that other active threads will be doing the very same thing, and may beat you to it, but all observe an authoritative reference point representing the "current" state.
3. Use Interlocked.CompareExchange to simultaneously see if the state object you based your work on is still the most current state, and replace it with your new one, otherwise fail (because another thread finished first) and take appropriate corrective action.

The most important part is how you handle the failure and get back on your horse. This is where we avoid livelocks, thinking too much and not doing enough or doing the right thing. I would say that locks create the illusion that you'll never fall off your horse, despite riding in a stampede, and while a thread daydreams in such a fantasy land, the rest of the system can fall apart and crash and burn.

So, is there something the "lock" construct can do that can't be achieved (better, in a less unstable fashion) with a lock-free implementation using CompareExchange and immutable logical state objects?

All of this is a realization I've come to on my own after dealing with locks intensely, but after some searching, in another thread Is lock free multithreaded programming making anything easier?, someone mentions that lock-free programming is going to be very important when we face highly parallel systems with hundreds of processors, were we cannot afford to use highly contended locks.

我在 Django 上使用 Apache2、mod_python 和 PostgreSQL 8.3 以及 postgresql_psycopg2 数据库后端运行一个中等流行的 Web 应用程序。我偶尔会遇到活锁，当 apache2 进程在几分钟或更长时间内持续消耗 99% 的 CPU 时可识别。

我在 apache2 进程上做了一个 strace -p pid，发现它不断重复这些系统调用：

这个确切的片段在跟踪中不断重复，并且在我最终杀死 apache2 进程之前运行了 10 多分钟。（注意：我对此进行了编辑，以用一个显示完整字符串内容而不是截断的新片段替换我以前的 strace 片段。）

我对上述内容的解释是，django 正在尝试对我的表 account_profile 进行存在检查，但在更早的时候（在我开始跟踪之前）出现了问题（SQL 解析错误？引用完整性或唯一性约束违规？谁知道？ )，现在 Postgresql 返回错误“当前事务已中止”。出于某种原因，它没有引发异常并放弃，而是不断重试。

一种可能性是这是在调用 Profile.objects.get_or_create 时触发的。这是映射到 account_profile 表的模型类。也许 get_or_create 中有一些东西旨在捕获过于广泛的异常并重试？从 Web 服务器日志来看，这种活锁可能是由于双击我网站注册表单中的 POST 按钮而发生的。

在过去的几天里，这种情况在现场已经发生了几次，在我干预之前导致速度显着放缓，所以除了无限死锁之外，几乎任何事情都会有所改善！:)

当您使用 Session-Per-Request 模式时，您在使用 NHibernate 需要支持重试事务失败的 3 层应用程序中使用什么模式/架构？（因为 ISession 在异常后变得无效，即使这是死锁或超时或活锁异常）。

有人可以用示例（代码）解释死锁和活锁有什么区别吗？

我正在运行一个 Xenomai 实时线程，有时需要调用 gettimeofday()，以便根据 ptpd 找出当前时间。

但是，这样做似乎是不安全的：特别是，它偶尔会使 Xenomai 线程和 Linux 内核进入“活锁”情况，导致 gettimeofday() 旋转 CPU 并且永远不会返回，如此处所述。

我的问题是，有没有一种安全的方法可以从 Xenomai 实时线程中获取 gettimeofday() 的信息？我正在考虑将我自己的 gettimeofday() 版本添加到我的 Linux 内核中（如果 read_seqretry() 返回 true，我的版本将失败，与发生这种情况时将永远循环的常规版本不同）。但是，如果有更好的方法，我不会立即开始定制 Linux 内核。

我遇到过 SQL Server 的这个术语，我只是无法理解它在 SQL Server 中到底发生了什么。我正在查看它发生的一些 SQL Server 示例...

我一直在谷歌上搜索，但一直在走廊示例中找到 2 个人。

使用sem_trywait()会让你陷入死锁或活锁吗？

对非同步的并发更新HashMap显然会导致活锁或其他数据损坏；为避免这种情况，应使用并发版本或实施同步机制。

对HashMap.get()的并发调用可以改变 HashMap 的状态，比如重新散列吗？

更新：

一些评论者想知道这个问题的实际方面，除了吹毛求疵的数据结构行为的理论乐趣。

如果get()不改变状态HashMap（并且不能因为另一个原因导致活锁），那么单个线程可以提前创建一个HashMap，然后多个线程可以同时读取它。如果并发读取不安全，我们需要ConcurrentHashMap对每个多线程访问，无论类型如何。

我有一个与 Java 线程活锁相关的有趣问题。就这样吧。

有四个全局锁 - L1,L2,L3,L4

有四个线程 - T1、T2、T3、T4

T1 需要锁 L1,L2,L3 T2 需要锁 L2 T3 需要锁 L3,L4 T4 需要锁 L1,L2

因此，问题的模式是 - 任何线程都可以运行并以任何顺序获取锁。如果任何线程检测到它需要的锁不可用，它会释放它之前获得的所有其他锁，等待固定时间，然后再次重试。循环重复产生活锁条件。

所以，为了解决这个问题，我有两个解决方案

1）让每个线程在重试之前等待一段随机的时间。

2）让每个线程按特定顺序获取所有锁（即使一个线程不需要所有锁）

我不相信这是我唯一可用的两个选项。请指教。