zcu/kiv/ds/zkouska

Z Studentská wiki

[editovat] Příklady písemných prací ke zkoušce z DS

[editovat] Načrtněte architekturu multiprocesorového systému se čtyřmi procesory a čtyřmi pamětmi s omega architekturou

Multistage switched (omega networks) (propojeni pamětí a procesorů). Pro tento případ nám stačí 2 bity pro propojení jakéhokoliv procesoru s jakoukoliv pamětí.

1. Postupně přepínaná cesta mezi procesorem a pamětí
2. Při větším počtu stupňů pomalé
3. nlog(n) přepínačů

P1--                       --M1 
    \                     / 
     --SWITCH --- SWITCH -
    /        \  /         \
P2--          \/           --M2
P3--          /\           --M3
    \        /  \         /
     --SWITCH --- SWITCH -
    /                     \
P4--                       --M4

[editovat] Zakreslete obrázek s možnými typy třívrstvé architektury klient/server, uveďte příklady použití a zhodnoťte je.

Model třívrstvé architektury rozlišuje tyto vrstvy:

• Prezentační vrstva – obsahuje funkce uživatelského rozhraní. Obvykle existuje několik prezentačních vrstev pro různé druhy zařízení, platformy a prostředí
• Aplikační vrstva – tvoří prostředníka mezi vrstvou prezentační a vrstvou datovou . Obsahuje tzv. business logiku aplikace. V této vrstvě dochází k transformací dat mezi vstupně / výstupními požadavky a datovou vrstvou.
• Datová vrstva – obsahuje funkce pro přístup k informacím v datovém úložišti

[editovat] Nakreslete diagram komunikace mezi klientem a serverem s použitím synchronního a asynchronního posílání zpráv s potvrzováním.

[editovat] Co je to sémantika volání vzdálených podprogramů, jaké sémantiky znáte a čím se liší.

[editovat] Nakreslete schéma souběžného přenosu dvou zpráv mezi dvěma uzly pomocí protokolu ABCAST. Co protokol zaručuje.

[editovat] V zadaném obrázku doplňte hodnoty logických maticových hodin.

[editovat] Popište Christiansův algoritmus synchronizace hodin mezi dvěma uzly.

[editovat] Co jsou to vektorové časové značky a čím se liší od časových značek dle Lamporta. V zadaném schématu označte vektorové časové značky a určete, které události jsou konkurentní a které ne.

[editovat] Naznačte jak bude fungovat algoritmus pro určení globálního stavu pro tři procesy s tím, že každý proces může komunikovat s oběma svými sousedy.

[editovat] Naznačte jak probíhá 3 fázový Lamportův algoritmus pro řešení úlohy distribuovaného vzájemného vyloučení s pomocí časových značek pro 2 procesy.

[editovat] Jsou dány dvě transakce T1 {R(x); R(y); W(y); W(x) } a T2 {R(x); R(y)}. Naznačte algoritmus řízení souběhu pomocí časových značek.

[editovat] Je dána transakce {z  x; x  y; y  z }. Rozepište, co se uloží do logu a jak se obnoví data v případě zrušení transakce.

[editovat] Jak se řídí provádění transakcí pomocí časových značek. Uveďte příklad souběžného přístupu dvou procesů, provádějících identickou transakci nad dvěma proměnnými X a Y pomocí operací čtení a zápis. Prováděné operace jsou následující: r(X), r(Y), w(X),X+Y.

[editovat] Popište 2-fázový commit.

[editovat] Popište realizaci operací P a V nad semafory s využitím nedělitelných operací advance(E), await(E,v) a ticket(S).

[editovat] Jaký rozdíl je mezi striktní a sekvenční konzistentností. Ukažte na kontra příkladech.

[editovat] Na obrázku ilustrujte jak se od sebe liší sekvenční konzistentnost od FIFO konzistentnosti.

[editovat] Co je to PRAM (Pipelined RAM) konzistentnost. Určete možné (správné) výsledky v zadaném příkladě.

[editovat] Popište jak se provádí operace write-update a jak write-invalidate. Na obrázku naznačte, jak lze zajistit pomocí write-invalidate sdílení dat v případě, že vyžadujete vícenásobný přístup pro čtení a výhradní přístup pro čtení a zápis.

[editovat] V zadaném příkladě popište výměnu zpráv algoritmus vhazování (Bully algoritmus).

[editovat] Popište decentralizovaný algoritmus vzájemného vyloučení s použitím pověření, které je předáváno v logickém kruhu.

[editovat] Naznačte algoritmus detekce uvíznutí v distribuovaném systému se třemi oblastmi.

[editovat] Co je to uvíznutí, jaké jsou nutné podmínky pro uvíznutí, jak se řeší detekce a odstranění uvíznutí v distribuovaných systémech.

[editovat] Co je to Bankéřův algoritmus, co řeší a jak.

[editovat] Vyjmenujte a popište sémantiky sdílení souborů v distribuovaném souborovém systému.

[editovat] Jak se provádí mapování souborového systému a jaká pravidla by se měla dodržovat. Jak se zde projeví transparentnost umístění a transparentnost přemisťování.

[editovat] Vysvětlete problém osiřených stromů v distribuovaných souborových systémech.

[editovat] Popište, jak obecně funguje algoritmus shody. Ilustrujte na příkladu 3 procesů, které se mají dohodnout na jedné (minimální) hodnotě.

[editovat] Popište průběh výměny zpráv v případě 4 Byzantinských generálů (A, B, C, D), z nichž jeden je zrádce (algoritmus shody na vektoru hodnot s poruchou). Nastavované hodnoty jsou následující: A(1), B(2), C(3), D(4).

[editovat] Co to jsou inkarnační čísla a kde se používají.

[editovat] Popište algoritmus hlasování (Maekawa 1985).