Ugrás a tartalomhoz

linearizability

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

linearizability (tsz. linearizabilities)

  1. (informatika) A linearizability (lineáris végrehajthatóság) egy konzisztenciamodell, amelyet párhuzamos rendszerek és osztott rendszerek viselkedésének formális meghatározására használnak. Különösen fontos a konkurens adatszerkezetek, megosztott memóriák és elosztott adatbázisok helyességének elemzésében.


📘 Definíció (magas szinten)

A linearizability azt mondja ki:

Egy konkurens (párhuzamos) rendszer működése helyes, ha minden művelet úgy tűnik, mintha egy valamilyen sorrendben, egymás után történt volna (szekvenciálisan), a valós időrenddel összhangban.

Más szavakkal: a konkurens műveletek sorrendje úgy nézzen ki kívülről, mintha egymás után történtek volna, még akkor is, ha valójában átfedik egymást időben.


📈 Fontos tulajdonságok

1. Szekvencializálhatóság

  • A rendszer viselkedése megfeleltethető egy sorban végrehajtott (szekvenciális) műveletsornak.

2. Valós idejű sorrend megtartása

  • Ha egy művelet „A” befejeződik egy másik „B” elkezdése előtt, akkor a szekvenciában is „A” legyen előbb.

Ez különbözteti meg a sequential consistency modelltől, ahol a valós idejű sorrendet nem szükséges megtartani.


🧠 Miért fontos?

A több szálon futó vagy elosztott rendszerekben ugyanarra az adatra több szál vagy gép végezhet írási/olvasási műveletet. A linearizability segít eldönteni, hogy a rendszer úgy viselkedik-e, mintha nem is lenne párhuzamosság – azaz helyesen.

Például egy push() és pop() függvénnyel rendelkező stack típusú adatstruktúránál linearizálhatóság biztosítja, hogy az értékek ugyanabban a sorrendben jönnek vissza, ahogy betették őket – függetlenül attól, hogy több szál dolgozik rajta egyszerre.


🧪 Példa

Tegyük fel, két szál párhuzamosan használ egy megosztott set(x) és get() operációt.

Idő Szál 1 Szál 2
T1 set(5)
T2 get() → ?

Ha a get() művelet T1 után kezdődik, akkor kötelező 5-öt visszaadnia, ha linearizálható a rendszer. Ha nem azt adja vissza, megsérti a linearizability elvet.


🔁 Műveletek idővonala (vizuálisan)

Szál A: [    WRITE(1)    ]
Szál B:        [   READ(?)   ]

Ha READ() időben belül van a WRITE(1) műveleten, akkor linearizálhatóság azt kívánja, hogy a READ vagy:

  • a művelet előtti állapotot látja (pl. még nem írták be az 1-et)
  • vagy utáni állapotot (már 1-et olvas), de semmiképp nem adhat vissza egy olyan értéket, amit se előtte, se utána nem volt ott.


📐 Formálisabb definíció (Herlihy & Wing alapján, 1990)

Egy konkurens végrehajtás linearizálható, ha létezik egy szekvenciális műveletsorozat, amely:

  1. Tartalmazza az összes eredeti műveletet,
  2. Megőrzi az eredeti műveletek hatását (pl. push(3) után pop() → 3),
  3. Megőrzi a valós idejű sorrendet: ha op1 véget ért, mielőtt op2 elkezdődött, akkor op1 előbb szerepel a szekvenciában.


📊 Linearizációs pont

Minden művelethez tartozik egy linearizációs pont: ez az az egy időpillanat, amikor a művelet logikailag megtörténik. Ezt használjuk arra, hogy a konkurens végrehajtást egy soros végrehajtásra leképezzük.

Példa:

  • push(5) linearizációs pontja lehet az a pillanat, amikor az érték ténylegesen bekerül a verembe.
  • pop() linearizációs pontja lehet az, amikor az érték kikerül a veremből.

Ha minden művelethez tudunk ilyen pontot hozzárendelni úgy, hogy az megfelel a kívánt sorrendnek → a rendszer linearizálható.


⚖️ Linearizability vs Sequential Consistency

Tulajdonság Linearizability Sequential Consistency
Valós idejű sorrend Megőrzi Nem szükséges
Könnyebb ellenőrizni Nehezebb Könnyebb
Erősebb követelmény ✅ ❌

Példa különbségre:

Ha egy írás előbb történik, mint egy olvasás → linearizability megköveteli, hogy az olvasás azt lássa. Sequential consistency ezt nem követeli meg, csak azt, hogy minden szál egyenlő sorrendben lássa az eseményeket.


🔧 Hogyan ellenőrizzük?

Automatikusan:

  • Model checking (pl. TLA+, SPIN)
  • Tesztkeretrendszerek: Jepsen (Clojure), Lincheck (JVM)

Kézzel:

  • Lineáris műveletsor keresése, ami megfelel az eredeti műveleteknek
  • Idővonalak rajzolása
  • Linearizációs pontok beazonosítása


🧵 Példák használatra

  • Concurrent data structures (pl. Java ConcurrentHashMap, ConcurrentQueue)
  • Elosztott adatbázisok (pl. Google Spanner, CockroachDB)
  • Lock-free programozás – az algoritmus akkor helyes, ha linearizálható
  • Multithreaded API-k tesztelése – linearizability tesztekkel garantálják a korrekt működést


⛔ Ellenpéldák

  • Ha egy get() művelet 10-et ad vissza, amit sosem írt senki, vagy amit csak a jövőben írnak majd → megsérti a linearizability-t.
  • Egy lock-free adatstruktúra, amely nem jól szinkronizálja a memóriahozzáférést, és így „kitalált” értékeket ad vissza → nem linearizálható.


🧩 Kapcsolódó fogalmak

  • Atomicity: egy művelet vagy teljesen megtörténik, vagy egyáltalán nem (linearizability általában atomicitást feltételez)
  • Consistency: adatbázisnál hasonló elv
  • CAP-elv: elosztott rendszereknél linearizability = “C” (konzisztencia)
  • Eventual consistency: sokszor a linearizability gyengébb alternatívája


🔚 Összegzés

A linearizability kulcsfontosságú szemlélet az elosztott és párhuzamos rendszerek helyességének bizonyításában. Azt garantálja, hogy a rendszer úgy viselkedik, mintha a műveletek egyenként, sorban történnének, a valós időbeli sorrendet tiszteletben tartva. Habár erős és néha nehezen elérhető követelmény, nélkülözhetetlen minden kritikus alkalmazásban, ahol a helyes és megbízható működés elsődleges.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=linearizability&oldid=3503933”