Newer
Older
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
package midterm22
import instrumentation.Monitor
import instrumentation.MockedMonitor
import org.junit.*
import org.junit.Assert.*
import instrumentation.*
import java.util.concurrent.atomic.AtomicInteger
class Part4Test:
// This test can result in a deadlock because locks can be called in any
// order. Here, Thread 1 locks Node 3 first and then Node 2, whereas Thread 2
// locks Node 2 first and then Node 3. This will lead to a deadlock.
@Test
def testQuestion9() =
TestUtils.assertDeadlock(
TestHelper.testManySchedules(
2,
scheduler =>
val allNodes = (for i <- 0 to 6 yield ScheduledNode(i, scheduler)).toList
// Shared by all threads
var sum: Int = 0
def increment(e: Int) = sum += e
(
List(
() =>
// Thread 1
var nodes: List[Node] = List(allNodes(1), allNodes(3), allNodes(2), allNodes(4))
nodes = nodes
lockFun(nodes, increment),
() =>
// Thread 2
var nodes: List[Node] = List(allNodes(5), allNodes(2), allNodes(3))
nodes = nodes
lockFun(nodes, increment),
),
results => (true, "")
)
)
)
// This will not lead to a deadlock because the lock acquire happens in a
// particular order. Thread 1 acquires locks in order 1->2->3->4, whereas
// Thread 2 acquires locks in order 2->3->5.
@Test
def testQuestion10() =
TestHelper.testManySchedules(
2,
scheduler =>
val allNodes = (for i <- 0 to 6 yield ScheduledNode(i, scheduler)).toList
// Shared by all threads
var sum: Int = 0
def increment(e: Int) = sum += e
(
List(
() =>
// Thread 1
var nodes: List[Node] = List(allNodes(1), allNodes(3), allNodes(2), allNodes(4))
nodes = nodes.sortWith((x, y) => x.guid > y.guid)
lockFun(nodes, increment),
() =>
// Thread 2
var nodes: List[Node] = List(allNodes(5), allNodes(2), allNodes(3))
nodes = nodes.sortWith((x, y) => x.guid > y.guid)
lockFun(nodes, increment),
),
results => (true, "")
)
)
// This will not lead to a deadlock because the lock acquire happens in a
// particular order. Thread 1 acquires locks in order 4->3->2->1, whereas
// Thread 2 acquires locks in order 5->3->2.
@Test
def testQuestion11() =
TestHelper.testManySchedules(
2,
scheduler =>
val allNodes = (for i <- 0 to 6 yield ScheduledNode(i, scheduler)).toList
// Shared by all threads
var sum: Int = 0
def increment(e: Int) = sum += e
(
List(
() =>
// Thread 1
var nodes: List[Node] = List(allNodes(1), allNodes(3), allNodes(2), allNodes(4))
nodes = nodes.sortWith((x, y) => x.guid < y.guid)
lockFun(nodes, increment),
() =>
// Thread 2
var nodes: List[Node] = List(allNodes(5), allNodes(2), allNodes(3))
nodes = nodes.sortWith((x, y) => x.guid < y.guid)
lockFun(nodes, increment),
),
results => (true, "")
)
)
// This test can result in a deadlock because locks are not called in any
// order. Thread 1 acquire order (3->2->4->1), Thread 2 acquire order
// (2->3->5). Thread 1 locks Node3 first and then Node2, whereas Thread 2
// locks Node 2 first and then Node3. This will lead to a deadlock.
@Test
def testQuestion12() =
TestUtils.assertDeadlock(
TestHelper.testManySchedules(
2,
scheduler =>
val allNodes = (for i <- 0 to 6 yield ScheduledNode(i, scheduler)).toList
// Shared by all threads
var sum: Int = 0
def increment(e: Int) = sum += e
(
List(
() =>
// Thread 1
var nodes: List[Node] = List(allNodes(1), allNodes(3), allNodes(2), allNodes(4))
nodes = nodes.tail.appended(nodes(0))
lockFun(nodes, increment),
() =>
// Thread 2
var nodes: List[Node] = List(allNodes(5), allNodes(2), allNodes(3))
nodes = nodes.tail.appended(nodes(0))
lockFun(nodes, increment),
),
results => (true, "")
)
)
)
// sum returns wrong answer because there is a data race on the sum variable.
@Test(expected = classOf[AssertionError])
def testQuestion13() =
TestHelper.testManySchedules(
2,
scheduler =>
val allNodes = (for i <- 0 to 6 yield ScheduledNode(i, scheduler)).toList
// Shared by all threads
var sum: Int = 0
def increment(e: Int) =
val previousSum = scheduler.exec{sum}("Get sum")
scheduler.exec{sum = previousSum + e}("Write sum")
(
List(
() =>
// Thread 1
var nodes: List[Node] = List(allNodes(1), allNodes(3), allNodes(2), allNodes(4))
nodes = nodes.sortWith((x, y) => x.guid < y.guid)
lockFun(nodes, increment),
() =>
// Thread 2
var nodes: List[Node] = List(allNodes(5), allNodes(2), allNodes(3))
nodes = nodes.sortWith((x, y) => x.guid < y.guid)
lockFun(nodes, increment),
),
results =>
if sum != 20 then
(false, f"Wrong sum: expected 20 but got $sum")
else
(true, "")
)
)
// sum value will be correct here because "sum += e" is protected by a lock.
@Test
def testQuestion14() =
TestHelper.testManySchedules(
2,
sched =>
val allNodes = (for i <- 0 to 6 yield ScheduledNode(i, sched)).toList
val monitor = new MockedMonitor: // Monitor is a type of a lock.
def scheduler = sched
// Shared by all threads
var sum: Int = 0
def increment(e: Int) =
monitor.synchronized { sum += e }
(
List(
() =>
// Thread 1
var nodes: List[Node] = List(allNodes(1), allNodes(3), allNodes(2), allNodes(4))
nodes = nodes.sortWith((x, y) => x.guid < y.guid)
lockFun(nodes, increment),
() =>
// Thread 2
var nodes: List[Node] = List(allNodes(5), allNodes(2), allNodes(3))
nodes = nodes.sortWith((x, y) => x.guid < y.guid)
lockFun(nodes, increment),
),
results =>
if sum != 20 then
(false, f"Wrong sum: expected 20 but got $sum")
else
(true, "")
)
)
// total will give correct output here as it is an atomic instruction.
@Test
def testQuestion15() =
TestHelper.testManySchedules(
2,
sched =>
val allNodes = (for i <- 0 to 6 yield ScheduledNode(i, sched)).toList
// Shared by all threads
var total: AtomicInteger = new AtomicInteger(0)
def increment(e: Int) =
total.addAndGet(e)
(
List(
() =>
// Thread 1
var nodes: List[Node] = List(allNodes(1), allNodes(3), allNodes(2), allNodes(4))
nodes = nodes.sortWith((x, y) => x.guid < y.guid)
lockFun(nodes, increment),
() =>
// Thread 2
var nodes: List[Node] = List(allNodes(5), allNodes(2), allNodes(3))
nodes = nodes.sortWith((x, y) => x.guid < y.guid)
lockFun(nodes, increment),
),
results =>
if total.get != 20 then
(false, f"Wrong total: expected 20 but got $total")
else
(true, "")
)
)
class ScheduledNode(value: Int, val scheduler: Scheduler) extends Node(value) with MockedMonitor