# On-the-Fly Repairing of Atomicity Violations in ARINC 653 Software
## 3 Related Work
### General-Purpose Platform  
Atomicity violations have been around for a long time in general-purpose platforms that we often use. The occurrence information of atomicity violations is shared among developers through each software's bug report. This information provides valuable patterns (or types) for research on on-the-fly repair approaches [36; 37; 38] to prevent system failure during operation. Since there is a wealth of information on atomicity violations in the bug report, most of the on-the-fly repairing research studies have been conducted on general-purpose platforms. It has to be noted that airborne software is hard real-time software. However, the software of a general-purpose platform does not require hard real-time. Considering the accuracy and overhead of existing research studies performed on a general-purpose platform, the method by [PERSON] et al. [36] and AI (anticipate invariant) [37] are suitable for use in real-time systems. These two research studies are similar in terms of the methods for diagnosing errors using the pre-test information and treating errors by stalling the thread where the error is diagnosed. [PERSON] et al. [36] defined the order of each static memory operation in a data structure as \(PSet\) (predecessor set). The collection conditions of \(PSet\) are as follows: (1) When there are two static memory operations, \(P\) and \(M\), at least one between \(P\) and \(M\) is a write access; (2) \(P\) and \(M\) are executed in two different threads; (3) \(M\) is executed immediately after \(P\) is executed. AI [37] defines the order for each static instruction as \(BSet\) (belonging set). The \(BSet\) collects static instructions (\(S_{x}\)) that satisfy the following conditions based on a dynamic instruction (\(D_{x}\)): (1) It accesses the same address as \(D_{x}\); (2) it is executed in another thread, to which \(D_{x}\) does not belong; (3) \(S_{x}\), accessed just before \(D_{x}\), is executed and stored. The methods of these two research studies are similar in that they store access information from different threads. However, [PERSON] et al. [36]'s method does not store access information in \(PSet\) if the previous access was executed in the same thread. On the other hand, AI stores the access information executed in a different thread even if the previous access was executed in the same thread. This difference makes the coverage of errors that AI can repair larger than that of [PERSON] et al. 's method. Figure 2 shows two types of interleaving that can occur in Figure 1. In Figure 1, the developer would have intended _instance_\(++\) to be executed atomically, as shown in Figure 2a. If this program is correctly executed in the testing phase, as shown in Figure 2a, since only read access \(R3\) of _thread_2 satisfies the collection condition of \(PSet\), the \(PSet\) corresponding to this interleaving is stored as a correct interleaving in Figure 2c. This interleaving information is used when diagnosing the occurrence of atomicity violations in comparison with actual interleaving in the operation phase. Figure 2b is the interleaving of atomicity violations that may occur in this program. If this program is incorrectly executed in the operation phase, as shown in Figure 2b, \(PSet\) is collected as shown in the atomicity violation of Figure 2c. If the actual execution is as shown in Figure 2b, [PERSON] et al. 's method repairs the atomicity violation using the following steps: First, when read access \(R1\) of _thread_1 executes, it is compared with the \(PSet(R1)\) of the correct interleaving and the \(PSet(R1)\) of the actual interleaving are the same. Next, when the read access \(R3\) of _thread_2 executes, it is compared with the \(PSet(R3)\) of the correct interleaving. It is diagnosed as an error, since the \(PSet(R3)\) of the correct interleaving and the \(PSet(R3)\) of the actual interleaving are different. At this time, [PERSON] et al.