Test-and-set Primitive

First of all, it’s not the same as “compare-and-swap”. Sounds similar, but different.

What it does is,

  • Set a variable to a new value
  • Return the old value of the variable
int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr; 
    *old_ptr = new;
    return old; // return the old value
}

It’s a hardware primitive, i.e. atomic. On x86 the instruction is `xchg`

What can it be used for? It can be used for implementing locks.

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
        ; // spin-wait (do nothing)
}

void unlock(lock_t *lock) { 
    lock->flag = 0;
}

Say the current flag value is 0. And t1 and t2 both arrives at line 2. Since TestAndSet is atomic, only one thread will get the return value as 0, the other will only get 1, hence only 1 thread gets the lock.

Leave a Comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.