17

好的，所以我正在阅读有关同步的内容，并阅读了各种算法，例如自旋锁、信号量和互斥锁，以避免竞争条件。

但是，当多个进程同时访问数据时，这些算法无法防止 SMP 中的竞争条件。

例如，假设处理器 A 中的线程 1 运行 lock(mutex1); 撤回（1000）；解锁（互斥体1）；

处理器 B 中的线程 2 运行 lock(mutex1)；存款（1000）；存款（1000）；解锁（互斥体1）；

当两个线程完全在同一时间运行时，两个线程将同时处于临界区。

唯一的解决方案（应该在硬件级别）是使每个处理器彼此稍微偏离运行，但这违背了并行性的目的。

是否有任何硬件级别的支持来避免多个处理器尝试同时获取锁的情况？

（这不是原子性问题，而是精确并行性问题，我想知道 SMP 是如何处理它的）。

4

5 回答 5

19

互斥锁的全部意义在于，即使两个核心试图同时获取它，其中一个也会被阻塞，直到另一个释放它。一个允许两个核心同时持有该互斥锁的互斥锁将完全被破坏，并且对于它唯一的预期目的毫无用处。

在硬件的某个地方，有一个总线仲裁器，它只允许一个内核控制连接这两个内核的总线。如果任一核心已经拥有在私有缓存中保存互斥锁的内存，则该核心将获胜。否则，谁先坐公交车就赢。

总线仲裁器可以以多种方式工作，但通常它会轮换。因此，如果核心是 0、1、2 和 3，并且核心 2 的总线位于最后，那么如果需要，总线将接下来转到核心 3，否则如果需要，则转到核心 0，否则如果需要，则转到核心 1，否则返回核心 2。根据具体涉及的总线（无论是两个核心的 L2 缓存之间的争斗还是内存本身或其他什么），一些核心可能会作为一个单元与其他核心组竞争，然后再竞争对于哪个特定的核心首先得到它。

可能是一个核心已经控制了总线，因此它将彻底获胜。通常，仲裁器允许核心持续持有总线，只要它继续想要将它用于一些事务，以避免不允许核心向前推进的浪费切换。

确切的细节可能会因大量因素而异，包括内核的排列方式、哪些内核在其缓存中处于何种状态、谁有总线最后以及总线仲裁器是否使用时间片、循环或某些其他机制等等。但是，任何不能保证只有一个核心最终获得锁的实现都将被视为严重损坏。

于 2011-10-23T01:19:17.500 回答
3

您可能想研究内存障碍。

http://en.wikipedia.org/wiki/Memory_barrier

在这种情况下，锁将使用内存屏障，因此锁中使用的内部值不能被多个处理器同时访问。

一些架构还允许锁定除 1 之外的所有内核以实现这一点。例如，x86 带有一个 LOCK 前缀，当添加到指令中时，该前缀将在该指令期间锁定对内存的访问。（例如：LOCK ADD EAX，1 表示寄存器的原子增量）

不支持 LOCK 或原子指令的架构使用比较和交换或测试和设置/交换。通常它涉及一个小的指令循环，在高层可能看起来像

while (target != value) target = value;

这可能看起来不会执行多次，但它确保在指令之间，值不会从它下面改变。这种方法的缺点是，如果目标竞争激烈，那么它可能会占用比您想要的更多的时钟周期，但它往往发生得足够快，因此它永远不会真正引人注目。

于 2011-10-23T00:58:07.433 回答
1

我强烈推荐Curt Schimmel 的 UNIX® Systems for Modern Architectures：Symmetric Multiprocessing and Caching for Kernel Programmers。不同的硬件架构为同步访问数据提供了不同的低级工具，包括一些几乎没有帮助的架构。Schimmel 的书提供了甚至可以在这些架构上工作的算法。

我希望我能很容易地找到我的副本来总结内容。

于 2011-10-23T01:10:25.807 回答
0

您可以使用 TLS 和 XCHG 等原子指令来防止这种情况。

你如何确保指令的原子性？

您可以在执行指令之前禁用所有中断，然后在指令完成后将它们全部启用。这对多核系统没有帮助，因为禁用处理器 1 中的中断对处理器 2 没有任何影响。在多核系统上，通过防止其他 CPU 访问内存总线（内存屏障）来确保指令的原子性.

因此，如果您使用这些说明来实现信号量，那么您在 SMP 上将没有问题。

使用 TSL 实现 mutex_lock 和 mutex_unlock：

 mutex_lock:
    TSL REGISTER, MUTEX ; copy mutex to register and sets mutex
    CMP REGISTER, #0    ; compare mutex to zero
    JZE ok              ; if zero return
    CALL thread_yield   ; else: mutex is busy, schedule another thread
    JMP mutex_lock      ; try again later
 ok: RET

 mutex_unlock:
    MOVE MUTEX,#0       ; free mutex
    RET

您可以在此处找到有关 TSL 的一些信息： http ://en.wikipedia.org/wiki/Test-and-set

一本可以帮助您的好书：http ://www.amazon.com/Modern-Operating-Systems-Andrew-Tanenbaum/dp/0136006639/ref=sr_1_sc_1?ie=UTF8&qid=1319333818&sr=8-1-spell

于 2011-10-23T01:27:02.140 回答
-1

这是一个经典的死锁问题。我不确定硬件支持，（但我几乎可以肯定这在硬件级别得到支持）但是，我可以给你一个关于数据库死锁问题的解决方案的例子。如果您知道所有依赖项，则您知道应该“杀死”哪个依赖项，这样给定节点的命令将失败，但系统将消除死锁，其他节点不会失败。我认为同样的方法应该在硬件层面。

于 2011-10-23T01:01:31.893 回答