Test and set (TAS) objects can be used to implement other concurrent objects, like fetch-and-increment (FAI). In 1. (subsection 3.4.1), FAI is implemented using TAS objects.
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
enter_critical_section:
MOV <tmp>, #1
XCHG <tmp>, <lock>
CMP <tmp>, #0
JNE enter_critical_section
RET
Test-and-set Lock (TLS) is used to implement entry into a critical section.
TLS <destination> <origin>
In general terms, TLS is an atomic operation consisting of two steps:
Copy the value from origin to destination
Set a value of origin to 1
Let's see how we can implement a simple mutex for entering critical section with a TLS CPU instruction.
We need a memory cell that will be used as a shared resource. Let's call it lock. It's important for us that we can set either 0 or 1 value to this cell of memory.
Then entering critical section will look like:
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
To leave a critical section, just set value of lock back to 0:
leave_critical_section:
MOV <lock>, #0
RET
P.S.
For example, in x86 there is an XCHG instruction, which allows exchanging value of a Registry/Memory with another Register.
XCHG <destination> <origin>
Implementation of entering critical section with XCHG instruction:
enter_critical_section:
MOV <tmp>, #1
XCHG <tmp>, <lock>
CMP <tmp>, #0
JNE enter_critical_section
RET
Basically, its use is exactly for mutexes, given the tremendous importance of atomicity. That's it.
Test-and-set is an operation that can be performed with two other instructions, non-atomic and faster (atomicity bears a hardware overhead when on multiprocessor systems), so typically you wouldn't use it for other reasons.
It's used when you need to get a shared value, do something with it, and change the value, assuming another thread hasn't already changed it.
As for practical uses, the last time I saw it was in implementations of concurrent queues (queues that may be pushed/popped by multiple threads without needing semaphores or mutexes).
Why would you use TestAndSet rather than a mutex? Because it generally requires less overhead than a mutex. Where a mutex requires OS intervention, a TestAndSet can be implemented as a single atomic instruction on the CPU. When running in parallel environments with 100's of threads, a single mutex in a critical section of code can cause serious bottlenecks.
Imagine you were writing a banking application, and your application had a request to withdraw ten pounds (yes, I'm English ;) ) from the account. So you need to read the current account balance into a local variable, subtract the withdrawal and then write the balance back to memory.
However, what if another, concurrent request happens between you reading the value and you writing it out? There's the possibility that the result of that request will get completely overwritten by the first, and the account balance will be incorrect.
Test-and-set helps us fix that problem by checking that the value your overwriting is what you think it should be. In this case, you can check that the balance was the original value that you read. Since it's atomic, it's non-interruptible so no-one can pull the rug out from under you between the read and the write.
Another way to fix the same problem is to take out a lock on the memory location. Unfortunately, locks are tremendously difficult to get right, hard to reason about, have scalability issues and behave badly in the face of failures, so they're not an ideal (but definitely practical) solution. Test-and-set approaches form the basis of some Software Transactional Memories, which optimistically allow every transaction to execute concurrently, at the cost of rolling them all back if they conflict.
You use it any time you want to write data to memory after doing some work and make sure another thread hasn't overwritten the destination since you started. A lot of lock/mutex-free algorithms take this form.
假设两个线程执行a = a + 1。 假设 a 以值 100 开头。 如果两个线程同时运行（多核），则两个线程都会将 a 加载为 100，递增到 101，然后存储该值回到a。 错误的！
对于 test-and-set，您所说的是“将 a 设置为 101，但前提是它当前的值为 100”。 在这种情况下，一个线程将通过该测试，但另一个线程将失败。 在失败的情况下，线程可以重试整个语句，这次将 a 加载为 101。 成功。
这通常比使用互斥体更快，因为：
大多数时候不存在竞争条件，因此更新无需获取某种互斥体即可发生。
即使在冲突期间，一个线程也根本不会被阻塞，并且另一个线程旋转并重试比在某些互斥体中将自身挂起要快。
A good example is "increment."
Say two threads execute a = a + 1. Say a starts with the value 100. If both threads are running at the same time (multi-core), both would load a as 100, increment to 101, and store that back in a. Wrong!
With test-and-set, you are saying "Set a to 101, but only if it currently has the value 100." In this case, one thread will pass that test but the other will fail. In the failure case, the thread can retry the entire statement, this time loading a as 101. Success.
This is generally faster than using a mutex because:
Most of the time there isn't a race condition, so the update happens without having to acquire some sort of mutex.
Even during collision, one thread isn't blocked at all, and it's faster for the other thread to just spin and retry than it would be to suspend itself in line for some mutex.
发布评论
评论（9）
测试和设置是一个同步机制。
Test and set is a synchronization Mechanism.
测试和设置 (TAS) 对象可用于实现其他并发对象，例如获取和增量 （固定资产投资）。 在1中。 （第 3.4.1 小节），FAI 是使用 TAS 对象实现的。
1. 拉希德·格拉维、彼得·库兹涅佐夫； 并发系统算法
Test and set (TAS) objects can be used to implement other concurrent objects, like fetch-and-increment (FAI). In 1. (subsection 3.4.1), FAI is implemented using TAS objects.
1. Rachid Guerraoui, Petr Kuznetsov; Algorithms for Concurrent Systems
测试和设置锁（TLS）用于实现进入关键部分。
一般来说，TLS 是一个原子操作，由两个步骤组成：
origin复制到destinationorigin的值设置为 1让我们了解我们如何实现一个简单的互斥锁，以使用 TLS CPU 指令进入临界区。
我们需要一个将用作共享资源的存储单元。 我们称之为
锁。 对我们来说重要的是我们可以为该内存单元设置 0 或 1 值。然后进入临界区将如下所示：
要离开临界区，只需将
lock的值设置回 0：PS
例如，在 x86 中，有一个 XCHG 指令，它允许与另一个寄存器交换注册表/内存的值。
XCHG指令进入临界区的实现：
Test-and-set Lock (TLS) is used to implement entry into a critical section.
In general terms, TLS is an atomic operation consisting of two steps:
origintodestinationoriginto 1Let's see how we can implement a simple mutex for entering critical section with a TLS CPU instruction.
We need a memory cell that will be used as a shared resource. Let's call it
lock. It's important for us that we can set either 0 or 1 value to this cell of memory.Then entering critical section will look like:
To leave a critical section, just set value of
lockback to 0:P.S.
For example, in x86 there is an XCHG instruction, which allows exchanging value of a Registry/Memory with another Register.
Implementation of entering critical section with XCHG instruction:
它还可以用来实现自旋锁：
It can also be used to implement spinlock:
基本上，考虑到原子性的巨大重要性，它的用途正是用于互斥体。 就是这样。
测试和设置是一种可以使用其他两条指令执行的操作，非原子且速度更快（在多处理器系统上原子性承担硬件开销），因此通常您不会出于其他原因使用它。
Basically, its use is exactly for mutexes, given the tremendous importance of atomicity. That's it.
Test-and-set is an operation that can be performed with two other instructions, non-atomic and faster (atomicity bears a hardware overhead when on multiprocessor systems), so typically you wouldn't use it for other reasons.
当您需要获取共享值、对其执行某些操作并更改该值（假设另一个线程尚未更改该值）时，将使用它。
至于实际用途，我最后一次看到它是在并发队列的实现中（可以由多个线程推送/弹出的队列，不需要信号量或互斥体）。
为什么要使用 TestAndSet 而不是互斥体？ 因为它通常比互斥体需要更少的开销。 当互斥锁需要操作系统干预时，TestAndSet 可以作为 CPU 上的单个原子指令来实现。 当在具有 100 个线程的并行环境中运行时，代码关键部分中的单个互斥体可能会导致严重的瓶颈。
It's used when you need to get a shared value, do something with it, and change the value, assuming another thread hasn't already changed it.
As for practical uses, the last time I saw it was in implementations of concurrent queues (queues that may be pushed/popped by multiple threads without needing semaphores or mutexes).
Why would you use TestAndSet rather than a mutex? Because it generally requires less overhead than a mutex. Where a mutex requires OS intervention, a TestAndSet can be implemented as a single atomic instruction on the CPU. When running in parallel environments with 100's of threads, a single mutex in a critical section of code can cause serious bottlenecks.
想象一下，您正在编写一个银行应用程序，并且您的应用程序请求从帐户中提取十英镑（是的，我是英国人；））。 因此，您需要将当前帐户余额读入局部变量，减去提款，然后将余额写回内存。
但是，如果在读取值和写出值之间发生另一个并发请求怎么办？ 该请求的结果有可能被第一个请求完全覆盖，并且帐户余额将不正确。
测试和设置通过检查您覆盖的值是否是您认为应该的值来帮助我们解决这个问题。 在这种情况下，您可以检查余额是否是您读取的原始值。 因为它是原子的，所以它是不可中断的，所以没有人可以在读取和写入之间从你身上拉出地毯。
解决同一问题的另一种方法是取出内存位置上的锁。 不幸的是，锁非常难以正确使用，难以推理，存在可扩展性问题，并且在面对故障时表现不佳，因此它们不是理想的（但绝对实用的）解决方案。 测试和设置方法构成了一些软件事务内存的基础，这些内存乐观地允许每个事务同时执行，但代价是如果它们发生冲突，则将它们全部回滚。
Imagine you were writing a banking application, and your application had a request to withdraw ten pounds (yes, I'm English ;) ) from the account. So you need to read the current account balance into a local variable, subtract the withdrawal and then write the balance back to memory.
However, what if another, concurrent request happens between you reading the value and you writing it out? There's the possibility that the result of that request will get completely overwritten by the first, and the account balance will be incorrect.
Test-and-set helps us fix that problem by checking that the value your overwriting is what you think it should be. In this case, you can check that the balance was the original value that you read. Since it's atomic, it's non-interruptible so no-one can pull the rug out from under you between the read and the write.
Another way to fix the same problem is to take out a lock on the memory location. Unfortunately, locks are tremendously difficult to get right, hard to reason about, have scalability issues and behave badly in the face of failures, so they're not an ideal (but definitely practical) solution. Test-and-set approaches form the basis of some Software Transactional Memories, which optimistically allow every transaction to execute concurrently, at the cost of rolling them all back if they conflict.
在完成一些工作后想要将数据写入内存时，您可以使用它，并确保自您启动以来另一个线程没有覆盖目标。 许多无锁/互斥算法这种形式。
You use it any time you want to write data to memory after doing some work and make sure another thread hasn't overwritten the destination since you started. A lot of lock/mutex-free algorithms take this form.
一个很好的例子是“增量”。
假设两个线程执行
a = a + 1。 假设a以值100开头。 如果两个线程同时运行（多核），则两个线程都会将a加载为100，递增到101，然后存储该值回到a。 错误的！对于 test-and-set，您所说的是“将
a设置为101，但前提是它当前的值为100”。 在这种情况下，一个线程将通过该测试，但另一个线程将失败。 在失败的情况下，线程可以重试整个语句，这次将a加载为101。 成功。这通常比使用互斥体更快，因为：
A good example is "increment."
Say two threads execute
a = a + 1. Sayastarts with the value100. If both threads are running at the same time (multi-core), both would loadaas100, increment to101, and store that back ina. Wrong!With test-and-set, you are saying "Set
ato101, but only if it currently has the value100." In this case, one thread will pass that test but the other will fail. In the failure case, the thread can retry the entire statement, this time loadingaas101. Success.This is generally faster than using a mutex because: