Příprava na zk. z KIV/DS Obsah Příprava na zk. z KIV/DS.....................................................................................................................1 Oficiální studijní materiály.........................................................................................................1 01-intro..............................................................................................................................1 03-Sychro-tanenbaum........................................................................................................1 04-Transakce-tanenbaum...................................................................................................2 05-DSAlgoritmy................................................................................................................2 06-DS-deadlock.................................................................................................................2 07-Konzistentnost..............................................................................................................2 07-Replikace......................................................................................................................3 08-Coda (distribuovaný systém souborů)..........................................................................3 08-DFS (distribuovaný systém souborů)...........................................................................3 09-dsm...............................................................................................................................4 10-DS-Poruchy..................................................................................................................4 10-DS-Shoda.....................................................................................................................4 11-DS-Migrace..................................................................................................................4 12-DS-P2P_site.................................................................................................................5 13-DS-Corba......................................................................................................................5 13-lab-corba.......................................................................................................................6 Cviceni-DS-2006-02..........................................................................................................6 Minulé zkoušky...........................................................................................................................6 Zkouška DS - 11.1.2007....................................................................................................6 Požadavky na znalosti.................................................................................................................7 Požadavky na znalosti u zkoušky z KIV/DS.....................................................................7
Oficiální studijní materiály 01-intro ● ● ● ● ● ● ●
obecně o DS předpoklady pro realizaci DS transparentnost škálovatelnost chyby OS jednoproc., multipoč. a síťové + porovnání
03-Sychro-tanenbaum ●
● ●
synchronizace hodin ○ Cristiansův algoritmus – zk. 11.1.2007 ○ Berkeley algoritmus ○ Lamportův algoritmus (časové značky) globální stav algoritmus vhazování (Bully algoritmus) – zk. 11.1.2007 -1-
● ●
algoritmus výběru v kruhu vzájemné vyloučení – zk. 11.1.2007 ○ centralizovaný algoritmus ○ distribuovaný algoritmus ○ algoritmus předávání pověření v kruhu (token ring) ○ + porovnání
04-Transakce-tanenbaum ● ● ● ● ● ● ●
transakční model distribuované transakce – zk. 11.1.2007 dopředný log (writeahead log) řízení souběhu (concurency) serializovatelnost dvoufázové uzamykání pesimistické uspořádání časovými značkami
05-DSAlgoritmy ● ● ● ●
distribuované vzájemné vyloučení algoritmy výběru 1 z N algoritmy shody algoritmy detekce ukončení
06-DS-deadlock ● ● ● ● ●
distribuovaný deadlock podmínky vzniku deadlocku zpracování deadlocku prevence deadlocku detekce deadlocku ○ Ho a Ramamoorthy dvoufázový centralizovaný algoritmus detekce deadlocku ○ Ho a Ramamoorthy jednofázový centralizovaný algoritmus detekce deadlocku
07-Konzistentnost ● ●
replikace – pro a proti, škálovatelnost konzistenční modely ○ Data-Centric ○ striktní konzistentnost ○ linearizovatelnost a sekvenční konzistentnost ○ příčinná (casual) konzistentnost – zk. 11.1.2007 ○ FIFO konzistentnost ○ slabá (weak) konzistentnost ○ uvolňující (release) konzistentnost ○ vstupní (entry) konzistentnost ○ + přehled ○ Client-Centric ○ možná (eventual) konzistentnost -2-
○
monotónní čtení/zápis
07-Replikace ● ● ●
●
replikace – pro a proti, škálovatelnost replikace objektů distribuční protokoly ○ repliky iniciované serverem ○ porovnání – protokoly push a pop ○ protokoly se vzdáleným zápisem ○ protokoly s lokálním zápisem ○ aktivní replikace ○ protokoly založené na hlasování ○ Orca ○ příčinně konzistentní líná replikace zpracování operací čtení a zápisu
08-Coda (distribuovaný systém souborů) ●
Coda ○ úvod ○ princip komunikace ○ jména a identifikátory ○ sdílení souborů v Coda ○ transakční sémantika ○ cache na straně klienta ○ replikace serveru ○ přerušené operace ○ bezpečné kanály ○ řízení přístupu ○ + shrnutí
08-DFS (distribuovaný systém souborů) ●
● ●
NFS ○ architektura ○ model (operace) ○ komunikace ○ jména ○ automount (automatické mapování) ○ atributy souborů ○ sémantika sdílení souborů – zk. 11.1.2007 ○ uzamykání souborů ○ cache na straně klienta ○ chyby RPC ○ bezpečnost ○ řízení přístupu souborový systém Coda – totéž jako 08-Coda Plan 9 ○ komunikace -3-
procesy ○ jména úvod do xFS ○ procesy ○ jména úvod do SFS ○ jména + shrnutí ○
●
● ●
09-dsm
(dlouhý doc, vypadá to, že je snad jen souhrnem některých předchozích přednášek)
10-DS-Poruchy ● ● ● ● ● ● ●
●
odolnost proti poruchám základní pojmy typy poruch typy selhání maskování chyb a redundance/replikace ○ aktivní replikace dohoda v systémech s poruchami skupiny procesů a tolerance chyb ○ Byzantinské chyby ○ Byzantinští generálové – zk. 11.1.2007 obnova po chybě ○ incarnation numbers (etapa) ○ kontrolní body
10-DS-Shoda ● ● ●
synchronní a asynchronní systémy interaktivní konzistentnost algoritmy shody – zk. 11.1.2007 ○ Byzantinští generálové ○ 2-fázový commit ■ centralizovaný ■ distribuovaný ■ stavové přechody ■ problémy ○ 3-fázový commit ■ princip ■ stavy ■ komunikace
-4-
11-DS-Migrace ● ● ●
●
● ● ●
motivace flexibilita modely ○ migrace kódu ○ migrace zdrojů ○ migrace virtuální paměti metody migrace ○ zmražení a kopírování ○ metoda předběžného kopírování ○ líná migrace ○ migrace s distribuovaným systémem souborů migrace komunikačních kanálů migrace v heterogenních systémech + zhodnocení zda migrovat
12-DS-P2P_site ● ● ● ● ●
● ● ● ● ● ● ● ● ●
●
rozdělení P2P sítí způsoby vyhledávání obsahu v P2P sítích směrování v P2P typy P2P modely ○ klient/server ○ peer-to-peer architektura charakteristiky výhody P2P aplikace ○ sdílení souborů Napster Gnutella Kazaa (síť FastTrack) Freenet strukturované P2P sítě ○ distribuované hashovací tabulky (DHT) – zk. 11.1.2007 ■ Chord ■ Pastry ■ CAN BitTorrent
13-DS-Corba ● ● ● ● ● ●
princip IDL ORB IIOP architektura Dynamic Invocation Interface -5-
●
● ● ● ●
služby ○ typy ○ jmenné služby komunikace události přenos zpráv příklad
13-lab-corba
(více-méně k nastudování nic víc než v 13-DS-Corba) Cviceni-DS-2006-02 ● ● ● ● ● ●
Lamportův algoritmus Vektorové časové značky Dvoufázové provádění operací (2 phase commit) ABCAST CBCAST GBCAST
Minulé zkoušky Zkouška DS - 11.1.2007
1. Semantika sdileni souboru v DFS – 08-DFS 2. Příčinná konzistentnost – 07-Konzistentnost 3. Bully Algorithm – 03-Synchro-tanedbaum 4. Vlastnosti a omezeni RPC 5. Christiansuv algoritmus na synchronizaci hodin – 03-Synchro-tanedbaum 6. Algoritmus vzájemného vyloučení, centr. i decentr. - 03-Synchro-tanedbaum 7. Vnořené a distribuované transakce – 04-Transakce-tanedbaum 8. Distribuované hash. tabulky – 12-DS-P2P_site 9. Silná a slabá mobilita - ? 11-DS-Migrace ? 10. Algoritmy shody, Byzantinský generálové – 10-DS-Shoda
-6-
Požadavky na znalosti Požadavky na znalosti u zkoušky z KIV/DS
Požadavky tak jak je Ledvina při listování sešitem diktoval na poslední přednášce DS v roce 2006. ● ● ● ● ● ● ● ● ●
● ● ● ● ● ● ● ●
● ● ●
Úvod do DS: vlastnosti modelu server-client, P2P Co to je transparentnost Problematika chyb v systému Budování DS: od základu+nadstavba, příklady Komunikace: posílání zpráv Volání vzdál. podproramů: jak to vypadá se sémantikou (+chyby), způsob spojování (boundary), přenos parametrů Přímé/nepřímé zprávy, ... Skupinová komunikace: ab cast, cb cast, gb cast !!! Transakce: zákl. vl. (4), konzistentnost (špinavá data, ...), vnořené transakce (a jakým způsobem se zpracovávají), distrib. transakce (centraliz./decentraliz. zpracování = zámky), algoritmy hlasování, zámky a uzamykání (konfliktní vs. bezkonfliktní), řešení uzamykání pomocí časových značek, zotavení transakce po chybě (undo, redo), logové soubory, stínové stránky Vzájemné vyloučení: semafory, distrib. sem. Alg. pro výběru 1 z n, algoritmy pro schodu (bizanti, ...), dead-locky Alg. ohledně glob. stavu Čas: logický, fyzický, jeho synchronizace, lamportovy a vektorové časové značky Konzistentnost: co to je, striktní, ... Data centric, client centric systémy Distrib. syst. souborů: rozdělení na funkce, mapování, vyrovnávací paměti, rozdíl modelů nfs a afs + sémentika, sémantika sdílení souborů, stavovost a bezestavovost Distrib. sdílená paměť: rozhození dat po uzlech vs. repliky, techniky opravy kopií (write invalidate, write update), falešné zápisy (zápis po celých blocích místo jen po zapisovaných dat), evidence stránek (centralizované vs. vlastník = ten kdo zapisuje a na ostatní šíří kopie) Corba: něco základního: soft. sběrnice Mobilní agenti, migrace P2P sítě
Hodně štěstí.
-7-
