Race Condition in Parallel Processing

ABSTRACT
Initially, computer systems were sequential. Although straightforward, this system architecture is sluggish. Getting to the electricity source

People added multiprogramming, timesharing, and multi-core technologies to computer systems to overcome the CPU constraint. A few issues that never arise in sequential systems did as well at the same time. One of them is the condition of race. A notorious problem in parallel systems is the race situation. Race situation results in nondeterministic behaviour that is very challenging to replicate and debug, which is certainly not what we want. Can a race situation be found in a parallel system? Can we locate every one of these issues? If so, is there a more elegant approach to resolve it? There are so many inquiries that require a response. Clearly, we will have a more dependable and resilient system if we can identify all of these possible dangers and avert them.
I shall introduce the racial condition in this essay. An racial condition is what? Why is it so challenging to resolve. I’ll also look at several approaches of trying to tackle this issue. Basically, there are two broad categories of methodologies used to identify race condition problems. The first is detection at compile time, also known as static detection, and the second is detection at run time, also known as dynamic detecting.Both of them have drawbacks, including those related to coverage and speed. I’ll introduce a few techniques from both groups in this essay. I’ll also demonstrate some methods for racial discrimination.

~Definition of race condition
When two or more threads that share data attempt to update the shared data, a race situation develops.
Users have no influence over the sequence in which threads access shared data since the operating system determines the thread schedule algorithm and can switch between threads at any moment. As a consequence, there has been no change in the data.

~How to detect Race Condition.

Such a situation is obviously inappropriate and not what we would anticipate.
There are typically two categories of solutions to this problem.
One approach is using compile-time race condition detection. Static detection is the name given to this technique. The application does not really need to execute in order to detect static. Static analysis is able to gather comprehensive and detailed information by scanning the entire programme of metadata from a complied application or annotation codes.coverage. Static detection has the drawback that there are a lot of erroneous reports as well.
The alternative approach, referred to as dynamic detection, is race condition detection during runtime. The dynamic approach of detection is more precise than the static method. Dynamic detection will, however, miss certain flaws that exist on uncovered pathways since it only finds race conditions in the path of execution.

Problems with Detection
Static detection with many semaphores is NP-hard [9], making it challenging to come up with a workable solution. If the

Although semaphores are a better synchronisation method, a precise and effective technique does exist [10]. The only other methods known are heuristic ones [3, 5]. Heuristic algorithms only report prospective racial circumstances, therefore there may be false alarms as many of the situations they detect are not actual racial conditions. One can never know which of these are actual race conditions, though, since identifying them is an NP-hard job. And for this reason, it is difficult to correctly utilise a technology to identify race conditions.

Outline
• I’ll cover static race detection in part 2 along with type-based systems and context-sensitive models.
• I will discuss dynamic race detection in section 3 along with the Happens-before relation, Lockset method, and the hybrid approach.
• I’ll provide some examples of tools for detecting races in section 4.
• Section 5 has a summary.

STATISTICAL DETECTION
Compilers were the primary users of static analysis. These days, it is also used in several other fields, including reverse engineering, testing, and programme comprehension.
System Based on Types
Any system with good typing is free of the race situation. A concurrent object calculus race-free type-based system was described by Flanagan et al.
Every method an object has has a type assigned to it by the type system. Additionally, it specifies a set of locks that must be held before to calling the method as well as a lock that must be held prior to updating the function. Each of these locks may be a unique lock connected to the object, as shown in Figure 1 [1], or they could be completely external to the object, as will be shown later.Before we access the methods, we will always verify the locks that that particular methods are intended to hold. In this manner, it is ensured that no two threads will simultaneously attempt to access the same shared data. Race situation won’t occur as a consequence.

Context-Aware Model
Some tools attempt to investigate every possible scenario for thread interleaving in order to provide a high level of programme behaviour coverage, but this poses a practical challenge because as the number of threads rises, the likelihood of this happening increases exponentially, rapidly raising compute complexity. This kind of solution so restricts the analysis’s capacity to scale.
The creators of KISS (Keep It Simple and Sequential) [15] attempt to provide a remedy for avoiding exponential complexity. Their answer is based on a method that turns a concurrent issue P into a sequential problem P’, simulating the behaviours of a significant portion of problem P. Issue P’ can be analysed by a checker with merely a semantic understanding of sequential execution since it is a sequential problem. More significant isbecause if a statement is false in issue P’, then problem P must also be false. Therefore, locating the mistake in P is simple.
It’s also important to remember that KISS is a full but flawed approach (may miss errors).
KISS is an assertion verifier for C programmes with many threads. It requires assistance from sequential model checkers like SLAM. KISS converts the concurrent C programme in Figure 4 to the sequential C programme. We may evaluate the C sequential issue using SLAM or other sequential model checkers like PREfix [2], MC [6], ESP [4], and Blast [11]. The original concurrent program’s error trail may be converted into a SLAM error trace.

Using KISS, 30 different race situations were found in Windows NT device drivers. The code sizes varied from 1KLOC to 10KLOC.Each thread in a concurrent application has its own stack. However, there is only one stack available for the particular thread. It is quite difficult to build behaviours that simulate the interleaving of several threads using only one stack. using a global variable access that passes a flag to r with a value from the set “0, 1, 2.” No access to r occurs when access is equal to 0, read access occurs when access is equal to 1, and write access occurs when access is equal to 2. To determine if there is a race situation brought on either read or write access to r, the two functions checkr and checkw are employed.

DYNAMIC DETECTION .
Run-time dynamic race detection occurs. Dynamic race detection does not provide false assertions, in contrast to static race detection, which occurs at build time. When compared to a static method, dynamic race detection is more accurate. I’ll discuss a few well-liked dynamic race detection techniques, particularly Happens-before and Lockset. Naturally, dynamic race identification also includes flaws like sluggish speed and miss mistakes.
3.1 Happens-before In a collection of concurrent threads, Happens-before specifies a partial order for events.
• If there is just one thread, the temporal sequence of occurrences is reflected by happens-before.
• If there are more than one thread, thread A occurs before thread B if both threads follow the rule while attempting to open the lock and thread A opens the lock before thread B. If accesses to shared data are not sorted by happens-before, data races may occur.
A thread must adhere to the following requirements while attempting to access shared data:
Get the lock [1].
[2] Perform a few actions.
Release the lock at [3].
There is a Happens-before connection between threads a and b if thread a gets the lock before thread b.
Since Thread 1 gains the lock in Figure 6 before Thread 2, it occurs before Thread 2. There is no race issue since Thread 1 releases the lock before Thread 2 attempts to acquire it. Figures 7 and 8 show a different outcome since the threads there do not adhere to the operational lock requirement. Additionally, in these two scenarios there will be a race condition.

According to the happens-before connection between threads 1 and 2 in Figure 7, thread 1 gets the lock before thread 2 does. There is no risk of a race situation since access to variables of both y and v are ordered by Happens-before.
The connection between Happens-before has a secret thread, however. Happens-before will not catch all problems since it only detects race conditions when the improper order of execution manifests. A completely different sequence of events might produce a different outcome.

Algorithm for Locksets
The fundamental tenet of the Lockset algorithm is that every shared piece of data has to be secured by a lock. A thread is required to hold the lock each time it accesses shared data. All reads and writes will be monitored by Eraser [16] to ensure this discipline. Eraser will infer the protection relation from the execution history since it has no notion which lock should be used to secure which piece of data.
3.2.1 Initial Iteration
Initialize C (v) to the set of all locks for each v.
Each time thread t accesses variable v,
If C (v) =, then a warning will be sent. Set C (v) = C (v) Locks held (t).
Shared data, V
Candidate locks are established for v in C (v).
Locks held (t) — Locks hold t the thread.

enhancing the discipline of locking
The locking discipline described above is obviously too severe. There are three typical instances when the rules are broken yet there is no data race problem.
• Initialization: When initialising, shared data often do not need a lock.
• Read-Shared Data: Certain data are solely intended for reading after initialization and do not need locks.
• Read-Write Locks: Read-write locks limit the number of writers while allowing many readers to access a shared piece of data.
There is no need for a thread to retain a lock while initialising data since no other threads have the ability to reference the data that is being accessed.
to prevent false alerts brought on by startup writes.
Eraser only takes into account threads that come after the first, at which point it assumes initialization is complete. Eraser won’t alter the candidate locks set as long as the first thread is still accessing the shared data.
Multiple threads reading the same shared data simultaneously is not a race either. Therefore, since the data is limited to race, there is no need to submit a race. The state transitions that reflect the timing of refining and race reports are shown in Figures .

TOOLS FOR RACE DETECTION
You may discover race condition with the aid of a variety of concurrent instruments on the market. Here are a few examples
CHESS, a Microsoft Research invention
Every run uses a distinct thread schedule; User-mode scheduler; Concurrency unit tests; and it is Reproducible

Summary

Due to their nondeterminism and difficulty in replication or debugging, race situations are the most pernicious faults in parallel computing. I discussed various popular ways to address the race condition in my blog. Either static methods (used at compile time) or dynamic methods (used at run time) are used to tackle the problem. gives some examples of well-known tools for detecting race as well.

6. REFERENCES [1] Abadi, M., Flanagan, C. and Freund, S. N. Types for safe locking: Static race detection for Java. ACM Trans. Program. Lang. Syst., 28, 2 2006), 207–255. [2] Bush, W. R., Pincus, J. D. and Sielaff, D. J. A static analyzer for finding dynamic programming errors. Softw. Pract. Exper., 30, 7 2000), 775–802. [3] Choi, J.-D. and Min, S. L. Race Frontier: reproducing data races in parallel-program debugging. SIGPLAN Not., 26, 7 1991), 145–154. [4] Das, M., Lerner, S. and Seigle, M. ESP: path-sensitive program verification in polynomial time. SIGPLAN Not., 37, 5 2002), 57–68. [5] Dinning, A. and Schonberg, E. Detecting access anomalies in programs with critical sections. SIGPLAN Not., 26, 12 1991), 85–96. [6] Engler, D., Chelf, B., Chou, A. and Hallem, S. Checking system rules using system-specific, programmer-written compiler extensions. In Proceedings of the Proceedings of the 4th conference on Symposium on Operating System Design \& Implementation — Volume 4 (San Diego, California, 2000). USENIX Association, [insert City of Publication],[insert 2000 of Publication]. [7] Flanagan, C. and Abadi, M. Object Types against Races. In Proceedings of the Proceedings of the 10th International Conference on Concurrency Theory (1999). Springer-Verlag, [insert City of Publication],[insert 1999 of Publication]. [8] Flanagan, C. and Freund, S. N. Type-based race detection for Java. In Proceedings of the Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation (Vancouver, British Columbia, Canada, 2000). ACM, [insert City of Publication],[insert 2000 of Publication]. [9] Ghosh, R. H. B. N. S. On the Complexity of Event Ordering for Shared-Memory Parallel Program Execution. International Conference on Parallel Processing1990), II93-II97. [10] Ghosh, R. H. B. N. S. Efficient Race Condition Detection for Shared-Memory Programs with Post/Wait Synchronization. International Conference on Parallel Processing, II1992), 242- 246. [11] Henzinger, T. A., Jhala, R., Majumdar, R., Gr, #233 and Sutre, g. Lazy abstraction. SIGPLAN Not., 37, 1 2002), 58–70. [12] Intel http://software.intel.com/en-us/articles/intelr-parallelinspector-comparison-with-intelr-thread-checker/. [13] O’Callahan, R. and Choi, J.-D. Hybrid dynamic data race detection. SIGPLAN Not., 38, 10 2003), 167–178. [14] Patil, R. V. and George, B. http://msdn.microsoft.com/enus/magazine/cc546569.aspx. [15] Qadeer, S. and Wu, D. KISS: keep it simple and sequential. SIGPLAN Not., 39, 6 2004), 14–24. [16] Savage, S., Burrows, M., Nelson, G., Sobalvarro, P. and Anderson, T. Eraser: a dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst., 15, 4 1997), 391–411.