Paralelne strukture podataka bez međusobnog isključivanja

diplomski rad

• Autor: Eduard Kalčićek
• Mentor: Mladen Jurak (mentor)
• Član povjerenstva: Mladen Jurak (predsjednik povjerenstva)
• Član povjerenstva: Saša Singer (član povjerenstva)
• Član povjerenstva: Matija Kazalicki (član povjerenstva)
• Član povjerenstva: Vedran Čačić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2018-07-18, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Tradicionalni mehanizmi višedretvenog programiranja obuhvaćaju međusobno isključivanje u svrhu zaštite podataka. U ovom je radu predstavljena metoda koja se ne oslanja na mutexe i kreiranje kritičnih odsječaka, već uz pomoć tzv. atomic operacija, standardiziranih u programskom jeziku C++ 2011. godine, postiže siguran pristup podacima od strane više različitih dretvi unutar procesa. Predstavljen je pripadni memorijski model koji služi kao osnova za konstrukciju lock-free algoritama. Opisani su redoslijedi modifikacija koji nam služe za sinkronizaciju podataka između dretvi. Detaljno su opisane paralelne implementacije lock-free strukture podataka stog te je prikazana razlika u efikasnosti izvođenja programa koji koriste različite memorijske modele. Navedene su i razlike u odnosu na ekvivalentne programe koji koriste mehanizme međusobnog isključivanja.

Sažetak (engleski)

Traditional mechanisms for multithreaded programming include mutual exclusion in order to protect data. This thesis presents a method which doesn’t rely on mutexes nor creation of critical sections, but which with the help of so called atomic
operations, standardized in programming language C++ 2011 revision, accomplishes safe data access for multiple threads inside a process. A memory model which serves as a basis for construction of lock-free algorithms was introduced. Modification orders are described which are used for data synchronization between multiple threads. Different implementations of data structure stack are described in detail, as well as difference in program efficiency which use different modification orders. The differences between lock-free algorithms and equivalent programs which use mechanisms for mutual exclusion are also presented.

• Ključne riječi: višedretveno programiranje; atomic operacije; C++; lock-free algoritam
• Ključne riječi (engleski): multithreaded programming; atomic operations; C++; lock-free algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:234918
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2018-11-29 12:36:16