Making a custom data structure threadsafe in java?

Question

I've been looking into thread safety when doing multithreading. I'm looking into the use of locks to make a custom data structure threadsafe.

Is this the most suitable implementation for making this custom histogram threadsafe?

Also I'm new here. Is there a tag that I can use if I would like help tracing code to find out what it does?

Histogram class (Unsafe)

public class Histogram
{
    protected long[] bins;
    protected int min, max, range;
    protected int numBins;

    public Histogram(int max, int min, int numBins)
    {
        this.max = max;
        this.min = min;
        this.numBins = numBins;
        bins = new long[numBins];
        range = max - min + 1;
    }

    public void add(int num)
    {
        int bin = (int) Math.floor(((num - min) * 1.0 / range) * numBins);
        bins[bin]++;
    }

    public int absDifference(Histogram histogram)
    {
        int sum = 0;
        if (histogram.min == min && histogram.max == max && histogram.numBins == numBins)
            for (int i = 0; i < bins.length; i++)
                sum += (int) Math.abs(bins[i] - histogram.bins[i]);

        return sum;
    }

    @Override
    public String toString()
    {
        String out = String.format("{Min: %d, Max: %d, # Bins: %d, Values: ", min, max, numBins);
        for (int i = 0; i < bins.length; i++)
            out += bins[i] + ", ";

        out = out.substring(0, out.length() - 2);
        out += "}";
        return out;
    }
}

Thread safe Histogram class

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;


public class HistogramSafe extends Histogram
{
    private Lock[] binLocks;

    public HistogramSafe(int max, int min, int numBins)
    {
        super(max, min, numBins);

        binLocks = new ReentrantLock[numBins];
        for (int i = 0; i < numBins; i++)
            binLocks[i] = new ReentrantLock();
    }

    @Override
    public void add(int num)
    {
        int bin = (int) Math.floor(((num - min) * 1.0 / range) * numBins);

        binLocks[bin].lock();
        bins[bin]++;
        binLocks[bin].unlock();
    }
}

Zabuzard · Accepted Answer · 2017-10-13 11:56:24Z

It depends. If your numBins (also min and max) variable can not change, i.e. your data structure is of fixed size, then it should be thread-safe, allowing parallel modification of different bins.

But if numBins (or min, max) is modifiable then it's not thread-safe anymore. As you previously access numBins which then is also a shared resource and it is not inside the same lock.

It could be possible that a thread enters the method, reads numBins and then sleeps (due to thread scheduler). Now another thread comes and executes the full method. The old thread continues and sets bins[bin]++, but with an outdated value for numBins.

If you, for example, also provide a remove function, then this could even lead to IndexOutOfBoundException since the first thread may read a size of 10 and then other threads reducing the size to 5. When the first thread continues, it may try to write to an invalid index.

Les · Accepted Answer · 2017-10-13 12:05:31Z

1

You should investigate using AtomicInteger for your bin members. In your example, the thread safety issue is due to the increment of an integer (read, add, write). AtomicInteger operations are thread safe and much faster.

Synchronization and locks are better for protecting complex data structures.

answered Oct 13, 2017 at 12:05

Les

10.6k4 gold badges44 silver badges61 bronze badges

Comments

Alexandru Stana · Accepted Answer · 2017-10-13 12:11:17Z

1

In order to ensure that a method is thread safe the synchronized keyword can be of help. Also any data structure which is immutable is mostly thread safe.

public synchronized void methodName(){}

as Zabuza said this will block all the threads which try to call the method.

Another way ensure thread safe is to make a synchronized block which will take as parameter an object on which you want to make the lock

public void methodName(){
  synchronized(object) {
     ...
  }
}

edited Oct 13, 2017 at 12:11

answered Oct 13, 2017 at 11:57

Alexandru Stana

792 silver badges5 bronze badges

1 Comment

Zabuzard Over a year ago

synchronized, in this case, would block the whole method for all threads. OP tries to realize that threads which want to modify different bins can continue.

Shadov · Accepted Answer · 2017-10-13 12:37:20Z

0

I'm gonna look at this from a different perspective - no, in my opinion it is not thread-safe. Why? Because you allowed inheritance. A lot of things can go wrong when someone extends this class - mostly overriding the add method.

answered Oct 13, 2017 at 12:37

Shadov

5,5862 gold badges21 silver badges44 bronze badges

Collectives™ on Stack Overflow

Making a custom data structure threadsafe in java?

4 Answers 4

Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related