Data Race Detection For Multi Threaded Programs Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Data race exists if there is a data race condition. Data race condition occurs when two or more threads concurrently access a shared variable (memory location) and at least one of these accesses is a write. Error: Reference source not found shows a kind of famous data race owning to incorrect interleaving of two threads.

Expected result of is 'counter=2' which differs from the above execution result because of incorrect interleaving executions of two threaded. When data race occurs, program may fail to its approach. So we have to detect such data races and modify programs. That is data race detection for multi-threaded programs.

As well as I known, researchers have proposed two kinds of algorithms for detection of data race: static ones and dynamic ones. Static data race detection is the analysis of programs without executing it (offline analysis), while dynamic one is the analysis during the executing it (online analysis). The difference between these two exists in various aspects. One difference is that dynamic race detectors can be applied to larger programs but static ones are not suitable for large programs. However, dynamic ones usually have higher performance overhead [4] than static data race detectors. Also dynamic data race detectors need to schedule the order of executing threads in order to detect more data races. Another difference is that static detector may be designed to find data races of all execution paths, which leads to reporting of false data races; while dynamic detectors have no ability to explore all execution paths but they can find real data races for a certain execution path.

I studied the dynamic data race detection. In the following sections, I will explain what I have learned through several algorithms and framework tools in section 2 and section 3 respectively. Section 4 reviews my study and section 5 gives my work for coming weeks.

Existing algorithms

Several algorithms have been proposed to detect data race dynamically for multi-threads programs, such as Eraser, Djit+, BasicVC, LiteRace and FastTrack; and they can be classified to two categories: lockset based algorithms and happens-before relation based algorithms.

Lockset based algorithms maintain a set of locks for each shared variable during executing of a multi-threaded program, and monitor every critical operations and update Lockset (add new locks or remove existing locks). Once the Lockset of a variable becomes empty, data race will be reported. However, some of reported data races are not actual data races. And also, some of real data races are missed. Hence, this kind of algorithms has both false positive and true negative problems.

Happens-before relation is a partial order of all events of a multi-threaded or concurrent program's execution. Algorithms based on this relation have to maintain a vector recording / logging a thread's current timestamp and other threads' timestamps known to it. When there is a critical operation on a variable, an event will be called to compare vectors of involved threads to find whether the global order of involved threads is disturbed by the operation (usually write and read to a shared variable) just executed. If so, data race will be reported. This kind of algorithms may also miss some real data races since that every execution cannot cover all execution paths while certain data races may only exist in certain execution paths. However, the reported data races by dynamic data race detector are real data races. Hence, only true negative problems exist in this kind of algorithms.

Both categories of algorithms need to instrument the source code files or binary files (including Java byte code files) and execute part or whole instrumented program to analyze data races depending on execution strategies.

Here are some critical operations commonly concerned by dynamic data race detection algorithms: read (rd) or write (wr) to a variable (v); acquire (acq) or release (rel) a lock; fork or join a thread (t).

Eraser

S. Savage, et al at [5] proposed a dynamic data race detector, Eraser, using lockset based algorithm. Lockset is a set of locks on a shared variable. In order to avoid failure of Error: Reference source not found, programmers usually put locks on shared variables, however, which may be used incorrectly. S. Savage, et al firstly introduced a simple lockset algorithm and then revised it to be more practical.

Assumed environment in simple lockset algorithm: each shared variable is protected by some locks whenever a thread reads or writes to .

Simple lockset algorithm: let is a set of locks on variable . Initially, contains all locks. On each access to , update to be interaction of and , where is also a set of locks held by thread . After updating , if = { }, a data race will be reported.

Error: Reference source not found shows an example using simple lockset algorithm to detect data race.

Simple lockset algorithm successfully detected a real data race in Error: Reference source not found in which variable is protected by different locks (lock_1 and lock_2) in different statements of two threads. However, the assumed environment of this simple lockset algorithm is less practical. S. Savage, et al at [5] discussed three problems in above algorithm:

Executing points of two threads:

Thread 2:

Sync (lock_2) {

v=3;

}

Sync (lock_2) {

v=3;

}

Sync (lock_2) {

v=3;

}

Thread 1:

Sync (lock_1) {

Sync (lock_2) {

v = 1;

}

v=2;

}

Thread 2:

Sync (lock_2) {

v=3;

}

Thread 1:

Sync (lock_1) {

Sync (lock_2) {

v = 1;

}

v=2;

}

Sync (lock_1) {

Sync (lock_2) {

v = 1;

}

v=2;

}

Sync (lock_1) {

Sync (lock_2) {

v = 1;

}

v=2;

}

{lock_1, lock_2}

{lock_1, lock_2}

{lock_1, lock_2}∩

{lock_1}=

{lock_1}

{lock_1}∩lock_2}=

{ }

=>Data race reported

Figure 2 an example of Lockset algorithm

Programmers usually put no lock on a variable when they initialize it. For example, to define and initialize an integer counter in Java, we may write like just this "static int counter = 0;" which contains no locks.

For read-shared variables, no lock needs to synchronize it. In this situation, no data race should be reported.

Shared variable is programmed to allow only single thread to write it and multi-threads to read it.

In case of above three problems, Simple Lockset Algorithm will report false data race. S. Savage, et al at [5] revised their Simple Lockset Algorithm to report data race according to state of which is monitored using following rules.

On allocating to , its state is denoted by Virgin (in this state, there is no write or read to yet). After initialization to , its state changes to Exclusive.

Being in state Exclusive, if there is only one thread accessing , state of remains Exclusive.

On the second thread's first read to , state of changes to Shared; or its first write to , state of changes to Shared-Modified.

Shared state can be changed to Shared-Modified only when a thread write to .

State of Shared-Modified is the final state of .

Being in each state, Eraser updates of and report data race as follows:

At state of Exclusive, Eraser does not update and does not report data race.

At state of Shared, Eraser updates but does not report data race regardless of emptiness of .

At state of Shared-Modified, Eraser updates and reports data race.

wr, new thread

wr

rd, new thread

rd / wr, first thread

wr

rd / wr

rd

Virgin

Exclusive

Shared-

Modified

Shared

Figure 3 a finite state machine of variable Revised Lockset algorithm can be illustrated through a finite state machine (Error: Reference source not found).

In implementation, Eraser needs to instrument original binary program to be new binary program so that Eraser functions can be called when critical operations executed.

Djit+

Djit+, which is a variant algorithm of Djit, also cares six above critical operations and maintains one vector for each thread t, one vector for each lock m and two vectors and for write and read of v. Each thread owns a time-stamp which can only be increased after release operations. records current time-stamps of thread t and others known to t on acquire operations. records latest time-stamps of all threads' operations (lock release) on Lock m. and record the latest time-stamps of write and read to variable v of all threads respectively.

Every acquire of lock m performed by thread t will trigger updating of to be max {, } while every release will trigger updating of to be and to be max {, }, orderly. And every read and write will trigger updating and to be and , respectively.

Immediately after each read to v, a comparison between and will be conducted to make sure that no write before this read. If , , no data race will be reported; otherwise a data race will be reported. Also immediately after each write, except of above comparison, a second comparison between and will be conducted to make sure that no write before this read. If , and , no data race will be reported; otherwise, a data race will be reported.

Error: Reference source not found

Operation Operation Comparison

<1,1> <1,1> <0,0> <0,0> <0,0> <0,0>

Figure 4 an example of Djit+ algorithm with two threads of Figure 2 ('→':execution order;

'<x, y>' : updated values; '<x, y>': values to be compared. Comparison with is omitted.)

Acq(lock_1)

<1,1> <1,1> <0,0> <0,0> <0,0> <0,0>

Acq(lock_2)

<1,1> <1,1> <0,0> <0,0> <1,0> <0,0>

Wr(v)

<1,1> <1,1> <0,0> <0,0> <1,0> <0,0> <1,1><1,0> ?√

Rel(lock_2)

<2,1> <1,1> <0,0> <2,1> <1,0> <0,0>

Acq(lock_2)

<2,1> <2,1> <0,0> <2,1> <1,0> <0,0>

<2,1> <2,1> <0,0> <2,1> <1,1> <0,0> <2,1><1,1> ?√

Wr(v)

Rel(lock_2)

<2,1> <2,2> <0,0> <2,2> <1,1> <0,0>

Wr(v)

<2,1> <2,2> <0,0> <2,2> <2,1> <0,0> <2,1><2,1> ?Ã-《《Type equation here.

is an example showing that Djit+ algorithm can successfully detect the data race existing in Error: Reference source not found under certain interleaving execution between two threads.

Djit+ is able to detect real data races. However, as mentioned above, it does not warrant detection of all data races because its ability is corresponding to coverage of execution paths.

Multi-Race

I learned Multi-Race algorithms at [1] not directly from the original paper. So I will give a general idea of it and my own analysis.

Multi-Race combines lockset algorithm and Djit+ algorithm. It maintains a , and for each variable v, a vector for each thread and a vector for each lock. Multi-Race applies both algorithms at the same time except that comparison in Djit+ is done only when the lockset of a variable becomes empty, which can eliminate false data races reported by lockset algorithm and also improve the performance of Djit+ algorithm by reducing some vector comparisons.

However, as a result of combination of above two algorithms, Multi-Race inherits the features of lockset algorithm that is it also misses some real data races. So false-positive problems still exist in Multi-Race algorithm, though, without true-negative problems.

FastTrack

Actually, FastTrack [1] is the first algorithm for dynamic data race detection of multi-threaded programs I have learned. From this algorithm, I then expanded my knowledge to more dynamic data race detection algorithms (such as Djit+, Eraser, Multi-Race and Lite-Race).

FastTrack is based on happens-before order and can be regarded as an improved version of Djit+ algorithm. Its improvement from Djit+ is in two aspects:

Just record the timestamp of last write to a variable. Unlike read-read race, write cannot be shared with write. So if no data race exists in the previous execution, the timestamp of last write to v is enough to detect a data race. Since there is only single value for write information of v, it can only detect data race existing in two concurrent threads and only the first data race on v.

Record a switchable read information for each variable: single value or vector value. Firstly or after a shared write to v, single value will be used for v. the later read operation of different threads will switch single to vector value to use until a new write to v when single is used again.

C. Flanagan, et al, showed through an empirical study that only 0.1% of reads will switch single value to vector value for read information of v, which improves the performance obviously compared to Djit+ algorithm by reducing space complexity and further reducing time complexity. That may be the reason that C. Flanagan, et al named their algorithm 'FastTrack'.

As same as Djit+, FastTrack has no false positive problems but true negative problems because it also cannot cover all executions paths.

The implementation of FastTrack was based on a framework tool called RoadRunner Dynamic Analysis Framework for Concurrent Programs [2] . Several dynamic data race detectors were already implemented on this framework by C. Flanagan, et al. I will give more about this framework in section 3 as well as other frameworks I know.

LiteRace

LiteRace is also based on happens-before relation. There is already some introduction to happen- before relation and its application in data race detection above; so I will explain LiteRace from another view point: strategies in executing instrumented programs, as well as strategies LiteRace adopted.

Dynamic data race detectors need to instrument original programs (source code or binary files) by adding caller functions in order to trigger events for each critical operation to analyze potential data races. There are some strategies to executing instrumented programs. Some detectors execute whole instrumented programs while others may execute portion of them. LiteRace is one of later detectors.

As I mentioned above, the number of detected data race of dynamic data race detector is corresponding to its coverage of execution paths. A dynamic data race detector may detect some data races for each executed path. However, it seems impossible to execute all paths. Then a question comes: which path should a detector adopt to execute? Certainly the ideal execution path should lead a detector to find more data races than other paths.

For some famous programs, such as Apache web server, Firefox web browser and gzip (a famous file compressor), the ideal path should be among those that do not or minor executed path based on statistics. Because these programs have been revised for many times and almost no data race exists in the most executed paths. However, for a newly developed program, nobody may know which path a detector should take.

LiteRace uses a sampling algorithm to execute portion of programs. It classifies the portion to be hot region and cold region dynamically for each thread. Following two paragraphs are a description of sampling algorithm used by LiteRace.

Instrumentation: when instrument the programs, LiteRace create two portions for each original portion. Since portion here is based on function, instrumented programs will contain two versions for each original function. One function is only instrumented by adding synchronization operations (lightly-instrumented) while the second function is instrumented by adding memory logging operations except synchronization operations (heavily-instrumented). In order to decide which instrumented function should be executed dynamically, an additional dispatch checker is added to each pair of differently instrumented functions. The dispatch checker is always called before execution of corresponding function to do some extra work and select one of two functions to be executed.

Selection of functions: for each pair of differently instrumented functions, there are two counters, frequency counter and sampling counter. Initially, frequency counter (denote as f-c) is zero and sampling counter (denote as s-c) is 100%. On each call to this function, f-c will be increased by one; then s-c will be compared to zero. If s-c is not zero, lightly-instrumented function will be selected; otherwise, heavily-instrumented function will be selected. At last, s-c will be updated according to f-c.

Through executing selected functions, only a small percent of variable accesses are monitored, which obviously improve the performance. According to [4] , LiteRace can detect more than 70% of data races by sampling less than 2% of variable accesses, from which we can see that strategies play a great important role in dynamic data race detection for multi-threaded programs.

Framework tools

Dynamic data race detector needs to instrument source code or binary code files in order to call its events to analyze in executing a program, which may be a burden to us. However, several framework tools have been developed to light our burden, such as Calfuzzer [3] [5] , RoadRunner [2] . I just learned RoadRunner in detail and did some experiments.

Extends

Instrument

JVM

RoadRunner

Original Java

Program

Instrumented

Java Program

Events receiver:

Tool

User Tool n

Events

Figure 5 RoadRunner Framework

User Tool 1

RoadRunner [2] is a framework designed for dynamic data race detection of concurrent programs of Java language and also wrote in Java language (Eclipse environment). It instruments Java programs by adding shadow fields and methods to call events (such as memory accessing, lock synchronization, threads forking and joining and, especially method entering and quitting) and further call events-receiver which can be extended for users to implement their tools. Users can also expand it by revising or adding features to it. RoadRunner allows combination of several algorithms. For example, Multi-Race combined Lockset and Djit+ algorithms. Under RoadRunner, this combination can be easily implemented. Error: Reference source not found shows RoadRunner framework.

Based on this framework, C. Flanagan and S. N. Freund implemented many dynamic data race detectors, such as Lockset, Djit+, Multi-Race and GoldiLocks, as well as data race analysis tools, such as Atomizer [2] .

Conclusion

Multi-threaded programs may fail owning to occurrence of data races. Debugging a program to find data race may be very difficult. But detection of data races is a possible way. Several algorithms have been proposed to detect it including static analysis of program codes or binary files and dynamic analysis of interleaving executing thread. Static algorithms not only miss some data races but also report false data races. Recent years, dynamic algorithms are developed much more. These dynamic algorithms are based on two concepts: lockset and happens-before relation. Lockset based algorithms check whether a variable is protected by at least one lock on each access to this variable. Eraser is a notable lockset algorithm based tool. Algorithms based on happen-before guarantee consistence of global order from thread-local orders of involved threads by logging each access to a shared variable for each thread. Djit+ and FastTrack are based on happens-before relation. Multi-Race is the combination of lockset and happens-before.

Dynamic data race detector needs to instrument original programs to call its analysis modules. It is a heavy burden. However, several existing tools may reduce our burden, such as Calfuzzer and RoadRunner framework for Java language programs. In my opinion, RoadRunner, as a event stream based framework, is much simpler to understand and to implement a tool to detect data race in Java programs and it can be expand to support more events. LiteRace instruments programs to support both original and instrumented functions to be selected to execute dynamically, which reduces number of monitoring accesses to memory locations and further improve performance.

Coming Work

When I did some experiments on RoadRunner framework, I found an interesting thing. If I directly run the original multi-threaded program that contained data race, there were no wrong results; however, if on RoadRunner frame work, wrong results would be produced at a high rate. I asked Dr. Chan and he told me that, in order to detect, and detect more, data races, interleaving between different threads would be scheduled, which is called thread schedule and is only one stage out of five. The whole stages include inputs, thread scheduling, monitoring of threads and memory accesses, correctness checking and reporting.

So my focus for coming weeks will be partially on inputs and thread scheduling. Here I can give an example to introduce what I know about inputs. Since a large number of software use UIs to receive data from users. How to test this kind of programs? It refers to inputs. Some data race detectors adopt single input, such as FastTrack mentioned above; while others adopt multi-inputs, such as ART. During the coming weeks, I will expand my study to scope of inputs selection and optimization, such as DART and KLEE.

Finally I am expected to get a deep understanding of the area of software engineering, especially one of its sub fields, software testing.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.