| Abstract | Pri pisanju višedretvenog programa, programeri najčešće koriste lokote odnosno međusobno isključivanje za zapisivanje i dohvaćanje podataka iz zajedničke memorije. U ovom radu predstavljena je alternativna metoda koja ne koristi lokote, već se oslanja na atomske tipove i operacije nad njima kako bi ostvarila sinkronizaciju među dretvama. Atomske operacije su po definiciji nedjeljive stoga ne mogu prouzročiti nedefinirano ponašanje. Štoviše, omogućuju preuređivanje atomskih i neatomskih operacija s obzirom na zadani memorijski uredaj. Atomski tipovi su uvedeni u standardu C++11 2011. godine. Uz atomske tipove i operacije, tim standardnom predstavljen je i memorijski model jezika C++ koji opisuje ponašanje dretvi s obzirom na memoriju i predstavlja podlogu za pisanje lock-free programa. Uvođenjem standarda C++20, dobivena je podrška za mnoge nove atomske tipove koji uvelike olakšavaju korištenje atomskih operacija i pisanje struktura podataka za asinhorni pristup. Sam rad se sastoji od dva poglavlja. U prvom dajemo opis memorijskog modela i zaglavlja <atomic>. Prvo opisujemo standardne atomske tipove uvedene standardnom C++11 i operacije koje oni podržavaju. Dajemo detaljan opis djelovanja svake operacije i primjere kada se koristi. Zatim dajemo opis najbitnijh tipova uvedenih standardom C++20, njihovog korištenja i prednosti koje dovode u odnosu na postojeće tipove. Nakon opisa tipova i operacija, dajemo pregled memorijskih uređaja. Opisujemo kako svaki memorijski uređaj djeluje na poredak pisanja i čitanja iz memorije u odnosu na atomsku operaciju u kojoj je zadan te dajemo primjere situacija u kojima se koriste. U drugom poglavlju dajemo pregled implementacije dvije lock-free strukture podataka: stoga i reda. U njihovoj implementaciji, oslanjamo se na pametne atomske pokazivače uvedene u standardu C++20 te opisujemo kako njihovim korištenjem možemo uvelike olakšati pisanje lock-free koda. Dajemo detaljan opis glavnih funkcije svake strukture te konačno uspoređujemo brzinu rada dane strukture s implementacijama koje koriste mutexe i koje se oslanjaju na atomske operacije uvedene u standardu C++11. |
| Abstract (english) | While writing multithreaded programs, programmers usually use locks, that is, mutual exclusion, to read and write data. This thesis presents an alternative method that does not use locks but relies on atomic types and operations to achieve synchronization. Atomic operations are, by definition, inseparable operations, which means they cannot cause data race or undefined behavior. Furthermore, they can establish inter-thread synchronization and order non-atomic memory accesses as specified by the given memory order. Atomic types were introduced in C++11 standard in 2011. Along with atomic types and operations, this standard introduced a memory model to the C++ language which describes the behavior of threads with respect to basic memory operations and serves as a basis for writing lock-free programs. With the recent C++20 standard, support was added for many new atomic features and types which greatly facilitates the usage of atomics while writing lock-free data structures. This paper is comprised of two chapters. In the first chapter, we give a description of the C++ memory model and <atomic> header. First, we describe standard atomic types introduced in 2011. and operations it supports. We give a detailed explanation of the effect of each operation and examples of how to use it. Next, we describe the main novelties introduced to the atomic library in standard C++20, their usage, and the advantages it has over the existing types. After this, we give an overview of the memory orders. We describe how each memory order affects memory accesses, including reads and writes to the memory, and their order around an atomic operation while giving examples of the situations in which they are used. In the second chapter, we give an overview of the implementation of two lock-free data structures: stack and queue. In their implementation, we rely heavily on smart atomic pointers introduced in the C++20 standard. We describe how by using them we can greatly facilitate the writing of lock-free code. We give a detailed description of the main functions and finally, we compare the operating speed of that data structure with one implementation which uses mutexes and one which relies on atomics from the C++11 standard. |
