Re: Locking objects in an array
Daniel Pitts wrote:
Philipp wrote:
On May 13, 11:48 pm, Daniel Pitts
<newsgroup.spamfil...@virtualinfinity.net> wrote:
Philipp wrote:
Hello,
I've come accross a threading problem for which I can't find a nice
solution. (SSCCP at end of post)
I have a bidimensionalarrayofobjects(view it as a 2D lattice). I
want to make atomic operations on random square 2x2 regions of the
lattice. Thus I want to lock the 4objectsof the region, then perform
the change, then unlock thoseobjects. Several threads should be
allowed to work on thearrayat the same time, if each thread is
accessing a 2x2 region which does not overlap with that of another,
they should be capable of doing the work in a parallel way.
How should I design the code to achieve this?
I was thinking about this a little longer, and one might be able to
create an algorithm that takes a Region and blocks as long as any
previously added Region is in use. I'm working on a prototype right
now, I'll post when I've completed it.
I don't know if this what you meant, but a possible approach would be
a non-blocking algorithm.
1. Take a snapshot of the objects in the region.
2. Do the work on them
3. Check if the region has not been modified.
4. Atomically commit the change if the region is the same as before in
1.
This might be particularly interesting if contention is not expected
(few threads, big array, small region) because we can limit
synchronization to point 4. Is this a way to follow?
Phil
I was thinking more about not having explicit locks per object, but
instead having a "Lock Request" that puts its region into a specific
data structure. That Lock Request would block as long as the current
region intersects any region currently ahead of it in that data
structure. Once work is complete, that Lock Request can be removed from
that data-structure, unblocking other threads waiting for that region.
Here is my idea put into code. This is *completely* untested. It is also
not verified for correctness. I *think* it is correct, but if someone
can point out flaws, I'd be interested in them.
--- GridLock.java
package net.virtualinfinity.concurrent;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
/**
* Locks based on concurrent access to a 2d space.
* @author Daniel Pitts
*/
public class GridLock {
private static final
AtomicReferenceFieldUpdater<Lock, Lock> nextUpdater =
AtomicReferenceFieldUpdater.newUpdater(Lock.class,
Lock.class, "next");
public class Lock {
private final Region region;
private volatile Lock next;
private volatile boolean complete;
private Lock(Region region, Lock next) {
this.region = region;
this.next = next;
}
private boolean compareAndSetNext(Lock oldNext, Lock newNext) {
return nextUpdater.compareAndSet(this, oldNext, newNext);
}
public void release() {
complete = true;
synchronized (this) {
notifyAll();
}
cleanLocks();
}
}
AtomicReference<Lock> head = new AtomicReference<Lock>();
/**
* Locks a region. Blocks until existing locks that intersect
* the region are released.
* @param region the region to lock
* @return a Lock handle.
* @throws InterruptedException if the thread is interrupted
*/
public Lock lock(Region region) throws InterruptedException {
Lock release = null;
try {
while (true) {
final Lock h = head.get();
release = new Lock(region, h);
if (!head.compareAndSet(h, release)) {
continue;
}
Lock cur = release;
Lock next = cur.next;
while (next != null) {
if (next.region.intersects(region)) {
while (!next.complete) {
synchronized (next) {
next.wait();
}
}
Lock nn = next.next;
cur.compareAndSetNext(next, nn);
}
cur = next;
next = cur.next;
}
Lock ret = release;
release = null;
return ret;
}
} finally {
if (release != null) {
release.release();
}
}
}
private void cleanLocks() {
Lock head;
head = this.head.get();
while (head.complete) {
Lock next = head.next;
if (head.complete) {
this.head.compareAndSet(head, next);
}
head = this.head.get();
}
Lock cur = this.head.get();
if (cur == null) {
return;
}
Lock next = cur.next;
while (true) {
if (next == null) {
return;
}
while (next.complete) {
cur.compareAndSetNext(next, next.next);
next = cur.next;
if (next == null) {
return;
}
}
cur = next;
next = cur.next;
}
}
}
--- Region.java
package net.virtualinfinity.concurrent;
/**
* Represents a rectangular region on a grid.
* @author Daniel Pitts
*/
public final class Region {
private final int x1;
private final int y1;
private final int x2;
private final int y2;
private Region(int x1, int y1, int x2, int y2) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
public static Region bySize(int x, int y, int width, int height) {
return new Region(x, y, x+width-1, y+height-1);
}
public static Region byBounds(int x1, int y1, int x2, int y2) {
return new Region(Math.min(x1, x2),
Math.min(y1, y2),
Math.max(x1, x2),
Math.max(y1, y2));
}
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Region)) return false;
Region region = (Region) o;
return x1 == region.x1 && x2 == region.x2 &&
y1 == region.y1 && y2 == region.y2;
}
public int hashCode() {
return 31 * (31 * (31 * x1 + y1) + x2) + y2;
}
public boolean intersects(Region other) {
return other.x2 >= x1 && other.y2 >= y1 &&
x2 >= other.x1 && y2 >= other.y1;
}
}
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>