{{predmet|Principy distribuovaných systémů|Filip Zavoral|SWI035}}
Anotace podle SISu: Funkce a architektury distribuovaných systémů, komunikace, synchronizace a identifikace objektů. Vzdálený běh a migrace procesů, distribuované souborové systémy, replikace. Distribuované sdílení paměti - konzistenční modely, distribuované stránkování.
Hezky přednášené.
== fragmenty ==
;vektorové hodiny
:vektor s kusy podle uzlů, před odesláním zvýším svoje počítadlo; před přijetím čekám, než moje hodiny budou větší než u zprávy ve všech složkách kromě odesílatele (tam může být zpráva o jednu větši); po přijetí svoje zvýším na maximum po složkách
:pro víc skupin: u zprávy posílám vektory všech skupin, kde jsem; při příjmu kontroluju kauzalitu i pro všechny skupiny, kde jsem (kromě té odesílatele, kde u něj může být větší o jedničku)
;logické hodiny
:průběžně si zvyšuji čas, když mi přijde zpráva, s časem >=, než mám, tak si svůj zvětším
;volba koordinátora
:bully (posílám větším), kruhový
;globální stav
:při příchodu značky ji rozešlu na výstupy a označím svoje I/O jako svůj stav, pak u příchozích kanálů počítám zprávy a čekám na značku. až přijde, zprávy mezi první a příchozí značkou kanálem jsou stav toho kanálu
;konzistence
*strict (vše viditelné hned všude)
*sekvenční (výsledek stejný, jako by procesory běžely v nějaké sekvenci a každý procesor běžel *podle programu -- může dát různé výsledky při spuštění stejného programu (není zaručeno zpoždění), *signatura (výstupy procesů v pevně daném pořadí), r+w>=t)
*kauzální (pořadí vázané jen pro kauzálně závislé věci, jako u zpráv, vyžaduje graf závislostí)
*PRAM (pipelined RAM, události jednoho procesu viděny ve stejném pořadí, nutné dodržet pořadí zápisů z jednoho zdroje)
;synchronizační proměnná
*weak (SP sekvenčně konzistentní, na SP se sahá až skončí všechny předchozí zápisy, na data se sahá až skončí všechny přístupy k SP)
*release (před přístupem k datům musí být dokončeny všechny Acq(), před Rel() musí být ukončeny všechny předchozí zápisy a čtení procesu, Acq() a Rel() musí být PRAM konzistentní)
**eager (vše se propaguje po Rel())
**lazy (vše se sosá před Acq())
*entry (Acq() až po aktualizacích všech chráněných dat, exkluzivní (RW) přístup k SP je exkluzivní -- po jeho skončení si příští přístup musí vyžádat kopii od vlastníka; sdílená data vázána na SP
;distribuované stránkování
*falešné sdílení (nezávislá data na stejné stránce)
*sekvenčně konzistetní (pro zápis musím být jediný vlastník)
*kauzálně konzistentní (vektorové hodiny pro stránky a procesy, při zápisu se zvýší TS stránky i procesu, při přenosy stránky se přiřadí procesu max, při zvýšení TS procesu se zneplatní stránky s nižším TS ve svém políčku)
;distribuované sdílené proměnné
*knihovny (typicky se SP, eliminace falešného sdílení,nepodporováno OS, závislé na jazyku, nutnost rekompilace, Munin -- read only, migratory (eager release), write-shared (dirty copy on write, po release se propaguje, při konfliktu dirty/dirty porovnání a případný pád)... konvenční sdílená (signle writer, many readers -- jako distrib. stránkování, sekvenční konzistence)
*distribuované objekty (základní distribuovaný předek, pak potomci, class deifinition language -- automatické generování kódu, middleware: CORBA, Java RMI)
;kapabilita
:jednoznační identifikace objektu a přístupu (user nemůže měnit ani generovat)
:ns - publikace kapabilit, reg - zádosti o otevření kanálu
;deadlocky
*pštrosí algoritmus
*detekce horší než lokálně: wait-for-graph (detekovaný deadlock musí existovat)
*centralizovaný (kauzální doručování proti falešnému uváznutí), hierarchický (každý řeší deadlocky podřízených)
*path-pushing (uzly sparvují lokální kusy WFG, sousedním uzlům zasílání externí žádosti, phantom deadlock s cyklem mezi uzly?)
*edge-chasing (pošlu zprávu všem, na které čekám, pokud se vrátí, jsem v háji -- ale mezitím se to ale mohlo doblokovat (řešení - aging, overkill -- zpráva zároveň hledá kandidáta))
;alokace
*up-down (trestné body + za proces jinde, - za neuspokojený požadavek, jinak směrem k nule)
*migrace s VP (při migraci -- dlouhé, pre-copy -- něco se kopíruje dvakrát, copy on reference)
*přesměrování (dočasné trvalé, komu oznámit?)
;systémy
*DEMOS/MP (83, migrace - cíl si proces tahá k sobě, nepřijaté zprávy přeneseny při migraci)
*Charlotte (sběr statistiky, podle toho migrace, při migraci se kopírují jen hlavičky zpráv, zbytek se dotahává potom průběžně)
*V (migruje se "logical host" -- víc procesů + adresový prostor), precopy)
*MOSIX (Izrael)
*Sprite (chtěli všechna volání jádra formardovat na pův systém -- reziduální dependence doma)
;load-balancing
*páry
*mosix (vektor, první vždy vlastní, pak pošle náhodně půlku pryč, došlá se proloží s vlastní)
*centralizované/hierarchické vyvažovací algoritmy
*lokální (prahová hodnota, když přelezu, ptám se po volných)
*problémy -- aktuálnost, samotná zátěž algoritmu
== Odkazy ==
*http://ulita.ms.mff.cuni.cz/mff/sylaby/swi035.html - Domovská stránka předmětu kde naleznete i promítané slajdy.
* http://www.cs.vu.nl/~ast/books/ds1/
** Distributed Systems: Principles and Paradigms; Andrew S. Tanenbaum, Maarten van Steen
** vo Figures veľa pekných diagramov
** v Sample Sections časti z kapitol knihy, jedna je napr. o RPC, jedna o CORBA-e
* http://www.sics.se/~seif/DatorSystem/2001/slides/ch12b.ppt
* učební text od Zavorala - dist-p.doc, 110 stran, 2.5MB
