Параллельный доступ к TreeSet не работает - PullRequest
Новая
       7

Параллельный доступ к TreeSet не работает

0 голосов
/ 08 января 2019

Я создаю класс Java IdGenerator, который присваивает уникальный целочисленный идентификатор каждый раз, когда его запрашивают. Он использует TreeSet для хранения диапазонов свободных идентификаторов, и каждый раз, когда запрашивается идентификатор, он ищет в наборе, чтобы найти диапазон, выделяет первый идентификатор в диапазоне, удаляет диапазон и добавляет новый диапазон, который на один меньше. Весь процесс распределения синхронизируется на множестве, чтобы гарантировать, что различные потоки не сталкиваются.

Это работало нормально, когда я проводил модульное тестирование класса, но я только что выполнил тест другого класса, где экземпляр класса IdGenerator вызывается десять раз подряд, разными потоками, и он возвращает одно и то же значение каждый раз. Ведение журнала показывает, что при каждом вызове набор, содержащий свободные диапазоны, имеет одинаковое содержимое, хотя переменная lastId отличается: -1 в первом вызове, 0 в остальных. Кажется, это говорит о том, что разные потоки используют разные копии набора, хотя это не то, чего я ожидал бы от кода.

Я использую JRE 1.8.0_191 в Eclipse Neon 4.6.3 в Windows 10.

Я попытался выполнить синхронизацию на объекте-генераторе, а не на наборе, оборачивая TreeSet в synchronizedSortedSet и используя объект Lock вместо синхронизированного ключевого слова. Ничто из этого не имело значения. 

private final SortedSet<Range> freeRanges = new TreeSet<>();
private int lastId;


public int allocateId() throws IllegalStateException
{
    int answer;
    synchronized (freeRanges)
    {
        LOG.debug("lastId = {}, freeRanges = {}", lastId, freeRanges);
        if (freeRanges.isEmpty())
            throw new IllegalStateException("All possible IDs are allocated");
        Range range = Stream
                .of(freeRanges.tailSet(new Range(lastId + 1)), freeRanges)
                .filter(s -> !s.isEmpty())
                .map(SortedSet::first)
                .findFirst()
                .get();
        answer = lastId = range.start;
        freeRanges.remove(range);
        if (range.start != range.end)
            freeRanges.add(new Range(range.start + 1, range.end));
        LOG.debug("Allocated {}, freeRanges = {}", answer, freeRanges);
    }
    return answer;
}

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

16:03:18.554 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - lastId = -1, freeRanges = [Range [start=0, end=100]]
16:03:18.570 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - Allocated 0, freeRanges = [Range [start=1, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - lastId = 0, freeRanges = [Range [start=0, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - Allocated 0, freeRanges = [Range [start=1, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - lastId = 0, freeRanges = [Range [start=0, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - Allocated 0, freeRanges = [Range [start=1, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - lastId = 0, freeRanges = [Range [start=0, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - Allocated 0, freeRanges = [Range [start=1, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - lastId = 0, freeRanges = [Range [start=0, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - Allocated 0, freeRanges = [Range [start=1, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - lastId = 0, freeRanges = [Range [start=0, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - Allocated 0, freeRanges = [Range [start=1, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - lastId = 0, freeRanges = [Range [start=0, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - Allocated 0, freeRanges = [Range [start=1, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - lastId = 0, freeRanges = [Range [start=0, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - Allocated 0, freeRanges = [Range [start=1, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - lastId = 0, freeRanges = [Range [start=0, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - Allocated 0, freeRanges = [Range [start=1, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - lastId = 0, freeRanges = [Range [start=0, end=100]]
16:03:18.586 [main] DEBUG uk.org.thehickses.idgenerator.IdGenerator - Allocated 0, freeRanges = [Range [start=1, end=100]]

1 Ответ

0 голосов
/ 09 января 2019

Спасибо всем, кто откликнулся. Я боюсь, что, возможно, я вас ввел в заблуждение - я понял, когда ехал на велосипеде домой прошлой ночью, что проблема не в том, чтобы делать несколько вызовов метода allocateId из разных потоков. Журнал, который я опубликовал, ясно показывает, что все эти вызовы выполняются в той же ветке (она называется "main").

И во время поездки на работу этим утром я понял, в чем проблема - в том, что другие потоки вызывают метод freeId, который возвращает идентификаторы в набор freeRanges. И, в частности, ID, назначаемый каждому вызову allocateId, освобождается до следующего вызова allocateId. Это объясняет, почему freeRanges имеет одинаковое содержимое каждый раз, когда вызывается allocateId.

Я сделал простое изменение, чтобы гарантировать, что когда это произойдет, если найденный диапазон содержит lastId + 1, тогда это назначенное значение, даже если оно не находится в начале диапазона. И, конечно, если он не находится в начале этого диапазона, диапазон заменяется в freeRanges двумя новыми диапазонами - один, содержащий все числа в диапазоне, которые меньше назначенного числа, и один, содержащий все те, которые больше, чем это. Это гарантирует, что мы перебираем все доступные числа настолько далеко, насколько это возможно, и только если нет свободных чисел, которые больше, чем последнее выделенное число, мы возвращаемся к началу.

Измененный код приведен ниже. Очевидно, что я должен проводить больше времени на своем велосипеде и меньше перед моим компьютером! 

public int allocateId() throws IllegalStateException
{
    int answer;
    synchronized (freeRanges)
    {
        LOG.debug("Allocating: lastId = {}, freeRanges = {}", lastId, freeRanges);
        if (freeRanges.isEmpty())
            throw new IllegalStateException("All possible IDs are allocated");
        int nextId = lastId + 1;
        Range range = Stream
                .of(freeRanges.tailSet(new Range(nextId)), freeRanges)
                .filter(s -> !s.isEmpty())
                .map(SortedSet::first)
                .findFirst()
                .get();
        answer = lastId = range.contains(nextId) ? nextId : range.start;
        freeRanges.remove(range);
        range.splitAround(answer).forEach(freeRanges::add);
        LOG.debug("Allocated {}, freeRanges = {}", answer, freeRanges);
    }
    return answer;
}
...