Synchronized Cache Matrix

Question

Im working on a java project for school where you have to deal with a multithreaded program. I need a class, shared between many threads that is basically a matrix of values that have to manage concurrent access, it looks something like:

public class CacheMatrix{
private MyType[][] cachedItems;

public CacheMatrix(int size){
    this.cachedItems = new MyType[size][size];
}
public MyType readItem(int x, int y){...}
public void storeItem(int x, int y, MyType item){...}
}

I was about to manage it using a matrix of ReentrantReadWriteLock, one for each item, but i realized that the matrix size is around 10^3 X 10^3 so i would have 1 million lock!

Do you think this is the way to go? (is it ok to create so many locks?)

Can you find a better way that preserve almost only the minimum mutual exclusion but uses less lock, considering that the number of threads that use this class is limited to a small number N (N range from 2 to 8)?

Thanks fro your support!

Answer 1

You may consider implementing lock striping in order to reduce the number of locks and still maintain performance.

Basically, an internal array holding mylockscount = min(concurrencylevel, size) locks is created. Whenever an read/write operation occurs, you lock on e.g. mylocks[somehashfunction(x, y) % mylockscount].

This way, the number of locks should only scale with the number of concurrent threads and not the size of the matrix.

Answer 2

Whats's about just making the accessing methods synchronized?

public synchronized MyType readItems(...){...}

Answer 3

Another option is to replace MyType[][] with AtomicReference<MyType>[][]; in this case void storeItem will become boolean storeItem(int x, int y, MyType oldValue, MyType newValue) that returns false if oldValue does not equal the value currently held at [x][y] (under the surface you'd be calling AtomicReference#compareAndSet(oldValue, newValue)). This way you don't have any locks, you just need to implement retry logic in case storeItem returns false

If MyType is a primitive, e.g. int, then use the appropriate atomic primitive e.g. AtomicInteger instead of AtomicReference

Answer 4

Two possible scenarios come to mind:

1) Use a single lock. It's a bit naive, but it might solve your problem.

2) Lock only the ROWS or COLUMNS. If you intend to access the matrix one item at a time on a random basis, this should do nicely, I think:

public class CacheMatrix
{
    private MyType[][] cachedItems;

    public CacheMatrix(int size) {
        this.cachedItems = new MyType[size][size];
    }

    public MyType readItem(int x, int y) {
        synchronized (cachedItems[x]) {
            return cachedItems[x][y];
        }
    }

    public void storeItem(int x, int y, MyType item) {
        synchronized (cachedItems[x]) {
            this.cachedItems[x][y] = item;
        }
    }
}