Модераторы: LSD, AntonSaburov
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Lock-free реализация класса 
V
    Опции темы
Ares4322
Дата 21.10.2013, 12:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 339
Регистрация: 25.9.2007
Где: Россия, Москва

Репутация: 1
Всего: 3
Доброго времени суток!

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

Напишите 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), но, мне кажется, что это не правильно.
PM MAIL   Вверх
LSD
Дата 21.10.2013, 12:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Leprechaun Software Developer
****


Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 210
Всего: 538
Цитата(Ares4322 @  21.10.2013,  13:15 Найти цитируемый пост)
Подскажите, правильно ли я его сделал?

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


Цитата(Ares4322 @  21.10.2013,  13:15 Найти цитируемый пост)
Можно вместо цикла с проверкой на установку значения сделать возвращение маркерного значения (например, null), но, мне кажется, что это не правильно. 

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


--------------------
Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.
PM MAIL WWW   Вверх
Ares4322
Дата 21.10.2013, 12:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 339
Регистрация: 25.9.2007
Где: Россия, Москва

Репутация: 1
Всего: 3
Да, из этого метода. Но, как я написал, мне кажется, что это неправильно. Так как клиенты класса ничего не должны знать о внутренностях реализации на атомиках.
PM MAIL   Вверх
LSD
Дата 21.10.2013, 13:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Leprechaun Software Developer
****


Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

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


--------------------
Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.
PM MAIL WWW   Вверх
Ares4322
Дата 21.10.2013, 16:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 339
Регистрация: 25.9.2007
Где: Россия, Москва

Репутация: 1
Всего: 3
А то, что порядок вызова метода разными потоками не будет совпадать с порядком возврата результата из этого метода, это нормально?
PM MAIL   Вверх
LSD
Дата 21.10.2013, 17:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Leprechaun Software Developer
****


Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 210
Всего: 538
Цитата(Ares4322 @  21.10.2013,  17:51 Найти цитируемый пост)
А то, что порядок вызова метода разными потоками не будет совпадать с порядком возврата результата из этого метода, это нормально?

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


--------------------
Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.
PM MAIL WWW   Вверх
Ares4322
Дата 22.10.2013, 10:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 339
Регистрация: 25.9.2007
Где: Россия, Москва

Репутация: 1
Всего: 3
А что будет в такой ситуации:
Есть несколько процессоров. И потоков у нас по количеству этих процессоров. Общий класс с критической секций на synchronized. Когда один поток зашел в секцию, то остальные BLOCKED. Может ли планировщик заблокировать этот рабочий поток? (я так понимаю, что да). Если он разблокирует другой, то будет ли он выполняться, ведь монитором владеет другой объект, который заблокирован?
PM MAIL   Вверх
LSD
Дата 22.10.2013, 10:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Leprechaun Software Developer
****


Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

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


--------------------
Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.
PM MAIL WWW   Вверх
Ares4322
Дата 22.10.2013, 11:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 339
Регистрация: 25.9.2007
Где: Россия, Москва

Репутация: 1
Всего: 3
Тогда понятно, чем написанная мной реализация лучше, чем реализация на блокировках. Если хотя бы один поток будет работать из всех потоков программы, то программа в общем будет двигаться вперед. Если же будет реализация на блокировке, то из-за описанного выше случая 3 программа даже с одним потоком не будет прогрессировать.
PM MAIL   Вверх
Farmazon
  Дата 12.11.2013, 04:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Разработчик
**


Профиль
Группа: Участник
Сообщений: 265
Регистрация: 7.7.2006

Репутация: 1
Всего: 5
Код


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



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

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

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


Это сообщение отредактировал(а) Farmazon - 12.11.2013, 05:06


--------------------
Таково моё общее мнение.
PM MAIL WWW   Вверх
Ares4322
Дата 12.11.2013, 09:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 339
Регистрация: 25.9.2007
Где: Россия, Москва

Репутация: 1
Всего: 3
Да, интерфейс именно такой. Я в первом сообщении написал задание.
Про коробку не понял...
PM MAIL   Вверх
Farmazon
Дата 12.11.2013, 18:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Разработчик
**


Профиль
Группа: Участник
Сообщений: 265
Регистрация: 7.7.2006

Репутация: 1
Всего: 5
BigIntger - коробка, не примитив... хотя мождет и из-за размерности...


--------------------
Таково моё общее мнение.
PM MAIL WWW   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Java"
LSD   AntonSaburov
powerOn   tux
javastic
  • Прежде, чем задать вопрос, прочтите это!
  • Книги по Java собираются здесь.
  • Документация и ресурсы по Java находятся здесь.
  • Используйте теги [code=java][/code] для подсветки кода. Используйтe чекбокс "транслит", если у Вас нет русских шрифтов.
  • Помечайте свой вопрос как решённый, если на него получен ответ. Ссылка "Пометить как решённый" находится над первым постом.
  • Действия модераторов можно обсудить здесь.
  • FAQ раздела лежит здесь.

Если Вам помогли, и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, LSD, AntonSaburov, powerOn, tux, javastic.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Java: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0999 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.