6. tétel - Konkurens adatszerkezetek II.

Milyen módszerekkel készíthető szálbiztos lista? Mutassa be a durván és a finoman szemcsézett, valamint optimista és lusta szinkronizáció elvi megoldását!

Szálbiztos lista

Definiáljuk a láncolt listát olyan generikus adatszerkezetként, amelynél adottak az Add(), Remove() és Contains() műveletek. Az egyes listaelemek esetén legyen elérhető az elem T típusú értéke, az elem kulcsa, és a következő listaelem referenciája.

Durván szemcsézett megoldás

• Minden hozzáférést ugyanaz a lock őriz
• Nem hatékony
• Ha a lock várósora FIFO, akkor kiéheztetésmentes
• Ha alacsony a versengés a hozzáférésért, akkor jó lehet, mert kicsi az overhead és könnyű az implementáció

Finoman szemcsézett megoldás

• A szerkezetet külön részegységekre bontjuk
• A listaelemek külön-külön kerülnek lockolásra, amikor műveletet végzünk rajtuk
• Ha a műveletnél csak a forráselemet lockoljuk, könnyen hibára vezethet a versenyhelyzet miatt
  • Pl: fej → a → b → c listában törölni akarjuk a-t és b-t párhuzamosan. Ehhez egyik szálnak a fej mutatóját a-ról b-re kell állítani, míg a másik szálnak a mutatóját b-ről c-re. Ekkor a versenyhelyzet miatt előállhat olyan eset, hogy b helytelenül a lista része marad, ha csak a mutatót tartalmazó csúcsok vannak zárolva.
• Megoldás: hand-over-hand locking:
  • referencia módosításakor vagy megszüntetésekor nem csak a mutató csúcsot lockoljuk, hanem a mutatott csúcsot is
  • A lockolás és feloldás csúszóablakos módszerrel, átfedéssel kell történjen
  • A sorrend mindenképp azonos kell legyen, minden művelet esetén, különben holtpont alakulhat ki
• Hátrány: sokáig blokkolhat olyan szálakat, amelyek csak bejárni akarják a listát

Optimista szinkronizáció

• előbb zárolás nélkül, blokkolásmentesen bejárjuk a listát
• megnézzük, van-e értelme továbblépni:
  • törlés esetén: megvan az elem
  • beszúrás esetén: nincs még ilyen elem
• ha van, akkor a két érintett csúcsot lockoljuk
• majd ellenőrizzük, hogy még mindig érintetlenek-e
• ha a validáció
  • sikeres: a művelet elvégezhető
  • sikertelen: újra be kell járni a listát, és újra próbálkozni
• ha a gyűjtemény nem módosul a bejárást követően, akkor hatékony és szálbiztos a szinkronizáció
• a validáció lépése hosszadalmas

Lusta szinkronizáció

• az optimista szinkronizáció validációs lépése lerövidíthető
• bevezetünk a listaelemek esetén egy MARKED nevű logikai mezőt
  • ez igaz értéket kap, ha az elemet kijelöljük törlésre
  • a bejárás szemszögéből ami nem MARKED, az elérhető a fejből kiindulva, ami MARKED, az valójában már nincs a gyűjteményben
• ADD():
  1. a beszúrandó elem helyét megtalálva a két szomszédos csúcsot lockolja, majd validál
  2. validáció esetén a elég a két elem MARKED mezőjének értékét és a referenciát megvizsgálni
     • logikai értékek hamisak => az elemek nincsenek törölve
     • mutató az előbbi csúcsból utóbbiba mutat => szomszédosak
  3. vizsgálat után mehet a beszúrás a két elem közé
• REMOVE():
  1. először a törlendő elemet keressük meg blokkolásmentesen
  2. ha megvan, a törlendő elem és a megelőző elem referenciáját zároljuk
  3. az elem MARKED mezejét igazra állítjuk
  4. az elemet kiláncoljuk
• CONTAINS():
  1. megkeresi az elemet
  2. ellenőrzi, hogy a MARKED mező hamis értékű