Test-and-set

From Free net encyclopedia

Revision as of 09:20, 13 April 2006; view current revision
←Older revision | Newer revision→

In computer science, the test-and-set instruction is an instruction used to atomically write to a memory location. This means setting a value, but first performing some test (such as, the value is equal to another given value). If the test fails, the value is not set. If multiple processes may access the same memory, and if a process is currently performing a test-and-set, no other process may begin a "test and set" until the first process is done. CPUs may use test-and-set instructions offered by other electronic components, such as Dual-Port RAM (DPRAM); CPUs may also offer a test-and-set instruction themselves.

1 Hardware Implementation
- 1.1 Variation 1
- 1.2 Variation 2
2 Pseudocode
3 Using test-and-set to implement semaphores
4 See also
5 External links

[edit]

Hardware Implementation

DPRAM test-and-set instructions can work in many ways. Here are two variations, both of which describe a DPRM which provides exactly 2 ports, allowing 2 separate electronic components (such as 2 CPUs) access to every memory location on the DPRAM.

[edit]

Variation 1

When CPU 1 issues a test-and-set instruction, the DPRAM first makes an "internal note" of this by storing the address of the memory location in a special place. If at this point, CPU 2 happens to issue a test-and-set instruction for the same memory location, the DPRAM first checks its "internal note", recognizes the situation, and issues a BUSY interrupt, which tells CPU 2 that it must wait and retry. This is an implementation of a busy-wait or spinlock using the interrupt mechanism. Since this all happens at hardware speeds, CPU 2's wait to get out of the spin-lock is very short.

Whether or not CPU 2 was trying access the memory location, the DPRAM performs the test given by CPU 1. If the test succeeds, the DPRAM sets the memory location to the value given by CPU 1. Then the DPRAM wipes out its "internal note" that CPU 1 was writing there. At this point, CPU 2 could issue a test-and-set, which would succeed.

[edit]

Variation 2

CPU 1 issues a test-and-set instruction to write to "memory location A". The DPRAM does not immediately store the value in memory location A, but instead simultaneously moves the current value to a special register, while setting the contents of memory location A to a special "flag value". If at this point, CPU 2 issues a test-and-set to memory location A, the DPRAM detects the special flag value, and as above, issues a BUSY interrupt.

Whether or not CPU 2 was trying access the memory location, the DPRAM now performs CPU 1's test. If the test succeeds, the DPRAM sets memory location A to the value specified by CPU 1. If the test fails, the DPRAM copies the value back from the special register to memory location A. Either operation wipes out the special flag value. If CPU 2 now issues a test-and-set, it will succeed.

[edit]

Pseudocode

The test and set instruction when used with boolean values 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 can't 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 guaranteed that only one process will be in the critical section at a time. The solution is unfortunately inefficient in multiprocessor machines as the constant reading and writing 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.

[edit]

Using test-and-set to implement semaphores

It's possible to use the test-and-set instruction to implement semaphores. In uniprocessor systems this technique isn't needed; to use semaphores, it is sufficient to disable interrupts before accessing a semaphore. However, in multiprocessor systems, it is undesirable, if not impossible, to disable interrupts on all processors at the same time. Even with interrupts disabled, two or more processors could be attempting to access the same semaphore's memory at the same time. In this case, the test-and-set instruction may be used.

[edit]