# Deadlocks Detection in Multithreaded Applications Based on Source Code Analysis
## 5 Deadlock  
For a deadlock to occur, four conditions must be met. The conditions can be found in operating system manuals [3] as well as in scientific papers [15]:  
1. Mutual exclusion: At least one resource must be non-shareable; that is, only one process can use this resource at a time. If another process requests access to the resource, it must be delayed until the resource is released. 2. Hold and wait: There must be a process that has been allocated at least one resource, and that is awaiting the allocation of an additional resource that is being held by another process. 3. No preemption: Resources are not subject to preemption, which means that a resource can only be released on the initiative of the holding process after the process has ended. 4. Circular wait: There must be set \(P_{0},P_{1},...,P_{n}\) of waiting processes, such that \(P_{0}\) is waiting for the resource held by \(P_{1}\). \(P_{1}\) is waiting for the resource held by \(P_{2},...,P_{n-1}\) is waiting for the resource held by \(P_{n}\), and \(P_{n}\) waiting for the resource held by \(P_{0}\) process. The above necessary condition has the annotation that all four conditions must be met for a deadlock to occur. It was also noted that the circular wait condition implies the hold and wait condition, so these four conditions are not completely independent. The deadlock phenomenon very often occurs as a result of the programmer's actions when he tries to prevent resource conflicts that cause the phenomena of a race condition and atomicity violation [16; 17]. The word deadlock is most often understood as a resource deadlock. There are four scenarios in which the phenomenon of deadlock may occur through (sources can be found at [[https://github.com/PKPhdDG/deadlock_examples](https://github.com/PKPhdDG/deadlock_examples)]([https://github.com/PKPhdDG/deadlock_examples](https://github.com/PKPhdDG/deadlock_examples))):  
1. mutually exclusive lock pairs (application implementing S1 scenario, let it be called DL0),
2. missing the unlocking operation, e.g., as a result of a control instruction (application implementing the S2 scenario, let it be called DL1),3. retrying the lock as a result of: 1. loop operation (application implementing the S3 scenario, let it be called DL2), 2. recursive function call (application implementing the S4 scenario, let it be called DL3). The condition of the deadlock phenomenon in the scenario implemented in the DL0 application code is the appropriate point in time. If the operating system scheduler runs threads at the same time (or the time difference between the runs is insignificant) and both threads put locks at the same time, mutual waiting occurs, and deadlock occurs. The condition of deadlock in the source code of DL1 and DL2 applications are the appropriate input data. It depends on the values given by the user, how the application will look like, and whether these values will lead to the fulfilment of the condition, which in turn will lead to deadlock. A deadlock in the DL3 application always occurs when the lock used in the recursively called code is of a different type than PMR. Figures 1 and 2 present four scenarios in which the phenomenon of deadlock may occur. Scenarios from Figure 1 were considered in several papers [16; 17], including those regarding the automatic fixing of errors related to atomicity violation. The AFix and Axis tools described there can automatically remove the atomicity violation without introducing new conflicts that could lead to a deadlock. Figure 1: Deadlock scenarios using one lock. Source [16]. Figure 2: Scenario 1 (S1): deadlocks due to mutually exclusive locking pairs. The proposed source code model of a multithreaded application is designed to enable detection of resource conflicts that cause these phenomena faster than other methods, by performing only static source code analysis. This approach is faster than the method used in the CTrigger tool.