Računarske nauke: Paralelno i konkurentno izvršavanje

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Koja je razlika između konkurentnog i paralelnog izvršavanja programa?

Paralelno izvršavanje predstavlja istovremeno izvršavanje više računarskih operacija, programa ili delova programa, dok konkurentno izvršavanje predstavlja izvršavanje više programskih tokova jednog programa tako da oni napreduju u vremenu, ali se ne moraju obavezno izvršavati istovremeno.

Koje su prednosti konkurentnog izvršavanja programa?

Omogućava da se preklopi računanje i I/O pristup na jednom računaru. Može da pojednostavi strukturu koda i/ili da poboljša odziv. Omogućava lakšu upotrebu više CPU-ova.

Šta je atomska operacija?

Atomska operacija je nedeljiva; ona se ili u potpunosti ili se uopšte ne izvršava.

Šta je kritična sekcija?

Kritična sekcija je deo koda koji ne sme da se izvrši konkurentno od strane više od jedne niti. Signup and view all the answers

Kako se manifestuje problem utrkivanja odnosno race condition-a kod pristupa deljenom resursu?

Race condition se manifestuje kada dve ili više niti pristupaju istovremeno jednom deljenom resursu, što može dovesti do neočekivanih rezultata. Signup and view all the answers

Šta je cilj ideje o konkurentnom pristupu deljenim promenljivama?

Dozvoliti više čitaoca da konkurentno pristupaju deljenim promenljivama bez medjusobnog isključivanja Signup and view all the answers

Kako se zove klasa za implementaciju deljenih promenljivih preko Read-Write lock-a?

ReadWriteMap Signup and view all the answers

Šta je StampedLock i koje su njegove osobine?

StampedLock je dodatak koji poboljšava performanse čitanja i pisanja pomoću vremenskih žigova. Omogućava optimističko čitanje, nadogradnju sa read na write lock i validaciju vremenskih žigova. Signup and view all the answers

Šta je lock stripping i zbog čega se koristi u strukturama podataka?

Lock Stripping je tehnika podeljenog zaključavanja koja se koristi da se omogući delimično zaključavanje kolekcija podataka, čime se izbegava zaključavanje celih kolekcija kada je pristup potreban samo delu kolekcije. Signup and view all the answers

Koja je svrha CountDownLatch barijere u Javi?

CountDownLatch barijera se koristi za sinhronizaciju u višenitnom okruženju, čekanje na završetak određenog broja aktivnosti pre nego što se nastavi izvršavanje. Signup and view all the answers

Koji modeli replikacije postoje?

Pasivna - koristi se primarna replika. Aktivna - sve replike se tretiraju identicno. Signup and view all the answers

Šta je Pasivna replikacija?

Poseduje: primarnu replikaciju (lidera), sekundarne replikacije, komunikaciju i otkaz lidera. Primenjuje se transakcije na lideru u totalnom rasporedu i promene se brodcastuju pratiocima po redosledu. Signup and view all the answers

Šta je Aktivna replikacija?

Osigurava da sve aplikacije obradjuju zahteve identicno i u istom redosledu, sto obezbedjuje konzistentnost podataka i otpornost na otkaze pojedinacnih replika. Signup and view all the answers

Kako se rešava problem konzistencije čitanje-posle-upisa kod distribuiranog sistema sa više replika?

Read-one/write-all, sinhronizovana replikacija, operacije čitanja i mehanizam potvrde. Signup and view all the answers

Zašto su neophodni konsenzus algoritmi u sistemu sa replikovanim serverima?

Pouzdanost i dostupnost, doslednost podataka, rukovanje otkazima, detekcija i oporavak od gresaka. Signup and view all the answers

Šta tvrdi SAR teorema?

Da je nemoguće da distribuirani sistem istovremeno obezbedi sve tri od sledećih osobina: konzistentnost, dostupnost i toleranciju na mrezne particije. Signup and view all the answers

Šta karakteriše sistem sa konačnom konzistentnošću (eventual consistency) i sa jakom konačnom konzistentnošću?

Konačna konzistentnost: Sve replike na kraju konvergiraju ka istom stanju ako ne postoje novi upisi. Jaka konačna konzistentnost: Garantuje da će svaka ispravna replika obraditi svaki update i biće u istom stanju kao ostale replike koje su obradile isti set update-a. Signup and view all the answers

Koje su ACID osobine transakcija?

Atomicnost, konzistentnost, izolacija i trajnost. Signup and view all the answers

Kako se vrši pretraga ključeva u uslovima otkaza čvorova kod Chord P2P sistema?

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č. Signup and view all the answers

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. Osnovne operacije su get(key), put(key, value), i delete(key). Lako se skaliraju horizontalno dodavanjem novih čvorova. Ne zahtevaju fiksnu šemu (schema-less), mogu skladištiti bilo koji tip podataka. Signup and view all the answers

Koji su tipovi NoSQL rešenja?

Ključ-vrednost skladišta, Kolumnska skladišta, Skladišta dokumenata, Grafovske baze podataka. Signup and view all the answers

Opisati Bloom filter, njegove osobine i primenu.

Bloom filter se sastoji od velikog bit-vektora i nekoliko heš funkcija. Za svaki element koji se dodaje, primenjuje se heš funkcija koja određuje poziciju u bit-vektoru koja se postavlja na 1. 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. Primena u kesiranju, detekciji spama, sistemima za preporuke i NoSQL bazama. Signup and view all the answers

Šta karakteriše Big Data?

Velocity Signup and view all the answers

MapReduce paradigma obrade podataka se sastoji samo od Map funkcije.

False Signup and view all the answers

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. Signup and view all the answers

Study Notes

Razlike između konkurentnog i paralelnog izvršavanja programa

Konkurentno izvršavanje: istovremeno izvršavanje više programa ili delova programa, ali ne moraju nuances istovremeno
Paralelno izvršavanje: istovremeno izvršavanje višeračunarskih operacija ili programa

Definicija distribuiranog sistema

DS se sastoji od hardverskih ili softverskih komponenti smeštenih na umreženim računarima
Komunikacija i koordinacija svojih akcija se vrši prenošenjem poruka

Razlozi za razvoj DS

Povećanje dostupnosti i pouzdanosti
Bolje performanse
Lakše skaliranje resursa sistema
Rešavanje zahtevnih problema

Problemi kod projektovanja DS

Komunikacija može da otkaze
Procesi mogu neočekivano da se zaustave
Diskovi i drugi hardverski uređaji mogu da otkaze
Fault tolerance - otpornost na otkaze i svaki kvar se dešava nepredvidivo

Osobine DS

Vise računara - čvorova
Mrežna komunikacija
Cilj (konzistencija, transparentnost)

Transparetnost kod DS

Pristup
Lokacija
Migracija
Replikacija
Konkurentnost
Otkazi

Razlike između procesa i niti

Procesi su instance programa koji se izvršavaju
Niti su entiteti koji se upravlja schedulerom

Resurse niti

Svaka nit ima svoj stek, programski brojac i registar
Resurse koje niti dele su: heap, segment podataka, kod segmenta, signali i obrada signala

Prednosti konkurentnog izvršavanja programa

Omogućava da se preklopi računanje i I/O pristup na jednom računaru
Može da pojednostavi strukturu koda i/ili da poboljša odziv
Omogućava laku upotrebu više CPU-ova

Problemi utrkivanja (race conditions)

Dve ili više niti pristupaju istovremeno jednom deljenom resursu, što može dovesti do neočekivanih rezultata

Kritična sekcija i uzejamno isključivanje

Kritična sekcija: deo koda koji ne sme da se izvršava konkurentno od strane više od jedne niti
Uzejamno isključivanje: ako se jedna nit izvršava u kritičnoj sekciji, svim ostalim nitima je zabranjeno da uđu u kritičnu sekciju

Atomska operacija

Atomska operacija: nedeljiva; ona se ili u potpunosti izvršava ili se uopšte ne izvršava

Implementacija kritične sekcije putem mutex-a

Dati primeri implementacije kritične sekcije putem mutex-a

Osobine deadlock-a, livelock-a i starvation-a

DeadLock: stanje kada se procesi/niti uzejamno blokira
LiveLock: procesi/niti se ne blokira, nema napretka u izvršavanju
Starvation: proces koji želi da uđe u kritičnu sekciju će čekati, ali neće biti efekta

Filter algoritam

Koristi se za implementaciju kritične sekcije
Omogućava međusobno isključivanje i pravičnost u pristupu kritičnoj sekciji za više niti

Ticket algoritam

Omogućava da niti ulaze u kritičnu sekciju redosledom koji je definisan redosledom dodeljenih brojeva
Osigurava međusobno isključivanje i pravičnost

Pekarski algoritam

Omogućava da se niti u kritičnu sekciju uđu u redosledu koji je definisan redosledom dodeljenih brojeva

Implementacija proizvođača-potrošača u Javi

Koriste se sincronizovane metode wait(), notify() i notifyAll()
Koriste se intrinic lock-ovi i eksterni lock-ovi (java.util.concurrent.locks)
Implementacija Condition interfejsa

StampedLock

Omogućava više konkurentnih niti pisaca
Nudi mogućnost nadogradnje sa read na write lock
Optimičko čitanje: pozivom tryOptimisticRead() pokušava se dobiti dozvola za čitanje ako nema aktivnog write lock-a

Primeri i zadaci sa StampedLock-om

Primeri implementacije optimistic reading u klasi OptimisticLocking
Primeri implementacije distanceFromOrigin u klasi OptimisticLockingHere are the study notes in Serbian:
Distributed Systems*

Lamport's Clock

Used for synchronization in distributed systems
Provides a way to order events in a distributed system
Uses a timestamp to determine the order of events

Mutual Exclusion

Needed to prevent data inconsistency and ensure correct execution of critical sections
Algorithms for achieving mutual exclusion:
- Centralized approach (e.g., token ring)
- Decentralized approach (e.g., Lamport's algorithm, Ricart-Agrawala algorithm, Maekawa's algorithm)

Replication

Types of replication:
- Passive replication (primary-backup)
- Active replication (all nodes are equal)
Advantages of replication:
- Increased availability and fault tolerance
- Improved performance
Consistency models:
- Strong consistency
- Weak consistency
- Eventual consistency

Consensus Protocols

Paxos protocol:
- Used for achieving consensus in a distributed system
- Consists of prepare, accept, and commit phases
Raft protocol:
- Used for achieving consensus in a distributed system
- Consists of election, log replication, and heartbeats

Transactions

ACID properties:
- Atomicity
- Consistency
- Isolation
- Durability
Types of transactions:
- Local transactions
- Distributed transactions
Concurrency control techniques:
- Locking
- Optimistic concurrency control
- Pessimistic concurrency control

Peer-to-Peer Systems

Characteristics:
- Decentralized architecture
- No central authority
- Nodes act as both clients and servers
Types of P2P systems:
- Unstructured P2P systems (e.g., Gnutella)
- Structured P2P systems (e.g., Chord, Pastry, Tapestry)

Consistent Hashing

Used for load balancing and distributed storage
Maps objects to nodes in a distributed system
Provides a way to efficiently locate and retrieve data

NoSQL Databases

Characteristics:
- Schema-less
- Scalable
- Flexible data model
Types of NoSQL databases:
- Key-value stores
- Column-family stores
- Document-oriented databases
- Graph databases

Big Data

Characteristics:
- Volume
- Velocity
- Variety
- Veracity
MapReduce paradigm:
- Used for processing large datasets
- Consists of map and reduce phases
Apache Spark:
- Used for processing large datasets
- Provides a way to process data in parallel across a cluster of nodes### Prednosti Apache Spark platforme
Brzina, interaktivna analiza, jednostavnost i fleksibilnost su prednosti Apache Spark platforme u odnosu na Hadoop platformu

Ključne apstrakcije podataka kod Apache Spark platforme

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

Tipovi operacija kod Apache Spark platforme

Transformacije i akcije su dve glavne vrste operacija kod Apache Spark platforme nad DataSet/RDD kolekcijama
Razlika između tih operacija nastaje zbog različitih svrha i efekata na RDD/Dataset kolekcije

Lineage Dataset/RDD-a

Lineage označava istoriju transformacija koje su primenjene na Dataset/RDD
Omogućava rekonstrukciju RDD u slučaju otkaza čvora

Apache Spark operacije

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

Otpornost na otkaze kod Apache Spark platforme

Spark koristi lineage informacije kako bi rekonstruisao izgubljene particije RDD-a ponovnim izvršavanjem transformacija

Programski modeli u Apache Spark-u

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

Prednost jedinstvene platforme za Big Data obradu

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

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Pitanja iz računarskih nauka o paralelnom i konkurentnom izvršavanju programa, kao i definicija distribuiranog sistema.