Test-and-set

Test-and-set — інструкція, що використовується в інформатиці як атомарна (тобто безперервна) операція для такої послідовності дій: запис в пам'ять і повернення старого значення.

Якщо декілька процесів можуть доступитися до одної ділянки пам'яті, і якщо процес наразі виконує test-and-set, жоден інший процес не може отримати доступ до цієї ділянки доки перший процес не завершить інструкцію. Центральні процесори можуть використовувати test-and-set інструкції запропоновані іншими електронними вузлами, такими як Dual-Port RAM; ЦП також пропонують власну test-and-set інструкцію.

Блокування може бути виконане із використанням атомарної test-and-set інструкції, наприклад так:

function Lock(boolean *lock) {
    while (test_and_set (lock) == 1);
}

Процес отримує блокування якщо старе значення було 0. Цикл продовжує встановлювати 1 доки умова не виконається.

Доведено, що test-and-set має кінцеве число узгодженості, на відміну операції compare-and-swap. Test-and-set операція може розв'язати задачу узгодженості без очікування не більше ніж для двох конкурентних процесів. Свобода від очікування є найсильнішою гарантією прогресу без блокування, яка поєднує загальну роботу системи із свободою від голодування. Алгоритм є вільним від очікування, якщо кожна операція має обмежену кількість кроків, які зробить алгоритм до того як вона завершиться.

Реалізація на рівні апаратного забезпечення

DPRAM test-and-set інструкція може бути виконуватись багатьма шляхами. Тут наведемо дві, обидві описують DPRAM, який має 2 порти, що дозволяє 2 окремим електронним вузлам (таким як 2 центральних процесори) доступатися до кожної комірки пам'яті на DPRAM.

Спосіб 1

Коли ЦП 1 запускає інструкцію test-and-set, DPRAM спочатку робить «внутрішню нотатку» про це шляхом збереження адреси в пам'яті в спеціальному місці. Якщо в цей момент ЦП 2 намагається виконати test-and-set інструкцію для того ж місця в пам'яті, DPRAM спочатку перевіряє свою «внутрішню нотатку», розпізнає ситуацію, і продукує BUSY переривання, яке каже ЦП 2, що він має почекати і повторити спробу згодом. Це є реалізацією busy waiting або spinlock із використанням механізму у переривання. Через те, що все це відбувається на апаратних швидкостях, ЦП 2 очікує дуже мало.

Намагався чи ні ЦП 2 доступитися до пам'яті, DPRAM виконує перевірку завдану ЦП 1. Якщо перевірка успішна, DPRAM встановлює комірку пам'яті значенням заданим ЦП 1. Тоді DPRAM стирає свою «внутрішню нотатку». В цей момент ЦП 2 може запустити виконання інструкції test-and-set, яка успішно виконається.

Спосіб 2

ЦП 1 запускає інструкцію test-and-set для запису «місця пам'яті A». DPRAM не зберігає значення A, натомість одночасно записує поточне значення в спеціальний регістр, і встановлює вміст пам'яті A в спеціальне «значення прапорець». Якщо в цей момент, ЦП 2 запускає test-and-set для A, DPRAM виявляє спеціальний прапорець, і як і в Способі 1, спричиняє BUSY переривання.

Намагався чи ні ЦП 2 доступитися до пам'яті, DPRAM виконує перевірку завдану ЦП 1. Якщо перевірка успішна, DPRAM встановлює комірку пам'яті А значенням заданим ЦП 1. Якщо тест провалюється, DPRAM копіює значення зі спеціального регістра в пам'ять А. Обидві операції затирають прапорець. Тепер ЦП 2 може успішно виконати свою test-and-set.

Реалізація на рівні програмного забезпечення

Багато процесорів мають атомарну test-and-set інструкцію на машинній мові. Це ті, які не можуть реалізувати атомарну test-and-set із використанням атомарного обміну (англ. swap) (як показано нижче) або через інші атомарні read-modify-write інструкції.

При використанні test-and-set інструкція поводяться подібно до наступної функції. Вирішальним моментом є атомарність виконання: жоден процес не може перервати функцію посеред виконання і таким чином побачити стан який виникає під час виконання функції. Наступний код слугує лише для пояснення поведінки test-and-set; атомарність вимагає явної підтримки на апаратному рівні, що унеможливлюю реалізацію у вигляді простої функції. Зауваження: В цьому прикладі, присвоєння 'initial' створює нове значення (не просто копіює посилання).

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

Попередній відтинок коду не є атомарним в сенсі test-and-set інструкції. Він також відрізняється від апаратного DPRAM test-and-set тим, що тут "встановлюване" значення і тест незмінні, і встановлення відбувається незалежно від результату проходження тесту, тоді як в описі DPRAM test-and-set, запис відбувається лише по успішному проходженню тесту, і встановлюване значення і умови тесту визначаються ЦП. Тут, значенням для встановлення може бути лише 1, але якщо лише 0 та 1 визначені можливими значеннями для комірки пам'яті, і перевірка на "ненульове значення" єдина дозволена, тоді це рівноцінно випадку описаному для DPRAM (або, більш точно, для випадку DPRAM зменшеному цими обмеженнями). З цієї точки зору, цей варіант вірно може бути названа «test-and-set» в повному розумінні цього терміну. Головним моментом для зауваження, який втілює ця функція, це мета і принцип інструкції test-and-set: тобто обидві дії з перевірки і встановлення виконуються в одній атомарній операції таким чином жоден інший потік програми не в змозі спричинити зміну задіяної комірки пам'яті після того як відбулась перевірка, але значення ще не встановлене, що порушило б логічну вимогу на те, що пам'ять буде встановлена винятково у випадку якщо вона містить певне значення. (Це є вирішальним чинником на відміну від підходу коли вона нещодавно містила це значення.)

В C, реалізація може бути такою:

 #define LOCKED 1
 int TestAndSet(int* lockPtr) {
     int oldValue;
     oldValue = SwapAtomic(lockPtr, LOCKED);
     return oldValue == LOCKED;
 }

де SwapAtomic атомарно спочатку читає поточне значення на яке вказує lockPtr і тоді записує туди 1. Справді атомарна, SwapAtomic ніколи не використовує кешовані значення і завжди одразу записує в спільну пам'ять (RAM).

Код також показує, що TestAndSet дійсно містить дві операції: атомарний обмін (англ. swap) і перевірку. Тільки обмін має бути атомарним. (Це дійсно так, тому що затримка порівняння на будь-який проміжок часу не змінить результат перевірки. Після того як обмін повернув початкове значення, результат перевірки може бути визначеним, навіть якщо він не був доти обчислений.)

Реалізація взаємного виключення із test-and-set

Можна реалізувати взаємне виключення через використання інструкції так:

boolean lock = false
function Critical(){
    while TestAndSet(lock) 
        skip //продовжуємо цикл доки не отримаємо блокування
    critical section //тільки один процес може бути тут
    lock = false //звільняємо блокування після завершення критичної секції
}

В псевдо C це буде схоже на:

volatile int lock = 0;

void Critical() {
    while (TestAndSet(&lock) == 1);
    critical section //тільки один процес може бути тут
    lock = 0 //звільняємо блокування після завершення критичної секції
}

Зауважте використання зарезервованого слова volatile. У відсутності volatile, компілятор та/або ЦП(и), швидше за все, оптимізують доступ до змінної lock та/або будуть використовувати кешовані значення, тобто цей код буде помилковий.

Навпаки, присутність volatile не гарантує, що читання і записування відбудуться з/в пам'яті. Деякі компілятори використовують бар'єри пам'яті з метою гарантування, що операції будуть записані в пам'ять, але через невиразну семантику volatile в C/C++, не всі компілятори роблять це. Перевірте документацію до свого компілятора для визначення чи робить він це.

Ця функція може бути викликана багатьма процесами, але вона гарантує, що лише не більше ніж один процес буде в критичній секцій в кожен момент.

Асемблерна реалізація Test-and-Set

  
enter_region:		; Вхідна точка функції

	tsl reg, flag		; Test and Set Lock; flag загальнодоступна змінна;
						; вона копіюється в регістр reg і тоді flag автоматично встановлюється в 1.

	cmp reg, #0		; Чи дорівнював flag нулю на вході?

	jnz enter_region	; Перехід на enter_region якщо reg не нульовий; тобто,
				; flag був не нульовим на вході.

	ret			; Вихід; тобто, flag дорівнював нулю на вході. 
				; Якщо ми потрапили сюди, tsl встановить його в не нуль;
				; таким чином, ми заявили ресурс як пов'язаний із flag.

Реалізація семафорів із використанням test-and-set

Можливо використати інструкцію test-and-set для реалізації семафорів. В однопроцесорних системах цей підхід непотрібний (за винятком використання декількох процесів для доступу до одних даних); для використання семафорів, достатньо заборонити переривання перед доступом до семафора. Однак, в багатопроцесорних системах, це небажано, якщо не неможливо, заборонити переривання на всіх процесорах одночасно. Навіть з забороненими перериваннями, два або й більше процесора можуть спробувати доступитися до пам'яті семафора одночасно. В такому випадку, test-and-set інструкція може бути використана.

Посилання

• Test-and-Set [Архівовано 13 листопада 2016 у Wayback Machine.](англ.)