Concurrency: 6 способів жити з shared state

concurrency
 
У багатопотоковому програмуванні багато складнощів, основними з яких є робота 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

 
Перший спосіб зробити клас коректно працюють у багатопотокової середовищі — це використовувати блокування і оголосити всі методи 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;
    }

}
 

 
Ми отримали клас, який коректно працює в багатопотокової середовищі, витративши при цьому мінімум зусиль. У першу чергу, ми жертвуємо продуктивністю. Продуктивність класу така ж, як якби він запускався в однопоточному середовищі. До того ж, використання локов приносить проблеми, такі як: deadlock , livelock і т.п.
 
 

Fine-Grained locking

 
Наступний спосіб — розбити наші структури на частини і захистити локами тільки ті секції, в яких відбувається робота з розділяються станом. Прикладом такого підходу є СoncurrentHashMap . У ньому всі дані розбиваються на кілька частин. При доступі блокується тільки та частина, зміна якої відбувається в поточний момент. Також є варіант використовувати більш функціональні локи, такі як: StampedLock , ReadWriteLock . При коректних алгоритмі і реалізації ми отримуємо більш високий рівень паралелізму. Приклад з використанням 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 ж навпаки — транзакційна пам'ять і незмінні структури даних. Транзакційна пам'ять, на мій погляд, багатообіцяючий інструмент (пропоную читачеві самостійно провести аналогію із збіркою сміття). Сподіваюся, що при наступному проектуванні системи, модуля або класу, ви згадаєте підходи, описані в цій статті, і виберіть відповідний саме вам.
 
Спасибі за увагу. Чекаю ваших зауважень і пропозицій.

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.