Livelock: Hvad er, eksempel, forskel med deadlock

⚡ Smart opsummering

Livelock er en samtidighedssituation, hvor processer bliver ved med at ændre deres tilstande som reaktion på hinanden, men alligevel ikke gør nogen reel fremgang, forbliver aktive og forbruger CPU-cyklusser uden nogensinde at fuldføre deres opgaver eller blive blokeret.

🔁 Definition: Livelock opstår, når processer konstant ændrer tilstand for at imødekomme hinanden, men aldrig fremskrider, i modsætning til de frosne processer i en dødvande.
🚶 Eksempel: To personer træderping side om side i en korridor, hvor man kan passere hinanden, illustrerer livelock, hvor man bevæger sig kontinuerligt, men aldrig krydser hinanden.
🧮 Årsag: Gentagen polling og genforsøg for låse, afgrænset af endelige procestabelpladser, driver processer til livelock uden at nogen af dem blokerer.
⚖️ Sammenligning: Deadlock fryser processer, sult nægter ressourcer på ubestemt tid, og livelock holder processer beskæftiget uden fremskridt.
🛡️ Forebyggelse: Randomiseret backoff, grænser for gentagelser og prioritetsrækkefølge bryder de symmetriske gentagelser, der skaber en livelock.
🤖 AI-vinkel: Maskinlæring markerer CPU-mønstre uden fremskridt, og Copilot hjælper med at skrive backoff- og lock-order-kode, der undgår livelock.

Læs mere

Hvad er Livelock?

A livelock er en situation, hvor en anmodning om en eksklusiv lås gentagne gange afvises, da mange overlapper hinandenping Delte låse forstyrrer hinanden. Processerne ændrer hele tiden deres status, hvilket forhindrer dem i at fuldføre opgaven.

Eksempler på Livelock

Eksempel 1:

Det nemmeste eksempel på Livelock er to personer, der mødes ansigt til ansigt i en korridor, og begge bevæger sig til side for at lade den anden passere. De bevæger sig fra side til side uden at gøre fremskridt, fordi de bevæger sig i samme retning på samme tid. Her krydser de aldrig hinanden.

Eksempel 2:

I billedet ovenfor har hver af de to processer brug for to ressourcer, og de bruger primitiv polling til at forsøge at finde de låse, de har brug for. Hvis et forsøg mislykkes, forsøger metoden igen.

Proces A holder ressource Y
Proces B rummer ressource X
Proces A kræver ressource X
Proces B kræver ressource Y

Antag at proces A kører først og henter ressource X, og derefter kører proces B og henter ressource Y. Uanset hvilken proces der kører først, gør ingen af dem yderligere fremskridt.

Ingen af de to processer er dog blokeret. De bruger CPU-ressourcer gentagne gange uden at gøre fremskridt, men de stopper aldrig for en behandlingsblok.

Derfor er denne situation ikke en dødvande, fordi ikke en eneste proces er blokeret; i stedet står vi over for en situation svarende til en dødvande, som kaldes LIVELOCK.

Hvad fører til Livelock?

Livelock er knyttet til antallet af processer, et system tillader, hvilket er defineret af det samlede antal poster i procestabellen. Disse procestabelpladser behandles derfor som begrænsede ressourcer. Når processer gentagne gange forsøger at få disse begrænsede ressourcer, mens de konstant viger for hinanden, gør ingen af dem fremskridt, og systemet går ind i en livelock.

Hvad er Deadlock?

A dødvande er en situation, der opstår i et operativsystem, når en proces går i ventetilstand, fordi en anden ventende proces holder den efterspurgte ressource. Deadlock er et almindeligt problem i multiprocessering, hvor flere processer deler en bestemt type gensidigt udelukkende ressource kendt som en soft lock eller software.

Eksempel på dødvande

Et eksempel fra den virkelige verden ville være trafik, der kun kører i én retning.
Her betragtes en bro som en ressource.
Når der opstår en fastlåst situation, kan den nemt løses, hvis én bil bakker (foregriber ressourcer og ruller tilbage).
Flere biler skal muligvis bakkes op, hvis der opstår dødvande.
Derfor er sult mulig.

Eksempel på dødvande

Hvad er sult?

Sult er en situation, hvor lavprioriterede processer blokeres, mens højprioriterede processer fortsætter. I ethvert system sker anmodninger om høj- og lavprioriterede ressourcer dynamisk. Derfor kræves der en politik for at bestemme, hvem der betjenes, og hvornår.

Med nogle algoritmer kan visse processer muligvis ikke modtage den ønskede service, selvom de ikke er fastlåste. Udsultning opstår, når nogle tråde gør delte ressourcer utilgængelige i en længere periode.

Eksempel på sult

For eksempel tilbyder et objekt en synkroniseret metode, der sandsynligvis vil tage lang tid at returnere. Hvis én tråd bruger denne metode ofte, blokeres andre tråde, der også har brug for hyppig synkroniseret adgang til det samme objekt, ofte.

Forskellen mellem Deadlock, Starvation og Livelock

En deadlock er en situation, der opstår i et operativsystem, når en proces går i ventetilstand, fordi den efterspurgte ressource holdes af en anden ventende proces.
En livelock er derimod næsten lig en deadlock, bortset fra at tilstandene af de processer, der er involveret i en livelock, altid ændrer sig som reaktion på hinanden, uden at nogen af dem skrider frem.
Så livelock er et unikt tilfælde af ressourcemangel.

Ofte Stillede Spørgsmål

Livelock reduceres ved at tilføje tilfældighed eller rækkefølge til genforsøg. Teknikker inkluderer randomiseret eller eksponentiel tilbagetrækning før genforsøg, begrænsning afping antallet af gentagne forsøg og håndhævelse af en fast låseerhvervelsesrækkefølge, så processer holder op med at spejle hinandens bevægelser.

Nej. Livelocked-processer blokeres aldrig – de bliver ved med at køre og bruger CPU-cyklusser gennem konstante genforsøg, uden at de gør nogen fremskridt. I en deadlock stopper de involverede processer og venter, så de ikke bruger CPU'en.

Ofte ja. Deadlockede processer sidder fastfrosset, hvilket er let at få øje på, mens livelockede processer forbliver aktive og bliver ved med at ændre tilstand. Detektion leder normalt efter højt CPU-forbrug kombineret med nul fremadrettet fremskridt over tid.

En kapløbstilstand er et forkert eller uforudsigeligt resultat forårsaget af usynkroniseret adgang til delte data. Livelock involverer derimod processer, der forbliver aktive og bliver ved med at ændre tilstand som reaktion på hinanden uden nogensinde at fuldføre deres arbejde.

Ja. Tråde, der gentagne gange reagerer på hinanden – for eksempel både frigiver og anmoder om en låsning på samme tid – kan livelockes uden nogensinde at blokere. Det forekommer ofte i gentagelses- og tilbagetrækningslogik, der mangler tilfældighed.

Maskinlæringsmodeller studerer CPU-, planlægnings- og ressourceforbrugsmønstre for at markere processer, der brænder cyklusser uden at fortsætte. Dette hjælper operatører med at opdage livelock tidligere end fastsatte tærskler, især i store cloud- og datacenterarbejdsbelastninger med mange interagerende processer.

Ja. GitHub Copilot kan foreslå randomiserede backoffs, timeouts og konsistente låseordensmønstre, der reducerer både risikoen for livelock og deadlock. Udviklere bør stadig gennemgå den genererede samtidighedslogik omhyggeligt, da subtile timingfejl er lette at overse.

Nogle gange. Hvis timingen ændrer sig – for eksempel gennem tilfældige gentagelsesintervaller – kan processer bryde mønsteret og fortsætte. Uden sådanne ændringer kan livelock fortsætte på ubestemt tid og spilde CPU, mens ingen proces afslutter sin opgave.