2

I will immediately confess that I do very little multithreading, so questions of style and organization in this domain a little fresh to me.

I've written a data structure (in Python, if that matters) which implements a special kind of a queue. I'd like to use this queue to pass messages between threads. Currently, the only logic I have has nothing to do with threads, and simply implements the "special sauce" of organizing messages in this queue.

I like having this queue as a data structure that has nothing to do with threads, just like any other data structure. However, I need to use mutexes, condition variables, etc. to implement the thread safety logic. The question is, where does this logic go?

Do I write a class, say, SpecialQueueConcurrent derived from SpecialQueue? Do I write a class that wraps SpecialQueue instead of deriving from it? Do I provide an option to make it concurrent in the constructor?

How is this usually done?

4
  • 1
    I thought what I'd do was, I'd pretend I was one of those mutex-based data structures... I recently converted a singly-thread-safe scheduler (with internal queue) to a multi-thread-safe version with rescheduling coming in from a separate thread. To really get the best out of the structure, it would have been hard to use inheritance and just bolt on mutexes without some huge performance issues. In another case, I had a chunk of code where I abstracted the mutex with an alternative no-op version so that locking more or less turned into a policy: again, inheritance wouldn't have worked well.
    – J Trana
    May 23, 2014 at 5:11
  • Nice Salinger reference. Good advise, too.
    – Phonon
    May 23, 2014 at 5:27
  • Are you aware that the Python standard library has a perfectly good and thread-safe queue? What makes your queue so special that you can't use the general-purpose one?
    – user7043
    May 23, 2014 at 14:14
  • @delnan Yes. The data structure I wrote is much more than a queue, and I had to write it for a very specific need. Unfortunately, I can't elaborate. The fact that it's a queue is not the point. How to implement a thread safe queue is not the question. The question is purely that of code organization.
    – Phonon
    May 23, 2014 at 18:46

1 Answer 1

3

It depends on the use-cases of the data structure, and any restrictions of that use you need to comply to (about that latter).

The use-cases

There are a few use cases that could determine the correct approach in choosing or implementing a concurrent data structure yourself. You need to consider:

  • The concurrency implementation supported by the structure:

    • Strict locking could guarantee supreme data consistency at the price of locks and can create performance bottlenecks.
    • Lock-free concurrent collections are special implementations that work without locks, but have (in most cases acceptable) possibility of one thread not reading the changes of the other. These are not the same as the case of using a standard collection without locks, as the lock-free collection would not allow the collection itself to become corrupted. With lock-free collections, the disadvantage is that multiple threads could perform the same operation, while only one of them would actually be taken into account. Depending on the context, this is often justified and acceptable, for these collections are introducing the best performance in concurrent processing, compared to lock usage, such repetitive processing situations are relatively rare to occur, and would usually not lead to corruption of the entire data/state.
    • Independent buckets that have their own locks is another approach that attempts to allow simultaneous use of the collection. In this approach the collection is internally split into multiple buckets with their own locks, that can be used by multiple threads. An example is a concurrent dictionary that would use internally an array of dictionaries. Based on the hash-code of the key the dictionary would decide which child dictionary to use from the corresponding thread, and will limit the lock to that child dictionary only. Another thread that would target another child dictionary will not be blocked. Alternatively, an array of lock objects can be used along a single container with quite the same effect. The problem with this approach is that the collection itself decides which bucket the current thread works on (and locks), so you do not have control of whether certain operations will really be concurrent (if manipulating by multiple buckets) or not (if they appear to affect the same bucket).
  • The number of threads dealing with a single instance of the structure simultaneously. This will determine the possibility of potential simultaneous uses that could cause blocking.

  • The ratio between read and write operations. This could help you decide which concurrent behavior from the listed above is suitable. For instance a collection that is more often being read from, than updated, would be more performant if it has a lock-free implementation, or if a read-write lock is used. The read-write lock is a special lock that allows you to control if it should block reads when a write is being performed, but to allow simultaneous reads.
  • The importance of data consistency within the structure. This is affected by the different approaches of such structure's implementation, as discussed above.

The restrictions

By restrictions I am referring to the code you are using. If you interact with a 3rd party API, or are somewhat restricted by the type of collection/structure you have to use (if you must pass it to the API's method), or you are enforced to implement certain interface, you need to find out the potential uses of this code and a suitable implementation that will fit. Most existing concurrent collection implementations would be compatible with at least the iterable and collection interfaces though.

Implementation notes

If you are going to base your structure on an existing collection, I recommend wrapping it, rather than using inheritance. Wrapping will guarantee you won't miss a method that needs to be synchronized, and will give you freedom to choose your locking behavior. You can always implement a standard collection interface in order to make your collection usable by other APIs (see restrictions section above)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.