Test-and-set
|
|
In computer science, the test-and-set CPU instruction is a special instruction that atomically tests and modifies the contents of a memory location. It is used to implement semaphores in multiprocessor systems.
In uniprocessor systems, it is sufficient to disable interrupts before accessing a semaphore.
However, in multiprocessor systems, it is impossible and undesirable to disable interrupts on all processors at the same time; and even with interrupts disabled, two or more processors could be attempting to access the same semaphore's memory at the same time. The test-and-set instruction, allows any processor to atomically test and modify a memory location, preventing such multiple processor collisions.
Implementation
The standard test and set instruction behaves like the following function. Crucially the entire function is executed atomically: no process can interrupt the function mid-execution and hence see a state that only exists during the execution of the function. This code only serves to help explain the behaviour of test-and-set, atomicity requires explicit hardware support and hence cant be implemented as a simple function.
function TestAndSet(boolean lock) {
boolean initial = lock
lock = true
return initial
}
Thus mutual exclusion can be implemented using:
boolean lock = false
function Critical(){
while TestAndSet(lock)
skip //spin until lock is acquired
critical section //only one process can be in this section at a time
lock = false //release lock when finished with the critical section
}
This function can be called by multiple processes, but it is guarenteed that only one process will be in the critical section at a time. The solution is unfortunately innefficient in multiprocessor machines as the constant read and writiting of the lock causes cache coherence problems. Test and Test-and-set is a more efficient solution. This usage of TestAndSet is an example of a Spinlock: the while-loop spins waiting to acquire the lock.
See also
External links
- Description (http://edis.win.tue.nl/sys/test-and-set/) from Encyclopaedia of Delay-Insensitive Systems
- "Wait-free Test-and-Set (http://citeseer.ist.psu.edu/355291.html)" by Yehuda Afek
- int testandset(int *lock) (http://www.cs.clemson.edu/~wayne/cpsc823/threads/testandset.s) - C-callable routine written in Sun Sparc assembly language
- Techniques for mutual exclusion (http://sankofa.loc.edu/chu/web/Courses/Cosi410/Ch2/testset.htm)