Procesy a paralelismus, koordinace běhu procesů, synchronizace procesů a synchronizace procesů pomocí komunikace mezi nimi.

• proces je instance provádění programu
• proces je identifikovatelný
• proces vlastní nějaké prostředky (např. otevřené soubory, prostor v paměti)
• stav procesu je v každém jeho okamžiku definovatelný pomocí:
  • obsah registrů
  • zásobníku
  • datové sekce
  • programu, který jej řídí

Z hlediska jádra je proces považovaný za entitu, která právě disponuje přidělenými systémovými prostředky. Nejedná se pouze o vykonávaný kód programu, ale i kontext, ve kterém se vykonává. Do tohoto kontextu patří hodnoty čítače instrukcí, registrů procesoru, zásobník obsahující dočasné data procesu (parametry podprogramů, návratové adresy a lokální proměnné) a datový segment, který obsahuje globální proměnné.

Hlavní rozdíl mezi programem a procesem spočívá v tom, že program je pasivní jednotka – obsah souboru uloženém na disku, zatímco proces je aktivní jednotka, ve které čítač instrukcí určuje, která instrukce se bude vykonávat.
Nad jedním programem se může vykonávat více procesů, ale každý proces má svou sekvenci vykonávání. Proces může během svého běhu vytvářet další procesy.

• OS maximalizuje využití procesoru prokládáním běhu procesů (minimalizuje tak dobu odpovědi)
• OS spravuje zdroje přidělováním procesům podle zvolené politiky (priorita, vzájemná výlučnost, zabraňuje uváznutí)
• OS podporuje tvorbu procesu a jejich komunikaci
• OS s multiprogramováním (= multitasking)

OS si udržuje tabulku se seznamem procesů

• stavové informace (registry procesoru, čítač instrukcí)
• informace nutné pro správu a řízení procesu (priorita procesu, stav procesu, informace o používaných zdrojích, PID - identifikátor procesu, informace o používání paměti)

• Nový – proces je vytvořen buď uživatelem, nebo na žádost operačního systému o provedení služby, či na žádost jiného procesu (rodiče)
• Připravený – čeká na přidělení procesoru
• Běžící – program se interpretuje procesorem
• Čekající – např. na I/O operaci
• Ukončený – ukončil své provádění

Proces je jednotka provádění programu, charakterizovaná přiděleným kontextem a paměťovým prostorem.

Vlákno je systémový objekt viditelný uvnitř procesu, typicky se vlákna přidělují procesům. Vlákno může být buď běžící nebo připravené a může přistupovat ke zdrojům vlastněným procesem.

Pokud vlákno přistoupí k nějakému zdroji, například si otevře soubor, vidí jej všechna ostatní vlákna daného procesu.

Vlákna si může spravovat buď aplikace sama, nebo se o ně může starat kernel.

• využití CPU (max)
• propustnost (max) – počet procesů, které dokončí svůj běh za jednotku času
• doba obrátky (min) – doba provedení konkrétního procesu
• doba čekání (min) – doba, po kterou proces čekal ve frontě připravený (ready)
• doba odpovědi (min) – doba, která uplyne od zadání požadavku do doby první reakce

Hlavním úkolem plánovací strategie je zamezit stárnutí procesů (starvation) a zajistit spravedlivé rozdělení času procesoru.

Nepreemptivní plánování – nedovoluje odebrání procesoru spravovanému procesu až do jeho dokončení (problém zasekávání u Windows 95).

First Come First Served (FCFS) – použitelný při dávkovém zpracování.

Shortest-Job-First Scheduling (SJF) – s každým procesem je asociován čas jeho následujícího CPU cyklu. Je-li CPU volný, je přidělen procesu s nejkratším následujícím CPU cyklem (preemptivní, nepreemptivní varianty)

Prioritní plánování (preemptivní, nepreemptivní) – zpracování z řady připravených procesů podle určitého kritéria. Priorita může být statická, dynamická, může být stanovena externím zadáním nebo vypočítána vnitřně v závislosti na průběhu zpracovávání a zatížení výpočetního systému.

Round Robin (RR) – podobný First Comes First Served, ale obsahuje navíc možnost preemptivního plánování. V systému je definovaná malá časová jednotka – časové kvantum – většinou 10-100 ms. Fronta připravených procesů je definována jako cyklická fronta a plánovač CPU touto frontou prochází stále dokola a přiděluje CPU jednotlivým procesům vždy na jedno časové kvantum.

Pro paralelní procesy musí obecně platit podmínka, že první operace jednoho procesu musí být zahájena dříve, než je ukončena poslední operace druhého procesu. Z hlediska synchronizace paralelních procesů není důležité, zda se skutečně překrývají v čase, nebo pouze střídavě využívají stejný procesor.

Paralelní procesy dělíme na soupeřící a spolupracující.

Soupeřící procesy se snaží získat výlučný přístup ke sdílenému prostředku. Pro tyto procesy se řeší úloha vzájemného vyloučení.

Spolupracující procesy také využívají společné prostředky. Pro spolupracující procesy se řeší úloha vzájemného vyloučení i úloha synchronizace pro zabezpečení správného pořadí vykonání obou procesů. Klasická úloha: producent-konzument.

Se souběžně běžícími procesy se můžeme setkat buď v přímo paralelním prostředí, kde je jedna paměť sdílena více procesy, nebo v prostředí distribuovaném, kde má každý proces vlastní lokální paměť. Hlavním problémem výskytu souběžných procesů je sdílení prostředků (paměť, zařízení, soubory, atd.) Tento problém se vyskytuje dokonce i v mnohouživatelských OS, kdy se např. řeší sdílení paměti mezi hlavní linií výpočtu v jádře a obslužnou rutinou přerušení při I/O operaci. Především při sdíleném přístupu do paměti nebo do souboru mohou vznikat neočekávané problémy – časově závislé chyby.

Souběh (race condition) je situace, kdy při přístupu dvou nebo více procesů ke sdíleným datům dojde k chybě, přestože každý z procesů samostatně se chová korektně. K chybě dochází díky tomu, že data jsou modifikována některým procesem v době, kdy s nimi jiný proces provádí několik operací, o kterých se předpokládalo, že budou provedeny jako jeden nedělitelný celek. Datům, která jsou sdílena několika procesy tak, že při přístupu k nim by mohlo dojít k souběhu, se říká kritická oblast.

Kritické oblasti jsou části programů, které využívají sdílené proměnné a jsou citlivé na synchronizaci. Jedná se pouze o ty části programu, které pracují se sdílenými proměnnými a pro které je potřeba zabezpečit vzájemné vyloučení. Zbývající část programů netvoří kritické oblasti, protože nepoužívá sdílené proměnné a neklade proto žádné požadavky na synchronizaci. Vzájemné vyloučení zabezpečuje, aby žádné dva procesy nebyly současně v kritické oblasti a tím se zabraňuje časové závislosti. Samotné vzájemné vyloučení není dostatečnou podmínkou pro správnou spolupráci paralelních procesů a pro efektivní využívání sdílených prostředků.

Pro správné řešení problému kritické sekce je třeba zajistit:

• Podmínku bezpečnosti (vzájemné vyloučení; mutual exclusion) – když proces provádí kritickou sekci, nemůže žádný jiný proces začít provádět kritickou sekci sdruženou se stejným zdrojem.
• Podmínku živosti (trvalost postupu) – jestliže žádný proces neprovádí kritickou sekci sdruženou s nějakým zdrojem, pak výběr procesu, který chce vstoupit do kritické sekce, sdružené s tímto zdrojem, nesmí trvat nekonečně dlouho.
• Podmínka spravedlivosti (konečnost doby čekání) – musí existovat horní mez počtu, kolikrát je povolen vstup do kritické sekce sdružené s nějakým sdíleným zdrojem jiným procesům, než procesu, který vydal žádost o vstup. To znamená, že pokud jeden proces usiluje o vstup do kritické sekce, nemohou ostatní procesy tomuto vstupu zabránit tím, že se v kritické sekci neustále střídají – mohou do této kritické sekce vstoupit pouze omezený počet krát (zpravidla pouze jednou)

Úlohou synchronizace je zajistit vzájemné vyloučení paralelních procesů, které využívají sdílené prostředky. Prakticky to znamená, že se rychlosti procesů musí sladit tak, aby se časy vykonání jejich kritických sekcí nepřekrývaly. Při tomto se uplatňují dva základní principy: aktivní a pasivní čekání.

Synchronizace aktivním čekáním znamená, že se odsun kritické sekce uskuteční vložením pomocných (běžně prázdných) instrukcí do kódu procesu. Mezi prostředky pro synchronizaci aktivním čekáním patří:

• zákaz přerušení (vhodné pro procesy jádra OS) - Zákaz přerušení znemožní přepnutí kontextu. Proces pak ale může zhavarovat nebo se dostat do nekonečného cyklu, což se může projevit zamrznutím celého systému.
• instrukce Test and Set Lock
• použití proměnných programů (pekařův algoritmus – čísla a postupné odbavování),
• Compare-and-swap.

Pasivní čakání znamená, že se odsun kritické sekce uskuteční dočasným pozastavením procesu, dokud se kritická sekce neuvolní. Mezi prostředky pro synchronizaci pasivním čekáním patří semafory a monitory.

Semafor je synchronizační primitivum, které obsahuje celočíselný čítač. Využívá se zejména jako ochrana proti souběhu proto, že chrání přístup do kritické sekce, k čemuž používá dvojici operací V (up) a P (down). Je tak zobecněním instrukce TSL, která používá proměnnou typu boolean. Operace down otestuje stav čítače a v případě že je nulový, zahájí čekání. Je-li nenulový, je čítač snížen o jedničku a vstup do kritické sekce je povolen. Při výstupu z kritické sekce je vyvolána operace up, která odblokuje vstup do kritické sekce pro další (čekající) proces. Čítač je možné si představit jako omezení počtu procesů, které mohou zároveň vstoupit do kritické sekce nebo například jako počitadlo volných prostředků.

Obecný semafor – celočíselná hodnota z neomezeného intervalu.

Binární semafor (mutex) – hodnota 0 nebo 1, jednodušší implementace, lze s jeho pomocí implementovat obecný semafor.

pokud zapomeneme v semaforu použít operaci release() na konci kritické sekce, potom procesy čekající ve frontě budou čekat navždy (uváznutí). Proto se používá monitor, synchronizační nástroj vyšší úrovně. Tento nástroj zavádí invariant, který musí být splněn v případě, že proces končí kritickou sekci. Dále obsahuje semafor pro výlučný přístup a sadu procedur, kterými lze manipulovat se sdílenou proměnnou. Deklaruje se proměnná typu condition, na které jsou definované dvě operace:

• wait() – proces, který volá tuto operaci je potlačen do doby, než jiný proces provede operaci signal()
• signal() – aktivuje právě jeden proces, který volal wait().

Monitory jsou bezpečnější než semafory, neboť jejich použití může řešit kompilátor a ne programátor, který může na správné zamykání zapomenout.

Monitor se skládá z dat, ke kterým je potřeba řídit přístup, a množiny funkcí, které nad těmito daty operují. Když chce proces vstoupit do monitoru (tj. zavolat jeho funkci), musí nejdříve získat zámek. Pokud zámek v tu chvíli drží někdo jiný, tak se proces zablokuje a čeká, dokud se zámek neuvolní (tj. dokud jiný proces neopustí monitor nebo nezačne čekat na podmíněnou proměnnou).
Monitor většinou splňuje dodatečné podmínky:

• data monitoru jsou přístupná jen z jeho funkcí,
• funkce monitoru nepoužívají data mimo monitor,
• každá funkce zajistí, že před uvolněním zámku jsou data v konzistentním stavu.

Pokud jsou tyto podmínky splněny, platí, že žádný proces nenajde data v nekonzistentním stavu, což je přesně důvod pro zavedení synchronizačního primitiva.

V této úloze se jedná o dva spolupracující procesy, které komunikují přes vyrovnávací paměť omezené velikosti. První proces produkuje informaci a vkládá ji do vyrovnávací paměti, odkud ji druhý proces vybírá.

• je třeba jeden semafor pro vzájemné vyloučení na bufferu (mutex) a další 2 semafory pro indikaci prázdných a plných míst (full a empty)
• zajistí se tím vlastnosti vzájemného vyloučení, dále vyloučení možnosti plnění již plného bufferu nebo čtení z prázdného bufferu

Souběh čtení a modifikace dat. Datový objekt (soubor nebo záznam) je sdílený mezi několika procesy. Některé procesy mohou pouze číst obsah sdíleného objektu, nazýváme je čtenáři, jiní ho mohou modifikovat (tj. číst i zapisovat) a nazýváme je písaři. Synchronizační problém spočívá v zajištění výlučného přístupu písařů. Čtenáři mohou k objektu přistupovat souběžně, zatímco písaři výlučně. V opačném případě může vzniknout chaos. Úloha se dá řešit pomocí semaforů:

• operace zápisu musí být exkluzivní – operace čtení mohou čtený zdroj sdílet, ovšem operace čtení musí být výlučná s operací zápisu
• priorita čtenářů – první čtenář daného zdroje zablokuje všechny písaře, poslední čtenář opět uvolní přístup písařům, písaři mohou stárnout. Řešení:
  • semafor wrt pro písaře
  • semafor readCountMutex pro čtenáře
  • využití integer readCount určující počet aktivních čtenářů, pokud se zvýší na 1, zamkne se wrt, pokud se sníží na 0, odemkne se wrt
• priorita písařů – totéž + první písař zablokuje přístup ke zdroji čtenářům, čtenáři mohou stárnout. Řešení složitější – 5 semaforů a 2 integery (ASI TODO).

Řešení uváznutí. Je pět filozofů, kteří tráví svůj život jídlem a přemýšlením. Filozofové sedí okolo kulatého stolu, na stole je pět talířů se špagetami a pět vidliček. Čas od času filozofovo rozjímání přeruší hlad a on se chce najíst. Za tímto účelem potřebuje dvě vidličky. V daném okamžiku filozof může filozof sebrat jen jednu vidličku a teprve poté se pokusí sebrat druhou. Nemůže sebrat vidličku, kterou už drží jeho soused. Pokud dostane obě dvě vidličky, může jíst, jinak musí nechat vidličku na stole a pokusit se o získání vidliček později. Naopak, pokud obě dostane, nají se, položí obě vidličky zpět na stůl a pokračuje v přemýšlení.
Synchronizační problém tu spočívá v nedovolení filozofovi držet jednu vidličku a čekat na uvolnění té druhé, protože může nastat uváznutí.

Možné řešení: zrušení symetrie, filozof smí uchopit vidličky jen když jsou obě dvě volné a musí je uchopit v kritické sekci. Řeší se pomocí monitoru.

Existuje rozdělení architektur na:
SIMD (Single Instruction Multiple Data) - provádíme jednu operaci nad více daty. Procesory jsou synchronizovány a provedení jedné operace jim trvá stejně dlouho.
MIMD (Multiple Instruction Multiple Data) - univerzálnější architektura. Každý procesor má svoje data a dělá si vlastní operace. Náročné na programování. Procesory jsou desinchronizované a řeší se zde známé synchronizační problémy. Dá se zde nasimulovat i SIMD model.

Bázovými formami komunikace mezi procesy (IPC - Interprocess Communication) probíhají pomocí výměny zpráv (message passing) nebo přes sdílenou paměť (shared memory).

Zaslaní zprávy může být realizováno předáním ukazatele na zprávu ve sdílené paměti, umístěním zprávy do vyrovnávací paměti nebo do fronty zpráv bud’ ve sdílené paměti nebo v paměti jádra systému, přičemž systém pak zajišťuje kopírovaní zpráv do paměťového prostoru příjemce zprávy, možná je i komunikace prostřednictvím sítě.

Nad zprávami jsou definované obyčejně alespoň dvě základní operace:

• send
• receive

Zprávy mohou mít buď pevnou nebo variabilní délku. Procesy, které komunikují, musí mít možnost jak na sebe odkazovat. Lze použít přímou nebo nepřímou komunikaci.

Následující interpretace z fi.muny je dost podivná, takže berte s rezervou nebo si udělejte vlastní přehled, … a nebo to tu upravte
Porty jsou IMHO právě od toho, že nelze adresovat procesy v jiném počítači (neznáme jejich PID) a proto posíláme na WK nebo předem domluvené porty a port-mapper je doručí správnému procesu.

Při přímé komunikaci každý proces, který potřebuje komunikovat, musí explicitně pojmenovat svého partnera. V tomto případě operace send a receive mají tvar:

• send(P,m) – zpráva m je zasílaná procesu P
• receive(P,m) – přijímá zprávu m od procesu Q

Při nepřímé komunikaci jsou zprávy zasílané a přijímané z mailboxů (někdy též označované jako porty). Na mailbox se můžeme abstraktně dívat jako na schránku, do které se zprávy mohou zasílat a vyzvedávat. Každý mailbox má svůj unikátní identifikátor. Jeden proces může komunikovat s dalšími procesy skrze několik různých mailboxů. Dva procesy mohou komunikovat přes mailbox jen pokud je tento mailbox sdílený. Operace send a receive mají v tomto případě tvar:

• send(A,m) – zasíllá zprávu m do mailboxu A
• receive(A,m) – přijímá zprávu m z mailboxu A

Ukázka komunikace:
Máme k dispozici schránku o kapacitě n zpráv a funkce pro zasílání zpráv send a příjem zpráv receive. Pokud je schránka prázdná a proces volá receive(), pak se proces uspí. Pokud je schránka přeplněná a proces volá send(), pak se také uspí. Pokud je schránka prázdná a proces volá send(), pak probudí jeden z čekajících procesů, který zavolal receive() na prázdnou schránku a analogicky naopak.

Příklad:
Vzájemné vyloučení zprávami

• mailbox mutex sdílený n procesy
• send() je asynchronní a končí odesláním zprávy
• receive() je synchronní, čeká, až je mailbox mutex neprázdná
• inicializace send(mutex, 'go')
• do kritické sekce vstupí proces P, který dokončí receive() jako první
• ostatní procesy čekají, dokud P zprávu 'go' nevrátí do schránky

Producent-Konzument

• producent umiťuje položky do mailboxu mayconsume
• konzument může konzumovat položky z mayconsume
• do mailboxu mayproduce se umístí n prázdných zpráv, tyto neprázdné zprávy se můžou přepsat produkovanými zprávami (omezení velikosti na n zpráv)

V bodech:

• Vlastní paměť u každého procesoru
• Explicitní komunikace – předávání zpráv
• Vysoká cena komunikace (výměny dat)
• Možnost prokládání výpočtů a komunikace

označuje část operační paměti RAM, do které může přistupovat více procesů zároveň za účelem zajištění komunikace. Poskytuje nejrychlejší komunikaci mezi procesy. Stejný paměťový segment je mapovaný do adresních prostorů dvou nebo více procesů. Ihned jak jsou data zapsaná do sdílené paměti, procesy, které mají k této paměti přístup mohou data číst. Při souběžném přístupu ke sdíleným datům je třeba zajistit synchronizaci přístupu. V tomto případě zodpovědnost za komunikaci padá na programátora, operační systém poskytuje pouze prostředky pro jeho uskutečnění.

V bodech:

• Paměť je oddělená od procesorů
• Uniformní přístup k paměti
• Nejsnazší propojení procesorů s pamětí je sběrnice
• „Levná“ komunikace
• Složité prokládání vypočtu a komunikace (aktivní čekání)

následující odstavec bych opět doporučil brát s rezervou

Roury (pipes) a FIFOs (pojmenované roury) – používané nejčastěji na přesměrování výstupu jednoh procesu na vstup dalšího. Je to nejvhodnější prostředek na implementace interakce mezi procesy založený na metodě producent/konzument. Roura je v příkazové řádce reprezentována znakem |.
FIFOs se od rour lyší pouze tím, že používají speciální soubory, do kterých popořadě zapisují svoje bajty a tak je možné tyto pojmenované roury za běhu mezi sebou sdílet.

zdroj míchá jedno přes druhý, nutno upravit

velká část paměti (RAM - Random Access Memory), do které lze přistupovat z několika procesorů (CPU - Central Processing Unit) víceprocesorového počítačového systému.

Synchronní komunikace pomocí zpráv (vysílač musí počkat až do doby než je k převzetí zprávy připraven i přijímač). Procedurální komunikace, která připomíná běžnou proceduru. RPC mechanismus kromě vlastní výměny žádostí mezi klientem a serverem, provedením funkce serverem a vrácení odpovědi klientovi má i mechanismus, který dává procedurální komunikaci formu běžného volání procedury. Tento mechanismus se nazývá stub (opět s rezervou).

Volání vzdálené metody používané v Javě je podobné RMI s tím rozdílem, že dovoluje předání objektů jako parametru volání vzdálené metody.

Koncové body pro komunikaci. Procesy komunikují pomocí dvojice socketů. Sockety využívají architektury klient-server. Socket se skládá z IP adresy a portu uzlu, ke kterému je připojený.

/nutno dodělat/

Distributed shared memory
Pokus vytvořit Shared Memory systém nad fyzicky distribuovaným hardwarem. Procesory mají opět každý svoji paměť, ale systém bude mít větší latence, protože je pod ním schováno zasílání zpráv.

Knihovna. Netransparentní, progámator musí program explicitně přizpůsobit.

Množina procesů uvázla, pokud každý proces z množiny čeká na událost, kterou může vyvolat pouze jiný proces z množiny. Protože všechny procesy z množiny čekají, žádný z nich nemůže vyvolat očekávanou událost, která by mohla uvolnit některý z čekajících procesů, tím pádem došlo k uváznutí.

Pro vznik uváznutí existují 4 podmínky (3 nutné, jedna postačující):

• výlučný přístup (mutual exclusion) - Existence prostředků, které jsou přidělovány pro výhradní použití jednomu procesu, tj. nesdílitelných prostředků.
• postupné přidělování prostředků (hold and wait) - Procesy nežádají o přidělení všech prostředků najednou, ale postupně. Pokud požadovaný prostředek není volný, musí proces čekat.
• nepreemptivní přidělování prostředků (no preemption) - jednou přidělené prostředky nelze procesu odebrat
• cyklické čekání (postačující podmínka)

Možné řešení problému uváznutí

Ignorování problému Pokud například můžeme odhadnout střední dobu mezi dvěma uváznutími na jeden rok, zatímco poruchy technických prostředků nebo selhání vlivem chyby v OS se vyskytuje přibližně každý měsíc, je jednodušší a lacinější poruchy uváznutí ignorovat.

Detekce uváznutí a zotavení systému (prevence) Nesplnění některých podmínek (spooling, jednorázové přidělování, násilné odebrání prostředku, hierarchické přidělování)

Vyvarování se uváznutí Přidělovat procesům prostředky a zároveň kontrolovat, zda požadované přidělení prostředku nevede k uváznutí. Správce prostředků si při tom ponechává potřebné rezervy prostředků, které zaručí, že procesy budou moci dokončit svou práci a nedojde k uváznutí. Tato metoda se nazývá bankéřův algoritmus.

Více například v AP5, IN5 Operační systémy.

PB152 - Operační systémy
PA150 - Principy operačních systémů
IA039 - Architektura superpočítačů a intenzivní výpočty

Tomáš Hřebíček, 256479
Marek Menšík, 255679

Zdroj je z fi.muny.cz, přeloženo do češtiny a upraveno.
http://www.nti.tul.cz/~kolar/os/os.pdf http://www1.osu.cz/~prochazka/ds/P3.pdf http://labe.felk.cvut.cz/vyuka/A3B33OSD/Tema-05-IPC+Deadlock-OSD-4.pdf http://is.muni.cz/auth/el/1433/jaro2012/IA039/um/vi/?videomuni=IA039-D2-20120306.avi - Nejdulezitejsi prednaska na FI:-) Hned ze zacatku vysvetli SIMD, MIMD, komunikaci mezi procesory, COMA, NUMA, cache coherenci a pak i propojovaci site(torus, hyperkrychle), tedy spousta veci napric otazkami magisterskych statnic.