CODEWITHSUNDEEP
javadata-structures
Priyanka
Priyanka

Reputation: 75

How to modify a 2D array from multiple threads without synchronization

How to design a 2D array in java in such a way that it allows multiple threads to modify or insert value at a particular position without using synchronization

Upvotes: 5

Views: 2708

Answers (5)

Alex Suo
Alex Suo

Reputation: 3119

There are several ways to do it.

Firstly, if you want maximum concurrency as a common library regardless of how many threads are accessing the matrix, and your int[][] is reasonably small, you can do like this.

  1. Set up a matrix of AtomicBoolean equals to the dimension of the int[][].
  2. While you are trying to update the int matrix, lock that AtomicBoolean first, the use Unsafe.putIntVolatile() to update the value in volatile way, then unluck the AtomicBoolean.

Secondly, if you know the number of threads in advance.

  1. Keep a marker object/value as per thread like int; then create an additional int[][] as the marker matrix. Initialize the marker matrix to some dummy value which doesn't equal to any of your thread marker value, e.g. -1.
  2. While you are trying to update the int matrix, lock the cell in thr marker matrix by using Unsafe.compareAndSet() first; then update it by Unsafe.putIntVolatile(); and finally unmark the marker matrix by reset the value to -1.

Lastly, if you can tolerate the int[][] isn't really an int matrix in the actual code, what you can do is to use a long[][] matrix, where the first 32 bit is the current number of updates to the value and the last 32 bit is the current value. Then you can easily use Unsafe.compareAndSet() to set this long value as a whole. Note you can circular the upper 32 bit value so you don't have to have a update upper limit == Integer.MAX_VALUE.

Upvotes: 2

Display Name
Display Name

Reputation: 8128

If you can guarantee that each element of the array(s) is only ever accessed by a single thread (until you completed the computation that can change the array(s) contents), then you can safely use many threads. (because they will be effectively independent) Otherwise, it's probably a bad idea…

Upvotes: 1

Vishrant
Vishrant

Reputation: 16628

Create a static variable that can be accessed by all your Threads like:

public class MainClass {

    public static void main(String[] args) {

        Thread t1 = new Thread(new Runnable() {
            public void run() {
                Constants.intValue[0][0] = new Integer(10);
            }
        });

        Thread t2 = new Thread(new Runnable() {
            public void run() {
                Constants.intValue[0][1] = new Integer(20);
            }
        });

        Thread t3 = new Thread(new Runnable() {
            public void run() {
                for (Integer[] valueArr : Constants.intValue) {
                    for (Integer intValue : valueArr) {
                        System.err.println(intValue);
                    }
                }
            }
        });

        t1.start();
        t2.start();
        t3.start();

    }

}

interface Constants {

    Integer[][] intValue = new Integer[2][2];

}

The only case will be next thread will override previous set value if it is using the same array position.

Upvotes: 0

Kai
Kai

Reputation: 39631

Does this question make sense? If we assume an int[][] all operations on it will be atomic so there should be no need for synchronization! But what confuses me on the question: you cannot insert values in means of changing the array bounds after you have declared it.

Upvotes: 1

Nazgul
Nazgul

Reputation: 1902

Well you cannot do it without synchronization. Only thing you can do is reduce the scope of he lock used. If you don't know yet, read about lock coarsening. ConcurrentHashMap uses it. Idea is that instead of locking the whole array to modifications you just lock a segment of array (e.g: start, middle or end) where the modification would happen. This keeps the array DS open for reads and writes by other threads and no blocking happens unless 2 threads try to mutate the same segment simultaneously.

Upvotes: 2

Related Questions