summaryrefslogtreecommitdiff
path: root/ACE/netsvcs/clients/Tokens/deadlock/README
blob: 829963e64bf5707e52262436eb7eee30ee9ab7d2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
$Id$

deadlock_detection_test

This example contains two deadlock tests, mutex and rwlock tests.
% ./deadlock_detection_test -u
./deadlock_detection_test:
[-r test readers/writer locks]
[-n <iterations>]
[-h <remote host>]
[-p <remote port>]
[-i ignore deadlock]

For both mutex and rwlock tests, -h and -p specify to use remote
mutexes.  -i specifies to ignore deadlock.  -n is repetitions through
the respective algorithms (default 100).  Both tests also use Token
Invariants to ensure correctness of the mutexes and readers/writer
locks.

------------------------------------------------------------

If you run ./deadlock_detection_test without -r, then the following
mutex test is run.

The mutex test spawns two threads which attempt to deadlock.
Logically, there are two tokens A and B.  Here is what both threads
try to do:

Thread 1		Thread 2
--------		--------
Repeat 100 times	Repeat 100 times
  acquire A		  acquire B
  acquire B		  acquire A
  release A and B	  release A and B
repeat			repeat

Notice that A and B are reversed in 1 and 2.  If the token manager
(which is not in the public interface, but hidden behind
ACE_Local_Mutex) works properly, they should detect the deadlock.  If
a thread detects deadlock, the resources held are released, and it
starts the whole process over again.

What can be confusing about the test program is all the other tricks
I'm pulling to test other aspects of the library.  For instance, I'm
using both "global" and "local" ACE_Local_Mutexes.  This is to test
the ability to have multiple threads using one token proxy as well as
multiple threads each using their own proxies.  All the while, the
same logical token is being used.  If this doesn't make sense, don't
worry about it.  Just use the ACE_Local_Mutex any way you want.

Another confusing trick is that I'm testing recursive acquisition.
(Two acquires in a row.)  I have to make sure that the token manager
doesn't detect a recursive acquire as deadlock.

To run a test, simply type:
% ./deadlock_detection_test

This should run 100 times through the above pseudo code.  If the
application halts, then we have trouble.  It should never ever halt.
I've included a little flag with the ACE_Local_Mutex class to allow
deadlock detection to be ignored.  So, if you run the test as follows,
deadlock detection will be ignored.

% ./deadlock_detection_test -i

In this case, the application should only run about a second before
deadlock occurs and the application halts.  This is good.

------------------------------------------------------------

If you run ./deadlock_detection_test *with* -r, then the following
rwlock test is run:

There are four tokens and four threads in the rwlock test.  The
readers/writer tokens are:

reader first
writer first 1
writer first 2
writer first 3

There are three reader threads that only acquire reader locks on the
above tokens.  Each of the reader threads first acquire "reader first"
and then one "writer first <tid>" (where <tid> is the corresponding
thread's id).  So reader thread 1 acquires "reader first" and then
"writer first 1".

There is a single writer thread that uses the following algorithm:

repeat 100
  acquire "writer first 1"
  acquire "reader first"
  acquire "writer first 2"
  acquire "reader first"
  acquire "writer first 3"
  acquire "reader first"

This strange mix of readers and writer create an interesting graph of
tokens that the deadlock detection algorithm must traverse.