java - 并发频率计数器更新java

Question

我正在尝试实现一个频率计数器来计算每个元素的出现次数。在这种情况下，两个进程可以同时调用 hfc.count(1) 和 hfc.count(2)。我正在总结进程数以确保其为 2000000，但我差了 ~100000。

class FrequencyCounter {
HashMap<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
int max ;

FrequencyCounter(int max) {
    this.max = max ;
    for (int i = 0; i < max; i++) {
        frequencyMap.put(i, 0);
    }
}

void count(int event) {
    synchronized (this) {
        if (frequencyMap.containsKey(event)) {
            frequencyMap.put(event, frequencyMap.get(event) + 1);
        }
    }
}

/**
 * @param event
 * @return the frequency of event since creation.
 */
int frequency(int event) {

    return frequencyMap.get(event);
}

并发频率计数器

class HighFrequencyCounter extends FrequencyCounter {

int[] count;
static int n;

/**
 * @ClassInvariant {frequencyMap != null && max > 0}
 */

HighFrequencyCounter(int max) {
    super(max);

    count = new int[max];
}

void count(int event) {
    if (count[event] != 0) {
        n++;
        super.count(event);
    }
    if (count[event] < 1) {
        count[event] = 1;
        frequencyMap.put(event, frequencyMap.get(event) + 1);
        count[event] = 0;

    }
}

public static void main(String Args[]) throws InterruptedException {

    class HEventer extends Thread {
        HighFrequencyCounter hfc;

        HEventer(HighFrequencyCounter hfc) {
            this.hfc = hfc;
        }

        public void run() {
            Random r = new Random();
            for (int i = 0; i < 20000; i++) {
                hfc.count(r.nextInt(10));
            }
        }
    }

    HighFrequencyCounter hfc = new HighFrequencyCounter(10);
    HEventer hev[] = new HEventer[1000];
    for (int i = 0; i < 1000; i++) {
        hev[i] = new HEventer(hfc);
    }

    long hstartTime = System.currentTimeMillis();
    for (int i = 0; i < 1000; i++) {
        hev[i].start();
    }
    for (int i = 0; i < 1000; i++) {
        hev[i].join();
    }
    long hendTime = System.currentTimeMillis();
    System.out.println(hendTime - hstartTime);

    int sumProcesses = 0;
    for (int i = 0; i < 10; i++) {
        System.out.println(i + " =  " + hfc.frequency(i));
        sumProcesses = sumProcesses + hfc.frequency(i);

    }
    System.out.println(sumProcesses);
    System.out.println(hfc.n);

}

我知道这可以使用 java 的并发散列图实现，但我只是尝试同步简单的散列图。我的普通 frequencyCounter 类确实按预期工作，但我不确定如何同步计数方法。

对于高频计数器，我同步了计数方法，并在 while(count[event] != 0) wait() 中使用了等待，但是这允许并发调用，因为我需要同步计数方法。

Answer 1

您需要同步对frequencyMap的所有共享访问， 不仅仅是写信给它。 由于写入 map 由 this 上的锁保护， 从 map 读取时，您需要在同一个锁上同步。

int frequency(int event) {
    synchronized (this) {
        return frequencyMap.get(event);
    }
}

没有同步， 一个线程可能看不到另一个线程写的内容。 这解释了您得到的不一致的值。

顺便说一句，我注意到构造函数将映射中的初始值设置为 [0..max) 范围内的 0。 如果 map 只会使用此范围内的键， 那么数组会比 HashMap 更合适、更轻量。

---

正如您在评论中所写:

My issue is regarding the count(event) function of HighFrequencyCounter. If i want to allow for two threads of different integer events, say hfc.count(4) and hfc.count(3) to run concurrently but not two concurrent calls to hfc.count(3), i used a count[0..Max] as an array to hold the condition. This is where i'm running into difficulties in synchronizing

根据这个描述， 每个柜台需要一把锁。 这是一个使用一个数组进行计数的简单实现， 和一个锁:

class FrequencyCounter {
    private final int[] counts;
    private final Object[] locks;

    FrequencyCounter(int max) {
        counts = new int[max];
        locks = new Object[max];
        IntStream.range(0, max).forEach(i -> locks[i] = new Object());
    }

    void count(int event) {
        synchronized (locks[event]) {
            counts[event]++;
        }
    }

    int frequency(int event) {
        synchronized (locks[event]) {
            return counts[event];
        }
    }
}