Test-and-set — інструкція, що використовується в інформатиці як атомарна (тобто безперервна) операція для такої послідовності дій: запис в пам'ять і повернення старого значення.
Якщо декілька процесів можуть доступитися до одної ділянки пам'яті, і якщо процес наразі виконує test-and-set, жоден інший процес не може отримати доступ до цієї ділянки доки перший процес не завершить інструкцію. Центральні процесори можуть використовувати test-and-set інструкції запропоновані іншими електронними вузлами, такими як ; ЦП також пропонують власну 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, що він має почекати і повторити спробу згодом. Це є реалізацією або із використанням механізму у переривання. Через те, що все це відбувається на апаратних швидкостях, ЦП 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) (як показано нижче) або через інші атомарні інструкції.
При використанні 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, компілятор та/або ЦП(и), швидше за все, оптимізують доступ до змінної 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 інструкція може бути використана.
Примітки
- Herlihy, Maurice (January, 1991). (PDF). ACM Trans. Program. Lang. Syst. 13 (1): 124—149. doi:10.1145/114005.102808. Архів оригіналу (PDF) за 5 червня 2011. Процитовано 20 травня 2007.
Посилання
- Test-and-Set [ 13 листопада 2016 у Wayback Machine.](англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Test and set instrukciya sho vikoristovuyetsya v informatici yak atomarna tobto bezperervna operaciya dlya takoyi poslidovnosti dij zapis v pam yat i povernennya starogo znachennya Yaksho dekilka procesiv mozhut dostupitisya do odnoyi dilyanki pam yati i yaksho proces narazi vikonuye test and set zhoden inshij proces ne mozhe otrimati dostup do ciyeyi dilyanki doki pershij proces ne zavershit instrukciyu Centralni procesori mozhut vikoristovuvati test and set instrukciyi zaproponovani inshimi elektronnimi vuzlami takimi yak CP takozh proponuyut vlasnu test and set instrukciyu Blokuvannya mozhe buti vikonane iz vikoristannyam atomarnoyi test and set instrukciyi napriklad tak function Lock boolean lock while test and set lock 1 Proces otrimuye blokuvannya yaksho stare znachennya bulo 0 Cikl prodovzhuye vstanovlyuvati 1 doki umova ne vikonayetsya Dovedeno sho test and set maye kinceve na vidminu operaciyi compare and swap Test and set operaciya mozhe rozv yazati zadachu uzgodzhenosti bez ochikuvannya ne bilshe nizh dlya dvoh konkurentnih procesiv Svoboda vid ochikuvannya ye najsilnishoyu garantiyeyu progresu bez blokuvannya yaka poyednuye zagalnu robotu sistemi iz svobodoyu vid goloduvannya Algoritm ye vilnim vid ochikuvannya yaksho kozhna operaciya maye obmezhenu kilkist krokiv yaki zrobit algoritm do togo yak vona zavershitsya Realizaciya na rivni aparatnogo zabezpechennyaDPRAM test and set instrukciya mozhe buti vikonuvatis bagatma shlyahami Tut navedemo dvi obidvi opisuyut DPRAM yakij maye 2 porti sho dozvolyaye 2 okremim elektronnim vuzlam takim yak 2 centralnih procesori dostupatisya do kozhnoyi komirki pam yati na DPRAM Sposib 1 Koli CP 1 zapuskaye instrukciyu test and set DPRAM spochatku robit vnutrishnyu notatku pro ce shlyahom zberezhennya adresi v pam yati v specialnomu misci Yaksho v cej moment CP 2 namagayetsya vikonati test and set instrukciyu dlya togo zh miscya v pam yati DPRAM spochatku pereviryaye svoyu vnutrishnyu notatku rozpiznaye situaciyu i produkuye BUSY pererivannya yake kazhe CP 2 sho vin maye pochekati i povtoriti sprobu zgodom Ce ye realizaciyeyu abo iz vikoristannyam mehanizmu u pererivannya Cherez te sho vse ce vidbuvayetsya na aparatnih shvidkostyah CP 2 ochikuye duzhe malo Namagavsya chi ni CP 2 dostupitisya do pam yati DPRAM vikonuye perevirku zavdanu CP 1 Yaksho perevirka uspishna DPRAM vstanovlyuye komirku pam yati znachennyam zadanim CP 1 Todi DPRAM stiraye svoyu vnutrishnyu notatku V cej moment CP 2 mozhe zapustiti vikonannya instrukciyi test and set yaka uspishno vikonayetsya Sposib 2 CP 1 zapuskaye instrukciyu test and set dlya zapisu miscya pam yati A DPRAM ne zberigaye znachennya A natomist odnochasno zapisuye potochne znachennya v specialnij registr i vstanovlyuye vmist pam yati A v specialne znachennya praporec Yaksho v cej moment CP 2 zapuskaye test and set dlya A DPRAM viyavlyaye specialnij praporec i yak i v Sposobi 1 sprichinyaye BUSY pererivannya Namagavsya chi ni CP 2 dostupitisya do pam yati DPRAM vikonuye perevirku zavdanu CP 1 Yaksho perevirka uspishna DPRAM vstanovlyuye komirku pam yati A znachennyam zadanim CP 1 Yaksho test provalyuyetsya DPRAM kopiyuye znachennya zi specialnogo registra v pam yat A Obidvi operaciyi zatirayut praporec Teper CP 2 mozhe uspishno vikonati svoyu test and set Realizaciya na rivni programnogo zabezpechennyaBagato procesoriv mayut atomarnu test and set instrukciyu na mashinnij movi Ce ti yaki ne mozhut realizuvati atomarnu test and set iz vikoristannyam atomarnogo obminu angl swap yak pokazano nizhche abo cherez inshi atomarni instrukciyi Pri vikoristanni test and set instrukciya povodyatsya podibno do nastupnoyi funkciyi Virishalnim momentom ye atomarnist vikonannya zhoden proces ne mozhe perervati funkciyu posered vikonannya i takim chinom pobachiti stan yakij vinikaye pid chas vikonannya funkciyi Nastupnij kod sluguye lishe dlya poyasnennya povedinki test and set atomarnist vimagaye yavnoyi pidtrimki na aparatnomu rivni sho unemozhlivlyuyu realizaciyu u viglyadi prostoyi funkciyi Zauvazhennya V comu prikladi prisvoyennya initial stvoryuye nove znachennya ne prosto kopiyuye posilannya function TestAndSet boolean lock boolean initial lock lock true return initial Poperednij vidtinok kodu ne ye atomarnim v sensi test and set instrukciyi Vin takozh vidriznyayetsya vid aparatnogo DPRAM test and set tim sho tut vstanovlyuvane znachennya i test nezminni i vstanovlennya vidbuvayetsya nezalezhno vid rezultatu prohodzhennya testu todi yak v opisi DPRAM test and set zapis vidbuvayetsya lishe po uspishnomu prohodzhennyu testu i vstanovlyuvane znachennya i umovi testu viznachayutsya CP Tut znachennyam dlya vstanovlennya mozhe buti lishe 1 ale yaksho lishe 0 ta 1 viznacheni mozhlivimi znachennyami dlya komirki pam yati i perevirka na nenulove znachennya yedina dozvolena todi ce rivnocinno vipadku opisanomu dlya DPRAM abo bilsh tochno dlya vipadku DPRAM zmenshenomu cimi obmezhennyami Z ciyeyi tochki zoru cej variant virno mozhe buti nazvana test and set v povnomu rozuminni cogo terminu Golovnim momentom dlya zauvazhennya yakij vtilyuye cya funkciya ce meta i princip instrukciyi test and set tobto obidvi diyi z perevirki i vstanovlennya vikonuyutsya v odnij atomarnij operaciyi takim chinom zhoden inshij potik programi ne v zmozi sprichiniti zminu zadiyanoyi komirki pam yati pislya togo yak vidbulas perevirka ale znachennya she ne vstanovlene sho porushilo b logichnu vimogu na te sho pam yat bude vstanovlena vinyatkovo u vipadku yaksho vona mistit pevne znachennya Ce ye virishalnim chinnikom na vidminu vid pidhodu koli vona neshodavno mistila ce znachennya V C realizaciya mozhe buti takoyu define LOCKED 1 int TestAndSet int lockPtr int oldValue oldValue SwapAtomic lockPtr LOCKED return oldValue LOCKED de SwapAtomic atomarno spochatku chitaye potochne znachennya na yake vkazuye lockPtr i todi zapisuye tudi 1 Spravdi atomarna SwapAtomic nikoli ne vikoristovuye keshovani znachennya i zavzhdi odrazu zapisuye v spilnu pam yat RAM Kod takozh pokazuye sho TestAndSet dijsno mistit dvi operaciyi atomarnij obmin angl swap i perevirku Tilki obmin maye buti atomarnim Ce dijsno tak tomu sho zatrimka porivnyannya na bud yakij promizhok chasu ne zminit rezultat perevirki Pislya togo yak obmin povernuv pochatkove znachennya rezultat perevirki mozhe buti viznachenim navit yaksho vin ne buv doti obchislenij Realizaciya vzayemnogo viklyuchennya iz test and setMozhna realizuvati vzayemne viklyuchennya cherez vikoristannya instrukciyi tak boolean lock false function Critical while TestAndSet lock skip prodovzhuyemo cikl doki ne otrimayemo blokuvannya critical section tilki odin proces mozhe buti tut lock false zvilnyayemo blokuvannya pislya zavershennya kritichnoyi sekciyi V psevdo C ce bude shozhe na volatile int lock 0 void Critical while TestAndSet amp lock 1 critical section tilki odin proces mozhe buti tut lock 0 zvilnyayemo blokuvannya pislya zavershennya kritichnoyi sekciyi Zauvazhte vikoristannya zarezervovanogo slova U vidsutnosti volatile kompilyator ta abo CP i shvidshe za vse optimizuyut dostup do zminnoyi lock ta abo budut vikoristovuvati keshovani znachennya tobto cej kod bude pomilkovij Navpaki prisutnist volatile ne garantuye sho chitannya i zapisuvannya vidbudutsya z v pam yati Deyaki kompilyatori vikoristovuyut bar yeri pam yati z metoyu garantuvannya sho operaciyi budut zapisani v pam yat ale cherez neviraznu semantiku volatile v C C ne vsi kompilyatori roblyat ce Perevirte dokumentaciyu do svogo kompilyatora dlya viznachennya chi robit vin ce Cya funkciya mozhe buti viklikana bagatma procesami ale vona garantuye sho lishe ne bilshe nizh odin proces bude v kritichnij sekcij v kozhen moment Asemblerna realizaciya Test and Setenter region Vhidna tochka funkciyi tsl reg flag Test and Set Lock flag zagalnodostupna zminna vona kopiyuyetsya v registr reg i todi flag avtomatichno vstanovlyuyetsya v 1 cmp reg 0 Chi dorivnyuvav flag nulyu na vhodi jnz enter region Perehid na enter region yaksho reg ne nulovij tobto flag buv ne nulovim na vhodi ret Vihid tobto flag dorivnyuvav nulyu na vhodi Yaksho mi potrapili syudi tsl vstanovit jogo v ne nul takim chinom mi zayavili resurs yak pov yazanij iz flag Realizaciya semaforiv iz vikoristannyam test and setMozhlivo vikoristati instrukciyu test and set dlya realizaciyi semaforiv V odnoprocesornih sistemah cej pidhid nepotribnij za vinyatkom vikoristannya dekilkoh procesiv dlya dostupu do odnih danih dlya vikoristannya semaforiv dostatno zaboroniti pererivannya pered dostupom do semafora Odnak v bagatoprocesornih sistemah ce nebazhano yaksho ne nemozhlivo zaboroniti pererivannya na vsih procesorah odnochasno Navit z zaboronenimi pererivannyami dva abo j bilshe procesora mozhut sprobuvati dostupitisya do pam yati semafora odnochasno V takomu vipadku test and set instrukciya mozhe buti vikoristana PrimitkiHerlihy Maurice January 1991 PDF ACM Trans Program Lang Syst 13 1 124 149 doi 10 1145 114005 102808 Arhiv originalu PDF za 5 chervnya 2011 Procitovano 20 travnya 2007 PosilannyaTest and Set 13 listopada 2016 u Wayback Machine angl