Lamports bagerialgoritme er en algoritme til deling af delte ressourcer mellem flere tråde ved gensidig udelukkelse . Udgivet af datalogen Leslie Lamport i 1974 [1] .
En almindelig situation inden for datalogi er, når flere tråde har brug for adgang til de samme ressourcer. Hvis to eller flere tråde forsøger at skrive til den samme hukommelsesplacering, eller hvis en tråd forsøger at læse noget, der endnu ikke er skrevet af en anden tråd, kan der opstå datakorruption. Lamports Bakery Algorithm er en af mange gensidige udelukkelsesalgoritmer designet til at forhindre parallelle tråde i samtidig at opholde sig i kritiske dele af koden for at eliminere risikoen for datakorruption.
Lamport foreslår at overveje et bageri med en nummereringsmaskine ved indgangen. Hver indkommende kunde får et nummer et mere end den forrige. Den samlede tæller viser nummeret på den aktuelt betjente klient. Alle andre kunder venter, indtil de er færdige med at betjene den nuværende kunde, og resultattavlen viser det næste tal. Efter at kunden har foretaget et køb og afleveret sit nummer, øger medarbejderen de tilladte tal for enheden med ét ved indgangen til udstedelse. Hvis kunden, der har foretaget købet, ønsker at købe noget igen, skal han tage nummeret ved indgangen igen og stille sig i den generelle kø.
Lad køberne være de strømme, der har modtaget tal i fra den globale variabel.
På grund af computerarkitekturens begrænsninger bør tidspunktet for udstedelse af numre ændres lidt, da der opstår en uklarhedssituation, hvis to eller flere købere (streams) ønsker at modtage et nummer med nummer n på én gang . Hvis der er flere tråde, der modtog nummeret n , når de gik ind i den kritiske sektion, vil tråden med det lavere tal i have en højere prioritet ved servering (indtastning af den kritiske sektion).
En kritisk sektion er et stykke kode, der kræver eksklusiv adgang til ressourcer og kun kan udføres af én tråd ad gangen.
Når en tråd vil ind i en kritisk sektion, skal den tjekke om den kan gøre det nu. Tråden skal kontrollere numrene n modtaget af andre tråde og sikre sig, at den har et lavere tal. Hvis to eller flere tråde har samme n , går tråden med det mindste i ind i det kritiske afsnit .
I pseudokode kan denne sammenligning for strømme a og b skrives som:
(n a , i a ) < (n b , i b ),hvilket svarer til:
(n a < n b ) eller ((n a == n b ) og (i a < i b ))Når en tråd afslutter sit arbejde i den kritiske sektion, frigiver den nummer n og går ind i den ikke-kritiske sektion.
En ikke-kritisk sektion er et stykke kode, der ikke har ressourcer, der kræver eksklusiv adgang. Dette er kode, som flere tråde kan udføre parallelt uden at forstyrre hinanden.
For at vende tilbage til analogien er dette en del af de handlinger, der sker efter købet er foretaget. For eksempel returnering af vekslepenge til en tegnebog.
I Lamports originale artikel gælder følgende betingelser for processen og nummereringsvariablen (indtastning, valg):
I eksemplet nedenfor udfører alle tråde den samme "hoved" trådfunktion . I rigtige applikationer har forskellige tråde ofte forskellige "master"-funktioner. Som i den originale artikel, her tjekker trådene sig selv, inden de går ind i det kritiske afsnit. Da sløjfebetingelsen vil returnere falsk , forårsager kontrollen ikke en væsentlig udførelsesforsinkelse.
// Erklæring og initialisering af værdierne af globale variabler Indtastning : array [ 1. . NUM_THREADS ] af bool = { false }; Antal : array [ 1. . NUM_THREADS ] af heltal = { 0 }; lås ( heltal i ) { Indtastning af [ i ] = sand ; Tal [ i ] = 1 + maks ( tal [ 1 ], ..., tal [ NUM_THREADS ]); Indtastning af [ i ] = falsk ; for ( heltal j = 1 ; j <= NUM_THREADS ; j ++ ) { // Vent på tråd j for at få sit nummer: while ( Indtastning af [ j ]) { /* do nothing */ } // Vent indtil alle tråde med et lavere nummer eller med det samme nummer, // men med en højere prioritet, vil afslutte deres arbejde: while (( Tal [ j ] != 0 ) && (( Tal [ j ], j ) < ( Tal [ i ], i ))) { /* gør ingenting */ } } } unlock ( heltal i ) { tal [ i ] = 0 ; } Tråd ( heltal i ) { mens ( sand ) { lås ( i ); // Udfør kritisk sektion... låse op ( i ); // Udfør ikke-kritisk sektion... } } Java -kode eksempel AtomicIntegerArray- billet = ny AtomicIntegerArray ( tråde ); // billet for tråde på linje, n - antal tråde // Hvert 'billet'-element initialiseres til 0 AtomicIntegerArray entering = new AtomicIntegerArray ( tråde ); // 1 når tråden går ind i linjen // Hvert 'indtastende' element initialiseres til 0 public void lock ( int pid ) // Tråd ID { ind . sæt ( pid , 1 ); int max = 0 ; for ( int i = 0 ; i < tråde ; i ++ ) { int nuværende = billet . få ( i ); hvis ( aktuel > maks .) { max = strøm ; } } billet . sæt ( pid , 1 + max ); ind . sæt ( pid , 0 ); for ( int i = 0 ; i < billet . længde (); ++ i ) { hvis ( i != pid ) { while ( indtastning af . get ( i ) == 1 ) { Tråd . udbytte (); } // Vent på tråd i at få sit nummer while ( billet . få ( i ) != 0 && ( billet . få ( i ) < billet . få ( pid ) || ( billet . få ( i ) == billet . få ( pid ) && i < pid ))) { Tråd . udbytte (); } } } // Udfør kritisk sektion } offentlig ugyldig oplåsning ( int pid ) { billet . sæt ( pid , 0 ); }Hver tråd skriver til sin egen hukommelse, kun en læseoperation kan udføres på delt hukommelse. Interessant nok bruger algoritmen ikke atomoperationer, såsom sammenligning med udveksling . Det originale bevis viser, at for overlappende læsninger og skrivninger til den samme celle, skal kun skrivningen være gyldig. Læseoperationen kan returnere en vilkårlig værdi. Derfor kan denne algoritme bruges til at implementere mutexes til hukommelse, der ikke har synkroniseringsprimitiver. For eksempel for en simpel SCSI -disk, der bruges af to computere på samme tid.
Behovet for Entering -arrayet er måske ikke indlysende, da der ikke er nogen låse på linje 7 - 13 i pseudokoden. Lad os dog sige, at vi fjerner det array, og to tråde beregner den samme Number[i] -værdi . Hvis tråden med højere prioritet derefter blev foregrebet før beregning af Number[i] , vil tråden med lavere prioritet se, at den første proces har Number[i] = 0 og gå ind i den kritiske sektion. Så vil den første, højere prioritet proces ignorere nummeret match Number[i] og også gå ind i den kritiske sektion. Som et resultat vil to processer samtidigt udføre den kritiske sektion. Indtastning er nødvendig for at udføre operationen på linje 6 som atom. Proces i vil aldrig se Tal[j] = 0, når proces j er ved at tage det samme tal som i .
Når du implementerer pseudokode på et enkelt- eller multitasking - system, er det bedst at erstatte ordene "gør ingenting" med en meddelelse til systemet for straks at skifte til næste tråd. Denne primitive kaldes ofte udbytte .
Lamports bagerialgoritme forudsætter brugen af en sekventielt konsistent hukommelsesmodel . Få, hvis nogen, sprog eller multi-core processorer implementerer en sådan hukommelsesmodel. Derfor kræver den korrekte implementering af algoritmen normalt indsættelse af vagter for at forhindre genbestilling [2] .