Eigenschap van een algoritme dat, ook als een thread halverwege stilvalt, minstens één van de andere threads vooruitgang kan boeken. Wordt gebouwd met atomaire instructies zoals CAS.
Japanse benaming: ロックフリー
“Lock-free” komt voor in 3 oefenvragen uit 1 onderwerpen, bijv. Multicore en synchronisatie.
Vakgebied: Multicore en synchronisatie
Antwoord: B. Wanneer een waarde van A naar B verandert en dan terug naar A, merkt CAS de verandering niet op en slaagt
Wanneer de kop van een gekoppelde lijst A is, kan terwijl een thread A leest en CAS voorbereidt een andere thread A verwijderen, bewerkingen met B uitvoeren en weer een knoop op hetzelfde adres A invoegen. CAS slaagt omdat de waarde nog A is, maar de inhoud van de lijst is intussen veranderd en de structuur raakt beschadigd. Dit wordt voorkomen door de pointer samen met een bijwerkteller te vergelijken, of met LR/SC.
Antwoord: A. Ook als een thread halverwege stilvalt, kan minstens één van de andere threads verder met zijn werk
Bij gebruik van locks worden alle anderen opgehouden als de lockhoudende thread stilvalt door een interrupt of lage prioriteit. Een lock-free algoritme werkt gedeelde gegevens rechtstreeks bij met bijvoorbeeld CAS, zodanig dat een thread alleen hoeft te herhalen als iemand anders is geslaagd. Zo komt in totaal altijd een van de threads vooruit. Het correct maken is echter moeilijk en aandacht voor onder meer het ABA-probleem is nodig.
Een lock-free algoritme werkt gedeelde gegevens rechtstreeks bij met bijvoorbeeld CAS, zodanig dat een thread alleen hoeft te herhalen als iemand anders is geslaagd.
Welke eigenschap van een lock-free algoritme is juist?Voorbeelden zijn CAS (compare-and-swap), fetch-and-add en de LR/SC- en AMO-instructies van RISC-V; ze vormen de basis voor locks en lock-free datastructuren.
Welke uitleg over atomaire instructies (ondeelbare instruct…ABA-probleem LR/SC Interrupt Atomaire instructie Numerieke apertuur (NA) Compare-and-swap Acquire-release Barrièresynchronisatie Conditievariabele Data race