1/73 Paměťový model Javy Ada Erlang Zadání Vláknové programování část X Lukáš Hejmánek, Petr Holub {xhejtman,hopet}@ics.muni.cz Laboratoř pokročilých síťových technologií PV192 2013–04–30 2/73 Paměťový model Javy Ada Erlang Zadání Přehled přednášky Paměťový model Javy Ada Erlang Zadání (příklady povětšinou převzaty z JCiP, Goetz) 3/73 Paměťový model Javy Ada Erlang Zadání long promenna = 10000000L; 4/73 Paměťový model Javy Ada Erlang Zadání Paměťový model Javy happens-before ◾ částečné uspořádání Tabulka převzata z JCiP, Goetz 5/73 Paměťový model Javy Ada Erlang Zadání Paměťový model Javy Tabulka převzata z JCiP, Goetz 6/73 Paměťový model Javy Ada Erlang Zadání Paměťový model Javy Piggybacking ◾ spojení happens-before pravidla s jiným pravidlem, obvykle monitorem nebo volatile ◾ raději nepoužívat ◾ příklad: http://kickjava.com/src/java/util/concurrent/FutureTask.java.htm postaveno na tryReleaseShared happens-before tryAcquireShared kombinace volatilní proměnné runner, do které tryReleaseShared zapisuje s program order 7/73 Paměťový model Javy Ada Erlang Zadání Paměťový model Javy void innerSet(V v) { 2 for (;;) { int s = getState(); 4 if (ranOrCancelled(s)) return; 6 if (compareAndSetState(s, RAN)) break; 8 } result = v; 10 releaseShared(0); done(); 12 } V innerGet() throws InterruptedException JavaDoc, ExecutionException JavaDoc { 2 acquireSharedInterruptibly(0); if (getState() == CANCELLED) 4 throw new CancellationException JavaDoc(); if (exception != null) 6 throw new ExecutionException JavaDoc(exception); return result; 8 } 8/73 Paměťový model Javy Ada Erlang Zadání Paměťový model Javy 1 protected int tryAcquireShared(int ignore) { return innerIsDone()? 1 : -1; 3 } 5 /** * Implements AQS base release to always signal after setting 7 * final done status by nulling runner thread. */ 9 protected boolean tryReleaseShared(int ignore) { runner = null; 11 return true; } 13 boolean innerIsCancelled() { 15 return getState() == CANCELLED; } 17 boolean innerIsDone() { 19 return ranOrCancelled(getState()) && runner == null; } 9/73 Paměťový model Javy Ada Erlang Zadání Paměťový model Javy líná inicializace public class UnsafeLazyInitialization { 2 private static Resource resource; 4 public static Resource getInstance() { if (resource == null) 6 resource = new Resource(); // unsafe publication return resource; 8 } 10 static class Resource { } 12 } 10/73 Paměťový model Javy Ada Erlang Zadání Paměťový model Javy @ThreadSafe 2 public class SafeLazyInitialization { private static Resource resource; 4 public synchronized static Resource getInstance() { 6 if (resource == null) resource = new Resource(); 8 return resource; } 10 static class Resource { 12 } } líná inicializace thread-safe 11/73 Paměťový model Javy Ada Erlang Zadání Paměťový model Javy @ThreadSafe 2 public class EagerInitialization { private static Resource resource = new Resource(); 4 public static Resource getResource() { 6 return resource; } 8 static class Resource { 10 } } „dychtivá“ inicializace využívá skutečnosti, že statické inicializátory jsou vždy dokončeny před použitím třídy 12/73 Paměťový model Javy Ada Erlang Zadání Paměťový model Javy @ThreadSafe 2 public class ResourceFactory { private static class ResourceHolder { 4 public static Resource resource = new Resource(); } 6 public static Resource getResource() { 8 return ResourceFactory.ResourceHolder.resource; } 10 static class Resource { 12 } } idiom líné inicializace s použitím holder class využívá líné inicializace tříd 13/73 Paměťový model Javy Ada Erlang Zadání Paměťový model Javy public class DoubleCheckedLocking { 2 private static Resource resource; 4 public static Resource getInstance() { if (resource == null) { 6 synchronized (DoubleCheckedLocking.class) { if (resource == null) 8 resource = new Resource(); } 10 } return resource; 12 } Double Checked Locking anti-pattern pomíjí možnost, že resource je v nedefinovaném stavu od Java 5.0 možno spravit použitím volatile nepoužívat ◾ ani v C/C++! 14/73 Paměťový model Javy Ada Erlang Zadání Přehled přednášky Paměťový model Javy Ada Erlang Zadání (některé příklady z Burns & Wellings: Concurrent and Real-Time Programming in Ada – CRTPA) 15/73 Paměťový model Javy Ada Erlang Zadání Atomické a volatilní proměnné pragma Atomic (); ◾ zajišťuje atomické aktualizace proměnných Prirozene_Cislo : Natural; 2 pragma Atomic (Prirozene_Cislo); pragma Atomic_Components (); ◾ zajišťuje atomické aktualizace součástí složeného typu record type Byte is range 0 .. 255; 2 for Byte’Size use 8; type Moje_Struktura is 4 record B1 : Byte; 6 B2 : Byte; B3 : Byte; 8 B4 : Byte; end record; 10 pragma Atomic_Components (Moje_Struktura); 16/73 Paměťový model Javy Ada Erlang Zadání Atomické a volatilní proměnné pragma Volatile (); ◾ upozornění pro kompilátor, že se hodnoty proměnných mohou neočekávaně měnit ◾ zejména kompilátor musí zamezit optimalizacím, které by mohly interferovat (zakazuje cachování na čtení i zápis) Buffer_Zarizeni : Integer; 2 pragma Volatile (Buffer_Zarizeni); pragma Volatile_Components (); ◾ totéž pro komponenty složeného typu record 17/73 Paměťový model Javy Ada Erlang Zadání Simpsonův algoritmus Kompilátor může mít omezení na maximální délku atomické proměnné ◾ pokud je (nesplnitelný) požadavek na větší atomickou proměnnou, musí ho kompilátor odmítnout Algoritmus pro větší proměnné: Simpson’901 ◾ dva sloty, každý o dvou bankách ◾ do jednoho slotu se zapisuje (round-robin do bank) ◾ ze druhého slotu se čte (poslední zapsaná hodnota) ◾ atomické nastavování indexů slotů a bank ◾ volatilní zápisy do bank/slotů generic 2 type Data is private; Initial_Value : Data; 4 package Simpsons_Algorithm is procedure Write(Item : Data); -- non-blocking 6 procedure Read (Item : out Data); -- non-blocking end Simpsons_Algorithm; 1H. Simpson, ‘Four-Slot Fully Asynchronous Communication Mechanism’, IEE Proceedings, 137 (Pt.E.1), 17–30 (January 1990). Implementace z CRTPA. 18/73 Paměťový model Javy Ada Erlang Zadání Simpsonův algoritmus 1 package body Simpsons_Algorithm is type Slot is (First, Second); 3 Four_Slot : array (Slot, Slot) of Data := (First => (Initial_Value,Initial_Value), 5 Second => (Initial_Value,Initial_Value)); pragma Volatile(Four_Slot); 7 Next_Slot : array(Slot) of Slot := (First, First); 9 pragma Volatile(Next_Slot); 11 Latest : Slot := First; pragma Atomic(Latest); 13 Reading : Slot := First; 15 pragma Atomic(Reading); 19/73 Paměťový model Javy Ada Erlang Zadání Simpsonův algoritmus procedure Write(Item : Data) is 2 Pair, Index : Slot; begin 4 if Reading = First then Pair := Second; 6 else Pair := First; 8 end if; if Latest = First then 10 Index := Second; else 12 Index := First; end if; 14 Four_Slot(Pair, Index) := Item; Next_Slot(Pair) := Index; 16 Latest := Pair; end Write; 20/73 Paměťový model Javy Ada Erlang Zadání Simpsonův algoritmus procedure Read(Item : out Data) is 2 Pair, Index : Slot; begin 4 Pair := Latest; Reading := Pair; 6 Index := Next_Slot(Pair); Item := Four_Slot(Pair, Index); 8 end Read; 10 end Simpsons_Algorithm; 21/73 Paměťový model Javy Ada Erlang Zadání Protected Types – Monitory Implementace monitorů ◾ funkce – nemohou měnit data procedury – mohou měnit data entry – strážený vstup, mohou měnit data ◾ efektivní paralelizace: podobne ReadWriteLocku v Javě funkce mohou přistupovat paralelně procedury a entries musí pracovat exkluzivně 1 protected type Muj_Typ is procedure Nastav_hodnotu (n : Integer); 3 procedure Odnastav_hodnotu; function Zjisti_hodnotu return Integer; 5 entry Pockej_na_nastaveni (n : Integer); private 7 Hodnota : Integer; Nastaveno : Boolean := False; 9 end Muj_Typ; 22/73 Paměťový model Javy Ada Erlang Zadání Protected Types – monitory 10 protected body Muj_Typ is procedure Nastav_hodnotu (n : Integer) is 12 begin Hodnota := n; 14 Nastaveno := True; end Nastav_hodnotu; 16 procedure Odnastav_hodnotu is 18 begin Nastaveno := False; 20 end Odnastav_hodnotu; 22 function Zjisti_hodnotu return Integer is begin 24 return Hodnota; end Zjisti_hodnotu; 26 entry Pockej_na_nastaveni 28 when Nastaveno is begin 30 null; end Pockej_na_nastaveni; 32 end Muj_Typ; 23/73 Paměťový model Javy Ada Erlang Zadání Guarded Entries chránění dle privátního stavu protected type Chraneno_Stavem is 2 entry Vstup; private 4 I : Integer; end Chraneno_Stavem; 6 protected body Chraneno_Stavem is 8 entry Vstup when I > 0 is begin 10 null; end Vstup; 12 end Chraneno_Stavem; ◾ používat pouze privátní proměnné ◾ např. implementace mutexů a semaforů 24/73 Paměťový model Javy Ada Erlang Zadání Guarded Entries Chránění dle atributů 1 protected type Chraneno_Stavem is entry Vstup; 3 private I : Integer; 5 end Chraneno_Stavem; 7 protected body Chraneno_Stavem is entry Vstup when Vstup’Count > 4 is 9 begin null; 11 end Vstup; end Chraneno_Stavem; ◾ možnost použití atributů ◾ atribut E’Count vrátí počet zablokovaných vláken na vstupu do entry E ◾ např. implementace bariér ◾ funguje bezpečně pouze u chráněných objektů, nikoli tasků 25/73 Paměťový model Javy Ada Erlang Zadání Problém řízení přístupu ke zdrojům Aspekty synchronizace požadavků (Bloom, 1979) 1. typ požadované služby 2. pořadí požadavků 3. interní stav přijímajícího vlákna 4. priorita volajícího 5. parametry požadavků 26/73 Paměťový model Javy Ada Erlang Zadání Problém řízení přístupu ke zdrojům Definice příkladu problému: ◾ n zdrojů (vidliček v příborníku) ◾ každé vlákno si může požadovat alokaci 1 . . . m zdrojů (vidliček) kde m ≤ n Možné řešení: ◾ pollování (zodpovědnost vlákna) ◾ rodiny entries (entry families) pro malé m ◾ podpora přístupu k in parametrům předávaným v rámci volání rendezvous není v Adě podporováno implementováno např. v jazce SR (Synchronizing Resources) problém s efektivitou implementace (bariéra se musí vyhodnocovat při každém řazení vlákna do fronty entry, nikoli jen jednou per entry) ◾ requeue 27/73 Paměťový model Javy Ada Erlang Zadání Rodiny entries Úplná formální signatura entry accept Entry_Name(Family_Index)(P : Parameters) do 2 -- sequence of statements exception 4 -- exception handling part end Entry_Name; Rodiny entries ◾ např. prioritizace a odlišení volajících vláken task Multiplexer is 2 entry Channel(1..3)(X : in Data); end Multiplexer; 28/73 Paměťový model Javy Ada Erlang Zadání Rodiny entries Příklad použití s vláknem ◾ multiplexer vynucuje pořadí vstupů cyklicky 1, 2, 3 1 task body Multiplexer is begin 3 loop for I in 1..3 loop 5 accept Channel(I)(X : in Data) do -- consume input data on channel I 7 end Channel; end loop; 9 end loop; end Multiplexer; 29/73 Paměťový model Javy Ada Erlang Zadání Rodiny entries Příklad řízení zdrojů 1 type Request_Range is range 1 .. Max; 3 protected Resource_Controller is entry Allocate(Request_Range)(R : out Resource); 5 procedure Release(R : Resource; Amount : Request_Range); private 7 Free : Request_Range := Request_Range’Last; end Resource_Controller; 9 protected body Resource_Controller is 11 entry Allocate(for F in Request_Range)(R : out Resource) when F <= Free is 13 begin Free := Free - F; 15 end Allocate; procedure Release(R : Resource; Amount : Request_Range) is 17 begin Free := Free + Amount; 19 end Release; end Resource_Controller; 30/73 Paměťový model Javy Ada Erlang Zadání Rodiny entries Příklad řízení zdrojů Problémy ◾ nevhodné pro větší množství alokovatelných zdrojů v jednom požadavku (m) ◾ v případě soutěžení je výběr náhodný (prioritu lze nastavovat v rámci Real-Time Systems Annex) 31/73 Paměťový model Javy Ada Erlang Zadání „Eggshell” model volání chráněného objektu 32/73 Paměťový model Javy Ada Erlang Zadání „Eggshell” model volání chráněného objektu Přednost entry calls čekajících ve frontě Zámek vnější slupky ◾ nedovolí vstup do slupky, pokud je jiné vlákno aktivní voláním procedury nebo entry ◾ po vstupu se vyhodnocuje asociovaná podmínka (stráž) ◾ tento mechanismus zajišťuje bezpečnost použití ’Count 33/73 Paměťový model Javy Ada Erlang Zadání „Eggshell” model volání chráněného objektu Vnitřní slupka ◾ po výstupu z každé procedury a entry se vyhodnocují podmínky a eventuálně se propouští volání čekající na vnitřní slupce 34/73 Paměťový model Javy Ada Erlang Zadání requeue Jak poslat za dveře někoho, koho už jsme si pustili do místnosti? requeue umožňuje vysunout aktivní vlákno v chráněném objektu do fronty před vnitřní slupku ◾ nové volání musí mít stejnou signaturu ◾ implicitně není přerušitelné pomocí abort, aby objekt nezůstal v rozpracovaném stavu ◾ nové volání může být přerušitelné requeue with abort requeue umí fungovat i napříč více chráněnými objekty/úlohami ◾ neobvyklé, používat opatrně 35/73 Paměťový model Javy Ada Erlang Zadání requeue type Request_Range is range 1 .. Max; 2 protected Resource_Controller is 4 entry Allocate(R : out Resource; Amount : Request_Range); procedure Release(R : Resource; Amount : Request_Range); 6 private entry Assign(R : out Resource; Amount : Request_Range); 8 Free : Request_Range := Request_Range’Last; New_Resources_Released : Boolean := False; 10 To_Try : Natural := 0; ... 12 end Resource_Controller; 14 protected body Resource_Controller is entry Allocate(R : out Resource; Amount : Request_Range) 16 when Free > 0 is begin 18 if Amount <= Free then Free := Free - Amount; 20 -- allocate else 22 requeue Assign; end if; 24 end Allocate; 36/73 Paměťový model Javy Ada Erlang Zadání requeue entry Assign(R : out Resource; Amount : Request_Range) 2 when New_Resources_Released is begin 4 To_Try := To_Try - 1; if To_Try = 0 then 6 New_Resources_Released := False; end if; 8 if Amount <= Free then Free := Free - Amount; 10 -- allocate else 12 requeue Assign; end if; 14 end Assign; 37/73 Paměťový model Javy Ada Erlang Zadání requeue procedure Release(R : Resource; Amount : Request_Range) is 2 begin Free := Free + Amount; 4 -- free resources if Assign’Count > 0 then 6 To_Try := Assign’Count; New_Resources_Released := True; 8 end if; end Release; 10 end Resource_Controller; 38/73 Paměťový model Javy Ada Erlang Zadání Ada: Tasks, Rendezvous Koncept CSP: Communicating Sequential Processes ◾ Hoare, 1978 ◾ paralelně běžící sekvenční procesy ◾ komunikace: zasílání zpráv ◾ synchronizace: synchronní zasílání zpráv odesílatel se zablokuje, dokud příjemce není schopen přijmout zprávu příjemce se zablokuje, dokud není schopen od odesílatele přijmout zprávu 39/73 Paměťový model Javy Ada Erlang Zadání Tasks, Rendezvous 40/73 Paměťový model Javy Ada Erlang Zadání Tasks task ◾ lokálně definované běží od začátku rozsahu, v němž jsou definované ◾ dynamicky alokované access typ alokace pomocí new běží až od alokace ◾ pole tasků ukončování ◾ spontánní ◾ abort 41/73 Paměťový model Javy Ada Erlang Zadání Tasks task T is 2 end T; 4 task body T is begin 6 makam; end T; 8 task type T_Type is 10 end T; 12 task body T_Type is begin 14 loop makam; 16 end loop; end T_Type; 18 Pole_T : array (1..10) of T_Type; 20 type T_Type_Access is access T_Type; 22 Dynamicky_T : T_Type_Access; Dynamicky_T := new T_Type; 42/73 Paměťový model Javy Ada Erlang Zadání Parametrizace vláken předávání parametrů při vzniku vlákna užitečné s typy vláken 1 type Monitor_Procedure_Type is access procedure; 3 task type Monitor_Task_Type (Mon_Proc : Monitor_Procedure_Type) is entry Run; 5 entry Stop; entry Request_Terminate; 7 end Monitor_Task_Type; 43/73 Paměťový model Javy Ada Erlang Zadání Parametrizace vláken 1 task body Monitor_Task_Type is Finish_Flag : Boolean := False; 3 Terminate_Flag : Boolean := False; begin 5 while not Terminate_Flag loop 7 select accept Run; 9 while not (Finish_Flag or Terminate_Flag) loop 11 select accept Stop do 13 Finish_Flag := True; end Stop; 15 else Mon_Proc.all; 17 end select; end loop; 19 or accept Request_Terminate do 21 Terminate_Flag := True; end Request_Terminate; 23 end select; Finish_Flag := False; 25 end loop; end Monitor_Task_Type; 44/73 Paměťový model Javy Ada Erlang Zadání Rendezvous místa synchronizace – předávání dat entry ◾ deklarace rendezvous bodu ◾ in, out, in out parametry accept ◾ implementace v těle tasku 45/73 Paměťový model Javy Ada Erlang Zadání Tasks, Rendezvous procedure Task1 is 2 task Vlakno is 4 entry ZadejX (X : in Integer); entry PrectiX (X : out Integer); 6 end Vlakno; 8 task body Vlakno is Hodnota : Integer; 10 begin accept ZadejX (X : in Integer) do 12 Hodnota := X; end ZadejX; 14 Hodnota := Hodnota + 1; accept PrectiX (X : out Integer) do 16 X := Hodnota; end PrectiX; 18 end Vlakno; 20 Chci_Inkrementovat : Integer; 22 begin Vlakno.ZadejX(Chci_Inkrementovat); 24 Vlakno.PrectiX(Chci_Inkrementovat); end Task1; 46/73 Paměťový model Javy Ada Erlang Zadání Rendezvous select ◾ výběr z více accept možností 1 task body T is begin 3 loop select 5 accept Rande1 do neco; 7 end Rande1; or 9 accept Rande2 do neco; 11 end Rande2; neco; 13 accept Rande3 do neco; 15 end Rande3; or 17 terminate; end loop; 19 end T; 47/73 Paměťový model Javy Ada Erlang Zadání Rendezvous select ◾ časovaný výběr 1 task body T is begin 3 loop select 5 accept Rande1 do neco; 7 end Rande1; or 9 delay 10.0; taky_neco; 11 end select; end loop; 13 end T; 48/73 Paměťový model Javy Ada Erlang Zadání Rendezvous select ◾ časovaný výběr 1 task body T is begin 3 loop select 5 accept Rande1 do neco; 7 end Rande1; else -- ekvivalent "or delay 0.0" 9 null; -- busy waiting end select; 11 end loop; end T; 49/73 Paměťový model Javy Ada Erlang Zadání Rendezvous výjimky během rendezvous ◾ jsou doručeny jak volajícímu vláknu, tak i vlastnímu vláknu ◾ pokud výjimka není ošetřena ve vláknu, je vlákno ukončeno a výjimka se nepropaguje do rodiče (považováno za příliš disruptivní) begin 2 select accept Volani do 4 ... raise Chyba; 6 ... end Volani; 8 end select; exception 10 when Chyba => Naprav_Stav; 12 when other => Oznam_Uzivateli; 14 end; 50/73 Paměťový model Javy Ada Erlang Zadání Rendezvous výjimky během rendezvous ◾ jsou doručeny jak volajícímu vláknu, tak i vlastnímu vláknu ◾ pokud výjimka není ošetřena ve vláknu, je vlákno ukončeno a výjimka se nepropaguje do rodiče (považováno za příliš disruptivní) -- 2 -- 4 begin T.Volani; 6 exception when Chyba => 8 Oznam_Uzivateli; end; 51/73 Paměťový model Javy Ada Erlang Zadání Vnořené Rendezvous možnost vícecestné synchronizace procedure Three_Way is 2 task User; task Device; 4 task Controller is 6 entry Doio (I : out Integer); entry Start; 8 entry Completed (K : Integer); end Controller; 10 task body User is ...; 12 -- includes calls to Controller.Doio(...) task body Device is 14 J : Integer; procedure Read (I : out Integer) is ...; 16 begin loop 18 Controller.Start; Read(J); 20 Controller.Completed(J); end loop; 22 end Device; 52/73 Paměťový model Javy Ada Erlang Zadání Vnořené Rendezvous možnost vícecestné synchronizace task body Controller is 2 begin loop 4 accept Doio (I : out Integer) do accept Start; 6 accept Completed (K : Integer) do I := K; 8 end Completed; end Doio; 10 end loop; end Controller; 12 begin null; 14 end Three_Way; User Controller DeviceController.Doio Controller.Start, Controller.Completed 53/73 Paměťový model Javy Ada Erlang Zadání Chráněné entries u vláken podobně jako u chráněných objektů s mírně odlišnou syntaxí task body Ukazka is 2 Zinicializovano : Boolean := False; Hodnota : Data; 4 begin loop 6 select when Zinicializovano => 8 accept Cti (H : out Data) do H := Hodnota; 10 end; or 12 accept Zapis (H : in Data) do Hodnota := H; 14 end; Zinicializovano := True; 16 end select; end loop; 18 end Ukazka; ◾ podmínka se vyhodnocuje při každém průchodu přes select ◾ pokud není žádná podmínka splněna, je vyhozena výjimka Program_Error (možno použít strukturu select ... else ... end select;) ◾ změna hodnot mezi testem a rendezvous (viz komentář u ’Count) 54/73 Paměťový model Javy Ada Erlang Zadání Atributy vláken Ada 95 Quality and Style Guide, Section 6.2.3 ’Terminated ◾ bezpečné pouze testování na True (po ukončení vlákno nemůže obživnout) ’Callable ◾ bezpečné pouze testování na False (po ukončení vlákno nemůže obživnout) 55/73 Paměťový model Javy Ada Erlang Zadání Atributy vláken Ada 95 Quality and Style Guide, Section 6.2.3 ’Count ◾ chování vlákna by nemělo záviset na tomto atributu (používat raději jen s chráněnými objekty) select 2 when Transmit’Count > 0 and Receive’Count = 0 => accept Transmit; 4 ... or 6 accept Receive; ... 8 end select; stav ’Count se může změnit mezi vyhodnocením a následnou akcí (např. volající použil časově omezené volání a mezi testem a accept se ukončil) ◾ u chráněných objektů: každá práce s frontou je chráněná (viz eggshell model) 56/73 Paměťový model Javy Ada Erlang Zadání Chráněné entries s timeoutem Nelze implementovat pomocí chráněných typů, jsou třeba vlákna task body Ukazka is 2 Zinicializovano : Boolean := False; Hodnota : Data; 4 begin loop 6 select when Zinicializovano => 8 accept Cti (H : out Data) do H := Hodnota; 10 end; or 12 delay 1.0; -- neco 14 end select; end loop; 16 end Ukazka; 57/73 Paměťový model Javy Ada Erlang Zadání Vynucené ukončování vláken Alternativní příklad select 2 T.Ukonci; or 4 delay 180*Seconds; abort T; 6 end select; nebo pokud nevěříme, že se úloha po T.Ukonci ukončí select 2 T.Ukonci; delay 60*Seconds; 4 or delay 180*Seconds; 6 end select; abort T; ◾ pozor na nebezpečí použití abort pragma Restrictions (No_Abort_Statements); ◾ ani druhé řešení není blbuvzdorné (pokud se T.Ukonci může zakousnout v rámci bloku accept, použití requeue) 58/73 Paměťový model Javy Ada Erlang Zadání Asynchronous Transfer of Control Potřeba rychle reagovat na asynchronní události ◾ reakce na chyby (např. výpadek HW, kvůli němuž se akce nikdy nedokončí) ◾ změny režimů v důsledku (neočekávaných) událostí ◾ dosažení co nejlepšího výsledku v případě iterativního přerušitelného výpočtu ◾ přerušení uživatelem 59/73 Paměťový model Javy Ada Erlang Zadání Asynchronous Transfer of Control Struktura select 2 -- triggering_statement delay 5.0; 4 -- post_trigger_part Put_Line ("Tudy cesta nevede!"); 6 then abort -- abortable_part 8 Prevelevelmidlouhe_Volani; end select; ◾ pokud abortable_part doběhne dříve než triggering_statement, pokusí se ukončit triggering_statement ◾ pokud triggering_statement doběhne dřív než abortable_part, je abortable_part ukončena a provede se část post_trigger_part ◾ triggering_statement – v Ada 95 delay/entry, v Ada 2005 i procedury ◾ abortable_part nemusí být implementována jako samostatný task 60/73 Paměťový model Javy Ada Erlang Zadání Asynchronous Transfer of Control Příklad: iterativní dlouhý výpočet, chceme nejlepší odhad v době, kdy jej potřebujeme (J. Barnes, Ada 95) ◾ chráněný objekt na předávání posledního výsledku 1 begin Result is procedure Set_Estimate(X : in Data); 3 function Get_Estimate return Data; private 5 Est : Data; end; ◾ signalizační objekt (např. uživatel chce výsledek) begin Trigger is 2 entry Wait; -- when Flag 4 procedure Signal; private 6 Flag : Boolean := False; end; 61/73 Paměťový model Javy Ada Erlang Zadání Asynchronous Transfer of Control Příklad: iterativní dlouhý výpočet, chceme nejlepší odhad v době, kdy jej potřebujeme (J. Barnes, Ada 95) ◾ použití 1 select Trigger.Wait; 3 then abort Computation; 5 end select; 1 Trigger.Signal; E := Result.Get_Estimate; ◾ oddělení logiky výpočtu od jeho ukončování – výpočet nemusí zjišťovat, kdy má končit 62/73 Paměťový model Javy Ada Erlang Zadání Asynchronous Transfer of Control Výjimky při ATC ◾ pokud se odehraje jen jedna výjimka (v jedné z částí), je možno ji zachytit ◾ pokud se odehrají dvě výjimky současně v řídící i přerušitelné části, je výjimka z přerušitelné části ztracena 63/73 Paměťový model Javy Ada Erlang Zadání Programování v reálném čase Real-Time and Distributed Systems Annex ◾ (dynamické) priority vláken při volání entries ◾ monotónní hodiny s vysokou přesností ◾ restrikce tasků pro speciální případy (Ravenscar profile) ◾ preemptivní abort ◾ mnoho dalšího 64/73 Paměťový model Javy Ada Erlang Zadání Přehled přednášky Paměťový model Javy Ada Erlang Zadání 65/73 Paměťový model Javy Ada Erlang Zadání Erlang: distribuované programování Erlang ◾ funkcionální programovací jazyk pro paralelní a distribuované programování ◾ An Erlang Course http://www.erlang.org/course/course.html ◾ http://www.erlang.org/doc/reference_manual/processes.html ◾ skutečně použitelný: např. ejabberd, zpracování transakcí u Goldman-Sachs Paralelismus na konceptu CSP ◾ komunikující procesy ◾ asynchronní zasílání zpráv ◾ každý proces má svůj „mailbox“ 66/73 Paměťový model Javy Ada Erlang Zadání Erlang: distribuované programování vytvoření procesu spawn(Modul, Exportovana_fce, Seznam_argumentu) předávání zpráv PID_procesu ! zprava receive zprava -> udelej_neco registrace procesů register(nejaky_atom, PID) whereis(registrovane_jmeno) 67/73 Paměťový model Javy Ada Erlang Zadání Erlang: distribuované programování -module (priklad). 2 -compile(export_all). 4 klient(Pid) -> Pid ! {self(),pozadavek,ping}, 6 receive {Pid,odpoved,Odpoved} -> 8 io:format("dorazila odpoved ~p~n",[Odpoved]), Pid ! exit 10 end, io:format("klient skoncil~n"). 12 server() -> 14 receive {Od,pozadavek,Pozadavek} -> 16 io:format("obdrzel jsem pozadavek ~p od ~p~n", [Pozadavek, Od]), 18 sleep(1000), Od ! {self(),odpoved,pong}, 20 server(); _ -> 22 io:format("server skoncil~n") end. 68/73 Paměťový model Javy Ada Erlang Zadání Erlang: distribuované programování sleep(Time) -> 26 receive after Time -> void 28 end. 30 spust() -> Pid = spawn(fun server/0), 32 spawn(fun() -> klient(Pid) end), io:format("spusteni server i klient~n", []). -bash-2.05b$ erl Erlang (BEAM) emulator version 5.5.2 [source] [async-threads:0] [hipe] Eshell V5.5.2 (abort with ^G) 1> c(priklad). {ok,priklad} 2> priklad:spust(). spusteni server i klient obdrzel jsem pozadavek ping od <0.37.0> ok dorazila odpoved pong klient skoncil server skoncil 69/73 Paměťový model Javy Ada Erlang Zadání Erlang: distribuované programování Svázené (linked) procesy link(Pid) -> true spawn_link(Modul, Exportovana_fce, Seznam_argumentu) unlink(Id) -> true ◾ pokud umře proces, pošle o tom zprávu všem, kteří jej mají „nalinkovaný“ {’EXIT’, FromPid, Reason} Monitorování procesů erlang:monitor(process, registrovane_jmeno) ◾ alternativa k použití linků ◾ při ukončení procesu zašle zprávu {’DOWN’, Ref, process, Pid2, Reason} ◾ vícenásobné volání vytvoří více monitorů Zachytávání Exit signálů process_flag(trap_exit,true) ◾ při exitu vygeneruje zprávu jako u linků 70/73 Paměťový model Javy Ada Erlang Zadání Zadání Java – lehká varianta Implementujte paralelní stahování do JOSM editoru: https://josm.openstreetmap.de/ paralelizace stahování File -> Download from OSM -> Raw GPS data paralelizace stahování Download from OSM along this track paralelizace Precache imagery along this trace Poslední dvě položky jsou k dispozici po otevření GPX pomocí kontextového menu a jsou ukázány na screenshotu na následujícím slajdu: File -> Open -> nějaký GPX (např. si stáhněte http://arwen.ics.muni.cz/~hopet/tmp/2013-04-14.gpx) 71/73 Paměťový model Javy Ada Erlang Zadání Zadání Java – lehká varianta 72/73 Paměťový model Javy Ada Erlang Zadání Zadání Java – těžká varianta Druhá možnost, která je složitější na studium, přemýšlení i implementaci, je paralelizace řešiče Choco pro programování s omezujícími podmínkami: http://www.emn.fr/z-info/choco-solver/ Existuje distribuovaná verze zvaná DisChoco http://sourceforge.net/projects/dischoco/ jejíž architektura je popsána v článku Redouane Ezzahir , Christian Bessiere , Mustapha Belaissaoui , Houssine Bouyakhf , U. Mohammed , V Agdal. DisChoco: A platform for distributed constraint programming. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.77.3936 73/73 Paměťový model Javy Ada Erlang Zadání Zadání Java – těžká varianta Nabízejí se dva možné přístupy: koncepty z DisChoco implementovat do zdrojových kódů Choco Solveru, nebo vyjít ze zdrojového kódu DisChoco a nahradit knihovnu "simple agent communication infrastructure (SACI)"za čistě vláknové operace - přičemž druhou možnost považuji osobně za jednodušší.