2

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.

4

6 回答 6

3

您的比较交换建议有一个很大的缺点 - 它不公平，因为它有利于短期任务。如果系统中有许多短任务，那么完成长任务的机会可能会非常低。

于 2009-09-16T00:01:27.867 回答
2

比赛的发生有四个条件。

  1. 第一个条件是可以从多个线程访问的内存位置。通常，这些位置是全局/静态变量，或者是可从全局/静态变量访问的堆内存。
  2. 第二个条件是存在与这些共享内存位置相关联的属性（通常称为不变量），该属性必须为真或有效，程序才能正常运行。通常，该属性需要在更新发生之前保持为真以使更新正确。
  3. 第三个条件是不变量属性在实际更新的某些部分不成立。（它在处理的某些部分暂时无效或错误）。

  4. 竞争发生必须发生的第四个也是最后一个条件是另一个线程在不变量被破坏时访问内存，从而导致不一致或不正确的行为。

    1. 如果您没有可从多个线程访问的共享内存位置，或者您可以编写代码以消除该共享内存变量，或将对其的访问限制为仅一个线程，那么就不可能出现竞争条件，您无需担心任何事情。否则，lock 语句或其他一些同步例程是绝对必要的，不能安全地忽略。

    2. 如果没有不变量（假设您所做的只是写入此共享内存位置，而线程操作中没有任何内容读取它的值），那么再一次，没有问题。

    3. 如果不变量永远不会无效，那么也没有问题。（假设共享内存是一个日期时间字段，存储代码最后一次运行的日期时间，那么除非线程根本无法写入它，否则它不会无效......

    4. 要消除 nbr 4，您必须使用锁定或一些类似的同步方法来限制对一次从多个线程访问共享内存的代码块的写访问。

在这种情况下，“并发命中”不仅是不可避免的，而且是绝对必要的。智能分析究竟什么是共享内存，以及您的关键“不变量”究竟是什么，让您可以对系统进行编码，以最大限度地减少这种并发“命中”。（即，安全地最大化并发。）

于 2009-09-16T01:08:44.453 回答
1

I'd like to know how you would perform this task using your lock free programming style? You have a number of worker threads all periodically hitting a shared lists of tasks for the next job to perform. (currently) They lock the list, find the item at the head, remove it, and unlock the list. Please take into account all error conditions and possible data races so that no two threads can end up working on the same task, or that a task is accidentally skipped.

I suspect that the code to do this may suffer from a problem of over-complexity and have a possibility of poor performance in the case of high contention.

于 2009-09-16T00:01:08.787 回答
1

与 Interlocked.CompareExchange 之类的 CAS 操作相比，锁定的最大优势在于您可以修改锁定中的多个内存位置，并且所有修改将同时对其他线程/进程可见。

使用 CAS，只有一个变量会自动更新。Lockfree 代码通常要复杂得多，因为您不仅可以一次仅将单个变量（或使用 CAS2 的两个相邻变量）的更新呈现给其他线程，还必须能够在 CAS 不处理时处理“失败”条件不成功。另外，您需要处理 ABA 问题和其他可能的并发症。

有多种方法，如低锁、细粒度锁、条带锁、读写锁等，可以使简单的锁代码更加多核友好。

也就是说，锁定和无锁代码都有很多有趣的用途。但是，除非您真的知道自己在做什么，否则创建自己的无锁代码不适合初学者。使用经过充分验证的无锁代码或算法并对其进行彻底测试，因为在许多无锁尝试中导致失败的边缘条件很难找到。

于 2009-10-30T16:18:10.883 回答
1

我想说的是，一般来说，悲观并发在乐观并发的情况下已经过时，或者模式 A 因为模式 B 而过时。我认为这与上下文有关。无锁很强大，但单方面应用它可能没有意义，因为并非每个问题都完全适合这一点。有取舍。也就是说，最好有一种通用的无锁、乐观的方法，而传统上它还没有实现。简而言之，是的，锁 可以做一些其他方法无法实现的事情：代表一个可能更简单的解决方案。再说一次，如果某些事情无关紧要，两者可能具有相同的结果。我想我有点模棱两可...

于 2010-07-27T03:12:53.140 回答
0

理论上，如果有固定数量的工作要做，使用的程序Interlocked.CompareExchange将设法在不加锁的情况下完成所有工作。不幸的是，在存在高争用的情况下，读取/计算新/compareExchange 循环最终可能会非常糟糕，以至于 100 个处理器每个尝试对一个公共数据项执行一次更新可能最终会花费更长的时间 -实时-比单个处理器按顺序执行 100 次更新。并行性不会提高性能——它会扼杀它。使用锁来保护资源意味着一次只有一个 CPU 可以更新它，但会提高性能以匹配单 CPU 的情况。

无锁编程的一个真正优势是，如果线程被阻塞任意时间，系统功能不会受到不利影响。通过结合使用锁和超时，可以保持这一优势，同时避免纯粹CompareExchange基于编程的性能缺陷。基本思想是在存在争用的情况下，资源切换到基于锁的同步，但是如果一个线程持有一个锁的时间过长，就会创建一个新的锁对象，而之前的锁将被忽略。这将意味着如果前一个线程仍在尝试执行CompareExchange循环，它将失败（并且必须重新开始），但后面的线程不会被阻塞，也不会牺牲正确性。

请注意，仲裁上述所有内容所需的代码将是复杂和棘手的，但如果希望系统在存在某些故障条件时保持稳健，则可能需要此类代码。

于 2013-02-12T00:27:14.430 回答