using threads on an Atomic Integer Array

Question

I am writing code to let 4 threads build a histogram.

I have an array in main:

int N = 10000;
Random r = new Random();
int[] a = new int[N];

for (int i = 0; i < a.length; i++)
{
    a[i] = Math.abs(r.nextInt() % 100);
}

So basically what I want to do is cycle through this array and count how many times each number appears.

So I have written my thread class, and I used AtomicInteger which I thought would help solve the problem of multiple threads trying to access the same index simultaneously.

import java.util.concurrent.atomic.AtomicInteger;

public class UseThread implements Runnable
{
private static int[] array;
private static AtomicInteger[] count;
private static boolean[] check;

public UseThread(int[] array, AtomicInteger[] count)
{
    this.array = array;
    this.count = count;
    this.check = new boolean[array.length];
}

public void run()
{
    for (int i = 0; i < array.length; i++)
    {
        if (!getIndex(this.check[i]))
        {
            this.check[i] = true;
            int number = array[i];
            count[number].incrementAndGet();
        }
    }
}

public synchronized static boolean getIndex(boolean check2)
{
    return check2;
}

However, this hasn't quite fixed my problem. Some of the threads are accessing the array at the same time, making the count array, hold a larger value than the length of the array array.

I think the problem is in the boolean array of checking. I have a feeling that multiple threads access the same boolean array index at the same time.

I figure it is probably a simple fix, but I am just not seeing it.

Any suggestions??

I have tried the AtomicBoolean array, but it has not helped. Below is the same class but with the AtomicBoolean array implemented.

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

public class Assign7Q3 implements Runnable
{
private static int[] array;
private static AtomicInteger[] count;
private static AtomicBoolean[] check;

public Assign7Q3(int[] array, AtomicInteger[] count)
{
    this.array = array;
    this.count = count;
    this.check = new AtomicBoolean[array.length];
    for(int i = 0; i < check.length; i ++)
        check[i] = new AtomicBoolean(false);
}

public void run()
{
    for (int i = 0; i < array.length; i++)
    {
        //System.out.println(this.check[i].get());
        if (!getIndex(this.check[i]))
        {
            this.check[i].set(true);
            int number = array[i];
            count[number].incrementAndGet();
        }
    }
}

public synchronized static boolean getIndex(AtomicBoolean check2)
{
    return check2.get();
}

Answer 1

You need to use compareAndSet for your if statement to be mutally exclusive:

if (this.check[i].compareAndSet(false, true))
{
    int number = array[i];
    count[number].incrementAndGet();
}

This both checks and sets the value atomically.

Without compareAndSet, there is a possibility that two threads can check the value and enter the if block at the same time before one has a chance to call set(true).