c++ - 是否可以在不锁定或提供 future 的情况下进行查找或创建？

Question

我有以下情况(简化):

/* Register objects living
   and retrieve them on demand if the object is still alive on request.
   The interface have to be concurrency-safe.
*/
class Registry 
{
public: 

    void add( const std::shared_ptr<Thing>& thing ) 
    { m_index.emplace_back( thing );

    std::shared_ptr<Thing> find( ThingId id )
    {
       auto find_it = m_index.id( id );
       if( find_it != end( m_index ) )
       {
           // we can't remove the index safely (see http://software.intel.com/sites/products/documentation/doclib/tbb_sa/help/index.htm )
           return find_it->second.lock(); // null if the object don't exist anymore
       }
       return nullptr;
    }

private:
   tbb::concurrent_unordered_map< ThingId, std::weak_ptr<Thing> > m_index;
};

// Concurrency safe too.
class Workspace
{
    Registry m_registry;
    std::unique_ptr<Thing> make_new_thing( ThingId id ); // not important 
public:

    std::shared_ptr<Thing> find( ThingId id ) { return m_registry.find(id); }

    /* The goal here is to either retrieve the existing object, 
       or to create it.
    */
    std::shared_ptr<Thing> find_or_create( ThingId id )
    {
        // HERE IS THE PROBLEM!!!
        if( auto thing = m_registry.find( id ) )
            return thing;
        return make_new_thing();
    }
 };

 // Concurrency-safe too.
 class Editor
 {
     Workspace& m_workspace;
     tbb::concurrent_unordered_set<std::shared_ptr<Thing>> m_things;
 public: 

     void add_target( ThingId id )
     {
         m_things.push( m_workspace.find_or_create( id ) );
     }

 }; 

上下文很重要，但让我们关注这部分:

std::shared_ptr<Thing> find_or_create( ThingId id )
{
    if( auto thing = m_registry.find( id ) )
        return thing;
    return make_new_thing(); 
}

这里如果同时调用此函数，则可能会同时调用 make_new_thing()，如果 Thing 没有相同的 id，这是有效的，但如果没有，则无效。 由于 concurrent_unordered_map 的实现，我们无法从注册表中删除 id，因此我们无法检查对象是否正在创建。

所有这些都表明，在这种情况下，需要同步机制。但是，如果我使用工作队列之类的东西，那么我将不得不提供一个当前处于锁定状态的 future ，但即使使用 future.then() ，调用者也可能会等待很长时间。

我想要的是尽可能避免锁定(使用互斥量)，并且没有 future (在这种特殊情况下)。

你有没有不用锁定的方法？

Answer 1

您可以使用事物的数组或环形缓冲区，以及原子操作。内置原子内部或处理器特定的 CMPXCHG 汇编操作码。

您将牺牲内存并实质上创建您自己的互斥锁和自旋等待。

在最简单的实现中，您的 ThingId 将作为数组的索引。您的“查找或创建”将是一个比较+交换原子操作，如果数组中的位置为空，您将交换一个已经创建的新对象，但是如果该位置不为空，您将删除预先创建的新对象或保存它用于下一次调用，但这将需要更多原子操作来实现对象存储的并发。