vzájemné vyloučení-mutex, zámky, Petersonův algoritmus, bounded Waiting a Bakery algoritmus.

author
8 minutes, 18 seconds Read

zvažte tento úryvek kódu.

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

umožňuje předpokládat dvě vlákna a A B přístup k této metodě getAndIncrement () současně.Níže je uveden možný tok provádění těmito dvěma vlákny

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

umožňuje zvážit další sekvenci provádění.

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

při provádění bloků bez atomového kódu, abychom zachovali konzistenci proměnných, musíme proces vázat na konkrétní vlákno a neumožnit další vlákna modifikovat . Část kódu, která musí být izolována a provedena jediným vláknem, aby se zachoval tento typ konzistence, je známá jako kritická sekce.

tento koncept se používá v souběžném programování s kritickou sekcí, kusem kódu, ve kterém procesy nebo vlákna přistupují ke sdílenému prostředku. Pouze jedno vlákno vlastní vzájemné vyloučení (mutex) najednou, a tak se při spuštění programu vytvoří mutex s jedinečným názvem. Když podproces obsahuje zdroj, musí uzamknout mutex z jiných podprocesů, aby se zabránilo souběžnému přístupu k prostředku. Po uvolnění zdroje vlákno odemkne mutex.

k dosažení vzájemného vyloučení použijeme zámky .Použijte zámky vzájemného vyloučení k serializaci provádění vláken. Zámky vzájemného vyloučení synchronizují vlákna, obvykle tím, že zajistí, že pouze jedno vlákno najednou provede kritickou část kódu. Zámky Mutex mohou také zachovat jednovláknový kód.

zámek by měl být,

  • Udržujte vzájemné vyloučení mezi vlákny.
  • Deadlock Free
  • bez hladovění

zámek bude bez hladovění →bez zablokování . Abychom mohli vyhodnotit zámek, musíme zkontrolovat, zda se vzájemně vylučuje, zda je bez zablokování nebo ne, a zda je bez hladovění nebo ne.

jednoduchý zámek

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;
}

řekněme, že tento blok kódu provádějí dvě vlákna(vlákno a a vlákno B).

Předpokládejme, že nejprve provede .Zadá metodu zámku, zkontroluje hodnotu příznaku v řádku 1 a odvodí ji jako nepravdivou.

kontextový přepínač nastane v tomto bodě A B provede další. Zadá metodu zámku, zkontroluje hodnotu příznaku v řádku 1 a odvodí ji jako nepravdivou. Poté provede Řádek-2 a vstoupí do kritické oblasti.

nyní se opět spustí a a ukazatel pro vlákno a je na řádku-2 (protože již provedl řádek-1) a také vstupuje do kritické oblasti.

zde není zachováno vzájemné vyloučení pro tyto 2 vlákna A A B, protože oba přistupují ke kritické oblasti současně..

Zamkněte jeden

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
}

řekněme, že dva podprocesy (vlákno a a vlákno B) provádějí tento blok kódu, jak je uvedeno výše . Zde místo jednoho booleovského příznaku máme pro každé vlákno dva příznaky.(Řádek-1)

Předpokládejme, že se provede jako první. zadá metodu zámku, přiřadí hodnotu „true“ jeho vlajce v řádku-2, zkontroluje hodnotu příznaku jiného vlákna v řádku-3 a odvodí ji jako false.Tak vstupuje do kritické oblasti.

pak B provede .Zadá metodu zámku, přiřadí hodnotu‘ true ‚jeho vlajce v řádku-2, zkontroluje hodnotu příznaku jiného vlákna v řádku-3 a odvodí ji jako „true“, protože již vlákno a změnilo hodnotu it na „true“. takže B vstoupí do smyčky a počká, až se příznak vlákna B stane false, aby se dostal ven ze smyčky while.

po dokončení kritické sekce vlákno a provede metodu odemknutí, přiřadí hodnotu“ false “ jeho příznaku a ukončí. Nyní, když smyčka stav závitu B stát false a B opouští smyčku a vstupuje do kritické oblasti.

vzájemné vyloučení je tedy v tomto zámku správně řešeno.

nyní umožňuje zvážit tento scénář.

Krok-1-Předpokládejme, že se provede první. zadá metodu zámku, přiřadí hodnotu‘ true ‚ jeho příznaku v řádku-2, dojde k přepínání kontextu a čeká.

Krok-2-pak B provede. zadá metodu zámku, přiřadí hodnotu‘ true ‚ jeho příznaku v řádku-2, dojde k přepínání kontextu a čeká.

Krok-3-Nyní se znovu spustí a A nyní je ukazatel a na řádku 3 a zkontroluje hodnotu příznaku jiného vlákna v řádku-3 a odvodí jej jako „true“ (kvůli kroku-2). Vstupuje tedy do smyčky while.

Krok-4-Nyní se znovu spustí B A nyní je ukazatel B na řádku 3 a zkontroluje hodnotu příznaku jiného vlákna v řádku-3 a odvodí jej jako „true“ (kvůli kroku-1). Vstupuje tedy do smyčky while.

nyní jsou obě vlákna ve smyčce a čekají, až se uvolní.Toto je stav zablokování.

Zamkněte dvě

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() {}}

pokud je vlákno B v kritické sekci, pak a je oběť a naopak.LockTwo tak uspokojuje vzájemné vyloučení.

pokud jsou obě vlákna obětí, pak se smyčí uvnitř smyčky while na řádku 3 a vytvoří zablokování. Ale zde může být obětí pouze jedna z nití. Pokud je oběť, bude smyčka uvnitř zatímco smyčky na řádku-3 a když B přiřadit sebe jako oběť a zlomí smyčku a vstoupí do kritické oblasti.Tento zámek je tedy bez zablokování.

Řekněme, že tento blok kódu provádí pouze jedno vlákno .To bude smyčka uvnitř zatímco smyčky na věky, aniž by nějaké závity k uvolnění it. It bude hladovět provést CS.Tento zámek tedy není bez hladovění.

Petersonův algoritmus

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

tím se odstraní všechny nevýhody, které jsme viděli v předchozích zámcích. Poskytne vzájemné vyloučení bez zablokování a hladovění.

eliminuje hladovění LockTwo . Pokud to provede pouze jedno vlákno, provede tento blok bez hladovění.

Bounded Waiting Concept

hladovění-svoboda zaručuje každé vlákno, které volá lock (), nakonec vstoupí do kritické sekce.Ale neexistuje žádná záruka o tom, jak dlouho to bude take.So pro zachování této spravedlnosti předpokládáme, že pokud a volá zámek () před B, A by měl vstoupit do kritické sekce před B .

analyzujeme zámek rozdělením na dvě části

  • D-dveřní sekce
  • w-čekací sekce
public void lock() { #Doorway Section
flag = true;
victim= i; #Waiting Section
while (flag && victim == i) {};
}

R-ohraničené čekání

Předpokládejme, že A A B provádějí zámek a a přistupuje k D( sekce dveří ) v n-tý čas a B přistupuje k D v m-tý čas, kde n>m. A n-té dveře předcházely B-té dveře.

n-tý kritická sekce tedy a předchází B (m + r)-té kritické sekci.To znamená, že B nemůže předjet A více než r krát.

kdo dřív přijde, ten dřív mele znamená r = 0 . Zámek je první na řadě, pokud vlákno a kdykoli dokončí své dveře dříve, než vlákno B zahájí své dveře,
pak a nemůže být předjímáno B.

pekařský algoritmus

pekařský algoritmus je jedním z nejjednodušších známých řešení problému vzájemného vyloučení pro obecný případ procesu N. Pekařský algoritmus je kritickým úsekovým řešením pro n procesy. Algoritmus zachovává vlastnost „kdo dřív přijde, ten dřív mele“.

lexikografické pořadí v pekařském algoritmu znamená (A, i) < (b, j), pokud a < b, nebo A = b a 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;
}}

v Pekařské metodě() přiřazujeme booleovský příznak a hodnotu štítku 0 pro každý ‚n‘ počet vláken.

pro každé vlákno, které přistupuje k metodě zámku, přiřazujeme true jeho příznaku a jeho hodnotu štítku zvyšujeme maximálním přírůstkem max všech dostupných štítků o 1.

(label,i) > (label,k)

ale zde řádek -2 není atomový .takže dvě vlákna mohou současně spustit Řádek-2 a získat stejnou hodnotu štítku. Tedy label = label. V tomto scénáři musíme upřednostňovat proces, který vstoupil do dveří jako první, a nechat tento proces vstoupit do kritické sekce. Zkontroluje tedy id vlákna a nechá vlákno, které má nejmenší id.

Similar Posts

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna.