Synchronize access to particular indexes in int array

Question

I use the int array.

I use that method to fill indexes in array.

public void makeSelectionOfGivenNumber(int number) throws InterruptedException 
{
    if (this.table[number]!= 0) 
    {
        int multiple;
        multiple = number + number;

        while (multiple <= upperRange) 
        {
            this.table[multiple] = 0;
            multiple += number;
        }
    }
}

For example, one thread starts from 2 and eliminates all multiples, a second thread starts from 5 and makes the same activities. In some case the simultaneously the value in index 10 (in both cases are multiples). How to use in this case semaphores or other tools to lock that only one thread has access on particular index, not the whole array. I want that these two threads would work in parallel on the same table.

@Bubletan, using AtomicIntegerArray and method set(index,value) -> only one thread at once on specific index can modify value? — maciejka
– maciejka, Commented Oct 15, 2017 at 12:25
Well, it doesn't lock, but it guarantees that changes are immediately visible to other threads. — Bubletan
– Bubletan, Commented Oct 15, 2017 at 12:38
@Bubletan All right, but when one thread starts from 2 and second starts from 3, can it be conflict for example on 6 index, when they both at the same time try to write cell on that index? Can AtomicIntergerArray exclude this situation? — maciejka
– maciejka, Commented Oct 15, 2017 at 22:05
Using table.compareAndSet method can resolve the access to the same index in array by two threads? — maciejka
– maciejka, Commented Oct 15, 2017 at 22:23

segabriel · Accepted Answer · 2017-10-15 13:17:56Z

1

I think You need to create an additional array of locks (ReadWriteLock, a dimension of the array is how you want) and before each attempt to read/change in the target array to take a lock on reading or on writing the element into the array. To take the lock need to calculate an index from the required index of target array and the capacity of the additional array.

Maybe I'm not quite correctly understood the task

public class SomeTask {

    private final ReadWriteLock[] locks = locks(5);
    private int[] table;
    private int upperRange;

    public SomeTask(int[] table, int upperRange) {
        this.table = table;
        this.upperRange = upperRange;
    }

    public void makeSelectionOfGivenNumber(int number) {
        if (this.table[number] != 0) {
            int multiple;
            multiple = number + number;
            while (multiple <= upperRange) {
                ReadWriteLock lock = getLock(multiple);
                try {
                    lock.writeLock().lock();
                    this.table[multiple] = 0;
                } finally {
                    lock.writeLock().unlock();
                }
                multiple += number;
            }
        }
    }

    private ReadWriteLock getLock(int number) {
        return locks[(locks.length - 1) & number];
    }

    private ReadWriteLock[] locks(int size) {
        ReadWriteLock[] result = new ReadWriteLock[size];
        for (int i = 0; i < size; i++) {
            result[i] = new ReentrantReadWriteLock();
        }
        return result;
    }

edited Oct 15, 2017 at 13:17

answered Oct 15, 2017 at 10:52

segabriel

261 silver badge3 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

maciejka Over a year ago

can you give some example of this?

NickL Over a year ago

Since you are only locking when you write, the first read access to this.table[number] != 0 is not synchronized, and you may not be able to see the value written to that index by another thread.

maciejka Over a year ago

@segabriel, your solution works fine. How about performance, I have checked times using difference Syste.nanoTime between start and end. It looks poor using threads in this case towards sequence task. Is it possible to boost it?

maciejka Over a year ago

This task is connected with Erastotenes Sieve. Problem is when one thread starts from 2 and second thread starts from 5, it can possible that they gain acccess to cell of number 10 at the same time. However finally it will be there 0, but it is not correct if we talk about paraller programm.

segabriel Over a year ago

@maciejka performance - maybe should add following check if (this.table[multiple] != 0) before try to get lock in the loop

Collectives™ on Stack Overflow

Synchronize access to particular indexes in int array

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related