linearizability (tsz. linearizabilities)
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.
Ez különbözteti meg a sequential consistency modelltől, ahol a valós idejű sorrendet nem szükséges megtartani.
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.
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.
Szál A: Szál B:
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:
Egy konkurens végrehajtás linearizálható, ha létezik egy szekvenciális műveletsorozat, amely:
push(3) után pop() → 3),op1 véget ért, mielőtt op2 elkezdődött, akkor op1 előbb szerepel a szekvenciában.
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ó.
| 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.
ConcurrentHashMap, ConcurrentQueue)
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.
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.