5. tétel - Konkurens adatszerkezetek I.

Mutassa be a termelő-fogyasztó problémát! Definiálja a szálbiztos adatszerkezet fogalmát! Sor adatszerkezet esetén milyen módszerrel érhető el a szálbiztosság?

A tételhez érdemes elolvasni az Alíz-Bob kutyás sztorit is (itt), szerintem segíti a megértést.

Termelő-fogyasztó probléma

Helyzet

  • Egy adatszerkezet áll a középpontban
    • a termelő behelyez elemeket
    • a fogyasztók pedig eltávolítanak elemeket
  • A termelő csak akkor végezheti a tevékenységét, ha a fogyasztók éppen nem fogyasztanak
  • Cél:
    • Nem akarjuk, hogy a termelő a fogyasztókra várakozzon
    • A fogyasztókat maximálisan ki akarjuk használni
  • Megoldás: egy buffert használunk, amely egy sor adatszerkezetként is értelmezhető
    • A termelő behelyezi a sorba az elemeket, a fogyasztók pedig kiveszik
    • A buffer mérete véges, tehát ha tele a sor, akkor a termelő várakozik, ha pedig üres, akkor a fogyasztók.
    • A termelő jelez a fogyasztóknak, ha behelyezte az első elemet
    • A fogyasztók jeleznek a termelőnek, ha kivették az utolsót

Probléma

  • Megtelik a buffer, a termelő leáll, de a fogyasztók már ki is ürítik a sort, és hamarabb jeleznek a termelőnek, mint az elkezdett volna várakozni.
  • Ekkor felek egymásra várnak, holtpont alakul ki.
  • Ha a buffer elérése nem atomi művelet, akkor az is okozhat problémát
  • Megoldható: szemaforral
    • Ekkor a termelő egy szemaforba próbál belépni, ha a buffer nincsen tele.
    • Siker esetén belehelyez egy elemet a tárolóba, és kilép a szemaforból.
    • A fogyasztó belép egy szemaforba, ha a bufferben van elem, ekkor azt eltávolítja, és kilép a szemaforból.
    • Több fogyasztó esetén a buffer elérését lockba kell zárni.

Termelő-fogyasztó probléma megoldása

Szálbiztos adatszerkezet

Szálbiztosnak akkor nevezünk egy adatszerkezetet, ha több szál szimultán kérésére is versenyhelyzettől mentes marad.

Szálbiztosság elérése sor adatszerkezet esetén

Korlátos sor

  • A termelő-fogyasztó problémánál bemutatott FIFO buffer szinkronizációját kell megoldani
    1. szemaforral
    2. monitorral
  • az elemszámot érdemes külön egész számként követni és mindig frissíteni
    1. kölcsönös kizárással
    2. atomi inkrementálás/dekrementálás műveletekkel
  • első és utolsó elem referenciáját tárolni kell
  • Durván szemcsézett megoldás: egy globális lock van
  • Finoman szemcsézett megoldás:
    • ENQ() és DEQ() műveletek konkurens elérhetőek, lehetőség van a sorhoz szimultán hozzáadni és onnan elemet levenni
    • ekkor két lock van, EnqLock és DeqLock
    • EnqLock megszerzésével lehet beszúrni:
      1. szabad helyek ellenőrzése
      2. ha van hely: beszúrás, majd EnqLock elengedése
        • a beszúrás után ébreszteni kell a levétellel foglalkozó várakozó ágakat, ha a lista üres volt, amihez DeqLock megszerzése szükséges
      3. ha nincs hely: EnqLock elengedése és várakozás
    • DeqLock megszerzésével lehet kivenni:
      1. várakozás, ha a sor üres
      2. kivétel
      3. szabad helyek számának frissítése
      4. ha teli volt, a blokkolt hozzáadó szálak ébresztése (EnqLock megszerzésével és jelzéssel)

Korlátlan sor

  • eltekintünk a kapacitástól
  • A finoman szemcsézett és a triviális durván szemcsézett megoldás mellett lehetőség van lock-mentes implementációra is CompareAndSet atomi műveletekre alapozva a megoldást.
    • Ebben az esetben ügyelni kell arra, hogy a művelet közben változhat a sor releváns eleme (első vagy utolsó, művelettől függően)
      • ekkor a CompareAndSet kiértékelés fázisában hamis visszajelzést ad: ekkor ismét próbálkozni kell.
    • Ez egyfajta lusta-elvű megközelítés a blokkolás helyett.