ABSTRACT

We present a unique approach for communication deadlock analysis for actor-model which has an under-approximated analysis result. Our analysis detects narrowly defined communication deadlocks by finding a cyclic dependency relation in a novel dependency graph called the slave dependency graph. The slave dependency graph is based on a new relationship between Actors, slave dependency, defined by us. After that, we implement this theory in Soot, an analysis tool for Java, and use it to analyze actor-based Java program realized by Akka, a Java library that allows actor-based programming. We argue that our analysis can detect a specific kind of communication deadlock with the precise result, but has many limitations.

Keywords:

Actor Model, Communication Deadlock, Program Analysis, Akka, Soot, Dependency Graph

1. Introduction

Deadlock detection in concurrency programs is a well-studied topic. Although most of those studies focus on the traditional thread-based concurrency model, some studies still have significant influences on us so that we decided to bring their ideas into our own study. Flores-Montoya et al. [1] present an analysis that finds deadlocks in concurrency programs through dependency graph construction as the deadlock situation occurs when the dependency graph contains a circle. A. von Mayrhauser et al. [2] have also used the approach of Control-and-Communication Flow analysis to develop an algorithm that can detect communication deadlock in codes written in Ada, which is also a concurrency language. Their research, however, focuses on an algorithm that is capable of doing automated and efficient re-analysis after changes in the Ada code. J-L. Colaço et al. [3] present an analysis based on the type inference model for a primitive actor calculus to handle the situation of “orphan messages”, the messages received by actors while never being processed. This analysis is important in detecting communication deadlock, since orphan message is one of the causes of communication deadlock. Maria Christakis and Konstantinos Sagonas [4] propose a static analysis that could detect both Communication deadlock and Behavioral deadlock in the Erlang language. The analysis detects deadlocks by generating a control flow graph and finds whether the graph is a closed figure or not. If the graph is not closed, the whole program is considered to have a deadlock. This approach is by far one of the best approaches for detecting deadlocks, and it has demonstrated its feasibility by finding communication deadlocks in some open source libraries.

According to the definitions of behavioral deadlock and livelock, there is a wide variety of causes of these kinds of deadlocks; hence, it is hard for researchers to specify them and think of a general solution, resulting in little progress on analyzing these kinds of deadlocks. Therefore, the studies on communication deadlock are relatively more common, which make it easier for us to learn about and do some research on this topic. However, as we dive deep into the field of communication deadlock analysis for actor models, we find that there are a lot more theoretic studies than practical implementation of theories on finding communication deadlock. As a result, we develop a novel approach involving a “Slave Graph” (based on changes to an existing approach), for finding communication deadlock in an Actor System. After that, we implement our analysis theory and use an analysis tool, Soot, to look for communication deadlocks in a certain actor-based programming toolkit in Java, Akka, by checking the definition statements of specific actor classes inside the program being analyzed.

In this paper, we will be focusing on creating and testing a novel approach in finding communication deadlocks. The first part of this paper is about the introduction of the specific type of communication deadlock, “restricted communication deadlock” and the method of detecting it. In the rest of our paper, we put this method into actor-based-system tests, which we carefully projected, and evaluate it by discussing its advantages and disadvantages according to the test results.

2. Definition and Background Information

Actors are isolated concurrent entities that communicate through asynchronous messages and do not share state [5] . An actor responds to an incoming message by generating a finite set of communications sent to other actors, a new behavior (which will govern the response to the next communication processed) and a finite set of new actors created [6] . The actor-based concurrency model is generally seen as an enhancement on the current thread-based concurrency model. Since actors can only interact with each other through the mean of message exchange, the states of each actor could only be subjected to mutation from itself, unlike how multiple thread can access the same process in the thread model. This means that the actor model is an effective solution to common problems in multi-thread program, such as data race conditions as well as deadlocks. However, thoughtless design of algorithms using the actor model is still possible to result in deadlocks [5] .

Soot is a static program analysis framework developed by the Sable Research Group at McGill University. It processes Java code into a 3-address intermediate language called “Jimple”, which is suitable for static analysis. The modules in Soot support intraprocedural and interprocedural analysis, point-to analysis, def/use chain, and graph construction, but the users can also create their own analysis, like communication deadlock analysis in this research, based on the framework. Since Java by default does not support actor model concurrency, the programs we analyze in this research are Java codes written in Akka framework. Akka is an open-source toolkit developed by Lightbend that provide support for actor-model concurrency in both Java and Scala.

A communication deadlock is a condition in a system where two or more actors are blocked forever waiting for each other to do something. This condition is similar to traditional deadlocks known from thread-based programs [5] . However, we have a more specific situation of communication deadlock to analyze and have to narrow its definition. In our research, restricted communication deadlock occurs when two or more actors don’t send messages that are required by another actor and only declared by themselves, so that the actor system reaches a state that each actor in the actor system is waiting for another actor to send its message. An example of PingPong is given in Figure 1.

In Figure 1, Actor Ping and Pong both have the messages that are required by each other: Ping needs Pong_msg and Pong needs Ping_msg. However, neither of them will send those messages. Instead, they send “ok”. Hence, they reach a state of waiting for each other to send messages in line 2, which becomes a situation of restricted communication deadlock.

3. Development of Analysis Theory

3.1. Derivation from Dependency Graph

As we read through papers about finding communication deadlocks, we found a simple way to spot deadlocks, which is from the work of Flores-Montoya’s team. They created a kind of state dependency graph G_S and state the definition of deadlock as following:

A program state S is deadlock if and only if when its dependency graph G_S contains a cycle [6] .

However, we misunderstood the definition of “dependency graph G_S”, and went straight into the wrong direction of looking for cycles in data dependency and control dependency graphs. In fact, G_S is actually built upon nodes like objects and task identifiers and whose edges are defined between objects and tasks, which is dramatically different from our work based on data dependency and control dependency graph.

At last, we found it couldn’t solve restricted communication deadlock and decided to take its idea of finding cycles in a kind of dependency graph and built our own dependency graph.

3.2. Slave Dependency Graph

3.2.1. Semantics

This section presents the semantics of actor-based language:

An Actor System S is a set S = Actors where Actors is the set of all created Actors.

An Actor is a term $A\left(a\mathrm{,}M\mathrm{,}RT\langle msg\mathrm{,}t\rangle \right)$ where a is the Actor identifier, M is the set of all messages created within the Actor, $RT\langle msg\mathrm{,}t\rangle$ is the set of all pairs of the message received and the message sent consequently, in which msg means the message received by this Actor and t means the message sent back by this Actor in response to the message it receives.

3.2.2. Definitions

Slave Dependency Relationship:

Given two Actors A₁ and A₂, we define their slave dependency relationship, A₁ is slave dependent on A₂ as follows:

$A_1\left(a_1\mathrm{,}MS{G}_1\mathrm{,}R{T}_1\langle msg\mathrm{,}{t}_1\rangle \right)$

$A_2\left(a_2\mathrm{,}MS{G}_2\mathrm{,}R{T}_2\langle msg\mathrm{,}{t}_2\rangle \right)$

$\frac{\exists x\mathrm{,}R{T}_1\left[x\right]\cdot msg\in MS{G}_2\wedge \exists y\mathrm{,}R{T}_2\left[y\right]\cdot msg\in MS{G}_1\wedge \forall z\mathrm{,}R{T}_2\left[y\right]\cdot t_2\ne R{T}_1\left[z\right]\cdot msg}{A_1\to A_2}$

This type of relation corresponds to the situation when A₁ wants A₂ message and sends itself’s message to A₂ whereas A₂ receives the message from A₁ and doesn’t send back its message.

Specifically speaking, this definition of slave dependency relationship has three premises: $\exists x\mathrm{,}R{T}_1\left[x\right]\cdot msg\in MS{G}_2$ , $\exists y\mathrm{,}R{T}_2\left[y\right]\cdot msg\in MS{G}_1$ and $\forall z\mathrm{,}R{T}_2\left[y\right]\cdot t_2\ne R{T}_1\left[z\right]\cdot msg$ . I will explain each of them explicitly. The first premise is $\exists x\mathrm{,}R{T}_1\left[x\right]\cdot msg\in MS{G}_2$ , which means there exists a message possessed by A₁ and required by A₂. The second premise is $\exists y\mathrm{,}R{T}_2\left[y\right]\cdot msg\in MS{G}_1$ , similar to the previous one, which means there exists a message possessed by A₂ and required by A₁. The third premise is $\forall z\mathrm{,}R{T}_2\left[y\right]\cdot t_2\ne R{T}_1\left[z\right]\cdot msg$ , which means that when A₂ receives the required message from A₁, it doesn’t send back any message required by A₁. In this situation, the slave dependency that A₁ is “slave-dependent” on A₂ establishes.

Slave Dependency Graph:

Given an Actor System S = Actors, we define its slave dependency graph G_S whose nodes are the existing Actors and whose edges are slave dependency relationship defined above.

Restricted Communication deadlock:

An Actor System S has a restricted communication deadlock iff its slave dependency graph contains a cycle.

Singhal [7] defines that a resource deadlock is a set of processes in a state where each process in the set requests a resource held by another process in the set and a communication deadlock is in a similar situation whereas each process requires and waits for messages instead of resources. It is a situation alike in restricted communication deadlock in an Actor System, where each slave-dependent Aactor awaits the message to be sent by the owner in a slave dependent relationship. Therefore, to achieve the state where every actor is restricted-communication-deadlocked, each of the Actors in the system needs to be slave dependent on anther, which consequently leads to a circle in slave dependency graph.

An example could be PingPong mentioned in the background information, in which PingPong can be expressed as follows:

$A_{Ping}\left(Ping\mathrm{,}\left\{Ping\mathrm{<mo>\; \_\; </mo>}msg\right\}\mathrm{,}\left\{\langle Pong\mathrm{<mo>\; \_\; </mo>}msg\mathrm{,}“ok”\rangle \right\}\right)$

$A_{Pong}\left(Pong\mathrm{,}\left\{Pong\mathrm{<mo>\; \_\; </mo>}msg\right\}\mathrm{,}\left\{\langle Ping\mathrm{<mo>\; \_\; </mo>}msg\mathrm{,}“ok”\rangle \right\}\right)$

Hence,

$\frac{Pon{g}_{msg}=Pon{g}_{msg}\wedge Pin{g}_{msg}=Pin{g}_{msg}\wedge “ok”\ne Pon{g}_{msg}}{A_{Ping}\to A_{Pong}}$

$\frac{Pin{g}_{msg}=Pin{g}_{msg}\wedge Pon{g}_{msg}=Pon{g}_{msg}\wedge “ok”\ne Pin{g}_{msg}}{A_{Pong}\to A_{Ping}}$

3.3. Slave Chain

After we generate a slave dependency graph for the actor model program, another algorithm will verify if the slave dependency graph has a cycle. Since the dependency graph is a collection of pairs of Actors in slave dependent relationship and we want to find a cycle in the graph, we merge these pairs into a chain called “Slave chain”. Here, we consider these pairs as a short chain of two Actors. We merge the Slave Chain with the next short chain iff the tail of the Slave Chain equals the head of the next one. After all the possible merges are finished, we look at the final product of Slave Chain. If the head of the Slave Chain equals its tail, which means the Actors in the chain are in a cyclic slave dependency relationship, we consider that the Actors in this chain are in a restricted communication deadlock.

For example in slave dependency graph G_S:

$A\to BB\to CC\to A$

G_S contains a restricted communication deadlock. As B is the tail of the first pair as well as the head of the second pair, we merge them into a Slave Chain:

$A\to B\to CC\to A$

We then merge the slave chain and the next pair for the same reason:

$A\to B\to C\to A$

Since the final Slave Chain $A\to B\to C\to A$ has its head and tail the same Actor A, and according to the theory above, the Actors in the chain, $A\mathrm{,}B\mathrm{,}C$ , are in the state of restricted communication deadlock.

Continue, using the example of PingPong, as we have determined their slave dependency relationship: $A_{Ping}\to A_{Pong}\mathrm{,}{A}_{Pong}\to A_{Ping}$ , we find that the Actor at the tail of the first chain is also at the head of the second one. We then merge them together into $A_{Ping}\to A_{Pong}\to A_{Ping}$ . Since the head is also the tail in this chain, we conclude that the Actors $A_{Ping}$ and $A_{Pong}$ are in restricted communication deadlock.

4. Implementation of the Analysis Theory

4.1. Pseudocode of Analysis Program

Illustrated by Algorithm 1, internal Transform() is automatically executed by Soot, extracting statements within a class. In our implementation, we turn Soot to whole-program mode, so that Soot can exact statements from every class of Actors.

1) In line 1, we transform every line of code being analyzed into a statement by using Soot. We then store them in a list for further analysis.

2) In line 2, Statement Sequence is a set of consecutive statements in a program.

3) In line 3, we use the pattern we found from the source code of .match() function. As long as Statement Sequence match this pattern, we can determine Actor’s name and the receiving and sending of an actor, where the Actor’s name is after @this, the sending message is after @parameter0 and receive message is after new.

For example, the output of Soot shows the source code of Actor Celcius:

4) In line 4, we add the receiving message and sending message pair to RecvSendMapping, which is a list of pairs describing how the Actor will react to the incoming message. ActorGraph is a data structure generally describing the characteristic of an Actor, which is a class contains Actor’s’ name and RecvSendMapping.

5) In line 6, we also found a pattern to make sure we can find all of the receiving messages whether it sends the correct message or not. Here the predication means the Actor doesn’t send the right message.

6) In line 7, we do the similar thing in line 4, whereas we add null to its send message.

Illustrated by Algorithm 2, findDependency() is the method that search among slave dependency graph and reports restricted communication deadlocks. It is executed only once.

1) In line 1, we find all of the Actors by finding keyword new and AbstractActor, and store them into corresponding created ActorGraph. graphList is a list of all ActorGraph in the Actor System.

2) In line 2, we store RecvSendMapping in corresponding ActorGraph.

3) In lines 3-11, we check if the two Actors are in slave dependent relationship and add them to slaveDependency in a pair. slaveDependency is a list of pairs in which the key of the pair is the slave Actor and the value is the master Actor.

4) In line 13, we create a list interval to store the Actors being merged.

5) In line 15, we add the interval Actor to interval.

6) In line 16 we add the merged slave chain to slaveChains. slaveChains is a collection of pairs describing a series of Actors that are in slave dependency relationship.

7) In line 19-23, if we eventually get a Pair in slaveChians that has Pair(a,a), which means a circle in our slave dependency graph, the program will report an error by showing all the Actors in this chain are in the state of restricted communication deadlock.

4.2. Restrictions

For the above analysis to be employed in an actor model program, the program must satisfy two restrictions:

Restriction 1:

The message must be sent by the Actor that it is belonged to. Although in Akka, messages can technically be sent by Actors that does not own that particular message. However, since we couldn’t find the right code showing the receiving message is sent by which Actor, we have to restrict the message being sent. If a message can only be sent by one Actor, it is much easier for us to trace back where the message is from.

Restriction 2:

In each method match() of an Actor class, there is only one tell() function, whose caller of must be sender(). If there are multiple tell functions, no matter who the receiver is, we shall assume an Actor with two sender.tell(a). If the sender can reply to a, and the message it sent can also be replied by the first Actor, then it will do the two sender.tell(a) twice, because it received the same message twice. Thus, the Actor’s reply of the sender would increase exponentially with a base of two in this simplest base case. It would soon cause the entire program to go into a chaos either because of an infinite loop or recursion. It would be meaningless to write such codes in an Actor. Secondly, if we assume an Actor has a tell method with a caller “A”, where A can react to the kind of message the Actor sent—it still can’t imply that the message the Actor sent is strictly owned by itself. If we cannot identify it, we will not be sure whether the Actor A is dependent on the first Actor or the actual owner of the message or actually. Hence, it is also a meaningless piece of code.

4.3. Test Cases

Test Case 1:

Test Case 2:

Test Case 3:

Test Case 4:

Test Case 5:

The above Figure 2, Figure 4, Figure 6, Figure 8, Figure 10 illustrate the test cases which are used to test our implemented program, shown by Algorithm 1, Algorithm 2. Figure 3, Figure 5, Figure 7, Figure 9, Figure 11 depict the slave dependent relationship within the test cases for better understanding. We perform the analysis of the test cases each for 20 trails to test the stability of our test program’s performance and get the following table. From Table 1, we find that the accuracy of finding errors decreases as the number of Actors increases in the Actor System.

5. Related Work and Conclusions

Among all the related works, Flores-Montoya et al. [1] present an analysis that finds deadlocks in concurrency programs through dependency graph construction, and the deadlock situation occurs when the dependency graph contains a circle. Although our analysis also looks for deadlocks by finding a cyclic relation in a graph, we use a different graph, Slave Dependency Graph. On the other hand, the work of Flores Montoya et al. pays more attention to the thread-based concurrency programs. For A. von Mayrhauser et al. [2] , their research, however, focuses on an algorithm that is capable of doing automated and efficient re-analysis after changes in the Ada code. Although this kind of algorithm is extremely useful in the setting of project maintenance, its focus on changes in the existing code and their impact is significantly different from our goal of detecting communication deadlock in the scope of the entire project. Although J-L. Colaço et al.’s work [3] directly relates to communication deadlock detection in actor model programs, their static detection algorithm in the paper could not detect all of the possible orphan messages, and the assist of dynamic detection still requires the locations of the remaining orphan messages. Maria Christakis and Konstantinos Sagonas’ work [4] is by far one of the best approaches for detecting deadlocks, and it has demonstrated its feasibility by finding communication deadlocks in some open source libraries. However, the approach we use is a more unique one.

We develop a novel dependency graph, slave dependency graph, in which we can find restricted communication deadlocks of an actor-based program, and demonstrate the algorithm’s feasibility by the implementation of building an analysis program. The analysis program can detect a specific kind of restricted communication deadlock in an actor-based Java program with Akka toolkit.

There are two limitations in our research. The first one is about the imperfect precision of our analysis program. According to Table 1, we can see as the number of Actors in an Actor System increases, the percentage of failing report increases notably. This is due to the internalTransform() method provided by Soot, which extracts the key information of an Actor from the Java source code. It seems this method is run in multi-threaded for analyzing all actor classes, which may cause the pattern we found fails to construct ActorGraph with right information. Thus, the analysis program cannot report all the restricted communication deadlocks correctly from time to time. According to the test result, we believe the percentage of failing report would increase significantly, and we would have a smaller possibility to identify all the restricted communication deadlocks in a huge Actor System. Therefore, our analysis program is more suitable for small Actor System. The second limitation is due to our narrow definition of restricted communication deadlock. Since we have such a strict definition for restricted communication deadlock, the slave dependency relationship ignores situations. For example, an Actor receives a message and sends its message to another Actor. This restriction of definition makes our program only able to perform a limit under-approximation analysis of communication deadlock in an Actor System.

Authors Contribution

Among all the contribution of our work, Yupeng Xi initiated this research, designed the semantics and the theoretical approaches, analyze the test results, wrote most of the paper and coordinated the whole research process; Jianrui Zhang implement the theoretical approach by writing most of the deadlock-detecting program as well as the test cases; Furi Xiang gathered the information the paper required and did the whole analysis of existing related studies.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Xi, Y.P., Zhang, J.R. and Xiang, F.R. (2019) The Implementation of a Communication Deadlock Analysis Based on the Theory of Deadlock Analysis for the Actor Model. Journal of Software Engineering and Applications, 12, 393-405. https://doi.org/10.4236/jsea.2019.1210024

References