Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Lock-free реализация класса

Автор: Ares4322 21.10.2013, 12:15

Доброго времени суток!

Есть такая задача.

Напишите lock-free реализацию класса с методом BigInteger next(), который возвращает элементы последовательности Фибоначчи. Код должен корректно работать в многопоточной среде.

Вот мое решение.
Подскажите, правильно ли я его сделал?

Код


class FibEntity {
    private final BigInteger prev;
    private final BigInteger cur;

    FibEntity(BigInteger prev, BigInteger cur) {
        this.prev = prev;
        this.cur = cur;
    }

    BigInteger getPrev() {
        return prev;
    }

    BigInteger getCur() {
        return cur;
    }
}

interface FibCounter{
    BigInteger next();
}

class FibCounterImpl implements FibCounter {

    private  AtomicReference<FibEntity> ref = new AtomicReference<FibEntity>(new FibEntity(ZERO, ONE));

    @Override
    public BigInteger next() {
        boolean b;
        BigInteger result;
        do{
            FibEntity entity = ref.get();
            BigInteger prev = entity.getPrev();
            BigInteger cur = entity.getCur();
            BigInteger next = prev.add(cur);
            result = next;
            b = ref.compareAndSet(entity, new FibEntity(cur, next));
        } while (!b);
        return result;
    }
}

Можно вместо цикла с проверкой на установку значения сделать возвращение маркерного значения (например, null), но, мне кажется, что это не правильно.

Автор: LSD 21.10.2013, 12:38

Цитата(Ares4322 @ 21.10.2013, 13:15

)

Подскажите, правильно ли я его сделал?

По моему нормально.

Цитата(Ares4322 @ 21.10.2013, 13:15

)

Возвращать null откуда? Из метода FibCounter.next() ?

Автор: Ares4322 21.10.2013, 12:42

Да, из этого метода. Но, как я написал, мне кажется, что это неправильно. Так как клиенты класса ничего не должны знать о внутренностях реализации на атомиках.

Автор: LSD 21.10.2013, 13:21

Да: иначе получается что контракт метода зависит от конкретной реализации (в случае реализации с блокировкой не будет такой проблемы), код получения значения в цикле будет повторяться во всех местах где используется FibCounter.next().

Автор: Ares4322 21.10.2013, 16:51

А то, что порядок вызова метода разными потоками не будет совпадать с порядком возврата результата из этого метода, это нормально?

Автор: LSD 21.10.2013, 17:07

Цитата(Ares4322 @ 21.10.2013, 17:51

)

Как бы ты его не реализовывал, порядок может не совпадать. Планировщик может в любой момент усыпить поток.

Автор: Ares4322 22.10.2013, 10:02

А что будет в такой ситуации:
Есть несколько процессоров. И потоков у нас по количеству этих процессоров. Общий класс с критической секций на synchronized. Когда один поток зашел в секцию, то остальные BLOCKED. Может ли планировщик заблокировать этот рабочий поток? (я так понимаю, что да). Если он разблокирует другой, то будет ли он выполняться, ведь монитором владеет другой объект, который заблокирован?

Автор: LSD 22.10.2013, 10:51

1. Количество процессоров/ядер значения не имеет, планировщик ОС может запинуть все потоки на одно ядро, или перекидывать с одного на другое.
2. Поток который захватил монитор может так же быть усыплен планировщиком как и любой другой.
3. Поток который ожидает освобождения монитора, может быть разбужен планировщиком, но как только он убедится что монитор по прежнему занят снова заснет.

Автор: Ares4322 22.10.2013, 11:23

Тогда понятно, чем написанная мной реализация лучше, чем реализация на блокировках. Если хотя бы один поток будет работать из всех потоков программы, то программа в общем будет двигаться вперед. Если же будет реализация на блокировке, то из-за описанного выше случая 3 программа даже с одним потоком не будет прогрессировать.

Автор: Farmazon 12.11.2013, 04:20

Код



    static BigInteger next(BigInteger prev, BigInteger cur) {
       return prev+cur;
    }

Нет разделяемых ресурсов = нет блокировок. smile

Или в задании где-то интерфейс уже дан?...в смысле, BigInteger next() - полная сигнатура?

Таки да, вернуть NULL или выкинуть исключение - тоже нормально. Занят я!) наверное для этого и есть коробка в сигнатуре...

Автор: Ares4322 12.11.2013, 09:00

Да, интерфейс именно такой. Я в первом сообщении написал задание.
Про коробку не понял...

Автор: Farmazon 12.11.2013, 18:12

BigIntger - коробка, не примитив... хотя мождет и из-за размерности...