Многопоточность Java - есть ли способ синхронизировать / заблокировать определенное значение на карте как для чтения, так и для записи? - PullRequest
Новая
       11

Многопоточность Java - есть ли способ синхронизировать / заблокировать определенное значение на карте как для чтения, так и для записи?

3 голосов
/ 09 мая 2019

Я хочу реализовать алгоритм топосортировки, который можно выполнять параллельно над графиком в Java с использованием потоков. В частности, алгоритм, найденный в этой статье здесь .

Важной частью этого алгоритма для этого вопроса является то, что значение расписания, которое мы храним для каждого узла, обновляется следующим образом: если поток встречает узел на графике, он будет читать его текущее значение. Если поток имеет более высокое значение, он заменит его и продолжит работу. В противном случае это остановится.

Мне нужно иметь возможность выполнять запись и чтение для определенного узла за одну атомарную операцию. Я хочу представить значение в виде значения на карте с идентификатором ключа int (для каждого узла). Однако из того, что я вижу, методы синхронизации для Карт в Java, кажется, либо блокируют только записи, либо блокируют всю карту. Если вся карта заблокирована, производительность также может быть однопоточной. Если чтение не заблокировано, я могу получить неправильное поведение.

Моя цель - блокировать только определенный индекс. Если два потока хотят читать и обновлять разные узлы, это нормально, но если два потока сталкиваются с одним и тем же узлом, мне нужно убедиться, что каждая операция read -> check -> update or stop происходит атомарно. Конкретный случай, которого я хочу избежать: 

Thread_1 (val 5) read g_1 -> value is 3, trigger update
Thread_2 (val 4) read g_1 -> value is 3, trigger update
Thread_1 (val 5) lock and update g_1 -> g_1 value is 5
Thread_2 (val 4) lock and update g_1 -> g_1 value is 4

Вместо этого я собираюсь сделать: 

Thread_1 (val 5) lock g_1
Thread_2 (val 4) wait for g_1
Thread_1 (val 5) read g_1 -> value is 3, update g_1 -> g_1 value is 5
Thread_1 (val 5) release g_1
Thread_2 (val 4) lock g_1
Thread_2 (val 4) read g_1 -> value is 5, do nothing
Thread_2 (val 4) release g_1

1 Ответ

3 голосов
/ 09 мая 2019

Если ваш набор ключей статичен, вы можете просто использовать значения AtomicInteger. Вы можете использовать compareAndSet так: 

atomicValue = map.get(key);
while (true) {
    value = atomicValue.get();
    if (value < myThreadNumber) {
        if (value.compareAndSet(value, myThreadNumber) {
            // successfully increased the thread number
            triggerUpdate();
            break;
        } // else value update failed, loop back to try again.
    } else {
        break;
    }
}

Кроме того, вы можете использовать ConcurrentHashMap, который не блокирует всю карту. В Java 8 добавлено много методов параллелизма, которые делают то, что вы хотите, относительно простым. Например, если ваш код триггера относительно быстрый, вы можете просто использовать compute(): 

map.compute(key, (key, value) -> {
    if (value < myThreadNumber) {
        triggerUpdate();
        return myThreadNumber;
    }
    return value; // no changes
})

Конечно, вы всегда можете создать тип значения, который соединит ваш int с блокировкой, но это полезно только для школьной работы. На практике замки настолько дороги, что вы определенно не хотите, чтобы они были внутри ваших внутренних петель.

...