CODEWITHSUNDEEP
synchronizationembeddedmutextest-and-set
Benoit
Benoit

Reputation: 39094

What is Test-and-Set used for?

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?

Upvotes: 19

Views: 43701

Answers (8)

H.H
H.H

Reputation: 491

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

Upvotes: 0

Aleksei Marashov
Aleksei Marashov

Reputation: 1

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

Upvotes: 0

Li Chen
Li Chen

Reputation: 5280

It can also be used to implement spinlock:

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

Upvotes: 0

HenryR
HenryR

Reputation: 8519

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.

Upvotes: 6

dongola7
dongola7

Reputation: 269

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.

Upvotes: 0

Jason Cohen
Jason Cohen

Reputation: 83081

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.

Upvotes: 21

moonshadow
moonshadow

Reputation: 89165

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.

Upvotes: 12

tzot
tzot

Reputation: 96061

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.

Upvotes: 1

Related Questions