Primenjeni distribuirani sistemi

Cilj i ishod predmeta

Uvod u koncepte i principe projektovanja u konstrukciji konkurentnih i distribuiranih sistema. Po završetku kursa, student je u stanju da: pokaže znanje i razumevanje različitih modela konkurentnih sistema kao i modela i arhitektura distribuiranih sistema; poseduje čvrstu osnovu u konceptima i principima projektovanja konkurentnih i distribuiranih sistema; projektuje i implementira softver u distribuiranom okruženju.

Teorijska nastava

Terminologija i klasifikacija. Uzajamno isključivanje. Konkurentni objekti. Konkurentnost i korektnost. Modeli konzistentnosti. Uslovi za progres. Spin-Lock. Test-and-Set (TAS). TTAS. Eksponencijalni Backoff. CLH i MSC Queue Lock. Kompozitni ključ. Klasteri i hijerarhijski ključevi. Monitori. Semafori. Barijere. Barijere sa promenom parnosti. Barijere sa kombinacionim i statičkim stablom. Barijere sa detekcijom završetka. Transakciona memorija. Transakcije i atomičnost. Softverska i hardverska transakciona memorija. Multiprocesorsko raspoređivanje. Raspodela opterećenja. Model distribuiranog izvršavanja. Modeli komunikacionih mreža. Globalno stanje distribuiranog sistema. Preseci kod distribuiranog izračunavanja. Logičko vreme. Sistem logičkih časovnika. Skalarno vreme. Vektorsko vreme. Matrično vreme. Sinhronizacija fizičkih časovnika. Globalno stanje i algoritmi za njegovo snimanje. Algoritmi za FIFO i ne-FIFO kanale. Snimanje stanja u sistemima sa kauzalnom isporukom. Nalaženje konzistentnih globalnih snimaka. Osnovni distribuirani algoritmi. Sinhronizatori. Izbor lidera. Redosled poruka i grupna komunikacija. Distribuirano uzajamno isključivanje. Distribuirana deljena memorija. Dogovor i konsenzus. Detekcija otkaza.

Praktična nastava

Implementacije sinhronizacionih primitiva i ključeva. Kreiranje i kontrola rada niti. Konkurentni alati. Rezervoari niti. Sinhronizacija. Proizvođač – potrošač. Čitaoci i pisci. Kritične sekcije. Petersonov algoritam. Filter algoritam. Lamportov pekarski algoritam. Spin-Lock i konflikt. Semafori i barijere. Prekid rada i uzajamno blokiranje niti. GUI – primeri konkurenosti. Distribuirani sistemi i brodkast. Implementacija vektorskih časovnika. Diferencijalna tehnika. Tehnika direktne zavisnosti. Adaptivna tehnika. Problemi u snimanju globalnog stanja. Algoritmi za FIFO kanale. Chandy–Lamport i Spezialetti–Kearns algoritam. Venkatesan inkrementalni algoritam. Helary talasni sinhronizacioni metod. Algoritmi za ne-FIFO kanale. Lai–Yang i Li algoritam. Mattern algoritam. Algoritmi za distribuirano uzajamno isključivanje. Lamportov algoritam. Ricart–Agrawala i Singhal algoritam. DHT i Chord.