Чтение-запись потокобезопасного интеллектуального указателя в C ++, x86-64 - PullRequest
Новая
       24

Чтение-запись потокобезопасного интеллектуального указателя в C ++, x86-64

5 голосов
/ 04 ноября 2011

Я разрабатываю некоторую структуру данных без блокировки, и возникает следующая проблема.

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

SmartPtr ptr;

class Reader : public Thread {
    virtual void Run {
       for (;;) {
           SmartPtr local(ptr);
           // do smth   
       }
    }   
};

class Writer : public Thread {
    virtual void Run {
       for (;;) {
           SmartPtr newPtr(new Object);    
           ptr = newPtr;  
       }
    }
};

int main() {
    Pool* pool = SystemThreadPool();
    pool->Run(new Reader());
    pool->Run(new Writer());
    for (;;) // wait for crash :(
}

Когда я создаю локальную копию потока ptr, это означает, как минимум,

  1. Чтение адреса.
  2. Инкрементсчетчик ссылок.

Я не могу выполнять эти две операции атомарно, и поэтому иногда мои читатели работают с удаленным объектом.

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

Для PowerPC я обнаружил http://drdobbs.com/184401888,выглядит красиво, но использует инструкции Load-Linked и Store-Conditional, которых нет в x86.

Насколько я понимаю, указатели boost предоставляют такую ​​функциональность только с помощью блокировок.Мне нужно решение без блокировки.

Ответы [ 4 ]

9 голосов
/ 04 ноября 2011

boost :: shared_ptr имеет atomic_store, который использует спин-блокировку без блокировки, которая должна быть достаточно быстрой для 99% возможных случаев. 

    boost::shared_ptr<Object> ptr;
class Reader : public Thread {
    virtual void Run {
       for (;;) {
           boost::shared_ptr<Object> local(boost::atomic_load(&ptr));
           // do smth   
       }
    }   
};

class Writer : public Thread {
    virtual void Run {
       for (;;) {
           boost::shared_ptr<Object> newPtr(new Object);    
           boost::atomic_store(&ptr, newPtr);
       }
    }
};

int main() {
    Pool* pool = SystemThreadPool();
    pool->Run(new Reader());
    pool->Run(new Writer());
    for (;;)
}

РЕДАКТИРОВАТЬ:

В ответ накомментарий ниже, реализация находится в "boost / shared_ptr.hpp" ... 

template<class T> void atomic_store( shared_ptr<T> * p, shared_ptr<T> r )
{
    boost::detail::spinlock_pool<2>::scoped_lock lock( p );
    p->swap( r );
}

template<class T> shared_ptr<T> atomic_exchange( shared_ptr<T> * p, shared_ptr<T> r )
{
    boost::detail::spinlock & sp = boost::detail::spinlock_pool<2>::spinlock_for( p );

    sp.lock();
    p->swap( r );
    sp.unlock();

    return r; // return std::move( r )
}
4 голосов
/ 04 ноября 2011

С некоторыми jiggery-pokery вы сможете сделать это, используя InterlockedCompareExchange128.Сохраните счетчик ссылок и указатель в массиве из двух элементов __int64.Если счетчик ссылок находится в массиве [0], а указатель - в массиве [1], атомарное обновление будет выглядеть так: 

while(true)
{
    __int64 comparand[2];
    comparand[0] = refCount;
    comparand[1] = pointer;
    if(1 == InterlockedCompareExchange128(
        array,
        pointer,
        refCount + 1,
        comparand))
    {
        // Pointer is ready for use. Exit the while loop.
    }
}

Если встроенная функция InterlockedCompareExchange128 недоступна для вашего компилятора, вы можете использоватьвместо этого лежащая в основе инструкция CMPXCHG16B, если вы не возражаете возиться на ассемблере.

2 голосов
/ 05 ноября 2011

Решение, предложенное RobH, не работает. У него та же проблема, что и у исходного вопроса: при доступе к объекту подсчета ссылок он, возможно, уже был удален.

Единственный способ решить проблему без глобальной блокировки (как в boost :: atomic_store) или инструкций условного чтения / записи - это каким-то образом отложить уничтожение объекта (или объекта общего подсчета ссылок, если такая вещь есть). используемый). Так что у Зеннехой есть хорошая идея, но его метод слишком небезопасен.

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

class Writer : public Thread {
    virtual void Run() {
        list<SmartPtr> ptrs; //list that holds all the old ptr values        

        for (;;) {
            SmartPtr newPtr(new Object);
            if(ptr)
                ptrs.push_back(ptr); //push previous pointer into the list
            ptr = newPtr;

            //Periodically go through the list and destroy objects that are not
            //referenced by other threads
            for(auto it=ptrs.begin(); it!=ptrs.end(); )
                if(it->refCount()==1)
                    it = ptrs.erase(it);
                else
                    ++it;
       }
    }
};

Однако все еще существуют требования к классу интеллектуальных указателей. Это не работает с shared_ptr, так как чтение и запись не являются атомарными. Это почти работает с boost :: intrusive_ptr. Назначение для intrusive_ptr реализовано так (псевдокод): 

//create temporary from rhs
tmp.ptr = rhs.ptr;
if(tmp.ptr)
    intrusive_ptr_add_ref(tmp.ptr);

//swap(tmp,lhs)
T* x = lhs.ptr;
lhs.ptr = tmp.ptr;
tmp.ptr = x;

//destroy temporary
if(tmp.ptr)
    intrusive_ptr_release(tmp.ptr);

Насколько я понимаю, единственное, чего здесь не хватает, это ограничения памяти уровня компилятора до lhs.ptr = tmp.ptr;. При этом добавляются, что чтение rhs и запись lhs будут поточно-ориентированными при строгих условиях: 1) архитектура x86 или x64 2) атомарный подсчет ссылок 3) rhs refcount не должен обнуляться во время назначения (гарантировано по описанному выше коду Writer) 4) только один поток записывает в lhs (используя CAS вы можете иметь несколько писателей).

В любом случае, вы можете создать свой собственный класс интеллектуальных указателей на основе intrusive_ptr с необходимыми изменениями. Определенно проще, чем повторная реализация shared_ptr. И, кроме того, если вам нужна производительность, навязчивый путь.

0 голосов
/ 04 ноября 2011

Причина, по которой это намного проще работает в java, - сборка мусора. В C ++ вы должны вручную убедиться, что значение не только начинает использоваться другим потоком, когда вы хотите удалить его.

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

100 миллисекунд было бы достаточно в моем случае, я выбрал несколько секунд, чтобы быть в безопасности.

...