У комп'ютерній архітектурі процесорна інструкція test-and-set (або послідовність інструкцій) призначена для реалізації взаємного виключення у багатопроцесорному середовищі. Хоча коректне блокування можна реалізувати за допомогою test-and-set, оптимізація test and test-and-set зменшує конкуренцію за ресурси, спричинену блокуванням шини, особливо накладні витрати, пов'язані з протоколом когерентності кеша у разі конкуренції за блокування.
Нехай задано змінну блокування: boolean locked := false // shared lock variable
Тоді протокол входу має такий вигляд: procedure EnterCritical() { do { while ( locked == true ) skip // spin using normal instructions until the lock is free } while ( TestAndSet(locked) == true ) // attempt actual atomic locking using the test-and-set instruction } а протокол виходу: procedure ExitCritical() { locked := false
Відмінність від простого протоколу test-and-set полягає в наявності додаткового циклу активного очікування (test у test and test-and-set) на початку протоколу входу, який використовує звичайні інструкції завантаження. Завантаження в цьому циклі виконується з меншими накладними витратами порівняно з атомарною операцією (або інструкцією load-exclusive). Наприклад, у системі, що використовує протокол когерентності кешу MESI, рядок кешу під час такого завантаження переводиться до стану Shared, тоді як інструкція test-and-set або load-exclusive переводить його до стану Exclusive.
Це особливо вигідно, коли кілька процесорів одночасно змагаються за одне й те саме блокування: якщо атомарна інструкція або інструкція load-exclusive потребує транзакції протоколу когерентності для надання процесору ексклюзивного доступу до рядка кешу (через що цей рядок постійно передається між задіяними процесорами), то звичайні операції завантаження рядка, що перебуває у стані Shared, взагалі не потребують транзакцій протоколу. Таким чином, процесори, які виконують активне очікування у внутрішньому циклі, працюють виключно локально.
Транзакції протоколу когерентності кешу використовуються лише у зовнішньому циклі, після того як початкова перевірка показала, що спроба захопити блокування має достатньо високі шанси на успіх.
Якщо використовувана мова програмування підтримує обчислення за короткою схемою, протокол входу можна реалізувати так: procedure EnterCritical() { while ( locked == true or TestAndSet(locked) == true ) skip // spin until locked
Застереження
Хоча ця оптимізація є корисною в системному програмуванні, використання test-and-set слід уникати у високорівневому конкурентному програмуванні: активне очікування в прикладних програмах позбавляє планувальник операційної системи інформації про те, який потік і на якому блокуванні очікує. Унаслідок цього планувальник змушений лише припускати, як розподіляти процесорний час між потоками, — зазвичай просто дозволяючи їм вичерпати свій часовий квант. У результаті потоки безрезультатно виконують активне очікування, чекаючи на потоки, які в цей момент навіть не заплановані до виконання.
Якщо ж використовувати об'єкти блокування, що надаються операційною системою, наприклад м'ютекси, операційна система може планувати виконання саме тих потоків, які не заблоковані.
Див. також Паралельні обчислення М'ютекс Test-and-set Fetch-and-add
Посилання Gregory R. Andrews, Foundations of Multithreaded, Parallel, and Distributed Programming, pp. 100–101. Addison-Wesley, 2000. .