Operační systémy - modelování a algoritmy paralelních výpočtů

Operační systémy modelování a algoritmy paralelních výpočtů texty pro distanční studium

Doc. Ing. Cyril Klimeš, CSc.

Ostravská univerzita v Ostravě, Přírodovědecká fakulta Katedra informatiky a počítačů

Operační systémy - modelování a algoritmy paralelních výpočtů

OBSAH 1

MEZIPROCESOVÁ KOMUNIKACE A SYNCHRONIZACE .......... 4

2

OBECNÁ PROBLEMATIKA SYNCHRONIZACE ............................ 5

3

METODY GRAFICKÉHO ZNÁZORNĚNÍ PARALELISMU........... 7 3.1 3.2

4

ZNÁZORNĚNÍ POMOCÍ POSTUPOVÉHO PROSTORU ................................. 7 ZNÁZORNĚNÍ POMOCÍ PETRIHO SÍTÍ ..................................................... 8

KLASICKÉ SYNCHRONIZAČNÍ ÚLOHY ....................................... 10 4.1 PRODUCENT - KONZUMENT ................................................................ 10 4.2 ČTENÁŘI – PÍSAŘI (READERS-WRITERS) .............................................. 11 4.3 PROBLÉM HLADOVÝCH FILOZOFŮ (THE DINING PHILOSOPHERS PROBLEM) ..................................................................................................... 13

5 NÁSTROJE MEZIPROCESOVÉ KOMUNIKACE A SYNCHRONIZACE....................................................................................... 15 5.1

VZÁJEMNÁ NEPŘÍSTUPNOST – VZÁJEMNÉ VYHRAZENÍ ČEKÁNÍM NA ČINNOST......................................................................................................... 16

Zákaz přerušení. ....................................................................................... 16 Zamykání pomocí proměnné..................................................................... 16 Přísná výměna. ......................................................................................... 16 Instrukce TSL ............................................................................................ 17 Deadlock – ztuhnutí systému. ................................................................... 18 5.2 KRITICKÉ SEKCE – MUTEXY ............................................................... 19 5.3 DESAKTIVACE A AKTIVACE (SLEEP A WEAKUP) .................................. 20 Semafory ................................................................................................... 21 5.4 UDÁLOST - EVENT .............................................................................. 26 6

KOMUNIKACE MEZI PROCESY...................................................... 30 6.1 6.2 6.3 6.4 6.5 6.6 6.7

SPOLEČNÁ OBLAST PAMĚTI ................................................................ 30 MONITOR ........................................................................................... 30 ZASÍLÁNÍ ZPRÁV A SIGNÁLY .............................................................. 32 POŠTOVNÍ SCHRÁNKA – MAILBOX ....................................................... 33 SETKÁNÍ – SOUBĚH (RENDEVOUS) ...................................................... 34 ALARMY, ČASOVAČE ......................................................................... 35 ROURA (PIPE) .................................................................................... 36

7 POUŽITÍ VLASTNOSTI PROSTŘEDKŮ MEZIPROCESOVÉ SYNCHRONIZACE....................................................................................... 38 8

PŘÍLOHA................................................................................................ 40 8.1 PETRIHO SÍTĚ ..................................................................................... 40 Analýza Petriho sítě.................................................................................. 42 Klasické techniky analýzy Petriho sítí ...................................................... 44 Modifikované Petriho sítě......................................................................... 47 8.2 IF THEN PRAVIDLA .......................................................................... 49 8.3 SIMULÁTOR PETRIHO SÍTÍ HPSIM ...................................................... 54 Menu File.................................................................................................. 55 Menu Edit ................................................................................................. 55 Menu View ................................................................................................ 56

2

Operační systémy - modelování a algoritmy paralelních výpočtů Menu Tools................................................................................................56 Menu Simulation .......................................................................................57 Menu Extra - nastavení editoru.................................................................58

3


1 Meziprocesová komunikace a synchronizace V mnoha operačních systémech může současně běžet mnoho procesů a v systému může existovat mnoho instancí jednoho programu (jeden program může být spuštěn několikrát současně). Každý proces má vyhrazen svůj paměťový prostor a k systémovým prostředkům přistupuje prostřednictvím volání jádra operačního systému. Současný běh několika různých procesů je typickým rysem pro aplikace v reálném čase. Tyto procesy mohou být navzájem nezávislé nebo nějakým způsobem může záviset běh jednoho procesu na běhu jiného procesu. Běh jednoho procesu má tedy vliv na běh druhého a naopak. Potom vyvstává potřeba mít k dispozici mechanismy pro: • synchronizaci dvou nebo více procesů navzájem, • předávání dat mezi procesy. Často jsou tyto dva mechanismy kombinovány. Například pokud jeden proces požaduje data po druhém procesu, musí čekat dokud nejsou data dostupná, teprve potom může dojít k jejich výměně. Procesy, které spolu navzájem komunikují, mohou přímo sdílet adresový prostor nebo mohou ke své komunikaci využívat sdílených souborů nebo paměťových modulů. Protože přístup jednotlivých procesů k těmto datům je asynchronní, může vést k narušení jejich konzistence. Aby k tomuto narušení nedošlo, je nutné vhodnými prostředky operačního systému zajistit koordinovaný přístup jednotlivých procesů k těmto sdíleným prostředkům. Tento koordinovaný přístup však znamená určitá omezení pro procesy, které k těmto datům přistupují. Omezení spočívá především v tom, že proces nemůže sdílená data měnit kdykoli, ale pouze se souhlasem ostatních procesů, případně operačního systému. Nezbytným požadavkem pro zajištění komunikace mezi procesy je sdílení a ochrana prostředků – zdrojů. Při sdílení prostředků se budeme zabývat problematikou: • kritických sekcí – úseky programů, kdy se sdílenými prostředky proces komunikuje, • zastavením činnosti systému (ztuhnutím) – deadlock – kdy zdroje jsou chybně chráněny proti současnému přístupu. • •

Při komunikaci s prostředky je nutno dodržet určitá pravidla: pouze jeden proces v daném čase může mít přístup k chráněnému prostředku – zdroji, procesy zůstávají vzájemně nezávislé, zastavení jednoho procesu neovlivní zpracování ostatních procesů.

U procesů je nutné zajisti: • bezpečnost, • životaschopnost.

4


2 Obecná problematika synchronizace Nekoordinovaný přístup ke sdíleným prostředkům může vést k častým chybám. Odstranění těchto chyb je možné provést synchronizací přístupu procesů ke sdíleným objektům. Přístup ke sdíleným prostředkům bude regulérní, pokud budou tyto procesy splňovat Bernsteinovy podmínky, tedy aby sdílené prostředky jednotlivých procesů byly použity pouze pro operace čtení. V praxi tyto Bernsteinovy podmínky znamenají tak velké omezení, že jsou pro mnoho úloh nesplnitelné a málokdy se používají. Pokud však procesy Bernsteinovy podmínky důsledně splňují, konzistence sdílených dat je zaručena. U procesů, které nesplňují Bernsteinovy podmínky, je nutno zajistit konzistenci dat jiným způsobem. Pro ukázku jak mohou vypadat procesy, které tyto podmínky nesplňují, poslouží následující příklad. Mějme dva procesy P1 a P2 sdílející společnou proměnnou. Proces P1 čte cyklicky každou sekundu hodnoty z A/D převodníku a provádí jejich součet. Proces P2 po 1 min. tento součet zobrazí. #define ADRESA _PORTU 0x300 ……………. int Soucet; while (1) { Soucet += inp (ADRESA_PORTU); Sleep(1000; } …………….. ……………. while (1) { printf ( “Soucet je %d/n”, Soucet); // Proces P2 Soucet = 0; Sleep (60000); } ………………. Jak můžeme vidět, procesy Bernsteinovy podmínky nesplňují, protože oba zapisují do proměnné Soucet. V případě, že procesy budou běžet v operačním systému s preemptivním plánovačem, tedy k přepnutí procesů může dojít po skončení kterékoliv strojové instrukce, může dojít k nastavení chybné hodnoty proměnné Soucet. Možná implementace příkazu: Soucet += inp (ADRESA_PORTU); může být následující: registrl = inp(ADRESA_PORTU); registrl = regitrl + Soucet; Soucet = registrl;

5

Operační systémy - modelování a algoritmy paralelních výpočtů Potom příznaky printf (“Soucet je % d/n “, Soucet), Soucet += inp (ADRESA_PORTU; a Soucet = 0; mohou být provedeny např. v takovémto sledu: printf (“Soucet je % d/n “, Soucet); P2 registrl = inp(ADRESA_PORTU); P1 registrl = registrl + Soucet; P1 Soucet = 0; P2 Soucet = registrl; P1 Je zřejmé, že příkaz vynulování proměnné Soucet po jejím zobrazení se neprojeví. Při následujícím sledu příkazů se zase neprojeví čtení hodnoty z A/D převodníku. printf (“Soucet je % d/n “, Soucet); P2 registrl = inp(ADRESA_PORTU); P1 registrl = registrl + Soucet; P1 Soucet = registrl; P1 Soucet = 0; P2 Odstranění těchto chyb je možné pomocí synchronizačních nástrojů. Tedy v použití koordinovaného přístupu ke sdíleným prostředkům. Pokud procesy nesplňují Bernsteinovy podmínky, je třeba vždy analyzovat možné kolize a ty potom odstranit synchronizačními nástroji. Procesy sdílí nějakou společnou oblast operační paměti, soubor nebo jiný systémový prostředek - zdroj. Pro využití tohoto systémového prostředku platí soutěžní podmínky. Příkladem může být spolupráce procesů s jedním V/V zařízením – tiskový spoiler (Simultaneous Periphrial Operations On Line) Sdílení prostředků definuje nalezení cesty, jak zakázat více než jednomu procesu zápis nebo čtení sdílených dat v daném časovém okamžiku. Problém stanovení soutěžních podmínek může být také formulován abstraktní cestou. Ta část programu, kde je požadován přístup k sdíleným prostředkům se nazývá kritická sekce. Je potřeba určit způsob, jak dva procesy mohou být ve svých kritických sekcích současně – soutěžní podmínky. Spolupráce paralelních procesů musí být korektní a musí efektivně využívat sdílená data. Je potřeba splnit 4 podmínky: • • • •

6

žádné dva procesy nesmí být současně uvnitř svých kritických sekcí, nejsou žádné předpoklady o relativní rychlosti procesu nebo počtu CDU, žáden proces běžící mimo svou kritickou sekci neblokuje jiné procesy, žáden proces by neměl čekat neomezeně dlouho na vstup do své kritické sekce.


3 Metody grafického znázornění paralelismu Slovní vyjádření problémů synchronizace procesů není někdy dostačující a přesné. Pro lepší a názornější představu o možných kolizích bývá vhodné použít pro rozkreslení běhu procesů některé grafické metody. Jednou z možností grafického vyjádření je použití postupového prostoru. Tato metoda umožňuje přehledně graficky znázornit zakázané sekce, do kterých se procesy při běhu mohou dostat. Tento způsob je však použitelný pouze pro dva, maximálně tři procesy. Při větším počtu procesů je vhodné pro grafické znázornění jejich toku a synchronizace použití Petriho sítí.

3.1 Znázornění pomocí postupového prostoru Postupový prostor dvou procesů je znázorněn kartézskou soustavou souřadnic, kde každá osa je přiřazena právě jednomu procesu. Obecně má postupový prostor dimenzi n, kde n je počet procesů, které znázorňuje. To je důvod, proč tohoto grafického znázornění lze použít maximálně pro tři procesy. Na obrázku 18 je vidět postupový prostor procesů vedených v předchozím příkladu. Osa x je přiřazena procesu P1, osa y pak procesu P2. Paralelnímu běhu procesů zde odpovídá postupová cesta. Každý bod této postupové cesty ukazuje pozici, ve které se běh daného procesu nachází. Tvar postupové cesty závisí na přepínání kontextu. U jednoprocesorového systému je postupová cesta složena z pravoúhlých úseček. Obecně má tvar neklesající funkce. Vyznačený obdélník určuje zakázanou sekci – oblast, kterou by postupová cesta neměla projít. V praxi to znamená, že v době průchodu postupové cesty kolem hrany zakázané sekce nesmí dojít k přepnutí mezi procesy, jichž se tato postupová cesta týká (přepnutí jiného procesu nemá vliv). Z takového grafického vyjádření pak máme velmi přesnou představu o umístění synchronizačních nástrojů, které zamezí nežádoucímu přepnutí kontextu, tedy k nekoordinovanému přístupu jednotlivých procesů ke sdíleným prostředkům.

7


Sleep

P2

Print

S=0

Postupová cena

Sleep

Zakázaná oblast

Sleep

P(port) reg.=reg.+S S=reg.

Sleep

P1

Obr. 1. Znázornění běhu aplikací pomocí postupového prostoru

3.2 Znázornění pomocí Petriho sítí Výhodnějším modelem znázornění paralelního běhu aplikací se jeví použití Petriho sítí. V příloze tohoto textu jsou vysvětleny základní definice Petriho sítí. Na obrázku 2 je vidět znázornění paralelního běhu dvou procesů pomocí Petriho sítě. Petriho síť lze znázornit grafem, obsahujícím tři typy prvků: Grafy sestávající ze tří typů prvků: • uzly – umožňují popsat stavy systému, v programu odpovídají jednotlivým příkazům, • přechody – modelují možnost změny stavu systému, • orientované hrany – propojují uzly a přechody, definují cesty.

8


A

KSP

B

C

KS Q

D

Obr. 2 Zázornění běhu aplikací pomocí Petriho sítě (problém kritické sekce) Pro znázornění běhu programu se využívá tzv. značené Petriho sítě. Každému prvku v síti je přidělen určitý počet značek, které jsou realizovány černými tečkami. Běh programu je znázorňován posunem černých teček jednotlivými uzly. Postup z jednoho uzlu do druhého lze provést, jestliže je splněna podmínka přechodu mezi nimi – přechod je otevřen. Přechod je otevřen, jestliže všechny prvky, které do přechodu vstupují, obsahují alespoň tolik teček, kolik z něj vystupuje. Otevření přechodu způsobí v síti změnu značkování. Změna značkování probíhá následujícím způsobem: • z každého uzlu je odebráno tolik teček, kolik je přiřazeno hranám do následujícího přechodu, • do každého uzlu je předáno tolik teček, kolik do něj vstupuje s orientovanými hranami z přechodů. Paralelní běh procesů se v grafu projeví existencí více teček. Petriho sítí je možné snadno vyjádřit konkrétní část programu, kde vznikají požadavky na synchronizaci procesů. Oproti postupovému prostoru lze Petriho sítě použít i pro znázornění více procesů. Pro popis celého běhu paralelních aplikací je však potřeba zachytit pohyb tečky všemi místy grafu. To bývá zvláště u složitějších procesů velmi náročné. Ke znázornění běhu

9

Operační systémy - modelování a algoritmy paralelních výpočtů aplikace pomocí Petriho sítí se často používá simulace pomocí programů navržených k těmto účelům.

4 Klasické synchronizační úlohy Pro detailnější popis problematiky synchronizace procesů budou v následujících odstavcích popsány klasické problémy, se kterými se lze při vytváření paralelních aplikací skoro vždy setkat. Každý příklad synchronizační úlohy je znázorněn Petriho sítí.

4.1 Producent - konzument Někdy tato úloha také bývá nazývána jako problém omezené vyrovnávací paměti- bufferu. Jedná se o jednosměrnou asynchronní komunikaci mezi procesy pomocí úseku paměti omezené délky (omezeného bufferu). Producent zapisuje položky do tohoto bufferu, konzument položky naopak odebírá. Ve vztahu producent-konzument můžeme také najít určitou symetrii. Při obecnějším pohledu na tuto úlohu lze říci, že producent produkuje plné položky pro příjemce, naopak konzument vytváří prázdné položky pro producenta. Asynchronní přístup zde znamená, že oba pracují nezávisle na sobě. Pokud je buffer prázdný (neexistují plné položky), je konzument nucen čekat, pokud je naopak buffer plný (neexistují prázdné položky), je producent nucen čekat. Jejich činnost však musí být synchronizována. Ve znázornění pomocí Petriho sítě je použito dvou uzlů znázorňujících prázdné a plné položky. Součet teček v obou těchto uzlech (prázdné a plné) udává kapacitu bufferu.

produce_data

S_empty

S_full

insert_data into_ buffer

remove_data From buffer

consume_data

producent Obr. 3. Producent - konzument

10

konzument

Operační systémy - modelování a algoritmy paralelních výpočtů Pohyb teček v grafu probíhá následujícím způsobem: • Producent před zápisem položek odebere jednu tečku z uzlu prázdné a po zápisu přidá jednu tečku do uzlu plné. • Konzument naopak před odebráním vyjme jednu tečku z uzlu plné a po odebrání přidá jednu tečku do uzlu prázdné. Úloha producent-konzument má praktické uplatnění všude tam, kde spolu procesy komunikují asynchronně, při vyrovnávání rychlostí produkce a zpracování dat. Příkladem takové úlohy v měřící aplikaci může být např. komunikace mezi procesem zajišťujícím kontinuální vzorkování z A/D převodníku a procesem zajišťujícím odesílání dat do jiného počítače ke zpracování pomocí rozhraní Ethernet. Kontinuální vzorkování představuje producenta, odesílání dat po komunikačním médiu konzumenta. Rychlost producenta je stále stejná, rychlost konzumenta může být velmi rozdílná v závislosti na zatížení Ethernetu. Výpadky v komunikaci jsou pak odstraněny pomocí vyrovnávacího bufferu. Obecně, čím větší je velikost bufferu, tím větší mohou být výpadky v komunikaci. Aby nedocházelo k zaplňování bufferu, musí být průměrná rychlost odebírání položek větší nebo rovna rychlosti zápisu těchto položek.

4.2 Čtenáři – písaři (Readers-Writers) Tato úloha se objevuje v procesech sdílejících společné datové struktury. Některé procesy tato data modifikují – písaři a některé procesy z těchto dat pouze čtou – čtenáři. Synchronizace mezi těmito procesy musí respektovat následující pravidla: • pokud písař data zapisuje, nesmí zapisovat žádný jiný písař, • pokud písař data zapisuje, nesmí tato data číst žádný čtenář, • pokud čtenář data čte, nesmí do nich žádný písař zapisovat, • pokud čtenář data čte, může libovolný jiný čtenář tato data číst také. Čtení může být tedy povoleno více čtenářům najednou, zápis v daném čase může provádět pouze jeden písař, ostatní písaři i čtenáři musí čekat na ukončení operací tohoto písaře. Model této úlohy Petriho sítí (obr.4 a 5) vypadá následovně: • Každý čtenář odebere před operací čtení z kontrolního uzlu jednu tečku. Po ukončení čtení tuto tečku vrátí zpět do kontrolního uzlu. • Každý písař čeká na dokončení operací všech čtenářů nebo jiného písaře a před operací zápisu z kontrolního uzlu odebere všechny tečky (znemožní jakékoli další čtení nebo zápis). Po ukončení zápisu vrátí všechny tyto tečky zpět do kontrolního uzlu. • Celkový počet teček odpovídá maximálnímu počtu čtenářů (č max).

11


Čtenář 1

čtení ……..

Čtenář 4

Zapisovatel

čtení

zápis

Obr. 4 Čtenáři - Písaři

Čtenář 1

Čtenář 4

čtení čtení čtení čtení

Obr. 5 Čtenáři - Písaři 12

Zapisovatel

zápis

Operační systémy - modelování a algoritmy paralelních výpočtů Z načrtnutého schématu jsou vidět možné problémy při řešení této úlohy. Může dojít k umoření písaře vlivem velmi dlouhé doby čekání na ukončení operací čtenářů. Čtenáři se mohou postupně střídat, takže jejich operace nemusí nikdy skončit. Při žádosti písaře o zápis je tedy třeba zajistit, aby žádný čtenář nezačal se sdílenými daty pracovat.

4.3 Problém hladových filozofů (The Dining Philosophers Problem) Představme si pět filozofů sedících okolo kulatého stolu. Všechen svůj čas tráví přemýšlením nebo jedením.U každého filozofa je miska rýže. Zprava i zleva má filosof k dispozici jednu hůlku ke konzumaci rýže. Hůlky musí filozofové sdílet, neboť mezi nimi je vždy jenom jedna. Filozof, pokud se chce najíst, musí se zmocnit hůlek po své pravé i levé ruce (jednou hůlkou se nenají, jiné jsou pro něj příliš daleko). V danou chvíli může filozof sebrat pouze jednu hůlku (každý filozof pracuje sekvenčně, takže nemůže vzít obě najednou). Pokud má obě hůlky, může se nasytit, poté odložit hůlky a dál přemýšlet. Pokud jsou hůlky používány, je nucen čekat až je sousední filozofové uvolní. Model této úlohy pomocí Petriho sítě je znázorněn na obrázku 22. Filozofové jsou zde označeni čísly 1 až 5, hůlky jsou prezentovány jako sdílené objekty S. Filozofové se mohou nacházet ve třech stavech: čekání na hůlky, jedení, přemýšlení.

F5

Filosof

F4

F1

talíř

vidlička problém

F2

F3

Obr. 6. Problém hladových filozofů

13


Při řešení této úlohy je třeba zajistit, aby se každý filozof občas najedl a neumřel hlady. Může také dojít k zablokování všech, např. pokud všichni uchopí hůlku po své pravé ruce, hůlky po své levé ruce by se potom nedočkali.

čeká

čeká S

jí

čeká S

jí

přemýšlí

čeká S

jí

přemýšlí

čeká S

jí

přemýšlí

S

jí

přemýšlí

přemýšlí

Obr. 7 Problém hladových filozofů – model pomocí Petriho sítě Úlohu lze řešit např.: • snížením počtu filozofů při zachování stejného počtu hůlek, • dovolit filozofovi vzít hůlku pouze tehdy, jsou-li volné obě, • řešit asymetricky přístup k hůlkám, lichý filozof by uchopil nejprve levou hůlku a pak pravou, sudý filozof naopak. Pokud bude úloha vyřešena jedním z výše uvedených způsobů nedojde k jejímu zablokování.

14


5 Nástroje meziprocesové komunikace a synchronizace Operační systémy, které podporují paralelní běh více procesů zpravidla obsahují synchronizační nástroje, pomocí kterých lze výše uvedené synchronizační úlohy vyřešit. Tyto nástroje se ve větších nebo menších obměnách vyskytují ve všech současných operačních systémech, které paralelní běh více aplikací podporují, a lze je rozdělit do několika skupin popsaných v následujících odstavcích. Jednotlivé nástroje si jsou v zásadě velmi podobné, různé charakteristiky jejich chování jsou určujícím faktorem pro jejich nasazení do různých aplikací. Obecně řečeno, tyto nástroje zajišťují koordinovaný postup jednotlivých procesů ke sdíleným prostředkům (proměnným, souborům, atd.). Tento koordinovaný přístup jde vždy na úkor efektivity běhu aplikací, neboť jednotlivé procesy jsou nuceny čekat na pokyny, které jim dovolí pokračovat ve svém zpracování. Aby například nedošlo ke ztrátě konzistence sdílených dat, je nutné zajistit vzájemně jednoznačný přístup k těmto datům. Pokud možno tak, aby nedošlo ke ztrátě efektivity běhu aplikací. Použití synchronizačních nástrojů podporovaných operačním systémem umožňuje efektivnější sestavení aplikací. Jednotlivé procesy nemusí trávit čas v dotazovacích smyčkách, kde zjišťují stav sdílených proměnných, jejichž hodnoty signalizují k čemu v systému došlo. Namísto toho mohou být ve stavu čekání na aktivaci prostřednictvím nějakého synchronizačního nástroje. Neubírají tedy zbytečně čas procesoru, který může být využit pro jiné činnosti. Mohlo by se říci, že nejlepší způsob návrhu aplikace je tedy ten, kdy jednotlivé procesy nedělají vůbec nic dokud v systému nedojde k něčemu, co by je mohlo zajímat. Tento přístup nemusí být vždy nejefektivnější. Například v multiprocesorových systémech může být naopak výhodné nechat jednotlivé procesy, běžící na různých procesorech, probíhat v cyklech jejich kódu. V takovém případě při aktivaci nedochází k přepnutí kontextu, které může znamenat významnou časovou prodlevu. Jednotlivé procesy potom běží v dotazovacích smyčkách a uvedený způsob synchronizace se nazývá kruhové blokování – spinlock. Například dvě aplikace (označme A,B) sdílejí velký blok dat. Provádí-li aplikace A v tomto bloku změnu, je z důvodu zachování konzistence těchto dat nutné uzamknout tento blok pro zápis aplikace B (úloha čtenář-písař). Aplikace B je tedy nucena čekat i v případě, že bude manipulovat se zcela jinou částí sdíleného bloku než aplikace A, což by při logické úvaze vůbec nemusela. Z hlediska efektivity je tedy vhodnější rozdělit tento blok na několik nezávislých částí a k těmto částem přistupovat samostatně.

15


5.1 Vzájemná nepřístupnost – vzájemné vyhrazení čekáním na činnost Zatímco jeden proces je činný v příslušné sdílené paměti ve své kritické sekci, žádný jiný proces nebude vstupovat do své kritické sekce, aby způsobil problémy při zpracování sdílených dat. Tuto úlohu můžeme řešit několika způsoby: Zákaz přerušení. Je to nejjednodušší řešení. Po vstupu do své kritické sekce proces zakáže přerušení-hardwarové zamknutí. Nemůže však vzniknout ani přerušení od hodin a procesor nemůže přepínat žádné procesy. Používá se proto pouze v jádře operačního systému a je omezeno na několik instrukcí např. pro uložení registrů, aktualizaci proměnných nebo seznamů. Nedá se použít jako mechanizmus vzájemného vyhrazení mezi uživatelskými procesy. Zamykání pomocí proměnné. Druhé řešení vzájemné nepřístupnosti je softwarové zamknutí. K zamykání je použita jednoduchá sdílená proměnná, která je na počátku ve stavu“0“-false. Jestliže proces vstupuje do své kritické sekce, bude se nejprve testovat zamknutí této proměnné. Jestliže je proměnná ve stavu“0“nastaví se proměnná na“I“- true a proces vstoupí do své kritické sekce. Jestliže je proměnná ve stavu“I“, bude proces čekat tak dlouho, dokud se její stav nezmění na “0“. To znamená, že“0“ indikuje, že žádný proces není v kritické sekci. Přísná výměna. Třetím způsobem vzájemného vyhrazení je metoda přísné výměny. Celočíselná proměnná f1 kontroluje přístup do kritické sekce. Na začátku proces0 zkoumá stav proměnné f1. Při zjištění, že je ve stavu “0“(false), stoupí do kritické sekce. Proces1 rovněž zjistí, že je f1 ve stavu “0“(false), ale testuje ji dále ve smyčce, dokud se f1 nedostane do stavu“1“(true). Nepřetržité testování proměnné, čekání na příslušnou hodnotu až se nastaví, se nazývá čekání na činnost (busy waiting). Může se použít při dostatečném volném času procesoru. Příklad: while (true) { while (f1 !=0) / * čekání */ critical_section ( ); f1 =1; noncritical_section; } ... while (true) { while (f1 ! =1) / * čekání */ critical_section ( ); f1 =0;

16

Operační systémy - modelování a algoritmy paralelních výpočtů noncritical_section; } Uvedený způsob ovšem není požadovaným řešením problému. Lepší algoritmus lze dostat použitím dvou proměnných f1 a f2. Může ovšem vést k situaci ztuhnutí procesů tzv. deadlock. Hodnota false je přiřazena k f1 a f2 před testem f1 = true a f2 = true. Deadlock a současný přístup k zablokovanému (chráněnému) prostředku jsou dva symetrické problémy vztažené na extrémní situace. Problém lze řešit třemi proměnnými f1, f2 a f3. Algoritmus Dekker – Dijstra nebo Petrsonovo řešení. Příklad: #define FALSE 0 #define TRUE 1 #define N2 / * počet procesů */ int f1; / * který f1 je to * / int f2 [N]; / * všechny poč. hod. 0 * / enter_region (process) int process; / * proces číslo 0 nebo 1 */ { int other; / * číslo jiného procesu * / other= 1 – process; / * opačný process * / f 2[process] = TRUE; / * potvrzení zájmu * / f 1 = process; / * nastavení flegu * / while ( f1 = = process & & f2 [other] = =TRUE) / * nulování * / } leave_region (process) int process; / * proces opouští kritickou sekci */ { f2 [process] = FALSE; / * indikace odchodu z kritické sekce */ } Instrukce TSL Problém lze rovněž řešit s využitím hardwaru. Instrukce TSL („test and set lock“) nebo TAS („test nad set“) pracuje následovně. Přečte obsah paměťového slova v registru a pak uloží nenulovou hodnotu na tuto paměťovou desku. Takto operace čtení slova a jeho uložení je nedělitelná. Žádný jiný proces nemá přístup k příslušnému paměťovému slovu, dokud instrukce neskončí. Procesor při zpracování instrukce TSL zamkne paměťovou sběrnici, aby zabránil ostatním procesorům přístup k paměti, dokud instrukce není ukončena. Při použití instrukce TSL je využita sdílená proměnná flag pro koordinaci přístupu ke sdílené paměti. Je-li flag roven“0“, může každý proces nastavit flag na“1“ použitím instrukce TSL a pak číst nebo zapisovat do sdílené paměti. Po ukončení operace nastaví proces flag zpět na“0“ např. použitím instrukce mov.

17


Příklad: enter_region: tsl register, flag na1 cmp register, #0 jnz enter_region ret sekce leave_region: mov flag, #0 ret

kopie flagu do registru a nastavení flagu je flag nula není-li nula, zamknutí, smyčka návrat k volajícímu, vstup do kritické uložení 0 do flagu návrat k volajícímu

Pravidla pro přístup ke kritické sekci: o když proces hodlá vstoupit do kritické sekce, dostane povolení to udělat, ovšem v konečném čase, o pouze jeden proces v daném okamžiku může vstoupit nebo pobývat v kritické sekci, o proces zůstává v kritické sekci konečnou a přesně stanovenou dobu. Deadlock – ztuhnutí systému. Některé nebo všechny procesy v systému čekají na nějakou událost. Všechny procesy mohou čekat nekonečně dlouho v podmínce dedlock. Jiný případ deadlocku nastane tehdy, jestliže všechny procesy běží, ale nevykazují žádný pokrok (obr. 23). Procesy stále testují podmínku, která se nemění. Pro vznik deadlocku je nutné splnit několik podmínek, nejsou-li splněny nemůže nastat: o Současný přístup. V systému jsou prostředky, které mohou být použity v daném časovém okamžiku pouze jedním procesem. o Nepremptivní vyhrazení. Prostředek může být uvolněn pouze procesem, který si jej vyhradil. o Postupné vyhrazení. Proces si může vyhradit potřebné prostředky v daném čase. o Vyhrazení v opačném pořadí. Procesy si mohou vyhradit prostředky v opačném pořadí.

18


Obr. 8 Znázornění deadlocku situací na křižovatce Tyto čtyři principy mohou způsobit deadlock. Čtvrtý případ vede k deadlocku nejsnadněji, první proces požaduje prostředky v pořadí A – B, druhý proces požaduje prostředky v opačném pořadí B – A. První čeká na uvolnění B a druhý na uvolnění A v nekonečné smyčce. Procesy nevykazují žáden pokrok.

5.2 Kritické sekce – mutexy Problém kritické sekce je ve své podstatě naznačen v předcházejícím textu při výkladu obecné problematiky synchronizace. Kritická sekce je také naznačena při výkladu grafického znázornění paralelismu. Kritická sekce je část běhu procesu, ve kterém je nežádoucí běh procesu jiného, který by mohl negativně ovlivnit běh procesu původního (porušení konsistence sdílených dat, nekoordinovaný přístup ke sdílené proměnné apod.). Problém kritické sekce tedy spočívá v zákazu běhu procesů, které by toto mohly provést. Nebo obecněji, pouze jejich části, která toto může provést. Grafické znázornění kritické sekce pomocí postupového prostoru je uvedeno na obrázku 18, pomocí Petriho sítě na obrázku 19. Kritickou sekcí je část kódu procesu, která přistupuje je sdíleným prostředkům (společné proměnné, soubory, atd.). Ve vyjádření běhu aplikace pomocí postupového prostoru musí každá aplikace tuto část projít mimo tzv. zakázanou sekci – oblast. Přístup k těmto prostředkům v daném čase musí mít vždy maximálně jeden proces. Je tedy nutné zajistit vzájemné vyhrazení (mutual exclusion) přístup k těmto prostředkům. Každý proces, který obsahuje kritickou sekci, by měl obsahovat následující část kódu: ....... Entry (Critical_Section); / * Cekani na prideleni prava vykonat svou kritickou sekci * / ....... / * Vykonani sve kriticke sekce * / Leave (Critical Section); / * Uvolneni kriticke sekce * / 19

Operační systémy - modelování a algoritmy paralelních výpočtů ....... Nástroje jednotlivých operačních systémů pro vyřešení problému kritické sekce mohou být v implementaci různé. Zpravidla se jedná o nejjednodušší synchronizační nástroj, který je v daném operačním systému k dispozici. Je charakteristický tím, že je binární. Kritická sekce (mutex) je buď signalizována anebo není. Tím je jasně dáno, zda je sdílený prostředek obsazen nebo je volný. Každý proces, který chce vykonat svou kritickou sekci, musí čekat na uvolnění sdíleného prostředku – kritické sekce (mutexu) a po skončení tento objekt uvolnit. Na implementaci v konkrétním operačním sytému potom závisí, je-li možné nastavit maximální dobu čekání (timeout) na přidělení kritické sekce (mutexu) a zamezit tak zatuhnutí procesu (deadlock). Zda se objekt, zajišťující tento způsob synchronizace, nazývá kritická sekce, mutex, nebo zcela jinak, závisí na implementaci. Důležitá je vlastnost, že operační systém zajistí přidělení tohoto objektu v daném čase vždy maximálně jednomu procesu.

5.3 Desaktivace a aktivace (sleep a weakup) Dvojice nepřerušitelných systémových volání sleep a weakup umožňuje přístup do kritické sekce. Sleep je systémové volání, umožňující blokování, tj. proces bude suspendován, dokud jej jiný proces neaktivuje. Volání wakeup má jeden parametr, proces je aktivován. Alternativně oba sleep i wakeup mají jeden parametr, paměťová adresa je použita pro prohození volání sleep a wakeup. Lze použít pro problém komunikace mezi producentem a konzumentem. Příklad: #define N 100 /* počet buněk v bufferu */ int count = 0; /* počet položek v bufferu */ producer ( ) { while (TRUE) { produce_item ( ); /* generace další položky */ if ( count = = N) sleep ( ); /* jestliže je buffer plný desaktivace */ enter_item ( ); /* vložení položky do bufferu */ count = count + 1; /* přírustek čitače položek v bufferu */ if (count = = 1) wakeup (consumer);/* byl buffer prázdný? */ } } consumer ( ) { while (TRUE) { if (count = = 0) sleep ( ); /* jestliže je buffe prázdný desaktivace */

20

Operační systémy - modelování a algoritmy paralelních výpočtů remove_item ( ); count = count – 1;

/* vezmi položku z bufferu */ /* ubýtek čitače položek v bufferu

*/ if (count = = N – 1) wakeup (producer); /* byl buffer plný? */ consume_item ( ); /* tisk položky */ } } Semafory Synchronizační nástroj typu semafor je tvořen proměnnou, která může nabývat hodnotu vždy větší nebo rovnou nule (definoval Djjkstra v r. 1965). Práce s objektem typu semafor umožňuje tři operace: • inicializace semaforu, nastavení proměnné na počáteční hodnotu, • čekání procesu na přidělení semaforu a jeho dekrementace, • inkrementace semaforu. Poslední dvě jmenované operace jsou atomické, což znamená, že tyto operace může provádět v daném čase pouze jeden proces. Semafor se typicky používá pro sledování volných prostředků. Zjednodušené použití semaforu bude ukázáno na řešení úlohy producentkonzument (obr. 20). Při řešení této úlohy se využívá dvou semaforů (PRAZDNE, PLNE), které jsou používány pouze těmito dvěma procesy. Úloha spravuje vyrovnávací paměť (BUFFER) o kapacitě N prvků. Na začátku je semafor PRAZDNE inicializován na hodnotu N, semafor PLNE na hodnotu nula. Semafory zajišťují, aby producent nemohl zapisovat prvky do plného bufferu a konzument nemohl číst prvky z prázdného bufferu. •

•

Celá úloha probíhá následujícím způsobem: Producent čeká na semafor PRAZDNE, je-li tento semafor větší než nula (v paměti BUFFER jsou k dispozici prázdné prvky), zapisuje jeden prvek a inkrementuje semafor PLNE (dává najevo, že v paměti BUFFER je o jeden prvek více). Konzument čeká na semafor PLNE, je-li tento semafor větší než nula (v paměti BUFFER jsou k dispozici plné prvky), čte jeden prvek a inkrementuje semafor PRAZDNE (dává najevo, že v paměti BUFFER je o jeden prvek méně).

Dojde-li k situaci, kdy semafor PRAZDNE nabude hodnoty nula (BUFFER je zcela zaplněn), producent je nucen čekat na přidělení alespoň jednoho prvku ze strany konzumenta (inkrementace semaforu PRAZDEN). Totéž platí analogicky i v případě konzumenta. Kód úlohy producent-konzument potom vypadá následujícím způsobem: .....

21

Operační systémy - modelování a algoritmy paralelních výpočtů Init_Sema(PRAZDNE, N) /* Inicializace semaforu PRAZDNE* / Init_Sema (PLNE, 0); /* inicializace semaforu PLNE* / ..... /* kod producenta */ ...... while (TRUE) do (Wait_Sema(PRAZDNE)) /* Cekani a nasledna PRAZDNE */ dekrementace semaforu { Write (BUFFER, Prvek); /* Zapis prvku do bufferu* / Signal_Sema (PLNE); /* Inkrementace semaforu PLNE*/ } ..... /* kod konzumenta */ ..... while (TRUE) do (wait_Sema (PLNE)); /*Cekani a nasledna PRAZDNE*/ dekrementace semaforu { Read (BUFFER, Prvek); /*Cteni prvku z bufferu*/ Signal_Sema (PRAZDNE); /*Inkremetnace semaforu PRAZDNE*/ ...... Oproti kritickým sekcím – mutexům se implementace semaforu v základní podobě v různých operačních systémech příliš neliší. Rozdíl v implementaci může být např. opět v možnosti nastavení maximální doby čekání (timeout) na přidělení semaforu. Některé operační systémy (např. OS9) podporují semafory pouze v binární formě. Aplikace binárních semaforů se potom spíše podobá aplikaci kritické sekce nebo mutexu než semaforu v jeho klasické podobě. Jádrem problému ochrany sdílených prostředků je operace kontroly a změny hodnoty proměnné, jejich oddělení a přerušení v čase. Nepřetržité testování hodnot proměnných zabírá příliš mnoho času procesoru. Semafory byly doporučeny již Dijkstrou jako základní synchronizační princip pro překlenutí problémů s ochrannými proměnnými. Semafor je nejpoužívanější metoda pro synchronizaci procesů. Semafory definují dvě operace, systémová volání, které mohou mít podle implementace různé názvy, nejčastěji se používají: • wait, Down, secure nebo lock, • signal, Up, release nebo unlock. Výsledek volání wait závisí na okamžité hodnotě semaforu. Je-li jeho hodnota větší než 0, sníží se touto operací o 1 a proces může pokračovat v činnosti. Jestliže je hodnota semaforu rovna 0, proces volající wait je pozastaven. Čekání procesu bude trvat tak dlouho, než hodnotu semaforu zvýší jiný proces voláním signal. Pouze potom je možné operací wait opět

22

Operační systémy - modelování a algoritmy paralelních výpočtů snížit hodnotu semaforu a pokračovat ve zpracování procesu. Volání signal zvyšuje hodnotu semaforu o 1 a nemá žádný účinek na zpracovávaný proces. Je velmi důležité, že testování a snížení hodnoty pomocí funkce wait se provádí pouze po krocích v rámci jedné operace. Operační systém nepovolí přerušení při zpracování volání wait, testování hodnoty a operace snížení hodnoty proběhne bez přerušení. Operace wait semaforu je totožná s operací TSL, je-li jí hardware počítače vybaven. Signal a wait mají mnemotechnický význam. Signal je spojen s během procesu a wait s jeho využitím. Jestliže semafor má hodnotu 0, proces musí čekat na signal. Jestliže několik procesů čeká na stejný signal, pouze jeden z nich může pokračovat ve zpracování, když je zadán signál. Závisí to na implementaci. Nejčastější implementací pro využití více než dvěma procesy je doplnění proměnné frontou. Procesy čekají ve frontě FIFO nebo mohou být vybrány z fronty jiným algoritmem k pokračování zpracování, např. náhodně. Semafory samy o sobě neřídí pořadí ve frontě, to určuje příslušná implementace semaforu v daném operačním systému. Obecný semafor Nejčastější implementace obecného semaforu je kombinace fronty a celočíselné hodnoty proměnné: • Systémové volání wait nejprve sníží hodnotu semaforu o 1. Je-li výsledná hodnota rovna nule, uloží systémové volání wait identifikační čísla aktivního procesu do fronty semaforu, převede aktivní proces do stavu čekání a vyvolává přeplánování-procesu je odebrán procesor. Tento proces čeká na příslušný signal, který bude volán v jiném procesu. • Systémové volání signal nejprve zvýší hodnotu semaforu o 1 a uvolní (release)první proces z fronty semaforu a převede jej do stavu připraven. Vlastně ukončí operaci wait pozastaveného procesu. Příklad: program sem_example var p1: semaphore begin p1:= 1; ... while TRUE do begin wait (p1); prostředek *) signal (p1); ... end while TRUE do begin

(* opakování *) (* proces A *) (* chráněný sdílený

(* proces A *) (* opakování *) (* proces B*)

23

Operační systémy - modelování a algoritmy paralelních výpočtů wait (p1); prostředek *) signal (p1); ... end ... end.

(* chráněný sdílený

(* proces B*) (* sem_example *)

Jedna proměnná semaforu postačuje ke koordinaci přístupu porovnáváním různých příznaků zpracovávaných procesů.Procesy zpracovávající volání wait jsou zařazeny do fronty čekajících procesů a nespotřebovávají čas CPU pro testování stavu proměnné semafor. Operační systém uvolní proces, když je zavolán odpovídající signal. Jsou-li synchronizovány procesy producent a konzument, musí vždy druhý proces, konzument, počkat až první proces, producent, zapíše data do sdílené oblasti paměti. Producent čeká až do chvíle než je konzument ze sdílené paměti odebere. Tak se oba procesy střídají ve zpracovávání. Zajištění efektivní implementace činnosti procesů producent a konzument je pomocí obecných semaforů jednoduché. Ukážeme si použití jiného typu volání down a up. Pro synchronizaci použijeme tři semafory. První semafor mutex bude řídit přístup do kritické sekce producenta a konzumenta. Jeho počáteční hodnotu nastavíme na 1. Další dva semafory indikují stav vyrovnávací paměti. Semafor empty indikuje stav prázdný a jeho počáteční hodnota bude dána počtem prázdných buněk vyrovnávací paměti např. N. Semafor full indikuje stav plný a jeho počáteční hodnota je dána počtem zaplněných buněk, na počátku tedy 0. Příklad: #define N 100 typedef int semaphore; semaphore mutex = 1; */ semaphore empty = N; bufferu */ semaphore full = 0; producer ( ); { int item; while (TRUE) { produce_item (&item); down (&empty); down (&mutex); enter_item (item); bufferu */ up (&mutex); up (&full); }

24

/* počet buněk v bufferu */ /* deklarace semaforu */ /* řízení přístupu do krit. sekce /* čitač prázdných buněk /* čitač plných buněk bufferu */

/* generace vstup do bufferu */ /* snížení čitače prázdný */ /* vstup do krit.sekce */ /* vložení nové položky do /* opuštění kritické sekce */ /* zvýšení čitače plný */

Operační systémy - modelování a algoritmy paralelních výpočtů } consumer ( ) { int item; while (TRUE) { down (&full); down (&mutex); remove_item (&item); up (&mutex); up (&empty); consume_item (item); } }

/* snížení čitače plný */ /* vstup do kritické sekce */ /* odebrání položky z bufferu */ /* opuštění kritické sekce */ /* zvýšení čitače prázdný*/ /* použití položky */

Řešení je možné i se dvěma semafory. První A bude řídit přístup a je inicializován na 0 a druhý B je inicializován velikostí sdílené paměti. Sdílená paměť je využita nejlépe, budou-li oba procesy pracovat stejně rychle, nejsou prodlevy. Jestliže se konzument zpozdí, umožní hodnota semaforu B producentovi generovat data bez přerušení, dokud nenaplní celou sdílenou paměť, pak bude pozastaven a musí čekat na konzumenta. Jestliže producent poběží pomaleji, bude konzument pozastaven, až bude sdílená paměť prázdná. Často nestačí informace o tom, že proces čeká na nějaký semafor, ale je nutné vědět, o který semafor se jedná. Každý semafor má tedy své identifikační číslo. Číslo semaforu se uloží do tabulky procesu(identifikačního segmentu). Binární semafory Semafor mutex v předcházejícím příkladu slouží pouze pro řízení přístupu do kritické sekce a může mít pouze dvě hodnoty, které můžeme označit jako jeho stavy. Takový typ semaforu označujeme jako binární semafor. Lze to porovnat se skutečným semaforem, kdy svítí buď zelená nebo červená. Může signalizovat stav, zda kritická sekce je otevřena nebo uzavřena. Implementace systémových volání může být opět různá. Činnost si vysvětlíme na volání unlock a lock, které lépe vyjadřují funkci binárního semaforu: • lock, • unlock. Systémové volání lock nejprve testuje hodnotu semaforu. Další činnost záleží na implementaci semaforu, zda počáteční hodnota je 1 nebo 0. V minulém příkladu byla jedna, nyní si ukážeme druhý případ, kdy bude počáteční hodnota nula a funkce semaforu bude trochu odlišná. Jestliže semafor byl nulový, svítila zelená, nastaví se na jedničku, svítí červená, volání je ukončeno (nepřerušitelná operace) a proces vstoupí do své kritické sekce. Jestliže obsahoval 1, svítila červená, uloží identifikační číslo procesu do fronty semaforů a pak jej suspenduje (proces suspenduje sám sebe). Bude-li počáteční hodnota semaforu 1, zelená, zachová se postup volání wait, kdy se hodnota semaforu snižuje o 1. Pro lepší pochopení principu jsou uváděny obě možnosti.

25


Systémové volání unlock nejprve ověří, je-li fronta semaforu neprázdná. Je-li tomu tak, vybere z ní první proces a převede jej do stavu připraven. Tato funkce odpovídá volání signal, který ukončuje volání wait. Pokud je fronta prázdná, nastaví volání unlock semafor na nulu pro případ počáteční hodnoty nula. Pro druhý případ zvýší hodnotu semaforu 1, standardní funkce volání signal. Každý proces před vstupem do kritické sekce zavolá systémové volání lock a po ukončení kritické sekce systémové volání unlock. Pro funkci binárního semaforu lze snadno použít i obecný semafor, což odpovídá druhému případu, kdy počáteční hodnota semaforu je rovna1. I když bylo uvedeno, že semafor může nabývat pouze nezáporných hodnot, lze v tomto případě využít i záporných hodnot semaforu a to v případě, že počáteční hodnota semaforu je nula. Každé volání wait sníží hodnotu semaforu o 1, záporná hodnota pak udává počet procesů, které čekají na semafor. Volání signal zvyšuje hodnotu semaforu o 1 až do stavu 0, kdy na semafor nečeká žádný proces a jeho stav odpovídá původnímu, což je nula, svítí zelená. Z uvedeného je zřejmé, že implementace obecného semaforu může být složitější, aby zabezpečovala možné funkce semaforu.

5.4 Událost - Event Události zpravidla slouží k oznámení jednoho procesu ostatním procesů, že nějaká operace skončila a mohou se provádět operace další. Ukončí-li např. proces zpracování bloku dat, oznámí pomocí služby událostevent tuto skutečnost ostatním procesům a tyto procesy mohou tento blok dat dále používat. Událost – event je tedy služba operačního systému, která umožňuje aktivovat vybrané procesy, které na ni čekají. Typickou úlohou, kde můžeme tuto složku využít je úloha čtenáři – písaři. Na rozdíl od kritické sekce nebo mutexu událost není žádnému procesu speciálně přidělován. Událost pouze signalizuje jednomu nebo více procesům, že k něčemu došlo. Například aplikace, kdy jeden proces získává data z A/D převodníku a ukládá je do datové struktury, a další procesy data z této struktury zpracovávají. Jeden proces z nich počítá efektivní hodnotu, druhý provádí harmonickou analýzu, třetí počítá průměr, čtvrtý je ukládá do databáze, atd. Vznikne tedy úloha typu jeden písař a N čtenářů. Písař po vytvoření datové struktury potřebuje dát najevo čtenářům, že struktura je kompletní a mohou ji začít zpracovávat. Aby se písař dozvěděl, že může vytvořit další datovou strukturu, bude nejjednodušší, aby všichni čtenáři signalizovali ukončení své činnosti svou vlastní událostí. Písař potom musí čekat na signalizaci ukončení činnosti od všech čtenářů. Kód písaře a čtenářů potom vypadá následujícím způsobem:

26


/* Kod pisare */ ..... while (!konec) { Cteni_A/D (Data); Set_Event (Event Data);

/* Vytvareni struktury data */ /* Aktivace udalosti, která signalizuje platna data pro ostatni procesy */ Wait_Event (Even_Ctenar_1); /* Cekani na ukonceni ctenare 1 */ Reset_Event (Event_Ctenar_1); /* Deaktivace udalosti ctenare 1 */ .... Wait_Event (Event_Ctenar_N); /* Cekani na ukonceni ctenare N */ Reset_Event (Event_Ctenar_N); Reset_Event (Event_Data); /* Deaktivace udalosti pro platna data*/ } .... /* Kod ctenare 1 */ .... while (konec) { Wait_Event (Event_Data); Zpracovani_Ctenare_1(Data); Set_Event (Event_Ctenar_1); } .... /* Kod ctenare N */ .... while (!konec) { Wait_Event (Event_Data); Zpracovani_Ctenare_N (Data); Set_Event (Event_Ctenar_N); } .... Takto uvedený kód je zcela v pořádku pouze na první pohled. Tento kód však může aktivovat čtenáře na jednu událost Event_Data několikrát, než ji stačí písař deaktivovat. Pokud např. čtenář 1 ukončí zpracování dat dříve než ostatní čtenáři a vrací se na příkaz čekání na událost Event_Data, která je stále nastavena, zpracuje tato data podruhé. Operační systémy, pokud mají implementováno volání obsluhující událost, obsahují zpravidla funkci Pulse_Event, která zajistí nastavení události, aktivaci příslušných procesů a desaktivaci této události. Konstrukce programu jednotlivých procesů se potom podstatně zjednoduší. Přistupují-li procesy ke společným datům, mohou být tato modifikována pouze při splnění určitých podmínek, které mohou být odlišné pro různé procesy. Všechny procesy mají následující strukturu:

27

Operační systémy - modelování a algoritmy paralelních výpočtů begin wait until condition; modify data; end Přístup ke společným datům musí být chráněn. Možné řešení je takové, že jedním semaforem řídíme přístup ke společným datům a jiným semaforem indikujeme, zda společná data jsou změněna. Všechny procesy přistupují k semaforu voláním mutex (současný přístup) a voláním change (změna dat) stejnou cestou. var

mutex, change: waiting:

semaphore; integer;

begin wait (mutex); while not condition do begin waiting : = waiting + 1; signal (mutex); wait (change); wait (mutex); end; (* operace na společných proměnných *) while (waiting > 0) do begin waiting : = waiting - 1; signal (change); end; signal (mutex); end; Příklady realizace služby událost – event Službě event mohou být přiřazena dvě volání například await a cause, tato jména volání nejsou všeobecně akceptována a jsou uváděna jako příklad dvou volání. Operací await je proces zařazen do fronty, zatím co se hodnota sdílených dat mění. Změna dat je řízena voláním cause. Po změně dat, tzn. uskutečnění události, jsou uvolněny všechny čekající procesy a ne pouze jeden jako v případě použití semaforu. Událost – event může být realizována jak binární proměnnou, tak čítačem (event counter). Služba událost nechrání kritickou sekci před současným přístupem několika procesů, jak je to u semaforů. Tato služba je určena pro jiné synchronizační úlohy, jak již bylo dříve uvedeno, např. písaři – čtenáři. Příklad realizace události pomocí proměnných event a semaphore je následující: var mutex: semaphore; change: event; begin while not condition do await (change);

28

Operační systémy - modelování a algoritmy paralelních výpočtů wait (mutex); (* operace na společných proměnných *) signal (mutex); end; Událost change je spojena se semaforem mutex. Volání signal semaforu mutex realizuje volání cause (události change). Při každé změně hodnoty události change všechny procesy testují podmínku a pouze procesy, pro které je podmínka splněna, mohou být zpracovávány. Pouze jeden proces může využívat chráněný prostředek, je chráněn semaforem mutex.

29


6 Komunikace mezi procesy Pro vzájemnou komunikaci využívají procesy několik systémových prostředků: • společná oblast paměti, • služba monitor, • služba poštovní schránka – mailbox, • služba setkání- rendevous, • služba zpráva – signal, • služna alarm a časovač – timer, • služba roura – pipe.

6.1 Společná oblast paměti Různé procesy mohou číst a zapisovat do společné oblasti paměti. Tato oblast může být chráněna pomocí semaforů, tuto službu si takto může realizovat uživatel.

6.2 Monitor Monitor je klasická metoda sdílení prostředků při meziprocesové komunikaci. Umožňuje výměnu informací mezi procesy, které musí být synchronizovány. Monitor zahrnuje vyhrazenou datovou oblast a příslušnou proceduru s výhradním právem práce s daty. Externí procedury nemají přímý přístup k oblasti dat obsluhované službou monitor, ale mohou ji použít pouze prostřednictvím služby monitor. Monitor umožňuje službu v daném okamžiku pouze jedné externí proceduře. Operační systém zajišťuje, aby příslušná procedura monitor nebyla přerušena jiným procesem. Takto volaná procedura monitor nemůže být ukončena před přístupem jiné procedury ke stejným datům. Příklad: Procedure monitor (* příklad monitoru *) var struct1: record; (* chráněná oblast *) procedure write_data (monitor_input); entry; begin ... with struct1 do ... end procedure read_data (monitor_output); entry; begin ...

30

Operační systémy - modelování a algoritmy paralelních výpočtů with struct1 do ... end; end. (* procedura monitor *) Procedury write_data a read_data jsou definovány jako entry procedury – vstupní procedury monitoru. Pouze přes tyto procedury se komunikuje s monitorem. Externí procesy nemají přímý přístup k sdílené datové oblasti structl a interní procedury nejsou explicitně definovány jako entry. Výhodou monitorů je to, že ponechávají sdílení prostředků a synchronizaci procesů na operačním systému, pokud jsou součástí jeho služeb a nemusí se jí zabývat uživatel. Monitory bývají rovněž součástí některých víceúlohových jazyků jako je Concurrent Pascal, kdežto v jiných běžně používaných jazycích jako je C nebo Pascal si jejich vlastní strukturu můžeme naprogramovat. Řešení problému producent-konzument pomocí monitoru: monitor ProducerConsumer condition full, empty; integer count; procedure enter; begin if count = N then wait (full); enter_item; count : = count + 1; if count = 1 then signal (empty); end; procedure remove; begin if count = 0 then wait (empty); remove_item; count : = count – 1; if count = N – 1 then signal (full); end; count : = 0; end monitor; procedure producer; begin while true do begin produce_item; ProducerConsumer.enter; end end; procedure consumer; begin

31

Operační systémy - modelování a algoritmy paralelních výpočtů while true do begin ProducerConsumer.remove; consume_item; end end;

6.3 Zasílání zpráv a signály Zasílání zpráv je základní metodou meziprocesové komunikace. Signál je nástrojem meziprocesové komunikace i synchronizace. Proces zašle signál nebo zprávu, která obsahuje parametr s hodnotou. Typické operace, které zasílání zpráv (message passing) umožňují jsou: • •

send (destination, &message), receive (source, &message).

Implementace u různých operačních systémů jsou odlišné, zejména co se týká parametrů příkazů. Obdobně to platí i u zasílání signálů. Typické operace, které operace se signály umožňují jsou: • send_signal (parametrs) – odeslání signálu, • receive_signal (parametrs) – přijetí signálu. Jednotlivé implementace zasílání signálů se liší především ve způsobu adresace vysílajícího a přijímajícího procesu, formátu zprávy a ve způsobu synchronizace zasílání zpráv. Způsob adresace lze rozdělit do tří částí: symetrická, asymetrická a nepřímá. Při symetrické adresaci je v synchronizačních příkazech uváděna identifikace přijímajícího i vysílajícího procesu . V přijímajícím procesu je uvedena adresa vysílajícího procesu, od kterého má být signál přijat. Při nesymetrické adresaci je uváděna pouze identifikace příjemce. Identifikaci vysílajícího procesu je možné zjisti po přijetí signálů z hodnoty přijatého signálu. V případě nepřímé adresace se uvádí pouze identifikace komunikačního kanálu, který příjem a zasílání zpráv zprostředkovává (např.mailbox). Podle způsobu synchronizace je možné mechanismy zasílání signálů rozdělit na asynchronní a synchronní. Synchronní zasílání zpráv obsahuje oproti asynchronnímu potvrzení přijetí zprávy vysílajícímu procesu. Je opět třeba připomenout, že správu signálů zajišťuje operační systém. Vysílající proces zavolá funkci send_ signal s odpovídajícími parametry a operačním systém zajistí aktivaci příslušného procesu, který na přijetí signálu čeká (je ve stavu spící ve funkci receive_signal). Signál obvykle prochází vyrovnávací pamětí, ve které je dočasně uložen.Velikost této paměti bývá zpravidla nastavitelná při vytváření objektu signálu. Přijímací proces tedy nemusí nutně okamžitě zpracovat příchozí signál. V případě nahromadění nezpracovaných signálů může funkce send_signal vrátit chybu nebo může být rozšířena o čekání (úloha typu producent-konzument).

32

Operační systémy - modelování a algoritmy paralelních výpočtů Hodnotou signálu je několikabytové číslo. Pomocí této hodnoty může vysílající proces sdělit přijímajícímu, jak má při zpracování na přijatý signál reagovat. Signálu lze tedy využít pro synchronizaci dvou procesů podobně jako události s rozšířením informace o tom, k čemu konkrétně ve vysílacím procesu došlo. Implementace v konkrétním operačním systému je uvedena v kapitole, kde je popisován operační systém QNX.

6.4 Poštovní schránka – mailbox Poštovní schránky synchronizují procesy (obr.26). Struktura dat schránky je orientována na komunikaci pomocí zpráv, které mohou být odesílány a přijímány.

Mailbox vstup zpráv

1

2

výstup zpráv

Obr. 8 Komunikace pomocí poštovní schránky V daném operačním systému mohou být definovány různé schránky, což umožňuje výměnu různých typů zpráv. V řadě operačních systémů jsou schránky zahrnuty mezi logické soubory a přístupová procedura je stejná jako k fyzickým paměťovým jednotkám. Pro schránky jsou definovány následující operace: • vytvoření, • otevření, • zápis zprávy, • čtení zprávy, • zavření, • vymazání. Schránky nemají nezávislou strukturu. Mohou být umístěny v operační paměti nebo na disku. Existují pouze, je-li systém v činnosti. Můžeme je charakterizovat jako dočasné soubory, které jsou zrušeny při vypnutí systému. Jsou označeny pouze logickými identifikátory (často čísly), které jsou definovány při vytvoření. Všechny procesy adresují schránku jeho logickým identifikátorem. Práce se schránkami je obdobná práci se soubory. Příklad zápisu: put_mailbox (#1, message) Příklad čtení: get_mailbox (#1, message)

33

Operační systémy - modelování a algoritmy paralelních výpočtů Při vytvoření schránky operační systém definuje ukazatele na oblast paměti pro operace čtení a zápisu a přiřadí proměnné pro ochranu přístupu. Nejčastější je schránka realizována jako vyrovnávací paměť(buffer), jejíž velikost je definována při vytvoření nebo připojeným seznamem struktury, který neomezuje počet zpráv, které mohou být ve schránce umístěny.

6.5 Setkání – souběh (rendevous) Souběh-setkání je v podstatě provedení společného úseku kódu více paralelními procesy. Před prováděním tohoto kódu je nutné, aby se všechny zainteresované procesy zastavily na jeho začátku. Provedení společného úseku je realizováno jako součást jednoho ze zúčastněných procesů. Tento proces může společný úsek provést přímo nebo prostřednictvím dalšího procesu. Ukončení souběhu je nutno všem zúčastněným procesům oznámit, aby mohly nezávisle pokračovat ve zpracování svých kódů. Model souběhu pomocí Petriho sítě ukazuje následující obrázek 9. V případě souběhu pouze dvou procesů je zajímavé znázornění běhu těchto procesů pomocí postupového prostoru. Kód obou procesů běží stejně rychle a skutečně paralelně, takže postupová cesta má směrnici vždy rovnou 1.

Obr. 9 Znázornění souběhu Souběh-rendevous je asymetrická operace: Jeden proces požaduje souběh a jiný deklaruje, že je připraven jej akceptovat. Princip je podobný volání podprogramu. Proces, žádající setkání, musí znát jméno volaného procesu, zatím co volaný nepotřebuje vědět, kdo je volající. Souběh se 34

Operační systémy - modelování a algoritmy paralelních výpočtů realizuje následovně. Volaný proces má spojení s ostatními procesy pomocí vstupního bodu (entry point). Vstupní bod je vázán na seznam parametrů, kde jednotlivé parametry jsou označeny jako in, out a inout, tzn. zda jsou vstupem, výstupem nebo vstupem i výstupem volání. Ve volaném programu je jedna nebo více volání accept, které ukazují, kde parametry z nějakého volajícího procesu musí proběhnout. Volající proces a volaný proces jsou zpracovávány nezávisle. Když jeden proces dosáhne svého volání accept nebo entry, dostane se do stavu čekání. Když druhý proces dosáhne odpovídajícího volání, uskuteční se setkání. Volaný proces pokračuje ve zpracování instrukcí v bloku volání accept, zatím co druhý čeká. Jakmile volaný dosáhne konce bloku accept, oba nezávisle pokračují ve zpracování. Souběh kombinuje přenos dat (přes seznam parametrů) se synchronizací procesů. Souběhu se může zúčastnit i více paralelních procesů. Různé procesy mohou provést odkaz na stejné volání entry. Pak tato volání jsou seřazena do fronty FIFO.

6.6 Alarmy, časovače Alarm je obdobou signálu, který zasílá operační systém danému procesu, který o to požádal. Tento signál zpravidla aktivuje proces, který se nachází ve stavu „spící“. Proces je zařazen do aktivní fronty, kde čeká na předělení času procesoru, aby vykonal obsluhu signálu a poté se vrátil zpět do stavu „spící“. Obvykle podporované způsoby použití alarmu nebo časovače jsou následující: • Jednorázová aktivace po uplynutí stanoveného intervalu. • Jednofázová aktivace ve stanovený datum a čas. • Cyklická aktivace po uplynutí stanoveného časového intervalu. • První aktivace ve stanovený datum a čas, další aktivace potom cyklicky po uplynutí stanoveného intervalu. • První aktivace po uplynutí stanoveného intervalu, další aktivace potom cyklicky po uplynutí jiného intervalu. Název tohoto synchronizačního nástroje závisí na implementaci v konkrétním operačním systému. Objekt, který se v rámci jednoho OS nazývá alarm, se jinde jmenuje časovač (Timer) nebo jakkoli jinak. Název konkrétního objektu mnohdy při prvním seznámení může velmi mást. Konkrétní zařazení objektu do správné skupiny je mnohdy nutné provést podle jeho vlastností, nikoli podle jeho názvu. Situace u tohoto synchronizačního nástroje je podobná jako u signálů, pouze s tím rozdílem, že zde neexistuje vysílací proces. Celá konstrukce se tedy poněkud zjednoduší. Odpadá identifikace přijímajícího procesu, potvrzení přijetí signálu, aj.

35

Operační systémy - modelování a algoritmy paralelních výpočtů S alarmem nebo časovačem se dají realizovat pouze tři operace: instalace, nastavení a odstranění. Přičemž instalace a nastavení může být v některých implementacích provedeno jednou funkcí. Volbou instalační funkce zpravidla vybírá výše uvedený způsob použití. Jako parametry této funkce jsou zadávány hodnoty intervalů pro aktivaci a dále pak adresa obslužné rutiny, pokud nějaká existuje. Tento synchronizační nástroj najde uplatnění všude tam, kde je zapotřebí periodické aktivace procesu. Klasickým příkladem u řídících systémů je např. čtení hodnot z A/D převodníku, obnovování údajů fyzikálních stavových veličin na visualizačních obrazovkách, z dalších aplikací je to potom periodické zálohování dat, aj.

6.7 Roura (pipe) Roura – pipe je navržena obdobně jako vyrovnávací paměť – buffer typu FIFO, sloužící k propojení dvou procesů, přičemž jeden proces do roury zapisuje a druhý z roury čte. Roura je tedy nástroj pro jednosměrnou komunikaci. Data zasílaná pomocí roury jsou dočasně uložena v operační paměti. Standardní implementace roury je velmi podobná implementaci souborů. Roury obsahují tři základní operace: • vytvoření roury, • zápis roury, • čtení roury. Roury se dělí na dvě základní skupiny: pojmenované a nepojmenované. Rozdíl spočívá v přístupu aplikací k danému typu roury. K nepojmenované rouře mohou přistupovat pouze příbuzné procesy (rodič-potomek, vlákna procesu). Pokud některý proces vytvoří jiný proces, stává se tento nově vytvořený proces jeho potomkem. Potomek zdědí přístup do adresového prostoru rodiče, může tedy pracovat s identifikátory roury pro zápis a čtení. Při vytvoření roury se vracejí identifikátory pro čtení a zápis do roury. Tyto identifikátory jsou přístupné pouze těmto příbuzným procesům. Procesy, které nejsou spolu genericky svázány, musí použít pojmenovanou rouru. Pojmenovaná roura je přístupná všem procesům na základě jejího identického jména. Pokud je tedy procesu známo jméno roury, může si příslušné identifikátory pro čtení nebo zápis zadat – namapovat do svého adresového prostoru. Při vytváření roury je specifikována její kapacita. Manipulace s rourou probíhá zpravidla pomocí funkcí obvyklých pro práci se soubory (create, read, write, close). Na implementaci konkrétního operačního systému potom závisí komfort správy této roury.

36

Operační systémy - modelování a algoritmy paralelních výpočtů Roury přímo vybízí k řešení úlohy producent-konzument. Nahradíme-li buffer z příkladu uvedeného u semaforu rourou, celá aplikace se podstatně zjednoduší. Producent v každém svém cyklu zapíše jeden prvek, konzument jeden prvek přečte. Jestliže je roura zcela zaplněna a producent zapisuje další prvek, správa roury zajistí čekání ve funkci write tak dlouho, dokud konzument neodebere z roury alespoň jeden prvek. Do té doby je producent uveden do stavu spící. Po uvolnění roury je zařazen do aktivní formy. Obdobná analogie platí i na straně konzumenta. Ke správě tedy nepotřebujeme semafor. Kód úlohy potom vypadá následujícím způsobem: /* Vytvoreni roury, funkce vrati identifikatory pro cteni a zapis hRead, hWrite */ Create_pipe (PIPE_BUFFER, &hRead, &hWrite, SIZE); /* kod producenta */ ..... while (Write (hWrite, PIPE_BUFFER, Prvek)) {/* Zapis prvku do roury, pripadne cekani, je-li roura plna */ . . . . /* Vlastni kod producenta */ } .... /* kod konzumenta */ .... while (Read (hRead, PIPE BUFFER, Prvek)) { /* Cteni prvku z roury, pripadne cekani, je-li roura prazdna */ . . . . /* Vlastni kod konzumenta */ } .... Vzhledem k tomu, že producent a konzument četl nezávisle na sobě, není k dispozici v daném čase údaj o stavu zaplnění roury. Řešení tohoto problému pomocí sdílené proměnné, kdy producent do zápisu provede její inkrementaci a konzument její dekrementaci, je nepřípustné z důvodů naznačených v kapitole, týkající se obecných problémů synchronizace. Pokud operační systém nemá správu roury na takové úrovni, aby bylo možné zjistit její aktuální stav, nezbývá než si tuto správu vytvořit. Nejjednodušší je použít již uvedené řešení pomocí semaforů. Hodnota semaforu PLNE potom určuje počet prvků v rouře. Změna oproti řešení z dílčí kapitoly 4.4.4, kde byly použity semafory, je nahrazení sdíleného bufferu rourou.

37


7 Použití vlastnosti prostředků meziprocesové synchronizace Jak již bylo uvedeno, jednotlivé synchronizační prostředky mají různé vlastnosti a tedy i různé oblasti použití. Jednou z vlastností synchronizačního nástroje může být oblast jeho použití. Některé nástroje lze používat v rámci operačního systému prakticky bez omezení (pokud neuvažujeme omezení systémovými prostředky), jiné lze používat pouze v některých případech. Již bylo citováno např. omezení použití nepojmenovaných rour v rámci příbuzných procesů a vláken procesu. Dalším implementačně závislým omezením může být použití některých nástrojů v obslužných rutinách přerušení. Zpravidla ne všechny nástroje, kterými daný operační systém disponuje, lze v těchto rutinách použít. Z hlediska aplikací pracujících v reálném čase je důležitým kritériem pro posouzení synchronizačního nástroje jeho rychlost. Popis této vlastnosti ukážeme na následujícím příkladu. Mějme proces, který čeká na uvolnění kritické sekce jiného procesu. Rychlostí synchronizačního nástroje se zde rozumí doba, za kterou tento čekající proces dostane přidělen procesor po uvolnění kritické sekce. Tato doba závisí jednak na efektivitě operačního systému, za jak dlouho dokáže zajistit přepnutí kontextu mezi oběma procesy, a jednak na postavení aktivovaného procesu v rámci plánovacího mechanismu. Např. v případě prioritního plánování doba této aktivace značně závisí na prioritě aktivovaného procesu. V podstatě jde o prodlevu v důsledku předání řízení mezi zainteresovanými procesy. Tabulka 7 ukazuje vlastnosti konkrétních nástrojů, které jsou důležité pro návrh aplikace pracující v reálném čase. U všech nástrojů se předpokládá sledování omezení oblasti použití (příbuzné procesy, obslužné rutiny přerušení). Jsou zde uvedeny i nástroje, které jsou zařazeny do komunikačních nástrojů, neboť plní jak funkci synchronizačního tak i komunikačního nástroje. Dále je ukázán na návrh algoritmu pro testování rychlosti synchronizačních nástrojů. Tento algoritmus je použitelný pro libovolný operační systém a pro testování rychlosti libovolného synchronizačního nástroje. Pomocí tohoto algoritmu lze zajistit doba potřebná k předání k předání řízení mezi dvěma procesy. Schéma měření je znázorněno na obrázku 25. K realizaci tohoto algoritmu je zapotřebí sdíleného časovače (timer), ke kterému mají přístup procesy P1 a P2. Pro objasnění algoritmu uvažujeme příklad procesů, kdy proces P1 předává řízení procesu P2 uvolněním kritické sekce. Přepokládejme, že proces P2 je po uvolnění kritické sekce na prvním místě ve frontě aktivních procesů. Tuto podmínku lze zajisti nastavením maximální priority procesu P2. Pokud proces P2 nebude na prvním místě fronty aktivních procesů, nedojde k přidělení procesoru procesu P2 okamžitě a výsledek měření bude zkreslený v důsledku postavení procesu P2 ve frontě aktivních procesů. Dalším předpokladem nezkresleného výsledku je dostatečně vysoká priorita procesů P1 a P2 vzhledem k ostatním procesům, 38

Operační systémy - modelování a algoritmy paralelních výpočtů aby nedošlo k jejich přerušení operačním systémem. Nesmí dojít k přerušení procesu P1mezi odečtením hodnoty čítače a uvolněním kritické sekce. Dále pak nesmí dojít k přerušení procesu P2 mezi jeho aktivací a přečtením hodnoty čítače. • • • • •

Samotný průběh měření je následující: Proces P2 čeká na uvolnění kritické sekce procesem P1. proces P1 přečte hodnotu čítače uloží jeho obsah do T1. Proces P1 uvolní kritickou sekci. Proces P2 po své aktivaci přečte hodnotu čítače a uloží jeho obsah do T2. proces P2 vypočte hodnotu T jako rozdíl hodnot T2 a T1.

Vypočtená hodnota T potom reprezentuje dobu předání řízení mezi oběma procesy.

39


8 Příloha 8.1 Petriho sítě V této kapitole si nadefinujeme nezbytný aparát pro pozdější výstavbu Fuzzy Petriho sítě. Začneme základními definicemi Petriho sítí a popíšeme jejich vlastnosti. Pojem Petriho sítě se poprvé objevil v roce 1992 v disertační prácí Carla Adama Petri. Hlavní motivací pro vznik těchto sítí bylo modelovat řídící systémy. Definice (Petriho síť): Petriho síť je trojice N = (P, T, F), kde P≠0 je konečná množina míst (places), T≠0 je konečná množina přechodů (transitions) a F je přechodová funkce (float) F : (P × T) ∪ (T × P) → N0 Tato definice se liší od původní přidáním podmínky neprázdné množiny míst a přechodů. Důvodem je skutečnost, že námi následně definovaná Fuzzy Petriho síť bude mít minimálně jeden přechod a jedno místo. Definice Nechť N = (P, T, F) je Petriho síť. Pro každý přechod t ∈ T a pro každé místo p ∈ P definujeme množiny t• = {p ∈ P | F(t, p) > 0} •t = {p ∈ P | F(p, t) > 0} p• = {t ∈ T | F(p, t) > 0} •p = {t ∈ T | F(t, p) > 0} Pro místo p ∈ P je p• neformálně množina přechodů, z nichž místo muže získat token a •p množina přechodů, do nichž může token odevzdat.

40


Definice (Označkování a uschopněný přechod) Nechť N = (P, T, F) je Petriho síť. Označkování (marking) je funkce M :P→N0. Přechod t ∈ T je uschopněn v M, pokud

∀ p ∈ t• : M(p)≥F(p, t) Neformálně lze označkování chápat jako distribuci tokenů v síti: udává počet tokenů v jednotlivých místech. Podívejme se na tuto definici trochu podrobněji. Důležitým místem je relace ≥ , pokud by byla použitá rovnost mnoho vlastností by bylo nerozhodnutelných. Za použití rovnosti by Petriho sítě byly stejně silné jako Turingovy stroje. Definice (Přechodový systém Petriho síti) Nechť N = (P, T, F) je Petriho síť a A je množina náveští (abeceda). Nechť je dána funkce l : T→A přiřazující přechodům ne nutně vzájemně různá náveští. Přechodový systém s návěštími pro Petriho síť N s olabelováním l definujeme jako TN = (S,A, →), kde S je množina všech označkování, → ⊆ S × A × S a M →a M´ právě tehdy, když existuje přechod t ∈ T uschopněný v M takový, že l(t)= a

∀ p ∈ P : M´0(p) = M(p) − F(p, t) + F(t, p) Jak již bylo řečeno, kromě matematického popisu Petriho sítí existuje i grafická reprezentace sítě.

Nyní si tyto jednotlivé části znázorníme a následně

sestrojíme ukázku jednoduché Petriho sítě. Grafické značení Místo (places)

41

Operační systémy - modelování a algoritmy paralelních výpočtů Přechod (transitions)

Orientované hrany (arcs)

Jednoduchá Petriho síť s dvěmi místy a jedním přechodem, kdy chceme vyjádřit „přesun“ z místa P0 do P1 přes přechod T0.

Obrázek 2.: Jednoduchá Petriho síť Místo se značkou (tokenem)

Analýza Petriho sítě Abychom mohli provést analýzu sítě, musíme si nadefinovat dosažitelnost, životnost přechodů a mrtvé přechody. Definice (Dosažitelné označkování) Označkování M´ je dosažitelné z M v Petriho síti N = (P, T, F), jestliže je v přechodovém systému indukovaném sítí N stav M´ dosažitelný z M. Definice (Množina dosažitelných označkování) Pro Petriho sít N a její označkování M definujeme funkci Reach(N,M) = {označkování M´ sítě N | M´ je dosažitelné z M} Definice (Živost přechodu, živost sítě)

42

Operační systémy - modelování a algoritmy paralelních výpočtů Buď N = (P, T, F) Petriho sít, M0 její označkování. Přechod t ∈ T je živý pro M0, jestliže pro každé M dosažitelné z M0 existuje M0 dosažitelné z M tak, že t je uschopněný v M. Petriho síť nazveme živou pro marking M0, pokud je pro M0 živý každý její přechod. Definice (Mrtvé místo, mrtvý přechod) Nechť N = (P, T, F) je Petriho sít. Místo p ∈ P se nazývá mrtvé v markingu M, pokud pro všechna označkování M´ dosažitelná z M platí M´(s) = 0. Přechod t ∈ T se nazývá mrtvý, není-li připravený v žádném označkování dosažitelném z M. Definice (bezpečná síť) Petriho síť nazýváme bezpečnou, jestliže pro každé její ohodnocení platí: M(p) ≤1. Definice (ohraničená síť) Petriho síť nazveme ohraničenou, jestliže ∃k ∈ N 0 ; ∀p; M ( p) ≤ k Definice (konzervativní) Petriho síť nazýváme konzervativní, jestliže pro každý její stav platí, že celkový počet značek je konstantní.

∀i; ∑ z ( i ) ( p j ) = k j

Definice (stabilizované ohodnocení)

Ohodnocení nazveme stabilizované, jestliže je dosažitelné z každého existujícího ohodnocení.

43

Operační systémy - modelování a algoritmy paralelních výpočtů Klasické techniky analýzy Petriho sítí Definice (Incidenční matice)

Nechť N = (P, T, F) je Petriho sít. Incidenční maticí N : P × T →{−1, 0, 1} rozumíme funkci udávající efekt přechodu t ∈ T na místo p ∈ P, tj. danou vztahem N(p, t) = F(t, p) − F(p, t). Incidenční matici můžeme rozdělit na zpětnou a dopřednou. Zpětná incidenční matice C- typu n x m je definována c ij− = F − ( p i , t j ), ∀p i ∈ P, t j ∈ T ,

analogicky dopředná incidenční matice C+ je definována jako c ij+ = F + ( p i , t j ), ∀p i ∈ P, t j ∈ T

Incidenční matice C se pak rovná C=C+-CDefinice (Kroneckerovo delta)

Pro snadnější zápis některých vztahu je vhodné zavést tzv. Kroneckerovo delta, funkci definovanou vztahem i= j σ ij = {10 pro jinak

Definice (Parikuv obraz)

Buď N = (P, T, F) Petriho síť, kde T = {t1, . . . , tn}. Nechť σ ∈ T * je posloupnost přechodů. Parikovým obrazem posloupnosti σ rozumíme vektor r

σ = ( σ 1, . . . , σ n)T kde σ i je počet výskytu ti v σ

Věta (Podmínka dosažitelnosti)

44


Nechť N = (P, T, F) je Petriho síť s incidenční maticí N. Nechť označkování σ M´ je dosažitelné z M, M ⎯ M´, kde σ ∈ T * . Potom existuje řešení ⎯→ r rovnice M´ = M + NX a řešením je i σ .

Nyní si uvedeme pro ilustraci několik názorných příkladů Petriho sítí.

Obrázek 3: Proces Producent-Konzument Jedná se o klasický příklad procesů v operačních systémech. Producent vyprodukuje hodnotu a konzument ji odebere. Nesmí dojít k přepsaní hodnoty dříve, než ji konzument odebere. Počet tokenů v místě kapacity udává velikost volné vyrovnávací paměti. Na následujícím příkladě si provedeme rozbor sítě prostřednictvím incidenční matice.

45


Obrázek 4.: Síť pro rozbor prostřednictvím incidenční matice z 0 = (3,0,5,4,0)

I − ( p3 , t 3 ) = I + ( p3 , t 4 ) = 5 ⎛1 ⎜ ⎜0 C − = ⎜1 ⎜ ⎜0 ⎜0 ⎝

0 1 0 0 0

0 0 5 1 0

0⎞ ⎛0 1 ⎟ ⎜ 0⎟ ⎜1 0 0⎟ , C + = ⎜0 1 ⎟ ⎜ 0⎟ ⎜0 0 ⎟ ⎜0 0 1⎠ ⎝

0 0 0 0 1

0⎞ 0 0⎞ ⎛ −1 1 ⎟ ⎜ ⎟ 0⎟ 0⎟ ⎜ 1 −1 0 5 ⎟ , C = ⎜ −1 1 − 5 5 ⎟ ⎜ ⎟ ⎟ 1⎟ ⎜ 0 0 −1 1 ⎟ ⎜0 0 0 ⎟⎠ 1 − 1⎟⎠ ⎝

Po uskutečnění přechodu T1 přejde počáteční ohodnocení z0 do stavu ⎛ 2⎞ ⎛1⎞ ⎜ ⎟ ⎜ ⎟ ⎜1⎟ ⎜ 0⎟ z ′ = z 0 + C⎜ ⎟ = ⎜ 4 ⎟ 0 ⎜ ⎟ ⎜ ⎟ ⎜ 4⎟ ⎜ 0⎟ ⎝ ⎠ ⎜ ⎟ ⎝0⎠ Po odpálení posloupnosti T1, T1, T1, T2 je výsledné ohodnocení

z ( 4)

46

⎛1⎞ ⎛ 3⎞ ⎜ ⎟ ⎜ ⎟ ⎜ 2⎟ ⎜1⎟ = z 0 + C⎜ ⎟ = ⎜ 3 ⎟ 0 ⎜ ⎟ ⎜ ⎟ ⎜ 4⎟ ⎜0⎟ ⎝ ⎠ ⎜ ⎟ ⎝0⎠

Operační systémy - modelování a algoritmy paralelních výpočtů Modifikované Petriho sítě

S nárůstem využití Petriho sítí vznikala potřeba stávající síť upravovat a rozšiřovat tak aby bylo možno modelovat různé typy problému v různých oblastech. My si nyní nadefinujeme dva typy modifikací Petriho sítí. Tyto modifikace jsou nezbytné pro pozdější rozšíření na Fuzzy Petriho sítě (FPN). Prvním rozšířením jsou Petriho sítě s inhibiční hranou. Toto rozšíření je nezbytné pro správný popis klasické logiky Petriho sítěmi. Definice (Petriho sítě s inhibiční hranou)

Inhibiční hrana Pi → Tj způsobí blokování přechodu Tj , je-li M(Pi) > 0, tedy obsahuje-li Pi alespoň jeden token. V situaci, kdy M(Pi)=0 je chování přechodu Tj standardní. Inhibiční hrana nepřenáší tokeny. Po podrobnějším prozkoumání a porovnání s klasickou hranou zjistíme, že se jedná o klasickou negaci. Grafické znační inhibiční hrany

Obrázek 5.: Petriho síť s inhibiční hranou u které nastane podle tohoto značení přechod Druhou popisovanou Petriho sítí budou Barevné Petriho sítě (CPN). Hlavní myšlenkou pro vznik Barevných Petriho sítí byla potřeba pracovat s různými typy tokenů. Chtěli jsme docílit toho aby se pro každý typ chovala stejná síť různě. Barevné Petriho sítě jsou velmi vhodným nástrojem pro popis velmi složitých systémů. Definice (Barevné Petriho sítě)

47


Barevná Petriho síť je množina CPN= (Σ , P,T, A, N, C, G, E, I) kde, 1. Σ je konečná neprázdná množina typů – množina barev 2. P je konečná množina míst 3. T je konečná množina přechodů 4. A je konečná množina hran, kde P ∩ T = P ∩ A = T ∩ A ≠ 0 5. N je uzlová funkce spojení místa a přechodu N : A → ( PxT ) ∪ (TxP) 6. C je funkce barvy C : P → Σ 7. G je hlídací funkce, G: T→ Expr, s řídící podmínkou: ∀t ∈ T (Type(G (t )) = Boole ∧ Type(Var (G (t ))) ⊆ Σ 8. E je hranová vyjadřovací funkce G: A→Expr s podmínkou

∀a ∈ A ∀p(a) ∈ N (a) 9. I je inicializační funkce I: P→ Exprclosed , kde ∀p ∈ P(Type( I ( p)) = C ( p ) MS ) Nyní si ukážeme na jednoduchých příkladech grafické značení Barevných Petriho sítí. Následuje ukázka místa v CPN se značením 3´Č + 5´M + 2´Z

3´Č + 5´M + 2´Z

3´Č + 5´M + 2´Z

NELZE!

Obrázek 6: Značení barevných Petriho sítí Označíme-li kapacitu místa, pak to znamená, že dané místo nemůže obsahovat více než tři tokeny typu Č, 5 tokenů typu M a 2 tokeny typu Z. Jedná-li se o ohodnocení hrany, pak to znamená, že v případě provedení přechodu přechází po hraně /do nebo z přechodu/ právě uvedená kombinace typů tokenů.

1´Č+3´Z+1´M

Obrázek 7: Příklad CPN

48

1´Č+3´Z+1´M


Podobně jako u všech dalších formálních jazyků, praktické použití Barevných Petriho sítí je závislé na existenci adekvátní softwarové podpory. Pro tyto účely byl na Univerzitě v Aarhusu v Dánsku vytvořen nástroj (Design/CPN tool package) pro podporu konstrukce, editace, kontrolu syntaxe a simulaci rozsáhlých, modulárních CPN s nebo bez časových prodlev. Tento nástroj je distribuován zdarma, a to všem typům uživatelů, tedy i komerční sféře. (http://www.daimi.au.dk/Cpnets/). My Barevné Petriho sítě a tento nástroj využijeme při výstavbě Fuzzy Petriho sítí.

8.2 IF THEN pravidla Většinu procesů můžeme popsat pomoci vět „když nastane A pak nastane B“, „když nastane A a současně B pak nastane C“, atd. Tyto věty se dají přepsat do známých formulí z klasické logiky IF THEN. V této části se podíváme jakým způsobem lze klasickou logiku převést na Petriho sítě [17]. Implikace

Prvním pravidlem, kterým začneme je implikace (A→B) nebo-li IF A THEN B . To znamená, když A je true pak B je true. Po přepisu do Petriho sítě pak bude vypadat toto pravidlo následovně:

Obrázek 8.: Implikace Když dáme do prvního místa (A) token, který bude označovat true a provedeme přepočet dostaneme v druhém stavu (B) token – true. , Obrázek 9.: Princip implikace Konjunkce v antecedentu

49


Druhým důležitým pravidlem je konjunkce v antecendentu, nebo-li klasické A AND B → C. Řekněme, že výrok C je true pouze, když výrok A a B je true. V Petriho sítích pak bude zápis vypadat následovně µ(t):AB→C.

Obrázek 10.: Konjunkce v antecedentu Nyní si toto pravidlo ověříme v Petriho sítí: a) Když A bude true B bude false pak C bude false

Obrázek 11.: Označkování A Přechod nenastane → C je false b) Když A bude false B bude true pak C bude false

Obrázek 12.: Označkování B Přechod nenastane → C je false c) Když A bude true B bude true pak C bude true

50


Obrázek 13.: Označkování A a B Přechod nastane → C je true Posledním nutným pravidlem je disjunkce v antecendentu, A OR B → C. Disjunkce v antecedentu

Řekněme, C je true, když A nebo B je true. Při použiti ekvivalence můžeme napsat ( A ∨ B → C ) ↔ (( A → C ) ∧ ( B → C )) µ(t1):A→C a µ(t2):B→C Toto pravidlo bychom mohli znázornit následovně.

Obrázek 14.: Disjunkce v antecedentu Nyní provedeme opět zkoušku jak se bude chovat Petriho síť v jednotlivých stavech. a) Když A bude true a B bude false pak C bude true

51


, Obrázek 15.: Označkování A Přechod nastane → C je true. b) Když A bude false a B bude true pak C bude true

, Obrázek 16.: Označkování B Přechod nastane → C je true. c) Když A bude true a B bude true pak C bude true

, Obrázek 17.: Označkování A a B Přechod nastane → C je true. Zde nastává problém. Jak už je patrno z obrázku zůstane nám v jednom z horních stavu token (v našem případě v A). Pokud bychom měli rozsáhlou síť objeví se nám tam navíc token, který by způsobil

52

Operační systémy - modelování a algoritmy paralelních výpočtů v sítí velké problémy. Podobné problémy, které se vyskytly u disjunkce v antecedentu

by nastaly při disjunkci s konsekventem. Z tohoto závěru

vyplývá, že nemůžeme použit klasickou logiku v klasických Petriho sítích. Abychom se těmto problémům vyhnuli pužijeme inhibitory. Inhibitorem zaručíme znázorňování všech logických formulí pomoci Petriho sítí. Podívejme se tedy ještě jednou na disjunkci v antecedentu s použitím inhibitoru. Petriho síť s inhibitorem pro disjunkci v antecedentu vypadá takto:

Obrázek 18.: Disjunkce v antecedentu s inhibitorem a) Když A bude true a B bude false pak C bude true

, Obrázek 19.: Označkování A Přechod nastane → C je true. b) Když A bude false a B bude true pak C bude true

53


, Obrázek 20.: Označkování B Přechod nastane → C je true. c) Když A bude true a B bude true pak C bude true

, Obrázek 21.: Označkování A a B Přechod nastane → C je true. Žáden token nám v počátečních stavech nezůstane, jako tomu bylo v klasických Petriho sítích.

8.3 Simulátor Petriho sítí HPSim Program HPSIM je volně dostupný program a lze stáhnout na adrese: http://www.winpesim.de/ Program není třeba nijak instalovat, pokud se jedná o stažený archiv, je nutno jej rozbalit do příslušného adresáře na disk.

54


Po spuštění programu se nám zobrazí následující okno:

Nyní si popíšeme nejdůležitější položky a nastavení , které se v programu nacházejí. Menu File Save - Uložení Petriho sítě do souboru. Standardní koncovka souborů je .hps Export - Export modelu PN-systému do souboru: •

Document - uložení celé sítě jako bitmapa Windows (.bmp)

•

View - uložení pouze označené části jako bitmapa Windows (.bmp)

•

Net - uložení následujících údajů pro pozdější možnost importu jiných programů (.txt): jména přechodů a míst, matice incidence, vektor značení, typy hran, druhy časových přechodů.

•

File - export do obecnějšího formátu (.hpx)

Menu Edit

55

Operační systémy - modelování a algoritmy paralelních výpočtů Group/Ungroup - sloučí / rozdělí označené objekty do jedné skupiny Popup - označené objekty nebo skupinu přenese do popředí Pushback - označené objekty nebo skupinu přenese do pozadí

Menu View Nastavení vypnutí/zapnutí zobrazování některých součástí na pracovní ploše. Mainbar - standardní sada nástrojů pro programy v prostředí Windows Simulation Bar - nástroje pro ovládání simulace Editbar - nástroje pro vytváření, editaci a manipulaci s prvky Petriho sítí a pasivních objektů Project Explorer - zde se nastavují vlastnosti jednotlivých prvků

Project Explorer - nastavení vlastností prvků sítě Editor Window - aktivuje se základní okno pro editaci Status Window - okno, které v textové podobě zobrazuje průběh analýzy a simulace Show Label - zobrazování pojmenování prvků v PN-systému

Menu Tools Všechny položky tohoto menu mohou být zobrazeny i přímo na pracovní ploše jako ikony. Select - označení nebo výběr objektu pro editaci Pan - volný pohyb po pracovní ploše pomocí myši

56

Operační systémy - modelování a algoritmy paralelních výpočtů Line - kreslení čáry Polygon - kreslení křivky Rectangle - kreslení obdélníku nebo elipsy Text - vloží textové pole Place - vložení místa Initial Tokens - počáteční množství tokenů Current Tokens - aktuální množství tokenů Capacity - max. kapacita místa v jednom značení (kolik se může v místě nacházet tokenů) Tokens Count - počítá kolik projde místem tokenů Transition - vložení přechodu Time Model - časový model udávající dobu trvání přechodu Initial Delay - počáteční zpoždění Range Delay - maximální možné zpoždění Current Delay - aktuální zpoždění při simulaci krok za krokem Tokens Fired - celkový počet tokenů, které přechod přijal Časové modely: Okamžitý - přechod bude proveden okamžitě Deterministický - v položce Initial Delay zadán čas, po jaké době bude přechod proveden S exponenciálním rozdělením - údaj v Initial Delay je střední hodnotou pro distribuční funkci exponenciálního rozdělení S uniformním rozdělením - hodnota v Initial Delay spodní a hodnota Range Delay horní hranicí pro distribuční funkci uniformního rozdělení Arc - vložení hrany Vlastnosti Weight - násobnost hrany

Obrázek 2.2: Tools - nástroje pro editaci Petriho sítí

Menu Simulation Klíčové menu programu, které umožňuje uživateli kontrolu nad průběhem simulace. Rovněž jsou tyto funkce dostupné přes ikony na pracovní ploše.

57

Operační systémy - modelování a algoritmy paralelních výpočtů Sim Mode - přepne uživatele do textového módu simulace nebo ho vrátí zpět do editačního režimu Single Step - umožňuje simulaci krok za krokem Run Normal, Run Fast - definuje rychlost simulace; normální nebo rychlá Increase Speed, Decrease Speed - rychlost simulace lze libovolně měnit (klávesami NUM+ a NUM-)<> Write Output File - zápis o průběhu simulace do výstupního souboru (vhodné pro rozpoznání, kde se nachází případný deadlock) Reset - obnovení původního nastavení PN-systému a příprava k nové simulaci

Simulation - nástroje pro simulaci

Menu Extra - nastavení editoru V tomto menu se nachází univerzální nastavení spojené s používáním editoru. Editor - nastavení velikosti základního okna, barvy pozadí atd. Grid - zapnutí/vypnutí zobrazování mřížky, rozteč rastru a možnost přichytávání objektů k mřížce Simulation - nastavení parametrů simulace: Sample Time: nastavení kroku časovače Simulation Time: nastavení maximální doby simulace (max. 160 mil.) Step Counter: nastavení maximálního počtu kroků simulace (max. 160 mil.) Output File: cesta kam bude uložen výstupní soubor s průběhem simulace

58


Extra (Properties) - nastavení parametrů simulace

Příklad. Model vytvořený pomoci HPSim První vytvořenou součástí sítě budou místa: V panelu nástrojů pro editaci sítě klikneme levým tlačítkem na ikonu znázorňující místo. Myší se na ploše postavíme tam, kde má místo} být a opět klikneme. Pokud je potřeba umístit další místa, nemusíme již tuto volbu označovat na panelu nástrojů, ale stačí posouvat a klikat levým tlačítkem myši nad pracovní plochou.

59


Postup při vkládání přechodů je velice podobný vkládání míst. Opět v panelu nástrojů klikneme na ikonu znázorňující přechod. Na ploše se kurzorem postavíme na místo, kde má být přechod a dalším kliknutím dojde k jeho vytvoření. Když chceme přidávat další, stačí klikat na ploše nad zvolenými místy.

Posledním prvkem do dotvoření modelu Petriho sítě jsou hrany. Myší klikneme na ikonu představující hranu. Postavíme se kurzorem nad objekt od kterého hrana povede. Stisknutím levého tlačítka a jeho následném uvolnění nad cílovým objektem dojde k propojení místa s přechodem. Opakováním tohoto postupu lze propojit všechny příslušné objekty.

60


V poslední fázi bychom měli určit vlastnosti sítě. Tyto vlastnosti nastavujeme kliknutím na jednotlivé prvky v sítí a v pravém okně vlastností upravujeme. Toto nastavení můžeme samozřejmě provádět už při výstavbě sítě. Při nastavování vlastností bychom neměli zapomenout na inicializaci sítě (tokeny). Ty lze také nastavit v režimu simulace.

Když je model dokončen a chceme provést simulaci, vybereme z menu Simulation volbu Sim Mode. Aktivuje se okno textových informací o simulaci. Pro lepší přehled a kontrolu nad situací je vhodné z menu Window vybrat položku Tile, čímž je uživatelův monitor rozdělen na dvě půlky. V jedné je možno sledovat samotný model PN-systému, v druhé zase textové informace o probíhající simulaci. Ihned po přepnutí do módu simulace se zobrazí základní charakteristika sítě: Počet míst a přechodů a také to, jestli se v síti vyskytují nějaké konflikty. Pokud ano, jsou tyto vypsány. Dále je zde základní časová jednotka, která bude použita při snižování zpoždění a limity po jejichž dosažení se simulace ukončí. Simulace je možná krok za krokem nebo zrychlená, přičemž rychlost jde nastavit. Při výběru tokengame (rychlá simulace) systém detekuje případný 61

Operační systémy - modelování a algoritmy paralelních výpočtů deadlock (uzamčení), o čemž uživatele informuje zprávou ve zmiňovaném textovém okně simulace.

Úloha: Vytvořte v simulátoru HPSim následující síť a proveďte simulaci.

5.2. Poses ++ Nyní si ve stručnosti popíšeme ještě další simulační nástroj. Princip těchto nástrojů je do jisté míry stejný a proto bude záležet na nás jaký program nám bude vyhovovat a který budeme používat.

62


Poses ++ je vysokorychlostní simulační prostředí. Modelování je založeno na vysoké úrovni Petriho sítě s časovanými přechody, je zaměřený obloukově, , zpřístupňuje algoritmizaci (FIFO, LIFO, beran, ...). Systém má za cíl nasimulovat rychle, užitečně a skutečně velké přesné modely. Největší známý ne-teoretický model celého systému obsahuje 30.000 přechodů, 30.000 predikátů a 100.000 utvořených elektrických oblouků. Nové pokusné modely obsahují přes 1.000.000 přechodů. Poses ++ je užitečný pro jakýkoliv druh modelování simulace (logistiky, hardware, komunikace, ...). Systém je postavený jako komplex multi - klientského/multi - serverového systému spojeného přes TCP/IP uvnitř LAN a přes internet. Toto a C- kódové rozhraní v modelovém jazyce nám dává největší možnosti pro jakýkoliv druh softwarové integrace.

5.3. Visual objekt oriented Petri Net based Engineering tool Visual objekt oriented Petri Net based Engineering tool si můžete stáhnout ze stránek www.systemtechnik.tu. Tento nástroj je velice podobný už dříve popisovanému nástroji HPSim. 63


Veškerá místo v okně programu je věnováno kreslící ploše. Vrchní lišta je obsazena klasickými tlačítky pro přechody, tokeny atd. Kreslící plocha je částečně překryta okny s vlastnosti libovolných objektu s kterými zrovna pracujeme. Práce s tímto programem je velice intuitivní a podobná HPSim, že nepotřebuje další podrobnější popis.

Program po spuštění

64


Vytváření sítě

65

Operační systémy - modelování a algoritmy paralelních výpočtů

Recommend Documents