-
Notifications
You must be signed in to change notification settings - Fork 1
/
LockFreeDataStructure.java
102 lines (85 loc) · 3 KB
/
LockFreeDataStructure.java
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
package com.jyotindersingh;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.LockSupport;
public class LockFreeDataStructure {
public static void main(String[] args) throws InterruptedException {
LockFreeStack<Integer> stack = new LockFreeStack<>();
Random random = new Random();
for (int i = 0; i < 100000; ++i) {
stack.push(random.nextInt());
}
List<Thread> threads = new ArrayList<>();
int pushingThreads = 2;
int poppingThreads = 2;
for (int i = 0; i < pushingThreads; ++i) {
Thread thread = new Thread(() -> {
while (true) {
stack.push(random.nextInt());
}
});
thread.setDaemon(true);
threads.add(thread);
}
for (int i = 0; i < poppingThreads; ++i) {
Thread thread = new Thread(() -> {
while (true) {
stack.pop();
}
});
thread.setDaemon(true);
threads.add(thread);
}
for (Thread thread : threads) {
thread.start();
}
Thread.sleep(10000);
System.out.println(String.format("%,d operations were performed in 10 seconds ", stack.getCounter()));
}
public static class LockFreeStack<T> {
private AtomicReference<StackNode<T>> head = new AtomicReference<>();
private AtomicInteger counter = new AtomicInteger();
public void push(T value) {
StackNode<T> newHeadNode = new StackNode<>(value);
while (true) {
StackNode<T> currentHeadNode = head.get();
newHeadNode.next = currentHeadNode;
if (head.compareAndSet(currentHeadNode, newHeadNode)) {
break;
} else {
LockSupport.parkNanos(1);
}
}
counter.incrementAndGet();
}
public T pop() {
StackNode<T> currentHeadNode = head.get();
StackNode<T> newHeadNode;
while (currentHeadNode != null) {
newHeadNode = currentHeadNode.next;
if (head.compareAndSet(currentHeadNode, newHeadNode)) {
break;
} else {
LockSupport.parkNanos(1);
currentHeadNode = head.get();
}
}
counter.incrementAndGet();
return currentHeadNode != null ? currentHeadNode.value : null;
}
public int getCounter() {
return counter.get();
}
private static class StackNode<T> {
public T value;
public StackNode<T> next;
public StackNode(T value) {
this.value = value;
this.next = next;
}
}
}
}