Vzájemné vyloučení (anglicky mutual exclusion, nebo zkráceně mutex) je algoritmus používaný v konkurentním programování jako synchronizační prostředek. V paralelní části předmětu PDV jsme s mutexy pracovali prakticky na každém cvičení. Mutex zabraňuje tomu, aby dvě vlákna (nebo procesy) vykonávala operace nad stejným sdíleným prostředkem - aby současně vstoupila do stejné kritické sekce. V paralelním programování za nás problém vzájemného vyloučení řešil operační systém, který plnil roli centrální autority. Na rozdíl od tohoto centralizovaného řešení se v distribuovaných výpočtech musí všechny procesy shodnout na tom, kdo v dané chvíli bude mutex vlastnit.
V tomto domácím úkolu si vyzkoušíte implementaci jednoho z algoritmů pro vzájemné vyloučení v distribuovaném prostředí. V takovém systému obecně nelze využít prostředků poskytovaných jediným lokálním strojem, řešení musí být od základu postaveno pouze na výměně zpráv. Algoritmus, který budete implementovat, se podle svých tvůrců jmenuje Ricart-Agrawalův a funguje následujícím způsobem:
Každý proces má své lokální skalární logické hodiny, a zámek (či několik zámků), kde každý má
Na začátku je stav každého zámku každého procesu nastaven na RELEASED. V systému kolují pro každou kritickou sekci dva typy zpráv: REQUEST a OK
Vaším úkolem bude doimplementovat třídu exclusion.ExclusionPrimitive
v hw08_exclusion.zip, která bude implementovat zámek podle protokolu Ricart-Agrawala. Instanci této třídy vlastní každý proces, který chce přistupovat do kritické sekce se jménem criticalSectionName
(seznam všech procesů, které rozhodují o přístupu do kritické sekce naleznete v poli allAccessingProcesses
). Proces, který danou instanci ExclusionPrimitive
vlastní na ní může volat následující metody:
requestEnter()
ve chvíli, kdy chce vstoupit do kritické sekce se jménem criticalSectionName
isHeld()
pro zjištění, zda mu byl už přidělen excluzivní přístup do sekce criticalSectionName
exit()
pro opuštění kritické sekce criticalSectionName
(a uvolnění zdroje pro ostatní procesy)
ExclusionPrimitive
zpracovává zprávy pomocí metody accept()
. Pokud se zpráva týká kritické sekce criticalSectionName
, tak ji zpracujte a vraťte true
. V opačném případě vraťte false
. Ve Vašem kódu můžete používat metody procesu, který danou instanci ExclusionPrimitive
vlastní - metody objektu owner
.
criticalSecionName
. Při zpracovávání zpráv tak musíte ověřovat, zda se přijatá zpráva skutečně týká kritické sekce, kterou obsluhuje daný ExclusionPrimitive
!
Abychom Vám usnadnili práci, naimplementovali jsme Vám logiku Lamportových (skalárních) hodin. Tato logika je implementovaná ve třídě clocked.ClockedProcess
a zajišťuje, že:
Inkrementaci logického času (například před odesláním zprávy) musíte provádět ručně voláním metody increaseTime()
.
ClockedProcess
u, Vaše zprávy musí dědit od třídy clocked.ClockedMessage
(a nikoliv od obecné třídy Message
)!
Vaší implemenaci můžete vyzkoušet na scénáři bank.Main
. Několik bankovních úředníků/úřednic (BankOfficerProcess
) zpracovává příkazy k převodu mezi bankovními účty. Ve chvíli, kdy dochází ke zpracování příkazu pro převod peněz z účtu accounti
na účet accountj
dojde
accounti
a accountj
(voláním metody requestEnter
odpovídajícího objektu ExclusionPrimitive
a následným vyčkáním na splnění podmínky isHeld()==true
). Vzpomeňte si, že jednou z možností, jak lze v případě zamykání více mutexů předejít deadlocku, je zamykat je v přesně daném pořadí - to zajišťuje třída MultiLock
.
ReadMessage
procesu DatastoreProcess
a vyčkáním na odpověď (zprávy ValueMessage
).
WriteMessage
procesu DatastoreProcess
a vyčkáním na potvrzení (zprávami WriteAcknowledgedMessage
).
accounti
a accountj
voláním metody exit()
na odpovídajících instancích ExclusionPrimitive
.
Zazipovaný soubor ExclusionPrimitive.java
s případnými vlastními třídami (nesmí přepisovat kód projektu) odevzdávejte do systému BRUTE do 5.5.2022 23:59 CET pro středeční cvičení a 6.5.2022 23:59 CET pro čtvrteční cvičení.
Za úlohu můžete získat maximálně 2 body v závislosti na kvalitě vašeho řešení.
exclusion
!