Examples of concurrent iterating scenarios needed

Question

I'm trying to wrap my head around different concurrency solutions to several threads iterating over the same collection but I'm having difficulty coming up with good realistic (but preferably easy to model) scenarios to code against. I'm looking for realistic scenarios for:

1. A scenario where several threads can iterate over a collection simultaneously and lock each item as it comes to it and do some modification, item's can't be visible in a partially updated state
2. A scenario where different threads try to iterate over a collection but only one at a time should be allowed to
3. A scenario where several threads might iterate over a collection for reading, but only one thread might iterate for writing

Any other nice concurrency iterating scenarios you might come up with are welcome as well :) thanks!

Answer 1

I am not sure about the need to find real world scenarios.

Why not just write code with these constraints where they are trying to get access to an effectively empty null object. This eliminates the need to solve the domain problem at the same time.

Add a variable time factor to the act of "touching" the null object to add some variance -- and watch the contention go, and toggle up and down the number of contenting threads and objects.

Then log all the collisions that take place - which hopefully you would have neatly protected, or watch it deadlock and trawl through your logs to spot where the deadlock happend.

Answer 2

Collections have specific concurrency issues. I'm a .net developer, but I can describe the issues in, fairly general terms I think.

Internally the collection could be implemented in a number of different ways. Let's assume it's just a linked list.

The collection can support a number of operations. Add and delete, delete[index] and insert. It also allows you to iterate over the collection.

So you have concurrent access. Here are some situations to consider.

You are iterating over the entire collection. You are doing something like (pseudo code)

for count = 1 to collection.count do something next

For the sake of the following, count currently = 5 and collection.count = 10.

While doing this you do any of the following. Run each scenario individually:

1) Add an item to the collection. This will probably work as long as the behaviour is to insert the item at the end.

2) Insert an item at position 3 Not too bad, count goes up one, the new item won't be included in our iteration though.

3) Delete an item at position 3 Ok, now we have issues. Count is now 9 (remember do each scenario on its own, 1) and 2) haven't happened in this case). our current position is still 5, but because 3 was removed, the list has moved left, we are now going to skip an item because item 6 is now item 5, and we're already reading 5. But it gets worse!!! Imagine your stuff that you are doing with item 5 is reading members of the object at position 5 based on its index.

thread 1 --> collection[5].element1 = 10 thread 2 --> delete item 3 thread 1 --> collection[5].element2 = 10

we've actually now set two elements on different items.

It get's worse still in the next one.

4) delete item 5 while currently on item 5. Yep, you remove the item, perhaps call its "Dispose" method as you remove it but you're still treating it as an active member of the collection on another thread.

That's simple cases. Hope it gives you some ideas.

Answer 3

If you're looking for concrete examples, one scenario I'd use is a simple list of items, say the database favourite "Products". You have an inwards goods department that adds products sometimes and changes the quantity of a product often. You have an outwards goods department that often changes the quantity of a product but never adds or removes products. You have a manager who adds, deletes, renames, changes quantities and reports on products. And you have a live stocktake team who add, remove and change quantities.

That covers the common CRUD actions, and makes use cases easy to generate. If your collection is also sorted you could add location to the above and sort by that (and just use another integer property for that to make it simple). I keep emphasising sorting because that rapid remove-add cycle is tricky to test.

Answer 4

(1) would be a naiive object-oriented approach to keeping a collection of moving objects in a simulation of sorts that needs to be made visible to other threads: The "simulator" would need to lock, not only its list (to prevent slicing), but also each "object" it is updating.

Realistically, I would do that for something like a pathfinder: Lock the agent collection to prevent slicing and iterate over all agents, putting them into a "job queue" (the queue pointers would be reserved for this purpose only, so no other thread would see it).

Then, using OpenMP or something similar, I'd have each worker thread quickly lock the queue, pop an agent off of it, then unlock the queue (or use an [almost] lock-free queue). Each worker thread locks its agent before updating it.

My answer for (1) could also apply to (2): The "simulator" and whatever keeps the collection of agents are really the only things that should be allowed to iterate over the whole list (and desirably do so in one thread at a time, or just one thread period).

An examaple for (3) would be a string table: Multiple threads can obtain a shared lock to look up existing strings, and only one thread at a time can add a string to the table.

Answer 5

An example I discovered at a previous workplace:

A piece of code had a collection of frame buffers that were being updated by multiple threads. The threads were:

• A thread that received frames from the network, processed them and updated the buffer in question. (Write operation)
• A thread that converted frames to pixels for display (Read operation)
• Another piece of code that maintained the connection status of the network, and replaced the buffer with the text "Connection Lost". (Write operation)

These frame buffers weren't properly synchronised. I managed to find that the reading thread was iterating the frame buffers and pushing them to native code, when thread 3 came along and caused the entire app to crash.

In this case, reading and writing had to become exclusive (your scenario 2).