Gjensidig Utelukkelse-Mutex, Låser, Peterson Algoritme, Avgrenset Venter Og Bakeri Algoritme.

author
8 minutes, 3 seconds Read

Vurder denne kodebiten.

public long getAndIncrement() {
temp = value; #Line-1
value = temp + 1; #Line-2
return temp;
}

la oss anta at to Tråder A og B får tilgang til denne getAndIncrement () – metoden samtidig.Gitt nedenfor er en mulig utførelsesflyt av disse to trådene

Sequence 1
Thread-A temp = value temp = 0, value = 0
Thread-A value = temp + 1 temp = 0, value = 1
Thread-B temp = value temp = 1, value = 0
Thread-B value = temp + 1 temp = 1, value = 2

la oss vurdere en annen utførelsessekvens.

Sequence 2
Thread-A temp = value temp = 0, value = 0
Thread-B temp = value temp = 0, value = 0
Thread-A value = temp + 1 temp = 0, value = 1
Thread-B value = temp + 1 temp = 0, value = 1

Dermed i å utføre ikke-atomkodeblokker for å opprettholde konsistens av variabler, må vi binde prosessen til en bestemt tråd og ikke tillate andre tråder å endre . Delen av koden som må isoleres og utføres av en enkelt tråd for å opprettholde denne typen konsistens er Kjent Som Kritisk seksjon.

dette konseptet brukes i samtidig programmering med en kritisk seksjon, et stykke kode der prosesser eller tråder får tilgang til en delt ressurs. Bare en tråd eier Mutex (Mutex) Om gangen, og dermed opprettes en mutex med et unikt navn når et program starter. Når en tråd har en ressurs, må den låse mutex fra andre tråder for å hindre samtidig tilgang til ressursen. Ved å frigjøre ressursen låser tråden mutexen.

For Å oppnå Gjensidig utelukkelse vil vi bruke låser .Bruk gjensidig utelukkelseslås til å serialisere trådutførelse. Gjensidig utelukkelse låser synkronisere tråder, vanligvis ved å sikre at bare en tråd om gangen utfører en kritisk del av koden. Mutex låser kan også bevare single-threaded kode.

en lås skal være,

  • Opprettholde Gjensidig utelukkelse mellom tråder.
  • Vranglås Gratis
  • Sult Gratis

en lås vil Være Sult Gratis →Vranglås Gratis . Så for å evaluere en lås må vi sjekke om det er gjensidig utelukkende, så om det er dødlåsfritt eller ikke, og så om det er sultfritt eller ikke.

Enkel Lås

class SimpleLock implements Lock { private volatile boolean flag; public void lock() {
while (flag == true) { } #Line-1
flag = true; #Line-2
} public void unlock() {
flag = false;
}

la oss si at to tråder (Tråd A Og Tråd B) utfører denne kodeblokken .

Anta a utfore forst .Det går inn i låsemetoden, sjekk for verdien av flagg I Linje-1 og det infers det som falsk.

Kontekstbryter skjer på dette punktet Og B utfører neste. Det går inn i låsemetoden, sjekk for verdien av flagg I Linje-1 og det infers det som falsk. Deretter utfører Den Linje-2 og går inn i den kritiske regionen.

Nå igjen a utfører og pekeren For Tråd A er På Linje-2 (som Den allerede utført Linje-1) og den går også inn i det kritiske området.

Her Opprettholdes Ikke Gjensidig utelukkelse for de 2 trådene A og B, da begge har tilgang til det kritiske området samtidig..

Lås En

class LockOne implements Lock { private volatile boolean flag = new boolean; #Line-1 public void lock() {
flag = true; #Line-2
while (flag) {} #Line-3
} public void unlock() {
flag = false; #Line-4
}

La oss si at to tråder (Tråd A Og Tråd B) utfører denne kodeblokken som ovenfor . Her i stedet for ett boolsk flagg har vi to flagg for hver tråd.(Linje-1)

Anta at En utfører først. den går inn i låsemetoden, tilordner verdien av ‘true’ til flagget I Linje-2, kontroller verdien av flagget til annen Tråd i Linje-3, og den utleder den som falsk.Dermed går det inn i den kritiske regionen.

deretter utfører B.Den går inn i låsemetoden, tilordner verdien av «sann» til flagget I Linje-2, kontroller verdien av flagget til annen Tråd i Linje-3, og det utleder det som «sant» Som Allerede Tråd a endret det verdi til «sant». Så b går inn i løkken og venter på at Flagget Av Tråd B blir falskt for å komme seg ut fra mens sløyfen.

Etter å ha fullført den kritiske delen Tråden a utfører unlock metoden tilordne verdien av «false» til flagget og utganger. Nå mens sløyfetilstanden Til Tråden B blir falsk Og b går Ut Av Løkken og går inn i den kritiske regionen.

Dermed Gjensidig utelukkelse håndteres riktig i denne låsen.

nå kan vi vurdere dette scenariet.

STEP-1-Anta at en utfører først. den går inn i låsemetoden, tilordne verdien av ‘true’ til flagget I Linje-2, kontekstveksling skjer og den venter .

TRINN-2-Deretter utfører B. den går inn i låsemetoden, tilordner verdien av ‘true’ til flagget I Linje-2, kontekstveksling skjer og den venter.

TRINN-3 – Nå utfører A Igjen, og nå er pekeren Til A På Linje 3 og den sjekker for verdien av flagget til annen Tråd I Linje-3, og den utleder den som «sann» (PÅ GRUNN AV TRINN-2). Dermed går det inn i mens sløyfen.

TRINN-4-Nå igjen b utfører og nå pekeren Av B er På Linje 3 og den sjekker for verdien av flagget til andre Tråden I Linje-3 og det infers det som «sant» (PÅ GRUNN AV TRINN-1). Dermed går det inn i mens sløyfen.

nå er begge trådene i mens løkken venter på hverandre for å bli utgitt.Dette er en fastlåst tilstand.

Lås To

public class LockTwo implements Lock { private volatile int victim; #Line-1 public void lock() {
victim = i; #Line-2
while (victim == i) { #Line-3
}; #Line-3
}
public void unlock() {}}

Hvis Tråd B er i kritisk seksjon, Er A offeret Og Omvendt.Dermed LockTwo tilfredsstiller Gjensidig utelukkelse.

Hvis begge trådene Er Offer, vil De sløyfe inne i mens sløyfen På Linje–3 og skape en dødlås. Men Her kan Bare En av tråden Være Et Offer. Hvis A Er Et Offer, vil det sløyfe inne i mens sløyfen På Linje-3 og Når B tilordner det selv som Et Offer, vil a bryte sløyfen og gå inn i det kritiske Området.Dermed er denne låsen dødlås Fri.

La oss si at bare en tråd utfører denne kodeblokken .Det vil sløyfe inne i mens sløyfen for alltid uten å ha noen tråder for å frigjøre den. Det vil sulte for å utføre CS.Dermed er denne låsen ikke sultfri.

Peterson Algoritme

public void lock() { 
flag = true;
victim= i;
while (flag && victim == i) {};
}public void unlock() {
flag = false;
}

dette vil eliminere alle ulemper som vi har sett i tidligere låser. Det vil gi gjensidig utelukkelse uten Dødlås og sult.

det eliminerer sulten Av LockTwo . Hvis bare en tråd utfører dette, vil den utføre denne blokken uten sult.

Bounded Waiting Concept

Sult-frihet garanterer at hver tråd som kaller lås () til slutt går inn i kritisk seksjon.Men det er ingen garantier om hvor lenge det vil take.So for å Opprettholde Denne Rettferdigheten vil vi anta at Hvis a kaller lås () før B, bør A gå inn i kritisk seksjon Før B .

vi analyserer låsen ved å dele den i to deler

  • d-Døråpning
  • w-Venter seksjon
public void lock() { #Doorway Section
flag = true;
victim= i; #Waiting Section
while (flag && victim == i) {};
}

r-Begrenset Venter

la anta At A og B utfører låsen Og a har tilgang Til D (Døråpningsseksjon) på n – th tid og B har tilgang Til D på m – th tid hvor n > m. Og A ‘S N-Th Døråpning gikk foran B’ s m-th Døråpning.

Dermed Er A ‘s n-th kritiske seksjon foran B’ s (m + r)-th kritiske seksjon.Det betyr At B ikke kan overta A med mer enn r ganger.

førstemann til mølla betyr r = 0 . En lås er først til mølla hvis, Når, Tråd a fullfører sin døråpning før tråd B starter sin døråpning,
Da a ikke kan overkjøres Av B.

Bakerialgoritme

Bakerialgoritmen er en av de enkleste kjente løsningene på gjensidig utelukkelsesproblemet For det generelle tilfellet Av n-prosess. Bakeri Algoritme er en kritisk seksjon løsning For n prosesser. Algoritmen bevarer først til mølla eiendom.

Leksikografisk rekkefølge I Bakeri Algoritme betyr, (a, i) < (b, j) , hvis a < b, eller a = b og i < j

class Bakery implements Lock {
volatile boolean flag;
volatile Label label;
public Bakery (int n) {
flag = new boolean;
label = new Label;
for (int i = 0; i < n; i++) {
flag = false; label = 0;
}
}
public void lock(){ #Doorway Section
flag = true; #Line1
label = max(label,label,......label)+1; #Line2 #Waiting Section
while(there exists k flag && (label,i) > (label,k)){
}
}
public void unlock() {
flag = false;
}}

I Bakeri() metode tilordner vi Et Boolsk flagg og en etikettverdi på 0 for hvert ‘ n ‘ antall tråder.

for hver tråd som har tilgang til låsemetoden, tilordner vi true til flagget og gjør etikettverdien som maksimum ved å øke maks for alle tilgjengelige etiketter med 1.

(label,i) > (label,k)

Men Her Er Linje -2 ikke atomisk. så to Tråder kan samtidig utføre Linje-2 og få samme etikettverdi. Etikett = etikett. I dette scenariet må vi favorisere prosessen som kom inn i døråpningen først og la den prosessen gå inn i den kritiske delen. Så det vil sjekke Iden Til Tråden og la Tråden som har den minste id.

Similar Posts

Legg igjen en kommentar

Din e-postadresse vil ikke bli publisert.