Hardware Reference
In-Depth Information
executed, as these operations will not result in unintended splitting or movement of
other droplets.
Figure
6.14
b shows the conflict graph derived from the scheduled fluid-handling
operations of droplets shown in Fig.
6.14
a. According to the conflict graph, we can
see that droplets D
1
and D
2
can be moved at time t
D
t
0
, because their fluid-
handling operations will not lead to unintended splitting or movement of other
droplets. Droplets D
3
and D
4
must remain at their current positions.
Deadlock in fluid-handling operations occurs if the manipulation of any droplet
may lead to unintended splitting or movement of one or more other droplets. In
this case, none of the fluid-handling operations can be executed. We can find the
following necessary and sufficient condition for the occurrence of deadlock from
the conflict graph.
Lemma 6.3.
Deadlock occurs at time
t
if and only if all the nodes in the
corresponding conflict graph have non-zero out-degrees.
Proof.
First, assume that deadlock occurs and none of the scheduled fluid-handling
operations can be executed. Hence, executing the operation of an arbitrarily-chosen
droplet D
K
may lead to the unintended splitting or movement for a group of other
droplets
f
D
K
1
;D
K
2
; :::; D
K
n
g
. Based on the definition of edges in the conflict
graph, directed edges will start from the node that represents droplet D
K
and go to
the nodes that represent droplets
f
D
K
1
;D
K
2
; :::; D
K
n
g
. The out-degree of the node
that represents droplet D
K
is non-zero. Since D
K
is an arbitrarily-chosen droplet,
we can conclude that when deadlock occurs, all the nodes in the conflict graphs have
non-zero out-degrees.
t
Next, we prove that Lemma
6.3
provides a sufficient condition for the occurrence
of deadlock. Based on the definition of a directed edge in the conflict graph, if the
out-degree for a node is non-zero, moving the droplet that is represented by the
node may lead to unintended splitting or movement of other droplets. If all the
nodes in the conflict graph have non-zero out-degrees, we can conclude that the
manipulation of any droplet may lead to unintended splitting or movement of other
droplets. Hence the deadlock occurs.
Based on the above argument, the necessity and sufficiency of the condition in
Lemma
6.3
are proven.
When the deadlock occurs, one or more fluid-handling operations need to be re-
scheduled. Here are the details of the re-scheduling procedure. Assume that a set
of operations S
d
is scheduled to be implemented concurrently, and the deadlock
occurs. Then an operation O
R
is randomly selected from S
d
and it is re-scheduled
to be implemented after all the other operations in S
d
are finished. Therefore,
operation O
R
will not have conflicts with any operations in the set S
d
nf
O
R
g
any
more. If the deadlock still exists, then another operation from S
d
nf
O
R
g
is randomly
selected and it is also re-scheduled to be executed after all the other operations are
