A Lamport sütőipari algoritmusa a megosztott erőforrások több szál között kölcsönös kizárással történő megosztására szolgáló algoritmus . Leslie Lamport informatikus publikálta 1974-ben [1] .
A számítástechnikában gyakori helyzet az, amikor több szálnak is szüksége van ugyanahhoz az erőforráshoz. Ha két vagy több szál próbál ugyanarra a memóriahelyre írni, vagy ha az egyik szál olyasmit próbál beolvasni, amit egy másik szál még nem írt meg, adatsérülés léphet fel. A Lamport's Bakery Algorithm egyike a sok kölcsönös kizárási algoritmusnak, amelyet arra terveztek, hogy megakadályozza, hogy párhuzamos szálak egyidejűleg a kód kritikus szakaszaiban tartózkodjanak , így elkerülhető az adatsérülés veszélye.
Lamport azt javasolja, hogy fontoljanak meg egy pékséget, amelynek bejáratánál számológép található. Minden bejövő ügyfél eggyel többet kap, mint az előző. A teljes számláló az éppen kiszolgált ügyfél számát mutatja. Az összes többi ügyfél megvárja, amíg befejezi az aktuális ügyfél kiszolgálását, és az eredménytábla a következő számot mutatja. Miután az ügyfél megvásárolta és leadta a számát, az alkalmazott eggyel növeli az eszköz megengedett számát a kibocsátási bejáratnál. Ha a vásárló újra szeretne vásárolni valamit, akkor ismét fel kell vennie a számot a bejáratnál, és be kell állnia az általános sorba.
Legyenek a vásárlók azok a folyamok, amelyek a globális változóból i számokat kaptak .
A számítógép-architektúra korlátai miatt a számok kiadásának pillanatát némileg módosítani kell, mivel félreérthető helyzet adódik, ha két vagy több vásárló (stream) szeretne egy n számú számot egyszerre kapni . Ha több olyan szál is van, amely a kritikus szakaszba való belépéskor n számot kapott, akkor az alacsonyabb i számú szálnak lesz magasabb prioritása a kiszolgáláskor (a kritikus szakaszba való belépéskor).
A kritikus szakasz olyan kódrészlet, amely kizárólagos hozzáférést igényel az erőforrásokhoz, és egyszerre csak egy szál hajthatja végre.
Ha egy szál egy kritikus szakaszba akar belépni, ellenőriznie kell, hogy most megteheti-e. A szálnak ellenőriznie kell a többi szál által kapott n számokat , és meg kell győződnie arról, hogy kisebb számmal rendelkezik. Ha két vagy több szálnak ugyanaz az n értéke , akkor a legkisebb i -vel rendelkező szál kerül a kritikus szakaszba .
A pszeudokódban az a és b folyamok összehasonlítása a következőképpen írható fel:
(n a , i a ) < (n b , i b ),ami egyenértékű:
(n a < n b ) vagy ((n a == n b ) és (i a < i b ))Amikor egy szál befejezi munkáját a kritikus szakaszban, felszabadítja az n számot, és belép a nem kritikus szakaszba.
A nem kritikus szakasz olyan kódrészlet, amely nem rendelkezik kizárólagos hozzáférést igénylő erőforrásokkal. Ez egy olyan kód, amelyet több szál párhuzamosan is végrehajthat anélkül, hogy zavarná egymást.
Visszatérve az analógiához, ez a vásárlás utáni műveletek része. Például az aprópénz visszaküldése a pénztárcába.
Lamport eredeti cikkében a következő feltételek vonatkoznak a folyamatra és a számozási (beviteli, választási) változóra:
Az alábbi példában minden szál ugyanazt a "fő" szál funkciót hajtja végre . Valós alkalmazásokban a különböző szálaknak gyakran különböző "mester" funkciói vannak. Az eredeti cikkhez hasonlóan itt is a szálak ellenőrzik magukat, mielőtt belépnének a kritikus részbe. Mivel a hurokfeltétel false értéket ad vissza , az ellenőrzés nem okoz jelentős végrehajtási késést.
// Globális változók értékeinek deklarálása és inicializálása Belépés : array [ 1. . NUM_THREADS ] of bool = { false }; Szám : tömb [ 1. . NUM_THREADS ] egész szám = { 0 }; zár ( integer i ) { [ i ] = igaz ; _ Szám [ i ] = 1 + max ( Szám [ 1 ], ..., Szám [ NUM_THREADS ]); Az [ i ] beírása = false ; for ( j egész = 1 ; j <= NUM_THREADS ; j ++ ) { // Várja meg, amíg a j szál megkapja a számát: while ( [ j ] beírása ) { /* ne csinálj semmit */ } Várjon, amíg az összes szál kisebb vagy azonos számmal rendelkezik, // de magasabb prioritással befejezik a munkájukat: while (( Szám [ j ] != 0 ) && (( Szám [ j ], j ) < ( Szám [ i ], i ))) { /* ne csinálj semmit */ } } } unlock ( integer i ) { szám [ i ] = 0 ; } szál ( integer i ) { míg ( igaz ) { zár ( i ); // Kritikus szakasz végrehajtása... kinyit ( i ); // Nem kritikus szakasz végrehajtása... } } Java kód példa AtomicIntegerArray jegy = new AtomicIntegerArray ( szálak ); // jegy a sorban lévő szálakhoz, n - szálak száma // Minden 'ticket' elem 0-ra inicializálódik AtomicIntegerArray beírása = new AtomicIntegerArray ( szálak ); // 1, amikor a szál sorba lép // Minden „belépő” elem 0-ra inicializálódik public void lock ( int pid ) // Szálazonosító { belépő . halmaz ( pid , 1 ); int max = 0 ; for ( int i = 0 ; i < szálak ; i ++ ) { int áram = jegy . kap ( i ); ha ( jelenlegi > max ) { max = áram ; } } jegyet . halmaz ( pid , 1 + max ); belépő . set ( pid , 0 ); for ( int i = 0 ; i < jegy . hossza (); ++ i ) { if ( i != pid ) { while ( entering . get ( i ) == 1 ) { Thread . hozam (); } // Várja meg, amíg az i szál megkapja a számát while ( jegy . get ( i ) != 0 && ( jegy . get ( i ) < jegy . get ( pid ) || ( jegy . get ( i ) == jegy . get ( pid ) && i < pid ))) { Szál . hozam (); } } } // Kritikus szakasz végrehajtása } nyilvános void feloldás ( int pid ) { jegyet . set ( pid , 0 ); }Minden szál a saját memóriájába ír, a megosztott memórián csak olvasási művelet hajtható végre. Érdekes módon az algoritmus nem használ atomi műveleteket, például az összehasonlítást a cserével . Az eredeti bizonyíték azt mutatja, hogy átfedő olvasás és írás esetén ugyanabba a cellába csak az írásnak kell érvényesnek lennie. Az olvasási művelet tetszőleges értéket adhat vissza. Ezért ez az algoritmus használható mutexek megvalósítására olyan memóriában, amely nem rendelkezik szinkronizálási primitívekkel. Például egy egyszerű SCSI - lemezre, amelyet egyszerre két számítógép használ.
Lehet, hogy az Entering tömb szükségessége nem nyilvánvaló, mivel a pszeudokód 7-13. soraiban nincsenek zárolások. Tegyük fel azonban, hogy eltávolítjuk ezt a tömböt, és két szál ugyanazt a Szám[i] értéket számítja ki . Ezután, ha a magasabb prioritású szálat megelőzték a Szám[i] kiszámítása előtt , az alacsonyabb prioritású szál látni fogja, hogy az első folyamat Szám[i] = 0, és belép a kritikus szakaszba. Ekkor az első, magasabb prioritású folyamat figyelmen kívül hagyja a Number[i] számegyezést , és belép a kritikus szakaszba. Ennek eredményeként két folyamat egyidejűleg hajtja végre a kritikus részt. A 6. vonalon végzett művelet atomiként történő végrehajtásához be kell lépni . Az i folyamat soha nem fogja látni a Szám[j] = 0 értéket, ha a j folyamat ugyanazt a számot fogja felvenni, mint i .
Ha pszeudokódot implementál egy egyfeladatos vagy többfeladatos rendszeren, a legjobb, ha a "ne csinálj semmit" szavakat a rendszernek küldött értesítéssel helyettesíted, hogy azonnal átválthass a következő szálra. Ezt a primitívet gyakran termésnek nevezik .
A Lamport sütőipari algoritmusa szekvenciálisan konzisztens memóriamodell használatát feltételezi . Kevés nyelv vagy többmagos processzor valósít meg ilyen memóriamodellt, ha van ilyen. Ezért az algoritmus helyes megvalósításához általában védőelemek beillesztése szükséges, hogy megakadályozzák az újrarendezést [2] .