0. Terminologija i klasifikacija, 1 0.1 Paradigme konkurentnog programiranja, 1 0.2 Terminologija, 2 0.3 Klasifikacija konkurentnih i distribuiranih sistema, 4 0.4 Klasifikacija paradigmi konkurentnog programiranja, 5 0.5 Programiranje pomoću deljenih promenljivih, 7 0.6 Distribuirano programiranje, 8 0.7 Virtuelni prostori, 9 0.8 Programske niti, 10 0.9 Java, 11 0.9.1 Kreiranje i kontrola rada niti, 11 0.9.2 Sinhronizacija, 12
1. Uvod, 15 1.1 Deljeni objekti i sinhronizacija, 15 1.2 Nova priča о Alisi i Bobu, 17 1.2.1 Osobine uzajamnog isključivanja, 20 1.2.2 Naravoučenije, 20 1.3 Proizvođač potrošač, 21 1.4 Čitaoci i pisci, 23 1.5 Surova realnost paralelizacije, 24
2. Uzajamno isključivanje, 27 2.1 Vreme, 27 2.2 Kritične sekcije, 27 2.3 Rešenje za dve niti, 30 2.3.1 Klasa LockOne, 30 2.3.2 Klasa LockTwo, 31 2.3.3 Petersonov algoritam, 32 2.4 Filter algoritam, 34 2.5 Da li je ovo fer algoritam?, 37 2.6 Lamportov pekarski algoritam, 37 2.7 Vremenski žigovi, 39 2.8 Donja granica broja memorijskih lokacija, 42
4. SpinLock i konflikt, 66 4.1 Realni svet, 66 4.2 Test And Set, 69 4.3 Revidirani TAS Spin Lock, 71 4.4 Eksponencijalni Backoff, 72 4.5 Redovi čekanja za niti, 74 4.5.1 Ključevi zasnovani na nizu, 74 4.5.2 CLHQueueLock, 77 4.5.3 MCS Queue Lock, 79 4.6 Queue Lock sa tajmautom, 81 4.7 Kompozitni ključ, 84 4.7.1 Kompozitni ključ sa brzom putanjom, 89 4.8 Klasteri i hijerarhijski ključevi, 92 4.8.1 Hijerarhijski Backoff, 92 4.8.2 Hijerarhijski CLH Queue ključ, 93 4.9 Jedan ključ za sve probleme, 98 4.10 Napomene, 98 4.11 Literatura, 99
5. Monitori, 101 5.1 Potreba za monitorima, 101 5.2 Ključevi i uslovi monitora, 101 5.2.1 Objekat uslova, 102 5.2.2 Problem propuštenog buđenja, 105 5.3 Čitaoci i pisci, 107 5.3.1 Jednostavan ReadersWriters ključ, 107 5.3.2 ReadersWriters fer ključ, 109 5.4 Reentrant ključ, 112 5.5 Semafori, 112
6. Barijere, 114 6.1 Uvod, 114 6.2 Implementacija barijere, 115 6.3 Barijera sa promenom pamosti, 116 6.4 Barijera sa kombinacionim stablom, 117 6.5 Barijera sa statičkim stablom, 120 6.6 Barijere sa detekcijom završetka, 121
7. Transakciona memorija, 125 7.1 Uvod, 125 7.1.1 Šta nije u redu sa zaključavanjem?, 125 7.1.2 Šta nije u redu sa compareAndSet()?, 125 7.1.3 Šta nije u redu sa kompozicijom?, 127 7.1.4 Šta mi možemo da uradimo po tom pitanju?, 128 7.2 Transakcije i atomičnost, 128 7.3 Softverska transakciona memorija, 131 7.3.1 Transakcije i transakcione niti, 134 7.3.2 Konkurentnost i zombi transakcije, 135 7.3.3 Atomični objekti, 136 7.3.4 Zavisni i nezavisni progres?, 138 7.3.5 Upravljanje konfliktima, 138 7.3.6 Implementacija atomičnih objekata, 140 7.3.7 Atomični objekti bez opstrukcije, 142 7.3.8 Atomični objekti sa ključevima, 145 7.4 Hardverska transakciona memorija, 152 7.4.1 Koherentnost keša, 152 7.4.2 Transakciona koherentnost keša, 153 7.4.3 Poboljšanja, 154
14. Distribuirano uzajamno isključivanje, 393 14.1 Uvod, 393 14.2 Preliminarna razmatranja, 394 14.2.1 Model sistema, 394 14.2.2 Zahtevi koje mora da ispuni algoritam, 394 14.2.3 Metrike performansi, 395 14.3 Lamportov algoritam, 396 14.4 RicartAgrawala algoritam, 400 14.5 Singhal algoritam, 403 14.5.1 Opis algoritma, 405 14.5.2 Korektnost, 407 14.5.3 Analiza performansi, 408 14.6 LodhaKshemkalyani fer algoritam, 409 14.6.1 Model sistema, 409 14.6.2 Opis algoritma, 409 14.6.3 Kompleksnost poruka, 414 14.7 Uzajamno isključivanje na bazi kvoruma, 415 14.8 Maekawa algoritam, 416 14.8.1 Problem uzajamnog blokiranja, 417 14.9 AgarwalEl Abbadi algoritam na bazi kvoruma, 418 14.9.1 Konstrukcija kvoruma sa strukturom stabla, 419 14.9.2 Analiza algoritama za konstrukciju kvoruma sa strukturom stabla, 420 14.9.3 Validacija, 420 14.9.4 Primeri kvoruma sa strukturom stabla, 421 14.9.5 Algoritam za distribuirano uzajamno isključivanje, 422 14.9.6 Dokaz korektnosti, 423 14.10 Algoritmi na bazi tokena, 423 14.11 SuzukiKasami brodkast algoritam, 424 14.12 Raymond algoritam na bazi stabla, 426 14.12.1 Promenljiva HOLDER, 427 14.12.2 Funkcionisanje algoritma, 428 14.12.3 Opis algoritma, 429 14.12.4 Korektnost, 431 14.12.5 Analiza cene i performansi, 433 14.12.6 Inicijalizacija algoritma, 434 14.12.7 Otkazi i oporavak čvorova, 434 14.13 Literatura, 435
15. Distribuirana deljena memorija, 436 15.1 Apstrakcija i prednosti, 436 15.2 Modeli konzistentnosti memorije, 439 15.2.1 Striktna konzistentnost/atomična konzistentnost/mogućnost linearizacije, 440 15.2.2 Sekvencijalna konzistentnost, 444 15.2.3 Kauzalna konzistentnost, 447 15.2.4 PRAM (Pipelined RAM) ili konzistentnost procesora, 448 15.2.5 Spora memorija, 450 15.2.6 Hijerarhija modela konzistentnosti, 450 15.2.7 Modeli konzistentnosti kod sinhronizacionih instrukcija, 451 15.3 Uzajamno isključivanje u deljenoj memoriji, 453 15.3.1 Lamportov pekarski algoritam, 454 15.3.2 Lamportov WRWR mehanizam i brzo uzajamno isključivanje . .455 15.3.3 Hardverska podrška uzajamnom isključivanju, 458 15.4 Algoritmi bez čekanja, 460 15.5 Hijerarhija registara i simulacija izvršavanja bez čekanja, 461 15.5.1 SRSW bezbedan u MRSW bezbedan, 464 15.5.2 SRSW regularni u MRSW regulami, 464 15.5.3 Bulov MRSW bezbedni u celobrojni MRSW bezbedni, 465 15.5.4 Bulov MRSW bezbedan u Bulov MRSW regularan, 466 15.5.5 Bulov MRSW regulami u celobrojni MRSW regularni, 467 15.5.6 Bulov MRSW regulami u celobrojni MRSW atomični, 468 15.5.7 Celobrojni MRSW atomični u celobrojni MRMW atomični , .471 15.5.8 Celobrojni SRSW atomični u celobrojni MRSW atomični, 472 15.6 Deljeni objekat atomični snimak bez čekanja, 474 15.7 Literatura, 478
16. Dogovor i konsenzus, 480 16.1 Deflnicija problema, 480 16.1.1 Vizantijski dogovor i ostali problemi, 482 16.1.2 Ekvivalentnost problema i notacije, 483 16.2 Pregled rezultata, 483 16.3 Dogovor u sinhronim i asinhronim sistemima bez otkaza, 485 16.4 Dogovor u sinhromm sistemima sa otkazima, 486 16.4.1 Algoritam konsenzusa kod sinhronih sistema sa otkazima, 486 16.4.2 Konsenzus kod sinhronih sistema sa Vizantijskim otkazima, 487
16.5 Dogovor u asinhronim sistemima sa prenosom poruka i sa otkazima, 499 16.5.1 Rezultat nemogućnosti za problem konsenzusa, 499 16.5.2 Terminacioni pouzdani brodkast, 501 16.5.3 Predaja kod distribuiranih transakcija, 502 16.5.4 kset konsenzus, 502 16.5.5 Približni dogovor, 503 16.5.6 Problem preimenovanja, 509 16.5.7 Pouzdani brodkast, 515 16.6 Konsenzus bez čekanja kod asinhronih sistema sa deljenom memorijom, 515 16.6.1 Rezultat nemogućnosti, 515 16.6.2 Brojevi konsenzusa i hijerarhija, 518 16.6.3 Univerzalnost konsenzus objekata, 523 16.6.4 kset konsenzus u deljenoj memoriji, 528 16.6.5 Preimenovanje u deljenoj memoriji, 529 16.6.6 Preimenovanje kod deljene memorije upotrebom splitera, 531 16.7 Literatura, 533
17. Detekcija otkaza, 535 17.1 Uvod, 535 17.2 Nepouzdani detektori otkaza, 535 17.2.1 Model sistema, 536 17.2.2 Detektori otkaza, 537 17.2.3 Osobine kompletnosti i tačnosti, 537 17.2.4 Tipovi detektora otkaza, 539 17.2.5 Redukcija detektora otkaza, 540 17.2.6 Redukovanje slabog detektora W na jaki detektor S, 541 17.2.7 Redukcija slabog detektora sa odlaganjem 0W najaki detektor sa odlaganjem 0S, 543 17.3 Problem konsenzusa, 545 17.3.1 Rešenja problema konsenzusa, 545 17.3.2 Rešenje upotrebom jakog detektora otkaza S, 545 17.3.3 Rešenje upotrebom jakog detektora otkaza sa odlaganjem 0S, 547 17.4 Atomični brodkast, 550 17.5 Rešenje za atomični brodkast, 551 17.6 Najslabiji detektori otkaza koji rešavaju osnovni problem dogovora, 552 17.6.1 Realistični detektori otkaza, 553 17.6.2 Najslabiji detektor otkaza za konsenzus, 555 17.6.3 Najslabiji detektor otkaza za terminacioni pouzdani brodkast, 555 17.7 Implementacija detektora otkaza, 556 17.8 Protokol za adaptivnu detekciju otkaza, 558 17.9 Literatura, 562
PredgovorKonkurentni i distribuirani sistemi više nisu egzotična oblast koja se povremeno izučava na master ili doktorskim studijama. Današnji programi su inherentno konkurentni i/ili distribuirani, počev od multiprocesorskih sistema, implementacija GUI (sistemi zasnovani na događajima), preko operativnih sistema, sistema u realnom vremenu pa sve do intemet aplikacija kao što su IoT, blockchain, P2P, itd. pri čemu tu treba uključiti infrastrukturu i samog intemeta (algoritmi i protokoli prenosa i шtiranja informacija).
Ova knjiga je nastala kao rezultat višegodišnjeg iskustva u nastavi na predmetu [8015] Konkurentni i distribuirani sistemi, koji se izvodi na studijskim programima osnovnih akademskih studija Računarske nauke i Računarsko inženjerstvo na Računarskom fakultetu Univerziteta Union u Beogradu. Iako je u početku bila namenjena isključivo kao udžbenik za ovaj predmet, ispostavilo se da ona ima i širu primenu. Knjiga može da koristi svakome ко želi da nauči kako konkurentni i distribuirani sistemi funkcionišu i zbog čega nekada, pored svog uloženog truda u njihov razvoj, ne funkcionišu. Potrebno predznanje studenata je na nivou analize sekvencijalnih algoritama. Poželjno je poznavanje funkcionisanja operativnih sistema i programskog jezika Java.
Primeri u knjizi, koji su dati u programskom jeziku Java, namenjeni su isključivo obrazovanju. Namerno su izostavljeni delovi koji proveravaju moguće greške, izuzetke i slično, a pojedini delovi koda i nisu u izvršnom obliku, već predstavljaju neku vrstu pseudo koda.
Knjiga nema nameru da bude sveobuhvatna. Opisani su osnovni pojmovi i principi iz kojih se dalje mogu izvoditi novi rezultati koji su specifični za datu primenu. Ukazano je na važnost generalizacije, apstrakcije i transparentnosti pojedinih rešenja, kao npr. kod transakcione memorije ili distribuirane deljene memorije.
Materijal za knjigu prikupljan je iz različitih izvora, pri čemu je u početku korišćen u okviru Beleški sa predavanja koje su bile osnovna literatura za predmet Konkurentni i distribuirani sistemi. Sasvim je moguće da se neke rečenice i fraze pojavljuju bez navođenja izvora. Autor je uložio maksimalan napor da naknadno citira upotrebljene resurse, pri čemu se citirana literatura nalazi na kraju pojedinih poglavlja. Svaka sličnost sa literaturom koja nije citirana je nenamerna i autor na te rezultate ne polaže nikakva autorska prava. U pojedinim delovima knjige korišćene su informacije i iz drugih knjiga koje se bave konkurentnim i distribuiranim sistemima, i to:
• Terminologija i klasifikacija preuzeta je iz knjige: Igor Ikodinović, Zoran Jovanović, Konkurentno programiranje: Teorijske osnove sa zbirkom rešenih zadataka, Akademska misao, 2004.
• Prvi deo knjige, koji se odnosi na konkurentne sisteme, zasnovan je na rezultatima koji su opisani u knjizi: Maurice Herlihy, Nir Shavit, The Art ofMultiprocessor Programming, Morgan Kaufmann, 2012.
• Drugi deo knjige, koji pokriva distribuirane sisteme, zasnovan je razultatima koji su opisani u knjizi: Ајау D. Kshemkalyani, Mukesh Singhal, Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press, 2008.
• Neki primeri u Javi za distribuirane sisteme preuzeti su iz knjige: Vijay K. Garg, Concurrent and Distributed Computing in Java, John Wiley & Sons, 2004.
Bez obzira na uloženi napor, u tekstu sigurno postoje greške. Mole se savesni čitaoci da greške koje pronađu prijave izdavaču, a autor im na tome unapred zahvaljuje.
U Beogradu, januara 2019. godine Prof. dr Stevan A. Milinković
Detaljni podaci o knjizi
Naslov: Konkurentni i distribuirani sistemi Izdavač: CET Strana: 580 (cb) Pismo: latinica Format: B5 Godina izdanja: 2019 ISBN: 978-86-7991-412-5