Transcript Concurrent R-trees

Mehdi Kargar
Department of Computer Science and Engineering
1


R-tree is useful for indexing and representing
multidimensional objects.
An R-tree is a depth balanced tree with a
dynamic index structure
◦ Leaf nodes point to actual keys
◦ The number of entries in a node is between m and
N (1 < m ≤ N)
◦ Root might have between 1 and N entries.
◦ All leaf nodes are at the same level
◦ The key for each internal node is the minimum
bounding rectangle of its child nodes
◦ keys at all levels might have overlap with each other
2
3
public class MonitorRTree
{
public synchronized void add(Rectangle rect)
{
.
.
.
}
}
public synchronized boolean search(Rectangle rect)
{
.
.
.
}
4
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class ReadWriteLockRTree
{
private ReentrantReadWriteLock lock;
....
public void add(Rectangle rect)
{
this.lock.writeLock().lock();
.
.
this.lock.writeLock().unlock();
}
public boolean search(Rectangle rect)
{
this.lock.readLock().lock();
.
.
this.lock.readLock().unlock();
}
}
5

Basic idea :
◦ Logical Serial Number (LSN) is used to capture
unfinished splits.
◦ Right Links is used to follow the split nodes.
6
public synchronized void readLock()
{
while (this.state == WRITE)
{
try
{
this.wait();
}
catch (InterruptedException e) {}
}
this.increment();
}
public synchronized void readUnlock()
{
this.decrement();
this.notifyAll();
}
public synchronized void writeLock()
{
while (this.readers != 0 ||
state == WRITE)
{
try
{
this.wait();
}
catch (InterruptedException e) {}
}
this.state = WRITE;
}
public synchronized void writeUnlock()
{
this.state = READ;
this.notifyAll();
}
7




No deadlock.
No uncaught exceptions.
No data races.
Post-conditions.
8

isValid()
◦ Tests whether the final tree has the properties of an
R-link tree. The tree should be balanced and the
number of children for each node should be less
than the specified maximum.

Search for all elements that are added to the
tree.
◦ All of the elements should be in the tree.
9

Small tests were verified by JPF
◦
◦
◦
◦
◦
No deadlock was found.
No uncaught exceptions were found.
No data races were found.
All post-conditions worked properly.
Small number of state space.
10

Small tests were verified by JPF
◦
◦
◦
◦
◦
No deadlock was found.
No uncaught exceptions were found.
No data races were found.
All post-conditions worked properly.
Large number of state space.
11

Small tests were verified by JPF
◦ No deadlock was found.
◦ No uncaught exceptions were found.
◦ Data race was found.
 But it is solved now !
◦ All post-conditions worked properly.
◦ Large number of state space.
12
===================================================
error #1 gov.nasa.jpf.listener.PreciseRaceDetector race for field [email protected]
I_1 at ConcurrentRLinkTree.split(ConcurrentRLinkTree.java:98)
"(ConcurrentRLinkTree.java:98)" : putfield S_1 at
ConcurrentRLinkTree.search(ConcurrentRLinkTree.java:218)
"(ConcurrentRLinkTree.java:218)" : getfield
===================================================
snapshot #1 thread
index=1,name=I_1,status=RUNNING,this=InsertThread@414,priority=5,lockCount
=0,suspendCount=0 call stack: at
ConcurrentRLinkTree.split(ConcurrentRLinkTree.java:99) at
ConcurrentRLinkTree.add(ConcurrentRLinkTree.java:48) at
ConcurrentRLinkTree.add(ConcurrentRLinkTree.java:35) at
InsertThread.run(InsertThread.java:36) thread
index=2,name=S_1,status=RUNNING,this=SearchThread@351,priority=5,lockCoun
t=0,suspendCount=0 call stack: at
ConcurrentRLinkTree.search(ConcurrentRLinkTree.java:218) at
SearchThread.run(SearchThread.java:36)
===================================================
results error #1: gov.nasa.jpf.listener.PreciseRaceDetector "race for field
[email protected] I_1 at Concurrent..."
13


In the search method, before read lock the
root node, the LSN of root node was added to
the stack.
It was solved by read lock the root node
before adding its LSN to the stack.
14
15
16
17
18
19
20

The monitor solution
◦ Very simple implementation
◦ Not efficient in search
◦ Small number of state space

The readers writers solution
◦ Simple implementation
◦ Efficient in search
◦ Large number of state space

The R-link tree solution
◦ Very complicated implementation
◦ Efficient in search.
◦ Large number of state space
21
22