Algoritmer för att förhindra dödläge
Inom datavetenskap används algoritmer för förebyggande av dödläge i samtidig programmering när flera processer måste få mer än en delad resurs . Om två eller flera samtidiga processer erhåller flera resurser urskillningslöst, kan en situation uppstå där varje process har en resurs som behövs av en annan process. Som ett resultat kan ingen av processerna få alla resurser den behöver, så alla processer blockeras från vidare exekvering. Denna situation kallas ett dödläge . En algoritm för förhindrande av dödläge organiserar resursanvändningen av varje process för att säkerställa att minst en process alltid kan få alla resurser den behöver. Ett sådant exempel på dödlägesalgoritm är Bankers algoritm.
Översikt
| namn | Coffmans förhållanden | Beskrivning |
|---|---|---|
| Bankers algoritm | Ömsesidig uteslutning | Bankers algoritm är en resursallokerings- och dödlägesalgoritm utvecklad av Edsger Dijkstra . |
| Förhindrar rekursiva låsningar | Ömsesidig uteslutning | Detta förhindrar att en enda tråd kommer in i samma lås mer än en gång. |
Distribuerat dödläge
Distribuerade dödlägen kan uppstå i distribuerade system när distribuerade transaktioner eller samtidighetskontroll används. Distribuerade dödlägen kan detekteras antingen genom att konstruera en global väntan-på-graf , från lokala väntan-på-grafer vid en dödlägesdetektor eller genom en distribuerad algoritm som kantjagning.
Phantom-blockerat låsläge är blockerat låsläge som upptäcks i ett distribuerat system på grund av systemets interna förseningar men som faktiskt inte längre existerar vid tidpunkten för upptäckten.
Förebyggande av dödläge
Det finns många olika sätt att öka parallellismen där rekursiva låsningar annars skulle orsaka dödlägen. Men det finns ett pris. Och det priset är antingen prestanda/overhead, tillåt datakorruption eller båda.
Några exempel inkluderar: låshierarkier, låsreferensräkning och preemption (antingen genom att använda versionshantering eller tillåta datakorruption när preemption inträffar); Wait-For-Graph (WFG) [1] algoritmer, som spårar alla cykler som orsakar dödlägen (inklusive tillfälliga låsningar); och heuristiska algoritmer som inte nödvändigtvis ökar parallellismen på 100 % av platserna där dödlägen är möjliga, utan istället kompromissar genom att lösa dem på tillräckligt många ställen för att prestanda/overhead vs parallellism är acceptabelt.
Tänk på en situation "när två tåg närmar sig varandra vid en korsning". Just-in-time-prevention fungerar som att ha en person stående vid övergångsstället (övergångsvakten) med en växel som släpper in endast ett tåg på "superspår" som går ovanför och över de andra väntande tågen.
- För icke-rekursiva lås kan ett lås endast anges en gång (där en enda tråd som går in två gånger utan att låsa upp kommer att orsaka ett dödläge, eller skapa ett undantag för att upprätthålla cirkulär vänteförhindrande).
- För rekursiva lås tillåts endast en tråd passera genom ett lås. Om några andra trådar går in i låset måste de vänta tills den initiala tråden som passerade slutförs n antal gånger den har gått in.
Så problemet med den första är att den inte förhindrar dödläge alls. Den andra förhindrar inte distribuerat dödläge. Men den andra omdefinieras för att förhindra ett dödlägesscenario som det första inte åtgärdar.
Rekursivt tillåts endast en tråd passera genom ett lås. Om andra trådar går in i låset måste de vänta tills den första tråden som passerade slutförs n antal gånger. Men om antalet trådar som går in i låsning är lika med antalet som är låsta, tilldela en tråd som supertråd och låt den bara köras (spåra antalet gånger den går in i/ut ur låsning) tills den slutförs.
När en supertråd är klar ändras tillståndet tillbaka till att använda logiken från det rekursiva låset och den avslutande supertråden
- anger sig själv som inte en supertråd
- meddelar skåpet att andra låsta, väntande trådar behöver kontrollera detta tillstånd igen
Om ett dödlägesscenario finns, ställ in en ny supertråd och följ den logiken. I annat fall, återuppta den vanliga låsningen.
Frågor som inte behandlas ovan
Mycket förvirring kretsar kring stoppproblemet . Men denna logik löser inte stoppproblemet eftersom förhållandena under vilka låsning sker är kända, vilket ger en specifik lösning (istället för den annars erforderliga allmänna lösningen som stoppproblemet kräver). Ändå förhindrar detta skåp alla blockerade bara med tanke på lås som använder denna logik. Men om det används med andra låsmekanismer, ett lås som startas låses aldrig upp (undantag som kastas ut utan att låsa upp, loopar obestämt i ett lås, eller kodningsfel som glömmer att ringa upplåsning), blockering är mycket möjligt. Att utöka villkoret till att inkludera dessa skulle kräva att man löste stoppfrågan, eftersom man skulle ha att göra med förhållanden som man inte vet något om och inte kan förändra.
Ett annat problem är att det inte tar upp det tillfälliga dödläget (inte egentligen ett dödläge, utan en prestationsdödare), där två eller flera trådar låser sig på varandra medan en annan orelaterade tråd körs. Dessa tillfälliga låsningar kan ha en tråd som löper uteslutande inom dem, vilket ökar parallelliteten. Men på grund av hur den distribuerade dödlägesdetekteringen fungerar för alla lås, och inte delmängder däri, måste den orelaterade löpande tråden slutföras innan supertrådslogiken utförs för att ta bort det tillfälliga dödläget.
Man kan se det tillfälliga live-lock-scenariot ovan. Om en annan orelaterade löpande tråd börjar innan den första orelaterade tråden går ut, kommer en annan varaktighet av tillfällig låsning att inträffa. Om detta händer kontinuerligt (extremt sällsynt), kan det tillfälliga dödläget förlängas tills precis innan programmet avslutas, då de andra orelaterade trådarna garanterat avslutas (på grund av garantin att en tråd alltid kommer att slutföras).
Ytterligare expansion
Detta kan utökas ytterligare för att involvera ytterligare logik för att öka parallelliteten där tillfälliga låsningar annars skulle kunna uppstå. Men för varje steg att lägga till mer logik, lägger vi till mer overhead.
Ett par exempel inkluderar: expanderande distribuerad super-thread låsmekanism för att beakta varje delmängd av befintliga lås; Wait-For-Graph (WFG) [2] algoritmer, som spårar alla cykler som orsakar dödlägen (inklusive tillfälliga låsningar); och heuristiska algoritmer som inte nödvändigtvis ökar parallelliteten på 100 % av platserna där tillfälliga dödlägen är möjliga, utan istället kompromissar genom att lösa dem på tillräckligt många ställen för att prestanda/overhead kontra parallellism är acceptabelt (t.ex. för varje tillgänglig processor, arbeta för att hitta dödläge cykler mindre än antalet processorer + 1 djup).