Kas saaks kirjeldada lock-free tööpõhimõtet?

Lock-free algoritmide põhivõte seisneb selles, et paralleelse juurdepääsu korral andmetele saab vähemalt üks voog alati lõpetada oma operatsiooni lõpliku sammu arvuga, sõltumata teiste voogude aktiivsusest. Seda saavutatakse atomaarsete operatsioonide, nagu Compare-And-Swap (CAS), Fetch-And-Add (FAA) ja teiste, kasutamisega, mida pakub protsessor.

Erinevused lukustustega:

Omadus	Lock-based (lukkudega)	Lock-free (ilma lukuta)
Edusamm	Voog võib olla lukustatud	Vähemalt üks voog edeneb
Vastuoluline lukustamine	Võimalik	Võimatu
Planeerija vajadus	Kõrge	Vähem
Rakendamise keerukus	Võrreldes lihtsam lihtsates juhtudes	Kõrgem, nõuab hoolikat disaini

Rakendused:

Lock-free andmestruktuurid ja algoritmid kasutatakse sageli kõrge koormusega süsteemides, kus minimaalne viivitus ja lukustuste vältimine on kriitilise tähtsusega:

• Kommunikatsioonikanalite rakendamine
• Järjekorrad ja virnad ilma lukudeta
• Ühise mälukasutuse jagamine

CAS näide:

// Atomaarne väärtuse value asendamine uue väärtusega, kui praegune väärtus on old_value.
// Tagastab true, kui asendus toimus, vastasel juhul false.
atomic.CompareAndSwapInt64(&value, old_value, new_value)

Lock-free keerukus:

Lock-free algoritmide väljatöötamine on keerulisem, kuna nõuab hoolikat voogude koostööd ja atomaarsete operatsioonide kasutamist. Võivad tekkida probleemid, nagu ABA probleem, mis nõuab täiendavaid mehhanisme, näiteks double-word CAS.