99 - Interakce mezi procesy a typické problémy paralelismu (synchronizační a komunikační mechanismy).
pátek 1. dubna 2016
10:58
Interakce mezi procesy
Interakce
Competition (soupeření) 
For use of resources
Because we are multiplexing resources
Mutual exclusion problem
Cooperation (kooperace) 
Each process solves part of problem
Pojmy 
Deadlock:  situace, kdy úspěšné dokončení první akce je podmíněno předchozím dokončením druhé akce, přičemž druhá akce může být dokončena až po dokončení první akce.
Nutné podmínky pro výskyt deadlocku:
Vzájemné vyloučení. Alespoň jeden zdroj je držen tak, že není sdílen s ostatními procesy
Alespoň jeden proces má nějaký zdroj a čeká na uvolnění jiného zdroje
Procesy se nemohou vzdát svého zdroje
Je zde cyklický graf procesů, kde p1 čeká na p2, p2 na p3... pn na p1
Vyhladovění: je to problém, kde procesu je opakovaně odmítáno přidělení zdrojů, které potřebuje ke svému běhu.
Kritická sekce: je to nejmenší část kódu, kde dochází k přístupu ke sdílenému prostředku (např. sdílená data, která označujeme jako kritická oblast), ke kterému nemohou současně přistupovat dva nebo více procesů
Přístupy pro implementaci KS:
Softwarové: bez podpory programovacího jazyka nebo OS
HW: speciální instrukce
OS: OS poskytuje podporu pro KS
Vzájemné vyloučení (mutual exclusion): je algoritmus používaný v programování jako synchronizační prostředek. Zabraňuje tomu, aby 2 procesy operovaly nad sdíleným prostředkem, jako například globální proměnná. Požadavky pro vzájemné vyloučení:
Pouze jeden proces může být v daném okamžiku v KS
Proces, který zastaví v nekritické sekci nesmí ovlivňovat ostatní procesy
Bez deadlocku a vyhladovění
Když není nikdo v KS, tak jakýkoliv proces, který vstup požádá ho musí dostat
Proces zůstane v KS konečnou dobu
Nezávislé na počtu procesorů nebo jejich rychlosti
Algoritmy vzájemného vyloučení v KS
Dekkerův algoritmus
Kód je pro 2 procesy (i a j), ale funguje i pro víc
Máme sdílené proměnné flag pro každý proces a jednu sdílenou proměnnou turn
Procesy si nastaví proměnnou flag, pokud chtějí jít do KS
Pokud je jich víc, tak se do KS pustí ten proces, jehož index je uložen v proměnné turn. Zbylé procesy, co se nedostanou do KS, cyklí na while (flag[j]) - tedy cyklí tak dlouho dokud flag druhého procesu (toho co je v KS) je nastaven na true
Proces co se dostal do KS, tak tam něco provede a po vystoupení z KS  přepíše proměnnou turn na hodnotu index druhého procesu. Potom přehodí svoji proměnnou turn na false a tím druhý proces přestane cyklit na while a vstoupí do KS
Petersonův algoritmus
Znovu flagy pro každý proces a proměnné turn. Pokud chce do KS, nastaví si flag na true.
Turn nastaví na index druhého procesu. Ten kdo tam to zapsal poslední bude čekat, zatímco ten druhý proces půjde do KS
Po ukončení KS proces nastaví flag na false a tím aktivuje druhý proces, který může jít do KS
Pomocí operátoru AWAIT
Operátor AWAIT:
<await B -> S>
<> značí atomicitu
B je booleovská podmínka
S je sekvence příkazů, které skončí v konečném čase
S se provede pouze pokud B je true
Obvykle je impementace awaitu příliš náročná a tak se moc nepoužívá
Proces čeká dokud flag toho druhého procesu je false.
Pak vstoupí do KS
Operátor je atomický, tak to tak jde udělat
Pomocí instrukce Test&Set
Lock = 0 -> KS je volná
Tzn. pokud je lock = 0 (false), tak while hned skončí (T&S vrací původní hodnotu svého parametru - pokud je lock false, tak vrátí false) a jde se do KS
Pomocí instrukce Swap
Vždy vyměníme lock a key. Pokud key je 0 (před výměnou byl tedy lock 0), tak se jde do KS a současně se KS uzamče, protože do lock se swapne 1. Jinak se cyklí
Synchronizační struktury
Semafor
Synchronizační nástroj, který nepoužívá aktivní čekání
Semafor S je struktura, která obsahuje integerovou proměnnou (zde bude nazývaná count) a frontu procesů. Kromě inicializace může provádě jen následující atomické  a vzájemně výlučné operace:
P(S) - vstup do semaforu
V(S) - uvolnění semaforu
Pokud proces čeká na semaforu, tak je zablokován a dán to fronty semaforu (pasivní čekání)
Pokud je count menší než 0, tak count značí počet procesů čekající na semaforu. Pokud je count větší než 0, tak count značí počet procesů, které mohou provést P(S) bez toho aby byly zablokovány
Použití semaforu pro čízení přístupu ke KS
Použití semaforu pro synchronizaci
Chceme aby S1 v P1 byl vykonán před S2 v P2
Speciálním případem jsou binární semafory. Jediný rozdíl je, že count je bool proměnná a tedy v KS může být max 1 proces. 
Monitor
High-level jazykové konstrukce, které poskytují shodnou funkcionalitu jako semafory, ale jsou snadněji použitelné
Mohou být implementovány pomocí semaforů
Je to softwarový modul, který obsahuje:
Jednu nebo víc procedur
Inicializační sekvenci
Lokální proměnné
Charakteristiky:
Lokální proměnné, které jsou přístupné pouze procedurám monitoru
Proces vstoupí do monitoru tím, že zavolá jednu z jeho procedur
Pouze jeden proces může být v monitoru v jeden čas
Condition variables
Jsou přístupné pouze z monitoru
Může k ním být přistupováno pouze pomocí těchto dvou funcí:
Proces dostane řízení pouze pokud jiný proces zavolá signal(a)
signal(a) - vzbudí nějaký blokovaný proces, který čeká na podmínku a
From <[link]> 
Typické problémy paralelismu
Večeřící filozofové (Dining philosophers)
5 filozofů, 5 vidliček
filozofové celý život přemýšlejí nebo jedí
filozof potřebuje 2 jemu nejbližší vidličky aby mohl jíst
deadlock (každý vezme 1 vidličku)
Řešení: 
lichý filozof bere nejdříve levou a pak pravou, sudý naopak [1]
vyhladovění (některému filozofovi soustavně chybí levá nebo pravá vidlička)
Čtenáři a písaři (Readers/writers)
k proměnné ve sdílené paměti přistupuje souběžně několik procesů:
čtenáři chtějí hodnotu číst - může jich přistupovat více současně
písaři chtějí hodnotu přepsat - k proměnné může v jeden okamžik pro zápis přistupovat jen jeden
dokud je proměnná zamčená pro zápis, nikdo nemůže ani číst
pokud je proměnná zamčená pro čtení, další čtenář by neměl být nucen čekat
1. řešení - reader priority: první čtenář zabírá zápisový zámek, poslední ho uvolňuje
samotné zamykání a odemykání čtenářem musí být obklopeno dalším zámkem - zajistí aby neprvní čtenáři čekali až první získá zápisový zámek [2]
neřeší hladovění písařů - pokud stále přicházejí noví čtenáři, žádný písař se nikdy nedostanou ke slovu
2. řešení - writer priority: inkrementace počtu čtenářů obalena zámkem, který písaři udržují zamčený po dobu kdy někdo hodlá zapisovat/zapisuje
Producenti a konzumenti (producer/consumer problem)
fronta/buffer pro komunikaci mezi procesy - producenti produkují data (přihazují do fronty), konzumenti konzumují (vyjímají z fronty)
pokud je fronta prázdná, konzument musí čekat dokud do ní něco není vloženo
pokud je velikost fronty omezená a fronta plná, producent musí čekat až bude ve frontě místo na jeho data
je nutné zajistit vzájemné vyloučení při práci s frontou
Řešení:
 void consume(){
     pthread_mutex_lock(mutex);
     while(isEmpty){
         pthread_cond_wait(isEmptyCond, mutex);
     }
     
     wasFull = queue->isFull();
     consumed = queue->pop();
     
     if (wasFull) {
         pthread_cond_signal(isFullCond);
     }
     pthread_mutex_unlock(mutex);
     return consumed;
 }

 void produce(produced){
     pthread_mutex_lock(mutex);
     while(isFull){
         pthread_cond_wait(isFullCond, mutex);
     }
     
     wasEmpty = queue->isEmpty();
     queue->push(produced);
     
     if (wasEmpty) {
         pthread_cond_signal(isEmptyCond);
     }
     pthread_mutex_unlock(mutex);
     
 }

From <[link]> 
Notes
2. Otazka (predmet) (okruh): Interakce mezi procesy a typické problémy paralelismu
Kdo me primarne zkousel: Orság
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Od základu k čemu je synchronizace mezi procesy a kritická sekce, přes atomické HW instrukce (TestAndSet a Swap), semafory, mutexy, monitory. Nakonec vymyslet úplně jednoduchý příklad, kde by bylo nutné použít KS (třeba čtenáře a písaře nechtěl, to že je moc složité), po chvilce zamyšlení jsem vyplodil dva procesy, kde jeden čte string do bufferu, druhý si ho občas zkopíruje a pracuje s ním. Pristup k bufferu je v KS, jinak by obsah mohl být nekonzistentní.
From <[link]> 
. Otazka (predmet) (okruh): 47. Interakce mezi procesy a typické problémy paralelismu (synchronizační a komunikační mechanismy). (PRL)
Kdo me primarne zkousel: Zboril ml.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: V podstate me nechal mluvit, rekla jsem obecne proc jsou treba takove mechanismy - bud vzajemne vylouceni nebo synchronizace, pak jsem rekla neco obecne o KS a pak jsem zacala mluvit o semfaorech, k tomu mel obcas nejake doplnujici dotazy, obcas jsem moc nechapala co presne mysli ale celkove to bylo docela v pohode. Na uplny konec jeste doslo na monitory, rekla jsem nejaky obecny zaklad, pak chtel neco vedet ale nechapala jsem moc co, zazvonil budik a nakonec rekl ze teda staci.
From <[link]> 
Interakce mezi procesy a typické problémy paralelismu (PRL)
Kdo me primarne zkousel: Staudek Jan, Doc. Ing. CSc.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Na papieriku bolo napísané, že sa mám zamerať na uviaznutie. Povedal som si, že dve také super otázky som si ani nezaslúžil, ale potom to prišlo. Chcel som nakresliť nejaký obrázok, od čoho ma zastavil a že to mám len nejak popísať. Tak som začal o tom ako môžu uviaznúť dva procesy, že napr. majú alokované zdroje a každý chce navzájom ten svoj. Na čo povedal, že to nechce. Keď som začal o kritickej sekcii, tak ma hneď zastavil, že o nej nič nechce. Skúšal som, či ma nechá rozprávať o semafóroch, monitoroch, algoritmy som mu chcel popísať, ale nič z toho ho vraj nezaujímalo. Až potom zo seba dostal, že chce počuť nutné podmienky k tomu, aby nastalo uviaznutie. A hneď na to som si spomenul, že veď to bolo na IOS, ale je to už nejaký rok odvtedy a už som bol tak zdeptaný, že som si na to nespomenul. A keď už začal sám hovoriť a ja som sa chytil a chcel pokračovať, tak zvýšil hlas, aby to dopovedal on. Ku koncu sa pridal aj Vojnár a chceli ako sa deteguje to uviaznutie. Povedal som že napríklad grafom, kde sú uzly procesy a prostriedky a keď vznikne cyklus, tak môže vzniknúť prípadné uviaznutie. A potom ako sa tomu predíde. Tak som povedal, že procesy môžu mať prioritu, tak tomu s menšou sa odobere zdroj. Z IOS sa mi vybavil aj spôsob vyhnutia uviaznutia tým, že si jeden proces mohol alokovať len prostriedky, ktoré majú väčší index ako jeho aktuálne prostriedky. Ale stále som na nich videl, že to nie je úplne to, čo chcú. Ja som im chcel povedať, že to čo chcú nie je úplne to, čo sme k tej téme brali na PRL, ale tak asi som to mal vedieť. Po chvíli povedali, že koniec a von som šiel z úplne neistým pocitom, ale dúfal som aspoň v E za aspoň nejaké tie veci, čo som spomenul i keď pána Staudeka nezaujímali. Naštastie to vyšlo - E.
From <[link]> 
Interakce mezi procesy, typicke problemy paralelismu
Kdo me primarne zkousel: Herout
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Zacal jsem nejaky obecny reci o synchronizaci. Nasledovala otazka na bariery, dostali jsme se k semaforum (signalizace udalosti - obecne semafory). Rychly prulet, jenom obecne veci. 
From <[link]> 