Asp Forum - LockFree SelfOrganizing List Opinion needed about correctness

moriczsandor.s

4/20/2016 7:49:00 AM

Hi I created a Lock Free SelfOrganizing List and I was wondering if any of you could give me an opinion about the implementation or how i could improve it. I used AtomicStampedReference to mark the different operations (add, remove, search).

All suggestions or welcome.
Thanks

It is available on github as well:
https://github.com/moricz/LockFreeAndLocked/tree/master/main/jav...

package lockfree.selfOrganizing;

import java.util.concurrent.atomic.AtomicStampedReference;

import common.interfaces.SelfOrganizingListInterface;
import lockfree.base.Node;

public class SelfOrgList implements SelfOrganizingListInterface<Node> {

private final int NONE = 0;
private final int ADD = 1;
private final int SEARCH = 2;
private final int STOPSEARCH = 5;
private final int REMOVE = 3;
private final int STOPREMOVE = 6;

public AtomicStampedReference<Node> head;
public AtomicStampedReference<Node> tail;

public SelfOrgList() {
head = new AtomicStampedReference<Node>(new Node(Node.INIT_INT, null), 0);
tail = new AtomicStampedReference<Node>(new Node(Node.INIT_INT, head.getReference()), 0);
}

/*
* (non-Javadoc)
*
* @see lockfree.selfOrganizing.SelfOrganizingListInterface#add(int) get to
* tail and insert element
*/
public boolean add(int value) {

AtomicStampedReference<Node> current = head;
AtomicStampedReference<Node> next = current.getReference().next;

back: while (true) {
// next is the tail
if (next.getReference() == null) {
// element before tail is not stamped
if (current.getStamp() != NONE)
continue back;

// stamp tail
if (next.attemptStamp(null, ADD)) {
// place new node with value to tail
if (next.compareAndSet(null, new Node(value, null), ADD, NONE))
return true;
}

continue back;
}

current = next;
next = next.getReference().next;

}

}
/*
*
* (non-Javadoc)
*
* @see lockfree.selfOrganizing.SelfOrganizingListInterface#remove(int)
*
* we have in the list -> first -> second -> third-> -> first -> third ->
*/

public boolean remove(int value) {
again: while (true) {
AtomicStampedReference<Node> first = head;
AtomicStampedReference<Node> second = first.getReference().next;
AtomicStampedReference<Node> third = second.getReference().next;

while (true) {

Node oldFirst = first.getReference();
Node oldSecond = second.getReference();

// if the removable node is the second element
if (second.getReference().getValue() == value) {
// if the mask is not stamped by others
if (first.getStamp() != NONE && second.getStamp() != NONE && third.getStamp() != NONE)
continue again;

// try stamp to begin removal
if (first.attemptStamp(oldFirst, STOPREMOVE) && second.attemptStamp(oldSecond, REMOVE)
&& third.attemptStamp(oldSecond.next(), STOPREMOVE)) {

/*
* create new node with value of first and next
* reference of second to replace the first node
*/

Node afterRemove = new Node(oldFirst.getValue(), oldSecond.next());

// replace the node
if (first.compareAndSet(oldFirst, afterRemove, STOPREMOVE, NONE))
return true;
}
} else {
if (third.getReference() == null)
return false;

first = second;
second = third;
third = third.getReference().next;
}
}

}
}

public Node search(int value) {
again: while (true) {
AtomicStampedReference<Node> before = head;
AtomicStampedReference<Node> swapA = before.getReference().next;
AtomicStampedReference<Node> swapB = swapA.getReference().next;

if (swapA.getReference().value == value)
return swapA.getReference();

back: while (true) {

Node oldPredecessor = before.getReference();
Node oldReplacable = swapA.getReference();
Node oldSearchable = swapB.getReference();
// verify if it is the node with the searched value
if (swapB.getReference().value == value) {

// check if the mask is stamped anywhere
if (before.getStamp() != NONE && swapA.getStamp() != NONE && swapB.getStamp() != NONE)
continue again;

// stamp the mask
if (before.attemptStamp(oldPredecessor, SEARCH) && swapA.attemptStamp(oldReplacable, STOPSEARCH)
&& swapB.attemptStamp(oldSearchable, STOPSEARCH)) {

// create the swaped construction from pred-a-b ->
// pred-b-a
Node swappedNode = new Node(oldSearchable.value,
new Node(oldReplacable.value, oldSearchable.next()));

// try to set the node
if (before.compareAndSet(oldPredecessor, new Node(oldPredecessor.value, swappedNode), SEARCH,
NONE))
return before.getReference();
}
continue back;
}

// if end of the list and it was not found
if (swapB.getReference().next() == null) {
System.out.println("Not Found");
return null;
}
before = swapA;
swapA = swapB;
swapB = swapB.getReference().next;

}

}
}

public boolean contains(int value) {
while (true) {
Node pred = head.getReference();

if (pred == null)
return false;

if (pred.value == value)
return true;

pred = pred.next();

}
}

public boolean list() {
Node node = head.getReference().next();
System.out.println("The List: ");
System.out.print("[ ");
int k = 1, row = 0;
System.out.print(row + ": ");
do {
if (k == 10) {
System.out.println(node.value);
row++;
k = 1;
System.out.print(row + "0: ");
} else {
k++;
System.out.print(node.value + " ");
}

node = node.next.getReference();
} while (node != null);
System.out.println(" ]");
return false;
}

public int size() {
int size = 0;
Node node = head.getReference();
while (node.next.getReference() != null) {

size++;

node = node.next.getReference();

}
return size;
}

}

2 Answers

Bonita Montero

4/21/2016 9:08:00 PM

Efficient algorithms in an inefficent language are paradox.

--
http://facebook.com/bonit...

tamashionuth

4/24/2016 5:33:00 PM

On Friday, April 22, 2016 at 12:08:28 AM UTC+3, Bonita Montero wrote:
> Efficient algorithms in an inefficent language are paradox.
>
> --
> http://facebook.com/bonit...

Yeah, I agree that Java may not be the best way to go. But is this algo lock-free?

comp.programming.threads

LockFree SelfOrganizing List Opinion needed about correctness

moriczsandor.s

Bonita Montero

tamashionuth

x Login to ForumsZone