Алгоритм Пітерсона, також відомий як розв'язок Пітерсона (англ. Peterson's algorithm, Peterson's solution) алгоритм паралельного програмування для взаємного виключення, який дозволяє двом процесам спільно використовувати одновикористовний ресурс без конфліктів, застосовуючи лише спільну пам'ять для зв'язку. Сформульовано Гарі Л. Пітерсоном 1981 року. Хоча у початковому формулюванні алгоритм Пітерсона працює лише з двома процесами, його можна узагальнити на декілька процесів.
Алгоритм
flag[0] = 0; flag[1] = 0; turn; P0: flag[0] = 1; P1: flag[1] = 1; turn = 1; turn = 0; while (flag[1] == 1 && turn == 1) while (flag[0] == 1 && turn == 0) { { // очікуваня // очікування } } // критична секція // критична секція ... ... // кінець критичної секції // кінець критичної секції flag[0] = 0; flag[1] = 0;
Алгоритм має дві змінні flag і turn. Якщо flag встановлений в 1, то процес намагається увійти до критичної секції. Вхід до критичної секції надається процесу P0, якщо P1 не намагається увійти до своєї критичної секції або P1 надав пріоритет P0 встановленням turn в 0.
Алгоритм задовільняє трьом головним критеріям розв'язку задачі критичної секції:
- Взаємне виключення
- Прогрес
- Обмежене очікування
Взаємне виключення
Процеси не можуть перебувати в критичній секції одночасно: якщо P0 у своїй критичній секції, тоді flag[0] дорівнює 1 і:
- або flag[1] дорівнює 0 (значить P1 вже завершив свою критичну секцію)
- або turn дорівнює 0 (значить P1 намагається увійти до критичної секції, але змушений очікувати).
В обох випадках, P1 не може перебувати в своїй критичній секції.
Прогрес
Прогрес визначається таким чином: якщо жоден процес не виконує свою критичну секцію і деякі процеси намагаються увійти до своєї критичної секції, тоді лише ці процеси враховуються під час прийняття рішення, хто з них увійде до критичної секції наступним. Це рішення не може відкладатися необмежено. Процес не може увійти до критичної секції одразу після виходу з неї, якщо інший процес вже встановив свій прапорець, висловивши цим своє бажання також увійти до критичної секції.
Обмежене очікування
Обмежене очікування означає, що «після здійснення будь-яким процесом запиту на вхід до критичної секції і до того, як цей запит буде задоволено, обмежується кількість входів до критичної секції, дозволених іншим процесам». В алгоритмі Пітерсона процес очікуватиме входу до критичної секції не довше, ніж один вхід іншого процесу.
Зауваження
У випадку роботи на апаратному рівні, алгоритм Пітерсона зазвичай не потребує атомарного доступу. Деякі процесори мають особливі команди, такі як test-and-set або compare-and-swap, які, шляхом блокування шини пам'яті, може бути застосовано для забезпечення взаємного виключення в SMP системах.
Примітки
- G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116
- As discussed in Operating Systems Review, January 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).
- Silberschatz. Operating Systems Concepts: Seventh Edition. John Wiley and Sons, 2005., Pages 194
Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Це незавершена стаття про програмування. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Pitersona takozh vidomij yak rozv yazok Pitersona angl Peterson s algorithm Peterson s solution algoritm paralelnogo programuvannya dlya vzayemnogo viklyuchennya yakij dozvolyaye dvom procesam spilno vikoristovuvati odnovikoristovnij resurs bez konfliktiv zastosovuyuchi lishe spilnu pam yat dlya zv yazku Sformulovano Gari L Pitersonom 1981 roku Hocha u pochatkovomu formulyuvanni algoritm Pitersona pracyuye lishe z dvoma procesami jogo mozhna uzagalniti na dekilka procesiv Algoritmflag 0 0 flag 1 0 turn P0 flag 0 1 P1 flag 1 1 turn 1 turn 0 while flag 1 1 amp amp turn 1 while flag 0 1 amp amp turn 0 ochikuvanya ochikuvannya kritichna sekciya kritichna sekciya kinec kritichnoyi sekciyi kinec kritichnoyi sekciyi flag 0 0 flag 1 0 Algoritm maye dvi zminni flag i turn Yaksho flag vstanovlenij v 1 to proces namagayetsya uvijti do kritichnoyi sekciyi Vhid do kritichnoyi sekciyi nadayetsya procesu P0 yaksho P1 ne namagayetsya uvijti do svoyeyi kritichnoyi sekciyi abo P1 nadav prioritet P0 vstanovlennyam turn v 0 Algoritm zadovilnyaye trom golovnim kriteriyam rozv yazku zadachi kritichnoyi sekciyi Vzayemne viklyuchennya Progres Obmezhene ochikuvannya Vzayemne viklyuchennya Procesi ne mozhut perebuvati v kritichnij sekciyi odnochasno yaksho P0 u svoyij kritichnij sekciyi todi flag 0 dorivnyuye 1 i abo flag 1 dorivnyuye 0 znachit P1 vzhe zavershiv svoyu kritichnu sekciyu abo turn dorivnyuye 0 znachit P1 namagayetsya uvijti do kritichnoyi sekciyi ale zmushenij ochikuvati V oboh vipadkah P1 ne mozhe perebuvati v svoyij kritichnij sekciyi Progres Progres viznachayetsya takim chinom yaksho zhoden proces ne vikonuye svoyu kritichnu sekciyu i deyaki procesi namagayutsya uvijti do svoyeyi kritichnoyi sekciyi todi lishe ci procesi vrahovuyutsya pid chas prijnyattya rishennya hto z nih uvijde do kritichnoyi sekciyi nastupnim Ce rishennya ne mozhe vidkladatisya neobmezheno Proces ne mozhe uvijti do kritichnoyi sekciyi odrazu pislya vihodu z neyi yaksho inshij proces vzhe vstanoviv svij praporec vislovivshi cim svoye bazhannya takozh uvijti do kritichnoyi sekciyi Obmezhene ochikuvannya Obmezhene ochikuvannya oznachaye sho pislya zdijsnennya bud yakim procesom zapitu na vhid do kritichnoyi sekciyi i do togo yak cej zapit bude zadovoleno obmezhuyetsya kilkist vhodiv do kritichnoyi sekciyi dozvolenih inshim procesam V algoritmi Pitersona proces ochikuvatime vhodu do kritichnoyi sekciyi ne dovshe nizh odin vhid inshogo procesu ZauvazhennyaU vipadku roboti na aparatnomu rivni algoritm Pitersona zazvichaj ne potrebuye atomarnogo dostupu Deyaki procesori mayut osoblivi komandi taki yak test and set abo compare and swap yaki shlyahom blokuvannya shini pam yati mozhe buti zastosovano dlya zabezpechennya vzayemnogo viklyuchennya v SMP sistemah PrimitkiG L Peterson Myths About the Mutual Exclusion Problem Information Processing Letters 12 3 1981 115 116 As discussed in Operating Systems Review January 1990 Proof of a Mutual Exclusion Algorithm M Hofri Silberschatz Operating Systems Concepts Seventh Edition John Wiley and Sons 2005 Pages 194 Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Ce nezavershena stattya pro programuvannya Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi