Одновременный доступ к TreeSet не работает

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

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

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

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

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]]

java synchronized treeset
person Jeremy Hicks    schedule 08.01.2019    source источник
comment
Ваша синхронизация в порядке (но вы также можете объявить весь метод синхронизированным). Ошибка должна быть в коде внутри блока. Вам действительно нужна вся эта потоковая обработка? Не хватит freeRanges.first()?   -  person Marco    schedule 08.01.2019
comment
Для ухмылки, что происходит, когда вы оборачиваете древовидный набор в синхронизированный набор?   -  person Makoto    schedule 08.01.2019
comment
Я мог бы объявить весь метод синхронизированным, но это было бы эквивалентно synchronized (this), а не synchronized (freeRanges). Я не поклонник synchronized (this), потому что это означает, что внешний код также может синхронизироваться с моим объектом; Я предпочитаю синхронизировать объект, о котором знаю только я,   -  person Jeremy Hicks    schedule 08.01.2019
comment
Вся эта потоковая обработка предназначена для обеспечения того, чтобы я, насколько это возможно, циклически перебрал все поддерживаемые идентификаторы, прежде чем начать заново с самого начала. Но я просто попытался изменить его на freeRanges.first(), и это не повлияло на проблему.   -  person Jeremy Hicks    schedule 08.01.2019
comment
Почему бы просто не использовать Queue<Range> (или даже Deque<Range>) и удалить диапазон, а затем добавить его в конец очереди? Это также означало бы, что вам не нужно было бы синхронизировать тело метода, если бы вы использовали потокобезопасную реализацию очереди.   -  person Daniel Pryden    schedule 08.01.2019
comment
Как указано выше, обертывание набора дерева в синхронизированном наборе не имеет значения.   -  person Jeremy Hicks    schedule 08.01.2019
comment
Хорошо; справедливо. Не могли бы вы опубликовать простую реализацию вашего класса Range, чтобы мы могли запустить его локально?   -  person Makoto    schedule 08.01.2019
comment
Queue<Range> усложнит ведение списка свободных диапазонов, когда он становится более фрагментированным, а также затруднит достижение цели циклического перебора всех возможных значений перед повторным запуском с самого начала.   -  person Jeremy Hicks    schedule 08.01.2019
comment
Полный код находится на github.com/hicksjduk/idgenerator. Класс Range - это внутренний класс IdGenerator.   -  person Jeremy Hicks    schedule 08.01.2019

Ответы (1)


arrow_upward
0
arrow_downward

Спасибо всем, кто откликнулся. Боюсь, что, возможно, я вас ввел в заблуждение - вчера вечером, возвращаясь домой на велосипеде, я понял, что проблема не связана с множественными вызовами метода allocateId из разных потоков. Опубликованный мной журнал ясно показывает, что все эти вызовы выполняются в одном потоке (он называется «основным»).

И пока утром ехал на работу на велосипеде, я понял, в чем проблема - другие потоки вызывают метод freeId, который возвращает идентификаторы в набор freeRanges. В частности, идентификатор, присвоенный каждому вызову 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;
}
person Jeremy Hicks    schedule 09.01.2019