views:

112

answers:

5

Hello,

I have to design a data structure that is to be used in a multi-threaded environment. The basic API is simple: insert element, remove element, retrieve element, check that element exists. The structure's implementation uses implicit locking to guarantee the atomicity of a single API call. After i implemented this it became apparent, that what i really need is atomicity across several API calls. For example if a caller needs to check the existence of an element before trying to insert it he can't do that atomically even if each single API call is atomic:

if(!data_structure.exists(element)) {
   data_structure.insert(element);
}

The example is somewhat awkward, but the basic point is that we can't trust the result of "exists" call anymore after we return from atomic context (the generated assembly clearly shows a minor chance of context switch between the two calls).

What i currently have in mind to solve this is exposing the lock through the data structure's public API. This way clients will have to explicitly lock things, but at least they won't have to create their own locks. Is there a better commonly-known solution to these kinds of problems? And as long as we're at it, can you advise some good literature on thread-safe design?

EDIT: I have a better example. Suppose that element retrieval returns either a reference or a pointer to the stored element and not it's copy. How can a caller be protected to safely use this pointer\reference after the call returns? If you think that not returning copies is a problem, then think about deep copies, i.e. objects that should also copy another objects they point to internally.

Thank you.

+3  A: 

You either provide a mechanism for external locking (bad), or redesign the API, like putIfAbsent. The latter approach is for instance used for Java's concurrent data-structures.

And, when it comes to such basic collection types, you should check-out whether your language of choice already offers them in its standard library.

[edit]To clarify: external locking is bad for the user of the class, as it introduces another source of potential bugs. Yes, there are times, when performance considerations indeed make matters worse for concurrent data-structures than externally synchronized one, but those cases are rare, and then they usually can only be solved/optimized by people with far more knowledge/experience than me.

One, maybe important, performance hint is found in Will's answer below. [/edit]

[edit2]Given your new example: Basically you should try to keep the synchronization of the collection and the of the elements separated as much as possible. If the lifetime of the elements is bound to its presence in one collection, you will run into problems; when using a GC this kind of problem actually becomes simpler. Otherwise you will have to use a kind of proxy instead of raw elements to be in the collection; in the simplest case for C++ you would go and use boost::shared_ptr, which uses an atomic ref-count. Insert usual performance disclaimer here. When you are using C++ (as I suspect as you talk about pointers and references), the combination of boost::shared_ptr and boost::make_shared should suffice for a while. [/edit2]

gimpf
Why is external locking bad? It may be that the user of the API knows more about when things need to be locked (for example, you might have an instance of the collection that isn't even shared between threads). For performance reasons, it might be perfectly reasonable to use external locking.
Michael Aaron Safyan
@Micheal: Yes, true. But external locking moves the burden to the user of a data structure. It all depends on the user. But, you're right, external locking is required in some cases, but even then I would use a plain non-concurrent data structure and do all locking externally.
frunsi
@frunsi, that is a good point... an object should either be threadsafe entirely or not-at-all. When I was thinking about external locking, I assumed that the datastructure would be made non-concurrent, but now that I reread the post, I see that the author was proposing some sort of hybrid, which would be very nasty indeed.
Michael Aaron Safyan
Sorry for the downvote. I would upvote it, but SO won't let me do so, now.
Michael Aaron Safyan
Yes, this happened to me too once; SO only lets you recast your vote within some time-limit, or after a substantial edit (or any edit, do not know). I hope I got the performance-issue a bit better now with the added text.
gimpf
A: 

What about moving the existance check into the .insert() method? A client calls it and if it returns false you know that something went wrong. Much like what malloc() does in plain old C -- return NULL if failed, set ERRNO.

Obviously you can also return an exception, or an instance of an object, and complicate your life up from there..

But please, don't rely on the user setting their own locks.

lorenzog
+1  A: 

Sometimes its expensive to create an element to be inserted. In these scenarios you can't really afford to routinely create objects that might already exist just in case they do.

One approach is for the [code]insertIfAbsent()[/code] method to return a 'cursor' that is locked - it inserts a place-holder into the internal structure so that no other thread can believe it is absent, but does not insert the new object. The placeholder can contain a lock so that other threads that want to access that particular element must wait for it to be inserted.

In an RAII language like C++ you can use a smart stack class to encapsulate the returned cursor so that it automatically rolls-back if the calling code does not commit. In Java its a bit more deferred with the [code]finalize()[/code] method, but can still work.

Another approach is for the caller to create the object that isn't present, but that to occasionally fail in the actual insertion if another thread has 'won the race'. This is how, for example, memcache updates are done. It can work very well.

Will
A: 

First of all, you should really separate your concerns. You have two things to worry about:

  1. The datastructure and its methods.
  2. The thread synchronization.

I highly suggest you use an interface or virtual base class that represents the type of datastructure you are implementing. Create a simple implementation that does not do any locking, at all. Then, create a second implementation that wraps the first implementation and adds locking on top of it. This will allow a more performant implementation where locking isn't needed and will greatly simplify your code.

It looks like you are implementing some sort of dictionary. One thing you can do is provide methods that have semantics that are equivalent to the combined statement. For example setdefault is a reasonable function to provide that will set a value only if the corresponding key does not already exist in the dictionary.

In other words, my recommendation would be to figure out what combinations of methods are frequently used together, and simply create API methods that perform that combination of operations atomically.

Michael Aaron Safyan
A: 

In an RAII style fashion you could create accessor/handle objects (don't know how its called, there probably exists a pattern of this), e.g. a List:

template <typename T>
class List {
    friend class ListHandle<T>;
    // private methods use NO locking
    bool _exists( const T& e ) { ... }
    void _insert( const T& e ) { ... }
    void _lock();
    void _unlock();
public:
    // public methods use internal locking and just wrap the private methods
    bool exists( const T& e ) {
        raii_lock l;
        return _exists( e );
    }
    void insert( const T& e ) {
        raii_lock l;
        _insert( e );
    }
    ...
};

template <typename T>
class ListHandle {
    List<T>& list;
public:
    ListHandle( List<T>& l ) : list(l) {
        list._lock();
    }
    ~ListHandle() {
        list._unlock();
    }
    bool exists( const T& e ) { return list._exists(e); }
    void insert( const T& e ) { list._insert(e); }
};


List<int> list;

void foo() {
    ListHandle<int> hndl( list ); // locks the list as long as it exists
    if( hndl.exists(element) ) {
        hndl.insert(element);
    }
    // list is unlocked here (ListHandle destructor)
}

You duplicate (or even triplicate) the public interface, but you give users the choice to choose between internal and safe and comfortable external locking wherever it is required.

frunsi
That's an overkill... if he wants to use locks at all, then he could just write an `insertIfNotFound` method: bool insertIfNotFound(T element){ lock.lock(); try { if(!data_structure.exists(element)) { data_structure.insert(element); return true; } return false } finally { lock.unlock(); } }
Lirik
@Lirik: whether it is overkill or not depends a lot on usage. In practice I do not use "concurrent" data-structures at all, but work with external locking more or less. But this thing here makes sense, if you have more complex requirements than `insertIf[not]Found` (those usage cases exist), then this way is fine. Also the overkill will be optimized away, so its just a lot of typing.
frunsi
*@frunsi* `insertIfNotFound` is mostly known as `putIfAbsent` which is a common method in concurrent data structures (clarifying myself there, I'm sure you've seen it). So your alternative to a concurrent data structure is external locking?
Lirik
@Lirik: My alternative is provided in my answer, in complete detail! Read it... answer is contained in it. `putIfAbsent` and/or any other `doIfBlabla` methods are fine for the usual cases, and help you solve most given problems, but my method (again, read my answer) is a general solution.
frunsi