On-line services already form an important part of modern life with an immense potential for growth. Most of these services are supported by transactional systems, which are backed by database management systems (DBMS) in many cases. Many on-line services use replication to ensure high-availability, fault tolerance and scalability. Replicated systems typically consist of different nodes running the service co-ordinated by a distributed algorithm which aims to drive all the nodes along the same sequence of states by providing a total order to their operations. Thus optimization of both local DBMS operations through concurrency control and the distributed algorithm driving replicated services can lead to enhancing the performance of the on-line services. Deferred Update Replication (DUR) is a well-known approach to design scalable replicated systems. In this method, the database is fully replicated on each distributed node. User threads perform transactions locally and optimistically before a total order is reached. DUR based systems find their best usage when remote transactions rarely conflict. Even in such scenarios, transactions may abort due to local contention on nodes. A generally adopted method to alleviate the local contention is to invoke a local certification phase to check if a transaction conflicts with other local transactions already completed. If so, the given transaction is aborted locally without burdening the ordering layer. However, this approach still results in many local aborts which significantly degrades the performance. The first main contribution of this thesis is PXDUR, a DUR based transactional system, which enhances the performance of DUR based systems by alleviating local contention and increasing the transaction commit rate. PXDUR alleviates local contention by allowing speculative forwarding of shared objects from locally committed transactions awaiting total order to running transactions. PXDUR allows transactions running in parallel to use speculative forwarding, thereby enabling the system to utilize the highly parallel multi-core platforms. PXDUR also enhances the performance by optimizing the transaction commit process. It allows the committing transactions to skip read-set validation when it is safe to do so. PXDUR achieves performance gains of an order of magnitude over closest competitors under favorable conditions. Transactions also form an important part of centralized DBMS, which tend to support multi-threaded access to utilize the highly parallel hardware platforms. The applications can be wrapped in transactions which can then access the DBMS as per the rules of concurrency control. This allows users to develop applications that can run on DBMSs without worrying about synchronization. texttt{Serializability} is the de-facto standard form of isolation required by transactions for many applications. The existing methods employed by DBMSs to enforce serializability employ explicit fine-grained locking. The eager-locking based approach is pessimistic and can be too conservative for many applications. The locking approach can severely limit the performance of DBMSs especially for scenarios with moderate to high contention. This leads to the second major contribution of this thesis is TSAsR, an adaptive transaction processing framework, which can be applied to DBMSs to improve performance. TSAsR allows the DBMS's internal synchronization to be more relaxed and enforces serializability through the processng of external meta-data in an optimistic manner. It does not require any changes in the application code and achieves orders of magnitude performance improvements for high and moderate contention cases. The replicated transaction processing systems require a distributed algorithm to keep the system consistent by ensuring that each node executes the same sequence of deterministic commands. These algorithms generally employ texttt{State Machine Replication (SMR)}. Enhancing the performance of such algorithms is a potential way to increase the performance of distributed systems. However, developing new SMR algorithms is limited in production settings because of the huge verification cost involved in proving their correctness. There are frameworks that allow easy specification of SMR algorithms and subsequent verification. However, algorithms implemented in such framework, give poor performance. This leads to the third major contribution of this thesis Verified JPaxos, a JPaxos based runtime system which can be integrated to an easy to verify I/O automaton based on Multipaxos protocol. Multipaxos is specified in Higher Order Logic (HOL) for ease of verification which is used to generates executable code representing the Multipaxos state changes (I/O Automaton). The runtime drives the HOL generated code and interacts with the service and network to create a fully functional replicated Multipaxos system. The runtime inherits its design from JPaxos along with some optimizations. It achieves significant improvement over a state-of-art SMR verification framework while still being comparable to the performance of non-verified systems. / Master of Science

Programmers often have to spend a significant amount of time inspecting the software code and execution traces to identify the root cause of a software bug. For a multithreaded program, debugging is even more challenging due to the subtle interactions between concurrent threads and the often astronomical number of possible interleavings. In this work, we propose a logical constraint-based symbolic analysis method to aid in the diagnosis of concurrency bugs and find their root causes, which can be later used to recommend repairs. In our method, the diagnosis process is formulated as a set of constraint solving problems. By leveraging the power of constraint satisfiability (SAT) solvers and a bounded model checker, we perform a semantic analysis of the sequential computation as well as the thread interactions. The analysis is ideally suited for handling software with small to medium code size but complex concurrency control, such as device drivers, synchronization protocols, and concurrent data structures. We have implemented our method in a software tool and demonstrated its effectiveness in diagnosing subtle concurrency bugs in multithreaded C programs. / Master of Science

As chip vendors are increasingly manufacturing a new generation of multi-processor chips called multicores, improving software performance requires exposing greater concurrency in software. Since code that must be run sequentially is often due to the need for synchronization, the synchronization abstraction has a significant effect on program performance. Lock-based synchronization — the most widely used synchronization method — suffers from programability, scalability, and composability challenges. Transactional memory (TM) is an emerging synchronization abstraction that promises to alleviate the difficulties with lock-based synchronization. With TM, code that read/write shared memory objects is organized as transactions, which speculatively execute. When two transactions conflict (e.g., read/write, write/write), one of them is aborted, while the other commits, yielding (the illusion of) atomicity. Aborted transactions are re-started, after rolling-back changes made to objects. In addition to a simple programming model, TM provides performance comparable to lock-based synchronization. Software transactional memory (STM) implements TM entirely in software, without any special hardware support, and is usually implemented as a library, or supported by a compiler or by a virtual machine. In this thesis, we present ByteSTM, a virtual machine-level Java STM implementation. ByteSTM implements two STM algorithms, TL2 and RingSTM, and transparently supports implicit transactions. Program bytecode is automatically modified to support transactions: memory load/store bytecode instructions automatically switch to transactional mode when a transaction starts, and switch back to normal mode when the transaction successfully commits. Being implemented at the VM-level, it accesses memory directly and uses absolute memory addresses to uniformly handle memory. Moreover, it avoids Java garbage collection (which has a negative impact on STM performance), by manually allocating and recycling memory for transactional metadata. ByteSTM uses field-based granularity, and uses the thread header to store transactional metadata, instead of the slower Java ThreadLocal abstraction. We conducted experimental studies comparing ByteSTM with other state-of-the-art Java STMs including Deuce, ObjectFabric, Multiverse, DSTM2, and JVSTM on a set of micro- benchmarks and macro-benchmarks. Our results reveal that, ByteSTM's transactional throughput improvement over competitors ranges from 20% to 75% on micro-benchmarks and from 36% to 100% on macro-benchmarks. / Master of Science

Embedded systems are commonplace, often with real-time requirements, limited resources and increasingly complex workloads with high demands on security and reliability. The complexity of these systems calls for extensive developer experience and many tools has been created to aid in the development of the software running on such devices. One of these tools, the Real-Time For the Masses (RTFM) concurrency framework developed at Luleå University of Technology (LTU), is built upon a pre-existing, well established and theoretically underpinned execution model providing deadlock free execution and strong guarantees about correctness. The framework is further enhanced by the memory safety provided by Rust, a modern systems programming language. This thesis documents the work done towards improving the framework by studying the possibility to make it extendable. For this, a model of the present layout is required, which in turn requires a solid understanding of Rust's way to structure code. To realise such a large structural change it was advisable to join the open-source RTFM community as a core developer. This role included new responsibilities and required work within different areas of the framework, not only directly related to the primary goal. It also provided the insight that in order to reach the desired extendable structure, many other improvements had to be done first, including the removal of large experimental features. To aid the development, usage of state of the art Continuous Integration testing (CI) were key. Changes to such systems are also part of the development process. The name of the project changed in the middle of this thesis work, going from RTFM to Real-Time Interrupt-driven Concurrency (RTIC). The implemented features and usability fixes detailed in this thesis improves the user experience for embedded system developers resulting in increased productivity while making the development process of such systems more accessible. These general improvements will be part of the next release of the framework. A version v0.6.0-alpha.0 of the framework has been released for testing. The experiences gained related to open-source project governance during this work are also presented.

To develop a high performant web service in Java, Reactive WebFlux has previously been utilized as the only alternative. With the introduction of virtual threads in Java 19, it has been considered that it would be an alternative to the current provided option. This paper presents the performance difference between Spring applications powered by normal threads, virtual threads, and its reactive counterpart Reactive WebFlux. The tests were done by creating three prototypes, which were used to call an endpoint with a set delay time and increasing the number of requests per second until system failure. The results show that the virtual threaded prototypes performed slightly better than the reactive prototype. The question remains whether the Reac- tive WebFlux application using the most optimal web server produces a different re- sult, as well as future research on how virtual threads perform with database usage. / För att utveckla högpresterande webbtjänster i Java har Reactive WebFlux varit det främsta alternativet. Med introduktionen av virtuella trådar i Java 19 har spekulerats kunna ersätta reaktiva webbtjänster. Detta arbete presenterar prestandaskillnaden mellan Spring-applikationer som drivs av normala trådar, virtuella trådar och dess reaktiva motsvarighet Reactive WebFlux. Testerna utfördes genom att skapa tre pro- totyper, som användes för att anropa en slutpunkt med en satt fördröjningstid och öka antalet förfrågningar per sekund fram till systemfel. Resultaten visade att proto- typen med virtuella trådar presterade något bättre än den reaktiva prototypen. Där- emot är det ännu oklart om Reactive WebFlux-applikationen med en optimal webb- server skulle producera ett annat resultat. Dessutom skulle det vara intressant för framtida forskning om hur virtuella trådar fungerar med databasanvändning.

Concurrent programming is a form of computing, where several computations are executed in overlapping time periods. This can improve a system’s capability of handling growing amounts of work and execute faster on multicore processors. Lock is a usual tool used to ensure shared data is handled correctly. However, using locks could also have some performance disadvantages caused by its overhead and waiting time during high contention.The company FIS believes a lock-free implementation using atomic operations could improve ability to handle growing amount of work and speed of a component in their trading system. Hence, the aim of this study is to provide insight of how impactful lock-free programming could be. This was achieved by developing a new version of the component and comparing its performance with the original lock-based implementation. The new implementation was developed by eliminating locks in the component and replacing them with lockfree data structures. However, a lock was still needed in one of the data structures, making the new implementation only partially lock-free. Results from tests performed directly on the component showed that the partially lockfree version performed better in some areas and worse in other. Furthermore, the partially lock-free implementation performed better in isolated tests which were used to measure parts of the component where direct tests could not be performed. This gives a sign of that a general performance improvement was achieved by using lock-free programming in the provided component. / Concurrent programming är en form av programmering, där flera beräkningar exekveras i överlappande tidsperioder. Detta kan förbättra ett systems förmåga att hantera växande mängder av arbete, och dessutom kunna exekveras snabbare på flerkärniga processorer. Lås är ett vanligt verktyg som används för att säkerställa att data i delat minne hanteras korrekt. Användningen av lås kan dock påverka prestandan negativt. Detta är på grund av minimalkostnad som tillkommer vid användning av lås samt väntetid på låset som kan uppstå vid hög konkurrens.FIS anser att en låsfri implementation baserat på atomiska operationer skulle kunna förbättra förmågan att hantera växande mängd arbete och hastigheten på en komponent i sitt tradingsystem. Syftet med denna studie är därför att ge insikt om hur effektiva låsfria program kan vara. Detta uppnåddes genom att utveckla en ny version av komponenten och jämföra dess prestanda med den ursprungliga, låsbaserade, implementation. Den nya implementationen utvecklades genom att eliminera lås med hjälp av låsfria datastrukturer. Dock behövdes ett lås i en av datastrukturerna, vilket innebar att komponenten endast var delvis låsfri. Resultat från tester utförda direkt på komponenten visade att den delvis låsfria versionen presterade bättre på vissa områden och sämre i andra. I de isolerade testerna dock, som användes för att mäta delar av komponenten där direkta tester inte kunde utföras, presterade den delvis låsfria versionen bättre. Detta ger en indikation på att en generell prestandaförbättring för den tillhandahållna komponenten uppnåddes med hjälp av låsfri programmering.

Due to limitations in hardware, raising processor clock speeds is no longer the primary way to increase computing performance. Instead, computing devices are equipped with multiple processors (they are multi-core) to increase performance by enabling parallel execution of code. To fully utilize all available computational power, programs need to be concurrent, i.e. be able to manage multiple tasks at the same time. To this end, programming languages and platforms often provide a concurrency model that allows developers to construct concurrent programs. These models can vary both in design and implementation. In September of 2021, a new version of the Swift programming language, most commonly used to develop mobile applications on Apple’s iOS platform, was released. This release introduced a new concurrency model, Swift concurrency (SC), featuring e.g. structured concurrency and the async/await pattern. The performance of a concurrency model is important, not the least because end users expect applications to be responsive and performant. This thesis investigates Swift’s new concurrency model from a performance perspective, comparing it to a previous model, Grand Central Dispatch (GCD). Six benchmark applications are developed and implemented in both the GCD and the Swift concurrency models. Three of the benchmarks are focused on exercising separate parts of the models in isolation. The other three use the models to solve classical computational problems: Fibonacci numbers, N-Queens problem, and matrix multiplication. A performance analysis is carried out to study the differences in execution time and memory consumption between the two models. The results show differences between the two models, especially in execution time, and indicate that neither model consistently outperforms the other. Finally, some possible avenues for future work are identified. / På grund av begränsningar i hårdvara går det inte längre att öka datorprestanda genom att enbart öka klockfrekvensen hos processorer. Datorer förses numera istället med flera processorer (s.k. multi-core) för att öka prestanda genom att möjliggöra parallell exekvering av kod. För att till fullo kunna utnyttja all tillgänglig datorkraft så måste program vara concurrent, det vill säga att de måste kunna hantera flera olika uppgifter samtidigt. För detta ändamål tillhandahåller programmeringsspråk och plattformar ofta en concurrency-modell som låter utvecklare konstruera program som är concurrent. Dessa modeller kan variera både i design och i hur de är implementerade. I september 2021 så släpptes en ny version av programmeringsspråket Swift, som främst används för att utveckla mobilapplikationer på Apples iOS-plattform. Den nya versionen introducerade en ny concurrency-modell, Swift concurrency, med bland annat strukturerad concurrency och async/await-mönstret. Prestandan i en concurrency-modell är viktig att beakta, inte minst för att användare förväntar sig att applikationer ska vara responsiva och kraftfulla. Denna studie utvärderar den nya concurrency-modellen ur ett prestandaperspektiv, och jämför den med en tidigare modell, Grand Central Dispatch (GCD). Sex stycken benchmark-applikationer skapas och implementeras i både GCD- och Swift concurrency-modellerna. Tre av våra benchmarks fokuserar på att utvärdera enskilda delar av modellerna var för sig. De andra tre använder modellerna för att lösa klassiska beräkningsproblem: Fibonacci-tal, N-Queens-problemet, och matrismultiplikation. En prestandaanalys utförs för att studera skillnaderna i exekveringstid och minnesanvändning mellan de två modellerna. Resultaten visar på skillnader mellan de två modellerna, särskilt i exekveringstid, och indikerar att ingendera modell konsekvent presterar bättre än den andra. Slutligen identifieras några möjliga vägar för framtida arbete.

[pt] O objetivo deste trabalho é explorar e estender a exibilidade provida pelo modelo híbrido de concorrência orientado a estágios, que visa integrar tanto loops de eventos cooperativos como threads preemptivas em um conceito único de mais alto nível. As contribuições deste trabalho estão centradas numa proposta de extensão do modelo de estágios que desacopla a especificação de aplicações concorrentes das decisões relacionadas ao ambiente de execução, permitindo que elas sejam fexivelmente mapeadas em diferentes configurações de acordo com as necessidades de escalonamento de tarefas e granularidade de processamento em partes específicas da aplicação. Procurando prover uma definição adequada para o conceito de modelos de concorrê- ncia híbridos, propomos um sistema de classificação que se baseia na combinação de características básicas de sistemas concorrentes e a possibilidade de execução paralela em múltiplos processadores. Com base nessa classificação, analisamos os benefícios e desvantagens associados a cada modelo de concorrência, justificando a adoção de modelos que combinam threads e eventos em um mesmo ambiente de programação, e descrevemos a extensão do paradigma de programação orientado a estágios. Finalmente, apresentamos a implementação do modelo proposto na linguagem Lua e seu uso em cenários de execução que confirmam os benefícios da extensão do modelo de estágios na especificação de aplicações concorrentes. / [en] The purpose of this work is to explore and extend the flexibility provided by the staged event-driven concurrency model to integrate both cooperative event loops and preemptive threads in a single high level abstraction. The contributions of this work are focused on the extension of the staged model that decouples the specification of concurrent applications of the decisions related to the execution environment, allowing them to be fl exibly mapped to different configurations according to the task scheduling needs and processing granularity in specific parts of the application. In order to provide an adequate definition of the concept of hybrid concurrency models, we propose a classification system that is based on the combination of basic features of concurrent systems and the possibility of parallel execution on multiple processors. Based on this classification, we analyze the benefits and drawbacks associated with each concurrency model, justifying the adoption of models that combine threads and events in the same programming environment and the extension of the staged model. Finally, we present the implementation of the proposed model in the Lua programming language and its use in execution scenarios that confirm the benefits of the extension of the staged model in the specification of concurrent applications.

Baigiamajame magistro darbe tiriama skydinių karkasinių gyvenamųjų namų rinka Lietuvoje. Atlikta rinkos struktūros analizė. Išnagrinėta situacija statybos sektoriuje ir aprašyti individualiųjų gyvenamųjų namų tipai. Remiantis įvairiais metodais atlikta įmonių, gaminančių skydinius namus, konkurencinė analizė. Daugiakriteriu metodu nustatyta racionaliai dirbanti įmonė, gaminanti skydinius namus. Anketiniu tyrimu išsiaiškintas visuomenės supratimas ir nuomonė apie skydinę karkasinę statybą. Ištyrus skydinių karkasinių gyvenamųjų namų rinką Lietuvoje, pateiktos baigiamojo darbo išvados. Darbą sudaro 8 dalys: Įvadas; Rinkos struktūros teorinė analizė; Statybos sektoriaus apžvalga; Individualiųjų gyvenamųjų namų Lietuvoje apžvalga; Gyvenamųjų namų Lietuvoje rinkos tyrimas; Medinių skydinių karkasinių gyvenamųjų namų rinkos tyrimas Lietuvoje; Išvados; Literatūros sąrašas. Darbo apimtis – 79 p. teksto be priedų, 32 paveikslai, 12 lentelių, 66 bibliografiniai šaltiniai. / In the final master’s work the market of living panel frame houses in Lithuania is being studied. Analysis of market structure was done. The situation of construction sector was analyzed and types of individual living houses were described. Referring to various methods the concurrency analysis of panel houses manufacturing companies was done. The multi-criteria method established rationally working company in this sector. The questioner research discovered understanding and opinions of society about panel frame construction. After the research of panel frame living houses market in Lithuania had been done, the conclusions of final work were made. The work includes 8 parts: Introduction; Analysis of market structure; Survey of construction sector; Review of individual living houses in Lithuania; Market research of living houses in Lithuania; Market research of wooden panel frame living houses in Lithuania; Conclusions; List of literature. Volume of work – 79 pages of text excluding enclosures, 32 pictures, 12 tables, 66 bibliography sources.

Many activities are comprised of temporally dependent events that must be executed in a specific chronological order. Supportive software applications must preserve these temporal dependencies. Whenever the processing of this type of an application includes transactions submitted to a database that is shared with other such applications, the transaction concurrency control mechanisms within the database must also preserve the temporal dependencies. A basis for preserving temporal dependencies is established by using (within the applications and databases) real-time timestamps to identify and order events and transactions. The use of optimistic approaches to transaction concurrency control can be undesirable in such situations, as they allow incorrect results for database read operations. Although the incorrectness is detected prior to transaction committal and the corresponding transaction(s) restarted, the impact on the application or entity that submitted the transaction can be too costly. Three transaction concurrency control algorithms are proposed in this dissertation. These algorithms are based on timestamp ordering, and are designed to preserve temporal dependencies existing among data-dependent transactions. The algorithms produce execution schedules that are equivalent to temporally ordered serial schedules, where the temporal order is established by the transactions' start times. The algorithms provide this equivalence while supporting currency to the extent out-of-order commits and reads. With respect to the stated concern with optimistic approaches, two of the proposed algorithms are risk-free and return to read operations only committed data-item values. Risk with the third algorithm is greatly reduced by its conservative bias. All three algorithms avoid deadlock while providing risk-free or reduced-risk operation. The performance of the algorithms is determined analytically and with experimentation. Experiments are performed using functional database management system models that implement the proposed algorithms and the well-known Conservative Multiversion Timestamp Ordering algorithm.