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?
9 Answers 9
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:
- Most of the time there isn’t a race condition, so the update happens without having to acquire some sort of mutex.
- 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.
@jason-cohen: That’s actually a description of Compare and Swap. Test and set typically involves only the values 0 and 1. The set part refers to setting the value at a specified memory location to 1. It returns the previous value, either a 1 or a 0, and does all of this in a single atomic operation.
@GregSlepak is correct, this is compare_and_swap. test_and_set() takes a boolean pointer to a target, sets it to TRUE and returns the original value of the pointer. If the return value of test_and_set(&lock) (i.e. original value of &lock) is true, then we enter critical section.
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.
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.
Команда Test-and-Set (проверить и присвоить).
К сожалению, даже в таком виде полученный алгоритм не удовлетворяет условию ограниченного ожидания для алгоритмов. Подумайте, как его следует изменить для соблюдения всех условий.
Команда Swap (обменять значения).
Выполнение команды Swap, обменивающей два значения, находящихся в памяти, можно проиллюстрировать следующей функцией:
Применяя атомарную команду Swap, мы можем реализовать предыдущий алгоритм, введя дополнительную логическую переменную key, локальную для каждого процесса:
Механизмы синхронизации процессов и потоков.
Рассмотренные в конце предыдущего раздела алгоритмы хотя и являются корректными, но достаточно громоздки и не обладают элегантностью. Более того, процедура ожидания входа в критический участок предполагает достаточно длительное вращение процесса в пустом цикле, т. е. напрасную трату драгоценного времени процессора. Существуют и другие серьезные недостатки у алгоритмов, построенных средствами обычных языков программирования. Допустим, что в вычислительной системе находятся два взаимодействующих процесса: один из них – H – с высоким приоритетом, другой – L – с низким. Пусть планировщик устроен так, что процесс с высоким приоритетом вытесняет низкоприоритетный процесс всякий раз, когда он готов к исполнению, и занимает процессор на все время своего CPU burst (если не появится процесс с еще большим приоритетом). Тогда в случае, если процесс L находится в своей критической секции, а процесс H, получив процессор, подошел ко входу в критическую область, мы получаем тупиковую ситуацию. Процесс H не может войти в критическую область, находясь в цикле, а процесс L не получает управления, чтобы покинуть критический участок.
Для того чтобы не допустить возникновения подобных проблем, были разработаны различные механизмы синхронизации более высокого уровня. Описанию ряда из них – семафоров, мониторов и сообщений – и посвящен данный раздел.
Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 г.