12

在阅读了 Test-and-Set Wikipedia entry之后，我仍然有一个问题“Test-and-Set 将用于什么？”

我意识到您可以使用它来实现 Mutex（如维基百科中所述），但它还有什么其他用途？

4

7 回答 7

17

一个很好的例子是“增量”。

说两个线程执行a = a + 1。Saya以 value 开头100。如果两个线程同时运行（多核），则两者都将加载a为100，递增到101，然后将其存储回a. 错误的！

使用 test-and-set，您说的是“设置a为101，但前提是它当前具有值100。” 在这种情况下，一个线程将通过该测试，但另一个线程将失败。在失败的情况下，线程可以重试整个语句，这次加载a为101. 成功。

这通常比使用互斥锁更快，因为：

  1. 大多数情况下没有竞争条件，因此无需获取某种互斥锁即可进行更新。
  2. 即使在冲突期间，一个线程根本不会被阻塞，并且另一个线程只是旋转并重试比将自己挂起以等待某个互斥体更快。
于 2008-09-23T13:30:33.967 回答
10

您在完成一些工作后想要将数据写入内存时使用它，并确保自您开始以来另一个线程没有覆盖目标。许多无锁/无互斥算法采用这种形式。

于 2008-09-23T13:26:59.903 回答
5

想象一下，您正在编写一个银行应用程序，并且您的应用程序请求从帐户中提取 10 英镑（是的，我是英国人；））。所以你需要将当前账户余额读入一个局部变量，减去取款，然后将余额写回内存。

但是，如果在读取值和写出值之间发生另一个并发请求怎么办？该请求的结果有可能被第一个完全覆盖，并且帐户余额将不正确。

测试和设置通过检查覆盖的值是否是您认为的值来帮助我们解决该问题。在这种情况下，您可以检查余额是否是您读取的原始值。因为它是原子的，所以它是不可中断的，所以没有人可以在读取和写入之间从你下面拉出地毯。

解决相同问题的另一种方法是锁定内存位置。不幸的是，锁非常难以正确，难以推理，存在可伸缩性问题并且在面对故障时表现不佳，因此它们不是理想（但绝对实用）的解决方案。测试和设置方法构成了一些软件事务存储器的基础，它乐观地允许每个事务同时执行，但如果它们发生冲突则以回滚它们为代价。

于 2008-09-23T13:43:29.333 回答
1

基本上，考虑到原子性的巨大重要性，它的用途恰好是互斥锁。就是这样。

测试和设置是一种可以使用其他两条指令执行的操作，非原子指令和更快（在多处理器系统上原子性承担硬件开销），因此通常您不会出于其他原因使用它。

于 2008-09-23T13:26:48.890 回答
0

当您需要获取共享值、对其执行某些操作并更改该值时使用它，假设另一个线程尚未更改它。

至于实际用途，我最后一次看到它是在并发队列的实现中（可以由多个线程推送/弹出而不需要信号量或互斥锁的队列）。

为什么要使用 TestAndSet 而不是互斥锁？因为它通常比互斥锁需要更少的开销。在互斥体需要操作系统干预的情况下，可以将 TestAndSet 实现为 CPU 上的单个原子指令。在具有 100 个线程的并行环境中运行时，关键代码部分中的单个互斥锁可能会导致严重的瓶颈。

于 2008-09-23T13:33:51.277 回答
0

它也可以用来实现自旋锁：

void spin_lock(struct spinlock *lock)
{
        while (test_and_set(&lock->locked));
}
于 2022-02-12T02:26:05.743 回答
0

测试和设置锁 (TLS) 用于实现进入临界区。

TLS <destination> <origin>

一般来说，TLS 是一个原子操作，包括两个步骤：

  1. 将值从复制origin到destination
  2. 将值设置origin为 1

让我们看看我们如何实现一个简单的互斥锁，用于使用 TLS CPU 指令进入临界区。

我们需要一个将用作共享资源的存储单元。让我们称之为lock。对我们来说重要的是，我们可以为这个内存单元设置 0 或 1 值。

然后进入临界区将如下所示：

enter_critical_section:
    TLS <tmp>, <lock>           ; copy value from <lock> to <tmp> and set <lock> to 1
    CMP <tmp>, #0               ; check if previous <lock> value was 0
    JNE enter_critical_section  ; if previous <lock> value was 1, it means that we didn't enter the critical section, and must try again
    RET                         ; if previous <lock> value was 0, we entered critical section, and can return to the caller

要离开临界区，只需将值设置lock回 0：

leave_critical_section:
  MOV <lock>, #0  
  RET

附言

例如，在 x86 中有一条XCHG 指令，它允许与另一个寄存器交换注册表/内存的值。

XCHG <destination> <origin>

XCHG指令进入临界区的实现：

enter_critical_section:
    MOV <tmp>, #1
    XCHG <tmp>, <lock>
    CMP <tmp>, #0
    JNE enter_critical_section
    RET
于 2022-02-22T09:59:06.537 回答