The primary goal of using a multithreaded approach during software development is to improve the per formance indicators of the program code. However, another equally important aspect of multithreaded development is maintaining software reliability.
Using multithreading and synchronization tools can lead to a number of errors: Data race, Race Condition, Deadlock, Livelock, and Starvation [2]. The presence of these problems in the code during program execution can lead to various consequences, from crashes to unpredictable or incorrect pro gram behavior. Approaches to solving multithreaded issues can vary significantly depending on the programming language, framework, development tools, etc. However, all of them have certain draw backs in their application, as they can negatively impact both the resource intensity of the development process and the performance of the developed program code. These approaches can be fundamentally divided into two types: those that prevent the occurrence of errors and those that allow the engineer to detect errors when they occur.
A Data race occurs when two threads simultaneously access the same memory area, with at least one of them performing a write operation [2]. A classical mechanism to prevent Data race in multithreaded code is the use of synchronization. By synchronizing data access, it is possible to 14th International Scientific and Practical Conference from Programming UkrPROG'2024, May 14-15, 2024, Kyiv, Ukraine * Corresponding author. † These authors contributed equally.
k.nesterenko@kpi.ua (K. Nesterenko); stiv.inna@gmail.com (I. Stetsenko); eduard.zharikov-fiot@lll.kpi.ua (E. Zharikov) 0000-0003-3921-4324 (K. Nesterenko); 0000-0002-4601-0058 (I. Stetsenko); 0000-0003-1811-9336 (E. Zharikov) ensure that a specific memory area can only be modified by one thread at a time or that it will not be modified during its reading by a thread. Synchronization tools are an integral part of modern programming languages and continue to evolve, expanding developers' capabilities in managing multithreaded programs and their resources, such as the C++ Concurrency Library [3]. However, the use of synchronization primitives has its drawbacks, the main one being a reduction in program code performance. Besides the fact that the application of a primitive, such as acquiring a mutex by a thread, takes additional time to execute, a significant amount of time can be lost by threads waiting for a resource protected by a synchronization primitive to be released.
To improve the performance of program code, developers increasingly use approaches to software development without blocking synchronization primitives [4]. However, this significantly increases the risk of Data race problems. Various tools are used to detect this problem directly during code execution, such as the Data Race Detector in the Go programming language [5] or by statically analyzing the written program code [6]. Recently, there have been developments related to using artificial intelligence to detect Data races in program code [7].
However, using such tools to detect Data races also has drawbacks, as it requires the introduction of additional tools in the software development and testing process, increasing the overall resource intensity of development. Furthermore, after detecting an error, it must be processed and corrected by the developer, and the program tool must be rechecked for new errors.
Unlike Data race, Race condition is a much more challenging problem to detect because its nature is not technical but semantic. The definition of the term Race condition has long been a subject of discussion, but currently, it can be formalized as a problem arising from the order of operations execution in threads affecting the program's result [8].
Similar to the Data race error, there are certain tools to detect Race condition that warn the developer of the potential occurrence of this problem through static code analysis [9] or by identifying dangerous patterns during code execution [10]. However, the accuracy of such detection is often unsatisfactory. These methods are also prone to false positives, requiring the developer to spend additional time and resources verifying the tool's data.
There are no formalized methods and tools to avoid Race condition in the general case. Reducing the number of such errors or avoiding them can only be achieved by using certain methods and architectural approaches to multithreaded software development [11].
Deadlock is a state in a multithreaded program where two or more threads cannot continue their execution due to mutual blocking. The classic strategy to avoid Deadlock is a method where a thread acquires all the resources it needs exclusively at the beginning of its execution [12]. This prevents the formation of cyclical dependencies between two threads. The thread either executes or waits until all the resources it needs are released. However, this approach negatively impacts performance, as, in the general case, the thread does not need all the resources at each moment of execution, and thus, they could be used by other threads.
There are many different methods and algorithms for detecting Deadlock. For example, by using timers, it is possible to control the execution time of certain critical sections of code in threads and, if this execution time exceeds a certain threshold, notify the developer of a potential Deadlock [12]. It is also worth noting that there are Deadlock recovery strategies [13], which are extremely important for systems with increased reliability requirements. However, it is evident that recovery strategies negatively affect software performance.
Starvation is a state in a multithreaded program where one of the threads cannot perform a task due to the inability to access the necessary resources. This state can arise due to design errors in multithreaded programs when resources protected by synchronization primitives are used by threads for a long time. As a result, other threads spend significant time waiting for the necessary resource to be released. To avoid Starvation, prioritization algorithms [14] or task scheduling [15] are usually used, guaran teeing that the task will be performed at a certain moment and allowing tasks to be distributed in such a way as to minimize time spent waiting for resources to be freed.
Various software tools can be used to detect Starvation, examining metrics about the execution time of individual functions in threads and allowing the developer to identify and fix problematic sections of the program code [16]. Such tools are often integrated into software testing automation processes to constantly monitor the program code state and notify developers of anomalies or performance issues.
In the result of the analysis of existing problems of multithreading and possible solutions, it can be stated that solving these problems significantly increases the resource intensity of multithreaded software development. Additionally, some of the existing solutions negatively affect the performance of the software, which puts the developer in a difficult position of choosing between performance and reliability of the software product.
Therefore, the problem of reducing the resource intensity of multithreaded software development without compromising its reliability and performance requires further research.
program based on a given dependency graph
The main idea of the method for managing the execution of tasks in a multithreaded program based on a dependency graph is to define the process of executing tasks, which the computations are divided into, as a dependency graph where each vertex corresponds to a specific task, and the graph edges denote dependencies between these tasks. Tasks can be executed in parallel in threads, considering the constraints imposed by the dependencies between them.
The method for managing the execution of tasks in a multithreaded program based on a dependency graph allows describing the execution process of multithreaded program code in a clear and well structured form and avoids or detects problems arising from the use of task execution synchronization.
Suppose that for successful program execution, it must complete K tasks that can be described by the set A = {A 0 , …, A K-1 }. If the program's result depends on the order of execution of tasks A i and A j , and only one of the possible results is correct, it means the tasks are in a semantic dependency. Let Y be a directed acyclic graph with vertices G = {G 0 , …, G K-1 } and arcs U. Each task A j from the set A corresponds to the vertex G j of the graph Y. If there is a semantic dependency between tasks A i and A j , or if tasks A i and A j use a shared resource during their execution, then there is a connection between the corresponding vertices G i and G j in the graph, and the arc (G i , G j ) is assigned to it in the graph. In this way, the set of arcs is created:
(1) Tasks can be dynamically loaded during program execution, creating new vertices and arcs in the graph, and deleted upon successful completion. Thus, each task has a representation in the dependency graph from creation to completion. Since the start of the task, the correspondent vertex is not available for creating a new arc. When a new task is created, the added arcs should not form a cycle in a graph. If all the added arcs are directed to the new vertex (G i , G x ) then the new graph will be acyclic. Indeed, if no path can be built through the new vertex then a new cycle cannot be built in the graph. Similarly, if all added arcs are directed from the new vertex (Gx, Gj) then the new graph will be acyclic. However, if among added arcs are both cases, to and from the new vertex, then the following condition should be checked. For each pair of added arcs (G i , G x ) and (G x , G j ), a path from G j to G i should not be found in graph U:
(2) where P is a path in graph Y, is an existing directed connection between vertices in graph. Indeed, if the path exists, then the following cycle would be found in a new graph:
(3)
Task A x can be executed in the program if and only if there is no arc (G i , G x ) in the dependency graph. If task Ax is executed, it is deleted from the graph along with the arcs (G x , G j ):
(4) Program execution is considered successful when the set of vertices in the dependency graph Y is empty at the end of the program, meaning that all tasks loaded for execution have been completed: .
The basis for implementing the method of task execution management in a multithreaded program based on a dependency graph is the implementation of the GraphManager class (Figure 1), which will be responsible for the order of task execution. Accordingly, this class must control the list of available tasks, select tasks that can be executed, and update the existing dependencies after their execution. To represent a task as a vertex in the dependency graph, it is necessary to create a GraphNode class, which will contain information about the task to be executed and a list of tasks it depends on and tasks that depend on it. Dependencies between tasks are established by the developer after the corresponding GraphNode class objects have been added to the GraphManager. During the implementation of the method, the developer must represent the types of tasks available in the program as separate SomeConcreteJob classes, which are descendants of the abstract AbstractJob class.
To avoid the Race condition problem, developers need only specify dependencies between tasks, ensuring the correct sequencing necessary for program output integrity. This method guarantees that tasks with established dependencies will execute in the specified order relative to each other.
To address Data race issues and improve performance by reducing the need for synchronization primitives to protect specific objects, developers can establish dependencies among tasks requiring exclusive access to certain resources while allowing parallel execution of tasks that do not modify shared resources.
While the proposed method does not eliminate Deadlock and Livelock issues entirely, it simplifies implementing mechanisms to detect these issues prior to executing the dependency graph. Dependency graph edges can denote not only semantic dependencies between tasks but also dependencies between tasks requiring exclusive access to shared resources. Deadlock problems arise when synchronized resources are mutually dependent between two threads. With this method, detecting potential Deadlocks reduces to finding cycles in the graph, a problem for which many algorithms exist [17]. Since cycle detection need not occur before every program execution but only after changes to the dependency graph, applying a depth-first search-based cycle detection algorithm suffices for this method.
Similarly, this approach applies to Livelock issues. Absence of cycles in the graph and construction of dependencies among tasks needing exclusive access to shared resources prevent such issues during program execution. The proposed method does not entirely prevent Starvation problems. However, it minimizes them and facilitates implementing runtime monitoring mechanisms without relying on external control mechanisms. Task execution management based on the dependency graph allows developers to configure the graph so that no task waits for the release of a specific shared resource after starting its execution. Instead, such a task simply will not start until the resource becomes available, adhering to task dependencies. Consequently, system resources can be directed toward executing tasks currently without dependencies or those whose dependencies have already been fulfilled.
Nevertheless, this method does not prevent scenarios where a task depends on many other tasks, thereby preventing them from executing until it completes successfully. Detecting such issues involves implementing mechanisms to monitor the graph's state, recording execution times, waiting times, and other relevant data for each task. With this information, developers can modify the code to address problematic areas and improve the performance of the software tool.
To evaluate the effectiveness of the proposed method, a program was developed in C++ that, using the Strategy design pattern, allows executing the same set of tasks either through a conventional implementation of a multithreaded program or based on a dependency graph. Thread management utilizes the Thread Pool design pattern (Figure 2).
To enable configuration of which approach to use for task execution, the IJobManager interface (Figure 3) was created. This interface encapsulates the mechanism through which the Thread Pool selects the next task for execution. The IJobManager interface is implemented in the DefaultJobManager class (Figure 4) and the GraphJob Manager class (Figure 5). The DefaultJobManager class is implemented using a traditional queue based on the "first in, first out" (FIFO) principle. Accordingly, it reflects the classic scenario of writing a multithreaded program where synchronization responsibility lies entirely on synchronization primitives. The GraphJobManager, in turn, is implemented using the proposed method. Within the class, there is a data structure called m_graphMap, which associates each task with a corresponding node in the graph, described using the GraphNode class (Figure 6). Each instance of the GraphNode class internally stores the number of unresolved dependencies for its corresponding task, or in other words, the number of edges entering this vertex in the graph. Additionally, each instance holds pointers to other instances of the GraphNode class, effectively describing edges leaving this vertex in the graph. When all dependencies for a graph vertex are satisfied, it is moved to the execution queue in the GraphJobManager class. The GraphJobManager class also includes the AddJobDependency function, which allows specifying dependencies between tasks, effectively creating a new edge in the dependency graph.
To test the Thread Pool, a pool of 4 threads was configured. The test set of tasks consists of 4 groups of 100 tasks each, which can be represented as sets А ={A 0 , …, A 99 }, B = {B 0 , …, B 99 }, C = {C 0 , …,C 99 }, D = {D 0 , …, D 99 }. Within each group, simulating real-world conditions for a multithreaded task, it is assumed that there is a specific resource for which each task obtains exclusive access using a mutex during its execution. After obtaining access, the task waits for 10 ms, simulating computation using the Busy wait approach [18], and successfully completes its execution. The use of Busy wait specifically avoids the impact of thread optimization mechanisms implemented in the operating system on the obtained result.
To obtain more accurate results for comparison, the test set of tasks is executed 100 times for each implementation. The following metrics are collected: fastest execution time, slowest execution time, and average execution time.
To measure the execution time of the program for computing the specified set of tasks using the dependency graph constructed based on the proposed method, the GraphJobManager will be used instead of the DefaultJobManager. When tasks are added in GraphJobManager, a graph node described by the GraphNode class is created for each task. Then, using the AddJobDependency function, dependencies between tasks are established, effectively adding edges in the dependency graph. In this case, the dependency object is the resource allocated for each group of tasks. Thus, using the AddJobDependency function, dependencies between tasks will be created as follows: each task Ai depends on the execution of task Ai-1, Bi depends on Bi-1, Ci depends on Ci-1, and Di depends on Di-1 where i ∈ [1,99].
It is worth noting that since the classical approach to executing multithreaded tasks is implemented using a queue, the total task execution time depends on their order in this queue. Accordingly, three testing scenarios were developed for the classical approach: best case, worst case, and realistic.
The best-case scenario considers tasks in the queue arranged such that the time spent waiting for access to resources by tasks is minimized. This scenario corresponds to arranging tasks in the queue where each belongs to a different group and requires a different resource for execution. Thus, the sequence of tasks in the queue will look like: {A 0 , B 0 , C 0 , D 0 , ..., A 99 , B 99 , C 99 , D 99 }.
The worst-case scenario considers tasks in the queue arranged such that the time spent waiting for access to resources by tasks is maximized. This scenario corresponds to arranging tasks in the queue where groups of tasks are sequentially placed in the queue. Thus, the sequence of tasks in the queue will look like: {A 0 , ..., A 99 , B 0 , ..., B 99 , C 0 , ..., C 99 , D 0 , ..., D 99 }. The realistic scenario considers tasks randomly placed in the queue, simulating conditions closer to those that may occur during real program execution.
The experimental results represented in Table 1 demonstrate that compared to the realistic and worst case execution scenarios, the proposed method showed significantly higher performance. This result was achieved because a proposed method allows developers to specify the task execution order by introducing dependencies between them, thereby reducing the impact of synchronization mechanisms on the overall program execution time. The experimental results of the best-case, realistic-case, and the case of dependency graph scenarios are represented in detail in Figure 7. The performance evaluation was done on 100 executions of the program.
In the best-case execution scenario, the results show minimal performance difference in favor of the classical approach. This can be easily explained by the fact that in this case, the task execution order is identical in both approaches, but the proposed method incurs additional time for graph construction and update. However, considering that such a scenario may rarely occur in real-world conditions.
Therefore, according to the results of the experimental study, it has been proven that the proposed method allows to increase the performance of the test program on average by approximately 35%, compared to the classical approach: (1542.71 − 1010.74) / 1542.71 •100% = 34.48%.
An analysis of the challenges arising during the development of multithreaded programs was con ducted. For each issue, current methods of resolution were discussed, outlining their advantages and disadvantages.
A method for managing task execution in a multithreaded program based on a specified dependency graph was proposed. The general idea, formal description, and programmatic details of the method were provided, along with how this method addresses the identified issues and the advantages it provides to developers compared to existing methods.
A C++ program and a suite of tasks were developed to measure the performance of the proposed method against the classical approach of executing tasks in threads. After analyzing the obtained results, it was concluded that the proposed method improves the performance of the test program on average by 35% compared to the classical approach.
Future plans include further development of the method's use for developing multithreaded programs based on dependency graphs, aiming to create a comprehensive development environment for such programs.