Test-and-set

Test-and-set

In computer science, the test-and-set instruction is an instruction used to both test and (conditionally) write to a memory location as part of a single atomic (i.e. non-interruptible) operation. 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 another 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.

Hardware Implementation

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

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 waiting 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.

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.

Code

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. NOTE: In this example, 'lock' is assumedto be passed by reference (or by name) but the assignment to 'initial' creates a new value (not just copying a reference).

function TestAndSet("boolean" lock) { "boolean" initial = lock lock = true return initial }

The above code segment is not atomic in the sense of the test-and-set instruction. It also differs from the descriptions of DPRAM hardware test-and-set above in that here the "set" value and the test are fixed and invariant, and the "set" part of the operation is done regardless of the outcome of the test, whereas in the description of DPRAM test-and-set, the memory is set only upon passage of the test, and the value to set and the test condition are specified by the CPU. Here, the value to set can only be 1, but if 0 and 1 are considered the only valid values for the memory location, and "value is nonzero" is the only allowed test, then this equates to the case described for DPRAM hardware (or, more specifically, the DPRAM case reduces to this under these constraints). From that viewpoint, this can correctly be called "test-and-set" in the full conventional sense of the term. The essential point to note, which this software function does embody, is the general intent and principle of test-and-set: that a value both is tested and is set in one atomic operation such that no other program thread might cause the target memory location to change after it is tested but before it is set, which would violate the logic requiring that the location will only be set when it has a certain value. (That is, critically, as opposed to merely when it very recently had that value.)

In the C programming language, the implementation would be like:

int TestAndSet(int* lockPtr) { int oldValue; oldValue = SwapAtomic(lockPtr, 1); return oldValue != 0; }

where SwapAtomic atomically first reads the current value pointed to by lockPtr and then writes 1 to the location. Being atomic, SwapAtomic never uses cached values and always commits to the shared memory store (RAM).

The code also shows that TestAndSet is really two operations: an atomical swap and a test. Only the swap needs to be atomic. (This is true because delaying the value comparison itself by any amount of time will not change the result of the test, once the value to test has been obtained. Once the swap acquires the initial value, the result of the test has been determined, even if it has not been computed yet--e.g. in the C language example, by the != operator.)

Implementing mutual exclusion with TestAndSet

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 }

In pseudo C it would be like:

volatile int lock = 0; void Critical() { while (TestAndSet(&lock) = 1); critical section "//only one process can be in this section at a time lock = 0 "//release lock when finished with the critical section }

Note the "volatile" keyword. In absence of volatile, the compiler and/or the cpus will quite certainly optimize access to lock and/or use cached values, thus rendering the above code erroneous.

Conversely, and unfortunately, the presence of "volatile" does "not" guarantee that reads and writes are committed to memory. Some compilers issue memory barriers to ensure that operations are committed to memory, but since the semantics of "volatile" in C/C++ is quite vague, not all compilers will do that. Consult your compiler's documentation to determine if it does.

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 test-and-set is an example of a Spinlock: the while-loop spins waiting to acquire the lock.

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 (unless using multiple processes to access the same data); 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.

ee also

*Fetch-and-add
*Test and Test-and-set
*Load-Link/Store-Conditional
*Compare-and-swap

External links

* [http://edis.win.tue.nl/sys/test-and-set/ Description] from Encyclopaedia of Delay-Insensitive Systems
*" [http://citeseer.ist.psu.edu/355291.html Wait-free Test-and-Set] " by Yehuda Afek
* [http://www.cs.clemson.edu/~wayne/cpsc823/threads/testandset.s int testandset(int *lock)] - C-callable routine written in Sun Sparc assembly language


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Test-and-set — Test and set  простая неразрывная (атомарная) процессорная инструкция, которая копирует значение переменной в регистр, и устанавливает некое новое значение. Во время исполнения данной инструкции процессор не может прервать её выполнение и… …   Википедия

  • Test and Test-and-set — In computer science, the test and set CPU instruction is used to implement mutual exclusion in multiprocessor environments. Although a correct lock can be implemented with test and set, it can lead to memory contention in busy lock (caused by bus …   Wikipedia

  • Test-and-set lock — TSL son las siglas de Test and set lock, una instrucción hardware utilizada por ciertos procesadores para facilitar la creación de semáforos y otras herramientas necesarias para la programación concurrente en computadores. TSL es una instrucción… …   Wikipedia Español

  • Test and tagging — is a generic name given to the process of visually inspecting and electrically testing in service electrical equipment for personal use and/or safety. Colloquially, it is also referred to as; tagging, test tag, test and tag, electrical tagging,… …   Wikipedia

  • Test and learn — is a set of practices followed by retailers and consumer focused companies to test ideas in a small number of locations or customers to predict impact. The process is often designed to answer three questions about any tested program before… …   Wikipedia

  • Test (Unix) — test is a Unix command that evaluates conditional expressions.yntax test expression or [ expression ] DescriptionThe test command evaluates the expression parameter. In the second form of the command, the [ ] (brackets) must be surrounded by… …   Wikipedia

  • Test fixture — refers to the fixed state used as a baseline for running tests in software testing. The purpose of a test fixture is to ensure that there is a well known and fixed environment in which tests are run so that results are repeatable. Some people… …   Wikipedia

  • Test-driven development — (TDD ) is a software development technique consisting of short iterations where new test cases covering the desired improvement or new functionality are written first, then the production code necessary to pass the tests is implemented, and… …   Wikipedia

  • Test light — Neon test lamp for line voltages A test light, test lamp, voltage tester, or mains tester is a very simple piece of electronic test equipment used to determine the presence or absence of an electric voltage in a piece of equipment under test.… …   Wikipedia

  • test — The event of a price movement that approaches a support level or a resistance level established earlier by the market. A test is passed if prices do not go below the support or resistance level, and the test is failed if prices go on to new lows… …   Financial and business terms

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”