FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
elimination-backoff-stack.java/Main.java at master · moocf/elimination-backoff-stack.java · GitHub
Uh oh!
There was an error while loading.
Please reload this page
.
moocf
/
elimination-backoff-stack.java
Public
Notifications
You must be signed in to change notification settings
Fork
1
Star
2
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
elimination-backoff-stack.java
/
Main.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
102 lines (95 loc) · 2.75 KB
Breadcrumbs
elimination-backoff-stack.java
/
Main.java
Copy path
File metadata and controls
102 lines (95 loc) · 2.75 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
import
java
.
util
.*;
class
Main
{
static
Deque
<
Integer
>
stack
;
static
EliminationBackoffStack
<
Integer
>
concurrentStack
;
static
List
<
Integer
>[]
poppedValues
;
static
int
TH
=
10
,
NUM
=
1000
;
// Each unsafe thread pushes N numbers and pops N, adding
// them to its own poppedValues for checking; using Java's
// sequential stack implementation, ArrayDeque.
static
Thread
unsafe
(
int
id
,
int
x
,
int
N
) {
return
new
Thread
(() -> {
String
action
=
"push"
;
try
{
for
(
int
i
=
0
,
y
=
x
;
i
<
N
;
i
++)
stack
.
push
(
y
++);
Thread
.
sleep
(
1000
);
action
=
"pop"
;
for
(
int
i
=
0
;
i
<
N
;
i
++)
poppedValues
[
id
].
add
(
stack
.
pop
());
}
catch
(
Exception
e
) {
log
(
id
+
": failed "
+
action
); }
});
}
// Each safe thread pushes N numbers and pops N, adding
// them to its own poppedValues for checking; using
// BackoffStack.
static
Thread
safe
(
int
id
,
int
x
,
int
N
) {
return
new
Thread
(() -> {
String
action
=
"push"
;
try
{
for
(
int
i
=
0
,
y
=
x
;
i
<
N
;
i
++)
concurrentStack
.
push
(
y
++);
Thread
.
sleep
(
1000
);
action
=
"pop"
;
for
(
int
i
=
0
;
i
<
N
;
i
++)
poppedValues
[
id
].
add
(
concurrentStack
.
pop
());
}
catch
(
Exception
e
) {
log
(
id
+
": failed "
+
action
); }
});
}
// Checks if each thread popped N values, and they are
// globally unique.
static
boolean
wasLIFO
(
int
N
) {
Set
<
Integer
>
set
=
new
HashSet
<>();
boolean
passed
=
true
;
for
(
int
i
=
0
;
i
<
TH
;
i
++) {
int
n
=
poppedValues
[
i
].
size
();
if
(
n
!=
N
) {
log
(
i
+
": popped "
+
n
+
"/"
+
N
+
" values"
);
passed
=
false
;
}
for
(
Integer
x
:
poppedValues
[
i
])
if
(
set
.
contains
(
x
)) {
log
(
i
+
": has duplicate value "
+
x
);
passed
=
false
;
}
set
.
addAll
(
poppedValues
[
i
]);
}
return
passed
;
}
@
SuppressWarnings
(
"unchecked"
)
static
void
testThreads
(
boolean
backoff
) {
stack
=
new
ArrayDeque
<>();
concurrentStack
=
new
EliminationBackoffStack
<>();
poppedValues
=
new
List
[
TH
];
for
(
int
i
=
0
;
i
<
TH
;
i
++)
poppedValues
[
i
] =
new
ArrayList
<>();
Thread
[]
threads
=
new
Thread
[
TH
];
for
(
int
i
=
0
;
i
<
TH
;
i
++) {
threads
[
i
] =
backoff
?
safe
(
i
,
i
*
NUM
,
NUM
) :
unsafe
(
i
,
i
*
NUM
,
NUM
);
threads
[
i
].
start
();
}
try
{
for
(
int
i
=
0
;
i
<
TH
;
i
++)
threads
[
i
].
join
();
}
catch
(
Exception
e
) {}
}
public
static
void
main
(
String
[]
args
) {
log
(
"Starting "
+
TH
+
" threads with sequential stack"
);
testThreads
(
false
);
log
(
"Was LIFO? "
+
wasLIFO
(
NUM
));
log
(
""
);
String
name
=
"elimination backoff stack"
;
log
(
"Starting "
+
TH
+
" threads with "
+
name
);
testThreads
(
true
);
log
(
"Was LIFO? "
+
wasLIFO
(
NUM
));
log
(
""
);
}
static
void
log
(
String
x
) {
System
.
out
.
println
(
x
);
}
}
Back
|
FazBrowse Home
|
New Git URL