Algoritmus pekařství Lamport je algoritmus pro sdílení sdílených zdrojů mezi více vlákny vzájemným vyloučením . Publikoval počítačový vědec Leslie Lamport v roce 1974 [1] .
Běžná situace v informatice je, když více vláken potřebuje přístup ke stejným zdrojům. Pokud se dvě nebo více podprocesů pokusí zapsat do stejného paměťového místa nebo pokud se jedno podproces pokusí přečíst něco, co ještě nebylo zapsáno jiným podprocesem, může dojít k poškození dat. Lamport's Bakery Algorithm je jedním z mnoha algoritmů vzájemného vyloučení navržených tak, aby zabránil paralelním vláknům v souběžném přebývání v kritických částech kódu, aby se eliminovalo riziko poškození dat.
Lamport navrhuje zvážit pekárnu s číslovacím automatem u vchodu. Každému příchozímu zákazníkovi je přiděleno číslo o jedno více než tomu předchozímu. Celkové počítadlo ukazuje číslo aktuálně obsluhovaného klienta. Všichni ostatní zákazníci čekají, až dokončí obsluhu aktuálního zákazníka a na výsledkové tabuli se zobrazí další číslo. Poté, co zákazník provede nákup a odevzdá své číslo, pracovník navýší o jedničku povolená čísla pro zařízení na vstupu k výdeji. Pokud si zákazník, který nakoupil, bude chtít něco koupit znovu, bude muset znovu vzít číslo u vchodu a postavit se do obecné fronty.
Nechť kupujícími jsou toky, které obdržely čísla i z globální proměnné.
Vzhledem k omezením architektury počítače by měl být okamžik vydávání čísel mírně upraven, protože nejasná situace nastává, pokud dva nebo více kupujících (streamů) chtějí získat číslo s číslem n najednou . Pokud existuje několik vláken, která při vstupu do kritické sekce obdržela číslo n , vlákno s nižším číslem i bude mít při obsluze (vstupu do kritické sekce) vyšší prioritu.
Kritická sekce je část kódu, která vyžaduje výhradní přístup ke zdrojům a může být spuštěna vždy pouze jedním vláknem.
Když chce vlákno vstoupit do kritické sekce, musí zkontrolovat, zda to nyní může udělat. Vlákno musí zkontrolovat čísla n přijatá jinými vlákny a ujistit se, že má nižší číslo. Pokud mají dvě nebo více vláken stejné n , vlákno s nejmenším i vstoupí do kritické sekce .
V pseudokódu lze toto srovnání pro proudy a a b zapsat jako:
(n a , i a ) < (nb , ib ) ,což je ekvivalentní:
(n a < n b ) nebo (( na == n b ) a (i a < i b ))Když vlákno dokončí svou práci v kritické sekci, uvolní číslo n a vstoupí do nekritické sekce.
Nekritická sekce je část kódu, která nemá prostředky vyžadující výhradní přístup. Toto je kód, který může paralelně spouštět více vláken, aniž by se navzájem rušily.
Abychom se vrátili k analogii, jedná se o součást akcí, které nastanou po provedení nákupu. Například vrácení drobných do peněženky.
V původním článku Lamporta platí pro proces a proměnnou číslování (zadání, výběr) následující podmínky:
V níže uvedeném příkladu všechna vlákna provádějí stejnou "hlavní" funkci Thread . V reálných aplikacích mají různá vlákna často různé „master“ funkce. Stejně jako v původním článku, i zde se vlákna před vstupem do kritické sekce zkontrolují. Vzhledem k tomu, že podmínka smyčky vrátí hodnotu false , kontrola nezpůsobí významné zpoždění provedení.
// Deklarace a inicializace hodnot globálních proměnných Zadání : pole [ 1. . NUM_THREADS ] z bool = { false }; Číslo : pole [ 1. . NUM_THREADS ] z celého čísla = { 0 }; zámek ( celé číslo i ) { Zadání [ i ] = true ; Číslo [ i ] = 1 + max ( Číslo [ 1 ], ..., Číslo [ NUM_THREADS ]); Zadání [ i ] = false ; for ( celé číslo j = 1 ; j <= NUM_THREADS ; j ++ ) { // Počkejte, až vlákno j získá své číslo: while ( Zadání [ j ]) { /* nedělat nic */ } // Počkejte, až budou všechna vlákna s nižším číslem nebo se stejným číslem, // ale s vyšší prioritou dokončí svou práci: while (( Číslo [ j ] != 0 ) && (( Číslo [ j ], j ) < ( Číslo [ i ], i ))) { /* nedělat nic */ } } } odemknout ( celé číslo i ) { číslo [ i ] = 0 ; } Vlákno ( celé číslo i ) { zatímco ( true ) { zámek ( i ); // Provedení kritické sekce... odemknout ( i ); // Spustit nekritickou sekci... } } Příklad kódu Java AtomicIntegerArray lístek = new AtomicIntegerArray ( vlákna ); // lístek pro vlákna v řadě, n - počet vláken // Každý prvek 'ticket' je inicializován na 0 AtomicIntegerArray zadání = new AtomicIntegerArray ( vlákna ); // 1 při vstupu vlákna do řádku // Každý prvek 'zadání' je inicializován na 0 public void lock ( int pid ) // ID vlákna { vstupující . set ( pid , 1 ); int max = 0 ; for ( int i = 0 ; i < vlákna ; i ++ ) { int aktuální = lístek . dostat ( i ); if ( aktuální > max ) { max = proud ; } } lístek . set ( pid , 1 + max ); vstupující . set ( pid , 0 ); for ( int i = 0 ; i < lístek . délka (); ++ i ) { if ( i != pid ) { while ( zadání . get ( i ) == 1 ) { Vlákno . výtěžek (); } // Počkejte, až vlákno i získá své číslo while ( ticket . get ( i ) != 0 && ( ticket . get ( i ) < ticket . get ( pid ) || ( ticket . get ( i ) == ticket . get ( pid ) && i < pid ))) { Vlákno . výtěžek (); } } } // Provedení kritické sekce } veřejné odemknutí neplatné ( int pid ) { lístek . set ( pid , 0 ); }Každé vlákno zapisuje do své vlastní paměti, na sdílené paměti lze provést pouze operaci čtení. Je zajímavé, že algoritmus nepoužívá atomické operace, jako je srovnání s výměnou . Původní důkaz ukazuje, že pro překrývající se čtení a zápisy do stejné buňky musí být platný pouze zápis. Operace čtení může vrátit libovolnou hodnotu. Proto lze tento algoritmus použít k implementaci mutexů pro paměť, která nemá synchronizační primitiva. Například pro jednoduchý SCSI disk používaný dvěma počítači současně.
Potřeba pole Entering nemusí být zřejmá, protože na řádcích 7 - 13 pseudokódu nejsou žádné zámky. Řekněme však, že odstraníme toto pole a dvě vlákna vypočítají stejnou hodnotu Number[i] . Pak, pokud bylo před výpočtem Number[i] preemptováno vlákno s vyšší prioritou , vlákno s nižší prioritou uvidí, že první proces má Number[i] = 0 a vstoupí do kritické sekce. Pak bude první proces s vyšší prioritou ignorovat shodu čísla Number[i] a také vstoupí do kritické sekce. V důsledku toho dva procesy současně provedou kritickou sekci. Zadání je nutné k provedení operace na řádku 6 jako atomic. Proces i nikdy neuvidí Číslo[j] = 0, když proces j bude mít stejné číslo jako i .
Při implementaci pseudokódu na jednoúlohovém nebo multitaskingovém systému je nejlepší nahradit slova „nedělat nic“ upozorněním do systému, aby se okamžitě přepnul na další vlákno. Tomuto primitivu se často říká výnos .
Lamportův pekařský algoritmus předpokládá použití sekvenčně konzistentního paměťového modelu . Jen málo jazyků nebo vícejádrových procesorů, pokud vůbec nějaké, implementuje takový model paměti. Správná implementace algoritmu proto obvykle vyžaduje vložení chráničů, aby se zabránilo přeuspořádání [2] .