PDS P.pdf

Uvod 1. Koja je razlika izmedju konkurentnog i paralelnog izvrsavanja programa? Paralelno izvrsavanje predstavlja istovremeno izvrsavanje vise racunarskih operacija, programa ili delova programa. Konkuretno izvrsavanje predstavlja izvrsavanje vise programskih tokova jednog programa tako da oni...

Uvod 1. Koja je razlika izmedju konkurentnog i paralelnog izvrsavanja programa? Paralelno izvrsavanje predstavlja istovremeno izvrsavanje vise racunarskih operacija, programa ili delova programa. Konkuretno izvrsavanje predstavlja izvrsavanje vise programskih tokova jednog programa tako da oni napreduju u vremenu, ali se oni ne moraju obavezno izvrsavati istovremeno. 2. Dati jednu od definicija DS DS cine hardverske ili softverske komponente smestene na umrezenim racunarima i koje komuniciraju i koordiniraju svoje akcije samo prenosenjem poruka. 3. Koji su razlozi za razvoj DS? Povecanje dostupnosti i pouzdanosti,bolje performanse, lakse skaliranje resursa sistema i resavanje zahtevnih problema. 4. Koji problemi postoje kod projektovanja DS? Komunikacija moze da otkaze, procesi mogu neocekivano da se zaustave, diskovi i drugi hardverski uredjaji mogu da otkazi, fault tolerance - otpornost na otkaze i svaki kvar se desava nepredvidivo. 5. Koje su sve osobine DS? a) Vise racunara - cvorovima (konkurentno izvrsavanje, nezavisni kvarovi, automatizovana administracija, veliki broj cvorova b) Mrezna komunikacija (asinhrona, nebezbednost, nepouzdanost) c) Cilj (konzistencija, transparentnost) 6. Koji sve tipovi transparetnosti postoje kod DS? Pristup, lokacija, migracija,replikacija, konkurentnost i otkazi. Konkurentnost 1. Koje su razlike izmedju procesa i niti? Procesi su instance programa koje se izvrsavaju. Poseduju virtualni adresni prostor i jednu ili vise niti. Niti su entiteti kojima upravlja scheduler. Izvrsavaju se u adresnom prostoru svog procesa kome pripadaju. 2. Koje resurse niti imaju same, a koje resurse dele sa ostalim nitima unutar procesa? Svaka nit ima svoj stek, programski brojac i registar. Resurse koje niti dele su: heap, segment podatka, kod segmenta, signali i obrada signala… 3. Koje su prednosti konkurentnog izvrsavanja programa? Omogucava da se preklopi racunanje i I/O pristup na jednom racunaru. Moze da pojednostavi strukturu koda i/ili da poboljsa odziv. Omogucava laksu upotrebu vise CPU-ova. 4. Kako se manifestuje problem utrkivanja odnosno race conditions kod pristupa deljenom resursu? Pr ,,roditelji kupuju mleko deci” -> ,,ostaviti nalepnicu” => uglavnom ispravan kod. Dve ili vise niti pristupaju istovremeno jednom deljenom resursu, moze dovesti do veoma neocekivanih rezultata. 5. Sta je kriticna sekcija i sta je uzejamno iskljucivanje i kako se ostvaruje? Kriticna sekcija je deo koda koji ne sme da se izvrsi konkurentno od strane vise od jedne niti. Uzejamno iskljucivanje: ako se jedna nit izvrsava u kriticnoj sekciji, svim ostalim nitima je zabranjeno da udju u kriticnu sekciju. Ostvarivanje: jedna nit uvek ima dozvoljen pristup kriticnoj sekciji.  6. Sta je atomska operacija? Atomska operacija je nedeljiva; ona se ili u potpunosti ili se uopste ne izvrsava. 7. Kako se implementira kriticna sekcija putem mutex-a? Dati primer Dodaljivanjem katanca za uzejamno iskljucivanje. (thread 2 je isti kao i thread 1). // thread 1 LOCK(frižiderLock); mleko = vidiFrižider(); if(!mleko) kupiMleko(); UNLOCK(frižiderLock); Koriscenjem mutex-a (friziderLock) obezbedjuje samo jednu nit u isto vreme moze pristupiti i azurirati zajednicki resurs (frizider). Ovo sprecava utrkivanje i osigurava da se mleko kupuje samo jednom 8. Koje su osobine deadlock-a, livelock-a i starvation-a kod konkurentnog izvrsavanja niti? DeadLock - stanje kada se procesi/niti uzejamno blokiraju. LiveLock - procesi/niti se ne blokiraju, nema napretka u izvrsavanju. Starvation - proces koji zeli da udje u kriticnu sekciju ce uci, ali nece biti efekta. 9. Pr. uzejamnog iskljucenja preko LockOne class LockOne implements Lock { private boolean[] flag = new boolean; public void lock() { int i = ThreadID.get(); // niti imaju id-jeve 0 i 1 int j = 1 - i; flag[i] = true; while (flag[j]) {} // wait } public void unlock() { int i = ThreadID.get(); flag[i] = false; } } Polje zastavica (flag) ima dve vrednosti, po jednu za svaku nit, koje označavaju da li nit želi ući u kritični sekciju.U metodi lock, trenutna nit postavlja svoju zastavicu na true i čeka dok druga nit takođe želi ući u kritični sekciju.U metodi unlock, trenutna nit postavlja svoju zastavicu na false, signalizirajući da je završila sa kritičnim sekcijom. 10. Pr. uzejamnog iskljucenja preko LockTwo class LockTwo implements Lock { private volatile int victim; public void lock() { int i = ThreadID.get(); victim = i; // prepuštanje da druga nit ide prva while (victim == i) {} // wait } public void unlock() {} } Polje victim je varijabla koja označava koja nit mora čekati, deklarirana kao volatile radi vidljivosti promena svim nitima.U metodi lock, trenutna nit dobija svoj ID i postavlja victim na svoj ID, signalizirajući da daje prednost drugoj niti, te čeka dok je victim jednak njenom ID-u. Metoda unlock je prazna jer kontrolu redosleda niti upravlja varijabla victim. 11. Pr. Petersenovog algoritma (LockOne i Lock Two) Process P (1) loop non-critical section flag[P] = true victim = P while(flag[Q] && victim == P); critical section flag[P] = false Process Q (2) loop non-critical section flag[Q] = true victim = Q while(flag[P] && victim == Q); critical section flag[Q] = false Izvršava ne-kritičnu sekciju. Postavlja flag[P] na true kako bi označio da želi ući u kritičnu sekciju.Postavlja victim na P, dajući prednost drugoj niti. Čeka dok flag[Q] nije false i victim nije P.Ulazi u kritičnu sekciju. Postavlja flag[P] na false nakon izlaska iz kritične sekcije. Isto tako i proces Q. 12. Pr. filter algoritma int[] level(#threads), int[] victim(#threads) lock(me) { for (int i=1; i= i && victim[i] == me) {}; } } unlock(me) { level[me] = 0; } Ovaj algoritam koristi niz level za označavanje nivoa na kojem se nalaze niti u procesu zaključavanja i niz victim za odlučivanje koja nit treba čekati. Algoritam osigurava međusobno isključivanje i pravičnost u pristupu kritičnoj sekciji za više niti, omogućavajući da niti postepeno prolaze kroz nivoe pre nego što uđu u kritiču sekciju.  13. Pr. Ticket algoritma int number = 1, next = 1, turn[1:n] = ([n] 0); process CS[i = 1 to n] { while (true) { critical section; noncritical section } } Ovaj algoritam koristi promenljive number, next, i niz turn kako bi osigurao da niti ulaze u kritičnu sekciju redosledom koji je definisan redosledom dodeljenih brojeva. Algoritam osigurava međusobno isključivanje i pravičnost, jer svaka nit mora čekati svoj red da uđe u kritičnu sekciju. 14. Pr. Pekarskog algoritma Process P loop non-critical section np = nq + 1 while (nq != 0 && nq < np); critical section np = 0 Process Q loop non-critical section nq = np + 1 while (np != 0 && np 0 || writersWaiting>0) try { wait(); } catch (InterruptedException e){} readers++; } synchronized void release_read() { readers--; notifyAll(); } synchronized void acquire_write() { writersWaiting++; while (writers > 0 || readers > 0) try { wait(); } catch (InterruptedException e) {} writersWaiting--; writers++; } synchronized void release_write() { writers--; notifyAll(); } } 12. Osobine asinhronog i sinhronog prosleđivanja poruka. Asinhrono: ne blokira slanje poruka i blokira primanje Sinhrono: blokira oba 14. Način sinhronizacije korišćenjem wait(), notify(), notifyAll(). U Javi postoji mehanizam za uslovni red za čekanje – skup čekajućih niti (wait set), koje čekaju da se ispuni neki uslov. Svaki objekat u Javi ima metode za uslovni red za čekanje i to: wait(), notify(), notifyAll(). Jedna nit može pozvati ove metode na nekom objektu, samo ako je zaključala dati objekat, tj. ima lock nad njim. while(!preduslov){ wait() //otkljucaj objekat i cekaj dok te ne probude eventualno se moze desiti tajmaut ili da je niti prekinuta ponogo dobijanje lock-a nad objektom } wait() – nit oslobadja lock na objektu i blokira se/čeka. Druge niti mogu da dobiju lock na objektu i promene njegovo stanje, neki uslov... notify() – metoda budi jednu nit koja čeka u redu na ovom objektu, ali ta nit nakon budjenja mora da sačeka da se oslobodi lock notifyAll() – metoda budi sve niti koje čekaju na ovom objektu – koje su izvršile wait() Nakon notifyAll, probudjene niti čekaju prvo da se oslobodi lock nad objektom, pa onda jedna po jedna dobija lock i mogu da nastave dalje ako je uslov ispunjen!. Probudjene niti proveravaju uslov u while petlji i može se desiti da se opet blokiraju, ako uslov nije ispunjen – možda ima više uslova za razne niti!  15. Primeri i zadaci implementacije proizvođača-potrošača u Javi korišćenjem uslovnih redova za čekanje. public class Consumer extends Thread{ private final UnboundedBuffer buffer; … public void run(){ long prime; while(true){ synchronize (buffer){ while(buffer.isEmpty()) buffer.wait(); prime buffer.take(); } computation(prime); }}} public class Producer extends Thread{ private final UnboundedBuffer buffer; … public void run(){ … while (true){ prime = computerNextPrime(prime); synchronize(buffer){ buffer.put(prime); buffer.notifyAll(); } }}} 16. Primeri i zadaci implementacije proizvođača-potrošača u Javi korišćenjem implementacija Condition i Lock interfejsa U Javi se sa synchronized koriste unutrašnji, tzv. intrinsic lock-ovi.Postoje i eksterni lock-ovi u paketu java.util.concurrent.locks. Fleksibilniji su za upotrebu za neke klase problema.Mogućnost pokušaja da se dobije lock, vreme isteka, mogućnost prekidanja(interrupted). public interface Lock{ void lock(); void lockInterruptibly() throws InterruptedExteption; boolean tryLock(); boolean tryLock(long timeout, TimeUnit unit) throws InterruptedExeption; void unlock(); Condition newCondition(); } Kada se Lock koristi kao zamena za synchronized, tada je Condition zamena za Object metode wait, notify i notifyAll. Nudi mogućnost više redova za čekanje na jednom Lock-u!Condition omogućuje da se neka nit suspenduje, dok je neka druga nit ne probudi ako je promenila neki uslov. Condition condition = lock.newCondition(); //Kreiranje novog uslova condition.await() – ekvivalent Object.wait(); condition.signal() – ekvivavelnt Object.notify(); condition.signalAll() – ekv. Object.notifyAll(); public class ConditionBoundedBuffer{ protected final Lock lock = new ReentrantLock(); // CONDITION PREDICATE: notFull (count < items.length) private final Condition notFull = lock.newCondition(); // CONDITION PREDICATE: notEmpty (count > 0) private final Condition notEmpty = lock.newCondition(); private final T[] items = (T[]) new Object[BUFFER_SIZE]; private int tail, head, count; 17. Primeri i zadaci implementacije proizvođača-potrošača u Javi korišćenjem BlockingQueue-a. Korišćenje uslovnih redova za čekanje preko Object metoda ili Condition može da bude izazovno za pisanje korektnih programa. Sinhronizacija izmedju proizvodjača i potrošača se može postići lakše sa nekom od implementacijom BlockingQueue intefejsa.Blokirajuće metode take i put za uzimanje i smeštanje objekata u red, ako je red prazan ili pun respektivno.Neblokirajuće metode sa tajmaoutom: boolean offer(E e) ili offer(e, timeoutMs, timeUnit) E poll(long timeout, TimeUnit unit) – vraća null ako je prazan red FIFO implementacije ArrayBlockingQueue i LinkedBlockingQueue. Preko reda: PriorityBlockingQueue 18. Realizacija problema čitaoca i pisaca preko ReadWriteLock-a. Ne postoji problem kod čitanja deljene promenljive izmedju više niti.Postoji problem kod upisa u deljenu promenljivu izmedju više niti.Postoji problem kod upisa i čitanja deljene promenljive izmedju više niti. Čitaoci – samo čitaju; Pisci – čitaju i pišu. Ideja: pustiti više čitaoca da konkurentno pristupa deljenim promenljivama, bez medjusobnog isključivanja, ako nema pisaca. Samo prvi čitalac zahteva medjusobno isključivanje. Ako naidju drugi čitaoci, nije potrebno medjusobno isključivanje. Ako naidje jedan pisac, on će čekati dok svi čitaoci ne izadju iz kritične sekcije. Ako je jedan pisac u kritičnoj sekciji, čitaoci moraju da sačekaju. Ima dosta primera kada je operacija čitanja češća od upisa podataka – primer lookup operacije.Implementacija preko Read-Write lock-a!  public class ReadWriteMap { private final Map map; private final ReadWriteLock lock = new ReentrantReadWriteLock(); private final Lock r = lock.readLock(); private final Lock w = lock.writeLock(); public ReadWritemap(Map map){ this.map = map; } } 19. Osobine StampedLock-a i njegova primena StampedLock je kreiran da bi se još više poboljšale performanse. Prilikom poziva writeLock() i readLock() vraća se kao rezultat vremenski trenutak (stamp) kada je dobijen lock i sa tom vrednošću se poziva unlockWrite(long stamp) odn. unlockRead(long stamp). Takodje, nudi mogućnost nadogradnje sa read na write lock, ako druge niti ne drže read lock istovremeno Optimističko čitanje: Pozivom tryOptimisticRead() pokušava se dobiti dozvola za čitanje ako nema aktivnog write lock-a, kao rezultat se dobija vremenski stamp.Nakon toga se čitaju promenljive i pozivom validate(stamp) proverava se da li je u medjuvremenu bio write lock. 20. Primeri i zadaci sa StampedLock-om public class OptimisticLocking{ private final StampedLock sl = new StampedLock(); public double optimisticRead(){ long stamp = sl.tryOptimisticRead(); // dobijen vremenski trenutak double currentState1 = state1, currecntState2 = state2. … etc.; // citanje promenjljivih u lokane prom. if(!sl.validate(stamp)){ // da li je bilo write-locka u medjuvremenu? Stamp = sl.readLock(); // ako je bio, onda moramo pesimisticki try{ currentState1 = state1; currentState2 = state2, … etc.; } finally{ sl.unlockRead(stamp); }} return calculateSomething(state1, state2); } public class OptimisticLocking{ private final StampedLock sl = new StampedLock(); public double distanceFromOrigin(){ long stamp = sl.tryOptimisticRead(); double currentX = x, currentY = y; if(!sl.validate(stamp)){ stamp = sl.readLock(); try{ currentX = x; currentY = y; } finally { sl.unlockRead(stamp); }} return Math.sqrt(currentX * currentX + currentY * currentY); }} 21. Primer particionisanja lock-a (StripedLock) kod struktura podataka sa velikim brojem elemenata Ako imamo neku kolekciju sa većim brojem objekata, poželjno je da podelimo lock u odredjeni broj lock-ova, kako bismo zaključavali samo delove te kolekcije.Ova tehnika se zove lock stripping.Na taj način možemo imati isti broj konkurentnih niti pisaca, kao što smo kreirali lock-ova. Svaki takav lock se odnosi na deo kolekcije i time izbegavamo da zaključamo celu kolekciju, jer tipično se pristupa samo jednom elementu ili manjem broju elemenata. Primer implementacije: ConcurrentHashMap sa nizom od 16 lokova. public class StripedLock{ private static final int N_LOCKS = 16; private final Node[] buckets; private final Object[] locks; private static class Node { … } public StripedMap(int numBuckets){ buckets = new Node[numBuckets]; locks = new Object[N_LOCKS]; for (int i = 0; i < N_LOCKS; I++) locks[i] = new Object(); } Primer sa velikim brojem elemenata public class StripedLock{ public void clear(){ for(int i = 0; i < buckets.length; i++){ synchronized (locks[i % N_LOCKS]){ buckets[i] = null; }}}} private final int hash(Object key) { int hash = hash(key); synchronized (locks[hash % N_LOCKS]){ for(Node m = buckets[hash]; m != null; m = m.next) if(m.key.equals(ke)) return m.value; return null;  22. Primeri i zadaci sa implementacijom barijere preko CountDownLatch u Javi. public static void main(String[] args){ BlockingQueue transactionsQueue = new LinkedBlockingQueue(BOUND); CountDownLatch synchronizer = new CountDownLatch(NUM_PAYMENT_CLIENTS); ConcurrentHashMap bankAccounts = initAccounts(MAX_ACCOUNT_ID); for(int i = 0; i < NUM_PAYMENT_CLIENTS; i++){ Thread t = new Thread(new PaymentClient(transactionsQueue, synchronizer, MAC_ACCOUNT_ID, MAX_AMOUNT, MAX_PAYMENTS)); …} Thread[] tWorkers = new Thread[N_WORKERS]; for (int i = 0; ireceive(m) 12. Opisati algoritam rada Lamportovog logičkog časovnika na nekom procesu i koja su osnovna svojstva tog vremena. Algoritam izvrsavanja: a) inicijalizacija logickog casovnika procesa Pi, Li = 0 b) inkrementiranje Li, pre izvrsavanja nekog dogadjaja Pi c) dodavanje t=Li prilikom svakog slanja poruke m kod Pi d) kod prijema poruke m sa vremenom t, setuje Li = max (t, Li), zatim inkrementira Li pre dodeljivanja vremenskog ziga dogadjaju receive(m) Svojstva: monotonost, konzistentnost, totalno uredjenje, brojanje dogadjaja. 13. Opisati algoritam rada vektorskog časovnika na nekom procesu i koja su osnovna svojstva tog vremena. a) Inicijalizacija Vi[j]=0 za i,j =1,2,3,..,N b) pre dodeljivanja vremenskog ziga nekom dogadjaju,Pi inkrementira Vi[i] c) Pi ukljucuje t = Vi prilikom slanja svake poruke d) po dobijanju poruke sa vektorskim casovnikom V, postavlja Vi[j] = max(Vi[j],V[j]) za svako j = 1,2,3…N Svojstva: parcijalno uredjenje, tacnost, monotonost… 14. Kako se vrši poređenje vektorskih vremenskih žigova? V=V’ akko V[j] = V’[j] za j=1, 2, …, N V≤V’ akko V[j] ≤ V’[j] za j=1, 2, …, N V multicast(m2). Kauzalni multicast - ako multicast(m1) -> multicast(m2) onda m1 mora da bude isporucen pre m2. Multicast sa totalnim redosledom - ako je m1 isporucen prvi na jedan cvor, onda mora i na ostalim cvorovima da bude prvi isporucen. Multicast sa FIFO- totalnim rasporedom - kombinacija FIFA i totalnog rasporeda. 6. Dati dijagram i opis FIFO broadcast-a. Poruke poslate sa istog čvora moraju biti isporučene po redu kako su poslate. Poruke poslate sa različitih čvorova mogu biti isporučene u bilo kom redosledu 7. Dati dijagram i opis kauzalnog broadcast-a. Kauzalno uređene poruke moraju biti isporučene u kauzalnom redosledu. Konkurentne poruke mogu biti isporučene u bilo kom redosledu. 8. Dati dijagram i opis broadcast-a sa totalnim redosledom/FIFO-totalnim rasporedom Primenjuje se konzistencija na čvorovima. Mora biti isti redosled isporuke poruka na svim čvorovima. Ovo uključuje i isporuku sopstvenih poruka čvorova Ovde je ispunjen i multikast sa FIFO-totalnim redosledom pošto je m1 isporučen pre m3  9. Dati opis jednostavnog broadcast algoritma. Koji problem može nastati i kako se on rešava sa željno pouzdanim broadcast algoritmom? Cvor koji multikastuje salje poruku direktno svakom cvoru. Problem: ako se poruka izgubi, a cvor padne pre nego sto je posalje ponovo, neki cvor moze da nikada ne primi poruku. Resenje: prvi put kada cvor primi poruku, on je multikastuje ka svakom drugom cvoru. 10. Koje su osobine i način funkcionisanja epidemijskog (gossip) broadcast algoritma? Osobine: optimizovan za toleranciju na otkaze, efikasan u smislu vremena, koristi mali propusni opseg, visoka verovatnoca da ce poruka biti isporucena na svim cvorovima. Funkcionisanje: a) cvor koji multikastuje salje poruke slucajno odabranim cvorovima iz fiksnog skupa,b) algoritam ne garantuje strogu isporuku svih cvorovima, ali pazljivim izborom parametra, velika je verovatnoca da ce se poruka isporuciti svim cvorovima. 11. Kako se može realizovati broadcast sa totalnim redosledom? Pristup sa jednim liderom: jednostavnost, sistem sa malim brojem cvorova i aplikacije gde je potrebna visoka konzistentnost. Pristup sa Lamportovim casovnikom: velike DS gde otpornost na otkaze i decentralizaciju imaju prednost i aplikacije koje zahtevaju visoku toleranciju. Distribuirano uzajamno isključivanje 1. Kada je neophodno primeniti distribuirano uzajamno isključivanje i koja postoje ograničenja? Da bi se sprecilo da resurs bude ostecen tj. Da dodje do nekonzistentnosti stanja, potrebno je procesima odobriti uzejamno iskljuciv pristup ka resursu. 2. Koje zahteve treba da ispune algoritmi distribuiranog uzajamnog isključivanja? Koji su od tih zahteva obavezni, a koji poželjni? Potrebno je obezbediti da samo jedna nit/proces izvrsava odredjeni deo koda koji se naziva kriticna sekcija. Bezbednost (neophodna), napredak (neophodan) i fer izvrsavanje-redosled (pozeljno). 3. Koji su parametri za evaluaciju performansi algoritama distribuiranog uzajamnog isključivanja? Kompleksnost poruka, kasnjenje sinhronizacije, vreme odziva i sistem propusnog opsega. 4. Opisati algoritam za distribuirano uzajamno isključivanje sa centralnim serverom, koje zahteve ispunjava i koje su njegove performanse. Server: primanje zahteva za ulazak u KS od procesa Pi i primanje tokena od procesa Pi. Zahtevi: bezbednost i napredak. Performanse: ogranicenja, kompleksnost poruka, kasnjenje sinhronizacije i vreme odziva. 5. Opisati algoritam za distribuirano uzajamno isključivanje na bazi prstena, koje zahteve ispunjava i koje su njegove performanse. Procesi su uredjeni u logicki prsten: svaki proces Pi ima komunikacioni kanal ka sledecem procesu P(i + 1) mod N. Zahtevi: bezbednost i napredak. Performanse: kompleksnost poruka, vreme odziva i kasnjenje sinhronizacije. 6. Opisati Ricart-Agrawala algoritam za distribuirano uzajamno isključivanje, koje zahteve ispunjava i koje su njegove performanse. Opis: stanje algoritma (released, wanted, held), ulazak u KS, izlazak iz KS, obrada podataka. Zahtevi: bezbednost, napredak i redosled. Performanse: kompleksnost poruke, vreme odziva, kasnjenje sinhronizacije i propusni opseg.  7. Opisati Maekawa algoritam za distribuirano uzajamno isključivanje, koje zahteve ispunjava i koje su njegove performanse. Zahteva se dozvola (replay) poruka samo od nekih procesa u grupi (skup glasaca). Zahtev: bezbednost. Performanse: propusni opseg, vreme odziva i sinhronizacija kasnjenja. Replikacija 1. Šta je replikacija i koji su sve razlozi za njeno korišćenje? Koje zahteve treba da ispuni replikacija? Replikacija - odrzavanje kopije istog podatka na vise cvorova. Razlozi: poboljasnje performansi, uvecana dostupnost, smanjena osetljivost na otkaze. Zahtevi: transparentnost i konzistencija. 2. Koji postoje načini za otklanjanje duplih zahteva za promenu podataka? Zahtevi se pamte u stabilnom skladistu podataka, pa se dupli zahtevi mogu detektovati cak i nakon oporavka. Drugi nacin: radi otklanjanja duplikata je da zahtevi budu idempotentni. 3. Šta su idempotentni zahtevi za promenu podataka? Koja su ograničenja idempotentnosti? Oni se mogu ponoviti bez pojave duplikata, ogranicenje na vise update-a u toku i dodavanje/ uklanjanje replika 4. Objasniti princip rada anti-entropije kod distribuiranih sistema sa replikacijom (obratiti pažnju na vremenske žigove i markere). U mnogim sistemima sa replikacijom, replike izvrsavaju protokol za detekciju i poravnanje razlika, tako da na kraju imaju konzistentne kopije podataka. Na osnovu markera moze se napraviti razlika izmedju obrisanih i podataka koji nisu kreirani. Na osnovu vremenskih zigova, mozemo reci koja verzija podataka je novija. 5. Dati formulu verovatnoće kvara kod čvorova i dostupnost čvorova u sistemu sa replikacijom. Verovatnoca da sve otkazu je p^n. Verovatnoca da jedan ili vise otkaze 1 -(1-p)^n. Dostpunost: 1 -p, a dostupnost za jednog ili vise 1 - p^n. 6. Koje uslove treba ispuniti radi postojanja konzistencije replika kod upisa i čitanja podataka? Da bi se obezbedila konzisentna replika, neophodno je da se operacije cuvaju u linearnom i hronoloskom redosledu, sto osigurava da svaka operacija citanja vidi najnoviju upisanu vrednost. 7. Koji modeli replikacije postoje? Pasivna - koristi se primarna replika. Aktivna - sve replike se tretiraju identicno. 8. Dati opis pasivne replikacije. Poseduje: primarnu replikaciju (lidera), sekundarne replikacije, komunikaciju i otkaz lidera. Primena:transakcije se izvrsavaju na lideru u totalnom rasporedu i promene se brodcastuju pratiocima koji ih primenjuju po redosledu. 9. Dati opis aktivne replikacije. Osigurava da sve aplikacije obradjuju zahteve identicno i u istom redosledu, sto obezbedjuje konzistentnost podataka i otpornost na otkaze pojedinacnih replika. 10. Opisati problem konzistencije čitanje-posle-upisa i kako se on rešava kod distribuiranog sistema sa više replika. Klijent izvrsi operaciju upisa na replici. Odmah nakon toga isti klijent pokusava da procita podatke sa druge replike koja mozda nije jos azurirana sa novim podacima. Ove stvari narusavaju konzistentnost. Resenje: read-one/ write-all, sinhronizovana replikacija, operacije citanja i mehanizam potvrde. 11. Opisati uslove za kvorum konsenzus protokol. Osigurava konzistentnost i integritet podataka u DS kroz definisanje minimalnog broja replika potrebnih za operaciju citanja i upisa. Uslov: Qr + Qw>S i 2*Qw>S. 12. Opisati tehniku oporavak čitanja(read recovery) za sinhronizaciju replika. Obezbediti da sve replikacije budu sinhronizovane sa najnovijim podacima, cime se poboljsava konzistentnost i pouzdanost DS. Klijent obavlja ovu tehniku nakon svakog zahteva za citanje ako primeti nesuglasenost odgovora ili nedostatak odgovora od nekih replika. 13. Opisati postupak replikacije mašine stanja. Obezbedjuje da sve replike u sistemu ostanu sinhronizove i konzistentne tako sto se operacije izvrsavaju u istom redosledu i na isti nacin na svim replikama. Visoka pouzdanost i otpornost na greske u DS. Konsenzus 1. Zašto su neophodni konsenzus algoritmi u sistemu sa replikovanim serverima? Pouzdanost i dostupnost, doslednost podataka, rukovanje otkazima, detekcija i oporavak od gresaka. 2. Opisati Paxos konsenzus algoritam – uloge i koraci. Uloga: predlagac - predlaze vrednosti ka prihvatacima, prihvatac - prihvata/ odbija predlozene vrednosti i ucenici - uce vrednosti. Koraci: 1 izbor replike koja ce biti lider, 2 lider uzima vrednost i brodkastuje je ka svim replikama u accept poruci, 3 ako vecina replika potvrdi lideru, postignut je konzensus. 3. Opisati faze Prepare, Accept i Commit Paxos protokola. Prepare: predlagac salje prihvatacima vrednost. Accept: prihvataju prihvatace. Commit: vrednost postoje odlucena kad vecina prihvati. 4. Koje su uloge čvorova u Raft protokolu i kako se vrši tranzicija? Uloge: lider - upravlja operacijama, kandidat - hoce da postane lider i pratilac - odgovor na njihove zahteve. Tranzicija: pratioca -> kandidat po isteku tajmaouta bez cuvanja kontakta sa liderom, kandidat->lider ako dobije vecinu glasova, kandidat -> pratioc ako dobije RPC poziv od novog lidera sa vecim term-om 5. Koja je uloga terma kod Raft protokola? ID terma, azuriranje informacija i jedinstven lider. 6. Šta sadrži jedan ulaz u logu kod Raft protokola? Index - poziciju, term i komandu - operaciju koju izvrsava. 7. Koje su normalne operacije kod Raft protokola? Lider dodaje unose na log pratioca, request vote RPC kandidat trazi glasove. 8. Koje osobine poseduju log-ovi na različitim čvorovima u Raft prokotolu? Identicnost i konzistentnost. 9. Navesti bezbedonosne zahteve za konsenzus logova u Raft prokokolu. Jedinstven lider po term-u. Unosi commit-ovani od strane lidera ce ostati commit-ovan. Logovi moraju biti identicni na svim cvorovima za commit-ovane unose. 10. Kako se vrši izbor najboljeg lidera u Raft protokolu? Kompletnost loga i vecina glasova.  11. Koje pravilo postoji kod Raft protokola da bi neki ulaz u logu bio komitovan? Mora biti sacuvan na vecini cvorova. Mora biti novi unos iz trenutnog term-a lidera koji je sacuvan na vecini cvorova. Konzistencija replika 1. Koja je osobina linearizabilnosti kod sistema sa replikovanim čvorovima i koje su prednosti i nedostaci? Operacija ima trenutak u vrednosti kada se cini da je izvrsena automatski. Prednosti: jednostavnost za programiranje i debagovanje. Mane: visoka cena performansi, ogranicena skalabilnost i dostupnost. 2. Opisati ABD algoritam za linearizabilnost kvoruma čitanja i upisa korišćenjem oporavka čitanjem. Citanje: klijent salje zahtev za citanje kvoruma replika. Ako dobije neusaglasen odgovor ili neke replike - ne odgovaraju koristi najnoviju vrednost. Upis: klijent salje zahtev za upis oporavak citanjem; ako klijent dobije neusaglasene/ nedovoljnoe onda ponovlja upis sa najnovijim vrednostima svim replikama. 3. Šta tvrdi SAR teorema? Dati primer aplikacije koja to ilustruje. SAR teorema tvrdi: Da je nemoguće da distribuirani sistem istovremeno obezbedi sve tri od sledećih osobina: konzistentnost, dostupnost i tolerancija na mrezne particije. 4. Šta karakteriše sistem sa konačnom konzistentnošću (eventual consistency) i sa jakom konačnom konzistentnošću? Konačna Konzistentnost (Eventual Consistency): Osobine: Sistem osigurava da će sve replike na kraju konvergirati ka istom stanju ako ne postoje novi upisi.Primer: Sistemi za replikaciju podataka koji omogućavaju brzu dostupnost, ali mogu vratiti zastarele podatke.Jaka Konačna Konzistentnost:Osobine: Garantuje da će svaka ispravna replika obraditi svaki update i da će bilo koje dve replike koje su obradile isti set update-a biti u istom stanju.Primer: Sistemi koji koriste mehanizme kao što je kauzalni brodkast da bi osigurali da se svaki update na kraju primeni na sve replike. Transakcije 1. Opisati dvofazni protokol komitovanja (two-phase commit protocol) uz dijagrame. Faza 1: Priprema (Prepare Phase) Koordinator: šalje PREPARE poruku svim čvorovima (učesnicima). Učesnici: svi čvorovi zapisuju transakciju i šalju odgovor VOTE_COMMIT ili VOTE_ABORT koordinatoru. Faza 2: Komitovanje (Commit Phase) Koordinator: ako su svi učesnici glasali VOTE_COMMIT, šalje COMMIT poruku svima; ako je neki učesnik glasao VOTE_ABORT, šalje ABORT poruku. Učesnici: izvršavaju komit ili prekid (abort) u zavisnosti od primljene poruke i potvrđuju koordinatoru. 2. Koje su ACID osobine transakcija? Atomicnost, konzistentnost, izolacija i trajnost. 3. Šta je serijalizabilno izvršavanje transakcija? Serijalizabilnost: Izvršavanje transakcija je serijalizabilno ako rezultat izvršavanja transakija odgovara nekom serisjkom redosledu transakcija, tj. kao da su se izvršavale jedna po jedna. 4. Koji su efekti loših rasporeda izvršavanja transakcija? Izgubljeni upisi, prljavo citanje i neusaglaseno citanje.  5. Koji su načini izolacije transakcija? Dvofazno zakljucavanje, redosled preko vremenskih zigova, optimisticka kontrola konkurentnosti. 6. Opisati izvršavanje transakcija sa dvofaznim zaključavanjem (2PL) i koji su potencijalni problemi. Faza širenja: Transakcija zaključava resurse (objekte).Faza skupljanja: Transakcija otključava resurse nakon završetka.Problem: Deadlock: Dve ili više transakcija čekaju na resurse koje su zaključale druge transakcije. 7. Opisati poboljšanje kod striktnog (strožijeg) 2PL protokola. Zaključavanje: Zaključavanje resursa kao i u 2PL.Otključavanje: Svi zaključani resursi ostaju zaključani do kraja transakcije (komitovanja ili prekida). 8. Opisati izvršavanje transakcija sa redosledom preko vremenskih žigova (Time Stamp Ordering) TSO. Dodela vremenskih žigova: Svaka transakcija dobija vremenski žig pri početku.Provera vremenskih žigova: Transakcije se izvršavaju u skladu sa redosledom vremenskih žigova. Ako transakcija pokuša da pristupi resursu sa starijim žigom, ona se prekida. 9. Opisati izvršavanje transakcija sa optimističkom kontrolom konkurentnosti (Optimistic Concurrency Control) OCC. Faza izvršavanja: Transakcije izvršavaju na kopijama podataka. Faza validacije: Proverava se da li su promene u skladu sa ostalim transakcijama. Faza komitovanja: Ako validacija prođe, promene se primenjuju; inače se transakcija ponavlja. 10. Kako se ostvaruju ACID osobine kod distribuiranih transakcija? Atomicnost, konzistentnost, izolacija i trajnost. 11. Opisati ključne osobine Google Spanner distribuiranih transakcija: read-only transakcije, MVCC tehniku redosleda izvršavanja transakcija, TrueTime tehniku za vremenske žigove sa intervalom neizvesnosti fizičkog časovnika. Read-Only Transakcije: Koriste MVCC i čitaju iz konzistentnog snimka (snapshot).MVCC (Multi-Version Concurrency Control): Čuvanje više verzija podataka sa vremenskim žigovima. TrueTime: Koristi vremenske žigove sa intervalom neizvesnosti za sinhronizaciju transakcija. 12. Koje su osobine dugih poslovnih transakcija i kako se kod njih primenjuje Saga patern? Duge poslovne transakcije: Traju duže i uključuju više koraka. Korišćenje Saga paterna za upravljanje kompleksnim transakcijama. Saga patern: Sekvenca lokalnih transakcija sa kompenzacionim koracima za otkaz. 13. Opisati Saga patern baziran na koreografiji. Lokalne transakcije publikuju domenske događaje. Druge transakcije slušaju i reaguju na te događaje. 14. Opisati Saga patern baziran na orkestraciji. Centralni orkestrator upravlja tokom transakcija. Orkestrator određuje redosled i upravlja kompenzacijom u slučaju otkaza. Peer-to-Peer sistemi 1. Opisati princip konzistentnog heširanja i gde se primenjuje. Princip: Objekti (fajlovi) i čvorovi se heširaju u istom prostoru i mapiraju na krug sa vrednostima od 0 do 2^m −1, gde je m broj bitova u heš vrednosti. Objekat se mapira na prvi čvor u pravcu kazaljke na satu čija heš vrednost je jednaka ili veća od heš vrednosti objekta. Primena: Konzistentno heširanje se koristi u Peer-to-Peer (P2P) sistemima i distribuiranim keš sistemima kao što su Chord, Amazon DynamoDB, i Cassandra za balansiranje opterećenja i upravljanje skladištenjem podataka. 2. Kako se smanjuje varijansa opterećenosti čvorova kod konzistentnog heširanja? Virtuelni čvorovi: Svaki fizički čvor se mapira na više virtuelnih čvorova u heš prostoru. Ovo smanjuje varijansu opterećenja jer svaki fizički čvor ima više šansi da dobije ravnomerniji deo ukupnog opterećenja 3. Šta su to peer-to-peer (P2P) sistemi i koje su njihove osobine? Decentralizovana arhitektura,svaki čvor deluje i kao klijent i kao server,skalabilnost,otpornost na otkaze,dinamičko dodavanje i uklanjanje čvorova. 4. Koje postoje generacije peer-to-peer sistema i koje su njihove osobine? I generacija (Napster): Centralizovani server za indeksiranje fajlova. II generacija (Gnutella, Kazaa, BitTorrent): Potpuno decentralizovani, koriste širokopojasni protok za pretragu i preuzimanje. III generacija (Chord, Pastry, Tapestry, Kademlia): Korišćenje strukturiranog pristupa sa distribuiranim heš tablama (DHT) za efikasno rutiranje i pretragu. 5. Koje su osobine Napster P2P sistema? Centralizovan server, pretraga i preuzimanje. 6. Opisati Gnutella P2P sistem. Potpuno decentralizovan: Nema centralnog servera. Tipovi poruka: Ping (pitanje), Pong (odgovor na pitanje), Query (upit za pretragu), QueryHit (odgovor na upit).Plavanje (Flooding): Upiti se šalju svim susednim čvorovima koristeći ograničenje TTL (time-to-live). 7. Kako se vrši mapiranje objekata-fajlova na čvorove kod Chord peer-to-peer sistema? Chord: Koristi SHA-1 heš funkciju za mapiranje i čvorova i ključeva u isti heš prostor. Ključ se mapira na prvi čvor čija heš vrednost je veća ili jednaka heš vrednosti ključa (successor). 8. Primer: Na koje čvorove će se mapirati fajlovi sa vrednošću ključa HH i YY, ako postoje čvorovi kao na slici kod Chord P2P sistema. Ako imamo čvorove sa ID vrednostima 0, 1, 3, 5 i 6: Ključ XX: Ako je heš XX 4, on će biti mapiran na čvor 5 (successor 4). Ključ YY: Ako je heš YY 2, on će biti mapiran na čvor 3 (successor 2). 9. Opisati pretragu kod Chord P2P sistema preko finger tabela. Finger tabele: Svaki čvor održava finger tabelu sa m unosa koji pomažu u brzom pronalaženju successora za zadati ključ. Pretraga počinje od trenutnog čvora i šalje zahtev najdaljem čvoru u finger tabeli koji ne prelazi traženu vrednost, ponavljajući proces sve dok se ne nađe traženi ključ. 10. Kako se vrši pretraga ključeva u uslovima otkaza čvorova kod Chord P2P sistema? Replikacija: Kopije ključeva se čuvaju na više čvorova (npr. r prethodnika i r sledbenika). Višestruki unosi u finger tabelama: Održavanje više unosa za svaki čvor, omogućavajući korišćenje sledećeg u slučaju otkaza. 11. Dati primer pridruživanja novog čvora kod Chord P2P sistema. Pridruživanje čvora: Novi čvor kontaktira postojeći čvor, inicira stabilizacioni proces da ažurira finger tabele i preuzme odgovarajuće ključeve. Primer: Novi čvor N40 kontaktira čvor N46. N46 ažurira svoj successora na N40. N40 inicijalizuje svoju finger tabelu i preuzima ključeve od N46. Svi čvorovi ažuriraju svoje finger tabele da uključe N40 Key-Value skladišta i NoSQL sistemi 1. Koje su osobine key-value skladišta? Princip rada: Skladištenje podataka u formatu parova ključ-vrednost. Struktura: Podseća na rečnik ili heš tabelu, gde se vrednost pristupa preko jedinstvenog ključa. Operacije: Osnovne operacije su get(key), put(key, value), i delete(key). Skalabilnost: Lako se skaliraju horizontalno (scale out) dodavanjem novih čvorova. Fleksibilnost: Ne zahtevaju fiksnu šemu (schema-less), mogu skladištiti bilo koji tip podataka. Primena: Korišćenje u sistemima gde su brzina i jednostavnost pristupa podacima ključni, npr. keširanje, sesije, inventari. 2. Koji su tipovi NoSQL rešenja? Ključ-vrednost skladišta: Amazon DynamoDB, Redis, Riak. Kolumnska skladišta: Google BigTable, Cassandra, HBase. Skladišta dokumenata: MongoDB, CouchDB. Grafovske baze podataka: Neo4J, Amazon Neptune. 3. Opisati Bloom filter, njegove osobine i primenu. Struktura: Sastoji se od velikog bit-vektora i nekoliko heš funkcija. Operacije: Insert: Za svaki element koji se dodaje, primenjuje se nekoliko heš funkcija koje određuju pozicije u bit-vektoru koje se postavljaju na 1.Check: Za proveru prisustva elementa, heš funkcije se primenjuju na element, i ako su sve odgovarajuće pozicije u bit-vektoru 1, element je verovatno prisutan; u suprotnom, sigurno nije prisutan. Osobine: lazni pozitivni, lazni negativni i efikasnost. Primena: kesiranje, detekcija spama, sistem za preporuke, NoSQL baze. Procesiranje velike količine podataka u klasteru 1. Šta karakteriše Big Data ? Volume, Velocity, variety i veracity. 2. Šta karakteriše MapReduce paradigmu obrade podataka? Map (Map): Funkcija koja obrađuje ulazne podatke i proizvodi skup ključ-vrednost parova. Smanji (Reduce): Funkcija koja agregira i obrađuje skup parova koje je proizvela map funkcija. Tok podataka: Ulazni podaci se čitaju iz distribuiranog skladišta, međurezultati se čuvaju na lokalnim diskovima, a finalni rezultati se smeštaju u distribuirano skladište. 3. Koji je tok podataka tokom izvršavanje MapReduce poslova kod Hadoop platforme? (Odakle se čitaju, gde se smeštaju međurezultati, gde se smeštati finalni rezultati). Čitanje podataka: Ulazni podaci se čitaju iz Hadoop Distributed File System (HDFS). Map: Obrada podataka kroz map zadatke, međurezultati se čuvaju na lokalnim diskovima. Smanji: Map zadaci šalju podatke smanji zadacima koji agregiraju i obrađuju rezultate. Finalni rezultati: Finalni rezultati se čuvaju u HDFS ili drugom stabilnom skladištu. 4. Opisati arhitekturu Apache Spark platforme za procesiranje u klasteru ili cloud-u. Driver program: Glavni program koji koordinira izvršavanje zadataka. SparkContext: Komunicira sa klaster menadžerom (YARN, Mesos, Kubernetes). Executors: Izvršavaju zadatke na čvorovima u klasteru. Cluster Manager: Upravlja resursima u klasteru. 5. Kako se vrši paralelno procesiranje podataka u Apache Spark-u? Particionisanje: RDDs se dele na particije koje se obrađuju paralelno na različitim čvorovima. Transformacije: Primena lentivnih transformacija (map, filter, join) kreira nove RDDs. Akcije: Akcije kao što su count, collect, save iniciraju izvršenje transformacija. 6. Koje su prednosti Apache Spark platforme u odnosu na Hadoop platformu? Brzina, interaktivna analiza, jednostavnost i fleksibilnost.  7. Koje su ključne apstrakcije podataka kod Apache Spark platoforme? RDD (Resilient Distributed Dataset): Kolekcija ne-promenljivih objekata. DataFrame: Kolekcija podataka sa poznatom šemom, slično tabeli u relacionoj bazi. Dataset: Apstrakcija slična RDD-u, ali sa boljom optimizacijom i integracijom sa DataFrame-om. 8. Opisati koji sve tipovi operacija postoje kod Apache Spark platforme nad DataSet/RDD kolekcijama i u čemu je razlika između tih operacija? Transformacije i akcije. 9. Šta označava tzv. lineage nekog Dataset/RDD-a? Lineage označava istoriju transformacija koje su primenjene na Dataset/RDD. Ovo omogućava rekonstrukciju RDD u slučaju otkaza čvora. 10. Навести неке Apache Spark операције. map: Primena funkcije na svaki element RDD-a. filter: Filtriranje elemenata RDD-a na osnovu uslova. reduce: Agregacija elemenata RDD-a korišćenjem binarne funkcije. 11. Kako se ostvaruje otpornost na otkaze kod Apache Spark platforme? Spark koristi lineage informacije kako bi rekonstruisao izgubljene particije RDD-a ponovnim izvršavanjem transformacija. 12. Koji sve programski modeli postoje u Apache Spark-u i koja je njihova namena? Spark SQL: Rad sa strukturiranim podacima i SQL upitima. Spark Streaming: Obrada strimova podataka u realnom vremenu. GraphX: Analiza i obrada grafova. MLlib: Biblioteka za mašinsko učenje. 13. Koja je prednost jedinstvene platforme za Big Data obradu kao što je Apache Spark u odnosu na specijalizovane platforme za određene vrste podataka? Unificiranje obrade: Kombinacija različitih tipova obrade podataka (SQL, striming, grafovi, mašinsko učenje) u jednoj platformi. Efikasnost: Izbegavanje troškova prenosa podataka između različitih specijalizovanih platformi. Jednostavnost razvoja: Razvoj aplikacija je lakši jer sve komponente koriste istu infrastrukturu i programski model.