Paralelne strukture podataka bez međusobnog isključivanja

master's thesis

• Author: Eduard Kalčićek
• Mentor: Mladen Jurak (mentor)
• Committee member: Mladen Jurak (predsjednik povjerenstva)
• Committee member: Saša Singer (član povjerenstva)
• Committee member: Matija Kazalicki (član povjerenstva)
• Committee member: Vedran Čačić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2018-07-18, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: višedretveno programiranje; atomic operacije; C++; lock-free algoritam
• Keywords (english): multithreaded programming; atomic operations; C++; lock-free algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:234918
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2018-11-29 12:36:16