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

Пригодные идиомы многопоточности С

Anna | 25.06.2014 | нет комментариев
Данная статья является продолжением цикла статей: Применение паттерна синглтон [1]Синглтон и время жизни объекта [2]Обращение зависимостей и порождающие образцы проектирования [3]Реализация синглтона в многопоточном приложении [4]. Теперь я хотел бы побеседовать о многопоточности. Эта тема настоль объемна и многогранна, что охватить ее всю не представляется допустимым. Тут я заострю внимание на некоторых практичных вещах, которые дозволят вообще не думать о многопоточности, ну либо думать о ней в весьма минимальном объеме. Если говорить вернее, то думать о ней только на этапе проектирования, но не реализации. Т.е. будут рассмотрены вопросы о том, как сделать так, Дабы механически вызывались положительные конструкции без головной боли. Такой подход, в свою очередь, разрешает гораздо уменьшить задачи, вызванные состояниями гонок (race condition, см. Состояние гонки [5]) и взаимными блокировками (deadlock, см. Взаимная блокировка [6]). Данный факт теснее сам по себе представляет немалую ценность. Также будет рассмотрен подход, тот, что разрешает иметь доступ к объекту из нескольких потоков единовременно без применения каких-либо блокировок и атомарных операций!

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

Изложение интерфейса мьютекса:

struct Mutex
{
    void lock();
    void unlock();

private:
    // OS specific
    ...
};
RAII примитив (exception-safe):

struct Lock
{
    Lock(Mutex& mutex_) : mutex(mutex_) { mutex.lock(); }
    ~Lock()                             { mutex.unlock(); }
private:
    Mutex& mutex;
};
Класс для измывательств в качестве простого примера:

struct A
{
    int data;
    mutable Mutex m;
};

Примеры применения:

Пример 1. Простейший подход: C-style

A a;
a.m.lock();
a.data = 10;
a.m.unlock();
Пример 2. Продвинутый подход: RAII-style

A a;
{
    Lock lock(a.m);
    a.data = 10;
}
Пример 3. Фактически идеал: инкапсуляция локов

struct B
{
    void setData(int data_)
    {
        Lock lock(m);
        data = data_;
    }

    int getData() const
    {
        Lock lock(m);
        return data;
    }

private:
    mutable Mutex m;
    int data;
};

B b;
b.setData(10);
int x = b.getData();

Тут стоит подметить, что конечный вариант редко встретишь в статьях про многопоточность, что является дюже грустным фактом: Многопоточность, всеобщие данные и мьютексы [9]Кросс-платформенные многопоточные приложения [10]Потоки, блокировки и условные переменные в C 11 (Часть 2) [11]. В этой статье будут рассмотрены интересные вопросы, которые помогут значительно упростить работу с многопоточными примитивами (см. Потоки, блокировки и условные переменные в C 11 (Часть 1) [12]Два примитивных правила для предотвращения взаимных блокировок на мьютексах [13]). В чем-то данная статья будет являться становлением идей, взятых из Enforcing Correct Mutex Usage with Synchronized Values [14]. Впрочем приведенные ниже идеи и методы реализации были разработаны самостоятельно от приведенной статьи.

Инвариант

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

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

Предположим, что у нашего класса есть способ isValid, тот, что возвращает true в случае сохранения инварианта, и false — когда инвариант нарушен. Разглядим дальнейший “неотрицательный” счетчик:

struct Counter
{
    Counter() : count(0) {}

    bool isValid() const
    {
        return count >= 0;
    }

    int get() const
    {
        return count;
    }

    void set(int newCount)
    {
        count = newCount;
    }

    void inc()
    {
           count;
    }

    void dec()
    {
        -- count;
    }

private:
    int count;
};

Применение:

Counter c;
c.set(5);
assert(c.isValid());    // вернет true
c.set(-3);
assert(c.isValid());    // вернет false и сработает assert

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

Тут мы будем применять инструментарий, разработанный в предыдущих циклах статей: Применение паттерна синглтон [1]Синглтон и время жизни объекта [2]Обращение зависимостей и порождающие образцы проектирования [3]Реализация синглтона в многопоточном приложении [4]. Ниже приведу для справки реализацию, которая подвергнется припарированию:

An.hpp

#ifndef AN_HPP
#define AN_HPP

#include <memory>
#include <stdexcept>
#include <string>

// декларативные определения, см. [1]
#define PROTO_IFACE(D_iface, D_an)    
    template<> void anFill<D_iface>(An<D_iface>& D_an)

#define DECLARE_IMPL(D_iface)    
    PROTO_IFACE(D_iface, a);

#define BIND_TO_IMPL(D_iface, D_impl)    
    PROTO_IFACE(D_iface, a) { a.create<D_impl>(); }

#define BIND_TO_SELF(D_impl)    
    BIND_TO_IMPL(D_impl, D_impl)

// Стержневой класс, реализующий подход DIP - dependency inversion principle
template<typename T>
struct An
{
    template<typename U>
    friend struct An;

    An()                                             {}

    template<typename U>
    explicit An(const An<U>& a) : data(a.data)       {}

    template<typename U>
    explicit An(An<U>&& a) : data(std::move(a.data)) {}

    T* operator->()                                  { return get0(); }
    const T* operator->() const                      { return get0(); }
    bool isEmpty() const                             { return !data; }
    void clear()                                     { data.reset(); }
    void init()                                      { if (!data) reinit(); }
    void reinit()                                    { anFill(*this); }

    T& create()                                      { return create<T>(); }

    template<typename U>
    U& create()                                      { U* u = new U; data.reset(u); return *u; }

private:
    // извлекает объект
    // при первом доступе происходит его заполнение
    // с применением внешней функции anFill,
	// которая должна быть переопределена для
	// всякого определенного типа T
    T* get0() const
    {
        // ленивая инициализации при первом доступе к объекту
        const_cast<An*>(this)->init();
        return data.get();
    }

    std::shared_ptr<T> data;
};

// заливка экземпляра, см. [1]
// по умолчанию кидается исключение
// нужно переопределять, применяя макросы выше
// заливать дозволено как новые экземпляры,
// так и синглтоны. см. [3]
template<typename T>
void anFill(An<T>& a)
{
    throw std::runtime_error(std::string("Cannot find implementation for interface: ")
              typeid(T).name());
}

#endif

Для того, Дабы иметь вероятность проверять консистентность, модифицируем доступ к объекту (приватный способ get0) дальнейшим образом:

template<typename T>
struct An
{
    // ...
    T* get0() const
    {
        const_cast<An*>(this)->init();
        assert(data->isValid());    // добавляем assert
        return data.get();
    }
    // ...
};

Все отлично, происходит проверка. Но вот напасть: она происходит не позже метаморфозы, а до. Таким образом, объект может оказаться в неконсистентном состоянии, и только дальнейший вызов сделает свою работу:

c->set(2);
c->set(-2);   // тут assert не сработает 
c->set(1);    // и только тут он сработает, правда значение теснее валидно!

Хочется, Дабы проверка происходила позже метаморфозы, а не до. Для этого будем применять прокси-объект, в деструкторе которого будет протекать надобная проверка:

template<typename T>
struct An
{
    // ...
    struct Access
    {
        Access(T& ref_) : ref(ref_) {}

        ~Access()
        {
            assert(ref.isValid());
        }

        T* operator->()             { return &ref; }

    private:
        T& ref;
    };

    // соответственно, вызов (только неконстантный, т.к. константный не должен менять значение):
    Access operator->()             { return *get0(); }

    // ...
};

Применение:

An<Counter> c;
c->set(2);
c->set(-2);        // сейчас assert сработает тут
c->set(1);

Что и требовалось.

Разумный мьютекс

Перейдем сейчас к нашим многопоточным задачам. Напишем новую реализацию мьютекса и назовем его “умным” по аналогии с разумным указателем. Идея разумного мьютекста в том, Дабы он брал на себя всю “грязную” работу по работе с объектом, а нам лишь оставалась самая аппетитная часть.

Для его приготовления нам понадобится “обычный” мьютекс (так же, как и для мудрого указателя нужен обыкновенный указатель):

// noncopyable
struct Mutex
{
// публичный интерфейс мьютекса
    void lock();
    void unlock();

private:
    // ...
};

Сейчас улучшим наработки, применяемые ранее при проверке инварианта. Для этого будем применять не только деструктор прокси-класса, но и конструктор:

template<typename T>
struct AnLock
{
    // ...
    template<typename U>
    struct Access
    {
        // в конструкторе захватываем мьютекс
        Access(const An& ref_) : ref(ref_)
        {
            ref.mutex->lock();
        }

        // в деструкторе мьютекс механически освобождаем
        ~Access()
        {
            ref.mutex->unlock();
        }

        U* operator->() const                { return ref.get0(); }

    private:
        const An& ref;
    };

    // изменяем реализацию операторов доступа к объекту
    Access<T> operator->()                   { return *this; }
    Access<const T> operator->() const       { return *this; }

    // модифицируем функцию создания
    template<typename U>
    U& create()                              { U* u = new U; data.reset(u); mutex.reset(new Mutex); return *u; }

private:
    // ...
    std::shared_ptr<T> data;
    std::shared_ptr<Mutex> mutex;
};

Применение:

AnLock<Counter> c;
c->set(2);    // изменяем значение
std::cout << "Extracted value: " << c->get() << std::endl;

Стоит подметить, что при применении константной ссылки метаморфоза значения будет приводить к ошибке компиляции (в различие от прямого применения shared_ptr):

const AnLock<Counter>& cc = c;
cc->set(3); // эта строчка не скомпилируется

Разглядим, что же у нас получилось. Добавив итог на экран для способов класса Counter и Mutex, получаем дальнейший итог на экран при изменении значения:

Mutex::lock
Counter::set: 2
Mutex::unlock

Последовательность действий при итоге на экран:

Mutex::lock
Counter::get: 2
Extracted value: 2
Mutex::unlock

Удобство налицо: взамен очевидного вызова мьютекса мы легко трудимся с объектом как-словно никакого мьютекса нет, а внутри происходит все, что необходимо.

Дозволено спросить: а что делать, если мне нужно, скажем, 2 раза вызвать inc, причем сделать это атомарно? Нет задач! Добавим вначале в наш класс AnLock парочку typedef для комфорта:

template<typename T>
struct AnLock
{
    // ...
    typedef Access<T> WAccess;         // доступ на запись
    typedef Access<const T> RAccess;   // доступ на чтение
    // ...
};

А после этого используем следующую конструкцию:

{
    AnLock<Counter>::WAccess a = c;
    a->inc();
    a->inc();
}

Что, в свою очередь, дает дальнейший итог:

Mutex::lock
Counter::inc: 1
Counter::inc: 2
Mutex::unlock

Чем-то напоминает транзакцию, не так ли?

Разумный RW-мьютекс

Выходит, сейчас мы можем испробовать реализовать несколько больше трудную конструкцию под наименованием read-write mutex (см. Readers–writer lock [7]). Суть применения довольно простая: допускать вероятность чтения данных объекта из нескольких потоков, в то время как одновременное чтение и запись либо запись и запись обязаны быть запрещены.

Представим, у нас есть теснее реализация RWMutex с таким интерфейсом:

// noncopyable
struct RWMutex
{
// публичный интерфейс мьютекса

// для чтения
    void rlock();
    void runlock();    

// для записи
    void wlock();
    void wunlock();

private:
    // ...
};

Казалось бы, все, что нужно сделать, это слегка изменить реализацию, Дабы наши прокси-типы RAccess иWAccess применяли различные функции:

template<typename T>
struct AnRWLock
{
    // ...

    // доступ при чтении
    struct RAccess
    {
        RAccess(const AnRWLock& ref_) : ref(ref_)
        {
            ref.mutex->rlock();
        }

        ~RAccess()
        {
            ref.mutex->runlock();
        }

        const T* operator->() const       { return ref.get0(); }

    private:
        const AnRWLock& ref;
    };

    // доступ при записи
    struct WAccess
    {
        WAccess(const AnRWLock& ref_) : ref(ref_)
        {
            ref.mutex->wlock();
        }

        ~WAccess()
        {
            ref.mutex->wunlock();
        }

        T* operator->() const             { return ref.get0(); }

    private:
        const AnRWLock& ref;
    };

    WAccess operator->()                  { return *this; }
    RAccess operator->() const            { return *this; }

    // ...

    // модифицируем функцию создания
    template<typename U>
    U& create()                           { U* u = new U; data.reset(u); mutex.reset(new RWMutex); return *u; }

private:
    // ...
    std::shared_ptr<T> data;
    std::shared_ptr<RWMutex> mutex;
};

Применение:

AnRWLock<Counter> c;
c->set(2);

Итог:

RWMutex::wlock
Counter::set: 2
RWMutex::wunlock

Пока все отменно! Но дальнейший код:

std::cout << "Extracted value: " << c->get() << std::endl;

Дает:

RWMutex::wlock
Counter::get: 2
Extracted value: 2
RWMutex::wunlock

Для некоторых это не станет неожиданностью, а для остальной части я поясню, отчего здесь не работает так, как ожидалось. чай мы применяли константный способ, следственно по идее должен был быть использован константный способ operator->. Впрочем, компилятор так не считает. И связано это с тем, что операции используются ступенчато: вначале используется операция -> к неконстантному объекту, а после этого вызывается константный способ Counter::get, но поезд ушел, т.к. неконстантный operator-> теснее был вызван.

В качестве банального решения дозволено предложить вариант с приведением типа к константному перед обращением к объекту:

const AnRWLock<Counter>& cc = c;
std::cout << "Extracted value: " << cc->get() << std::endl;

С итогом:

RWMutex::rlock
Counter::get: 2
Extracted value: 2
RWMutex::runlock

Но выглядит это решение, мягко говоря, не дюже притягательно. Хочется писать легко и коротко, а не применять массивные конструкции при всяком обращении к константным способам.

Для решения этой задачи введем новейший оператор длинная стрелка --->, тот, что бы осуществлял запись в объект, т.е. доступ к неконстантным способам, а обыкновенную (короткую) стрелку -> оставим для чтения. Аргументы применения короткой стрелки для чтения и длинной — для записи, а не напротив, следующие:

  1. Визуальный. Сразу видно, где какая операция применяется.
  2. Смысловой. Чтение — это как бы поверхностное применение объекта: потрогал и отпустил. А запись — это больше глубинная операция, метаморфоза, так сказать, внутренностей, следственно и стрелка длиннее.
  3. Прагматичный. При замене обыкновенного мьютекса на RW-мьютекс нужно легко исправить ошибки компиляции, заменив короткую стрелку на длинную в этих местах, и все будет трудиться особенно оптимальным образом.

Здесь, вероятно, внимательный читатель задался вопросом: а где взять такую же травку, как и у автора статьи? чай

Давайте глядеть на реализацию:

// длинная стрелка, запись:
WAccess operator--(int)         { return *this; }
// короткая стрелка, чтение:
RAccess operator->() const      { return *this; }

Применение:

AnRWLock<Counter> c;
// не будет компилироваться: c->set(2)
c--->set(2);

Последовательность действий:

RWMutex::wlock
Counter::set: 2
RWMutex::wunlock

Все как и прежде, за исключением применения длинной стрелки. Глядим дальше:

std::cout << "Extracted value: " << c->get() << std::endl;
RWMutex::rlock
Counter::get: 2
Extracted value: 2
RWMutex::runlock

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

Если читатель не вовсе разобрался, как это работает

Если читатель не вовсе разобрался, как это работает, то я приведу дальнейший равнозначный код применения “длинной” стрелки в качестве подсказки:

(c--)->set(2);

Copy-on-write

Дальше разглядим следующую увлекательную и пригодную идиому: copy-on-write (COW), либо Копирование при записи [8]. Как ясно из наименования, основная идея заключается в том, что непринужденно перед изменением данных некоторого объекта вначале происходит копирование в новое место памяти, и теснее после этого метаморфоза данных по новому адресу.

Правда подход COW не связан непринужденно с многопоточностью, тем не менее, применение такого подхода коллективно с другими гораздо улучшает удобство работы и добавляет ряд необходимых элементов. Именно следственно ниже приводится реализация COW. Больше того, разработанные трюки легко и непосредственно переносятся на реализацию этой идиомы.

Выходит, как и для RW-мьютекса, нам нужно отличать операции чтения от операции записи. При чтении ничего особенного не должно протекать, а вот при записи, если у объекта больше одного обладателя, то заранее нужно данный объект скопировать.

template<typename T>
struct AnCow
{
    // ...

    // запись с применением длинной стрелки
    T* operator--(int)            { return getW0(); }
    // чтение с применением короткой стрелки
    const T* operator->() const   { return getR0(); }

    // функция клонирования (только для неполиморфных объектов!)
    void clone()                  { data.reset(new T(*data)); }

    // ...
private:
    T* getR0() const
    {
        const_cast<An*>(this)->init();
        return data.get();
    }

    T* getW0()
    {
        init();
        // клонирование в случае “неуникальности” объекта
        if (!data.unique())
            clone();
        return data.get();
    }

Стоит обратить внимание, что тут не рассматривается применение полиморфных объектов (т.е. никогда не создаем преемников шаблонного класса T), т.к. это выходит за рамки данной статьи. В дальнейшей статье я постараюсь дать детальное решение этого вопроса, при этом реализация будет довольно странной.

Перейдем к применению:

Код Итог в консоли
AnCow<Counter> c;
c--->set(2);
Counter::set: 2
std::cout << "Extracted value: " << c->get() << std::endl;
Counter::get: 2
Extracted value: 2
AnCow<Counter> d = c;
std::cout << "Extracted value: " << d->get() << std::endl;
Counter::get: 2
Extracted value: 2
d--->inc();
Counter copy ctor: 2
Counter::inc: 3
c--->dec();
Counter::dec: 1

В самом начале не происходит ничего увлекательного: установка значения и итог на экран этого же значения — 2. Дальше происходит присвоение значения новой переменной, при этом данные объекта применяются одни и те же. При итоге значения d->get() применяется тот же самый объект.

Дальше при вызове d--->inc() происходит самое увлекательное: вначале копируется объект, а после этого получившееся значение возрастает до 3-х. При дальнейшем вызове c--->dec() копирования не происходит, т.к. обладатель сейчас только один и у нас имеется две разные копии объекта. Думаю, данный пример наглядно иллюстрирует работу COW.

Key-value хранилище в памяти

Напоследок разглядим некоторые вариации реализации key-value хранилища в памяти при работе в многопоточной среде с применением разработанных методологий.

Будем применять следующую реализацию для наших хранилищ:

template<typename T_key, typename T_value>
struct KeyValueStorageImpl
{
    // добавление значения в хранилище
    void set(T_key key, T_value value)
    {
        storage.emplace(std::move(key), std::move(value));
    }

    // приобретение значения
    T_value get(const T_key& key) const
    {
        return storage.at(key);
    }

    // удаление значения
    void del(const T_key& key)
    {
        storage.erase(key);
    }

private:
    std::unordered_map<T_key, T_value> storage;
};

Привяжем хранилище к синглтону для облегчения дальнейших манипуляций (см. Применение паттерна синглтон [1]):

template<typename T_key, typename T_value>
void anFill(AnRWLock<KeyValueStorageImpl<T_key, T_value>>& D_an)
{
    D_an = anSingleRWLock<KeyValueStorageImpl<T_key, T_value>>();
}

Таким образом, при создании экземпляра AnRWLock<KeyValueStorageImpl<T,V>> будет “заливаться” объект, извлеченный из синглтона, т.е. AnRWLock<KeyValueStorageImpl<T,V>> неизменно будет указывать на исключительный экземпляр.

Для справки приведу используемую инфраструктуру:

AnRWLock.hpp

#ifndef AN_RWLOCK_HPP
#define AN_RWLOCK_HPP

#include <memory>
#include <stdexcept>
#include <string>

#include "Mutex.hpp"

// fill
#define PROTO_IFACE_RWLOCK(D_iface, D_an)    
    template<> void anFill<D_iface>(AnRWLock<D_iface>& D_an)

#define DECLARE_IMPL_RWLOCK(D_iface)    
    PROTO_IFACE_RWLOCK(D_iface, a);

#define BIND_TO_IMPL_RWLOCK(D_iface, D_impl)    
    PROTO_IFACE_RWLOCK(D_iface, a) { a.create<D_impl>(); }

#define BIND_TO_SELF_RWLOCK(D_impl)    
    BIND_TO_IMPL_RWLOCK(D_impl, D_impl)

#define BIND_TO_IMPL_SINGLE_RWLOCK(D_iface, D_impl)    
    PROTO_IFACE_RWLOCK(D_iface, a) { a = anSingleRWLock<D_impl>(); }

#define BIND_TO_SELF_SINGLE_RWLOCK(D_impl)    
    BIND_TO_IMPL_SINGLE_RWLOCK(D_impl, D_impl)

template<typename T>
struct AnRWLock
{
    template<typename U>
    friend struct AnRWLock;

    struct RAccess
    {
        RAccess(const AnRWLock& ref_) : ref(ref_)
        {
            ref.mutex->rlock();
        }

        ~RAccess()
        {
            ref.mutex->runlock();
        }

        const T* operator->() const            { return ref.get0(); }

    private:
        const AnRWLock& ref;
    };

    struct WAccess
    {
        WAccess(const AnRWLock& ref_) : ref(ref_)
        {
            ref.mutex->wlock();
        }

        ~WAccess()
        {
            ref.mutex->wunlock();
        }

        T* operator->() const                  { return ref.get0(); }

    private:
        const AnRWLock& ref;
    };

    AnRWLock()                                 {}

    template<typename U>
    explicit AnRWLock(const AnRWLock<U>& a) : data(a.data) {}

    template<typename U>
    explicit AnRWLock(AnRWLock<U>&& a) : data(std::move(a.data)) {}

    WAccess operator--(int)                    { return *this; }
    RAccess operator->() const                 { return *this; }
    bool isEmpty() const                       { return !data; }
    void clear()                               { data.reset(); }
    void init()                                { if (!data) reinit(); }
    void reinit()                              { anFill(*this); }

    T& create()                                { return create<T>(); }

    template<typename U>
    U& create()                                { U* u = new U; data.reset(u); mutex.reset(new RWMutex); return *u; }

private:
    T* get0() const
    {
        const_cast<AnRWLock*>(this)->init();
        return data.get();
    }

    std::shared_ptr<T> data;
    std::shared_ptr<RWMutex> mutex;
};

template<typename T>
void anFill(AnRWLock<T>& a)
{
    throw std::runtime_error(std::string("Cannot find implementation for interface: ")
              typeid(T).name());
}

template<typename T>
struct AnRWLockAutoCreate : AnRWLock<T>
{
    AnRWLockAutoCreate()                       { this->create(); }
};

template<typename T>
AnRWLock<T> anSingleRWLock()
{
    return single<AnRWLockAutoCreate<T>>();
}

#endif

AnCow.hpp

#ifndef AN_COW_HPP
#define AN_COW_HPP

#include <memory>
#include <stdexcept>
#include <string>

// fill
#define PROTO_IFACE_COW(D_iface, D_an)    
    template<> void anFill<D_iface>(AnCow<D_iface>& D_an)

#define DECLARE_IMPL_COW(D_iface)    
    PROTO_IFACE_COW(D_iface, a);

#define BIND_TO_IMPL_COW(D_iface, D_impl)    
    PROTO_IFACE_COW(D_iface, a) { a.create<D_impl>(); }

#define BIND_TO_SELF_COW(D_impl)    
    BIND_TO_IMPL_COW(D_impl, D_impl)

#define BIND_TO_IMPL_SINGLE_COW(D_iface, D_impl)    
    PROTO_IFACE_COW(D_iface, a) { a = anSingleCow<D_impl>(); }

#define BIND_TO_SELF_SINGLE_COW(D_impl)    
    BIND_TO_IMPL_SINGLE_COW(D_impl, D_impl)

template<typename T>
struct AnCow
{
    template<typename U>
    friend struct AnCow;

    AnCow()                                    {}

    template<typename U>
    explicit AnCow(const AnCow<U>& a) : data(a.data) {}

    template<typename U>
    explicit AnCow(AnCow<U>&& a) : data(std::move(a.data)) {}

    T* operator--(int)                         { return getW0(); }
    const T* operator->() const                { return getR0(); }
    bool isEmpty() const                       { return !data; }
    void clear()                               { data.reset(); }
    void init()                                { if (!data) reinit(); }
    void reinit()                              { anFill(*this); }

    T& create()                                { return create<T>(); }

    template<typename U>
    U& create()                                { U* u = new U; data.reset(u); return *u; }

    // TODO: update clone functionality on creating derived instances
    void clone()                               { data.reset(new T(*data)); }

private:
    T* getR0() const
    {
        const_cast<AnCow*>(this)->init();
        return data.get();
    }

    T* getW0()
    {
        init();
        if (!data.unique())
            clone();
        return data.get();
    }

    std::shared_ptr<T> data;
};

template<typename T>
void anFill(AnCow<T>& a)
{
    throw std::runtime_error(std::string("Cannot find implementation for interface: ")
              typeid(T).name());
}

template<typename T>
struct AnCowAutoCreate : AnCow<T>
{
    AnCowAutoCreate()                          { this->create(); }
};

template<typename T>
AnCow<T> anSingleCow()
{
    return single<AnCowAutoCreate<T>>();
}

#endif

Дальше будут рассмотрены разные методы применения этого хранилища, от простого к трудному.

Пример 1. Простейшее применение.

Будем непринужденно применять хранилище без дополнительных изысков:

// для простоты объявим класс для последующего применения
template<typename T_key, typename T_value>
struct KeyValueStorage : AnRWLock<KeyValueStorageImpl<T_key, T_value>>
{
    typedef T_value ValueType;
};

Пример применения:

Код Итог в консоли
// ключ - имя
// значение - возраст
KeyValueStorage<std::string, int> kv;
kv--->set("Peter", 28);
RWMutex::wlock
Key-value: inserting key: Peter
RWMutex::wunlock
kv--->set("Nick", 25);
RWMutex::wlock
Key-value: inserting key: Nick
RWMutex::wunlock
std::cout << "Peter age: " << kv->get("Peter") << std::endl;
RWMutex::rlock
Key-value: extracting key: Peter
Peter age: 28
RWMutex::runlock

В первой строчке мы создаем объект kv, в тот, что заливается исключительный экземпляр хранилища, применяя синглтон (см. функцию anFill). Дальше добавляются записи Peter и Nick, а после этого выводится возраст Peter.

Думаю, из итога ясно, что при записи механически берется write-lock, а при чтении — read-lock.

Пример 2. Вложенные RW-мьютексы.

Разглядим чуть больше трудный пример. Представим сейчас, что мы хотим завести именованные счетчикиCounter и применять их из нескольких потоков. Нет задач:

// объявляем новейший класс, тот, что может в себе беречь объекты с AnRWLock
template<typename T_key, typename T_value>
struct KeyValueStorageRW : KeyValueStorage<T_key, AnRWLock<T_value>>
{
};

// объявим тип для наших счетчиков
typedef KeyValueStorageRW<std::string, Counter> KVRWType;

Пример применения:

Код Итог в консоли
KVRWType kv;
// AnRWLockAutoCreate - механическое создание экземпляра
kv--->set("users", AnRWLockAutoCreate<Counter>());
RWMutex::wlock
Key-value: inserting key: users
RWMutex::wunlock
kv--->set("sessions", AnRWLockAutoCreate<Counter>());
RWMutex::wlock
Key-value: inserting key: sessions
RWMutex::wunlock
kv->get("users")--->inc();
RWMutex::rlock
Key-value: extracting key: users
RWMutex::wlock
Counter::inc: 1
RWMutex::wunlock
RWMutex::runlock
kv->get("sessions")--->inc();
RWMutex::rlock
Key-value: extracting key: sessions
RWMutex::wlock
Counter::inc: 1
RWMutex::wunlock
RWMutex::runlock
kv->get("sessions")--->dec();
RWMutex::rlock
Key-value: extracting key: sessions
RWMutex::wlock
Counter::dec: 0
RWMutex::wunlock
RWMutex::runlock

Как говорится, вуаля!

Пример 3. Оптимизация доступа.

Правда о некоторых оптимизациях я хотел бы рассказать в дальнейшей статье, впрочем тут опишу, на мой взор, довольно значимую оптимизацию.

Ниже приведены разные варианты применения для сопоставления.

Вариант 1: обыкновенный
Код Итог в консоли
kv->get("users")--->inc();
RWMutex::rlock
Key-value: extracting key: users
RWMutex::wlock
Counter::inc: 2
RWMutex::wunlock
RWMutex::runlock
Вариант 2: наилучший
Код Итог в консоли
auto users = kv->get("users");
RWMutex::rlock
Key-value: extracting key: users
RWMutex::runlock
users--->inc();
RWMutex::wlock
Counter::inc: 3
RWMutex::wunlock

Во втором примере видно, что 2-й мьютекс на запись для объекта Counter берется только позже отпускания первого, тот, что контролирует key-value хранилище. Такая реализация обеспечивает больше оптимальное применение мьютексов, правда и получаем в итоге больше длинную запись. Эту оптимизацию стоит иметь в виду при применении вложенных мьютексов.

Пример 4. Помощь атомарности изменений.

Представим, что нам нужно атомарно увеличить на 100 один из счетчиков, скажем “users”. Безусловно, для этого дозволено позвать 100 раз операцию inc(), а дозволено сделать так:

Код Итог в консоли
auto c = kv->get("users");
RWMutex::rlock
Key-value: extracting key: users
RWMutex::runlock
KVRWType::ValueType::WAccess cw = c;
cw->set(cw->get()   100);
RWMutex::wlock
Counter::get: 4
Counter::set: 104
RWMutex::wunlock

Обратите внимание, что при применении WAccess дальше все операции идут с обыкновенной “короткой” стрелкой, т.к. доступ к объекту на запись теснее получен. Также стоит обратить внимание на то, что операции get и set идут под одним и тем же мьютексом, чего мы и хотели достичь. Это дюже схоже на то, что мы как словно открыли транзакцию при действии над объектом.

Данный же трюк дозволено применять коллективно с описанной выше оптимизацией для доступа непринужденно к счетчикам.

Вариант 1: обыкновенный
Код Итог в консоли
kv->get("users")--->inc();
RWMutex::rlock
Key-value: extracting key: users
RWMutex::wlock
Counter::inc: 4
RWMutex::wunlock
RWMutex::runlock
kv->get("sessions")--->dec();
RWMutex::rlock
Key-value: extracting key: sessions
RWMutex::wlock
Counter::dec: -1
RWMutex::wunlock
RWMutex::runlock
Вариант 2: наилучший
Код Итог в консоли
AnRWLock<Counter> c1, c2;
{
    KVRWType::RAccess r = kv;
    c1 = r->get("users");
    c2 = r->get("sessions");
}
RWMutex::rlock
Key-value: extracting key: users
Key-value: extracting key: sessions
RWMutex::runlock
c1--->inc();
RWMutex::wlock
Counter::inc: 5
RWMutex::wunlock
c2--->dec();
RWMutex::wlock
Counter::dec: -2
RWMutex::wunlock

Вновь же, во втором примере мьютексы применяются больше оптимально: read lock берется ровно один раз, write lock берется вне read-lock, что дает огромную продуктивность при конкурентном достсчетов.

В целом, дозволено было бы безусловно применять копирование всех элементов перед расчетом. Впрочем при наличии довольно большого числа информации это будет довольно долгая операция. Следственно она в обозначенном подходе откладывается до тех пор, пока подлинно нужно скопировать данные, т.е. только при их одновременном применении в расчетах и изменении.

Обзор и суммирование

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

COW в деталях

Разглядим последовательность операций последнего примера. Ниже приведена всеобщая схема при извлечении значения из контейнера:

Тут Data — это User в описанном выше примере, а shared_ptr<Data> — это содержимое объекта AnCow. Последовательность операций:

N Операция Изложение
1 lock Блокировка хранилища, делается механически при вызове operator->
2 copy Копирование shared_ptr<Data>, т.е. реально происходит примитивное увеличение счетчиков (use_count и weak_count внутри объекта shared_ptr<Data>)
3 unlock Снятие блокировки хранилища деструкторе временного объекта

Позже этих операций дозволено делать разные действия над объектом. При чтении никаких дополнительных действий не происходит: легко берем и считываем данные объекта непринужденно из занимаемой области данных. Здесь стоит упомянуть дюже непредвиденный нюанс: чтение данных объекта происходит без взятия блокировки! Это непредвиденное качество я и хотел подчеркнуть, разбирая COW.

Что же происходит при записи данных в объект. Глядим:

Последовательность операций при этом выглядит дальнейшим образом:

N Операция Изложение
4 clone Клонирование объекта, вызывается конструктор копирования объекта Data, т.е. копирование всех его полей в новую область памяти. Позже этой операции shared_ptr начинает глядеть на опять сделанный объект.
5 modify Непринужденно операция модификации. Может протекать долгое время, т.к. является неблокирующей.
6 lock Перед обновлением хранилища прозводится взятие блокировки.
7 replace Замена ветхого значения shared_ptr<Data> на новое, модифицированное на 5-м шаге.
8 unlock Снятие блокировки хранилища.

Как и в случае чтения, запись в объект происходит без участия блокировок, т.к. мы — исключительный обладатель сделанного объекта. В тезисе, ту же схему операций дозволено отслеживать при манипуляциях с объектом простого типа, скажем, типа int. Существеннmk!/th> Разумный мьютекс COW Доступ к полям объекта Блокируется на время чтения/записи Не блокируется Метаморфоза объекта в контейнере Метаморфоза “на месте” (in-place) Позже метаморфозы нужно положить новое значение обратно в контейнер

Итоги

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

  1. Простота. Нет необходимости очевидного применения многопоточных примитивов, все происходит автомагически.
  2. Эластичность. Решение применимо для широкого класса многопоточных задач с вероятностью комбинирования разных идиом. Тут также стоит упомянуть поддержку транзакционности (в памяти) на некотором исходном ярусе.
  3. Качество. Применение такого подхода разрешает значительно уменьшить число задач, связанных с состоянием гонки (race condition) и взаимной блокировки (deadlock). Состояния гонки устраняются наличием механических блокировок вследствие разумным мьютексам. Вероятность взаимной блокировки значительно уменьшается вследствие гранулярному (fine-grained) доступу к данным на всяком ярусе, и фиксированным механическим порядком захвата и снятия блокировок.

Такой многофункциональный подход стал допустим вследствие тому, что в реализации An-классов происходит полный контроль применения хранимых объектов. Следственно возникает вероятность добавлять необходимый функционал, механически вызывая на границах доступа нужные способы. Данный подход будет значительно углублен и расширен в дальнейшей статье.

В приведенном материале не рассматривалось применение полиморфных объектов. В частности, реализацияAnCow работает только с тем же шаблонным классом, т.к. неизменно вызывается конструктор копирования для объявленного типа T. В дальнейшей статье будет приведена реализация для больше всеобщего случая. Также будет проведена унификация объектов и методов их применения, рассказано о разных оптимизациях, о многопоточных ссылках, и многое другое.

Письменность

[1] Програпрогр: Применение паттерна синглтон
[2] Програпрогр: Синглтон и время жизни объекта
[3] Програпрогр: Обращение зависимостей и порождающие образцы проектирования
[4] Програпрогр: Реализация синглтона в многопоточном приложении
[5] Википедия: Состояние гонки
[6] Википедия: Взаимная блокировка
[7] Wikipedia: Readers–writer lock
[8] Википедия: Копирование при записи
[9] Програпрогр: Многопоточность, всеобщие данные и мьютексы
[10] Програпрогр: Кросс-платформенные многопоточные приложения
[11] Програпрогр: Потоки, блокировки и условные переменные в C 11 [Часть 2]
[12] Програпрогр: Потоки, блокировки и условные переменные в C 11 [Часть 1]
[13] Програпрогр: Два примитивных правила для предотвращения взаимных блокировок на мьютексах
[14] DrDobbs: Enforcing Correct Mutex Usage with Synchronized Values

P.S. Решение задачи про число копирований

Представим, на всяком из ярусов имеется n объектов, число ярусов — k, а всеобщее число элементов — a. Тогда число элементов a = n^k, либо k = ln a/ln nУменьшая ln получаем k = a/n. число копирований = n*k (нужно пройти всякий слой и скопировать на всяком слое n раз). Т.е. число копирований = n*ln a/ln nлибо легко n/ln n, т.к. a — const. Легко обнаружить локальный минимум, он достигается при n = e, что ближе каждого соответствует целому числу 3.

И напоследок — опрос. На повестке дня 2 вопроса:

Понравилась ли статья?
85%
(158)
Да, понравилась. Ожидаю продолжения.

15%
(27)
Ничего увлекательного, только напрасно потратил время на прочтение.

Проголосовало 185 человек. Воздержалось 60 человек.

?сно ли, откуда взялось число 3 для оптимизации числа операций копирования при рассмотрении вложенных COW-объектов?
17%
(14)
Да, я сам получил такое же число, все ясно.

83%
(69)
Нет, непостижимо. Итог в студию! (теснее в P.S.)

Проголосовало 83 человека. Воздержалось 92 человека.

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

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