Računarske nauke: Paralelno i konkurentno izvršavanje

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