Search
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:
exclusion.ExclusionPrimitive
criticalSectionName
allAccessingProcesses
ExclusionPrimitive
requestEnter()
isHeld()
exit()
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.
accept()
true
false
owner
criticalSecionName
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:
clocked.ClockedProcess
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().
increaseTime()
ClockedProcess
clocked.ClockedMessage
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
bank.Main
BankOfficerProcess
accounti
accountj
requestEnter
isHeld()==true
MultiLock
ReadMessage
DatastoreProcess
ValueMessage
WriteMessage
WriteAcknowledgedMessage
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 10.5. 23:59 CET pro středeční cvičení a 11.5. 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í.
ExclusionPrimitive.java