Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Concurrency: 6 методов жить с shared state

Anna | 2.06.2014 | нет комментариев
В многопоточном программировании много трудностей, основными из которых являются работа c разделяемым состоянием и результативное применение предоставляемых ядер. Об применении ядер пойдет речь в дальнейшей статье.

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

Все примеры приведены на Java, но содержат комментарии и я верю будут внятны программистам не приятелем c Java. Данная статья носит обзорный нрав и не претендует на полноту. В то же время она наполнена ссылками, которые дают больше подробное трактование терминам и заявлениям.

Shared State

Работу с разделяемым состоянием я покажу на примере вычисления чисел фибоначчи.
Формула для вычисления выглядит так:

f(0) = 0
f(1) = 1
f(n) = f(n - 1)   f(n - 2) , n >= 2

В первую очередь определим интерфейс:

public interface FibonacciGenerator<T> {
    /**
     * Следующее сгенерированное значение
     */
    T next();

    /**
     * Нынешнее значение в генераторе
     */
    public T val();
}

Наши классы будут реализовывать интерфейс FibonacciGenerator<BigInteger>. Из формулы видно, что для предоставления дальнейшего числа, нужно беречь два предыдущих — это и будет разделяемое состояние, за которое будет проходить соперничество. Наша реализация должна быть потоко-неопасной. То есть самостоятельно от одновременного числа покупателей, она будет сберегать свои инварианты и придерживаться контракта. И так, приступим.

Locking

1-й метод сделать класс правильно работающим в многопоточной среде — это применять блокировки и объявить все способы synchronized. Примером может служить класс Vector.

public class IntrinsicLock implements FibonacciGenerator<BigInteger> {

    private BigInteger curr = BigInteger.ONE;
    private BigInteger next = BigInteger.ONE;

    @Override
    public synchronized BigInteger next() {
        BigInteger result = curr;
        curr = next;
        next = result.add(next);
        return result;
    }

    @Override
    public synchronized BigInteger val() {
        return curr;
    }

}

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

Fine-Grained locking

Дальнейший метод — разбить наши конструкции на части и оградить локами только те сегменты, в которых происходит работа с разделяемым состоянием. Примером такого подхода является СoncurrentHashMap. В нем все данные разбиваются на несколько частей. При доступе блокируется только та часть, метаморфоза которой происходит в нынешний момент. Также есть вариант применять больше функциональные локи, такие как: StampedLockReadWriteLock. При правильных алгорифме и реализации мы получаем больше высокий ярус параллелизма. Пример с применением ReadWriteLock:

public class FineGrainedLock implements FibonacciGenerator<BigInteger> {

    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private BigInteger curr = BigInteger.ONE;
    private BigInteger next = BigInteger.ONE;

    @Override
    public BigInteger next() {
        BigInteger result;
        lock.writeLock().lock();
        try {
            // Вход иным потокам запрещен
            result = curr;
            curr = next;
            next = result.add(next);
            return result;
        } finally {
            lock.writeLock().unlock();
        }
    }

    @Override
    public BigInteger val() {
        lock.readLock().lock();
        try {
            // При отпущенном write lock
            // Допуст`им вход множества потоков
            return curr;
        } finally {
            lock.readLock().unlock();
        }
    }
}

Мы улучшили класс и добились больше высокой пропускной способности на чтение. У такой реализации есть все минусы локов. К тому же, из минусов добавилось то, что алгорифм усложнился (добавилось шума, не связанного с логикой работы) и вероятность некорректной реализации усилилась.

Lock-free algorithms

Применение локов влечет массу задач с продуктивностью и корректностью. Существует альтернатива в виденеблокирующих алгорифмов. Такие алгорифмы возведены на атомарных операциях, предоставляемых процессорами. Примером служит способ get в ConcurrentHashMap. Дабы писать неблокирующие алгорифмы, имеет толк воспользоваться существующими неблокирующими классами: ConcurrentLinkedQueue, ConcurrentHashMap и т.п. Напишем неблокирующую реализацию нашего класса.

public class LockFree implements FibonacciGenerator<BigInteger> {

    // Инкапсулируем состояние генератора в класс
    private static class State {
        final BigInteger next;
        final BigInteger curr;

        public State(BigInteger curr, BigInteger next) {
            this.next = next;
            this.curr = curr;
        }
    }

    // Сделаем состояние класса атомарным
    private final AtomicReference<State> atomicState = new AtomicReference<>(
            new State(BigInteger.ONE, BigInteger.ONE));

    public BigInteger next() {
        BigInteger value = null;
        while (true) { 
            // сберегаем состояние класса 
            State state = atomicState.get();
            // то что возвращаем если удалось изменить состояние класса
            value = state.curr; 
            // конструируем новое состояние
            State newState = new State(state.next, state.curr.add(state.next));
            // если за время пока мы конструировали новое состояние
            // оно осталось бывшим, то заменяем состояние на новое,
            // напротив пробуем сконструировать еще раз
            if (atomicState.compareAndSet(state, newState)) {break;}
        }
        return value;
    }

    @Override
    public BigInteger val() {
        return atomicState.get().curr;
    }
}

Из плюсов такого подхода следует подметить увеличение продуктивности, по сопоставлению с блокирующими алгорифмами. А также, что не менее значимо, освобождение от недостатков локов. Минус в том, что неблокирующий алгорифм придумать значительно труднее.

Software Transactional Memory

Альтернативой неблокирующим алгорифмам является использование программной транзакционной памяти. Её применение схоже на применение транзакций при работе с базами данных. Доктрина достаточно таки новая (1995) и среди знаменитых языков, нативная помощь есть только в Clojure. Помощь STM на ярусе библиотек есть во многих языках, в том числе и Java. Я буду применять STM, реализованный в рамках плана Akka.

public class STM implements FibonacciGenerator<BigInteger> {

    // Оборачиваем переменные в транзакционные ссылки
    // система будет отслеживать метаморфозы этих переменных внутри транзакции
    private final Ref<BigInteger> curr = new Ref<>(BigInteger.ONE);
    private final Ref<BigInteger> next = new Ref<>(BigInteger.ONE);

    @Override
    public BigInteger next() {
        // Создаем транзакцию
        return new Atomic<BigInteger>() {
            // Метаморфозы внутри способа 
            // будут владеют АСI (https://en.wikipedia.org/wiki/ACID)
            @Override
            public BigInteger atomically() {
                // Все значения отслеживаемых переменных согласованы
                BigInteger result = curr.get();
                // Метаморфозы не видны иным потокам
                curr.set(next.get());
                next.set(result.add(next.get()));
                // Проверяется были ли метаморфозы над отслеживаемыми
                // переменными. Если да, то нас опередили, но мы
                // оптимистичны и повторяем транзакцию еще раз.
                // Если мы первые, то атомарно записываем новые значения.
                return result;
            }
        // и исполняем ее
        }.execute();
    }

    @Override
    public BigInteger val() {
        // Транзакция создается неявно
        return curr.get();
    }

}

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

Immutability

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

public class Immutable {

    private final BigInteger next;
    // Нынешнее значение
    public final BigInteger val;

    private Immutable(BigInteger next, BigInteger val) {
        this.next = next;
        this.val = val;
    }

    public Immutable next() {
        return new Immutable(val.add(next), next);
    }

    public static Immutable first() {
        return new Immutable(BigInteger.ONE, BigInteger.ONE);
    }

}

Как вы подметили, интерфейс класса изменился и это затребует других методов работы с ним.

Isolated mutability

Идея изолированной изменяемости объектов состоит в том, что доступ к ним лимитирован неизменно одним потоком. Следственно у нас не возникнет задач, характерных для многопоточных программ. Такой подход использует модель акторов. Акторы — это сущности схожие на объекты, у которых есть изменяемое состояние и поведение. Взаимодействие акторов происходит через асинхронную передачу сообщений. Сообщения неизменяемы и актор обрабатывает одно сообщение за раз. Итогом обработки сообщения является метаморфоза поведения, состояния и выполнение других действий. Пример применения акторов будет приведен в дальнейшей статье.

Вывод

У всякого подхода есть свои минусы и плюсы и невозможно дать универсального совета.
Комбинация fine-grained локов и неблокирующих алгорифмов, особенно Зачастую применяемый подход в Java. В Clojure же наоборот — транзакционная память и неизменяемые конструкции данных. Транзакционная память, на мой взор, перспективный инструмент (предлагаю читателю независимо провести параллель со сборкой мусора). Верю, что при дальнейшем проектировании системы, модуля либо класса, вы припомните подходы, описанные в данной статье, и выберите подходящий именно вам.

Спасибо за внимание. Ожидаю ваших примечаний и предложений.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB