Lamports bagerialgoritm är en algoritm för att dela delade resurser mellan flera trådar genom ömsesidig uteslutning . Publicerad av datavetaren Leslie Lamport 1974 [1] .
En vanlig situation inom datavetenskap är när flera trådar behöver tillgång till samma resurser. Om två eller flera trådar försöker skriva till samma minnesplats, eller om en tråd försöker läsa något som ännu inte har skrivits av en annan tråd, kan datakorruption uppstå. Lamports Bakery Algorithm är en av många algoritmer för ömsesidig uteslutning som utformats för att förhindra parallella trådar från att samtidigt bo i kritiska avsnitt av koden för att eliminera risken för datakorruption.
Lamport föreslår att man överväger ett bageri med en numreringsmaskin vid ingången. Varje inkommande kund får ett nummer ett mer än den föregående. Totalräknaren visar numret på den för närvarande betjänade klienten. Alla andra kunder väntar tills de är klara med att betjäna den nuvarande kunden och resultattavlan visar nästa nummer. Efter att kunden har gjort ett köp och lämnat in sitt nummer, ökar den anställde med ett de tillåtna numren för enheten vid ingången till utfärdandet. Om kunden som gjort köpet vill köpa något igen måste han ta numret vid entrén igen och ställa sig i den allmänna kön.
Låt köparna vara de flöden som har fått nummer i från den globala variabeln.
På grund av datorarkitekturens begränsningar bör tidpunkten för utfärdande av nummer ändras något, eftersom en oklarhetssituation uppstår om två eller flera köpare (strömmar) vill ta emot ett nummer med nummer n på en gång . Om det finns flera trådar som fick numret n när de gick in i den kritiska sektionen, kommer tråden med det lägre numret i att ha högre prioritet vid servering (inträde i den kritiska sektionen).
En kritisk sektion är en kod som kräver exklusiv åtkomst till resurser och som bara kan köras av en tråd åt gången.
När en tråd vill gå in i ett kritiskt avsnitt måste den kontrollera om den kan göra det nu. Tråden måste kontrollera siffrorna n som tas emot av andra trådar och se till att den har ett lägre nummer. Om två eller flera trådar har samma n kommer tråden med det minsta i :et att gå in i den kritiska delen .
I pseudokod kan denna jämförelse för strömmarna a och b skrivas som:
(n a , i a ) < (n b , i b ),vilket motsvarar:
(n a < n b ) eller ((n a == n b ) och (i a < i b ))När en tråd avslutar sitt arbete i den kritiska delen släpper den nummer n och går in i den icke-kritiska delen.
En icke-kritisk sektion är en kod som inte har resurser som kräver exklusiv åtkomst. Detta är kod som flera trådar kan köra parallellt utan att störa varandra.
För att återgå till liknelsen är detta en del av de åtgärder som sker efter köpet genomförts. Till exempel att returnera växel till en plånbok.
I Lamports originalartikel gäller följande villkor för processen och numreringsvariabeln (inmatning, val):
I exemplet nedan kör alla trådar samma "huvud" trådfunktion . I verkliga applikationer har olika trådar ofta olika "master"-funktioner. Som i den ursprungliga artikeln, här kontrollerar trådarna sig själva innan de går in i det kritiska avsnittet. Eftersom loopvillkoret kommer att returnera false orsakar inte kontrollen någon betydande exekveringsfördröjning.
// Deklarera och initialisera värdena för globala variabler Går in i : array [ 1. . NUM_THREADS ] av bool = { false }; Antal : array [ 1. . NUM_THREADS ] av heltal = { 0 }; lås ( heltal i ) { Ange [ i ] = sant ; Tal [ i ] = 1 + max ( Tal [ 1 ], ..., Tal [ NUM_THREADS ]); Ange [ i ] = false ; för ( heltal j = 1 ; j <= NUM_THREADS ; j ++ ) { // Vänta tills tråd j får sitt nummer: while ( Skriver [ j ]) { /* gör ingenting */ } // Vänta tills alla trådar med ett lägre nummer eller med samma nummer, // men med högre prioritet, kommer att avsluta sitt arbete: while (( Number [ j ] != 0 ) && (( Number [ j ], j ) < ( Number [ i ], i ))) { /* gör ingenting */ } } } låsa upp ( heltal i ) { nummer [ i ] = 0 ; } Tråd ( heltal i ) { while ( sant ) { lås ( i ); // Kör kritisk sektion... låsa upp ( i ); // Kör icke-kritiskt avsnitt... } } Java -kodexempel AtomicIntegerArray- biljett = ny AtomicIntegerArray ( trådar ); // biljett för trådar i rad, n - antal trådar // Varje 'ticket'-element initieras till 0 AtomicIntegerArray entering = new AtomicIntegerArray ( trådar ); // 1 när tråd går in i linje // Varje 'inträdande' element initieras till 0 public void lock ( int pid ) // Tråd-ID { går in . set ( pid , 1 ); int max = 0 ; för ( int i = 0 ; i < trådar ; i ++ ) { int aktuell = biljett . få ( i ); om ( ström > max ) { max = ström ; } } biljett . set ( pid , 1 + max ); går in . set ( pid , 0 ); for ( int i = 0 ; i < biljett . längd (); ++ i ) { om ( i != pid ) { while ( träder in . get ( i ) == 1 ) { Tråd . utbyte (); } // Vänta på att tråd i får sitt nummer while ( biljett . få ( i ) != 0 && ( biljett . få ( i ) < biljett . få ( pid ) || ( biljett . få ( i ) == biljett . få ( pid ) && i < pid ))) { Tråd . utbyte (); } } } // Kör kritisk sektion } offentlig void upplåsning ( int pid ) { biljett . set ( pid , 0 ); }Varje tråd skriver till sitt eget minne, endast en läsoperation kan utföras på delat minne. Intressant nog använder algoritmen inte atomoperationer som jämför med utbyte . Originalbeviset visar att för överlappande läsningar och skrivningar till samma cell måste endast skrivningen vara giltig. Läsoperationen kan returnera ett godtyckligt värde. Därför kan denna algoritm användas för att implementera mutexes för minne som inte har synkroniseringsprimitiver. Till exempel för en enkel SCSI- disk som används av två datorer samtidigt.
Behovet av Entering- arrayen kanske inte är uppenbart, eftersom det inte finns några lås på raderna 7 - 13 i pseudokoden. Men låt oss säga att vi tar bort den arrayen och två trådar beräknar samma Number[i] -värde . Sedan, om tråden med högre prioritet var förebyggd före beräkningen av Number[i] , kommer tråden med lägre prioritet att se att den första processen har Number[i] = 0 och gå in i det kritiska avsnittet. Sedan kommer den första, högre prioriterade processen att ignorera nummermatchningen Number[i] och även gå in i den kritiska delen. Som ett resultat kommer två processer att exekvera det kritiska avsnittet samtidigt. Inmatning behövs för att utföra operationen på rad 6 som atomär. Process i kommer aldrig att se Number[j] = 0 när process j är på väg att ta samma tal som i .
När du implementerar pseudokod på ett system med enstaka uppgifter eller flera uppgifter , är det bäst att ersätta orden "gör ingenting" med ett meddelande till systemet för att omedelbart byta till nästa tråd. Denna primitiva kallas ofta avkastning .
Lamports bagerialgoritm förutsätter användningen av en sekventiellt konsekvent minnesmodell . Få, om några, språk eller flerkärniga processorer implementerar en sådan minnesmodell. Därför kräver den korrekta implementeringen av algoritmen vanligtvis införande av skydd för att förhindra omordning [2] .