What is Test-and-Set used for?

Question

After reading the Test-and-Set Wikipedia entry, I am still left with the question "What would a Test-and-Set be used for?"

I realize that you can use it to implement Mutex (as described in wikipedia), but what other uses does it have?

Achromatin

Answer 1

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.

Philippeville

Answer 2

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:

1. Most of the time there isn't a race condition, so the update happens without having to acquire some sort of mutex.
2. 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.

Indore

@jason-cohen: That's actually a description of Compare and Swap. Test and set typically involves only the values 0 and 1. The set part refers to setting the value at a specified memory location to 1. It returns the previous value, either a 1 or a 0, and does all of this in a single atomic operation. – Edrick

@GregSlepak is correct, this is compare_and_swap. test_and_set() takes a boolean pointer to a target, sets it to TRUE and returns the original value of the pointer. If the return value of test_and_set(&lock) (i.e. original value of &lock) is true, then we enter critical section. – Bourguiba

Agree with @GregSlepak that above reply is an example of Compare-and-swap, instead of Test-and-set. – Anorthosite

Answer 3

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.

Incorruptible

Answer 4

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.

Slipnoose

Answer 5

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.

Orange

mutex internally might use test & set. how do you compare TestAndSet & mutex. I think it's not right comparison – Pith

In Python, mutex objects explicitly have a "testandset" method. The documentation refers to it as "atomic", with quotes, which does not inspire confidence, but it does indicate that the two concepts are not, erm, mutually exclusive. – Forman

Answer 6

It can also be used to implement spinlock:

void spin_lock(struct spinlock *lock)
{
        while (test_and_set(&lock->locked));
}

Bujumbura

Answer 7

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:

1. Copy the value from origin to destination
2. 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

Outsoar

Answer 8

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

Intracellular

Answer 9

Test and set is a synchronization Mechanism.

Forecastle

Welcome to Stack Overflow! While we appreciate contributions from new users, you really have to consider what your answer adds to the others, some of which were posted 15 years ago. – Inexhaustible