Koordonálás osztott rendszerekben

A számítógépes algoritmusok világában a szinkronizálás, kölcsönös kizárás, feloldhatatlan helyzet olyan problémák, amelyeket a többfelhasználós, multitaszk környezetekben meg kell oldani. Egyszerű, egyprocesszoros rendszerekben ezek a problémák könnyedén megoldhatók az ismert mechanizmusok (jelzőbitek, szemaforok, figyelőalgoritmusok (monitorok)) segítségével. Ezek mind feltételezik egyetlen, megosztott memória és egy globális rendszeridő létét. Mindez az osztott rendszerekben nem létezik.

Egyszerű példa: tranzakciók és a globális állapot

Tételezzük fel, hogy valakinek van egy bankszámlája, és ennek a banknak két fiókja van. Annak eldöntésére, hogy az ügyfélnek mennyi pénze van, a bankfiókok meghatározott időpontokban kicserélik az ügyfelek számláinak állapotára vonatkozó információkat egymás között. Tételezzük fel, hogy ez déli 12 órakor történik meg. Osztott rendszerek esetében ez megfelel a globális állapot megismerésére tett kisérletnek. Lássuk, mi történik, ha az ügyfelünk valamikor 12 óra tájban át akarja utalni az A bankfiókban lévő száz dollárját a B bankfiókba!

Három alapvető helyzet egyike állhat elő:

1. A két rendszer órái tökéletes szinkronban vannak, a kritikus időszakban nem történik tranzakció, tehát az ügyfelünk vagy 12 óra előtt sikeresen átutalta a pénzét és a tranzakció le is zárult, vagy csak a kritikus időszak letelte után történik meg az átutalás. Ilyenkor természetesen a számlaegyenleg helyes lesz, tehát az ügyfelünk tévábbra is úgy szerepel, mint akinek bankunknál összesen egy százasa van.
2. A rendszerórák ebben az esetben is szinkronban vannak, de a tranzakció valamikor 12 óra előtt kezdődik és 12 után ér véget. Tehát a kritikus időszakban a pénz valahol útközben van, tehát a rendszer - tévesen - azt a következtetést vonja le, hogy a számla-egyenleg zéró, tehát ügyfelünk pénz nélkül maradt...
3. De mi van akkor, ha az órák nincsenek szinkronban, hanem az A fiók órája siet a B fiók órájához képest. Ha az ügyfelünk úgy "időzíti" az átutalást, hogy az A fiók úrája szerint már elmúlt 12 óra, és a tranzakció lezárul, mielőtt a B fiókban is delet ütne az óra, a renszer szerint a pénze megduplázódik, hisz a kritikus szakaszban - szerinte - az A és a B fiókban is volt száz-száz zöldhasúja.

Mit lehet tenni? Az órák tökéletes szinkronizációja esetén is - a kiszámíthatatlan adatátviteli idő-késleltetések miatt - további hasonló problémák adódhatnak. A kulcsprobléma az, hogy egy osztott rendszerről nem készíthető egy pontos "pillanatfelvétel". A klasszikus szinkronizálás tehát nem lehetséges.

Logikai órák, a Lamport algoritmus

Annak megállapítására, hogy az A esemény a B esemény előtt következett be nem feltétlenül egy fizikai órára van szükségünk. Az egyik lehetséges megoldás az un. Lamport algoritmus. Ennek lényege, hogy minden rendszereseményhez egy idő-eseményt társítunk, amint keresztül a következő eseménynek átadja az ő belső "órájának" az állapotát. Ez az esemény, az ő során ehhez igazíthatja a saját számlálóját. E belső számláló állása adja meg az események időbeni egymásutániságát. A technika alkalmazása nagyon elterjedt, például az összes fejlett fájlrendszer ennek az algoritmusnak valamelyik változatát használja.

Fizikai órák

Sok esetben sajnos ez az algoritmus nem elég, a valós idejő alkalmazásoknál szükség van a valós fizikai idő és a Lamport-órák összehangolt alkalmazására Ilyen esetben több külső órát használnak. Ez a megoldás két alapvető problémát vet fel:

1. Hogy szinkronizáljuk ezeket az órákat a külső világ óráival?
2. Hogy szinkronizáljuk ezeket az órákat egymással?

A megoldást szolgáltató algoritmusok a következő gondolatmeneten alapulnak: minden számítógépnek van egy saját belső órája. A rendszerek, amelyekben ezek a gépek működnek, vagy kapcsolódnak a NIST (National Institute of Standard Time) vagy valamelyik más Internetes idő-szolgáltatásra, vagy nem. Ha igen, akkor ez a hálózati somópont lesz az un. time server, vagy ha nem, valamelyik csomópontot neveznek ki időszolgáltatónak, és a rendszerben található összes többi csomópont saját belső óráját renszeres időközökben ehhez az időszolgáltatóhoz igazítja, egy közös, kijelölt algoritmus alapján. Ez a módszer - minden hibája ellenére - már kielégítő szinkronizálást biztosít az esetek döntő többségében