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?

Answer 1

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.

Answer 2

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.

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.

Answer 4

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.

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.